前言
hello,大家好呀,我是Humble,本篇博客承接之前的C语言进阶——数据结构之链表
的内容(没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~),上次我们重点说了链表中的单链表,即不带头单向不循环链表
还说到了链表的分类虽然有8种,但实际上最常用的还是单链表和双向链表(带头双向循环链表)
所以今天我们就来讲讲双向链表的实现吧~
双向链表的结构
下面是双向链表的一个图示:
双向链表,全称为带头双向循环链表
双向与循环这2个概念很好理解,所以我们下面看一下什么是带头
这个“带头”跟之前我们说的“头节点”是两个概念,
实际前面在说单链表时有称呼并不严谨,但是为了大家更好的理解就直接称为单链表的头节点
带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨 的
哨兵位”存在的意义: 遍历循环链表避免死循环
对于双向链表的节点,我们这样定义:
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next; //指针保存下一个节点的地址
struct ListNode* prev; //指针保存前一个节点的地址
}LTNode;
双向链表的实现
下面我们来实现一下双向链表的各个功能
其实当我们掌握了单链表的各个操作后,我们会发现其实双向链表虽然在结构上看着比单链表复杂不少,但在实现上并不难~
我们首先在VS上创建一个List的工程,再分别创建List.h头文件,List.c源文件以及Test.c测试文件,在这之上,我们依次去实现双向链表的各个功能~
初始化 LTInit
首先是初始化,因为双向链表多了一个头节点,即哨兵位,所以我们需要对其初始化~
代码如下:
LTNode* LTInit() //对哨兵位初始化~
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
perror("malloc fail!");
exit(1);
}
phead->data = -1;
phead->next =phead->prev =phead;
return phead;
}
下面来测试一下~
void ListTest()
{
LTNode* plist = LTInit();
}
int main()
{
ListTest();
return 0;
}
这里我们通过调试来观察一下初始化是否成功:
另外,因为我们后面还要多次用到申请节点空间,所以我们单独封装一个函数LTBuyNode,
这样后面再使用只需要调用它就可以了
LTNode* LTBuyNode(LTDataType x) //申请新节点
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
同时,关于上面初始化的代码我们也可以进行简化:
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
尾插LTPushBack
好,有了这样一个链表,下面我们实现一下尾插LTPushBack
代码如下:
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //phead不能为空
LTNode* newnode = LTBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
同样,我们在Test.c文件中进行测试
void ListTest()
{
LTNode* plist = LTInit();
//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
}
int main()
{
ListTest();
return 0;
}
调试后,,结果如下:
这样尾插的功能就实现了~
不过,我们后续如果一直用调试的方式去观察未免有些麻烦,所以这里我们也封装一个打印的函数
//打印
void LTPrint(LTNode* phead)
{
//phead不能为空
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
}
有了打印函数,我们再测试尾插,只要运行代码就可以了
结果如下:
头插LTPushFront
接下来,我们来实现一下头插LTPushFront
关于头插,有一个需要注意的点,头插要插在第一个、有效节点之前,而不是在哨兵位之前
头插代码如下:
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->next
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
老规矩,写完后,我们来测试一下:
void ListTest()
{
LTNode* plist = LTInit();
//头插
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
}
int main()
{
ListTest();
return 0;
}
尾删 LTPopBack
写删除操作时要注意:当链表为空时(只有一个哨兵位节点),要assert断言
代码如下:
void LTPopBack(LTNode* phead)
{
assert(phead);
//链表为空:只有一个哨兵位节点
assert(phead->next != phead);
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = NULL;
}
下面是测试代码以及结果:
void ListTest()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
//尾删
LTPopBack(plist);
LTPrint(plist);
printf("\n");
LTPopBack(plist);
LTPrint(plist);
printf("\n");
LTPopBack(plist);
LTPrint(plist);
}
int main()
{
ListTest();
return 0;
}
头删LTPopFront
接下来我们来实现头部删除LTPopFront
直接上代码:
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->next;
LTNode* next = del->next;
next->prev = phead;
phead->next = next;
free(del);
del = NULL;
}
下面来测试:
void ListTest()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
//头删
LTPopFront(plist);
LTPrint(plist);
printf("\n");
LTPopFront(plist);
LTPrint(plist);
printf("\n");
LTPopFront(plist);
LTPrint(plist);
printf("\n");
}
int main()
{
ListTest();
return 0;
}
运行结果如下:
查找LTFind
在前面我们已经实现了插入的4种操作,下面我们看一下查找
代码如下:
LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
return pcur;
pcur = pcur->next;
}
return NULL;
}
来测试一下吧~
void ListTest()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTNode* findRet = LTFind(plist, 3);
if (findRet == NULL)
printf("未找到!\n");
else
printf("找到了!\n");
}
int main()
{
ListTest();
return 0;
}
在指定位置之后插入数据LTInsert
插入代码如下:
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
测试代码如下:
void ListTest()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4); //4->3->2->1->
LTNode* findRet = LTFind(plist, 3);
LTInsert(findRet,66); //预期结果为 //4->3->66->2->1->
LTPrint(plist);
}
int main()
{
ListTest();
return 0;
}
运行结果:
删除pos位置的数据LTErase
删除代码如下:
//删除pos位置的数据
void LTErase(LTNode * pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
}
下面我们来进行测试~
void ListTest()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4); //4->3->2->1->
LTNode* findRet = LTFind(plist, 3);
LTErase(findRet);
LTPrint(plist); //预期结果为:4->2->1->
}
int main()
{
ListTest();
return 0;
}
链表的销毁LTDestroy
最后我们看一下双向链表的销毁LTDestroy
注意:我们这里的函数要传的是地址,也就是要用到二级指针,因为这里我们直接要对链表的哨兵位做修改,要与前面的代码相区分哦~
销毁的代码如下:
void LTDesTroy(LTNode** pphead)
{
assert(pphead);
//哨兵位不能为空
assert(*pphead);
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//链表中只有一个哨兵位
free(*pphead);
*pphead = NULL;
}
至于销毁操作的调试,大家可以自行测试,这里就不再赘述了
到此,我们就把双向链表的操作给讲完了
事实上学会了单链表和双向链表的操作,即使将来遇到链表的其他6种类型也可以游刃有余,很快上手并解决问题的,所以建议大家还是要好好掌握单链表和双向链表的操作~
结语
好了,今天关于链表的分享就到这里了,如果对大家有帮助就太好啦~
在学习编程的道路上Humble与各位同行,加油吧各位!
最后,希望大家点个免费的赞或者关注吧(感谢感谢),也欢迎大家订阅我的专栏
让我们在接下来的时间里一起成长,一起进步吧!