💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫
导读:
我们在前面学习了单链表和顺序表。
今天我们来学习双向循环链表。
在经过前面的一系列学习,我们已经掌握很多知识,相信今天的内容也是很容易理解的。
关注博主或是订阅专栏,掌握第一消息。
1. 双链表结构特征
今天我们要学的是双向带头循环列表。
双向循环链表是一个链表的数据结构,每个节点包含两个指针,分别指向前一个节点和后一个节点。与普通的链表不同的是,双向循环链表的尾节点的后继节点指向头节点,头节点的前驱节点指向尾节点,形成一个闭环。
双向循环链表的特点是可以从任意一个节点开始遍历整个链表。
由于每个节点都可以直接访问前一个节点和后一个节点,所以在双向循环链表中插入和删除节点的操作更加方便和高效。
在插入和删除节点时,只需要修改相邻节点的指针即可,不需要像普通链表那样需要遍历找到前一个节点。
2. 实现双向循环链表
我们需要创建两个 C文件: study.c 和 SList.c,以及一个 头文件: SList.h。
头文件来声明函数,一个C文件来定义函数,另外一个C文件来用于主函数main()进行测试。
2.1 定义结构体
typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。
若struct SeqList {}这样来定义结构体的话。在申请SeqList 的变量时,需要这样写,struct SList n;
若用typedef,可以这样写,typedef struct SList{}SL; 。在申请变量时就可以这样写,SL n;
区别就在于使用时,是否可以省去struct这个关键字。
定义两个指针next和prev,分别指向该节点的下一个节点和前一个节点,data记录该节点存放的值。
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;
2.2 创造节点
因为链表的插入都需要新创建一个节点,为了方便后续的使用以及避免代码的重复出现,我们直接定义函数,后续直接调用即可。
LTNode* CreateLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
malloc开辟一块空间,存入想要插入的值,前后指针闲置为空,后面调用后再去改变,返回该节点的指针。
2.3 双向链表初始化
先把哨兵位创建出来,前后指针都先指向自己,该节点不存储任何实际的数据,只是作为链表的起始点。
LTNode* LTInit()
{
LTNode* phead = CreateLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
2.4 双向链表打印
方便我们后面测试代码是否出错。
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("哨兵位<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\n");
}
2.5 双向链表尾插
首先,需要找到链表的尾节点(即头节点的前驱节点)。
然后将新节点插入到尾节点的后面,即新节点的前驱指向尾节点,新节点的后继指向头节点(即原先的尾节点的后继节点),头节点的前驱指向新节点,头节点的后继指向新节点。
最后,将新节点作为尾节点。
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;//尾节点
LTNode* newnode = CreateLTNode(x);//新建一个节点
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
我们用尾插插入1,2,3,4来进行测试。
void TestLT1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
}
int main()
{
TestLT1();
return 0;
}
最开始的时候链表只有一个哨兵位,它的前后指针都是指向自己,所以找尾节点找到的就是哨兵位。
第一个数据的插入:
第二个数据的插入:
2.6 双向链表尾删
要实现带头双向循环链表的尾删操作,可以按照以下步骤:
首先判断链表是否为空,如果为空,则直接返回。
如果链表不为空,找到链表中的最后一个节点的前一个节点,即尾节点的前一个节点。
将尾节点的前一个节点的next指针指向头节点,即将尾节点从链表中移除。
释放尾节点的内存空间。
更新链表的尾指针,即将尾指针指向尾节点的前一个节点。
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next);
LTNode* tail = phead->prev;//最后一个节点
LTNode* tailprev = tail->prev;//倒数第二个节点
phead->prev = tailprev;
tailprev->next = phead;
free(tail);
tail = NULL;
}
测试:
void TestLT1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
}
int main()
{
TestLT1();
return 0;
}
2.7 双向链表头插
头插法是指将新的节点插入链表的头部,而不是尾部。
在带头双向链表中,首先创建一个新的节点,并将其next指针指向原来的头节点,然后将原来的头节点的prev指针指向新的节点即可。
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = CreateLTNode(x);//增加新节点
LTNode* next = phead->next;//记录原先的第一个节点
phead->next = newnode;
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
}
测试:
void TestLT2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushFront(plist, 99);
LTPushFront(plist, 88);
LTPushFront(plist, 77);
LTPushFront(plist, 66);
LTPushFront(plist, 55);
LTPrint(plist);
}
int main()
{
TestLT2();
return 0;
}
2.8 双向链表头删
带头双向链表的头删操作可以通过以下步骤实现:
- 如果链表为空,直接返回。
- 将头节点的下一个节点指针保存在一个临时变量中。
- 将头节点的下一个节点的前驱节点指针指向空。
- 将临时变量指向的节点的前驱节点指针指向空。
- 将头节点指向临时变量指向的节点。
- 释放临时变量指向的节点的内存空间。
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next);
LTNode* del = phead->next;//第一个节点
LTNode* next = del->next;//第二个节点
phead->next = next;
next->prev = phead;
free(del);
del = NULL;
}
测试:
void TestLT2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushFront(plist, 99);
LTPushFront(plist, 88);
LTPushFront(plist, 77);
LTPushFront(plist, 66);
LTPushFront(plist, 55);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
}
int main()
{
TestLT2();
return 0;
}
2.9 双向链表查找
在带头双向链表中查找一个特定的元素可以按照以下步骤进行:
- 如果链表为空,则返回空指针或者空值,表示找不到目标元素。
- 通过指针访问链表的第一个节点,即头节点的下一个节点。
- 从第一个节点开始,依次遍历链表的每一个节点,直到找到目标元素或者遍历到链表的末尾。
4 如果找到目标元素,返回该节点的指针或者该节点的值,表示找到了目标元素。- 如果遍历到链表的末尾都没有找到目标元素,则返回空指针或者空值,表示找不到目标元素。
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.10 双向链表任意位置插入
我们利用查找函数,插入到找到的数前面。
- 判断链表里是否有这位数。
- 创建一个新节点。
- 改变pos位置前一个节点、pos节点和新节点的前后驱指针。
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = CreateLTNode(x);//增加新节点
LTNode* cur = pos->prev;//pos前一个节点
cur->next = newnode;
newnode->prev = cur;
pos->prev = newnode;
newnode->next = pos;
}
测试:
//任意位置插入测试
void TestLT5()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
if (LTFind(plist, 2))
{
LTNode* pos = LTFind(plist, 2);
LTInsert(pos, 999);
LTPrint(plist);
}
else
{
printf("fail\n");
}
}
int main()
{
TestLT5();
return 0;
}
2.11 双向链表任意位置删除
仍然是利用查找函数,删除find函数返回的节点。
- 判断是否存在这个数。
- 把该节点的前一个节点和后一个节点相关联。
- 释放该节点。
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* before = pos->prev;//pos前一个节点
LTNode* next = pos->next;//pos后一个节点
before->next = next;
next->prev = before;
free(pos);
pos = NULL;
}
测试:
//任意位置删除测试
void TestLT6()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushFront(plist, 99);
LTPushFront(plist, 88);
if (LTFind(plist, 2))
{
LTNode* pos = LTFind(plist, 2);
LTErase(pos);
}
LTPrint(plist);
}
int main()
{
TestLT6();
return 0;
}
2.12 双链表销毁
动态内存开辟空间,使用完之后需要进行销毁。
void LTDestory(LTNode* phead)
{
assert(phead);
assert(phead->next);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
2.13 利用任插、任删完成头尾插入和头尾删除
因为我们是带头双向链表,所以我们利用哨兵位就可以轻松找到链表的头尾结点。
所有我们只需要把哨兵位的位置做为参数,就可以轻易完成。
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next);
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead->next, x);
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next);
LTErase(phead->next);
}
测试:文章来源:https://www.toymoban.com/news/detail-772944.html
//任意位置插入删除(头尾增删调用)
void TestLT4()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPrint(plist);
LTPushFront(plist, 99);
LTPushFront(plist, 88);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTDestory(plist);
}
int main()
{
TestLT4();
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-772944.html
到了这里,关于【C语言】数据结构——带头双链表实例探究的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!