设为首页收藏本站
开启辅助访问

数据结构之带头结点的循环双向链表详细图片+文字讲解

 您所在的位置：网站首页 › 链表逆序存储什么意思 › 数据结构之带头结点的循环双向链表详细图片+文字讲解

数据结构之带头结点的循环双向链表详细图片+文字讲解

2024-07-12 12:16:14| 来源: 网络整理| 查看: 265

双向循环链表

文章目录 双向循环链表前言文件的创建双向链表结构的定义创建返回链表的头结点值传递时：地址传递： 双向链表的销毁双向链表的打印开辟一个新结点双向链表的尾插双向链表的头插双向链表的尾删双向链表的头删双向链表查找双向链表在pos的前面进行插入双向链表删除pos位置的结点源代码List.h(双向链表结构及其函数的声明)List.c(双向链表函数的实现)test.c(双向链表函数功能的测试)

前言

在开始讲解带头双向循环链表之前，我们先来看一个带哨兵位的头结点的单链表和不带哨兵位的头结点的单链表的区别：

image-20210805081848631

不带哨兵位的头结点

不带哨兵位的头结点，在链表的系列操作函数中可能会修改到指向存储有效数据的第一个结点的指针plist，对在第一元素结点前插入结点和删除第一结点时，其操作与其他结点的操作不统一，我们需要在这系列操作中分别考虑不同情况

带哨兵位的头结点

这个结点不存储有效数据，链表的系列操作函数永远不会修改到指向存储有效数据的第一个结点的指针plist，因为拥有这个带哨兵位的头节点，对在第一元素结点前插入结点和删除第一结点时，其操作与其他结点的操作就统一了。这个带哨兵位的头节点看起来简单一点，为什么我们的单链表不设计这个结构呢？这个头节点的结构在实际中很少出现，包括哈希桶、邻接表做子结构都是不带头，其次就是OJ中给的链表基本都是不带头的，都有先入为主思维，我们直接写带头，容易对后面的学习产生误导。

我们链表的结构有很多，但是实际中我们最常用的还是下面两种结构：

image-20210805090324128

无头单向非循环链表

结构简单，一般不会单独用来存数据，实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中会出现很多，因为他有很多的可考之处。

带头双向循环链表

结构很复杂，一般单独用来存数据，实际中使用的链表数据结构都是带头双向循环链表，这个结构虽然很复杂，但是代码实现它的一系列增删查改等会很简单，下面我们就实现带头双向循环链表的一系列操作。

下面我们就来看带头双向循环链表的基本操作：

文件的创建

首先我们先创建三个文件：

List.h对相关头文件的包含，以及实现双向链表的结构和函数的声明

List.c对实现双向链表增删查改等操作的函数进行定义

test.c文件进行双向链表相关函数和双向链表功能的测试

image-20210805094842435

双向链表结构的定义

了解了带头双向循环链表的结构，我们先定义这样的一个结构体：

typedef struct ListNode { int data; struct ListNode* prev; struct ListNode* next; }LTNode;

和我们前面讲过的顺序表和单链表一样，我们为了方便我们数据类型的变化，我们进行类型重定义，在想要换我们的双向链表的数据类型时，直接在typedef这里修改就可以了，如下：

typedef int LTDataType; typedef struct ListNode { int data; struct ListNode* prev; struct ListNode* next; }LTNode;

我们定义好结构之后，首先在测试文件中创建一个头结点phead，先赋值为NULL：

void Test1() { LTNode* phead = NULL; } int main() { Test1(); return 0; }

接下来我们对下面的带头双向链表操作进行讲解：

// 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(LTNode* plist); // 双向链表打印 void ListPrint(LTNode* plist); // 双向链表尾插 void ListPushBack(LTNode* plist, LTDataType x); // 双向链表尾删 void ListPopBack(LTNode* plist); // 双向链表头插 void ListPushFront(LTNode* plist, LTDataType x); // 双向链表头删 void ListPopFront(LTNode* plist); // 双向链表查找 ListNode* ListFind(LTNode* plist, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(LTNode* pos);

我们写的双向链表是带头的，所以我们首先需要创建头结点：

创建返回链表的头结点 值传递时： // 创建返回链表的头结点. LTNode* ListCreate(LTNode* plist) { plist = (LTNode*)malloc(sizeof(LTNode)); if (plist == NULL) { perror("malloc plist"); return NULL; } plist->next = plist; plist->prev = plist; return plist; }

image-20210805101757894

我们malloc一个结点，这个结点不存储数据，初始化时我们将plist的next指向它自己，plist的prev指向它自己，因为plist出函数会销毁，并且里面的形参的改变不会影响实参的改变，所以我们在值传递时需要将plist返回

地址传递： // 创建返回链表的头结点. LTNode* ListCreate(LTNode** plist) { assert(plist); *plist = (LTNode*)malloc(sizeof(LTNode)); if (*plist == NULL) { perror("malloc plist"); return NULL; } (*plist)->next = *plist; (*plist)->prev = *plist; }

为了代码的统一性，我们这里就使用值传递，因为后面的函数我们都会使用值传递，因为有了哨兵位的头结点我们不会改变phead的指向。

有双向链表的创建那就有双向链表的销毁：

双向链表的销毁 // 双向链表销毁 void ListDestory(LTNode* plist) { assert(plist);//链表不为NULL，为NULL那还销毁啥 LTNode* cur = plist->next; while (cur!= plist) { LTNode* next = cur->next; free(cur); cur = next; } free(plist); plist = NULL;//这句代码无意义，因为传值时函数里面无法改变外面的实参 }

image-20210805102908726

在销毁时需要注意：

链表不为NULL，为NULL那还销毁啥，所以我们前面断言一下我们的这个链表时循环链表，如果循环的判断为cur是不是NULL，那么这个循环成死循环了，因为cur永远都不可能为NULL，所以我们判断进入循环的语句应该是cur!=plist

接下来我们来看双向链表的打印：

双向链表的打印 void ListPrint(LTNode* plist) { LTNode* cur = plist->next; while (cur != plist) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); }

和前面一样，我们在遍历链表时，需要注意循环进行的条件需要是cur不等于plist。只有条件是cur不等于plist时，我们才刚好遍历了一遍链表。

接下来我们来看如何开辟一个新结点：

开辟一个新结点 //开辟一个新结点 LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc Node"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }

我们malloc一个结点，然后将结点的data初始化，然后将next域和prev域置NULL，然后将该节点返回

接下来我们进入双向链表操作函数的主题，首先我们来看双向链表的尾插：

双向链表的尾插 // 双向链表尾插 void ListPushBack(LTNode* plist, LTDataType x) { LTNode* tail = plist->prev; LTNode* newnode = BuyListNode(x); tail->next = newnode;//1 plist->prev = newnode;//2 newnode->prev = tail;//3 newnode->next = plist;//4 } 双向链表尾插的图解

image-20210805113922791

有没有觉得比单链表的操作简单了很多，单链表我们还需要先找尾，还需要考虑没有结点时的情况，而我们的这个结构的双向链表操作尾插时间复杂度O(1)，简单了很多

我们在测试文件中测试：

image-20210805114139297

下面我们来看头插：

双向链表的头插 // 双向链表头插 void ListPushFront(LTNode* plist, LTDataType x) { LTNode* next = plist->next; LTNode* newnode = BuyListNode(x); newnode->next = next; newnode->prev=plist; next->prev = newnode; plist->next = newnode; } 双向链表的头插图解

image-20210805115744558

我们在测试文件中测试：

image-20210805115817439

接下来我们来看双向链表的尾删

双向链表的尾删 //双向链表的尾删 void ListPopBack(LTNode* plist) { assert(plist->next);//链表不能为空 LTNode* tail = plist->prev; tail->prev->next = plist;//1 plist->prev = tail->prev;//2 free(tail); tail = NULL; } 双向链表的尾删图解

image-20210805120830481

我们在测试文件中测试：

image-20210805121014097

接下来我们来看双向链表的头删

双向链表的头删 // 双向链表头删 void ListPopFront(LTNode* plist) { assert(plist->next);//链表不能为空 LTNode* next = plist->next; plist->next = next->next;//1 next->next->prev = plist;//2 free(next); next = NULL; } 双向链表的头删图解

image-20210805122010149

我们在测试文件中测试：

image-20210805122137849

接下来我们来看双向链表查找

双向链表查找 // 双向链表查找 LTNode* ListFind(LTNode* plist, LTDataType x) { assert(plist->next); LTNode* cur = plist->next; while (cur != plist) { if (cur->data == x) { return cur;//找到了，返回结点 } cur = cur->next; } return NULL;//找不到 }

和前面一样，我们在遍历链表时，需要注意循环进行的条件需要是cur不等于plist。只有条件是cur不等于plist时，我们才刚好遍历了一遍链表。找到返回结点，找不到返回NULL

我们在测试文件中测试：

image-20210805122806379

下面我们来看双向链表在pos的前面进行插入：

双向链表在pos的前面进行插入 // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos);//pos位置不能为NULL LTNode* pre = pos->prev; LTNode* newnode = BuyListNode(x); pre->next = newnode;//1 newnode->prev = pre;//2 newnode->next = pos;//3 pos->prev = newnode;//4 } 双向链表在pos的前面插入图解

image-20210805132904524

我们在测试文件中测试：

image-20210805123556031

下面我们来看双向链表删除pos位置的节点：

双向链表删除pos位置的结点 // 双向链表删除pos位置的节点 void ListErase(LTNode* pos) { assert(pos);//pos位置不能为NULL LTNode* pre = pos->prev; LTNode* next = pos->next; pre->next = next;//1 next->prev = pre;//2 free(pos); pos = NULL; } 双向链表删除pos位置结点图解

image-20210805132711924

我们在测试文件中测试：

image-20210805133118345

注意：因为我们销毁链表函数是值传递，所以我们需要在外面将phead置为NULL，我们在销毁时，要在调用函数后面一行将phead置空，不然phead就为野指针了。

ListDestory(phead); phead=NULL;

image-20210805133636142

带头结点的双向循环链表的操作我们就讲到这里，下面附上源代码：

源代码 List.h(双向链表结构及其函数的声明) #include #include #include typedef int LTDataType; typedef struct ListNode { int data; struct ListNode* prev; struct ListNode* next; }LTNode; //值传递创建头结点 LTNode* ListCreate(LTNode* phead); //地址传递创建头结点 //LTNode* ListCreate(LTNode** phead); // 双向链表销毁 void ListDestory(LTNode* plist); //双向链表的打印 void ListPrint(LTNode* plist); //开辟一个新结点 LTNode* BuyListNode(LTDataType x); // 双向链表尾插 void ListPushBack(LTNode* plist, LTDataType x); // 双向链表头插 void ListPushFront(LTNode* plist, LTDataType x); //双向链表的尾删 void ListPopBack(LTNode* plist); // 双向链表头删 void ListPopFront(LTNode* plist); // 双向链表查找 LTNode* ListFind(LTNode* plist, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(LTNode* pos); List.c(双向链表函数的实现) #include"List.h" // 创建返回链表的头结点 //值传递创建头结点 LTNode* ListCreate(LTNode* plist) { plist = (LTNode*)malloc(sizeof(LTNode)); if (plist == NULL) { perror("malloc plist"); return NULL; } plist->next = plist; plist->prev = plist; return plist; } //地址传递创建头结点 //LTNode* ListCreate(LTNode** plist) //{ // assert(plist); // *plist = (LTNode*)malloc(sizeof(LTNode)); // if (*plist == NULL) // { // perror("malloc plist"); // return NULL; // } // (*plist)->next = *plist; // (*plist)->prev = *plist; //} // 双向链表销毁 void ListDestory(LTNode* plist) { assert(plist);//链表不为NULL，为NULL那还销毁啥 LTNode* cur = plist->next; while (cur!= plist) { LTNode* next = cur->next; free(cur); cur = next; } free(plist); plist = NULL;//这句代码无意义，因为传值时函数里面无法改变外面的实参 } // 双向链表打印 void ListPrint(LTNode* plist) { LTNode* cur = plist->next; while (cur != plist) { printf("%d->", cur->data); cur = cur->next; } printf("\n"); } //开辟一个新结点 LTNode* BuyListNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc Node"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } // 双向链表尾插 void ListPushBack(LTNode* plist, LTDataType x) { LTNode* tail = plist->prev; LTNode* newnode = BuyListNode(x); tail->next = newnode; plist->prev = newnode; newnode->prev = tail; newnode->next = plist; } // 双向链表头插 void ListPushFront(LTNode* plist, LTDataType x) { LTNode* next = plist->next; LTNode* newnode = BuyListNode(x); newnode->next = next; newnode->prev = plist; next->prev = newnode; plist->next = newnode; } //双向链表的尾删 void ListPopBack(LTNode* plist) { assert(plist->next);//链表不能为空 LTNode* tail = plist->prev; tail->prev->next = plist; plist->prev = tail->prev; free(tail); tail = NULL; } // 双向链表头删 void ListPopFront(LTNode* plist) { assert(plist->next);//链表不能为空 LTNode* next = plist->next; plist->next = next->next; next->next->prev = plist; free(next); next = NULL; } // 双向链表查找 LTNode* ListFind(LTNode* plist, LTDataType x) { assert(plist->next); LTNode* cur = plist->next; while (cur != plist) { if (cur->data == x) { return cur;//找到了，返回结点 } cur = cur->next; } return NULL;//找不到 } // 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* pre = pos->prev; LTNode* newnode = BuyListNode(x); pre->next = newnode; newnode->prev = pre; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(LTNode* pos) { assert(pos); LTNode* pre = pos->prev; LTNode* next = pos->next; pre->next = next; next->prev = pre; free(pos); pos = NULL; } test.c(双向链表函数功能的测试) #include"List.h" void Test1() { LTNode* phead = NULL; phead = ListCreate(phead); ListPushBack(phead, 1); ListPushBack(phead, 2); ListPushBack(phead, 3); ListPushBack(phead, 4); ListPrint(phead); ListPushFront(phead, 5); ListPushFront(phead, 6); ListPrint(phead); ListPopBack(phead); ListPrint(phead); ListPopFront(phead); ListPopFront(phead); ListPrint(phead); LTNode* pos= ListFind(phead, 2); printf("%d\n", pos->data); LTNode* pos1 = ListFind(phead, 2); ListInsert(pos1, 10); ListPrint(phead); LTNode* pos2 = ListFind(phead, 10); ListErase(pos2); ListPrint(phead); ListDestory(phead); phead = NULL; } int main() { Test1(); return 0; }

下一篇博主讲说一说顺序表和链表的区别，他们各自的优缺点。 如果认为博主文章还不错，那就点个赞再走吧，欢迎大家互相学习讨论



【本文地址】

公司简介

联系我们

今日新闻

点击排行
实验室常用的仪器、试剂和
说到实验室常用到的东西，主要就分为仪器、试剂和耗
不用再找了，全球10大实验
01、赛默飞世尔科技（热电）Thermo Fisher Scientif
三代水柜的量产巅峰T-72坦
作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这
通风柜跟实验室通风系统有
说到通风柜跟实验室通风，不少人都纠结二者到底是不
集消毒杀菌、烘干收纳为一
厨房是家里细菌较多的地方，潮湿的环境、没有完全密
实验室设备之全钢实验台如
全钢实验台是实验室家具中较为重要的家具之一，很多

推荐新闻

图片新闻
实验室药品柜的特性有哪些
实验室药品柜是实验室家具的重要组成部分之一，主要
小学科学实验中有哪些教学
计算机 计算器 一般 打孔器 打气筒 仪器车 显微镜
实验室各种仪器原理动图讲
1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分
高中化学常见仪器及实验装
1、可加热仪器：2、计量仪器：（1）仪器A的名称：量
微生物操作主要设备和器具
今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦
浅谈通风柜使用基本常识
　众所周知，通风柜功能中最主要的就是排气功能。在

专题文章
    CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭