-4

任何人都可以给我链接或好的教程或任何给出插入和删除双链表的书的链接。我需要创建 2 个函数：一个用于在一个位置之后插入一个元素并在一个位置之后删除一个元素。我发现了许多在线程序，但完全不了解其背后的算法或逻辑。谁能解释我在某个节点之后插入或删除发生了什么？到目前为止，我所理解的是 node 被全局声明为：

 struct node{
             struct node *prev;
             struct node *next;
             int info;
            }*start;

这是什么*start意思？

4

1 回答 1

2

假设您迭代直到第 N 个元素（通过索引或搜索条件找到）。

插入

您想在 *Nth 和 Nplus1th = Nth->next 之间插入节点 fooitem

1）备份Nth->next的引用

node *Nplus1th = Nth->next; //save it for now

2）覆盖第N个->下一个

Nth->next = &fooitem; //The next of Nth references fooitem

3) 将 fooitem 的 next 设置为 this->next 的备份引用

fooitem.next = Nplus1th;

4) 将备份的上一个设置在 fooitem 引用旁边

Nplus1th->prev = &fooitem;

5) 将 fooitem prev 设置为 Nth

fooitem.prev = Nth;

删除

您想删除 *Nth 和 Nplus1th = Nth->next 之间的节点 fooitem

node *fooitem = Nth->next;
Nth->next= fooitem->next; //"forward bridge" to next->next
fooitem->next->prev = Nth; //"backward bridge" to prev->prev

//Delete references for safety
fooitem->prev=NULL;
fooitem->next=NULL;

return fooitem;

重要提示：以上代码假定第 (N+1) 个节点不为 NULL。在尝试访问此节点的下一个或上一个引用时，必须包含检查以验证此假设。

于 2013-09-12T13:24:25.107 回答