【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!)

这篇具有很好参考价值的文章主要介绍了【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表


【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表

🐸一、前言

在前面我们学习实现了单链表(无头单向不循环链表),这里我们引入带头双向循环链表
很明显这两种链表的结构截然不同,但都是作为链表最常使用链表结构
前者因其结构上的缺点而作为面试考题的常驻嘉宾,而且复杂麻烦
后者则是以结构最优著称,实现起来也是非常的简单(少了单链表头节点,尾节点,前一节点等问题的困扰),可以说是最的链表结构🤭

🐸二、链表的分类

🍄1. 单向或者双向链表

【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表

  • 单向:节点结构中只存在下一节点的地址,所以难以从后一节点找到前一节点
  • 双向:节点结构中存在前一节点和后一节点的地址,寻找前一节点和后一节点很便利

🍄2. 带头或者不带头链表

【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表

  • 带头:在本来的头节点之前还有一个哨兵卫节点作为头节点,它的址域指针指向头节点,值域不做使用
  • 不带头:没有哨兵卫头节点,在尾删尾插等问题中要考虑头节点的情况(局限)

🍄3. 循环或者非循环

【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表

  • 循环:头节点会与尾节点相连
  • 非循环:头节点不与尾节点相连

🍄4. 最常用链表

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
🔴无头单向非循环链表
【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表
🔴带头双向循环链表
【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表

  • 🚩1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 🚩2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

🐸三、带头双向循环链表详解

【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表

🍎创建带头双向循环链表

🥰这里先创建三个文件:
1️⃣:List.h文件用于函数的声明
2️⃣:List.c文件用于函数的定义
3️⃣:Test.c文件用于测试函数
建立三个文件的目的: 将链表作为一个项目来进行编写,方便我们的学习与观察。

⭕接口1:定义结构体(LTNode)

🥰请看代码与注释👇

//自定义类型
typedef int ListNodeDataType;

//创建双向链表
typedef struct ListNode
{
	struct ListNode* prev; //前址域
	struct ListNode* next; //后址域
	ListNodeDataType data; //值域
}LTNode;

⭕接口2:初始化(创建哨兵卫)(LTInit)

🥰请看代码与注释👇

//初始化(创建哨兵卫)
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1); //哨兵卫不存储有效值
	phead->prev = phead; //初始化哨兵卫头节点址域
	phead->next = phead;

	return phead;
}

⭕接口3:打印(LTPrint)

🥰请看代码与注释👇

//打印
void LTPrint(LTNode* phead)
{
	//断言传入指针不为NULL
	assert(phead);

	printf("guard<==>");

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data); //打印数据
		cur = cur->next; //找到下一个节点
	}
	printf("\n");
}

⭕接口4:创建新结点(BuyLTNode)

🥰请看代码与注释👇

//创建新节点
LTNode* BuyLTNode(ListNodeDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail"); //失败打印错误信息并结束进程
		return;
	}
	//初始化节点
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

⭕接口5:释放(LTDestroy)

🥰请看代码与注释👇

//释放
void LTDestroy(LTNode* phead)
{
	//断言传入指针不为NULL
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next; //记录下一个节点地址
		free(cur); //释放当前节点
		cur = next; //找到下一个节点
	}

	free(phead);
}

⭕接口6:判空(LTEmpty)

🥰请看代码与注释👇

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead; //判断只剩哨兵卫头结点的情况
}

⭕接口7:头插(LTPushFront)

🥰请看代码与注释👇

//头插
void LTPushFront(LTNode* phead, ListNodeDataType x)
{
	assert(phead);

	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next; //记录哨兵卫头结点的下一节点
	
	//构建各节点之间的关系
	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;
}

⭕接口8:尾插(LTPushBack)

🥰请看代码与注释👇

//尾插
void LTPushBack(LTNode* phead, ListNodeDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev; //找到尾节点
	LTNode* newnode = BuyLTNode(x);
	
	//构建尾节点与新节点,新节点与哨兵卫头结点的关系
	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}

⭕接口9:头删(LTPopFront)

🥰请看代码与注释👇

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* first = phead->next; //记录哨兵卫头节点下一节点及其的下一节点
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
}

⭕接口10:尾删(LTPopBack)

🥰请看代码与注释👇

//尾删
void LTPopBack(LTNode* phead)
{
	//判空 以及 判断只剩哨兵卫头结点的情况
	assert(!LTEmpty(phead));
	
	//记录尾节点及其前一节点
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	
	//构建尾节点前一节点与哨兵卫头结点的关系
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail); //释放尾节点
}

⭕接口11:查找(LTFind)

🥰请看代码与注释👇

LTNode* LTFind(LTNode* phead, ListNodeDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;;
	while (cur != phead)
	{
		if (cur->data == x) //比较数据
		{
			return cur;
		}
		
		cur = cur->next; //找到下一个节点
	}

	return NULL; //没找到则返回NULL
}

⭕接口12:修改(LTModify)

🥰请看代码与注释👇

//修改
void LTModify(LTNode* phead, LTNode* pos, ListNodeDataType x)
{
	assert(phead);
	assert(pos);

	pos->data = x;
}

⭕接口13:在pos之前插入(LTInsert)

🥰请看代码与注释👇

//在pos之前插入
void LTInsert(LTNode* pos, ListNodeDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;
	
	newnode->next = pos;
	pos->prev = newnode;
}

⭕接口14:删除pos位置的值(LTErase)

🥰请看代码与注释👇

//删除pos位置的值
void LTErase(LTNode* pos)
{
	assert(pos);
	
	//记录pos的前一节点和后一节点
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos); //释放节点
}

🐸四、完整代码

🥝List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//自定义类型
typedef int ListNodeDataType;

//创建双向链表
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	ListNodeDataType data;
}LTNode;

//初始化(创建哨兵卫)
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//释放
void LTDestroy(LTNode* phead);
//判空
bool LTEmpty(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, ListNodeDataType x);
//尾插
void LTPushBack(LTNode* phead, ListNodeDataType x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, ListNodeDataType x);
//修改
void LTModify(LTNode* phead, LTNode* pos, ListNodeDataType x);
//在pos之前插入
void LTInsert(LTNode* pos, ListNodeDataType x);
//删除pos位置的值
void LTErase(LTNode* pos);

🥝List.c

#include "List.h"

//创建新节点
LTNode* BuyLTNode(ListNodeDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

//初始化(创建哨兵卫)
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1); //哨兵卫不存储有效值
	phead->prev = phead;
	phead->next = phead;

	return phead;
}

//打印
void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//释放
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

//头插
void LTPushFront(LTNode* phead, ListNodeDataType x)
{
	assert(phead);

	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;
}

头插
//void LTPushFront(LTNode* phead, ListNodeDataType x)
//{
//	assert(phead);
//
//	LTInsert(phead->next, x);
//}

//尾插
void LTPushBack(LTNode* phead, ListNodeDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	
	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}

尾插
//void LTPushBack(LTNode* phead, ListNodeDataType x)
//{
//	assert(phead);
//
//	LTInsert(phead, x);
//}

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* first = phead->next;
	LTNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
}

头删
//void LTPopFront(LTNode* phead)
//{
//	assert(!LTEmpty(phead));
//
//	LTEmpty(phead->next);
//}

//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}

尾删
//void LTPopBack(LTNode* phead)
//{
//	assert(!LTEmpty(phead));
//
//	LTEmpty(phead->prev);
//}

//查找
LTNode* LTFind(LTNode* phead, ListNodeDataType x)
{
	assert(phead);

	LTNode* cur = phead->next;;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		
		cur = cur->next;
	}

	return NULL;
}

//修改
void LTModify(LTNode* phead, LTNode* pos, ListNodeDataType x)
{
	assert(phead);
	assert(pos);

	pos->data = x;
}

//在pos之前插入
void LTInsert(LTNode* pos, ListNodeDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;
	
	newnode->next = pos;
	pos->prev = newnode;
}

//删除pos位置的值
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

🥝Test.c

#include "List.h"

//头插测试
void TestList01()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 4);
	LTPushFront(plist, 3);
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

//尾插测试
void TestList02()
{
	LTNode* plist = LTInit();

	LTPushBack(plist, 4);
	LTPushBack(plist, 3);
	LTPushBack(plist, 2);
	LTPushBack(plist, 1);

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

//头删测试
void TestList03()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 4);
	LTPushFront(plist, 3);
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	LTPopFront(plist);

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

//尾删测试
void TestList04()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 4);
	LTPushFront(plist, 3);
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	LTPopBack(plist);

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

//查找修改测试
void TestList05()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 4);
	LTPushFront(plist, 3);
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);
	
	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTModify(plist, pos, 8);
	}

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

//在pos之前插入
void TestList06()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 4);
	LTPushFront(plist, 3);
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);

	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 7);
	}

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

//删除pos位置的值
void TestList07()
{
	LTNode* plist = LTInit();

	LTPushFront(plist, 4);
	LTPushFront(plist, 3);
	LTPushFront(plist, 2);
	LTPushFront(plist, 1);

	LTNode* pos = LTFind(plist, 2);
	if (pos)
	{
		LTErase(pos);
	}

	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}



int main()
{
	//TestList01();
	//TestList02();
	//TestList03();
	//TestList04();
	//TestList05();
	//TestList06();
	//TestList07();

	return 0;
}

🥰这期内容比较容易一些而且比较有趣,希望烙铁们可以理解消化哦!

总结🥰
以上就是 【数据结构】带头双向循环链表—C语言版 的全部内容啦🥳🥳🥳🥳
本文章所在【数据结构与算法】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰

【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!),数据结构与算法,数据结构,链表,c语言,双向循环链表文章来源地址https://www.toymoban.com/news/detail-684561.html

到了这里,关于【数据结构】带头双向循环链表---C语言版(单链表我们分手吧,不要再找我玩了!!!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——带头双向循环链表

    在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针,目的在与存储前一个节点的地址,便于将整个链表连在一起。 动态申请内存结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断

    2024年02月09日
    浏览(42)
  • 【数据结构】带头双向循环链表

      🧑‍🎓 个人主页:简 料   🏆 所属专栏:C++   🏆 个人社区:越努力越幸运社区   🏆 简       介: 简料简料,简单有料~在校大学生一枚,专注C/C++/GO的干货分享,立志成为您的好帮手 ~ C/C++学习路线 (点击解锁) ❤️ C语言阶段(已结束) ❤️ 数据结构与算法(ing) ❤

    2024年01月16日
    浏览(78)
  • 数据结构---带头双向循环链表

    什么是双向带头循环链表? 上面简单的一个非空 带头循环双向链表逻辑图 如何定义一个双向链表? 根据图和代码可以看双向链表就是单链表的每个结点中,在设置一个指向前驱节点的指针 简单认识之后,对他进行初始化(申请一个头节点,让前驱和后驱指针都指向自己) 代码

    2024年02月07日
    浏览(69)
  • 带头双向循环链表--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏:🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的 点赞 👍和 关注 💖,支持一

    2024年02月01日
    浏览(54)
  • 数据结构-带头双向循环链表

    前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要针对这两种链表进行整理。 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用

    2023年04月09日
    浏览(49)
  • 『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表(单链表&&双向循环链表)附完整源码

      本章内容 1.什么是链表 2.链表常见几种形式 3.无头单向非循环链表的实现 3.1结点结构的定义 3.2函数接口的实现 3.2.1尾插 3.2.2尾删 4. 带头双向循环链表的实现 4.1结点结构的定义 4.2函数接口的实现 5.两种链表的差异 ①尾插与尾删的时间复杂度 ②头插与头删的时间复杂度 ③

    2024年02月16日
    浏览(78)
  • 数据结构之带头双向循环链表

    目录 链表的分类 带头双向循环链表的实现 带头双向循环链表的结构 带头双向循环链表的结构示意图 空链表结构示意图 单结点链表结构示意图  多结点链表结构示意图 链表创建结点 双向链表初始化 销毁双向链表 打印双向链表  双向链表尾插 尾插函数测试 双向链表头插

    2024年02月08日
    浏览(72)
  • 数据结构_带头双向循环链表

    相较于之前的顺序表和单向链表,双向链表的逻辑结构稍微复杂一些,但是在实现各种接口的时候是很简单的。因为不用找尾,写起来会舒服一点。(也可能是因为最近一直在写这个的原因) 在实现接口的时候,除了没有找尾,其他的操作和单向链表是差不多的,这里就不多

    2024年04月14日
    浏览(62)
  • 【数据结构】实现带头双向循环链表

    之前我们已经学习了单链表,有了单链表的基础,现在开始学习带头双向循环链表~ 结构最复杂 ,一般用在单独存储数据。 实际中使用的链表数据结构,都是带头双向循环链表 。另外这个结构虽然结构复杂,但是使用代码实现以后会发现 结构会带来很多优势 ,实现反而简单

    2024年02月10日
    浏览(44)
  • 【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包