数据结构与算法(C语言版)P3.2---链表之带头双向循环链表的实现

2023-09-16 15:43:28

1、前言

前面一章详细介绍了链表的概念、结构以及分类。并且实现了无头单向非循环链表。
这一篇主要实现带头双向循环链表的。由于需要串联前面的知识，把上一篇至此：链表之无头单向非循环链表的实现

2、带头双向循环链表的特性和结构

2.1、结构

在这里插入图片描述
（1）、每个结点有两个指针域（next，prev），一个数据域（data）。
（2）前面结点的next指针域指向后一个结点的地址，并且后一个结点的prev指针域指向前一个结点的地址。
（3）头结点的prev指针域指向尾节点的地址，并且尾节点的next指针域指向头结点地址。

由以上复杂的结构构成了带头双向循环链表。

2.2、特性

带头双向循环链表：结构复杂，使用简单。一般用在单独存储数据。实际中使用的链表结构，都是带头双向链表，另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

为什么说带头双向循环链表的使用简单呢？
其中有一个原因就是"带头"。
那这里就不得不说链表中带头结点（哨兵位）的好处了。

3、带头结点和不带头结点的区别

链表中带哨兵位和不带哨兵位的主要区别在于对边界条件的处理。下面是它们的一些区别：

哨兵位：

  • 带哨兵位的链表在头节点之前插入一个特殊的节点，称为哨兵节点或者虚拟头节点。
  • 哨兵节点的值一般为空，它的存在使得链表的操作更加简单，避免了很多边界条件的判断。
  • 带哨兵位的链表通常有更统一的代码结构，操作起来更加方便。

边界条件处理：

  • 不带哨兵位的链表需要特殊处理空链表和只有一个节点的情况。
  • 在不带哨兵位的链表中，需要单独对头节点为空或者只有一个节点的情况进行处理，增加了代码编写和维护的复杂度。

空间开销：

  • 带哨兵位的链表相比不带哨兵位的链表会多占用一个节点的空间。

总结来说就是，如果使用带哨兵位的链表，我们在遇见插入和删除结点的操作时不用再特殊考虑一些边界情况。比如：没有头结点，只有一个结点或者有多个结点时的3种情况。

所以说使用带哨兵位可以降低链表的难度。

那下面就来实现带头双向循环链表。

4、带头双向循环链表的实现

主要实现接口功能：

  • 哨兵位初始化（ListInit）
  • 扩容（BuyListNode）
  • 头插（ListPushFront）
  • 打印（ListPrint）
  • 销毁（ListDestroy）
  • 头删（ListPopFront）
  • 尾插（ListPushBack）
  • 尾删（ListPopBack）
  • 查询指定pos位置元素（ListFind）
  • 在pos位置之前插入（ListInsert）
  • 删除pos位置结点（ListErase）

4.1、定义结构体

#pragma once

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

typedef int LTDataType;

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

next指针变量用于本结点链接后继节点。
prev指针变量用于本结点链接前继节点。
data变量用于存储数据。

4.2、哨兵位初始化

LNode* ListInit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));

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

这里的哨兵位初始化，一定要注意，由于带头双向循环链表结构的特殊性，哨兵位的首尾是相连的。所以我们需要将哨兵位的next和prev都指向本身。

4.3、扩容

扩容的思想千篇一律，不在介绍。

LNode* BuyListNode(LTDataType x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

4.4、头插

除了要考虑相邻结点之间的链接，这里还要考虑首结点和尾节点的首尾相连。

void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	LNode* newnode = BuyListNode(x);

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

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

4.5、打印

这里打印接口说明一下，和无头单向非循环相比，这里的while循环结束的条件不同。因为带头双向循环链表结点是首尾相连的，所以这里的尾节点不在是NULL了，而phead，所以当cur == phead说明链表遍历结束。

void ListPrint(LNode* phead)
{
	assert(phead);

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

4.6、销毁

while循环条件结束和打印接口的一样，都是cur == phead时链表遍历结束。

void ListDestroy(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

4.7、以上接口功能测试

实现了头插，打印，销毁，扩容，初始化等接口功能，就可以测试以下基本插入程序了。

#include "list.h"

void TestList1()
{
	LNode* plist = ListInit();

	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);
	ListPushFront(plist, 6);

	ListPrint(plist);

	ListDestroy(plist);
}

int main()
{
	TestList1();
	return 0;
}

输出：
在这里插入图片描述

基础接口功能没问题，继续向下完善。

4.8、头删

void ListPopFront(LNode* phead)
{
	//断言是否只有哨兵位
	assert(phead);
	assert(phead->next != NULL);

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

4.9、尾插

这里需要说明，在以往的无头单向非循环链表中，我们需要依次向后遍历的找尾节点。但是在这里找为节点是很简单的操作。因为带头双向循环链表时首位结点相互链接的。哨兵位的prev指向的就是尾节点。

void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

4.10、尾删

void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

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

4.11、查询指定pos位置元素，返回结点地址pos

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

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

4.12、在pos位置之前插入

核心思想：记录pos前继结点，然后依次链接即可。

void ListInsert(LNode* pos,LTDataType x)
{
	assert(pos);
	LNode* newnode = BuyListNode(x);
	LNode* posPrev = pos->prev;

	posPrev->next = newnode;
	newnode->prev = posPrev;

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

4.13、删除pos位置

核心思想：记录pos的前继、后驱结点，然后依次链接即可。

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

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

那到此为止带头双向循环链表的基础接口就实现完毕了。

其实在进行__头插、头删、尾插、尾删__的时候有个高级的处理方式。就是借助__ListFind、ListInsert、ListErase__接口进行处理。下面我们来具体写代码演示。

5、头插、头删、尾插、尾删的高级实现方式

5.1、头插

核心思想：ListInsert接口本身就是完成指定pos位置之前的插入。如果我们想要在头插种使用，那只需要传参头结点后驱结点的地址即可。在头结点的后驱结点使用ListInsert就是头插。

void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	/*
	LNode* newnode = BuyListNode(x);

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

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

	//使用ListInsert接口完成头插功能
	ListInsert(phead->next, x);
}

5.2、头删

void ListPopFront(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	*/

	//使用ListErase接口完成头删功能
	ListErase(phead->next);
}

5.3、尾插

核心思想：这里有个地方难理解。为什么我们使用ListInsert接口函数进行尾插，需要传参phead？我们不应该传尾节点的地址吗？那是因为带头双向循环链表的首位结点时相连的，因为phead就是尾节点的地址，所以就需要传参phead。

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

	/*
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
	*/

	//使用ListInsert接口完成尾插功能
	ListInsert(phead,x);
}

5.4、尾删

void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
	*/

	//使用ListErase接口完成尾删功能
	ListErase(phead->prev);
}

至此带头双向循环链表主要功能已全部实现，下面展示全代码验证其正确性。

6、全代码展示

这里使用三个文件：

  • list.h：用于结构体、各种函数接口的声明
  • list.c：用于各种函数接口的定义。
  • test.c：用于创建链表，实现链表。

6.1、list.h

#pragma once

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

typedef int LTDataType;

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


//哨兵位初始化
LNode* ListInit();

//扩容
LNode* BuyListNode(LTDataType x);

//头插
void ListPushFront(LNode* phead, LTDataType x);

//打印
void ListPrint(LNode* phead);

//销毁
void ListDestroy(LNode* phead);

//头删
void ListPopFront(LNode* phead);

//尾插
void ListPushBack(LNode* phead, LTDataType x);

//尾删
void ListPopBack(LNode* phead);

//查询指定pos位置元素，返回结点pos地址
LNode* ListFind(LNode* phead, LTDataType x);

//在pos位置之前插入
void ListInsert(LNode* pos,LTDataType x);

//删除当前pos位置结点
void ListErase(LNode* pos);

6.2、list.c

#include "list.h"

//哨兵位初始化
LNode* ListInit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));

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

//扩容
LNode* BuyListNode(LTDataType x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

//头插
void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	/*
	LNode* newnode = BuyListNode(x);

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

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

	//使用ListInsert接口完成头插功能
	ListInsert(phead->next, x);
}

//打印
void ListPrint(LNode* phead)
{
	assert(phead);

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

//销毁
void ListDestroy(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

//头删
void ListPopFront(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	*/

	//使用ListErase接口完成头删功能
	ListErase(phead->next);
}

//尾插
void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);

	/*
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
	*/

	//使用ListInsert接口完成尾插功能
	ListInsert(phead,x);
}

//尾删
void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
	*/

	//使用ListErase接口完成尾删功能
	ListErase(phead->prev);
}

//查询指定pos位置元素，返回结点pos地址
LNode* ListFind(LNode* phead, LTDataType x)
{
	assert(phead);

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

//在pos位置之前插入
void ListInsert(LNode* pos,LTDataType x)
{
	assert(pos);
	LNode* newnode = BuyListNode(x);
	LNode* posPrev = pos->prev;

	posPrev->next = newnode;
	newnode->prev = posPrev;

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

//删除当前pos位置结点
void ListErase(LNode* pos)
{
	assert(pos);

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

6.3、test.c

#include "list.h"

void TestList1()
{
	LNode* plist = ListInit();

	ListPushFront(plist, 11);
	ListPushFront(plist, 22);
	ListPushFront(plist, 33);
	ListPushFront(plist, 44);
	ListPushFront(plist, 55);
	ListPushFront(plist, 66);

	ListPopBack(plist);

	//LNode* pos = ListFind(plist, 4);
	//ListErase(pos);

	ListPrint(plist);

	ListDestroy(plist);
}

int main()
{
	TestList1();
	return 0;
}
更多推荐

Unity shader内置standard代码解析

最近有相关需求制作，所以这里编写一个文档，方便后续的流程查看。下载源码由于unity内置的shader是无法查看源码的，你需要去官网下载对应版本内置源码查看在引擎下载那里，会有一个BuiltinShaders，下载打开以后，就是对应的shader内置的shandard在DefaultResourcesExtra目录内，

更快，更稳，更智能，科聪穿梭车（RGV）快速构建方案！

随着自动化物流发展，密集存储得到越来越广泛地应用，已经是现代物流的重要组成部分之一。作为密集存储系统中关键设备之一，穿梭车（RGV）越来越受到大家的重视。穿梭车（RGV）是一种智能机器人，可以编程实现取货、运送、放置等任务，并可与上位机、调度系统或WMS系统进行通讯，结合RFID、条码等识别技术，实现自动化识别、存取等

Git：Git的一些基本操作

文章目录基本认识使用方法创建本地仓库配置本地仓库工作区、暂存区、版本库的概念添加文件版本回退撤销修改删除操作基本认识首先要对Git有一个基本的认知：Git本质上是一个版本控制器，可以对一个信息的多个版本进行一些控制，而能对版本的控制的好处就是，不管需要哪个版本的内容，都可以借助Git这个工具找到所需要的信息Git是一个

API接口在电商商品数据获取中的应用

一、引言在当前的数字化时代，电子商务平台已经成为了人们购物的主要场所之一。许多电商平台都提供了API接口，以便开发者可以获取商品数据并进行创新应用。本文将深入探讨如何使用API接口获取商品数据，以及如何将这些数据应用到电商领域中。二、API接口概述1.API接口定义API（ApplicationProgrammingI

Java-List＜Map＞的复制 深拷贝与浅拷贝

博客背景是Java开发。讲一讲List<Map>的复制中深拷贝与浅拷贝。文章目录1、浅拷贝1.1循环遍历复制1.2使用list实现类的构造方法1.3addAll方法2、深拷贝深拷贝工具类SerializationUtils.clone1、浅拷贝Map除了基本类型是值传递，其余的都是引用地址传递。由于map的value存

MySql(随记)

一条MySql执行过程首先Mysql的架构分为两层，Server层和存储引擎层。Server层：MySql大多数核心功能，主要包括，连接器，查询缓存，解释器，预处理器，优化器，执行器等存储引擎层：负责数据的获取和存储。（innodb，MyISAM）连接器1.首先经过TCP三次握手，随后进行权限验证，若有问题则返回“Ac

UI美工设计岗位的基本职责概述（合集）

UI美工设计岗位的基本职责概述11、有良好的美术功底、设计新颖，整体配色及设计创意理念，能够独立完成整个网站页面设计及制作;2、熟练运用DIV+CSS，HTML设计制作网页;3、熟练运用Photoshop,Dreamweaver,Coreldraw(或Illustrator),Flash，Fireworks等软件。4、

两个有序链表序列的交集

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。输出格式:在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。输入

红黑树插入的实现

红黑树：1.概念：红黑树的性质：红黑树的插入操作：其前面的插入和二叉搜索树的一模一样，只是后面需要判断是否满足红黑树的性质：具体分为三种情况：1.uncle节点存在且为红色的：对应如图：这种情况只需要将parent和uncle节点都弄成黑色，对应的grandparent节点弄成黑色接下来又会分为三种情况：1.如果对应的

创新未来，工信部组建【AI应用工作组】助力人工智能进步

随着人工智能大模型技术的快速发展和成熟，AI应用已经从早期的概念阶段进入了千行百业的实践落地阶段，三百六十行、行行需AI。如今，AI已经成为推动各行各业创新和发展的重要引擎，对经济、社会和文化的发展产生了深远的影响。为了进一步推动人工智能应用的落地和创新，工业和信息化部工业文化发展中心于9月12日上午在北京王府井希尔顿

Go net http包

文章目录1Request2Response3client4HTTPServer服务端5自定义处理器（CustomHandlers）6将函数作为处理器7中间件Middleware8静态站点在Go中，搭建一个HTTPserver简单到令人难以置信。只需要引入net/http包，写几行代码，一个HTTP服务器就可以正常运行并

热文推荐
  1. cms之帝国cms安装

    内容摘要帝国网站管理系统，英文名称为EmpireCMS，简称“帝国CMS”，本文将介绍帝国网站管理系统的安装方法。前言：本文安装教程是以帝国CMS7.5版本为基础进行图文讲解。各位看官，一定要按照每个步骤去执行，技术是以熟能生巧为主，在学习的过程中，要认真仔细的去做好每一步。关注我，手把手帮你搭建自己的小窝一、安装前准

  2. Spring源码分析(三) IOC 之 getBean()和doGetBean()

    b、在中篇会正式经历一套生命周期流程getBean()->doGetBean()->createBean()->doCreateBean()->createBeanInstance()->populateBean()->initializeBean()流程1、AbstractBeanFactory#getBean()此

  3. 计算机遇到MSVCP140.dll丢失问题？全面分析解决方案

    今天我要和大家分享的主题是：计算机中丢失MSVCP140.dll的解决方法。在我们日常使用电脑的过程中，经常会遇到一些棘手的问题，而MSVCP140.dll文件丢失就是其中之一。这个问题可能会给我们的工作、学习和娱乐带来诸多不便，因此我希望通过今天的演讲，能够帮助大家解决这个问题。首先，让我们来了解一下什么是MSVCP

  4. 面对突如其来的 GC 问题如何下手解决

    今天我们主要从一个实战案例入手分析面对突如其来的GC问题该如何下手解决。想要下手解决GC问题，我们首先需要掌握下面这三种问题。如何使用jstat命令查看JVM的GC情况？面对海量GC日志参数，如何快速抓住问题根源？你不得不掌握的日志分析工具。工欲善其事，必先利其器。我们前面课时讲到的优化手段，包括代码优化、扩容、参数优

  5. OpenWrt kernel install分析（2）

    一.前言接下来分析make-CimagecompileinstallTARGET_BUILD=。二.Makefile分析1.命令首先运行target/linux/mediatek/image/Makefile,该文件内容如下：target/linux/mediatek/image/Makefile:include$(T

  6. Win32 位图直接绘制

    CBitmapDraw.h#pragmaonce#include<wtypes.h>#include<type_traits>#defineCOLOR_RGB_TO_BGR(_rgb)((_rgb&0xFF)<<16)|(_rgb&0x00FF00)|((_rgb>>16)&0xFF)typedefstruct_BIT

  7. 易点易动库存管理系统：引领库存用量控制新时代，助力企业节约成本

    在现代企业经营中，库存管理一直是一个关键的环节。过多的库存会造成资金占用和浪费，而过少的库存则容易导致生产中断和客户满意度下降。为了解决这一难题，易点易动库存管理系统应运而生。一、全面的库存数据管理易点易动库存管理系统通过与企业的仓储系统实时对接，实现了对库存数据的全面管理。无论是原材料、半成品还是成品，系统都能准确记

  8. 什么是Vue的Vetur插件？它有哪些功能

    引言在现代前端开发中，Vue.js已经成为了一个备受欢迎的JavaScript框架。随着Vue.js的流行，开发人员需要强大的工具来提高他们的生产力和Vue.js项目的质量。Vetur插件是一个为Vue.js开发者提供的强大工具，它不仅提供了丰富的功能，还能让你更轻松地编写和维护Vue.js应用程序。本文将深入探讨Ve

  9. 007-第一代软件需求整理

    第一代软件需求整理文章目录第一代软件需求整理项目介绍需求来源需求来源1：竞品软件分析需求来源2：医生（市场）需求来源3：项目组内部需求来源4：软件组内部需求来源5：软件开发成员需求来源6：法律和法规总结一下关键字：Qt、Qml、需求、类型、采集项目介绍欢迎来到我们的QML&C++项目！这个项目结合了QML（QtMeta