数据结构——带头节点的双向循环列表

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

带头节点的双向循环链表是一种特殊的双向链表,它与普通的双向链表相比,最大的区别是链表头结点的 next 指针不再指向第一个实际节点,而是指向链表中的第一个节点。同时,链表尾结点的 prev 指针也不再指向 NULL,而是指向链表中的最后一个节点。

另外,带头节点的双向循环链表相对于普通的双向链表来说,在插入和删除节点时,需要特别注意头结点和尾结点的指针处理,以保证链表的循环性。
数据结构——带头节点的双向循环列表

typedef int LTDatatype;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDatatype data;
}LTNode;

这个代码片段定义了一个名为 ListNode 的结构体,包含三个成员:

next:指向链表中下一个节点的指针。
prev:指向链表中上一个节点的指针。
data:保存节点数据的 LTDatatype 类型变量。
typedef int LTDatatype; 语句创建了一个名为 LTDatatype 的 int 数据类型的别名。这使得程序员可以通过更改 typedef 语句而不是修改整个代码,轻松修改链表中使用的数据类型。

总体来说,这段代码简单地定义了一个用于 C 语言双向链表节点的结构体。

//双向列表的初始化
LTNode* LTInit()
{
	LTNode* plist= BuyListNode(-1);
	plist->next = plist;
	plist->prev = plist;
	return plist;
}

这是一个 C 语言函数,用于初始化一个双向链表。函数的返回值是指向链表头结点的指针,函数名为 LTInit,意味着“初始化链表”。

// 双向链表销毁
void ListDestory(LTNode* plist) {
	LTNode* p = plist; // 从头节点开始遍历
	while (p != NULL) {
		LTNode* tmp = p; // 保存当前节点指针
		p = p->next; // 移动到下一个节点
		free(tmp); // 释放当前节点的内存
	}
	plist = NULL; // 将头结点指针置为 NULL
}

这是一个 C 语言函数,用于销毁一个带头节点的双向循环链表。函数的参数是指向链表头结点的指针 plist,函数没有返回值。函数名为 ListDestory,意味着“销毁链表”。

注意,在带头节点的双向循环链表中,头结点的 next 指针不再指向第一个实际节点,而是指向链表中的第一个节点。因此,在销毁链表时,需要从头结点的 next 指针指向的节点开始遍历,直到回到头结点为止。同时,在释放头结点的内存之前,需要先释放链表中的所有节点的内存。

// 双向链表打印
void ListPrint(LTNode* plist)
{
	assert(plist);
	printf("<=head=>");
	LTNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

这是一个 C 语言函数,用于打印一个带头节点的双向循环链表中所有节点的数据。函数的参数是指向链表头结点的指针 plist,函数没有返回值。函数名为 ListPrint,意味着“打印链表”。

注意,在带头节点的双向循环链表中,头结点的 next 指针不再指向第一个实际节点,而是指向链表中的第一个节点。因此,在打印链表时,需要从头结点的 next 指针指向的节点开始遍历,直到回到头结点为止。同时,在输出节点数据时,需要注意区分头结点和实际节点,以免混淆。

bool LTEmpty(LTNode* plist)
{
    assert(plist != NULL); // 确保链表头结点不为空
    return plist->next == plist; // 如果头结点的 next 指针指向自身,说明链表为空,返回 true,否则返回 false
}

这是一个 C 语言函数,用于判断一个带头节点的双向循环链表是否为空。函数的参数是指向链表头结点的指针 plist,函数返回一个布尔值。函数名为 LTEmpty,意味着“链表是否为空”。

// 双向链表尾删
void ListPopBack(LTNode* plist)
{
	assert(plist);
	assert(!LTEmpty(plist));
	LTNode* tail = plist->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = plist;
	plist->prev = tailPrev;
	free(tail);
	tail = NULL;
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中删除最后一个节点。函数的参数是指向链表头结点的指针 plist,函数没有返回值。函数名为 ListPopBack,意味着“尾删链表”。

函数的实现通常涉及以下步骤:
检查链表头结点和链表是否为空,如果为空,抛出异常。
找到链表中的最后一个节点,即尾结点。
找到尾结点的前驱节点,并将其 next 指针指向头结点,将头结点的 prev 指针指向尾结点的前驱节点。
释放尾结点的内存,并将其指针置为 NULL。

// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x)
{
    assert(plist != NULL); // 确保链表头结点不为空
    LTNode* newnode = BuyListNode(x); // 创建新节点
    newnode->next = plist->next; // 将新节点的 next 指针指向头结点的下一个节点
    plist->next->prev = newnode; // 将头结点的下一个节点的 prev 指针指向新节点
    plist->next = newnode; // 将头结点的 next 指针指向新节点
    newnode->prev = plist; // 将新节点的 prev 指针指向头结点
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中在头部插入一个新节点。函数的参数是指向链表头结点的指针 plist 和要插入的节点数据 x,函数没有返回值。函数名为 ListPushFront,意味着“头插链表”。

// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x)
{
	assert(plist);
	/*LTNode* newnode = BuyListNode(x);
	LTNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
	plist->prev = newnode;*/
	ListInsert(plist, x);
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中在尾部插入一个新节点。函数的参数是指向链表头结点的指针 plist 和要插入的节点数据 x,函数没有返回值。函数名为 ListPushBack,意味着“尾插链表”。

函数的实现通常涉及以下步骤:

检查链表头结点是否为空,如果为空,抛出异常。
创建一个新节点,并将其 next 指针指向头结点,将头结点的前驱节点的 next 指针指向新节点。
将新节点的 prev 指针指向头结点的前驱节点,将头结点的 prev 指针指向新节点。

// 双向链表头删
void ListPopFront(LTNode* plist) {
	if (plist == NULL) {
		return; // 如果链表为空,直接返回
	}

	LTNode* p = plist; // 保存头节点指针
	plist = plist->next; // 将下一个节点设置为新的头节点
	if (plist != NULL) {
		plist->prev = NULL; // 如果新的头节点不为空,则将其前驱节点的指针设置为 NULL
	}
	free(p); // 释放原始头节点的内存
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中删除第一个节点。函数的参数是指向链表头结点的指针 plist,函数没有返回值。函数名为 ListPopFront,意味着“头删链表”。

函数的实现通常涉及以下步骤:

检查链表头结点是否为空,如果为空,直接返回。
将头结点的下一个节点设置为新的头节点,并保存原始头节点的指针。
如果新的头节点不为空,则将其前驱节点的指针设置为 NULL。
释放原始头节点的内存,并将其指针置为 NULL。

// 双向链表查找
LTNode* ListFind(LTNode* plist, LTDataType x) 
{
	LTNode* p = plist->next; // 从第一个节点开始遍历
	while (p != NULL && p->data != x) { // 遍历链表,直到找到指定数据或到达链表结尾
		p = p->next; // 移动到下一个节点
	}
	return p; // 返回找到的节点的指针,如果未找到则返回 NULL
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中查找指定数据的节点。函数的参数是指向链表头结点的指针 plist 和要查找的数据 x,函数返回找到的节点的指针,如果未找到则返回 NULL。函数名为 ListFind,意味着“查找链表”。

函数的实现通常涉及以下步骤:

从第一个节点开始遍历链表。
在遍历链表时,如果找到了数据值等于 x 的节点,则返回该节点的指针。
如果遍历到链表的结尾都没有找到符合条件的节点,则返回 NULL。

// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中在指定节点的前面插入一个新节点。函数的参数是指向指定节点的指针 pos 和要插入的节点数据 x,函数没有返回值。函数名为 ListInsert,意味着“插入链表”。

函数的实现通常涉及以下步骤:

检查指定节点是否为空,如果为空,抛出异常。
创建一个新节点,并将其 next 指针指向指定节点,将指定节点的前驱节点的 next 指针指向新节点。
将新节点的 prev 指针指向指定节点的前驱节点,将指定节点的 prev 指针指向新节点。

// 双向链表删除pos位置的结点
void ListErase(LTNode* pos) 
{
	if (pos == NULL || pos->prev == NULL) {
		return; // 如果待删除节点为 NULL 或者是头结点,则直接返回
	}

	LTNode* prev_node = pos->prev; // 保存待删除节点的前驱节点
	prev_node->next = pos->next; // 将前驱节点的 next 指针指向待删除节点的后继节点
	if (pos->next != NULL) {
		pos->next->prev = prev_node; // 如果待删除节点有后继节点,则将后继节点的 prev 指针指向前驱节点
	}
	free(pos); // 释放待删除节点的内存
}

这是一个 C 语言函数,用于在带头节点的双向循环链表中删除指定位置的节点。函数的参数是指向指定节点的指针 pos,函数没有返回值。函数名为 ListErase,意味着“删除链表”。

函数的实现通常涉及以下步骤:

检查待删除节点是否为空,如果为空或者是头结点,则直接返回。
保存待删除节点的前驱节点指针。
将前驱节点的 next 指针指向待删除节点的后继节点。
如果待删除节点有后继节点,则将后继节点的 prev 指针指向前驱节点。
释放待删除节点的内存。

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

这是一个 C 语言函数,用于创建一个新的双向链表节点并返回其指针。函数的参数是节点中存储的数据 x,函数返回新节点的指针。函数名为 BuyListNode,意味着“购买链表节点”,通常也可以称为 CreateListNode 或者 NewListNode。

函数的实现通常涉及以下步骤:

分配一个新的节点结构体的内存空间。
将节点的 data 成员赋值为参数 x。
将节点的 next 和 prev 成员指针初始化为 NULL。
返回新节点的指针。文章来源地址https://www.toymoban.com/news/detail-501410.html

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;


//双向列表的初始化
LTNode* LTInit();
// 双向链表销毁
void ListDestory(LTNode* plist);
// 双向链表打印
void ListPrint(LTNode* plist);
// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(LTNode* plist);
// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(LTNode* plist);
// 双向链表查找
LTNode* ListFind(LTNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(LTNode* pos);

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}

//双向列表的初始化
LTNode* LTInit()
{
	LTNode* plist= BuyListNode(-1);
	plist->next = plist;
	plist->prev = plist;
	return plist;
}
// 双向链表销毁
void ListDestory(LTNode* plist) {
	LTNode* p = plist; // 从头节点开始遍历
	while (p != NULL) {
		LTNode* tmp = p; // 保存当前节点指针
		p = p->next; // 移动到下一个节点
		free(tmp); // 释放当前节点的内存
	}
	plist = NULL; // 将头结点指针置为 NULL
}

// 双向链表打印
void ListPrint(LTNode* plist)
{
	assert(plist);
	printf("<=head=>");
	LTNode* cur = plist->next;
	while (cur != plist)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


//判断链表是否为空
bool LTEmpty(LTNode* plist)
{
	assert(plist);
	return plist->next == plist;
}

// 双向链表尾删
void ListPopBack(LTNode* plist)
{
	assert(plist);
	assert(!LTEmpty(plist));
	LTNode* tail = plist->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = plist;
	plist->prev = tailPrev;
	free(tail);
	tail = NULL;
}

// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x)
{
	assert(plist);
	/*LTNode* newnode = BuyListNode(x);
	newnode->next = plist->next;
	plist->next->prev = newnode;
	plist->next = newnode;
	newnode->prev = plist;*/
	ListInsert(plist->next, x);
}

// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x)
{
	assert(plist);
	/*LTNode* newnode = BuyListNode(x);
	LTNode* tail = plist->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = plist;
	plist->prev = newnode;*/
	ListInsert(plist, x);
}
// 双向链表头删
void ListPopFront(LTNode* plist) {
	if (plist == NULL) {
		return; // 如果链表为空,直接返回
	}

	LTNode* p = plist; // 保存头节点指针
	plist = plist->next; // 将下一个节点设置为新的头节点
	if (plist != NULL) {
		plist->prev = NULL; // 如果新的头节点不为空,则将其前驱节点的指针设置为 NULL
	}
	free(p); // 释放原始头节点的内存
}
// 双向链表查找
LTNode* ListFind(LTNode* plist, LTDataType x) 
{
	LTNode* p = plist->next; // 从第一个节点开始遍历
	while (p != NULL && p->data != x) { // 遍历链表,直到找到指定数据或到达链表结尾
		p = p->next; // 移动到下一个节点
	}
	return p; // 返回找到的节点的指针,如果未找到则返回 NULL
}
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
// 双向链表删除pos位置的结点
void ListErase(LTNode* pos) 
{
	if (pos == NULL || pos->prev == NULL) {
		return; // 如果待删除节点为 NULL 或者是头结点,则直接返回
	}

	LTNode* prev_node = pos->prev; // 保存待删除节点的前驱节点
	prev_node->next = pos->next; // 将前驱节点的 next 指针指向待删除节点的后继节点
	if (pos->next != NULL) {
		pos->next->prev = prev_node; // 如果待删除节点有后继节点,则将后继节点的 prev 指针指向前驱节点
	}
	free(pos); // 释放待删除节点的内存
}

到了这里,关于数据结构——带头节点的双向循环列表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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)
  • 【数据结构】实现带头双向循环链表

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

    2024年02月10日
    浏览(45)
  • 玩转带头双向链表——【数据结构】

    W...Y的主页 今天我们接着来说数据结构——带头双向链表 目录 带头双向链表的实现 结构体的创建 初始化兵创建哨兵节点 释放链表所以内容  打印链表函数 尾插 尾删 头插 ​编辑 头删 计数函数实现 查找数据相应位置函数 在pos位置之前插入  在pos位置删除  顺序表与链表的

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

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

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

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

    2024年04月14日
    浏览(63)
  • 【数据结构】线性表——带头双向循环链表

    带头双向循环链表的优点 1.支持任意位置时间复杂度为O(1)的插入和删除。 2.按照需求申请释放空间,无需担心空间不够用,无需担心浪费。 3.带头可以省去链表为空时的判断,可以使代码更加简约 带头双向循环链表的缺点 1.不可以进行下标随机访问。 2.缓存利用率低 带头双

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

    目录 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.结构实现 2.3.1接口实现 2.3.2函数实现 3.总结 ,又和大家见面了,今天要给大家分享的是双链表的知识,跟着我的脚步,包学包会哦~ 规矩不乱,先赞后看! ps:(孙权劝学) 前期学习了单链表,我们尝到了它的甜头,但是容易越界访问这一个问题也是时有出

    2024年03月22日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包