数据结构 ——— C语言实现带哨兵位双向循环链表

devtools/2024/10/22 10:48:56/

 

目录

前言

无哨兵位单向不循环链表的缺陷

带哨兵位双向循环链表的概念

带哨兵位双向循环链表的结构

带哨兵位双向循环链表逻辑结构示意图​编辑

实现带哨兵位双向循环链表的准备工作

实现带哨兵位双向循环链表

1. 创建新节点

2. 初始化哨兵位

3. 定义哨兵位指针

4. 打印链表所有节点的数据

5. 在链表尾部插入节点

6. 在链表头部插入节点

7. 在链表尾部删除节点

8. 在链表头部删除节点

9. 查找链表中的指定节点

10. 在pos节点之前插入节点

11. 删除pos节点

小结

12. 释放链表

List.h

List.c

前言

在前几章实现了用C语言实现无哨兵位单向不循环链表，以及一些单链表的oj题

数据结构 ——— C语言实现无哨兵位单向不循环链表-CSDN博客

数据结构 ——— 单链表oj题：相交链表（链表的共节点）-CSDN博客

数据结构 ——— 单链表oj题：环状链表（判断链表是否带环）-CSDN博客 

接下来要学习的是带哨兵位双向循环链表的概念及其实现

无哨兵位单向不循环链表的缺陷

  1. 在实现 无哨兵位单向不循环链表 时，可以发现对其尾插节点的时间复杂度为：O(N) ；因为要从头节点遍历，找到原尾节点，才能进行插入节点
  2. 在查找当前节点的前一个节点时，也需要从头节点开始遍历才能查找到
  3. 且在没有哨兵位的情况下，在进行插入时，都需要判断链表的头节点是否为 NULL

所以给出了 带哨兵位双向循环链表，可以有效的解决以上问题

带哨兵位双向循环链表的概念

  1. 带哨兵位可以有效的避免对头节点为 NULL 时的判断，可以直接插入或者删除
  2. 双向的好处在于对当前节点的前一个节点或者后一个节点的查找时间复杂度为：O(1)
  3. 链表循环的好处在于对于尾插的时间复杂度为：O(1)

带哨兵位双向循环链表的结构

// 节点数据的类型
typedef int LTDataType;typedef struct ListNode
{struct ListNode* prev; //指向前一个节点的指针LTDataType data; //节点的数据struct ListNode* next; //指向后一个节点的指针
}LNode;

以上的结构就是 带哨兵位双向循环链表 中每一个节点的结构
prev 指针指向前一个节点，next 指针指向后一个节点，这样就实现了双向的结构

带哨兵位双向循环链表逻辑结构示意图

哨兵位 head 节点的 prev 指向最后一个节点，next 指向第一个节点
这样就实现了带哨兵位循环的结构

实现带哨兵位双向循环链表的准备工作

和实现 无哨兵位单向不循环链表 一样，需要准备3个文件

test.c 文件：用来测试代码功能的完善性

List.h 文件：用来声明头文件和定义单链表的结构以及函数的声明

List.c 文件：用来实现单链表的功能函数

实现带哨兵位双向循环链表

1. 创建新节点

static LNode* BuyLTNode(LTDataType x)
{LNode* newnode = (LNode*)malloc(sizeof(LNode));// 判断是否开辟成功if (newnode == NULL){perror("BuyLTNode fail");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}

 使用 malloc 函数动态开辟一个 newnode 节点，并判断是否开辟成功
将数据 x 存储到 newnode 的 data 中，最后返回 newnode 节点指针

2. 初始化哨兵位

LNode* LTInit()
{LNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

在函数内部创建哨兵位，最后再返回哨兵位的指针，这样做的好处是避免使用二级指针
为什么要将哨兵位的 prev 和 next 都指向自己呢？这个留作悬念，在尾插时会讲解到

3. 定义哨兵位指针

LNode* plist = LTInit();

直接利用初始化哨兵位的函数定义链表，这样就避免了使用二级指针
因为如果使用传址初始化哨兵位的话，就需要传递二级指针才能改变指针的指向
没有这样做是因为稳定函数的统一性，使函数都使用一级指针进行增删查改

4. 打印链表所有节点的数据

void LTPrint(LNode* phead)
{LNode* cur = phead->next;printf("head<->");while (cur != phead){printf("%d<->", cur->data);cur = cur->next;}printf("head\n");
}

phead 的 next 也就是链表的第一个节点 cur 
因为链表是循环链表，那么尾节点的 next 就是哨兵位
所以 while 循环的判断条件是头节点 cur 不等于 哨兵位 phead
这样就实现了打印链表所有节点的数据

5. 在链表尾部插入节点

void LTPushBack(LNode* phead, LTDataType x)
{// 判断哨兵位的有效性assert(phead);LNode* newnode = BuyLTNode(x); //申请新节点LNode* tail = phead->prev; //找原尾节点// 原尾节点链接新尾节点tail->next = newnode;newnode->prev = tail;// 哨兵位链接新尾节点phead->prev = newnode;newnode->next = phead;
}

在链表尾部插入数据，那么就要先找到链表中原来的尾节点
且原来的尾节点 tail 就是哨兵位 phead 节点的 prev

先把原尾节点 tail 的 next 指向 新节点 newnode ，新节点 newnode 的 prev 指向原尾节点 tail ，这样 newnode 就成功链接成新的尾节点
最后再把哨兵位 phead 的 prev 指向新的尾节点 newnode ，新尾节点 newnode 的 next 指向 phead ，这样哨兵位就成功链接了新的尾节点

且当链表为空时，以上的代码逻辑同样适用，这就是为什么在初始化哨兵位时要将哨兵位的 prev 和 next 都指向自己的原因

测试代码：

6. 在链表头部插入节点

void LTPushFront(LNode* phead, LTDataType x)
{assert(phead);LNode* newnode = BuyLTNode(x); //申请新节点LNode* first = phead->next; //找原头节点// 原头节点链接新头节点newnode->next = first;first->prev = newnode;// 哨兵位链接新头节点phead->next = newnode;newnode->prev = phead;
}

先找到原来的头节点 first ，原来的头节点也就是 phead 的 next
再把原头节点和新头节点链接、哨兵位和新头节点链接，无论先后顺序都可以
这样就实现了在链表头部插入数据

以上的代码逻辑同样适用于当链表为空的情况

测试代码：

7. 在链表尾部删除节点

void LTPopBack(LNode* phead)
{assert(phead);// 当链表为空时if (phead->prev == phead){printf("链表无节点可删除\n");return;}// 找到尾节点的前一个节点LNode* tailPrev = phead->prev->prev;// 删除（释放）尾节点free(phead->prev);// 哨兵位链接新尾节点tailPrev->next = phead;phead->prev = tailPrev;
}

先找到尾节点的前一个节点，phead 的 prev 是尾节点，那么 phead 的 prev 的 prev 就是尾节点的前一个节点
再释放尾节点，最后再链接哨兵位和新的尾节点 tailPrev
这样就实现了在链表尾部删除节点

以上的代码逻辑在 链表只有一个节点 或者 链表为空 的时候同样适用

测试代码：

8. 在链表头部删除节点

void LTPopFront(LNode* phead)
{assert(phead);// 当链表为空时if (phead->next == phead){printf("链表无节点可删除\n");return;}// 找到头节点的下一个节点LNode* firstNext = phead->next->next;// 释放头节点free(phead->next);// 哨兵位链接新的头节点phead->next = firstNext;firstNext->prev = phead;
}

先找到头节点的下一个节点，phead 的 next 就是头节点，那么 phead 的 next 的 next 就是头节点的下一个节点
再释放头节点，最后在把哨兵位和新的头节点链接
这样就实现了在链表头部删除节点

以上的代码逻辑在 链表只有一个节点 或者 链表为空 的时候同样适用

测试代码：

9. 查找链表中的指定节点

LNode* LTFind(LNode* phead, LTDataType x)
{assert(phead);LNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

和 打印链表所有节点的数据 的逻辑差不多，也是需要遍历链表
当 cur 的 data 等于 x 时，cur 就是要查找的节点，返回 cur
当链表遍历完一遍还没有找到指定节点时，说明没有此节点，返回NULL即可 

以上的逻辑既有读也有写的功能，因为返回值是指定节点的指针，那么就可以进行修改
且在实现中间插入删除节点时，都要利用 LTFind 函数配合使用 

10. 在pos节点之前插入节点

void LTInsert(LNode* pos, LTDataType x)
{assert(pos);LNode* newnode = BuyLTNode(x);LNode* posPrev = pos->prev; //找到 pos 节点的前一个节点// posPrev 节点链接新节点posPrev->next = newnode;newnode->prev = posPrev;// 新节点链接 pos 节点newnode->next = pos;pos->prev = newnode;
}

优先判断 pos 指针的有效性，因为当 LTFind 函数没有查找到指定节点时，会返回 NULL
找到 pos 节点的前一个节点 posPrev
再将 posPrev 和 newnode 和 pos 节点各自链接，无论先后顺序都可以
这样就实现了在链表 pos 节点之前插入节点

以上代码逻辑同样适用于当链表只有一个节点的情况

测试代码：

11. 删除pos节点

void LTErase(LNode* pos)
{assert(pos);// 找到 pos 节点的前一个节点LNode* posPrev = pos->prev;// 找到 pos 节点的后一个节点LNode* posNext = pos->next;// 释放 pos 节点free(pos);// 链接 posPrev 和 posNext 节点posPrev->next = posNext;posNext->prev = posPrev;
}

同样优先判断 pos 节点的有效性
再找到 pos 节点的前一个节点 posPrev 和 pos 的后一个节点 posNext
最后释放 pos 节点，再链接 posPrev 和 posNext 节点即可
这样就实现了删除 pos 节点

以上代码逻辑同样适用于当链表只有一个节点的情况

测试代码：

小结

只要有了 LTFind 和 LTInsert 和 LTErase 这三个函数，以上的头插、尾插、头删、尾删这些函数都可以复用这三个函数，具体怎么复用我就不写了，望大家自己实现

12. 释放链表

void LTDestroy(LNode* phead) 
{assert(phead);LNode* cur = phead->next;LNode* next = NULL;while (cur != phead){next = cur->next;free(cur);cur = next;}free(phead);
}

从第一个节点开始释放，释放前要先存储下一个节点
最后再释放哨兵位 phead

自此，带哨兵位双向循环链表的基本函数都以实现，接下来就是做一些有关链表的oj题
感谢大家阅读，最后我会把定义和实现的所有代码文件展示在下面

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 节点数据的类型
typedef int LTDataType;typedef struct ListNode
{struct ListNode* prev; //指向前一个节点的指针LTDataType data; //节点的数据struct ListNode* next; //指向后一个节点的指针
}LNode;// 初始化哨兵位
LNode* LTInit();// 打印
void LTPrint(LNode* phead);// 尾插
void LTPushBack(LNode* phead, LTDataType x);// 头插
void LTPushFront(LNode* phead, LTDataType x);// 尾删
void LTPopBack(LNode* phead);// 头删
void LTPopFront(LNode* phead);// 查找
LNode* LTFind(LNode* phead, LTDataType x);// pos节点之前插入
void LTInsert(LNode* pos, LTDataType x);// 删除pos节点
void LTErase(LNode* pos);// 释放链表
void LTDestroy(LNode* phead);

List.c 

#include"List.h"// 创建新节点
static LNode* BuyLTNode(LTDataType x)
{LNode* newnode = (LNode*)malloc(sizeof(LNode));// 判断是否开辟成功if (newnode == NULL){perror("BuyLTNode fail");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;
}// 初始化哨兵位
LNode* LTInit()
{LNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}// 打印
void LTPrint(LNode* phead)
{assert(phead);LNode* cur = phead->next;printf("head<->");while (cur != phead){printf("%d<->", cur->data);cur = cur->next;}printf("head\n\n");
}// 尾插
void LTPushBack(LNode* phead, LTDataType x)
{// 判断哨兵位的有效性assert(phead);LNode* newnode = BuyLTNode(x); //申请新节点LNode* tail = phead->prev; //找尾节点// 原尾节点链接新尾节点tail->next = newnode;newnode->prev = tail;// 哨兵位链接新尾节点phead->prev = newnode;newnode->next = phead;
}// 头插
void LTPushFront(LNode* phead, LTDataType x)
{assert(phead);LNode* newnode = BuyLTNode(x); //申请新节点LNode* first = phead->next; //找原头节点// 原头节点链接新头节点newnode->next = first;first->prev = newnode;// 哨兵位链接新头节点phead->next = newnode;newnode->prev = phead;
}// 尾删
void LTPopBack(LNode* phead)
{assert(phead);// 当链表为空时if (phead->prev == phead){printf("链表无节点可删除\n");return;}// 找到尾节点的前一个节点LNode* tailPrev = phead->prev->prev;// 删除（释放）尾节点free(phead->prev);// 哨兵位链接新尾节点tailPrev->next = phead;phead->prev = tailPrev;
}// 头删
void LTPopFront(LNode* phead)
{assert(phead);// 当链表为空时if (phead->next == phead){printf("链表无节点可删除\n");return;}// 找到头节点的下一个节点LNode* firstNext = phead->next->next;// 释放头节点free(phead->next);// 哨兵位链接新的头节点phead->next = firstNext;firstNext->prev = phead;
}// 查找
LNode* LTFind(LNode* phead, LTDataType x)
{assert(phead);LNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}// pos节点之前插入
void LTInsert(LNode* pos, LTDataType x)
{assert(pos);LNode* newnode = BuyLTNode(x);LNode* posPrev = pos->prev; //找到 pos 节点的前一个节点// posPrev 节点链接新节点posPrev->next = newnode;newnode->prev = posPrev;// 新节点链接 pos 节点newnode->next = pos;pos->prev = newnode;
}// 删除 pos 节点
void LTErase(LNode* pos)
{assert(pos);// 找到 pos 节点的前一个节点LNode* posPrev = pos->prev;// 找到 pos 节点的后一个节点LNode* posNext = pos->next;// 释放 pos 节点free(pos);// 链接 posPrev 和 posNext 节点posPrev->next = posNext;posNext->prev = posPrev;
}// 释放链表
void LTDestroy(LNode* phead) 
{assert(phead);LNode* cur = phead->next;LNode* next = NULL;while (cur != phead){next = cur->next;free(cur);cur = next;}free(phead);
}

http://www.ppmy.cn/devtools/125531.html

相关文章

QD1-P23 CSS 基础选择器

QD1-P23 CSS 基础选择器

本节学习&#xff1a;CSS 基础选择器&#xff08;5种&#xff09; 本节视频 https://www.bilibili.com/video/BV1n64y1U7oj?p23 基础选择器是 CSS 中最常用的选择器类型&#xff0c;它们用于选择 HTML 文档中的元素。以下是基础选择器的列表以及它们的优先级&#xff08;权重…
阅读更多...
中国上市药品目录集数据库查询方法-支持数据下载

中国上市药品目录集数据库查询方法-支持数据下载

《中国上市药品目录集》由国家食品药品监督管理总局以数据库形式发布并实时更新&#xff0c;由CDE负责日常维护和管理。《中国上市药品目录集》收录了在中国批准上市的创新药、改良型新药、化学药品新注册分类的仿制药以及通过质量和疗效一致性评价的药品的具体信息。这个目录集…
阅读更多...
XML 和 SimpleXML 简介

XML 和 SimpleXML 简介

XML 和 SimpleXML 简介 XML（可扩展标记语言）是一种用于存储和传输数据的标记语言。它定义了一组规则，用于在文档中编码数据，以便人和机器都能理解。XML 的设计目标是既易于人类阅读，也易于机器解析。SimpleXML 是 PHP 中的一个扩展，用于处理 XML 数据。它提供了一个简单…
阅读更多...
泡沫背后：人工智能的虚幻与现实

泡沫背后：人工智能的虚幻与现实

人工智能的盛世与泡沫 现今&#xff0c;人工智能热潮席卷科技行业&#xff0c;投资者、创业者和用户都被其光环吸引。然而&#xff0c;深入探讨这种现象&#xff0c;人工智能的泡沫正在形成&#xff0c;乃至具备崩溃的潜质。我们看到的&#xff0c;无非是一场由资本推动的狂欢…
阅读更多...
【软件考试】一文学会原码，反码与补码

【软件考试】一文学会原码，反码与补码

文章目录 三码互转十进制数转二进制 三码互转 在计算机中&#xff0c;数值通常以二进制形式表示&#xff0c;原码、反码和补码是三种不同的表示方法。 一、原码 概念&#xff1a; 原码是最直观的二进制表示法&#xff0c;最高位为符号位&#xff0c;0 表示正数&#xff0c;1 …
阅读更多...
鸿蒙NEXT开发-动画（基于最新api12稳定版）

鸿蒙NEXT开发-动画（基于最新api12稳定版）

注意&#xff1a;博主有个鸿蒙专栏&#xff0c;里面从上到下有关于鸿蒙next的教学文档&#xff0c;大家感兴趣可以学习下 如果大家觉得博主文章写的好的话&#xff0c;可以点下关注&#xff0c;博主会一直更新鸿蒙next相关知识 专栏地址: https://blog.csdn.net/qq_56760790/…
阅读更多...
Python笔记之识别到当前python脚本所在的目录，而不是执行python命令的目录

Python笔记之识别到当前python脚本所在的目录，而不是执行python命令的目录

Python笔记之识别到当前python脚本所在的目录&#xff0c;而不是执行python命令的目录 code review! 文章目录 Python笔记之识别到当前python脚本所在的目录&#xff0c;而不是执行python命令的目录1.题解2.在脚本所在的目录后面拼接下一层目录 1.题解 要在Python脚本中识别到…
阅读更多...
前端发送了请求头的参数，经debug发现后端请求对象请求头中没有该参数

前端发送了请求头的参数，经debug发现后端请求对象请求头中没有该参数

debug测试&#xff0c;发现前端发来请求头中确实没有找到添加的请求头参数&#xff0c;但是 Network 中却显示请求头中有该参数信息。 原因是RequestHeaders中设置的请求参数含有下划线&#xff0c;NGINX将静默地丢弃带有下划线的HTTP标头&#xff0c;这样做是为了防止在将头映…
阅读更多...
最新文章

Copyright @ 2022~2023