【 C 】在双链表中插入一个新值的简明程序
上两篇博文讲了如何在单链表中插入一个值：
这篇博文讲解如何在双链表中插入一个值。
单链表的替代方案就是双链表。在一个双链表中，每个节点都包含两个指针——指向前一个节点的指针和指向后一个节点的指针。这可以使我们以任何方向遍历双链表，甚至可以忽前忽后地在双链表中访问。下图展示了一个双链表：
下面是节点类型的声明：
-
typedef struct NODE
-
{
-
struct NODE *fwd;
-
struct NODE *bwd;
-
int value;
-
} Node;
现在，存在两个根指针：一个指向链表的第一个节点，另一个指向链表的最后一个节点。这两个指针允许我们从链表的任何一端开始遍历链表。
我们可能想把两个根指针分开声明为两个变量。但这样一来，我们必须把两个指针都传递给插入函数。为根指针声明一个完整的节点更为方便，（下面的例子也是这么做的），只是它的值字段绝不会被使用。在我们的例子中，这个技巧只是浪费了一个整型值的内存空间。对于值字段非常大的链表，分开声明两个指针可能更好一些。另外，我们也可以在根节点的值字段中保存其他一些关于链表的信息，例如链表当前包含的节点数量。
根节点的fwd字段指向链表的第一个节点，根节点的bwd字段指向链表的最后一个节点。如果链表为空，这两个字段都为NULL。链表的第一个节点的bwd字段和最后一个节点的fwd字段都为NULL。在一个有序的链表中，各个节点将根据value字段的值以升序排列。
下面，我们编写一个函数，把一个值插入一个有序的双链表中。dll_insert函数接受两个参数：一个指向根节点的指针和一个需要插入的整型值。
开头提到的两个博文，在单链表中插入函数把重复的值也添加到链表中。在有些应用程序中，不插入重复的值可能更为合适。下面在双链表中插入一个值就是这种情况，dll_insert函数只有当欲插入的值原先不存在于链表中时才将其插入！
让我们以一种更为规范的方法来编写这个函数。当我们把一个节点插入一个链表中时，可能出现4中情况：
- 新值可能必须插入到链表的中间位置；
- 新值可能必须插入到链表的起始位置；
- 新值可能必须插入到链表的结束位置；
- 新值可能既插入到链表的起始位置又插入到链表的结束位置。
在情况1和2，新节点的fwd字段必须设置为指向链表的下一个节点的指针，链表的下一个节点的bwd字段必须设置为指向这个新节点。
在情况3和4，新节点的fwd字段必须设置为NULL，根节点的bwd字段必须设置为指向新节点。
在情况1和3，新节点的bwd字段必须设置为指向链表的前一个节点，而链表前一个节点的fwd字段必须设置为指向新节点 。
在情况2和4，新节点的bwd字段必须设置为NULL，根节点的fwd字段必须设置为指向新节点。
为了让认识更为清晰，我画了一个示意图，示意双链表节点之间的情况：
下面的程序就是根据这来设计的，认真体会，或许更为清晰：
程序：
-
//简明的双链表插入函数
-
//把一个值插入到一个双链表中，rootp是一个指向根节点的指针，value是要插入的新值
-
//返回值：如果欲插值原先已经存在与链表中，函数返回0
-
//如果内存不足导致无法插入，返回返回-1；如果插入成功，函数返回1
-
-
#include < stdlib.h>
-
#include < stdio.h >
-
#include < dll_node.h > //这是自己建立的一个头文件，用于保存双链表的节点声明
-
-
int dll_insert( Node *rootp, int new_value )
-
{
-
Node *this; //指向新节点之前的那个节点
-
Node *next; //指向新节点之后的那个节点
-
Node *newnode; //指向新节点本身
-
-
//查看value是否已经存在于链表中，如果是就返回。
-
//否则，为新值创建一个新的节点（newnode将指向它)
-
for( this = rootp; ( next = this->fwd ) != NULL; this = next )
-
{
-
if( next->value == new_value ) //如果插入的新值在链表中已经存在，则返回0，不需要插入
-
return 0;
-
if( next->value > new_value ) //如果插入的新值小于当前节点的值，则直接跳出循环，也就是需要在该节点之前插入新值
-
break;
-
//如果上面两种情况都不是，则插入的新值大于当前节点的值，继续循环
-
}
-
-
//为新节点开辟内存空间
-
newnode = ( Node*)malloc( sizeof( Node ) );
-
if( newnode == NULL )
-
return -1; //如果内存分配不成功，则返回 -1；
-
newnode->value = new_value; //为新节点赋新值
-
-
if( next != NULL ) //这个条件的意思是新节点并非位于链表尾部
-
{
-
if(this != rootp ) //新节点并非位于链表起始位置
-
{
-
newnode->fwd = next;
-
this->fwd = newnode;
-
newnode->bwd = this;
-
next->bwd = newnode;
-
}
-
else //新节点位于链表起始位置
-
{
-
newnode->fwd = next;
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
next->bwd = newnode;
-
}
-
}
-
else //新节点位于链表的尾部
-
{
-
if( this != rootp ) //新节点并非位于链表的起始位置（链表不为空）
-
{
-
newnode->fwd = NULL;
-
this->fwd = newnode;
-
newnode->bwd = this;
-
rootp->bwd = newnode;
-
}
-
else
-
{
-
//新节点既位于起始位置，又位于尾部，也就是说原链表为空
-
newnode->fwd = NULL;
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
rootp->bwd = newnode;
-
-
}
-
}
-
-
-
-
return 1;
-
-
-
-
}
一开始，函数使 this 指向根节点。next 指针始终指向 this 之后的那个节点。它的思路是这两个指针同步前进，直到新节点应该插入这两者之间。for循环检查next所指向的节点的值，判断是否到达需要插入的位置。
如果在链表中找到新值，也就是说链表中本身就存在需要插入的新值：
-
if( next->value == new_value ) //如果插入的新值在链表中已经存在，则返回0，不需要插入
-
return 0;
那么就简单的返回。否则，当到达链表尾部（
( next = this->fwd ) == NULL
）或者找到适当的插入位置：
-
if( next->value > new_value ) //如果插入的新值小于当前节点的值，则直接跳出循环，也就是需要在该节点之前插入新值
-
break;
循环终止。
在任何一种情况下，新节点都应该插入到 this 指向的节点的后面。注意，在我们决定新值是否应该实际插入到链表之前，并不为它分配内存。如果事先分配内存，如果发现新值原先已经存在于链表中，就有可能发生内存泄露。
当我们把12插入到链表中时，观察下情况：下面这张图显示了for循环终止之后几个变量的状态。
然后，函数为新节点分配内存，下面几条语句执行之后，
-
newnode->fwd = next;
-
this->fwd = newnode;
链表的样子如下：
然后，执行下列语句：
-
newnode->bwd = this;
-
next->bwd = newnode;
这就完成了把新值插入到链表中的过程：
文章来源: reborn.blog.csdn.net，作者：李锐博恩，版权归原作者所有，如需转载，请联系作者。
原文链接：reborn.blog.csdn.net/article/details/82665322
- 点赞
- 收藏
- 关注作者
评论（0）