安庆商务网站建设,网站建设 会议主持稿,wordpress二开,建筑工程的公司目录 一、前言
二、带头双向循环链表
1.带头双向循环链表的结构
#xff08;1)什么是带头#xff1f; (2)什么是双向呢#xff1f;
#xff08;3#xff09;那什么是循环呢#xff1f;
2.带头双向循环链表的实现
#xff08;1#xff09;节点结构
#xff08;2…
目录 一、前言
二、带头双向循环链表
1.带头双向循环链表的结构
1)什么是带头 (2)什么是双向呢
3那什么是循环呢
2.带头双向循环链表的实现
1节点结构
2创建链表的头节点也即哨兵节点
3创建其他节点和链表打印
4链表尾插和尾删功能的实现
5链表的头插和头删
6链表的查找
7双链表在pos位置前后插入和删除pos位置功能 一、前言 在上一篇博客中我们实现的是单链表。我们知道链表有8种结构由单向和双向、有头和无头、循环和非循环组合而成。单链表就是无头单向非循环链表。它是一种结构简单的链表通常不会用来单独作为存储数据用实际中更多的是作为其它数据结构的子结构存在如哈希桶、图的邻接等等。单链表虽然在头插、头删方面很方便但在尾插和尾删又比不过顺序表。那么有没有一种链表在头插头删和尾插尾删上都很方便呢 当然有那就是链表中的“王者”------带头双向循环链表。它的结构非常复杂但效率极高。让我们来看看带头双向循环链表的结构吧
二、带头双向循环链表
1.带头双向循环链表的结构
1)什么是带头
指链表中没有存储数据的节点时头指针仍然指向一个节点这个节点不存储数据只起到站位的作用其后才是链表的实际数据节点因此它也被成为哨兵节点。
它的作用是什么呢在单链表中我们在改变头指针的链接对象时需要使用二级指针。有了哨兵节点我们就不需要二级指针。在执行插入、删除等操作时也不需要对链表是否为空或是否为最后一个节点进行特殊判断从而使代码更加简洁和统一也让我们不至于被绕晕。 (2)什么是双向呢
看图就可以明白。
节点结构体指针域中有两个指针。一个指向上一个节点一个指向下一个节点。如此就可以由一个链表中的一个节点位置得到所有节点的位置。
3那什么是循环呢
循环链表则是将尾节点的后继指针指向头结点而头结点的前驱指针指向尾节点从而形成一个闭环。这样的设计使得从链表的任何一个节点开始都可以很方便地遍历整个链表无论是向前还是向后。也即
循环链表的哨兵节点的头指针指向尾节点尾节点的next指针指向哨兵节点。
不要看带头双向循环链表的结构很复杂就认为它的实现也很难正因为结构如此它的实现也避开了需多难题。相比于单链表的实现它反而简单。
2.带头双向循环链表的实现
1节点结构
为了实现双向那么作为节点的结构体就需要有两个指针和存储数据的位置。代码如下
typedef int type;
typedef struct ListNde
{struct ListNde* next;//指向下一个节点struct ListNde* head;//指向上一个节点type data;//存储数据
}ListNode;
2创建链表的头节点也即哨兵节点
先看代码
ListNode* ListCreate()
{//动态申请一个结构体空间ListNode* head (ListNode*)malloc(sizeof(ListNode));if (head NULL){perror(ListCreate::malloc);return NULL;}//使节点不存储数据head-data NULL;//因为作为头节点存在因此在没有其他节点时需要让//前指针和后指针都指向自己head-head head;head-next head;//如果不返回那就需要传二级指针来使头指针和哨兵节点链接return head;
}
为什么哨兵节点的前指针和后指针都要指向自己。看图 3创建其他节点和链表打印
创建其他节点和之前单链表创建节点一样代码如下
ListNode* BuyListNode()
{ListNode* ptr (ListNode*)malloc(sizeof(ListNode));if (ptr NULL){perror(BuyListNode::malloc);return NULL;}ptr-head NULL;ptr-next NULL;return ptr;
}
链表打印和单链表打印大至一样循环打印即可但与单链表打印不同的是它需要有一个循环终止条件单纯的不为空可不行带头双向循环链表可没有为空。而且因为哨兵节点没有存储数据因此要避免打印哨兵节点。代码如下
void ListPrint(ListNode* plist)
{//不打印哨兵节点哨兵节点不存储任何数据ListNode* ptr plist-next;//以这个代表哨兵节点printf(head);//循环打印while (ptr){printf(%d, ptr-data);//因为带头双向循环链表尾节点和哨兵节点是相链接的//所以需要一个条件来作为循环的终止条件if (ptr-next plist){//ptr指向尾节点时ptr-next指向哨兵节点退出循环break;}ptr ptr-next;}
}
4链表尾插和尾删功能的实现
先看图 我们想要使新节点和链表链接最好带顺序的去进行指针的互换不然容易漏掉或者换错。我们先让尾节点的后指针指向新节点新节点的前指针指向尾节点新节点的后指针指向哨兵节点哨兵节点的前指针指向新节点这样按顺序来既不容易漏掉也具有逻辑美更容易理解。代码如下
void ListPushBack(ListNode* plist)
{//断言判断plist不为空因为有哨兵节点存在那么plist//传过来的必定不为空assert(plist);ListNode* ptr plist;//由ptr-head得到尾节点ListNode* tail ptr-head;//申请一个新的节点ListNode* NewNode BuyListNode();printf(请输入要尾插的数字\n);scanf(%d, NewNode-data);//尾插尾节点的next指向新节点tail-next NewNode;//新节点的前指针指向尾节点NewNode-head tail;//新节点的后指针指向哨兵节点NewNode-next ptr;//哨兵节点的前指针指向新节点ptr-head NewNode;
}
链表的尾删也很简单只需按上述步骤逆着来然后释放要删除的空间就行了。代码如下
void ListPopBack(ListNode* plist)
{assert(plist);ListNode* ptr plist;ListNode* tail ptr-head;ListNode* tail1 tail-head;tail1-next ptr;ptr-head tail1;free(tail);printf(删除成功\n);
}
5链表的头插和头删
链表的头插和头删和链表的尾插尾删差不多只不过这里的头插和头删是在哨兵节点的下一个节点不是让你删或者插在哨兵节点后面。并且在所有带头链表的删除功能里一定不能删除哨兵节点。那会出现野指针的程序运行也会不安全。代码如下
// 双向链表头插
void ListPushFront(ListNode* plist)
{assert(plist);ListNode* ptr plist;ListNode* newnode BuyListNode();ListNode* ptrnext ptr-next;ptr-next newnode;newnode-head ptr;newnode-next ptrnext;ptrnext-head newnode;printf(请输入头插数字\n);scanf(%d, newnode-data);printf(插入成功\n);
}
// 双向链表头删
void ListPopFront(ListNode* plist)
{assert(plist);ListNode* ptr plist;ListNode* ptrnext2 ptr-next-next;free(ptr-next);ptr-next ptrnext2;ptrnext2-head ptr;printf(删除成功\n);
}
6链表的查找
ListNode* ListFind(ListNode* plist)
{assert(plist);int a;printf(请输入要查找的数字\n);scanf(%d, a);ListNode* ptr plist-next;while (ptr){//查找到直接返回if (ptr-data a){printf(查找成功\n);return ptr;}//一定要有这个条件防止查找不到陷入死循环if (ptr-next plist){printf(查找失败未找到\n);return NULL;}ptr ptr-next;}
}
7双链表在pos位置前后插入和删除pos位置功能
这些和头插头删没有多大区别且双链表在pos位置前插入比单链表简单。代码如下
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos)
{assert(pos);ListNode* front pos-head;ListNode* ptr pos;ListNode* newnode BuyListNode();front-next newnode;newnode-head front;newnode-next ptr;ptr-head newnode;printf(请输入要在pos前插入的数\n);scanf(%d, newnode-data);printf(插入成功\n);
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* front pos-head;ListNode* posnext pos-next;free(pos);front-next posnext;posnext-head front;printf(删除成功\n);
}
// 双向链表在pos位置之后插入
void ListInsertAfter(ListNode* pos)
{assert(pos);ListNode* posnext pos-next;ListNode* newnode BuyListNode();ListNode* ptr pos;ptr-next newnode;newnode-head ptr;newnode-next posnext;posnext-head newnode;printf(请输入要插入的数字\n);scanf(%d, newnode-data);
}
这样一个带头双向循环链表也就完成了。单链表和带头双向循环链表虽然是两个极端但当我们可以自主实现后其他的链表结构我们也可以信手拈来。
全部代码如下
listnode.h
#pragma once
#pragma warning(disable : 4996)
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int type;
typedef struct ListNde
{struct ListNde* next;//指向下一个节点struct ListNde* head;//指向上一个节点type data;//存储数据
}ListNode;
// 创建链表的头节点也即哨兵节点.
ListNode* ListCreate();
//创建其他节点
ListNode* BuyListNode();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 双向链表在pos位置之后插入
void ListInsertAfter(ListNode* pos);
Flistnode.c:
#includelistnode.h
ListNode* ListCreate()
{//动态申请一个结构体空间ListNode* head (ListNode*)malloc(sizeof(ListNode));if (head NULL){perror(ListCreate::malloc);return NULL;}//使节点不存储数据head-data NULL;//因为作为头节点存在因此在没有其他节点时需要让//前指针和后指针都指向自己head-head head;head-next head;//如果不返回那就需要传二级指针来使头指针和哨兵节点链接return head;
}ListNode* BuyListNode()
{ListNode* ptr (ListNode*)malloc(sizeof(ListNode));if (ptr NULL){perror(BuyListNode::malloc);return NULL;}ptr-head NULL;ptr-next NULL;return ptr;
}
void ListDestory(ListNode* plist)
{//assert(plist);ListNode* ptr plist-next;while (ptr){ListNode* ptrnext ptr-next;free(ptr);if (ptrnext plist){break;}ptr ptrnext;}free(plist);printf(销毁成功\n);
}
void ListPrint(ListNode* plist)
{//不打印哨兵节点哨兵节点不存储任何数据ListNode* ptr plist-next;//以这个代表哨兵节点printf(head);//循环打印while (ptr){printf(%d, ptr-data);//因为带头双向循环链表尾节点和哨兵节点是相链接的//所以需要一个条件来作为循环的终止条件if (ptr-next plist){//ptr指向尾节点时ptr-next指向哨兵节点退出循环break;}ptr ptr-next;}
}void ListPushBack(ListNode* plist)
{//断言判断plist不为空因为有哨兵节点存在那么plist//传过来的必定不为空assert(plist);ListNode* ptr plist;//由ptr-head得到尾节点ListNode* tail ptr-head;//申请一个新的节点ListNode* NewNode BuyListNode();printf(请输入要尾插的数字\n);scanf(%d, NewNode-data);//尾插尾节点的next指向新节点tail-next NewNode;//新节点的前指针指向尾节点NewNode-head tail;//新节点的后指针指向哨兵节点NewNode-next ptr;//哨兵节点的前指针指向新节点ptr-head NewNode;
}void ListPopBack(ListNode* plist)
{assert(plist);ListNode* ptr plist;ListNode* tail ptr-head;ListNode* tail1 tail-head;tail1-next ptr;ptr-head tail1;free(tail);printf(删除成功\n);
}
// 双向链表头插
void ListPushFront(ListNode* plist)
{assert(plist);ListNode* ptr plist;ListNode* newnode BuyListNode();ListNode* ptrnext ptr-next;ptr-next newnode;newnode-head ptr;newnode-next ptrnext;ptrnext-head newnode;printf(请输入头插数字\n);scanf(%d, newnode-data);printf(插入成功\n);
}
// 双向链表头删
void ListPopFront(ListNode* plist)
{assert(plist);ListNode* ptr plist;ListNode* ptrnext2 ptr-next-next;free(ptr-next);ptr-next ptrnext2;ptrnext2-head ptr;printf(删除成功\n);
}ListNode* ListFind(ListNode* plist)
{assert(plist);int a;printf(请输入要查找的数字\n);scanf(%d, a);ListNode* ptr plist-next;while (ptr){//查找到直接返回if (ptr-data a){printf(查找成功\n);return ptr;}//一定要有这个条件防止查找不到陷入死循环if (ptr-next plist){printf(查找失败未找到\n);return NULL;}ptr ptr-next;}
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos)
{assert(pos);ListNode* front pos-head;ListNode* ptr pos;ListNode* newnode BuyListNode();front-next newnode;newnode-head front;newnode-next ptr;ptr-head newnode;printf(请输入要在pos前插入的数\n);scanf(%d, newnode-data);printf(插入成功\n);
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* front pos-head;ListNode* posnext pos-next;free(pos);front-next posnext;posnext-head front;printf(删除成功\n);
}
// 双向链表在pos位置之后插入
void ListInsertAfter(ListNode* pos)
{assert(pos);ListNode* posnext pos-next;ListNode* newnode BuyListNode();ListNode* ptr pos;ptr-next newnode;newnode-head ptr;newnode-next posnext;posnext-head newnode;printf(请输入要插入的数字\n);scanf(%d, newnode-data);
}
listnode.c:
#includelistnode.h
ListNode* pplist NULL;
int main()
{int a;pplist ListCreate();ListNode* pos NULL;do{printf(请输入数字);scanf(%d, a);switch (a){case 1:// 双向链表打印ListPrint(pplist);break;case 2:// 双向链表尾插ListPushBack(pplist);break;case 3:// 双向链表的头插ListPushFront(pplist);break;case 4:// 双向链表的尾删ListPopBack(pplist);break;case 5:// 双向链表头删ListPopFront(pplist);break;case 6:// 双向链表查找pos ListFind(pplist);break;case 7:// 双向链表在pos位置之后插入xListInsertAfter(pos);break;case 8:// 在pos的前面插入ListInsert(pos);break;case 9:// 删除pos位置ListErase(pos);break;case 0://链表的销毁ListDestory(pplist);printf(退出\n);break;default:printf(输入数字错误请重新输入\n);break;}} while (a);return 0;
}至此链表就完了大家可以去力扣或者牛客上找一些链表的题做一做来巩固一下。提个建议如果在链表中或者说在整个数据结构中画图永远是你最好的伙伴。
