【 C 】简化双链表插入函数（对在双链表中插入一个新值的简明程序的简化）
【摘要】 目录
背景
第一个技巧是语句提炼（statement factoring）
第二个简化技巧
最终简化版本
背景
上篇博文：【 C 】在双链表中插入一个新值的简明程序，讲了一个简明的双链表插入函数，那个函数写的比较中规中矩，就是按照思维逻辑写的，几乎谁都懂，但是程序未免有些冗余，对于优秀的程序员来说，出现这么多的重复代码会感到厌烦。（《c与指针》说的优秀的程序员呀...
目录
第一个技巧是语句提炼（statement factoring）
背景
上篇博文：【 C 】在双链表中插入一个新值的简明程序，讲了一个简明的双链表插入函数，那个函数写的比较中规中矩，就是按照思维逻辑写的，几乎谁都懂，但是程序未免有些冗余，对于优秀的程序员来说，出现这么多的重复代码会感到厌烦。（《c与指针》说的优秀的程序员呀，什么时候我也能对此感到厌烦呀！）
下面给出一些技巧来消除这些重复的代码：
先把上篇博文中代码贴出来，这篇博文就是以此为基础，来提炼它：
-
//简明的双链表插入函数
-
//把一个值插入到一个双链表中，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;
-
-
-
-
}
上面的这段代码中最需要提炼的这部分（把新节点插入到链表中）：
-
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;
-
-
}
-
}
第一个技巧是语句提炼（statement factoring）
如下面的例子所示：
-
if( x == 3 )
-
{
-
i = 1;
-
...
-
j = 2;
-
}
-
else
-
{
-
i = 1;
-
...
-
j = 2;
-
}
注意不管表达式 x == 3的值是真还是假，语句 i = 1 和 j = 2 都将执行。在 if 之前执行 i = 1 将不会影响 x == 3 的测试结果，所以这两条语句都可以被提炼出来，这样就产生了同样简单但同样完整的语句：
-
i = 1;
-
if( x == 3 )
-
{
-
...
-
}
-
else
-
{
-
...
-
}
-
j = 2;
警告：如果if之前的语句会影响到测试的结果，那么千万不能把它提取出来，例如，下面的例子：
-
if( x == 3 )
-
{
-
x = 0;
-
...
-
}
-
else
-
{
-
x = 0;
-
...
-
}
语句x = 0，如果提到if之前那就完蛋了。
根据这个语句提炼的技巧，我们来处理插入链表程序的第一个简化：（简化1）
-
if( next != NULL ) //这个条件的意思是新节点并非位于链表尾部
-
{
-
newnode->fwd = next; //只要新节点不位于链表尾部，新节点的前向指针就指向下一个节点
-
if(this != rootp ) //新节点并非位于链表起始位置
-
{
-
this->fwd = newnode;
-
newnode->bwd = this;
-
}
-
else //新节点位于链表起始位置
-
{
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
}
-
next->bwd = newnode; //只要新节点不位于链表尾部，next指向的节点的后向指针就指向新节点
-
}
-
else //新节点位于链表的尾部
-
{
-
newnode->fwd = NULL; //新节点位于链表的尾部，则新节点的前向指针为空（NULL）
-
if( this != rootp ) //新节点并非位于链表的起始位置（链表不为空）
-
{
-
this->fwd = newnode;
-
newnode->bwd = this;
-
}
-
else
-
{
-
//新节点既位于起始位置，又位于尾部，也就是说原链表为空
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
}
-
rootp->bwd = newnode; //新节点位于链表尾部，那么根节点的后向指针就指向新节点
-
}
根据上面的技巧简化了下，道理也能说得通，程序也没有那么冗余了。确实不错！
第二个简化技巧
用下面的例子说明：
-
if( pointer != NULL )
-
field = pointer;
-
else
-
field = NULL;
这段代码的意图就是设置一个和 pointer 相等的变量，如果pointer 未指向任何东西，这个变量就设置为 NULL。但是，请看下面这条语句：
field = pointer;
和上面的那条语句功能完全一致！但是简洁很多。
根据这个情况，我们可以把（简化1）程序中的这条语句改进下：
-
if( next != NULL ) //这个条件的意思是新节点并非位于链表尾部
-
{
-
newnode->fwd = next; //只要新节点不位于链表尾部，新节点的前向指针就指向下一个节点
-
...
-
}
-
else //新节点位于链表的尾部
-
{
-
newnode->fwd = NULL; //新节点位于链表的尾部，则新节点的前向指针为空（NULL）
-
...
-
}
改为（简化2）：
-
if( next != NULL ) //这个条件的意思是新节点并非位于链表尾部
-
{
-
newnode->fwd = next; //只要新节点不位于链表尾部，新节点的前向指针就指向下一个节点
-
...
-
}
-
else //新节点位于链表的尾部
-
{
-
newnode->fwd = next; //新节点位于链表的尾部，则新节点的前向指针为空（NULL）
-
...
-
}
上面的改动引起了连锁效应，因为技巧1中可以再次对（简化2）进行提炼，如下：
-
newnode->fwd = next;
-
if( next != NULL ) //这个条件的意思是新节点并非位于链表尾部
-
{
-
...
-
}
-
else //新节点位于链表的尾部
-
{
-
...
-
}
上面比较完整的程序版本是这样的：
-
-
newnode->fwd = next;
-
if( next != NULL ) //这个条件的意思是新节点并非位于链表尾部
-
{
-
if(this != rootp ) //新节点并非位于链表起始位置
-
{
-
this->fwd = newnode;
-
newnode->bwd = this;
-
}
-
else //新节点位于链表起始位置
-
{
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
}
-
next->bwd = newnode; //只要新节点不位于链表尾部，next指向的节点的后向指针就指向新节点
-
}
-
else //新节点位于链表的尾部
-
{
-
if( this != rootp ) //新节点并非位于链表的起始位置（链表不为空）
-
{
-
this->fwd = newnode;
-
newnode->bwd = this;
-
}
-
else
-
{
-
//新节点既位于起始位置，又位于尾部，也就是说原链表为空
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
}
-
rootp->bwd = newnode; //新节点位于链表尾部，那么根节点的后向指针就指向新节点
-
}
亮瞎纯钛合金眼镜的时刻到了，嵌套的两个if语句竟然完全一致，这样就出大事了，根据技巧1，可以把这两个嵌套内的if语句提出来，如下：（简化3）
-
-
newnode->fwd = next;
-
-
if(this != rootp )
-
{
-
this->fwd = newnode;
-
newnode->bwd = this;
-
}
-
else
-
{
-
rootp->fwd = newnode;
-
newnode->bwd = NULL;
-
}
-
-
if( next != NULL )
-
{
-
next->bwd = newnode;
-
}
-
else
-
{
-
rootp->bwd = newnode;
-
}
最后一次需要简化的是第一个if语句，用第2个技巧简化：
-
-
newnode->fwd = next;
-
this->fwd = newnode;
-
-
if(this != rootp )
-
{
-
-
newnode->bwd = this;
-
}
-
else
-
{
-
newnode->bwd = NULL;
-
}
-
-
if( next != NULL )
-
{
-
next->bwd = newnode;
-
}
-
else
-
{
-
rootp->bwd = newnode;
-
}
最终简化版本
那最后给出最终完整版本：
-
-
-
//简明的双链表插入函数
-
//把一个值插入到一个双链表中，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; //为新节点赋新值
-
-
-
newnode->fwd = next;
-
this->fwd = newnode;
-
-
if(this != rootp )
-
{
-
newnode->bwd = this;
-
}
-
else
-
{
-
newnode->bwd = NULL;
-
}
-
-
if( next != NULL )
-
{
-
next->bwd = newnode;
-
}
-
else
-
{
-
rootp->bwd = newnode;
-
}
-
-
return 1;
-
-
}
过程很有意思，但是我却不愿意读了。。。
程序真的很简化了，简化到了我恐怕都不认识了。也许是我菜吧！供大家参考！
文章来源: reborn.blog.csdn.net，作者：李锐博恩，版权归原作者所有，如需转载，请联系作者。
原文链接：reborn.blog.csdn.net/article/details/82686235
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）