带头双向循环链表
2023-05-18 18:24:01 199浏览
一、如何实现带头双向循环链表
1.如何解决双向问题
双向的目的就是要让当前节点既要指向前一个节点，也要指向后一个节点，这一点的实现很简单，我们只要给每个节点配置两个指针即可。
双向链表也是由一个个节点串联起来，因为是双向链表，所以存在两个指针，pre指针指向当前当前节点的前一个结点，next指针指向当前节点的后一个节点。
如下图，是一个双向链表的一部分：
2.如何解决头节点以及循环的问题
循环的问题很好解决，我们来画图分析一下。
如上是一个双向链表，对于双向链表，除了头节点的pre指针和尾节点的next指针需要指向NULL,其余的pre与next指向都是指向当前节点的前一个节点与后一个节点。而要想链表循环，只要让头节点的pre指针指向尾节点，尾节点的next指针指向头节点即可，如下图：
而链表如果要带头节点，在链表为空时，我们首先需要对头节点进行初始化。如果是带头的单链表，我们会将头节点中的next指针初始化为空。但是对于双向循环链表的初始化来说，整个链表只有头节点自己一个节点，因此我们只要让头节点的pre指针和next指针指向头节点本身，这样既满足了循环和双向的问题也符合当链表为空时的情况（这两种情况pre和next都会指向头节点自己）。如下图：
3.带头双向循环链表节点的实现
每一个节点都包含三个变量，因此我们应当用结构体来实现
typedef int Datatype;
typedef struct ListPerfect
{
Datatype data;
struct ListPerfect* pre;
struct ListPerfect* next;
}LP;为了使用方便，我们用typedef重定义了结构体的数据类型为LP，变量data的类型重定义为Datatype。
4.带头双向循环链表的初始化
LP* Init()//建立头节点,初始化链表
{
LP* phead = Creativespace(0);
phead->pre = phead;//
phead->next = phead;
return phead;
}LP* Creativespace(Datatype x)//动态申请新节点并初始化
{
LP* newspace= (LP*)malloc(sizeof(LP));
assert(newspace);
newspace->data = x;
newspace->pre = NULL;
newspace->next = NULL;
}二、链表基本功能的实现
1.头插和尾插
void Pushfront(LP* phead, Datatype x)//头插
{
LP* new = Creativespace(x);
LP* head = phead->next;//指向头节点next指针指向的节点
//链表为空时，head指向的就是头节点
head->pre = new;
new->next = head;
new->pre = phead;
phead->next = new;//头插到这里就结束啦
}头插具体分析：
phead指针指向的始终是头节点
当链表为空时，head指向的就是头节点，new指向的要头插的节点。
head->pre=new使得头节点的pre指针指向new节点，new->next=head使得new节点的next指针指向头节点，new->pre=phead使得new节点的pre指针指向头节点，phead->next=new使得头节点的next指针指向new节点，到此new节点已经插入链表当中，并且满足双向和循环的要求。
而当链表不为空时，head指向的是存储数据的第一个节点，我们需要改变的指针有头节点的next，new节点的pre与next，节点一的pre，使得三个节点相互连接起来。head->pre = new;使得节点一的pre指针指向new节点，new->next = head;使得new节点的next指针指向节点一，new->pre = phead;使得new的pre指针指向头节点，phead->next = new;使得头节点的next指针指向new节点，也满足了双向循环链表的需求。
void Pushback(LP* phead, Datatype x)//尾插
{
LP* new = Creativespace(x);
LP* tail = phead->pre;
tail->next = new;
new->pre = tail;
new->next = phead;
phead->pre = new;
}对于尾插来说，链表为空或者不为空都是一样的，用tail指针指向未插入前的尾节点，我们只要让尾节点的next指针指向尾插节点，尾插节点的pre指针指向尾节点，next指针指向头节点，头节点的pre指针指向尾插节点就可以完美的连接节点。链表为空时，头节点就是尾节点，链表不为空时，尾节点就是当前链表的尾节点。区别只在于插在了谁的后头，而插入情况是相同的。我们对比一下不带头节点的单链表的尾插会发现，我们这里对链表的是实现更加简洁明了。
2.头删和尾插
void Popfront(LP* phead)//头删
{
if (phead->next == phead)//没有元素可以删除则直接返回
{
return;
}
LP* head = phead->next;//指向未头删的存储数据的第一个节点
//连接头节点与第二个节点，并且释放第一个节点的空间
phead->next = head->next;
head->next->pre = phead;
free(head);
head = NULL;
}void Popback(LP* phead)//尾删
{
if (phead->next == phead)//没有元素可以删除则直接返回
{
return;
}
LP* tail = phead->pre;//指向未尾删的尾节点
//连接尾节点的前一个结点与头节点，并释放尾节点
tail->pre->next = phead;
phead->pre = tail->pre;
free(tail);
tail = NULL;
}3.查找
LP* Find(LP* phead, Datatype x)//查找节点
{
assert(phead->next != phead);//链表不能为空
LP* start = phead->next;//指向第一个节点
while (start != phead)//从第一个节点开始寻找
{
if (start->data == x)
return start;//找到则返回地址
start = start->next;//指向下一个节点
}
return NULL;//出来代表没找到，返回空
}4.打印和销毁
void Prin(LP* phead)//打印
{
LP* start = phead->next;//指向第一个节点
while (start != phead)//start指向phead时，链表回到头节点
{
printf("%d->", start->data);//打印数据
start = start->next;//指向下一个节点
printf("NULL\n");
}void Destory(LP* phead)//销毁
{
LP* cur = phead->next;//指向第一个节点
while (cur!=phead)//结束条件，与打印相同
{
LP* next = cur->next;//提前存储下一个节点
free(cur);//释放当前指向的节点
cur = next;//指向下一个节点
}
cur = NULL;
//节点全部释放后，还剩下头节点，需要对头节点初始化
phead->pre = phead;
phead->next = phead;
}5.任意位置的插入和删除
void Insert(LP* phead, LP* pos, Datatype x)//在pos位置前插入节点
{
LP* new = Creativespace(x);
LP* pre = pos->pre;//指向pos位置的前一个结点
//，按照pre,new,pos的顺序重新连接
pre->next = new;
new->pre = pre;
new->next = pos;
pos->pre = new;
}void Erase(LP* phead, LP* pos)//删除pos位置的节点
{
assert(phead->next != phead);//链表为空无法删除
LP* pre = pos->pre;//指向删除位置的前一个结点
//连接pos的前一个与后一个结点，并释放pos位置的结点
LP* next = pos->next;
pre->next = next;
next->pre = pre;
free(pos);
}三、带头双向循环链表的优势
对比结构最简单的无头单向不循环链表，我们就会发现，在实现链表的功能时，带头双向循环链表只需要几行代码就可以捋清楚结点直接的关系，并建立结点之间的联系，而单链表在实现链表功能时，往往需要对链表进行判空，代码量也会更大，逻辑结构上比较复杂。
相比单链表，带头双向循环链表更像是我们的梦中情表，虽然它的结构稍微复杂了一些，但是它给我们带来的便利和好处都是单链表远远无法比拟的，它使得链表在实现上就如我们想象的一样简单。
四、整体代码（附加对链表的测试）
1.ListPerfect.h
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int Datatype;
typedef struct ListPerfect
{
Datatype data;
struct ListPerfect* pre;
struct ListPerfect* next;
}LP;
LP* Init();//建立头节点
LP* Creativespace(Datatype x);//创造新节点
LP* Find(LP* phead, Datatype x);//找某个节点
void Insert(LP* phead, LP* pos, Datatype x);//在pos 前插入
void Erase(LP* phead, LP* pos);//删除pos位置的节点
void Pushback(LP* phead, Datatype x);//尾插
void Pushfront(LP* phead, Datatype x);//头插
void Popback(LP* phead);//尾删
void Popfront(LP* phead);//头删
void Prin(LP* phead);//打印
void Destory(LP* phead);//销毁2.ListPerfect.c
链表所有功能的实现在目录第二章内容链表基本功能的实现当中都有，想要自己参考编写.c文件时只要记得包含头文件，再把代码拿过去即可
3.test.c
#define _CRT_SECURE_NO_WARNINGS
#include"Listperfect.h"
void test()
{
LP* phead = Init();//初始化了头节点的空链表
/*Pushback(phead, 1);//尾插测试
Pushback(phead, 2);
Pushback(phead, 3);
Pushback(phead, 4);*/
Pushfront(phead, 0);//头插测试
Pushfront(phead, -1);
Pushfront(phead, -2);
Pushfront(phead, -3);
/*Popback(phead);//尾删与头删测试
Popfront(phead);*//
LP* find = Find(phead, -3);//查找测试
if (find)
{
Insert(phead, find, 30);//任意位置插入测试（在位置前插入）
}
Erase(phead, find);//任意位置删除测试
Prin(phead);//打印测试
Destory(phead);//销毁测试
Prin(phead);
}
int main()
{
test();
}五、最后
代码属于临时编写，如有错误，欢迎纠错，谢谢。
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
您可能感兴趣的博客
