网站导航
> 文档中心 > 链表界的“扛把子”—双向带头循环链表

链表界的“扛把子”—双向带头循环链表

网友: 文档中心 2022-04-10 11:01:00

目录

一：链表的分类

二：链表的实现

2-1：创建链表

2-2：创建新的结点

2-3：初始化链表 

2-4：打印链表  

2-5：销毁链表  

 三：链表的核心功能

3-1：尾插

3-2：尾删

3-3：链表查找

3-4：在pos结点前插入数据

3-5：头插

3-6：删除pos位置结点

3-7：头删

四：源码 

一：链表的分类

链表的分类分为以下几种：

 

在实际中链表的结构非常多样，以上情况组合起来就有8种链表结构。我们在前面已经讲过最简单的结构：单向无头非循环链表。并且在我们所刷的OJ题里也涉及到了有无头结点情况，今天我们讲解最复杂结构：双向带头循环链表。在我们讲解之前我们先了解一下这两种结构在链表界的重要性。

1：无头单向非循环链表：

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

2：带头双向循环链表：

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

                                 正文开始

二：链表的实现

2-1：创建链表

思路：

因为链表为双向链表，所以在我们创建的结构体中需要创建两个结构体指针prev和next，其中prev指向上一个结点，next指向下一个结点。

Lish.h文件 

typedef int LTDataType; //重定义方便数据类型的转换，这里以int为主typedef struct ListNode{LTDataType data;//存储数据struct ListNode* next; //存储下一个结点的地址struct ListNode* prev; //存储上一个结点的地址}LTNode;

 2-2：创建新的结点

Lish.h文件 

//创建一个结点LTNode* BuyLTNode(LTDataType x);

List.c文件 

//创建一个结点LTNode* BuyLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) //检查内存是否开辟成功{printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}

 2-3：初始化链表 

思路1：

我们所创建的链表为带头链表，所以我们在初始化链表的时候就需要把哨兵位头结点创建好，哨兵位头结点不存储数据，但却有着至关重要的作用，当链表为空链表时哨兵位头结点仍存在。同时形参的改变并不会影响实参，所以我们在传参的时候需要传二级指针，因为保存哨兵位头结点地址的地址不可能为空，所以我们需要用assert进行断言，同时因为是双向链表，所以哨兵位结点的prev和next都指向自己。

⭐：对于不可能出现空指针的情况，我们需要断言。

Lish.h文件 

//初始化链表(二级指针)void ListInit(LTNode pphead);

List.c文件 

//初始化链表(二级指针)void ListInit(LTNode pphead){assert(pphead); //pphead不可能为空指针*pphead = BuyLTNode(0);//创建一个结点给哨兵位头结点//哨兵位头结点初始化next和prev不能为空，需都指向自己(*pphead)->next = *pphead;//注意优先级问题，需要加括号。(*pphead)->prev = *pphead;}

思路2：

如果我们想传一级指针也可以，只不过函数的返回值为结构体指针。

Lish.h文件 

//初始化链表(一级指针)LTNode* ListInit();

List.c文件 

//初始化链表(一级指针)LTNode* ListInit(){LTNode*phead = BuyLTNode(0);phead->prev = phead;phead->next = phead;return phead;}

 2-4：打印链表  

思路：

首先需要明确的是哨兵位结点不存储数据，所以我们要打印链表数据就需要创建一个指针变量cur从phead->next开始依次遍历打印链表，因为链表是循环的，所以当cur回到phead时停止。

Lish.h文件 

//打印数据void ListPrint(LTNode* phead);

List.c文件 

//打印数据void ListPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;//cur从phead->next开始while (cur != phead)//cur回到phead时停止{printf("%d ", cur->data);cur = cur->next;}printf("\n");}

  2-5：销毁链表  

思路：

销毁链表我们可以创建指针变量cur遍历链表，先把有效数据的结点free掉，最后再把哨兵位结点free掉即可。

Lish.h文件 

//销毁链表void ListDestory(LTNode* phead);

List.c文件 

//销毁链表void ListDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead)//从第一个结点开始依次销毁{LTNode* next = cur->next;free(cur);cur = next;}//销毁哨兵结点free(phead);phead = NULL;}

看到这里是不是觉得双链表也就那样，并没有想象中的那么难，前面已经理解的话我们继续往下走，不理解的话多看几遍多敲敲代码，说不定过一会就理解了~~

 三：链表的核心功能

3-1：尾插

思路：

尾插就体现了双向链表的结构优势，因为哨兵位头节点的phead的prev指向的就是链表尾结点的地址，所以我们找到了尾结点后就需要再创建一个结点存储插入数据。

 Lish.h文件 

//尾插一个结点void ListPushBack(LTNode* phead, LTDataType x);

List.c文件 

//尾插一个结点void ListPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* tail = phead->prev;//保存尾结点地址LTNode* newnode = BuyLTNode(x);//创建一个新的结点//循环链表tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

Test.c文件

void TestList1(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);}

3-2：尾删

思路：

当我们谈到尾删时，双向链表的结构优势再次体现出来。对于传统的单向链表如果想要实现尾删就必须遍历链表，找到尾结点将其free掉，遍历链表时间复杂度为O(N)。而对于双向链表来说因为链表是循环的，所以链表尾结点的地址时刻存在哨兵位结点的prev里面，时间复杂度为O(1)，我们可以创建指针变量tail保存尾结点地址。同时删除尾结点的同时我们也要保证尾结点的上一个结点地址被保存，所以我们创建指针变量tailPrev指向tail的prev，然后把tailPrev的next指向哨兵位结点phead，把哨兵位phead的prev置成tailPrev。

 Lish.h文件 

//尾删一个结点void ListPopBack(LTNode* phead);

List.c文件 

//尾删一个结点void ListPopBack(LTNode* phead){assert(phead);//哨兵位不能为空assert(phead->next != phead);//链表不能为空，防止删除哨兵位结点LTNode* tail = phead->prev;//尾结点放入tailLTNode* tailPrev = tail->prev;//新的尾结点tailPrevfree(tail);tail = NULL;//循环链表tailPrev->next = phead;phead->prev = tailPrev;}

Test.c文件

void TestList2(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);    ListPrint(pList);}

 3-3：链表查找

思路：

创建一个指针变量cur指向哨兵位phead的next，然后开始遍历链表，判断cur->data是否为查找的数据，如果是就返回cur，不是继续遍历（cur=->cur->next),终止条件是cur指向哨兵位结点。

 Lish.h文件 

//链表查找LTNode* ListFind(LTNode* phead, LTDataType x);

List.c文件 

//链表查找LTNode* ListFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

 3-4：在pos结点前插入数据

思路：

用上一个查找数据函数查找pos，然后在pos之前插入数据：创建一个新的结点newnode，pos上一个结点的next指向新的结点newnode，同时把newnode的prev指向pos上一个结点，newnode的next指向pos，pos的prev指向newnode。

Lish.h文件 

//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x);

List.c文件 

//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x){assert(pos);//创建插入结点LTNode* newnode = BuyLTNode(x);//存储pos上一个结点地址LTNode* posPrev = pos->prev;//循环链表newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;}

Test.c文件

void TestList3(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);LTNode* pos = ListFind(pList, 3);if (pos)//判断链表中是否有要查找的元素{ListInsert(pos, 30);//在数字3前插入30}ListPrint(pList);}

⭐：有了这个函数那么尾插也就可以更改一下，直接调用这个函数。

//尾插一个结点void ListPushBack(LTNode* phead, LTDataType x){      assert(phead);ListInsert(phead, x);}

 3-5：头插

思路：

同样的，头插我们也可以引用ListInsert函数，当pos=phead->next时，我们实现的就是头插。

Lish.h文件 

//头插void ListPushFront(LTNode* phead, LTDataType x);

List.c文件 

//头插void ListPushFront(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead->next, x);}

Test.c文件

void TestList4(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);//头插10和20ListPushFront(pList, 10);ListPushFront(pList, 20);ListPrint(pList);}

 3-6：删除pos位置结点

思路：

创建两个指针变量prev和next分别保存pos上一个结点和下一个结点的地址，然后将pos结点free掉，连接prev和next。

Lish.h文件 

//删除pos处结点void ListErase(LTNode* pos);

List.c文件 

//删除pos处结点void ListErase(LTNode* pos){assert(pos);//保存pos前一个结点LTNode* prev = pos->prev;//保存pos下一个结点LTNode* next = pos->next;free(pos);pos = NULL;//连接链表prev->next = next;next->prev->prev;}

Test.c文件

void TestList5(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);LTNode* pos = ListFind(pList, 3);if (pos)//判断链表中是否有要查找的元素{ListErase(pos);//删除pos位结点 pos=NULL//防止野指针}ListPrint(pList);}

⭐：当我们有了ListErase函数后，直接调用此函数就能实现尾删。

void ListPopBack(LTNode* phead){    assert(phead);assert(phead->next != phead);ListErase(phead->prev);}

 3-7：头删

思路：

直接调用ListErase函数，删除head->next位置结点。

Lish.h文件 

//头删void ListPopFront(LTNode* phead);

List.c文件 

//头删void ListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);ListErase(phead->next);}

Test.c文件

void TestList6(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPushBack(pList, 5);ListPushBack(pList, 6);ListPrint(pList);//头插三个元素ListPushFront(pList, 0);ListPushFront(pList, -1);ListPushFront(pList, -2);ListPrint(pList);//尾删三个元素ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPrint(pList);//头删三个元素ListPopFront(pList);ListPopFront(pList);ListPopFront(pList);ListPrint(pList);}

接口终于都实现完了~

 

四：源码 

List.h文件

#pragma once#include #include #include typedef int LTDataType; //重定义方便数据类型的转换，这里以int为主typedef struct ListNode{LTDataType data;//存储数据struct ListNode* next; //存储下一个结点的地址struct ListNode* prev; //存储上一个结点的地址}LTNode;//初始化链表(二级指针)void ListInit(LTNode pphead);//初始化链表(一级指针)//LTNode* ListInit();//销毁链表void ListDestory(LTNode* phead);//打印数据void ListPrint(LTNode* phead);//创建一个结点LTNode* BuyLTNode(LTDataType x);//尾插一个结点void ListPushBack(LTNode* phead, LTDataType x);//尾删一个结点void ListPopBack(LTNode* phead);//头插void ListPushFront(LTNode* phead, LTDataType x);//头删void ListPopFront(LTNode* phead);//链表查找LTNode* ListFind(LTNode* phead, LTDataType x);//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x);//删除pos处结点void ListErase(LTNode* pos);

List.c文件

#include "List.h"//初始化链表(二级指针)void ListInit(LTNode pphead){assert(pphead);*pphead = BuyLTNode(0);//创建一个结点给哨兵位头结点//哨兵位头结点初始化next和prev不能为空，需都指向自己(*pphead)->next = *pphead;//注意优先级问题，需要加括号。(*pphead)->prev = *pphead;}初始化链表(一级指针)//LTNode* ListInit()//{//LTNode*phead = BuyLTNode(0);//phead->prev = phead;//phead->next = phead;//return phead;//}//销毁链表void ListDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead)//从第一个结点开始依次销毁{LTNode* next = cur->next;free(cur);cur = next;}//销毁哨兵结点free(phead);phead = NULL;}//打印数据void ListPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;//cur从phead->next开始while (cur != phead)//cur回到phead时停止{printf("%d ", cur->data);cur = cur->next;}printf("\n");}//创建一个结点LTNode* BuyLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}//尾插void ListPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* tail = phead->prev;//保存尾结点地址LTNode* newnode = BuyLTNode(x);//创建一个新的结点//循环链表tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//法二/*assert(phead);ListInsert(phead, x);*/}//尾删void ListPopBack(LTNode* phead){assert(phead);//哨兵位不能为空assert(phead->next != phead);//链表不能为空，防止删除哨兵位结点LTNode* tail = phead->prev;//尾结点放入tailLTNode* tailPrev = tail->prev;//新的尾结点tailPrevfree(tail);tail = NULL;//循环链表tailPrev->next = phead;phead->prev = tailPrev;/*assert(phead);assert(phead->next != phead);ListErase(phead->prev);*/}//链表查找LTNode* ListFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x){assert(pos);//创建插入结点LTNode* newnode = BuyLTNode(x);//存储pos上一个结点地址LTNode* posPrev = pos->prev;//循环链表newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;}//头插void ListPushFront(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead->next, x);}//删除pos处结点void ListErase(LTNode* pos){assert(pos);//保存pos前一个结点LTNode* prev = pos->prev;//保存pos下一个结点LTNode* next = pos->next;free(pos);pos = NULL;//连接链表prev->next = next;next->prev=prev;}//头删void ListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);ListErase(phead->next);}

Test.c文件

#include "List.h"void TestList1(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);}void TestList2(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);    ListPrint(pList);}void TestList3(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);LTNode* pos = ListFind(pList, 3);if (pos)//判断链表中是否有要查找的元素{ListInsert(pos, 30);//在数字3前插入30}ListPrint(pList);}void TestList4(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);//头插10和20ListPushFront(pList, 10);ListPushFront(pList, 20);ListPrint(pList);}void TestList5(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPrint(pList);LTNode* pos = ListFind(pList, 3);if (pos)//判断链表中是否有要查找的元素{ListErase(pos);//删除pos位结点pos = NULL;}ListPrint(pList);}void TestList6(){LTNode* pList = NULL;ListInit(&pList);ListPushBack(pList, 1);ListPushBack(pList, 2);ListPushBack(pList, 3);ListPushBack(pList, 4);ListPushBack(pList, 5);ListPushBack(pList, 6);ListPrint(pList);//头插三个元素ListPushFront(pList, 0);ListPushFront(pList, -1);ListPushFront(pList, -2);ListPrint(pList);//尾删三个元素ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPrint(pList);//头删三个元素ListPopFront(pList);ListPopFront(pList);ListPopFront(pList);ListPrint(pList);}int main(){/*TestList1();*//*TestList2();*//*TestList3();*//*TestList4();*//*TestList5();*/TestList6();return 0;}

看完觉得有收获的要记得点赞噢~ 

 

全民K歌电脑版

网络标签：

相关问题