C语言超详细讲解双向带头循环链表
[Pokemon]大猫猫 人气:0在上一篇所讲述的单链表中,存在一些缺陷:
1、在进行尾插和尾删时,需要遍历链表找到尾结点
2、在进行中间插入和删除时,也需要先遍历链表找到前一个结点
对于这些缺陷,可以采用一种结构更为复杂的链表 双向带头循环链表
双向带头循环链表结构虽然复杂,但在链表的操作上带来了很大的优势
一、双向带头循环链表的结构
//存储数据的类型,这里以 int 来举例 typedef int LTDataType; //结点的类型 typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode;
二、双向带头循环链表的函数接口
1. 申请结点
在插入等操作时需要申请结点,为了避免麻烦重复的操作,这里将申请结点封装为一个函数
申请结点函数如下:
LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { //开辟空间失败,打印错误信息 perror("malloc"); //结束程序 exit(-1); } newnode->data = x; newnode->prev = newnode->next = NULL; return newnode; }
2. 初识化
在双向带头循环链表中,即使没有存储数据也 至少会包含一个哨兵位的头结点
初始化函数如下:
LTNode* InitLT() { //申请头结点,头结点的数据存什么无关紧要 LTNode* phead = BuyLTNode(-1); //改变指针指向,构成循环 phead->prev = phead->next = phead; return phead; }
3. 打印
为了验证插入、删除等得到的结果是否正确,提供打印函数,这里数据类型以 int 为例,当读者采用的类型不同时,自行更改函数即可
打印函数如下:
void LTPrint(LTNode* phead) { //链表不能为空 assert(phead); LTNode* cur = phead->next; printf("head->"); while (cur != phead) { printf("%d->", cur->data); cur = cur->next; } printf("head\n"); }
4. 尾插尾删
尾插:在链表的最后一个结点之后插入结点
尾插函数如下:
void LTPushBack(LTNode* phead, LTDataType x) { //链表不能为空 assert(phead); LTNode* newnode = BuyLTNode(x); //找到尾结点 LTNode* tail = phead->prev; //改变指针指向 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
尾删:删除链表最后一个结点
尾删函数如下:
void LTPopBack(LTNode* phead) { assert(phead); //链表不能为空 assert(phead->next != phead); //空链表不能删 //找尾结点及尾结点的前一个结点 LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; //改变指针指向 tailPrev->next = phead; phead->prev = tailPrev; free(tail); }
5. 头插头删
头插: 在第一个结点之前插入新结点
头插函数如下:
void LTPushFront(LTNode* phead, LTDataType x) { //链表不能为空 assert(phead); LTNode* newnode = BuyLTNode(x); //找到头结点后的第一个结点 LTNode* first = phead->next; //改变指针指向 phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
头删:删除链表的第一个结点
头删函数如下:
void LTPopFront(LTNode* phead) { assert(phead); //链表不能为空 assert(phead->next != phead); //空链表不能删 //找到头结点后的第一个和第二个结点 LTNode* first = phead->next; LTNode* second = first->next; //改变指针指向 phead->next = second; second->prev = phead; free(first); }
6. 查找
查找:如果数据存在,返回该数据结点的指针,不存在返回 NULL
查找函数如下:
LTNode* LTFind(LTNode* phead, LTDataType x) { //链表不能为空 assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
7. 中间插入和删除
中间插入:通过查找函数 LTFind 获得指向结点的指针 pos,在 pos 指向的 结点之前 插入结点
在 pos 之前插入结点函数如下:
void LTInsert(LTNode* pos, LTDataType x) { //pos 不能为空 assert(pos); LTNode* newnode = BuyLTNode(x); //找到 pos 的前一个结点 LTNode* posPrev = pos->prev; //改变指针指向 posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
在调用中间插入函数 LTInsert 时
- 如果在链表头结点之前插入数据,便和尾插函数的功能一样
- 如果在链表头结点之后插入数据,便和头插函数的功能一样
因此在尾插和头插函数的实现中可以直接调用中间插入函数 LTInsert
尾插和头插函数更改如下:
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { //链表不能为空 assert(phead); LTInsert(phead, x); } //头插 void LTPushFront(LTNode* phead, LTDataType x) { //链表不能为空 assert(phead); LTInsert(phead->next, x); }
中间删除:通过查找函数 LTFind 获得指向结点的指针 pos,删除 pos 指向的结点
删除 pos 指向的结点函数如下:
void LTErase(LTNode* pos) { //pos 不能为空 assert(pos); //找到 pos 的前一个和后一个结点 LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; //改变指针指向 posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
在调用中间删除函数 LTErase 时
- 如果删除链表头结点的前一个结点,便和尾删函数的功能一样
- 如果删除链表头结点的后一个结点,便和头删函数的功能一样
因此在尾删和头删函数的实现中可以直接调用中间删除函数 LTErase
尾删和头删函数更改如下:
//尾删 void LTPopBack(LTNode* phead) { assert(phead); //链表不能为空 assert(phead->next != phead); //空链表不能删 LTErase(phead->prev); } //头删 void LTPopFront(LTNode* phead) { assert(phead); //链表不能为空 assert(phead->next != phead); //空链表不能删 LTErase(phead->next); }
8. 判空及求链表长度
判空:判断链表是否为空
判空函数如下:
bool LTEmpty(LTNode* phead) { //链表不能为空 assert(phead); return phead->next == phead; }
链表长度:链表有效数据个数
链表长度函数如下:
size_t LTSize(LTNode* phead) { //链表不能为空 assert(phead); size_t size = 0; LTNode* cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size; }
9. 销毁单链表
在链表中,存储数据的结点是由自己开辟的,当不使用链表时,应将其销毁
销毁链表函数如下:
void LTDestroy(LTNode* phead) { //链表不能为空 assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* curNext = cur->next; free(cur); cur = curNext; } free(phead); }
加载全部内容