当前位置：首页 > news >正文

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

news 来源：原创 2025/9/12 3:15:43

用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前面插入9DCLLPrint(plist);//遍历DCLLErase(ret);//删除数据域为4的这一结点DCLLPrint(plist);//遍历DCLLDestroy(plist);//销毁return 0;
}

运行结果如图：
运行测试

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

1.头文件——DCLL.h

在双向循环链表中，我们为了实现它的基本功能，写了很多的函数，如果我们将结构体，函数的声明，函数的定义，以及函数的调用测试写在同一个源文件中，会大大降低代码的可读性和可维护性；因此，我们可以将结构体以及一些函数的声明放在头文件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前面插入9DCLLPrint(plist);//遍历DCLLErase(ret);//删除数据域为4的这一结点DCLLPrint(plist);//遍历DCLLDestroy(plist);//销毁
}int main()
{Test_one();Test_two();return 0;
}

三、本期总结+下期预告

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

感谢大家的关注，我们下期再见！
在这里插入图片描述