1. Toy模板网首页
  2. > Toy博客

C语言--带哨兵位的双向循环链表的创建及使用详解

10月前 作者：小小分享君 分类：Toy博客 阅读(34) 违法举报

这篇具有很好参考价值的文章主要介绍了C语言--带哨兵位的双向循环链表的创建及使用详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 双向循环链表定义

1.1 定义

带哨兵位的双向循环链表是一种数据结构，它由多个节点组成，每个节点包含一个数据元素和两个指针，分别指向前一个节点和后一个节点，这样可以实现双向遍历。而且由于是循环链表，所以最后一个节点的后继节点是第一个节点，第一个节点的前驱节点是最后一个节点。与普通的双向循环链表不同的是，带哨兵位的链表在链表头部有一个哨兵节点，它不存储任何数据，仅用于简化链表操作。定义如下：

typedef int LTDataType;//定义存放数据的类型，便于不同类型数据的修改

typedef struct ListNode//定义链表结构
{
	struct ListNode* next;//指向下一个节点的地址
	struct ListNode* prev;//指向前一个数据的地址
	LTDataType data;//存放的数据
}LN;//重新命名

1.2 优点：

  1. 简化边界情况处理：哨兵节点的存在简化了对链表为空或者只有一个节点的情况的处理，使得代码更加简洁和易于理解。
  2. 方便实现循环遍历：由于是循环链表，可以方便地实现对链表的循环遍历，并且在实现迭代器等功能时也更加方便。
  3. 提高代码的可读性和可维护性：哨兵节点的引入使得链表操作的边界情况处理更加统一，减少了代码中的特殊情况处理，提高了代码的可读性和可维护性。

1.3 物理结构

物理结构如下图：
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

  1. 该链表的第一个节点为哨兵位节点，不存放任何数据。phead 的next指向的节点才是第一个数据存放的位子。尾节点的next指向头节点地址，头节点的prev指向尾节点地址
  2. 当链表仅剩下哨兵位时，perv 和 next 均指向自己，此时数据为空，链表中总会存在一个节点。在进行后面的操作的时候不需要判空，仅需要判别next 是否和prev 指向的位置相同

C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

2. 双向链表的创建

2.1 文件创建

为方便代码管理，将文件内容分为三个文件来共同组成单链表，如下：

List.h//存放函数的声明、链表定义
List.c//存放具体函数的定义，用于函数的实现
test.c//测试文件，用于测试函数的功能

链表的定义：

typedef int LTDataType;//定义存放数据的类型，便于不同类型数据的修改

typedef struct ListNode//定义链表结构
{
	struct ListNode* next;//指向下一个节点的地址
	struct ListNode* prev;//指向前一个数据的地址
	LTDataType data;//存放的数据
}LN;//重新命名

2.2 节点创建

链表结构由一个个链表节点前后链接而成，每个链表节点的开辟如下：

//新链表要完成数据数据插入，然后传回插入过后的地址
LN* BuyList(LTDataType x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));//开辟新的节点空间
	newnode->data = x;//放入数据
	//前后节点指向置空
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;//返回新开辟空间的地址
}

3. 链表操作

3.1 初始化

带哨兵位的双向链表的初始化需要创建一个哨兵位，同时将头指针和尾指针都指向哨兵位的地址，物理图如下：
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构
代码如下：

//初始化的本质是创建一个不放数据的节点，返回该节点地址
LN* ListInit()
{
	LN* phead = BuyList(0);//创建的哨兵位节点
	phead->next = phead;//头节点指向哨兵位自己
	phead->prev = phead;//尾节点指向哨兵位自己
	return phead;//返回创建的哨兵位的地址
}

3.2 显示

形参 phead 来接收整个链表的头地址 phead 的值，通过 phead 来访问显示链表中的数据。代码如下：

//显示操作仅对链表内部内容进行操作，仅需要哨兵位节点就可以访问所有数据
void ListPrint(LN* phead)
{
	//phead指向的是哨兵位的位置，第一个数据在哨兵位之后
	LN* cur = phead->next;//寻找第一个数据的位置
	
	//循环结构，当尾指针指向哨兵位时完成一个循环
	//当链表里面仅剩哨兵位时，cur指向的仍为phead,循环直接结束
	while (cur != phead)
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3 尾插

将最后一个节点tail 的next 指向新的节点newnode，新的节点newnode 的next 指向 phead，新的节点newnode 的prev 指向最后一个节点 tail 的地址，phead 的prev 指向新节点newnode 的地址.
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

//尾插需要链表的哨兵位节点与要插入的数据，不需要返回任何值
void ListPushBack(LN* phead, LTDataType x)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* tail = phead->prev;//找尾节点
	LN* newnode = BuyList(x);//新建节点
	//将新节点链接到尾节点tail之后，再与哨兵位链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

3.4 头插

将第一个数据节点first 的prev 指向新的节点newnode，新的节点newnode 的prev 指向 phead，新的节点newnode 的next 指向第一个节点 first的地址 ，phead 的next 指向新节点newnode 的地址.
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

//头插需要链表的哨兵位节点与要插入的数据，不需要返回任何值
void ListPushFront(LN* phead, LTDataType x)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* first = phead->next;//找到第一个数据的位置
	LN* newnode = BuyList(x);//新建节点
	//将新节点插入哨兵位之后，first之前
	first->prev = newnode;
	newnode->prev = phead;
	newnode->next = first;
	phead->next = newnode;
}

3.5 尾删

pead 的prev 指向倒数第二个数据pretail 的地址，prevtail 的next 指向phead 的地址,释放tail 的空间。
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

//尾删仅需要找到尾节点的位置，改变节点位置即可，不需要返回任何值
void ListPopBack(LN* phead)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错
	assert(phead->next != phead);//断言，当链表内容为空的时候报错

	LN* tail = phead->prev;//寻找尾节点
	LN* prevtail = tail->prev;//寻找尾节点之前的节点
	//改变链接顺序，将倒数第二个节点与哨兵位链接起来
	prevtail->next = phead;
	phead->prev = prevtail;
	//释放最后一个节点的空间
	free(tail);
	tail = NULL;
}

3.6 头删

pead 的next 指向第二个数据second 的地址，second 的prev 指向phead 的地址,释放first 的空间。
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

//头删仅需要找到第一个数据的的位置，改变节点位置即可，不需要返回任何值
void ListPopFront(LN* phead)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错
	assert(phead->next != phead);//断言，当链表内容为空的时候报错

	LN* first = phead->next;//寻找第一个数据存放节点
	LN* second = first->next;//寻找第二个数据存放节点
	//改变链接顺序，将第二个节点与哨兵位链接起来
	second->prev = phead;
	phead->next = second;
	//释放第一个节点的空间
	free(first);
	first = NULL;
}

3.7 查找

通过给定的数据，以遍历的方式寻找该数据，如果存在，则返回该数据的位置，不存在则返回空。

//查找需要被查找具体的数据，并且返回该数据的位置
LN* ListFind(LN* phead, LTDataType x)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* cur = phead->next;//第一个数据的位置
	while (cur != phead)//最坏情况为找一圈也不见要查找的数据
	{
		if (cur->data == x)//找到数据则返回地址
		{
			return cur;
		}
		cur=cur->next;
	}
	return NULL;//为找到数据则返回空
}

3.8 指定位置前插入

将指定数据节点pos 的prev 指向新的节点newnode，新的节点newnode 的prev 指向 prevpos，新的节点newnode 的next 指向pos的地址 ，prevpos 的next 指向新节点newnode 的地址.
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

//指定位置前插入需要指定的位置以及需要插入的数据
void ListInsert(LN* pos, LTDataType x)
{
	assert(pos);//断言，在链表哨兵位节点被误删时报错

	LN* prev = pos->prev;//找到指定位置前一个数据的位置
	LN* newnode = BuyList(x);//定义新的节点
	//将新的节点插入指定节点前面
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prev;
	prev->next = newnode;

}

3.9 指定位置删除

nextpos 的prev 指向prevpos 的地址，prevpos 的next 指向nextpos 的地址,释放pos 的空间。

C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

//指定位置删除仅需指定的位置即可
void ListErase(LN* pos)
{
	assert(pos);//断言，在链表哨兵位节点被误删时报错

	LN* PosNext = pos->next;//找到指定位置后一个数据的位置
	LN* PosPrev = pos->prev;//找到指定位置前一个数据的位置
	//将指定位置前的数据与指定位置后的数据链接起来
	PosNext->prev = PosPrev;
	PosPrev->next = PosNext;
	//释放指定位置的空间
	free(pos);
	pos = NULL;
}

3.10 链表销毁

通过哨兵位，将所有的链表空间一个一个的释放，最后将哨兵位的空间释放。

//链表销毁需要对整个链表进行操作
void ListDstroy(LN* phead)
{
	assert(phead);//断言，在链表哨兵位节点被误删时报错

	LN* cur = phead->next;//找到第一个数据的位置
	while (cur != phead)
	{
		LN* next = cur->next;//找到下一个数据的位置
		free(cur);//释放当前数据的空间
		cur = next;//cur重新变为存在数据的对一个位置
	}
	//释放哨兵位节点空间
	free(phead);
	phead = NULL;
}

4. 链表总内容

4.1 List.c 文件

#define  _CRT_SECURE_NO_WARNINGS

#include "List.h"

LN* BuyList(LTDataType x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

void ListPrint(LN* phead)
{
	LN* cur = phead->next;
	while (cur != phead)
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

LN* ListInit()
{
	LN* phead = BuyList(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListDstroy(LN* phead)
{
	assert(phead);

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

void ListPushBack(LN* phead, LTDataType x)
{
	assert(phead);

	/*LN* tail = phead->prev;
	LN* newnode = BuyList(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/

	ListInsert(phead->prev, x);

}

void ListPushFront(LN* phead, LTDataType x)
{
	assert(phead);

	/*LN* first = phead->next;
	LN* newnode = BuyList(x);

	first->prev = newnode;
	newnode->prev = phead;
	newnode->next = first;
	phead->next = newnode;*/

	ListInsert(phead->next, x);
}

void ListPopBack(LN* phead)
{
	assert(phead);
	/*assert(phead->next != phead);

	LN* tail = phead->prev;
	LN* prevtail = tail->prev;
	prevtail->next = phead;
	phead->prev = prevtail;

	free(tail);
	tail = NULL;*/
	ListErase(phead->prev);
}

void ListPopFront(LN* phead)
{
	assert(phead);
	/*assert(phead->next!=phead);


	LN* first = phead->next;
	LN* second = first->next;
	second->prev = phead;
	phead->next = second;

	free(first);
	first = NULL;*/

	ListErase(phead->next);

}

LN* ListFind(LN* phead, LTDataType x)
{
	assert(phead);

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

void ListInsert(LN* pos, LTDataType x)
{
	assert(pos);

	LN* prev = pos->prev;
	LN* newnode = BuyList(x);
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prev;
	prev->next = newnode;

}

void ListErase(LN* pos)
{
	assert(pos);

	LN* PosNext = pos->next;
	LN* PosPrev = pos->prev;
	PosNext->prev = PosPrev;
	PosPrev->next = PosNext;

	free(pos);
	pos = NULL;
}

4.2 List.h文件

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LN;

LN* BuyList(LTDataType x);

LN* ListInit();

void ListDstroy(LN* phead);

void ListPushBack(LN* phead, LTDataType x);

void ListPrint(LN* phead);

void ListPushFront(LN* phead, LTDataType x);

void ListPopBack(LN* phead);

void ListPopFront(LN* phead);

LN* ListFind(LN* phead, LTDataType x);

void ListInsert(LN* pos,LTDataType x);

void ListErase(LN* pos);

4.3 test.c文件

#define  _CRT_SECURE_NO_WARNINGS

#include "List.h"

void test1()
{
	LN* plist = NULL;//链表头位置的创建
	plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	ListPushFront(plist, 0);
	ListPushFront(plist, -1);
	ListPrint(plist);

	ListPopFront(plist);
	ListPrint(plist);

	ListPopBack(plist);
	ListPrint(plist);
}

void test2()
{
	LN* plist = NULL;
	plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	LN* pos = ListFind(plist, 3);
	if (pos)
	{
		ListInsert(pos, 0);
	}
	ListPrint(plist);

	ListErase(pos);
	ListPrint(plist);
}
int main()
{
	//test1();
	test2();

	return 0;
}

test1函数结果
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构
test2函数结果
C语言--带哨兵位的双向循环链表的创建及使用详解,c语言,链表,开发语言,学习,算法,数据结构

5. 总结

双向循环链表创建的难度从总体来说是小于单向链表的，只要熟悉了单向链表的创建，双向循环链表将会很快得到解决。
同时链表的学习是往后很多数据结构类型学习的基础，熟练掌握链表，对后续的学习又很大的帮助。文章来源地址https://www.toymoban.com/news/detail-811734.html

到了这里，关于C语言--带哨兵位的双向循环链表的创建及使用详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 双向带头循环链表的实现

    双向带头循环链表的实现

    当我们要学习和了解一个事物时，我们要做的第一步便是对这个事物有一个体的的了解。现在我们要学习双向带头循环链表的第一步也是这个，我们现在先来了解一下这种链表的结构---- 就像该图所呈现的那样，双向循环链表就是长这样。但是你可 千万不要将head当成head。  

    2024年02月05日
    浏览(45)
  • 链表的极致——带头双向循环链表

    链表的极致——带头双向循环链表

    ​ 双向带头循环链表是链表结构最复杂，但使用最方便的链表。 [图中phead表示链表的头节点（哨兵）; d1，d2等表示链表存储的数据； d1，d2等左侧的方框存储是指向该节点的上一个节点的指针（prev），右侧方框存储指向该节点的下一个的指针（next）] 双向带头循环链表的每

    2024年04月10日
    浏览(76)
  • 双向循环链表的插入和删除

    双向循环链表的插入和删除

    ·插入 1）头插 2）尾插 3)中间插 ·删除 1）头删 2）尾删 3）中间删

    2024年04月25日
    浏览(50)
  • 双向循环链表的增删改查功能

    双向循环链表的增删改查功能

    双向循环链表的增删改查 结果验证：

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

    【数据结构】双向带头循环链表的实现

    前言：在前面我们学习了顺序表、单向链表，今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学习!一起努力！ 带头双向循环链

    2024年01月15日
    浏览(49)
  • 数据结构-带头双向循环链表的实现

    数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构，它的结构是很完美的，它弥补了单链表的许多不足，让我们一起来了解一下它是如何实现的吧！         它的节点中存储着数据和两个指针，一个 指针_prev 用来记录前一个节点的地址，另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(49)
  • 来领略一下带头双向循环链表的风采吧

    来领略一下带头双向循环链表的风采吧

    🍉 博客主页：阿博历练记 📖文章专栏：数据结构与算法 🚍代码仓库：阿博编程日记 🌹欢迎关注：欢迎友友们点赞收藏+关注哦 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但

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

    追梦之旅【数据结构篇】——详解C语言动态实现带头结点的双向循环链表结构

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

    2024年01月17日
    浏览(61)
  • 【数据结构】链表：带头双向循环链表的增删查改

    【数据结构】链表：带头双向循环链表的增删查改

    本篇要分享的内容是带头双向链表，以下为本片目录 目录 一、链表的所有结构 二、带头双向链表 2.1尾部插入 2.2哨兵位的初始化 2.3头部插入 2.4 打印链表 2.5尾部删除 2.6头部删除  2.7查找结点 2.8任意位置插入 2.9任意位置删除  在刚开始接触链表的时候，我们所学仅仅所学的

    2024年02月05日
    浏览(91)
  • 【数据结构】—带头双向循环链表的实现（完美链表）

    【数据结构】—带头双向循环链表的实现（完美链表）

    链表结构一共有八种形式，在前面的文章里已经讲完了不带头单向非循环链表的实现，但是我们发现该链表实现尾插与尾删时比较麻烦，要先从头节点进行遍历，找到尾节点，时间复杂度为O(N)，而本次所讲的带头双向循环单链表，则可以直接找到尾节点。 虽然该链表看起来

    2024年01月25日
    浏览(63)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包