试图在双向链表的中间插入新节点时，我错了吗？

结构看上去像：试图在双向链表的中间插入新节点时，我错了吗？

class DList{ 
private: 
     struct Elem { 
     Elem *prev, *next; 
     }; 
     Elem *_head, *_tail; 
}

现在我有两个现有节点：CUR和CUR->接下来，我想插入它们之间的新节点插件。这是我做的：

cur->next = ins;//step-1-1 cur 
    ins->prev = cur;//step-1-2 cur 

    ins->next = cur->next;//step-2-1 cur->next 
    cur->next->prev = ins;//step-2-2 cur->next

问题是在我的程序的进一步遍历循环我的指针无法再达到_tail了。我在插入部分中是否有什么东西？（一旦我评论上面的中间代码的插入，循环完美工作）

来源

2017-10-09 Ray-Von-Mice

当你做'ins-> next = cur-> next'时，你已经设置了'cur-> next = ins'。所以你最终与'ins-> next == ins' –

@IgorTandetnik步骤2-1设置钩子插入和原始cur->下一个节点，有两个，所以我认为我必须钩两个 –

那么，是的，这就是你的意图 - 但那时你已经失去了指向**原始**'cur-> next'节点的指针。 'cur-> next'不再指向所述原始节点，而是指向'ins'。 –

是的，这里有一个接线错误。让我们画画吧！

想象的事情是这样的，首先：

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | ----------------------> | next | --> ... 
     +----------+       +----------+ 
... <-- | prev | <---------------------- | prev | <-- ... 
     +----------+       +----------+ 
          +----------+ 
          | next | 
          +----------+ 
          | prev | 
          +----------+ 
           ^
           | 
           ins

首先，执行cur->next = ins;，它将会：

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
          +----------+ 
          | next | 
          +----------+ 
          | prev | 
          +----------+ 
           ^
           | 
           ins

请注意，我们不再有一个指针原是元素curr之后 - 哎呀！那会在稍后出现问题。现在

，我们做ins->prev = curr;，它看起来像这样：

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
      ^   +----------+ 
       |   | next | 
       |   +----------+ 
       +---------- | prev | 
          +----------+ 
           ^
           | 
           ins

现在，我们写ins->next = curr->next;。但哎呀！请注意，curr->next点ins，所以我们只是在这里增加了一个循环：

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
      ^   +----------+ 
       |   | next | --+ 
       |   +----------+ | 
       +---------- | prev | <-+ 
          +----------+ 
           ^
           | 
           ins

最后，你写cur->next->prev = ins;但糟糕！curr->next仍然prev，所以我们得到一个循环：

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
          +----------+ 
         +-> | next | --+ 
         | +----------+ | 
         +-- | prev | <-+ 
          +----------+ 
           ^
           | 
           ins

这里的问题是，你失去跟踪小区的第一次分配后指向由curr->next，让你失去了在正确的地方看的能力。

如果你从写这样的东西开始呢？

DList* next = curr->next;

然后用next代替curr->next在一些情境？

来源

2017-10-09 02:53:33 templatetypedef

不用担心！这种绘制图片的方法在处理链表时非常有用。我一直在做这个多年，仍然觉得它对我自己有帮助！ – templatetypedef

关键是不丢失将在稍后使用的值。您的第一行代码cur->next = ins;会使您失去原始值(cur->next);此后你真的不知道谁将会是next到ins。

使用此逻辑在中间插入新节点。比方说，最初，

cur - cur->next 
    | 
    [ins]

做的，

ins->next = cur->next;

（现）（INS） - （CUR->旁边）{假设 - 明年，并为= next和prev}

cur->next = ins;

（CUR） - （INS） - （CUR->下）

ins->prev = cur;

CUR =插件 - （CUR->旁边）

ins->next->prev = ins;

CUR =插件=（CUR-下一页>）

来源

2017-10-09 02:50:31

试图在双向链表的中间插入新节点时，我错了吗？

回答

相关问题