嘉义县网站建设_网站建设公司_导航易用性_seo优化

1.链表的分类

如图所示，链表具有以下不同特征，所以有2*2*2=8种不同的链表。

在上一篇文章中我们介绍的是单链表，Technically speaking,单向不带头不循环链表

这次我们就要来实现一下双向带头循环链表。

2.双向链表的具体实现

我实在是太懒了，还是跟前面单链表和顺序表一样要用两个.c文件，一个.h文件，不多说了。

双向链表的一个节点中包含三部分

1.存储的数据

2.指向下个节点的指针

3.指向前一个节点的指针。

用图表就是这样：

（1）初始化LTNode** pphead /LTNode* LTInit()

第一种方法显而易见，因为形参要对实参的改变做出影响，所以需要传地址。第二种方法呢，后面我们再介绍为什么要用。

初始化的时候需要创建一个新节点，也就是要动态开辟空间，这就涉及到了第二个函数

LTNode* LTBuyNode(LTDataType x)，

大体还是与之前单链表开辟空间大差不差，一样要判断空间是否开辟成功，然后将数据x存储在节点的data中，但这里，新开辟节点的两个指针都要指向本身，而不能置为NULL，因为我们要创建的是循环链表，如果置为NULL，就无法做到循环，而如果指向自己，则后面就可以通过插入数据实现循环效果

这就是新开辟出来的节点的效果，当然因为第一个开辟的节点是哨兵位，不存储任何有效数据。

在监视窗口中就可以清晰的看到，plist已经有一个哨兵位节点，next,prev指针均指向自己初始化步骤完成。

最后跟大家区分一个点，链表为空，代表链表中没有有效节点，也就是只有一个哨兵位节点，而链表无效证明连哨兵位都没有，这俩并不对等。

（2）尾插void LTPushBack(LTNode* phead, LTDataType x);

首先来画个图理解一下

先开辟一个newnode节点并调整newnode中两个指针的指向,确保原链表不受影响。

1.newnode此时的下个节点为哨兵位(newnode->next=head)

2.原来的尾节点d3的下一个节点调整为为newnode(newnode->prev=head->prev，其中head->prev表示原先的尾节点)

接下来调整剩下的两个指针

1.让原先尾节点d3指向下个节点的指针现在指向newnode(head->prev->next=newnode,其中head->prev表示原先的尾节点)

2.哨兵位的上一个节点要调整为newnode（head->prev=newnode）

尾插代码完成，进行测试前需要再写一个打印链表的函数

与单链表基本一致，断言链表有效且链表不为空，定义pcur指向哨兵位的下一个节点，也就是第一个有效节点，而循环则是在pcur遍历到哨兵位时结束。

打印结果：

尾插成功。

（3）头插void LTPushFront(LTNode* phead, LTDataType x);

头插并不是插在哨兵位之前，否则就与尾插相同了，头插是指插在哨兵位之后一个节点。

参考尾插，先改变newnode节点中的指针

1.newnode的下个节点调整为d1(newnode->next=head->next，head->next即d1)

2.newnode的前一个节点为哨兵位(newnode->prev=head)

然后再改变指向newnode的指针

1.哨兵位的下个节点为newnode(head->next=newnode)

2.d1的前一个节点为newnode(newnode->next->prev=newnode，此时newnode->next就是d1节点)

根据上述思路写出代码即可。

测试成功。

（4）尾删void LTPopBack(LTNode* phead);

还是先看图，为了方便理解，定义del指针指向双向链表的尾节点，防止后面要删除的节点丢失。

1.哨兵位上一个节点为尾节点的前一个节点(head->prev=del->prev)

2.尾节点的前一个节点此时指向哨兵位(del->prev->next=head,del->prev即为尾节点的前一个节点)

3.最后释放del指针指向的节点并手动置NULL

测试：

（5）头删void LTPopFront(LTNode* phead);

其实还是改变几个指针的指向，断言链表有效且链表不为空。

1.修改哨兵位的下一个节点为d2，(head->next=del->next)

2.d2的前一个节点修改为哨兵位(del->next->prev=head，此时del->next为d2)

测试：

（6）查找LTNode*LTFind(LTNodephead,LTDataType x);

不过多赘述，断言+遍历即可实现，若找到则返回指向节点的指针，若未找到则返回NULL。

（7）插入void LTInsert(LTNode* pos, LTDataType x);

利用查找时返回的下标(pos)实现这个功能，还是一步步梳理改变的指针指向，如图

先改变插入的节点newnode中的两个指针的指向：

1.newnode的下一个节点是原先pos的下一个节点d3(newnode->next=pos->next)

2.newnode的前一个节点是pos(newnode->prev=pos)

再改变指向newnode的两个指针(下面两行代码的顺序不能调换)：

1.d3的前一个节点要修改为newnode(pos->next->prev=newnode，这里pos->next即为d3)

2.pos的下一个节点是newnode(pos->next=newnode)

实现并测试完成。

（8）删除指定位置void LTErase(LTNode* pos);

处理与pos有关的四个指针：

1..d3指向上个节点的指针现在指向d1(pos->next->prev=pos->prev，pos->next即为d3)

2.d1中指向下个节点的指针现在要指向pos的下个节点d3(pos->prev->next=pos->next，pos->prev即为d1)

3.释放pos节点并置为NULL

（9）销毁void LTDestroy(LTNode* phead);

说到这里了，还记得前面初始化的时候提到的另一种方法吗？

LTNode* LTInit()，这种初始化与前面相比更好，因为能够更好的保持接口一致性。也就是传递的都是一级指针，就无需做区分。

因此我们可采用这种返回节点的初始化方式，更加清晰。

那么说回销毁，也是遍历然后释放节点即可。

不过这里有些巧妙的是，定义pcur遍历链表，但是在循环内定义了一个next指针，每次都指向pcur的下一个节点，而释放完pcur节点后，pcur会走到Next的位置，还是比较巧妙的。最后pcur走到哨兵位跳出循环，但是哨兵位还未被销毁，因此还要再销毁一次。

还没有结束！因为我们传的是一级指针，实参还要手动置为空

验证一下：

监视中显示此时数据都被销毁，而最后一步置空即可。

这就是双向链表实现的全过程，我发现不用遍历链表还是比较爽的。

又要爽爽写高数和线代了！