【C语言】数据结构——带头双链表实例探究

这篇具有很好参考价值的文章主要介绍了【C语言】数据结构——带头双链表实例探究。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

导读:

我们在前面学习了单链表和顺序表。
今天我们来学习双向循环链表。
在经过前面的一系列学习,我们已经掌握很多知识,相信今天的内容也是很容易理解的。
关注博主或是订阅专栏,掌握第一消息。

1. 双链表结构特征

今天我们要学的是双向带头循环列表。
双向循环链表是一个链表的数据结构,每个节点包含两个指针,分别指向前一个节点和后一个节点。与普通的链表不同的是,双向循环链表的尾节点的后继节点指向头节点,头节点的前驱节点指向尾节点,形成一个闭环。
【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言
双向循环链表的特点是可以从任意一个节点开始遍历整个链表。

由于每个节点都可以直接访问前一个节点和后一个节点,所以在双向循环链表中插入和删除节点的操作更加方便和高效。
在插入和删除节点时,只需要修改相邻节点的指针即可,不需要像普通链表那样需要遍历找到前一个节点。

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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言
最开始的时候链表只有一个哨兵位,它的前后指针都是指向自己,所以找尾节点找到的就是哨兵位。
【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言
第一个数据的插入:
【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

第二个数据的插入:

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

2.6 双向链表尾删

要实现带头双向循环链表的尾删操作,可以按照以下步骤:

  1. 首先判断链表是否为空,如果为空,则直接返回。

  2. 如果链表不为空,找到链表中的最后一个节点的前一个节点,即尾节点的前一个节点。

  3. 将尾节点的前一个节点的next指针指向头节点,即将尾节点从链表中移除。

  4. 释放尾节点的内存空间。

  5. 更新链表的尾指针,即将尾指针指向尾节点的前一个节点。

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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言
【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

2.8 双向链表头删

带头双向链表的头删操作可以通过以下步骤实现:

  1. 如果链表为空,直接返回。
  2. 将头节点的下一个节点指针保存在一个临时变量中。
  3. 将头节点的下一个节点的前驱节点指针指向空。
  4. 将临时变量指向的节点的前驱节点指针指向空。
  5. 将头节点指向临时变量指向的节点。
  6. 释放临时变量指向的节点的内存空间。
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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言
【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

2.9 双向链表查找

在带头双向链表中查找一个特定的元素可以按照以下步骤进行:

  1. 如果链表为空,则返回空指针或者空值,表示找不到目标元素。
  2. 通过指针访问链表的第一个节点,即头节点的下一个节点。
  3. 从第一个节点开始,依次遍历链表的每一个节点,直到找到目标元素或者遍历到链表的末尾。
    4 如果找到目标元素,返回该节点的指针或者该节点的值,表示找到了目标元素。
  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 双向链表任意位置插入

我们利用查找函数,插入到找到的数前面。

  1. 判断链表里是否有这位数。
  2. 创建一个新节点。
  3. 改变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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

2.11 双向链表任意位置删除

仍然是利用查找函数,删除find函数返回的节点。

  1. 判断是否存在这个数。
  2. 把该节点的前一个节点和后一个节点相关联。
  3. 释放该节点。
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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言

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);
}

测试:

//任意位置插入删除(头尾增删调用)
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;
}

【C语言】数据结构——带头双链表实例探究,数据结构学习,c语言,数据结构,开发语言文章来源地址https://www.toymoban.com/news/detail-772944.html

到了这里,关于【C语言】数据结构——带头双链表实例探究的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(202)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(58)
  • 【数据结构】 循环双链表的基本操作 (C语言版)

    目录 一、循环双链表 1、循环双链表的定义: 2、循环双链表的优缺点: 二、循环双链表的基本操作算法(C语言)    1、宏定义  2、创建结构体 3、循环双链表的初始化  4、循环双链表按位查找 5、循环双链表插入 6、循环双链表查找 7、循环双链表删除 8、求循环双链表长

    2024年01月22日
    浏览(53)
  • 【数据结构】C语言实现单链表(带头结点)

    Single linked list with leading nodes 关于不带头结点的单链表:不带头结点的单链表 结点定义: 接口定义: 初始化需要申请头结点,让头指针指向空的头结点。 将申请结点的代码进行封装: 需要越过头结点 找到尾结点,然后插入到尾结点的后面。 对比不带头结点的单链表的尾插

    2024年02月02日
    浏览(183)
  • 【数据结构】C语言实现双向链表(带头结点、循环)

    结点定义: 接口定义: 我们将申请结点的代码封装成函数,方便后续使用 由于是带头结点的双向链表,因此在使用链表前,我们需要对链表进行初始化。 遍历链表,值得说的是,带头结点的双向链表的循环结束条件是 cur != phead 尾插时,需要先找到尾结点,然后将新结点插

    2024年02月03日
    浏览(68)
  • 【数据结构 -- C语言】 双向带头循环链表的实现

    目录 1、双向带头循环链表的介绍 2、双向带头循环链表的接口 3、接口实现 3.1 开辟结点 3.2 创建返回链表的头结点 3.3 判断链表是否为空 3.4 打印 3.5 双向链表查找 3.6 双向链表在pos的前面进行插入 3.6.1 头插 3.6.2 尾插 3.6.3 更新头插、尾插写法 3.7 双向链表删除pos位置的节点

    2024年02月09日
    浏览(62)
  • 追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年01月17日
    浏览(59)
  • 数据结构入门(C语言版)线性表带头双向循环链表接口实现

    在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。 如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客: 线性表中链表介绍及无头单向非循环链

    2023年04月12日
    浏览(45)
  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(43)
  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(60)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包