链表/双向循环链表（C/C++）

        本篇将给出双向循环链表的有关操作，以及对应的一些解释，大多都以注释给出。本篇给出的双向循环链表全称为带头双向循环链表。即如下图所示：

        在本篇中一共包含三个代码片段，分别为：双向链表需要实现的内容、双向链表函数的实现、双向链表的全部代码与测试。如有需要，可直接在对应位置查找。

        其中的head，为头结点，我们也称之为哨兵位，该位置不会存放任何的有效数据，但这个结点是真实存在的。

        注意：对于头结点（哨兵位）来说，由图我们可以得出：

        1.哨兵位的下一位才是第一个结点，即head->next是第一个结点;

        2. 哨兵位的前一个结点为尾结点，即head->prior为最后一个结点。

        对于哨兵为的意义来说就是：遍历循环链表的时避免死循环。

1.双向链表的实现内容

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* prior;
	struct ListNode* next;
}LTNode;

//双向链表初始化
LTNode* LTInit();
//双向链表的销毁
void LTDestroy(LTNode* phead);
//判断链表是否为NULL
void LTEmpty(LTNode* phead);
//遍历双向链表
void LTPrint(LTNode* phead);

//尾插/头插
void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead, DataType x);

//尾删/头删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//查找结点位置
LTNode* LTFind(LTNode* phead, DataType x);  

//在指定位置之前/之后插入数据
void LTInsert(LTNode* pos, DataType x);
void LTInsertBefore(LTNode* pos, DataType x);

//删除指定位置
void LTErase(LTNode* pos);

2.双向链表函数的实现 

        在以下的实现内容中的每个函数，都会有一定的注释，便于读者理解：

//创建一个头结点
LTNode* CreateNode(DataType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟空间是否成功，但其实一般情况下都是可以申请成功（以下判断条件可有可无）
	if (newNode == NULL) {
		perror("malloc:");
		exit(1);
	}
	newNode->data = x;
	//创建一个新结点的同时，将新节点的前驱和后继指向自己
	newNode->next = newNode->prior = newNode;
	return newNode;
}

//双向链表初始化
LTNode* LTInit() {
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	if (head == NULL) {
		perror("malloc:");
		exit(1);
	}
	head->data = -1;
	head->prior = head->next = head;
	//可以用创建结点函数来获取头结点
	//head = CreateNode(-1);
	return head;
}

//尾插，在尾结点插入一个元素
void LTPushBack(LTNode* phead,DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//尾结点的下一个结点指向的是头结点
	newNode->next = phead;
	//头结点的prior结点为尾结点，将新节点的前驱指向原来的尾结点
	newNode->prior = phead->prior;
	
	//phead->prior为原来的尾结点,将原来的尾结点指向newNode
	phead->prior->next = newNode;
	//phead->prior指向新节点
	phead->prior = newNode;
}

//头插，在第一个结点处插入元素
void LTPushFront(LTNode* phead, DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//将新节点的前驱指向头结点
	newNode->prior = phead;
	//新节点的后继指向原来的第一个结点
	newNode->next = phead->next;

	//phead->next为原来的头结点
	phead->next->prior = newNode;
	phead->next = newNode;
}

//尾删，删除链表的尾结点
void LTPopBack(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);
	//哨兵位的前一个结点为尾结点
	LTNode* delete = phead->prior;
	//prior为尾结点的前一个结点
	LTNode* prior = delete->prior;

	//将尾结点的前一个结点指向头结点
	prior->next = phead;
	//更新头结点的前驱（尾结点）
	phead->prior = prior;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL; 
}

//头删，删除链表的第一个结点
void LTPopFront(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);

	//phead->next为第一个结点
	LTNode* delete = phead->next;
	LTNode* next = delete->next;

	//将第二节点的前驱指向phead(delete->prior)
	next->prior = delete->prior;
	//更新第一个结点
	phead->next = next;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL;
}

//遍历链表
void LTPrint(LTNode* phead) {
	assert(phead);
	if (phead->next == phead) {
		printf("该链表为NULL\n");
		return;
	}
	//将current指向第一个结点
	LTNode* current = phead->next;
	printf("head->");
	//当current为头结点时，停止遍历
	while (current!= phead) {
		printf("%d->", current->data);
		current = current->next;
	}
	printf("head\n");
}

//判断链表是否为NULL
void LTEmpty(LTNode* phead) {
	assert(phead);
	//头结点的后继指向自己或者前驱指向自己时，链表为NULL
	if (phead->next == phead) {
		printf("空链表\n");
	}
	else {
		printf("非空链表\n");
	}
}

//链表的销毁
void LTDestroy(LTNode* phead) {
	assert(phead);
	//从第一个结点开始删除
	LTNode* current = phead->next;
	while (current != phead) {
		//先找到下一个结点
		LTNode* next = current->next;
		free(current);
		//更新current
		current = next;
	}
	//删除尾结点
	free(phead);
	//注：由于phead与传入的指针head同为一级指针，
	//free(phead)只能释放head存放的东西，
	//但不能改变head的地址，在函数外还需要将head置为NULL
}

//找元素
LTNode* LTFind(LTNode* phead, DataType x) {
	assert(phead);
	//从第一个结点开始遍历
	LTNode* current = phead->next;
	while (current != phead) {
		if (current->data == x) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}

//在指定位置尾插
void LTInsert(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->next = pos->next;
	newNode->prior = pos;

	//将pos位置的后继的proir指针指向新节点
	pos->next->prior = newNode;
	//pos的next指针指向新节点
	pos->next = newNode;
}

//在指定位置之前插入元素
void LTInsertBefore(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->prior = pos->prior;
	newNode->next = pos;

	//将pos位置的前驱的next指针指向新节点
	pos->prior->next = newNode;
	//将pos的prior指针指向新节点
	pos->prior = newNode;
}

//删除指定位置的元素
void LTErase(LTNode* pos) {
	assert(pos);
	//将pos位置的前驱结点和后继结点记录下来
	LTNode* prior = pos->prior;
	LTNode* next = pos->next;

	//前驱结点的next指针指向后继结点
	prior->next = next;
	//后继结点的proir指针指向前驱结点
	next->prior = prior;
	free(pos);
	pos = NULL;
}

3.双向链表的全部代码与测试

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* prior;
	struct ListNode* next;
}LTNode;

//创建一个头结点
LTNode* CreateNode(DataType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟空间是否成功，但其实一般情况下都是可以申请成功（以下判断条件可有可无）
	if (newNode == NULL) {
		perror("malloc:");
		exit(1);
	}
	newNode->data = x;
	//创建一个新结点的同时，将新节点的前驱和后继指向自己
	newNode->next = newNode->prior = newNode;
	return newNode;
}

//双向链表初始化
LTNode* LTInit() {
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	if (head == NULL) {
		perror("malloc:");
		exit(1);
	}
	head->data = -1;
	head->prior = head->next = head;
	//可以用创建结点函数来获取头结点
	//head = CreateNode(-1);
	return head;
}

//尾插，在尾结点插入一个元素
void LTPushBack(LTNode* phead,DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//尾结点的下一个结点指向的是头结点
	newNode->next = phead;
	//头结点的prior结点为尾结点，将新节点的前驱指向原来的尾结点
	newNode->prior = phead->prior;
	
	//phead->prior为原来的尾结点,将原来的尾结点指向newNode
	phead->prior->next = newNode;
	//phead->prior指向新节点
	phead->prior = newNode;
}

//头插，在第一个结点处插入元素
void LTPushFront(LTNode* phead, DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//将新节点的前驱指向头结点
	newNode->prior = phead;
	//新节点的后继指向原来的第一个结点
	newNode->next = phead->next;

	//phead->next为原来的头结点
	phead->next->prior = newNode;
	phead->next = newNode;
}

//尾删，删除链表的尾结点
void LTPopBack(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);
	//哨兵位的前一个结点为尾结点
	LTNode* delete = phead->prior;
	//prior为尾结点的前一个结点
	LTNode* prior = delete->prior;

	//将尾结点的前一个结点指向头结点
	prior->next = phead;
	//更新头结点的前驱（尾结点）
	phead->prior = prior;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL; 
}

//头删，删除链表的第一个结点
void LTPopFront(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);

	//phead->next为第一个结点
	LTNode* delete = phead->next;
	LTNode* next = delete->next;

	//将第二节点的前驱指向phead(delete->prior)
	next->prior = delete->prior;
	//更新第一个结点
	phead->next = next;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL;
}

//遍历链表
void LTPrint(LTNode* phead) {
	assert(phead);
	if (phead->next == phead) {
		printf("该链表为NULL\n");
		return;
	}
	//将current指向第一个结点
	LTNode* current = phead->next;
	printf("head->");
	//当current为头结点时，停止遍历
	while (current!= phead) {
		printf("%d->", current->data);
		current = current->next;
	}
	printf("head\n");
}

//判断链表是否为NULL
void LTEmpty(LTNode* phead) {
	assert(phead);
	//头结点的后继指向自己或者前驱指向自己时，链表为NULL
	if (phead->next == phead) {
		printf("空链表\n");
	}
	else {
		printf("非空链表\n");
	}
}

//链表的销毁
void LTDestroy(LTNode* phead) {
	assert(phead);
	//从第一个结点开始删除
	LTNode* current = phead->next;
	while (current != phead) {
		//先找到下一个结点
		LTNode* next = current->next;
		free(current);
		//更新current
		current = next;
	}
	//删除尾结点
	free(phead);
	//注：由于phead与传入的指针head同为一级指针，
	//free(phead)只能释放head存放的东西，
	//但不能改变head的地址，在函数外还需要将head置为NULL
}

//找元素
LTNode* LTFind(LTNode* phead, DataType x) {
	assert(phead);
	//从第一个结点开始遍历
	LTNode* current = phead->next;
	while (current != phead) {
		if (current->data == x) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}

//在指定位置尾插
void LTInsert(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->next = pos->next;
	newNode->prior = pos;

	//将pos位置的后继的proir指针指向新节点
	pos->next->prior = newNode;
	//pos的next指针指向新节点
	pos->next = newNode;
}

//在指定位置之前插入元素
void LTInsertBefore(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->prior = pos->prior;
	newNode->next = pos;

	//将pos位置的前驱的next指针指向新节点
	pos->prior->next = newNode;
	//将pos的prior指针指向新节点
	pos->prior = newNode;
}

//删除指定位置的元素
void LTErase(LTNode* pos) {
	assert(pos);
	//将pos位置的前驱结点和后继结点记录下来
	LTNode* prior = pos->prior;
	LTNode* next = pos->next;

	//前驱结点的next指针指向后继结点
	prior->next = next;
	//后继结点的proir指针指向前驱结点
	next->prior = prior;
	free(pos);
	pos = NULL;
}

void Test01() {
	LTNode* head = LTInit();
	LTPushBack(head, 1);
	LTPushBack(head, 2);
	LTPushBack(head, 3);
	LTPushBack(head, 4);
	LTPrint(head); // 1 2 3 4

	LTPushFront(head, 5);
	LTPushFront(head, 6);
	LTPushFront(head, 7);
	LTPrint(head); // 7 6 5 1 2 3 4

	LTPopBack(head);
	LTPrint(head); // 7 6 5 1 2 3 

	LTPopFront(head);
	LTPrint(head); // 6 5 1 2 3 


	LTNode* Find = LTFind(head, 3);
	if (Find == NULL) {
		printf("没有找到\n");    //找到了
	}
	else {
		printf("找到了\n");   
	}

	LTInsert(Find, 5); 
	LTInsertBefore(Find, 6); 
	LTPrint(head); // 6 5 1 2 6 3 5

	LTErase(Find);
	LTPrint(head); // 6 5 1 2 6 5
	LTDestroy(head);
	head = NULL;
}

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

        测试结果：

        这些所有操作即为带头双向循环链表的所有操作了。 

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

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

相关文章

JS进阶-解构赋值（一）

JS进阶-解构赋值（一）

扩展&#xff1a;解构赋值时Js特有的一种处理数据的方式&#xff0c;在Java中没有处理数据的方式 知识引入&#xff1a; 思考&#xff1a;在js中&#xff0c;在没有学习解构赋值之前&#xff0c;我们是如何获取数组的内容的&#xff1f; 以上要么不好记忆&#xff0c;要么书写麻…
阅读更多...
gitlab备份-迁移-升级方案9.2.7升级到15版本最佳实践

gitlab备份-迁移-升级方案9.2.7升级到15版本最佳实践

背景 了解官方提供的版本的升级方案 - GitLab 8: 8.11.Z 8.12.0 8.17.7 - GitLab 9: 9.0.13 9.5.10 9.2.7 - GitLab 10: 10.0.7 10.8.7 - GitLab 11: 11.0.6 11.11.8 - GitLab 12: 12.0.12 12.1.17 12.10.14 - GitLab 13: 13.0.14 13.1.11 13.8.8 13.12.15 - G…
阅读更多...
利用nginx宝塔免费防火墙实现禁止国外IP访问网站

利用nginx宝塔免费防火墙实现禁止国外IP访问网站

本章教程&#xff0c;主要介绍&#xff0c;如何利用nginx宝塔面板中的插件免费防火墙&#xff0c;实现一键禁止国外IP访问网站。 目录 一、安装宝塔插件 二、 开启防火墙 一、安装宝塔插件 在宝塔面板中的软件商店&#xff0c;搜索防火墙关键词&#xff0c;找到Nginx免费防火…
阅读更多...
详解STP生成树

详解STP生成树

华子目录 前沿导入二层环路导致问题&#xff1a; 生成树802.1D 角色选举根网桥根端口指定端口非指定端口&#xff08;阻塞端口&#xff09; cost值接口状态down侦听学习转发阻塞 收敛时间当结构发生变化时 802.1D缺点802.1D配置命令PVSTPVST快速生成树RSTP基于组的快速生成树MS…
阅读更多...
Docker数据管理

Docker数据管理

管理 Docker 容器中数据主要有两种方式&#xff1a;数据卷&#xff08;Data Volumes&#xff09;和数据卷容器&#xff08;DataVolumes Containers&#xff09;。 在生成容器的同时&#xff0c;加上 -v 选项&#xff0c;指定把当前服务器的目录映射到容器中&#xff0c;实现do…
阅读更多...
单核QPS近6000S，陌陌基于OceanBase的持久化缓存探索与实践

单核QPS近6000S，陌陌基于OceanBase的持久化缓存探索与实践

挚文集团于 2011 年 8 月推出了陌陌&#xff0c;这款立足地理位置服务的开放式移动视频社交应用在中国社交平台领域内独树一帜。陌陌和探探作为陌生人社交领域的主流应用&#xff0c;涵盖了多种核心业务模块&#xff0c;包括直播服务、附近动态功能、即时通讯&#xff08;IM&am…
阅读更多...
亚马逊测评：自养号测评的深度解析与策略

亚马逊测评：自养号测评的深度解析与策略

亚马逊测评对于卖家来说至关重要&#xff0c;特别是在当今竞争激烈的电商环境中。然而&#xff0c;许多人对亚马逊测评的理解仅停留在刷销量和积累好评的层面&#xff0c;忽视了自养号测评的其他重要功能。本文将深入探讨自养号测评的多种功能&#xff0c;以及如何建立稳定、高…
阅读更多...
用graalvm将maven项目打包成可执行文件

用graalvm将maven项目打包成可执行文件

概述&#xff1a;配置graalvm或者用graalvm打包springboot项目请看下面文章&#xff1a; Springboot3新特性&#xff1a;开发第一个 GraalVM 本机应用程序(完整教程)-CSDN博客 废话不多说&#xff0c;咱们开始用GraalVM打包maven项目。 第一步&#xff1a;引入依赖和插件 p…
阅读更多...
mac 修改flutter sdk配置

mac 修改flutter sdk配置

问题描述&#xff1a;我mac电脑上有高低2个版本的flutter sdk&#xff0c;我需要低版本sdk的项目在setting里设置了sdk版本&#xff0c;可是命令行还是提示我版本过高。 直接上解决办法&#xff1a; 打开mac终端&#xff0c;输入open -e .bash_profile&#xff0c;然后修改下…
阅读更多...
06.搭建一个自己的私有仓库-Gitea

06.搭建一个自己的私有仓库-Gitea

06.搭建一个自己的私有仓库-Gitea | DLLCNX的博客 如果你是一位程序员或者IT相关领域的从业者&#xff0c;那么肯定知道git&#xff0c;而且也或多或少接触了不少开源仓库以及公司的私有仓库&#xff0c;但是我们有没有想过自己也搭建一个私有仓库呢。 这么多开源仓库&#xf…
阅读更多...
Goodbye！ Xshell、iTerm2、FinalShell，mobaxterm，新一代开源免费的终端工具真香！

Goodbye！ Xshell、iTerm2、FinalShell，mobaxterm，新一代开源免费的终端工具真香！

前言 众所周知&#xff0c;在数字化时代&#xff0c;远程连接成为工作和管理中不可或缺的一环。 而在这个领域&#xff0c;SSH&#xff08;Secure Shell&#xff09;一直是最常用的协议之一&#xff0c;为远程管理提供了安全的通信渠道。 然而&#xff0c;伴随着技术的发展和…
阅读更多...
docker 体验怀旧游戏（魂斗罗等）

docker 体验怀旧游戏（魂斗罗等）

docker run --restart always -p 8081:80 --name fc-games -d registry.cn-hangzhou.aliyuncs.com/bystart/fc-games:latest ip:8081访问 jsnes: js制作了一个网页版的NES模拟&#xff0c;可以在网页上玩fc游戏 (gitee.com)
阅读更多...
Unity中URP下计算额外灯的方向

Unity中URP下计算额外灯的方向

文章目录 前言一、为什么额外灯的方向&#xff0c;不像主平行灯一样直接获取&#xff1f;1、主平行灯2、额外灯中&#xff0c;包含 点光源、聚光灯 和 平行灯 二、获得模型顶点指向额外灯的单位向量三、Unity中的实现 前言 在上一篇文章中&#xff0c;我们获取了URP下额外灯的…
阅读更多...
探索Gin框架：快速构建高性能的Golang Web应用

探索Gin框架：快速构建高性能的Golang Web应用

前言 Gin框架是一个轻量级的Web框架&#xff0c;基于Go语言开发&#xff0c;旨在提供高性能和简洁的API。它具有快速的路由和中间件支持&#xff0c;使得构建Web应用变得更加简单和高效。无论是构建小型的API服务还是大型的Web应用&#xff0c;Gin框架都能够满足你的需求。 无论…
阅读更多...
vivado I/O和时钟规划设计流程步骤

vivado I/O和时钟规划设计流程步骤

I/O和时钟规划设计流程步骤 下图显示了左侧的项目设计流程步骤。水平箭头表示项目设计流程中可以执行I/O和时钟规划的点。中的步骤I/O和时钟规划设计流程如右图所示。 项目设计流程从一个空的I/O规划项目、RTL设计项目或合成后网表项目。使用这些项目类型中的任何一种&#xf…
阅读更多...
【江科大】STM32：USART串口（理论部分）上

【江科大】STM32：USART串口（理论部分）上

串口 全双工&#xff1a;可以进行同步通信 单端信号&#xff1a;信号线传输的就是单端信号。&#xff08;也就是与地线&#xff08;GND&#xff09;的电势差&#xff09; 缺点&#xff1a;防干扰能力差 原因&#xff1a;当信号从A点传输到B点&#xff0c;理想条件是A&#xff0…
阅读更多...
Unity 解决异步分发方案

Unity 解决异步分发方案

很多程序&#xff0c;包括游戏、小程序、一些AR、VR的程序&#xff0c;因为客户端体量太大&#xff0c;更新频繁都涉及到远程热更新的问题&#xff0c;解决这类问题的思路基本上是客户端解决主要功能&#xff0c;资源类放置在服务器。 下面记录下&#xff1a; 1.CDN或者云轻量…
阅读更多...
探讨Go语言中的HTTP代理模式：看Go如何玩转网络中转站

探讨Go语言中的HTTP代理模式：看Go如何玩转网络中转站

在互联网的海洋中&#xff0c;HTTP代理服务器像一座灯塔&#xff0c;为我们的网络冲浪提供了指引。而当Go语言遇上HTTP代理&#xff0c;会碰撞出怎样的火花呢&#xff1f;今天&#xff0c;让我们一起探讨Go语言中的HTTP代理模式&#xff0c;看看它如何玩转这个网络中转站&#…
阅读更多...
BGV/BFV 的统一自举算法

BGV/BFV 的统一自举算法

参考文献&#xff1a; [GV23] Geelen R, Vercauteren F. Bootstrapping for BGV and BFV Revisited[J]. Journal of Cryptology, 2023, 36(2): 12.Bit Extraction and Bootstrapping for BGV/BFV 文章目录 Bootstrapping for BGV and BFVDecryption FunctionBGVBFV Bootstrapp…
阅读更多...
项目管理中，项目经理如何预防需求蔓延？

项目管理中，项目经理如何预防需求蔓延？

在项目管理中&#xff0c;需求蔓延是一个常见的问题&#xff0c;需求蔓延可能会导致项目进度延误、成本增加和产品质量下降。为了防止这种情况发生&#xff0c;项目经理需要采取一系列措施来预防需求蔓延。 一、明确项目范围和需求 项目经理需要在项目开始阶段明确项目范围和…
阅读更多...
最新文章

Copyright @ 2022~2023