🧑🎓个人主页:简 料
🏆所属专栏:C++
🏆个人社区:越努力越幸运社区
🏆简 介:简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~
C/C++学习路线 (点击解锁) |
---|
❤️C语言阶段(已结束) |
❤️数据结构与算法(ing) |
❤️C++(ing) |
❤️Linux系统与网络(队列中…) |
😎前言
-
前面学习了单链表的结构,并且做了些许单链表的
OJ
练习,相信大家已经对单链表的结构了如指掌。因此,本章带来了与单链表同源的但拥有不同的结构的链表 —带头双向循环链表供大家学习。 -
可能大家听到带头双向循环链表这个名字,就会认为该结构很复杂(的确很复杂,是链表当中结构最复杂的),肯定比单链表要难许多,说实在的,如果没有前面单链表的铺垫,直接上这个结构,那肯定挺难的。但现在我们有了单链表的基础,并且做了挺多单链表的题了,也就不用怕了。
-
实际上,带头双向循环链表只是 看起来难,听起来难,但它实现起来,比单链表简单多了。并且许多细节地方都不需要那么的繁琐。
-
注意:下面所说的头节点都是指那个哨兵位的头节点。
带头双向循环链表的初始化
-
既然是双向,也就是即指向前也指向后,因此每一个节点不光要存储一个数据,还要两个结构体指针,一个指针
prev
指向前,一个指针next
指向后,也就是next
指针指向下一个节点,prev
指针指向前一个节点。按照这个形式由一个一个的节点组成的链表,就是双向的,这剔除了单链表的单向性。由此可知遍历这个双向链表不仅可以往后遍历,还可以往前遍历,这是不是方便了许多呢? -
那循环在这是什么意思?循环就是链表的第一个节点的
prev
指向链表的最后一个节点,链表的最后一个节点的next
指向链表的第一个节点,例如:
不带哨兵位的头节点的双向循环链表:
-
但是这里,我们讨论带头的双向循环链表。
-
为啥要带头呢?很简单,便于下面的一系列操作。想一下,如果没有哨兵位的头节点进行增删查改,遇到头删或者头插的话,此时需要更新一下头节点,既然要更新一下头节点,那就与单链表章节一样,需要用到二级指针,或者带返回值,这就很麻烦了。但如果带哨兵位头节点的话,二级指针和返回值都不需要用到,并且头删头插尾插尾删都特别的方便,它的优势处,下面会一一体现。
带头双向循环链表:
-
当然,有了前面的数据结构的学习,毫无疑问,这里也是需要三个文件来实现的,这里就不多说了,分别是
DList.h,DList.c,test.c
-
有了上面的介绍,我们首先包含需要用到的头文件:
#include <stdio.h>
// assert断言
#include <assert.h>
// 动态内存函数所需
#include <stdlib.h>
// 判空所需 bool 类型
#include <stdbool.h>
- 然后将节点的结构创建出来(两个指针一个数据):
// 存储的数据的类型
typedef int LTDataType;
typedef struct ListNode
{
// 存储数据
LTDataType _data;
// 指向下一个节点的指针
struct ListNode* _next;
// 指向前一个节点的指针
struct ListNode* _prev;
}ListNode; // 重命名是为了方便
- 接着就是对各个函数接口一一实现了。各个函数接口的声明:(由于前面的与函数接口声明都在
.h
文件,并且该文件只有这些,这里就直接放.h
文件了):
#include <stdio.h>
// assert断言
#include <assert.h>
// 动态内存函数所需
#include <stdlib.h>
// 判空所需 bool 类型
#include <stdbool.h>
// 带头+双向+循环链表增删查改实现
// 存储的数据的类型
typedef int LTDataType;
typedef struct ListNode
{
// 存储数据
LTDataType _data;
// 指向下一个节点的指针
struct ListNode* _next;
// 指向前一个节点的指针
struct ListNode* _prev;
}ListNode; // 重命名是为了方便
// 创建返回链表的头结点.
ListNode* ListCreate();
// 得到一个结点
ListNode* BuyListNode(LTDataType x);
// 双向链表清理
void ListClear(ListNode* phead);
// 双向链表销毁
void ListDestory(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 判空
bool ListEmpty(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 修改某一节点的数据
void ListModify(ListNode* pos, LTDataType x);
创造一个哨兵位头节点
-
我们首先得创造一个带哨兵位的头节点,这样才能进行后续的操作。
-
当然,我们每次创造的一个节点都是使用
malloc
向内存申请一段空间来存储。 -
这里也是一样,我们向内存申请一个节点的空间后,将这个节点的两个指针都指向自己,并且里面的数据任意给(这里不做要求,也可以不给,它默认随机值,不过最好给
-1
),这样就得到一个哨兵位的头节点。有了该函数的功能,我们每次测试的时候,开始都要有这一步操作:
ListNode* plist = ListCreate(); // 将plist指向那个哨兵位头节点
下面是相关接口函数功能实现:
// 创建返回链表的头结点.
ListNode* ListCreate()
{
// BuyListNode(),该函数是获取一个节点,下面有介绍,大概理解这样操作就欧克啦
ListNode* head = BuyListNode(-1);
return head;
}
得到节点
-
该函数在获取头节点函数和所有插入函数中都需要用到,因此这里把它抽离出来单独形成一个接口,以此来提高效率。
-
得到一个节点,那当然是在内存中申请一段空间,这个空间就作为新的那个节点的空间。
-
每次得到的这个节点,让它的两个指针都先指向自己,然后数据存放自己给出的值,之后将这个节点的地址返回即可,因为该节点的空间是在堆上的,函数栈帧销毁不会影响这段空间。
下面是相关接口函数功能实现:
// 得到一个结点
ListNode* BuyListNode(LTDataType x)
{
// 向内存中申请一个节点的空间
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
// 判断一下是否申请失败
assert(newnode);
// 将next和prev都指向自己
newnode->_next = newnode;
newnode->_prev = newnode;
// 存放自己给的数据
newnode->_data = x;
// 返回这个节点的地址
return newnode;
}
链表清理
-
当我们创建了一个带头双向循环链表后,不想要了但又还想继续操作怎么办👻?当然是将每个节点释放(
free
)。 -
注意:清理是将每个有效的节点删除(释放),不会干掉头节点,因此,我们从头节点的下一个节点开始,向右遍历链表,一边遍历一边删除(所以这里需要创建一个节点指针来存放下一个节点的地址),直到最后遍历到头节点的时候结束操作。
下面是相关接口函数功能实现:
void ListClear(ListNode* phead)
{
// 避免传NULL的情况,phead是NULL就不能操作了
assert(phead);
// 从phead的下一个节点开始操作
ListNode* cur = phead->_next;
while (cur != phead)
{
// 存放当前节点的下一个节点的地址
ListNode* next = cur->_next;
free(cur);
cur = next;
}
}
链表销毁
-
我们在一系列操作后,一定要记得链表销毁,不然会出现内存泄漏的情况,尽管现在的编译器大部分都很明智了,会自动把申请的空间返还给操作系统。但是我们要养成这样一个好习惯,因此这里将该函数接口的实现放在前面。
-
销毁与清理可就不一样了,销毁是要将所有申请的空间释放,因此也就包括那个哨兵位的头节点。
-
前面已经实现了清理的函数,所以这里直接考虑复用清理的函数,最后再将头节点释放即可。
下面是相关接口函数功能实现:
// 双向链表销毁
void ListDestory(ListNode* phead)
{
// 判断phead是否是NULL
assert(phead);
// 复用
ListClear(phead);
// 最后释放头节点
free(phead);
}
打印链表
-
打印功能可以说必不可少,它在你进行操作的时候,可以直观的展现你进行了那些操作。
-
当然打印不需要打印头节点,你可以把头节点当作一个虚的。
-
因此这里需要从头节点的下一个节点开始依次打印,直到遍历链表遍历到头节点时结束打印。
下面是相关接口函数功能实现:
// 双向链表打印
void ListPrint(ListNode* phead)
{
assert(phead);
// 从头节点的下一个开始
ListNode* cur = phead->_next;
// 遍历到头结束
while (cur != phead)
{
// 打印当前节点的数据
printf("%d ", cur->_data);
// 寻找下一个节点
cur = cur->_next;
}
printf("\n");
}
链表判空
-
这里还提供一个判空函数,这个判空是判断除头节点以外还有没有其它节点,如果没有,说明空,返回
true
;如果有,说明不空,返回false
。 -
如何来判?在前面初始化创建一个头节点时,将该节点的两个指针分别指向了自己,因此,当链表为空,没有其它节点的时候我们直接判断头节点的
next
或者prev
指针是否指向自己就好,如果是指向自己,说明为空,反之,不为空。 -
当在删除链表的节点的时候,判空会起到有效的作用。
下面是相关接口函数功能实现:
// 判空
bool ListEmpty(ListNode* phead)
{
assert(phead);
// 判断头节点的next是否指向自己,判断prev也是可行的
return phead->_next == phead;
}
链表尾插
-
链表的尾插,就是在链表的最后一个节点的后面连接一个节点,因此我们先要得到一个节点,然后找到链表的最后一个节点,再进行连接。
-
由于该链表是带头双向循环链表,既然是循环,要找到最后一个节点,那可是易如反掌。它不就是头节点的
prev
嘛。 -
连接过程也是简简单单:
- 如果此时链表中没有有效的节点,那么此时直接得到一个节点与头节点连接即可,不需要考虑单链表章节是否要更新头指针的情况,这也体现了带头的优处。
下面是相关接口函数功能实现:
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
// 得到一个节点
ListNode* newnode = BuyListNode(x);
// 存储最后一个节点的指针
ListNode* cur = phead->_prev;
// 连接
cur->_next = newnode;
newnode->_prev = cur;
newnode->_next = phead;
phead->_prev = newnode;
}
链表尾删
-
尾删就是删除最后一个节点,所以我们先要找到最后一个节点的前一个节点(
phead->prev->prev
),然后将最后一个节点删除(释放),最后将最后一个节点的前一个节点与头节点连接即可。 -
如果此时只有一个节点,也是一样的删,没有其它的麻烦,多想想就明白了(自行体会)。
-
如果此时没有节点,这是判空的作用就来了,没有节点当然就是不给删咯,直接
assert
断言暴打。
下面是相关接口函数功能实现:
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
// 如果为空返回真 ,!一下为假
assert(phead && !ListEmpty(phead));
// 要删除的尾节点的指针
ListNode* cur = phead->_prev;
// 尾节点的前一个结点
ListNode* prev = cur->_prev;
free(cur);
// 连接
prev->_next = phead;
phead->_prev = prev;
}
链表头插
-
头插就是在头节点的后面插入,得到一个节点后,只管连接即可,轻轻松松。
-
当然这里要注意的是,如果不存放当前头节点的下一个节点的地址,那么需要先将新的节点与头节点的下一个节点连接,然后才与头节点连接,因为先与头节点连接的话,就找不到下一个节点了,此时就会连接中断。
-
如果存放当前头节点的下一个节点的地址的话,是可以随意连接的,没有主次。
下面是相关接口函数功能实现:
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
// 得到一个节点
ListNode* newnode = BuyListNode(x);
// 这里是存放下一个节点的地址
ListNode* cur = phead->_next;
// 连接
newnode->_next = cur;
cur->_prev = newnode;
phead->_next = newnode;
newnode->_prev = phead;
}
链表头删
-
链表头删是删除头节点的下一个节点,为了删除之后,能够正常连接,所以需要存放此时头节点的下一个节点的下一个节点的地址,然后将头节点的下一个节点删除,最后再将头节点与存放的那个地址指向的节点连接即可。
-
注意,既然是删除,那就要复用判空函数判断链表是否为空,不然没有节点了还去删除,就会出问题。
下面是相关接口函数功能实现:
// 双向链表头删
void ListPopFront(ListNode* phead)
{
// 判空
assert(phead && !ListEmpty(phead));
// 存放当前链表头节点的下一个节点的地址
ListNode* cur = phead->_next;
// 存放当前链表头节点的下一个节点的下一个节点的地址
ListNode* next = cur->_next;
// 删除(释放)
free(cur);
// 连接
phead->_next = next;
next->_prev = phead;
}
链表查找
-
这里的查找是你给定一个数据,然后在链表中寻找
data
与这个数据相等的节点,最终返回这个节点的地址。 -
如果没有找到,就返回
NULL
。 -
如何查找?很简单,遍历一遍链表即可。
-
如果链表为空,也就是只有一个头节点,这时
phead
的next
就是自己,判断条件为假,返回NULL
。
下面是相关接口函数功能实现:
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
// 从头节点的下一个位置开始查找
ListNode* cur = phead->_next;
// 直到遍历到头节点结束
while (cur != phead)
{
// 找到相等的直接返回当前的节点
if (cur->_data == x) return cur;
cur = cur->_next;
}
// 如果循环内没有相等的数据对应,则返回空
return NULL;
}
链表修改
-
链表的修改就是将链表中的某一个节点的数据修改成你想要的值。
-
这里通过传递某一个节点的地址来进行修改,言外之意就是可以先使用查找函数查找到你想要修改的那个节点,然后将查找函数的返回值作为要修改的那个节点的参数,最后进行修改即可。
-
如果此时链表为空,在查找函数就直接会返回
NULL
,因此这里需要断言一下pos
的有效性。
下面是相关接口函数功能实现:
// 修改某一节点的数据
void ListModify(ListNode* pos, LTDataType x)
{
// 判断pos的有效性
assert(pos);
// 直接修改数据即可
pos->_data = x;
}
任意插入
-
这里的任意插入,是将你要插入的节点插入在你想要插入的位置的前面。
-
同样的,这里需要传递一个节点的指针(
pos
)代表你要插入的位置,所以这里搭配查找函数会更好。 -
前面学习了头插尾插,相信大家对插入的连接已经了如指掌了,任意位置插入也不难。
-
既然是在想插入的位置的前面插入,那么这里就需要存放一下该位置的前一个节点的地址,然后进行连接即可。
下面是相关接口函数功能实现:
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
// 判断pos是否有效
assert(pos);
// 得到一个节点
ListNode* newnode = BuyListNode(x);
// 存放pos的前一个节点
ListNode* prev = pos->_prev;
// 连接
newnode->_next = pos;
pos->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
}
有了任意插入的函数,前面的头插尾插都可以改为复用噢!(在后面整体代码中展示)
任意删除
-
任意删除,是删除
pos
位置,这个pos
就是你指定要删除的那个节点的地址。 -
既然是删除
pos
位置,那么就需要存放一下pos
的前一个节点的地址和pos
的下一个节点的地址,以便于连接。最后将pos
位置的节点释放即可。 -
任意删除函数实际上是不需要判空的,直接判断
pos
的有效性就可以了,加入pos
为NULL
,就说明要么没找到你要删的那个节点,要么链表为空,所以空的情况已经包含在内了。
下面是相关接口函数功能实现:
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
// 判断pos的有效性
assert(pos);
// 存放pos的下一个节点的地址
ListNode* next = pos->_next;
// 存放pos的前一个节点的地址
ListNode* prev = pos->_prev;
// 删除(释放)pos
free(pos);
// 连接
prev->_next = next;
next->_prev = prev;
}
有了任意删除函数接口,前面的头删尾删就可以复用该函数接口了。
整体代码
DList.h:
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 得到一个结点
ListNode* BuyListNode(LTDataType x);
// 双向链表清理
void ListClear(ListNode* phead);
// 双向链表销毁
void ListDestory(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 判空
bool ListEmpty(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 修改某一节点的数据
void ListModify(ListNode* pos, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
DList.c:
#include "DList.h"
// 创建返回链表的头结点.
ListNode* ListCreate()
{
ListNode* head = BuyListNode(-1);
return head;
}
// 得到一个结点
ListNode* BuyListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
assert(newnode);
newnode->_next = newnode;
newnode->_prev = newnode;
newnode->_data = x;
return newnode;
}
// 双链表清理
void ListClear(ListNode* phead)
{
// 避免传NULL的情况,phead是NULL就不能操作了
assert(phead);
// 从phead的下一个节点开始操作
ListNode* cur = phead->_next;
while (cur != phead)
{
// 存放当前节点的下一个节点的地址
ListNode* next = cur->_next;
free(cur);
cur = next;
}
}
// 双向链表销毁
void ListDestory(ListNode* phead)
{
// 判断phead是否是NULL
assert(phead);
// 复用
ListClear(phead);
// 最后释放头节点
free(phead);
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->_next;
while (cur != phead)
{
printf("%d ", cur->_data);
cur = cur->_next;
}
printf("\n");
}
// 判空
bool ListEmpty(ListNode* phead)
{
assert(phead);
return phead->_next == phead;
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
//ListNode* newnode = BuyListNode(x);
//ListNode* cur = phead->_prev;
//cur->_next = newnode;
//newnode->_prev = cur;
//newnode->_next = phead;
//phead->_prev = newnode;
insert(phead, x);
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
assert(phead && !ListEmpty(phead));
//ListNode* cur = phead->_prev;
//ListNode* prev = cur->_prev;
//free(cur);
//prev->_next = phead;
//phead->_prev = prev;
erase(phead->prev);
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
//ListNode* newnode = BuyListNode(x);
//ListNode* cur = phead->_next;
//newnode->_next = cur;
//cur->_prev = newnode;
//phead->_next = newnode;
//newnode->_prev = phead;
insert(phead->next, x);
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{
assert(!ListEmpty(phead));
//ListNode* cur = phead->_next;
//ListNode* next = cur->_next;
//free(cur);
//phead->_next = next;
//next->_prev = phead;
erase(phead->next);
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->_next;
while (cur != phead)
{
if (cur->_data == x) return cur;
cur = cur->_next;
}
return NULL;
}
// 修改某一节点的数据
void ListModify(ListNode* pos, LTDataType x)
{
assert(pos);
pos->_data = x;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyListNode(x);
ListNode* prev = pos->_prev;
newnode->_next = pos;
pos->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* next = pos->_next;
ListNode* prev = pos->_prev;
free(pos);
prev->_next = next;
next->_prev = prev;
}
test.h:
#include "DList.h"
void test1()
{
ListNode* plist = ListCreate();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
ListPushBack(plist, 6);
ListPrint(plist);
ListPopBack(plist);
ListPrint(plist);
ListPopBack(plist);
ListPrint(plist);
ListPopFront(plist);
ListPrint(plist);
ListPopFront(plist);
ListPrint(plist);
ListPopBack(plist);
ListPrint(plist);
ListPopBack(plist);
ListPrint(plist);
ListDestory(plist);
plist = NULL;
}
void test2()
{
ListNode* plist = ListCreate();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
ListPushBack(plist, 6);
ListPrint(plist);
ListErase(ListFind(plist, 3));
ListPrint(plist);
ListInsert(ListFind(plist, 4), 3);
ListPrint(plist);
ListDestory(plist);
plist = NULL;
}
int main()
{
//test1();
test2();
return 0;
}
😳写在最后
💝带头双向循环链表可以说实现起来是比较简单了,虽然它的结构比较复杂。所以以后在学习的过程中,看到复杂的东西不要怕,说不定还挺简单呢,如果看到不复杂的,也别太掉以轻心,说不定它展开来却很难呢。
❤️🔥后续将会持续输出有关数据结构的文章,你们的支持就是我写作的最大动力!文章来源:https://www.toymoban.com/news/detail-795288.html
感谢阅读本小白的博客,错误的地方请严厉指出噢~文章来源地址https://www.toymoban.com/news/detail-795288.html
到了这里,关于【数据结构】带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!