C语言简单的数据结构：双向链表的实现
目录：
1.双向链表的结构和初始化
1.1双向链表的结构
之前我们的单向链表指的是：不带头单向不循环链表
而双向链表指的是：带头双向循环链表
其中头节点为哨兵位（不存储任何数据），尾部要指向哨兵位
它的节点有：数据，指向下一个节点的指针和指向下一个节点的指针
这就是双向链表的节点定义，写入VS：
1.2双向链表的初始化
当双向链表为NULL时，还有一个头节点，说一初始化时就是创建一个哨兵位
首先是申请链表：
接着是哨兵位的创建（放入一个无效数据就行）
测试：
2.双向链表的相关操作
2.1双向链表的尾插、打印和头插
2.11双向链表的尾插
这里的传参是什么呢？
58c66ffd3020b137a.png)
47be39ed4525a16999a787187d86.png)
对于这个问题其实很简单，对于完成操作来说这两种都可以，但是我们使用第一种是没办法改变哨兵位的，但是我们第二种有机会改变哨兵位的，如果让我们代码更安全一点，就使用第一个
这里的d3就是phead指向的prev指针
我们优先修改newnode指向，然后在修改phead的指向
我们再来判断NULL链表的情况：
当插入NULL指针时，并不会对NULL指针进行解引用，这个代码就没问题
这两行代码不能直接进行交换，因为会找不到d3这个数据，从而改变不了
2.12双向链表的打印
这里要用到哨兵为来确定是否循环一遍
测试：
2.13双向链表的头插
顺序为3 1 4 2
测试：
2.2双向链表的尾删和头删
2.21双向链表的尾删
首先要判断链表必须有效并且链表不能为NULL
我们只对2 3进行改变就行了
测试：
2.22双向链表的头删
测试：
2.3双向链表查找和任意位置插入、删除
2.31双向链表查找
进行遍历，然后进行判断
测试：
2.32双向链表任意位置之后插入
还是对newnode进行改变然后在该pos指针
测试：
2.33双向链表任意位置删除
删除位置理论上不能为phead，但是没有phead参数，无法增加校验
也是先将pos后的指针先修改好，然后在修改pos前的指针
测试：
这里虽然对实参进行改变了，但这里为什么不传二级指针呢
这里是为了保持接口一致性，方便我们的记忆，我们可以通过外部值NULL来解决
这里我们之前的初始化代码也可以进行优化
一个以参数的方式初始化，一个以返回值的方法初始化
2.4双向链表的销毁
销毁后要向下走，所以我们要将指针存一下
这里也是一级指针，所以无法改变头节点
手动置为NULL即可
本文代码：
List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
LTNode* LTBuyNode(LTDataType x);//申请空间
//void LTInit(LTNode** pphead);//初始化
LTNode* LTInit();
void LTPrint(LTNode* phead);
//插入数据
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
LTNode* LTBuyNode(LTDataType x)
{
//申请节点
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc");
exit(1);
}
node->data = x;
node->next = node->prev = node;
return node;
}
//void LTInit(LTNode** pphead)
//{
//*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
void LTPrint(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead phead->prev newnode
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
void LTPopBack(LTNode* phead)
{
//链表必须有效并且链表不能为NULL
assert(phead && phead->next != phead);
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
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 LTErase(LTNode* pos)
{
assert(pos);
//pos理论上不能为phead，但是没有phead参数，无法增加校验
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest01()
{
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
//LTPushBack(plist, 1);
//LTPrint(plist);
//LTPushBack(plist, 2);
//LTPrint(plist);
//LTPushBack(plist, 3);
//LTPrint(plist);
//LTPushBack(plist, 4);
//LTPrint(plist);
LTPushFront(plist, 4);
LTPrint(plist);
LTPushFront(plist, 3);
LTPrint(plist);
LTPushFront(plist, 2);
LTPrint(plist);
LTPushFront(plist, 1);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
void ListTest02()
{
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
void ListTest03()
{
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTNode* find1 = LTFind(plist, 3);
if (find1 == NULL)
{
printf("找不到\n");
}
else
{
printf("找到了\n");
}
LTNode* find2 = LTFind(plist, 5);
if (find2 == NULL)
{
printf("找不到\n");
}
else
{
printf("找到了\n");
}
LTDestroy(plist);
plist = NULL;
}
void ListTest04()
{
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTNode* find1 = LTFind(plist, 2);
LTInsert(find1, 66);
LTPrint(plist);
LTNode* find2 = LTFind(plist, 4);
LTInsert(find2, 99);
LTPrint(plist);
LTNode* find3 = LTFind(plist, 66);
LTErase(find3);
find3 = NULL;
LTPrint(plist);
LTNode* find4 = LTFind(plist, 99);
LTErase(find4);
find4 = NULL;
LTPrint(plist);
LTDestroy(plist);
plist = NULL;
}
int main()
{
//ListTest01();
//ListTest02();
//ListTest03();
ListTest04();
return 0;
}
以上就是本文的全部内容了，希望对大家有所帮助，大家加油！！！
原文地址：https://blog.csdn.net/2302_82004664/article/details/137740754
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！