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

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

  • 1. 双向循环链表定义
    • 1.1 定义
    • 1.2 优点:
    • 1.3 物理结构
  • 2. 双向链表的创建
    • 2.1 文件创建
    • 2.2 节点创建
  • 3. 链表操作
    • 3.1 初始化
    • 3.2 显示
    • 3.3 尾插
    • 3.4 头插
    • 3.5 尾删
    • 3.6 头删
    • 3.7 查找
    • 3.8 指定位置前插入
    • 3.9 指定位置删除
    • 3.10 链表销毁
  • 4. 链表总内容
    • 4.1 List.c 文件
    • 4.2 List.h文件
    • 4.3 test.c文件
  • 5. 总结

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 物理结构

物理结构如下图:
在这里插入图片描述

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

在这里插入图片描述

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 初始化

带哨兵位的双向链表的初始化需要创建一个哨兵位,同时将头指针和尾指针都指向哨兵位的地址,物理图如下:
在这里插入图片描述
代码如下:

//初始化的本质是创建一个不放数据的节点,返回该节点地址
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 的地址.
在这里插入图片描述

//尾插需要链表的哨兵位节点与要插入的数据,不需要返回任何值
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 的地址.
在这里插入图片描述

//头插需要链表的哨兵位节点与要插入的数据,不需要返回任何值
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 的空间。
在这里插入图片描述

//尾删仅需要找到尾节点的位置,改变节点位置即可,不需要返回任何值
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 的空间。
在这里插入图片描述

//头删仅需要找到第一个数据的的位置,改变节点位置即可,不需要返回任何值
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 的地址.
在这里插入图片描述

//指定位置前插入需要指定的位置以及需要插入的数据
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 的空间。

在这里插入图片描述

//指定位置删除仅需指定的位置即可
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函数结果
在这里插入图片描述
test2函数结果
在这里插入图片描述

5. 总结

双向循环链表创建的难度从总体来说是小于单向链表的,只要熟悉了单向链表的创建,双向循环链表将会很快得到解决。
同时链表的学习是往后很多数据结构类型学习的基础,熟练掌握链表,对后续的学习又很大的帮助。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/329813.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Qt之模型视图】2. 模型类及QModelIndex模型索引、自定义模型

1. 模型类 在模型/视图体系结构中&#xff0c;模型提供了一个标准接口&#xff0c;视图和委托使用该接口访问数据。在Qt中&#xff0c;标准接口是由QAbstractItemModel类定义的。无论数据项如何存储在任何底层数据结构中&#xff0c;QAbstractItemModel的所有子类都会以层次结…

GPT APP的开发步骤

开发一个GPT&#xff08;Generative Pre-trained Transformer&#xff09; Store&#xff08;存储&#xff09;涉及到使用预训练的语言模型&#xff08;例如GPT-3&#xff09;来生成和管理内容。以下是一般的步骤&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&…

云计算入门——Linux 命令行入门

云计算入门——Linux 命令行入门 前些天发现了一个人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;最重要的屌图甚多&#xff0c;忍不住分享一下给大家。点击跳转到网站。 介绍 如今&#xff0c;我们许多人都熟悉计算机&#xff08;台式机和笔记本电…

vscode 中配置 python 虚拟环境

vscode 中配置 python 虚拟环境 Start 在编写代码的过程中&#xff0c;我们经常会用到一些第三方依赖&#xff0c;帮助我们快速完成功能。在 Python 中&#xff0c;默认情况都是统一安装在全局环境中&#xff0c;但是这样伴随着电脑项目越来越多&#xff0c;不同项目对依赖的…

XTuner 大模型单卡低成本微调实战

1 概述 1.1 XTuner 一个大语言模型微调工具箱。由 MMRazor 和 MMDeploy 联合开发。 1.2 支持的开源LLM (2023.11.01) InternLM ✅Llama&#xff0c;Llama2ChatGLM2&#xff0c;ChatGLM3QwenBaichuan&#xff0c;Baichuan2…Zephyr 1.3 特色 &#x1f913; 傻瓜化&#xf…

pytest学习和使用-pytest如何进行分布式测试?(pytest-xdist)

1 什么是分布式测试&#xff1f; 在进行本文之前&#xff0c;先了解些基础知识&#xff0c;什么是分布式测试&#xff1f;分布式测试&#xff1a;是指通过局域网和Internet&#xff0c;把分布于不同地点、独立完成特定功能的测试计算机连接起来&#xff0c;以达到测试资源共享…

Ubuntu系统环境搭建(十三)——使用docker-compose安装redis

ubuntu环境搭建专栏&#x1f517;点击跳转 Ubuntu系统环境搭建&#xff08;十三&#xff09;——使用docker-compose安装redis 文章目录 Ubuntu系统环境搭建&#xff08;十三&#xff09;——使用docker-compose安装redis1.搭建文件夹2.docker-compose.yaml配置文件3.redis.co…

银河麒麟操作系统 v10 中离线安装 Docker

银河麒麟操作系统 v10 中离线安装 Docker 1. 查看系统版本2. 查看 Linux 内核版本&#xff08;3.10以上&#xff09;3. 查看 iptabls 版本&#xff08;1.4以上&#xff09;4. 判断处理器架构5. 离线下载 Docker 安装包6. 移动解压出来的二进制文件到 /usr/bin 目录中7. 配置 Do…

Shiro框架:Shiro用户访问控制鉴权流程-内置过滤器方式源码解析

目录 1.配置访问控制鉴权流程的2种方式 2.Shiro内置过滤器 3.权限控制流程解析 3.1 权限&#xff08;Permissions&#xff09;配置和初始化流程 3.1.1 通过filterChainDefinitionMap配置url权限 3.1.1.1 应用层配置方式 3.1.1.2 配置解析过程 3.1.1.2.1 FilterChainMan…

css3 纯代码案例

css3 纯代码案例 前言渐变之美1.1 纯CSS3实现的渐变背景1.2 使用多重颜色和方向打造丰富渐变效果1.3 渐变色停留动画的巧妙运用 纯CSS图形绘制2.1 使用border属性制作三角形、梯形等形状伪类箭头图标2.2 利用transform创建旋转、缩放的图形 浮动的阴影敲代码css准备reset 样式复…

电商平台spu和sku的完整设计

一、关于数据库表的设计 1、商品属性表 比如一个衣服有颜色、尺码、款式这个叫属性表 -- ------------------------ -- 商品属性表 -- ------------------------ DROP TABLE IF EXISTS attribute; CREATE TABLE attribute (id int(11) NOT NULL PRIMARY KEY AUTO_INCREMENT CO…

Maven工程 — 继承与聚合 相关知识点详解

简介&#xff1a;这篇帖子主要讲解Maven工程中的继承与聚合的相关知识点&#xff0c;用简洁的语言和小编自己的理解&#xff0c;深入浅出的说明Maven工程的继承与聚合。 目录 1、继承 1.1 继承关系的实现 1.2 版本锁定 2、聚合 2.1 聚合方法 3、总结 1、继承 图 1-1 继承…

阿里云国外服务器价格购买与使用策略

阿里云国外服务器优惠活动「全球云服务器精选特惠」&#xff0c;国外服务器租用价格24元一个月起&#xff0c;免备案适合搭建网站&#xff0c;部署独立站等业务场景&#xff0c;阿里云服务器网aliyunfuwuqi.com分享阿里云国外服务器优惠活动&#xff1a; 全球云服务器精选特惠…

Vue3在点击菜单切换路由时,将页面el-main的内容滚动到顶部

功能&#xff1a;Vue3在点击菜单切换路由时&#xff0c;将页面el-main的内容滚动到顶部&#xff0c;布局如下&#xff0c;使用ui组件为ElementPlus 在网上搜很多都是在route.js中的router.beforeEach中使用window.scrollTop(0,0) 或 window.scrollTo(0,0) 滚动&#xff0c;但是…

springboot-简单测试 前端上传Excel表格后端解析数据

导入依赖 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>5.2.2</version></dependency><dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxm…

uni-app的数据缓存

数据缓存uni.setStorage 将数据存储在本地缓存中指定的 key 中&#xff0c;会覆盖掉原来该 key 对应的内容&#xff0c;这是一个异步接口。 参数名类型必填说明keyString是本地缓存中的指定的 keydataAny是需要存储的内容&#xff0c;只支持原生类型、及能够通过 JSON.string…

vite和webpack的区别和作用

前言 Vite 和 Webpack 都是现代化的前端构建工具&#xff0c;它们可以帮助开发者优化前端项目的构建和性能。虽然它们的目标是相似的&#xff0c;但它们在设计和实现方面有许多不同之处。 一、Vite详解和作用 vite 是什么 vite —— 一个由 vue 作者尤雨溪开发的 web 开发工…

ArcGIS Pro 标注牵引线问题

ArcGIS Pro 标注 模仿CAD坐标牵引线问题 右键需要标注的要素&#xff0c;进入标注属性。 选择背景样式 在这里有可以选择的牵引线样式 选择这一个&#xff0c;可以根据调整间距来进行模仿CAD标注样式。 此图为cad样式 此为调整后gis样式 此处可以调整牵引线的样式符号 …

【NodeJS】nodejs后端渲染html

背景 Node.js 后端渲染 HTML 在提高网站性能、优化用户体验、简化前端开发流程以及提升内容可抓取性等方面都具有显著的价值。这种模式特别适用于那些不需要复杂交互的网站&#xff0c;例如博客、产品页面或者一些信息发布平台等。然而&#xff0c;对于需要高度交互和动态用户…

华为路由设备DHCPV6配置

组网需求 如果大量的企业用户IPv6地址都是手动配置&#xff0c;那么网络管理员工作量大&#xff0c;而且可管理性很差。管理员希望实现公司用户IPv6地址和网络配置参数的自动获取&#xff0c;便于统一管理&#xff0c;实现IPv6的层次布局。 图1 DHCPv6服务器组网图 配置思路 …