用C语言实现一个链表（四）

用C语言实现一个链表（四）

在上期内容中，我们探讨了实现一个双向循环链表的准备工作以及一些功能——创建新结点，初始化头结点，尾插数据，尾删数据，遍历的代码，上期内容留下了一个判断是否存在有效数据的函数，本期内容，我们会将其补充完整并且继续讨论其他一些功能的代码实现。

一、双向循环链表的实现（代码+分析） 1.头部插入数据

头部插入数据相对轻松，只要理解指针的链接关系即可，结合画图理解会比较轻松，如图： 代码如下：

void DCLLPushFront(DCLLNode* phead, DataType x)//这里只需要一级指针即可，因为改变的是结构体里面的内容，而不是改变结构 { assert(phead); DCLLNode* newnode = CreateDCLLNode(x);//创建一个新结点 newnode->next = phead->next;//新结点的next指向头结点的下一个结点 phead->next->prev = newnode;//原来头结点的下一个结点的prev指向新结点 phead->next = newnode;//头结点的next指向新结点 newnode->prev = phead;//新结点的prev指向头结点 } 2.判断是否存在有效数据

函数用来判断是双向循环链表是否为空。 存在有效数据就返回0（不为空），不存在有效数据就返回1（为空），代码如下：

bool DCLLisEmpty(DCLLNode* phead) { assert(phead); return phead->next == phead;//如果phead的next还是phead，就说明双向循环链表只有一个头结点，并没有存入了数据的新结点 } 3.头部删除数据

结合图示理解： 代码如下：

void DCLLPopFront(DCLLNode* phead) { assert(phead); assert(!DCLLisEmpty(phead)); DCLLNode* front = phead->next; phead->next = phead->next->next; phead->next->prev = phead; free(front); front = NULL; } 4.特定位置寻找

寻找就是遍历，要注意的还是循环条件的控制，代码如下：

DCLLNode* DCLLFind(DCLLNode* phead, DataType x) { assert(phead); DCLLNode* cur = phead->next;//可以移动的指针指向第一个存储有效数据的结点 while (cur != phead)//循环条件的控制和遍历相同 { if (cur->data == x) { return cur;//找到了，就返回对应结点的地址 } cur = cur->next; } return NULL;//找不到就返回一个空指针 } 5.特定位置插入数据

结合图示理解： 代码如下：

void DCLLInsert(DCLLNode* pos, DataType x)//在特定位置插入数据，需要提供对应的地址和数据 { assert(pos); DCLLNode* newnode = CreateDCLLNode(x);//创建新结点 DCLLNode* prev = pos->prev;//这里是在特定位置的前面插入 prev->next = newnode;//特定位置的前一个结点的next指向新结点 newnode->prev = prev;//新结点的prev指向的就是特定位置的前一个结点 newnode->next = pos;//新结点的next指向特定位置的结点 pos->prev = newnode;//特定位置结点的prev指向新结点 } 6.特定位置删除

结合图示理解： 代码如下：

void DCLLErase(DCLLNode* pos)//在特定位置删除，需要提供特定位置的地址 { assert(pos); pos->prev->next = pos->next;//删除的是特定位置本身，它的前一个结点的next指向特定位置的后一个结点 pos->next->prev = pos->prev;//后一个结点的prev指向特定位置的前一个结点 free(pos);//释放特定位置的空间 pos = NULL; } 7.双向循环链表的销毁

和单链表一样，在销毁每一个结点时，要注意保存下一个结点的地址，代码如下：

void DCLLDestroy(DCLLNode* phead) { assert(phead); DCLLNode* cur = phead->next; while (cur != phead) { DCLLNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } 8.运行测试

代码如下：

int main() { DCLLNode* plist = DCLLInit();//初始化头结点 DCLLPushBack(plist, 1);//尾插数据 DCLLPushBack(plist, 2); DCLLPushBack(plist, 3); DCLLPushBack(plist, 4); DCLLPushBack(plist, 5); DCLLPushBack(plist, 6); DCLLPushBack(plist, 7); DCLLPrint(plist);//遍历 DCLLPushFront(plist, 1);//头插数据 DCLLPushFront(plist, 2); DCLLPushFront(plist, 3); DCLLPushFront(plist, 4); DCLLPushFront(plist, 5); DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLNode* ret = DCLLFind(plist, 4);//寻找数据域为4的结点，返回它的地址 DCLLInsert(ret, 9);//在4前面插入9 DCLLPrint(plist);//遍历 DCLLErase(ret);//删除数据域为4的这一结点 DCLLPrint(plist);//遍历 DCLLDestroy(plist);//销毁 return 0; }

运行结果如图：

二、使用头文件——将声明与定义分离 1.头文件——DCLL.h

在双向循环链表中，我们为了实现它的基本功能，写了很多的函数，如果我们将结构体，函数的声明，函数的定义，以及函数的调用测试写在同一个源文件中，会大大降低代码的可读性和可维护性；因此，我们可以将结构体以及一些函数的声明放在头文件DCLL.h中，代码如图：

2.源文件——DCLL.c

在源文件DCLL.c中，我们存放函数具体实现的代码，在第一行应加上 #include"DCLL.h"，代码如下：

#include"DCLL .h" DCLLNode* CreateDCLLNode(DataType x) { DCLLNode* node = (DCLLNode*)malloc(sizeof(DCLLNode));//创建一个新结点 if (node == NULL)//判断动态内存开辟是否成功 { perror("malloc fail"); return NULL; } node->data = x;//对新结点 的数据域赋值 node->next = NULL;//对新结点的指针域赋值 node->prev = NULL;//对新结点的指针域赋值 return node;//返回的是一个指针，指向新创建的节点 } DCLLNode* DCLLInit() { DCLLNode* phead = CreateDCLLNode(-1); phead->next = phead;//当还没有开始插入新结点时，头结点的next指向的是头结点本身 phead->prev = phead;//当还没有开始插入新结点时，头结点的prev指向的也是头结点本身 return phead;//返回的是头结点的地址 } void DCLLPrint(DCLLNode* phead) { assert(phead); DCLLNode* cur = phead->next; printf("<=head=>"); while (cur!=phead)//最后一个结点的特点就是它的next指向的是头结点，因此指针指向头结点是就说明双向循环链表遍历结束了 { printf("%d<=>", cur->data); cur = cur->next;//cur向后移动，指向下一个结点 } printf("\n"); } void DCLLPushBack(DCLLNode* phead, DataType x)//这里只需要一级指针即可，因为改变的是结构体里面的内容，而不是改变结构体指针 { assert(phead); DCLLNode* newnode = CreateDCLLNode(x);//创建一个新结点 DCLLNode* tail = phead->prev;//头结点的prev指针就是指向的尾部结点 tail->next = newnode;//尾结点的next指向插入的新结点 newnode->prev = tail;//新结点的prev指向的是尾结点（双向链接） newnode->next = phead;//新结点的next就是接上了头结点 phead->prev = newnode;//而头结点的prev又连上了尾结点（新结点） } bool DCLLisEmpty(DCLLNode* phead) { assert(phead); return phead->next == phead;//如果phead的next还是phead，就说明双向循环链表只有一个头结点，并没有存入了数据的新结点 } void DCLLPopBack(DCLLNode* phead) { assert(phead); assert(!DCLLisEmpty(phead));//双向循环链表有数据才能删除数据 DCLLNode* tail = phead->prev;//新建一个DCLLNode型结构体指针，指向尾结点 DCLLNode* tailprev = tail->prev;//新建一个DCLLNode型结构体指针，指向尾结点的前一个结点 tailprev->next = phead;//尾结点的前一个结点不再指向尾结点，而是指向头结点 phead->prev = tailprev;//头结点的prev指向为现在的尾结点 free(tail);//释放刚才尾结点的空间 tail = NULL; } void DCLLPushFront(DCLLNode* phead, DataType x)//这里只需要一级指针即可，因为改变的是结构体里面的内容，而不是改变结构 { assert(phead); DCLLNode* newnode = CreateDCLLNode(x);//创建一个新结点 newnode->next = phead->next;//新结点的next指向头结点的下一个结点 phead->next->prev = newnode;//原来头结点的下一个结点的prev指向新结点 phead->next = newnode;//头结点的next指向新结点 newnode->prev = phead;//新结点的prev指向头结点 } void DCLLPopFront(DCLLNode* phead) { assert(phead); assert(!DCLLisEmpty(phead)); DCLLNode* front = phead->next; phead->next = phead->next->next; phead->next->prev = phead; free(front); front = NULL; } DCLLNode* DCLLFind(DCLLNode* phead, DataType x) { assert(phead); DCLLNode* cur = phead->next;//可以移动的指针指向第一个存储有效数据的结点 while (cur != phead)//循环条件的控制和遍历相同 { if (cur->data == x) { return cur;//找到了，就返回对应结点的地址 } cur = cur->next; } return NULL;//找不到就返回一个空指针 } void DCLLInsert(DCLLNode* pos, DataType x)//在特定位置插入数据，需要提供对应的地址和数据 { assert(pos); DCLLNode* newnode = CreateDCLLNode(x);//创建新结点 DCLLNode* prev = pos->prev;//这里是在特定位置的前面插入 prev->next = newnode;//特定位置的前一个结点的next指向新结点 newnode->prev = prev;//新结点的prev指向的就是特定位置的前一个结点 newnode->next = pos;//新结点的next指向特定位置的结点 pos->prev = newnode;//特定位置结点的prev指向新结点 } void DCLLErase(DCLLNode* pos)//在特定位置删除，需要提供特定位置的地址 { assert(pos); pos->prev->next = pos->next;//删除的是特定位置本身，它的前一个结点的next指向特定位置的后一个结点 pos->next->prev = pos->prev;//后一个结点的prev指向特定位置的前一个结点 free(pos);//释放特定位置的空间 pos = NULL; } void DCLLDestroy(DCLLNode* phead) { assert(phead); DCLLNode* cur = phead->next; while (cur != phead) { DCLLNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } 3.源文件——Test.c

在源文件Test.c中调用双向循环链表的功能函数，完成测试，当然第一行还是得写上 #include"DCLL.h" 。在这里，我们将上期和这期的内容结合在一起，写了两个测试函数 void Test_one()和void Test_two()，代码如下：

#define _CRT_SECURE_NO_WARNINGS #include"DCLL .h" void Test_one() { DCLLNode* plist = DCLLInit();//初始化头结点 DCLLPushBack(plist, 1);//尾插数据 DCLLPushBack(plist, 2); DCLLPushBack(plist, 3); DCLLPushBack(plist, 4); DCLLPushBack(plist, 5); DCLLPrint(plist);//遍历 DCLLPopBack(plist);//尾删数据 DCLLPrint(plist);//遍历 DCLLPopBack(plist);//尾删数据 DCLLPrint(plist);//遍历 DCLLPopBack(plist);//尾删数据 DCLLPrint(plist);//遍历 DCLLPopBack(plist);//尾删数据 DCLLPrint(plist);//遍历 DCLLPopBack(plist);//尾删数据 DCLLPrint(plist);//遍历 } void Test_two() { DCLLNode* plist = DCLLInit();//初始化头结点 DCLLPushBack(plist, 1);//尾插数据 DCLLPushBack(plist, 2); DCLLPushBack(plist, 3); DCLLPushBack(plist, 4); DCLLPushBack(plist, 5); DCLLPushBack(plist, 6); DCLLPushBack(plist, 7); DCLLPrint(plist);//遍历 DCLLPushFront(plist, 1);//头插数据 DCLLPushFront(plist, 2); DCLLPushFront(plist, 3); DCLLPushFront(plist, 4); DCLLPushFront(plist, 5); DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLPopFront(plist);//头删数据 DCLLPrint(plist);//遍历 DCLLNode* ret = DCLLFind(plist, 4);//寻找数据域为4的结点，返回它的地址 DCLLInsert(ret, 9);//在4前面插入9 DCLLPrint(plist);//遍历 DCLLErase(ret);//删除数据域为4的这一结点 DCLLPrint(plist);//遍历 DCLLDestroy(plist);//销毁 } int main() { Test_one(); Test_two(); return 0; } 三、本期总结+下期预告

本期内容书接上回，完成了带头双向循环链表的C语言实现，下期将为大家带来栈和队列的内容！

感谢大家的关注，我们下期再见！