双链表的实现

我们知道链表其实有很多种，什么带头，什么双向啊，我们今天来介绍双向带头循环链表，了解了这个其他种类的链表就很简单了。冲冲冲！！！

链表的简单分类

链表有很多种，什么带头循环链表，我们先看这一个图就十分了解了。

我们只需要知道链表的底层逻辑，那么不管什么链表都能说出个大概。

双链表的简要概述

带头双向循环链表（以下都称双链表）和顺序表一样它是一个连着一个，但有一个哨兵位（充当头节点，注意里面没有有效数据），它的特点通俗的讲每个节点都能找到邻位，这个好处是循环用的少。我们带图来理解一下。

双链表的实现

我们创建一个List.h文件放双链表增删查改函数的声明，一个List.c文件放增删查改函数的实现。而链表节点的声明：

typedef int LDataType;
//双链表节点
typedef struct ListNode
{
	LDataType x;
	struct ListNode* prev;
	struct ListNode* next;
}LNode;

初始化函数的实现

这个函数的作用是创建一个哨兵位节点，以后的增删查改函数都基于这个哨兵位上面。既然是要创建节点，那么我们得先开辟一个节点空间，不如我们将开辟空间封装成一个函数，后续开辟空间调用这个函数即可。

//链表节点申请
LNode* LBuyNode(LDataType  x)
{
	LNode* node = (LNode*)malloc(sizeof(LNode));
	if (node == NULL)
	{
		perror("LBuyNode::malloc!");
		return NULL;
	}
	node->x = x;
	node->prev = node;
	node->next = node;
	return node;
}
//链表的初始化
void InitList(LNode** pphead)
{
	//将第一个节点设为哨兵位
	*pphead = LBuyNode(-1);
}

尾插函数的实现

在尾插之前我们首先要开辟节点然后再插入，进行一系列操作。

//尾插
void LpushBack(LNode* phead, LDataType x)
{
	assert(phead);
	LNode* newnode = LBuyNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}

打印函数的实现

注意我们这个函数的打印和顺序表，单链表打印完全不同，稍不注意就会陷入死循环。

//链表打印
void LPrint(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->x);
		cur = cur->next;
	}
	printf("\n");
}

头插函数的实现

和尾插函数一样，插入之前要先开辟节点空间再进行一系列操作。

//头插
void LpushFront(LNode* phead, LDataType x)
{
	//插入之前哨兵位不能没有哨兵位
	assert(phead);
	LNode* newnode = LBuyNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

查找函数的实现

这个函数还是和打印函数一样，注意别陷入死循环。

//查找某个值
LNode* LFind(LNode* phead, LDataType x)
{
	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->x == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

在指定位置之后插入函数的实现

这个函数一般配合上面的查找函数一起合作完成。

//在pos位置之后插入
void InsertAfter(LNode* pos, LDataType x)
{
	//插入的位置不能为空
	assert(pos);
	LNode* newnode = LBuyNode(x);
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
	newnode->prev = pos;
}

在指定位置之前插入函数的实现

这个函数仍然要和查找函数配合完成。

//在pos位置之前插入
void InsertBefore(LNode* pos, LDataType x)
{
	assert(pos);
	LNode* newnode = LBuyNode(x);
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
}

尾删函数的实现

//尾删
void LpopBack(LNode* phead)
{
	assert(phead);
	LNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}

头删函数的实现

这个函数还是和上面尾删函数没啥特点，我们自己想几分钟就行。这里不过多介绍。

//头删
void LpopBefore(LNode* phead)
{
	assert(phead);
	LNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}

删除指定位置节点

//删除pos节点
void LDelpos(LNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

链表销毁函数的实现

这里销毁函数和其他链表函数销毁不同，这里注意区别，防止陷入死循环。

//链表的销毁
void LDestory(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur!=phead)
	{
		free(cur);
		cur = cur->next;
	}
	cur = NULL;
	free(phead);
	phead = NULL;
}

总代码

List.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LDataType;
//双链表节点
typedef struct ListNode
{
	LDataType x;
	struct ListNode* prev;
	struct ListNode* next;
}LNode;

//链表的初始化
void InitList(LNode** pphead);

//链表节点申请
LNode* LBuyNode(LDataType  x);

//头插
void LpushFront(LNode* phead, LDataType x);

//链表打印
void LPrint(LNode* phead);

//尾插
void LpushBack(LNode* phead, LDataType x);

//查找某个值
LNode* LFind(LNode* phead, LDataType x);

//在pos位置之后插入
void InsertAfter(LNode* pos, LDataType x);

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

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

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

//删除pos节点
void LDelpos(LNode* pos);

//链表的销毁
void LDestory(LNode* phead);

List.c文件

#include"List.h"
//链表节点申请
LNode* LBuyNode(LDataType  x)
{
	LNode* node = (LNode*)malloc(sizeof(LNode));
	if (node == NULL)
	{
		perror("LBuyNode::malloc!");
		return NULL;
	}
	node->x = x;
	node->prev = node;
	node->next = node;
	return node;
}
//链表的初始化
void InitList(LNode** pphead)
{
	//将第一个节点设为哨兵位
	*pphead = LBuyNode(-1);
}
//链表打印
void LPrint(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->x);
		cur = cur->next;
	}
	printf("\n");
}
//头插
void LpushFront(LNode* phead, LDataType x)
{
	//插入之前哨兵位不能没有哨兵位
	assert(phead);
	LNode* newnode = LBuyNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}
//尾插
void LpushBack(LNode* phead, LDataType x)
{
	assert(phead);
	LNode* newnode = LBuyNode(x);
	phead->prev->next = newnode;
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev = newnode;
}
//查找某个值
LNode* LFind(LNode* phead, LDataType x)
{
	LNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->x == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//在pos位置之后插入
void InsertAfter(LNode* pos, LDataType x)
{
	//插入的位置不能为空
	assert(pos);
	LNode* newnode = LBuyNode(x);
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
	newnode->prev = pos;
}
//在pos位置之前插入
void InsertBefore(LNode* pos, LDataType x)
{
	assert(pos);
	LNode* newnode = LBuyNode(x);
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
}
//尾删
void LpopBack(LNode* phead)
{
	assert(phead);
	LNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del = NULL;
}
//头删
void LpopBefore(LNode* phead)
{
	assert(phead);
	LNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}
//删除pos节点
void LDelpos(LNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
//链表的销毁
void LDestory(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur!=phead)
	{
		free(cur);
		cur = cur->next;
	}
	cur = NULL;
	free(phead);
	phead = NULL;
}

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

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

相关文章

【c基础】文件操作

【c基础】文件操作

1.fopen和fclose函数 函数原型 FILE *fopen(const char *path, const char *mode); 参数解释&#xff1a; 返回值&#xff1a;fopen打开成功&#xff0c;则返回有效file的有效地址&#xff0c;失败返回NULL。path是文件路径&#xff0c;可以相对路径&#xff0c;可以绝对路径…
阅读更多...
“手撕“三大特性之一的＜继承＞（上）

“手撕“三大特性之一的＜继承＞（上）

目录 一、为什么需要继承 二、什么是继承 三、继承怎么写 四、成员的访问 1.父类与子类的成员变量不同名 2.父类与子类的成员变量同名 3.父类与子类的成员方法不同名 4.父类与子类的成员方法同名 五、super关键字 一、为什么需要继承 先让我们看一段Java代码&#…
阅读更多...
Unity地形关联出错的解决办法以及地形深度拷贝

Unity地形关联出错的解决办法以及地形深度拷贝

问题 最近发现unity地形系统的一个bug&#xff0c;导入的场景地形数据关联错乱了&#xff0c;关联到别的场景的地形数据了&#xff0c;meta替换了也没用&#xff0c;不清楚它具体是怎么关联的。 看下面的案例&#xff1a; 可以看到正常这个场景的地形数据应该关联的是Scene_E…
阅读更多...
力扣HOT100 - 142. 环形链表 II

力扣HOT100 - 142. 环形链表 II

解题思路&#xff1a; public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set new HashSet<>();while (head ! null) {if (!set.add(head)) {return head;}head head.next;}return null;} }
阅读更多...
文心一言 VS 讯飞星火 VS chatgpt （241）-- 算法导论17.3 7题

文心一言 VS 讯飞星火 VS chatgpt （241）-- 算法导论17.3 7题

七、为动态整数多重集 S (允许包含重复值)设计一种数据结构&#xff0c;支持如下两个操作&#xff1a;① INSERT(S,x) 将 x 插入 S 中&#xff1b;② DELETE-LARGER-HALF(S) 将最大的 ⌈|S|/2⌉ 个元素从S中删除。解释如何实现这种数据结构&#xff0c;使得任意 m 个 INSERT 和…
阅读更多...
Linux的firewalld防火墙

Linux的firewalld防火墙

介绍firewalld&#xff1a; ①、firewalld&#xff08;Dynamic Firewall Manager of Linux systems&#xff0c;Linux系统的动态防火墙管理器&#xff09;服务是默认的防火墙配置管理工具&#xff0c;它拥有基于CLI&#xff08;命令行界面&#xff09;和基于GUI&#xff08;图…
阅读更多...
Web Tours系统使用说明书

Web Tours系统使用说明书

1.系统简介 产品名称&#xff1a;LoadRunner的Web Tours系统 产品功能&#xff1a;注册和登录用户信息、订票办理、退片办理、查询已定票信息、退出系统 系统默认用户&#xff1a;用户名jojo 密码&#xff1a;bean 2. 功能简介 2.1 注册用户信息 点击 sign up now&#xff…
阅读更多...
（自学用）正演理论

（自学用）正演理论

基于波动方程如何解决数值频散问题——快速正演方法 NAD方法&#xff1a; 怎样离散/逼近高阶偏导数&#xff08;如何采样&#xff09;&#xff1a; 传统方法是用某一点及其周围点的函数f的线性组合来逼近导数。只有函数值&#xff0c;要想提高精度&#xff0c;压制数值频散就必…
阅读更多...
（C语言）fscanf与fprintf函数详解

（C语言）fscanf与fprintf函数详解

目录 1 fprintf详解 1.1 向文件流中输入数据 1.2 向标准输入流写数据 2. fscanf函数详解 2.1 从文件中读取格式化数据 2.2 从标准输入流中读取格式化数据 1 fprintf详解 头文件&#xff1a;stdio.h 该函数和printf的参数特别像&#xff0c;只是多了一个参数stream&#…
阅读更多...
Unity类银河恶魔城学习记录13-5,6 p146 Delete save file,p147 Encryption of saved data源代码

Unity类银河恶魔城学习记录13-5,6 p146 Delete save file,p147 Encryption of saved data源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili FileDataHandler.cs using System; using System.IO; using UnityEngine; p…
阅读更多...
现代农业AI智能化升级之路：机器学习在现代农业领域的现状与未来发展

现代农业AI智能化升级之路：机器学习在现代农业领域的现状与未来发展

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…
阅读更多...
Android AIDL接口

Android AIDL接口

一.AlDI接口简介 AIDL&#xff08;Android Interface Definition Language&#xff09;是一种 IDL 语言&#xff0c;用于生成可以在 Android 设备上两个进程之间进行进程间通信&#xff08;IPC&#xff09;的代码。 通过 AIDL&#xff0c;可以在一个进程中获取另一个进程的数据…
阅读更多...
力扣112，路径总和

力扣112，路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 叶子节点 是指没有子节点…
阅读更多...
.cur 鼠标光标编辑器

.cur 鼠标光标编辑器

详解透明贴图和三元光栅操作 - CodeBus 鼠标指针文件格式解析——Windows&#xff08;二&#xff09; (qq.com) [C/C] RGBA数组生成Windows下的ico文件_c ico格式-CSDN博客 色环设计 - CodeBus 左键绘制 右键选颜色 ctrl右键设置鼠标热点 F1导出.cur文件 //代码来源&…
阅读更多...
分组查询得到一列多行数据后，怎么用来和表中的某列数据进行一一比较

分组查询得到一列多行数据后，怎么用来和表中的某列数据进行一一比较

#10&#xff09;查询每个学生超过他自己选修课程平均成绩的课程号 这里要先进行分组得到每个学号对应的平均成绩&#xff0c;在用表中的成绩grade与得到的平均成绩一一比较 这里可以进行连表操作&#xff0c;把分组查询得到的结果与原表通过sno学号进行等值连接 &#xff0c;就…
阅读更多...
轻量级SQLite可视化工具Sqliteviz

轻量级SQLite可视化工具Sqliteviz

什么是 Sqliteviz &#xff1f; Sqliteviz 是一个单页面离线优先的渐进式网络应用&#xff08;PWA&#xff09;&#xff0c;用于完全客户端的 SQLite 数据库或 CSV 文件的可视化。 所谓完全客户端&#xff0c;就是您的数据库永远不会离开您的计算机。使用 sqliteviz&#xff0c…
阅读更多...
ubuntu server 安装emqx tdengine

ubuntu server 安装emqx tdengine

文章目录 1 安装emqx2 安装taos 1 安装emqx 86 wget https://www.emqx.com/zh/downloads/broker/5.6.0/emqx-5.6.0-ubuntu22.04-amd64.deb87 ls88 pwd89 sudo apt install ./emqx-5.6.0-ubuntu22.04-amd64.deb90 sudo systemctl start emqx91 systemctl status emqx92 s…
阅读更多...
C语言求自幂数（水仙花数与其他自幂数）

C语言求自幂数（水仙花数与其他自幂数）

前言 今天我们来看一下如果求解自幂数&#xff08;水仙花数&#xff09;&#xff0c;水仙花数是自幂数的一种&#xff0c;我们来看看自幂数的概念吧&#xff0c;当一个n位数&#xff0c;它的每个位上的数字的n次幂之和等于它本身的时候&#xff0c;我们称这个数为自幂数。水仙花…
阅读更多...
文本溢出体验进阶：CSS 技巧实现单行/多行隐藏展示以及实际场景应用，确保内容可读性和布局整洁性

文本溢出体验进阶：CSS 技巧实现单行/多行隐藏展示以及实际场景应用，确保内容可读性和布局整洁性

CSS文本溢出隐藏是一种常见的场景&#xff0c;它广泛应用于各种网页设计中&#xff0c;旨在确保内容的可读性和布局的整洁性&#xff0c;特别是在空间有限或需要适应不同屏幕尺寸的情况下。 一、文本溢出隐藏并显示省略号 1、单行文本溢出隐藏并显示省略号 对于单行文本&…
阅读更多...
怎么找程序员对象？和程序员谈恋爱是什么体验？

怎么找程序员对象？和程序员谈恋爱是什么体验？

和程序员谈恋爱是一种非常累的体验&#xff0c;因为他们大部分时间都会加班&#xff0c;守在电脑面前不能够陪自己。但是这样的男孩子&#xff0c;忠诚、认真、不会花花草草、收入贼高&#xff0c;恋爱幸福指数接近满分哦&#xff01; 程序员都是宅男&#xff0c;都是电脑狂魔&…
阅读更多...
最新文章

Copyright @ 2022~2023