双链表的实现

news/2024/10/21 7:32:35/

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

链表的简单分类

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

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

双链表的简要概述

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

双链表的实现

我们创建一个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;
}

http://www.ppmy.cn/news/1426843.html

相关文章

【C语言】贪吃蛇项目（2）- 实现代码详解

【C语言】贪吃蛇项目（2）- 实现代码详解

文章目录 前言一、游戏开始界面设计首先 - 打印环境界面其次 - 游戏地图、蛇身及食物的设计1、地图2、蛇身设置及打印3、食物 二、游戏运行环节蛇的上下左右移动等功能蛇的移动 三、结束游戏代码 前言 在笔者的前一篇博客中详细记载了贪吃蛇项目所需的一些必备知识以及我们进行…
阅读更多...
【算法刷题day28】Leetcode：93. 复原 IP 地址、78. 子集、90. 子集 II

【算法刷题day28】Leetcode：93. 复原 IP 地址、78. 子集、90. 子集 II

文章目录 Leetcode 93. 复原 IP 地址解题思路代码总结 Leetcode 78. 子集解题思路代码总结 Leetcode 90. 子集 II解题思路代码总结 草稿图网站 java的Deque Leetcode 93. 复原 IP 地址 题目&#xff1a;93. 复原 IP 地址 解析&#xff1a;代码随想录解析 解题思路 “.”参数初…
阅读更多...
ORACLE错误提示概述

ORACLE错误提示概述

OceanBase分布式数据库-海量数据 笔笔算数 保存起来方便自己查看错误代码。 ORA-00001: 违反唯一约束条件 (.) ORA-00017: 请求会话以设置跟踪事件 ORA-00018: 超出最大会话数 ORA-00019: 超出最大会话许可数 ORA-00020: 超出最大进程数 () ORA-00021: 会话附属于其它某些进程…
阅读更多...
改进前后端交互实例

改进前后端交互实例

前后端交互实例(javaweb05)-CSDN博客 在这之前我假设大家都已经学完了IOC和DI 不明白的这里我也解释一下,首先是两个概念 1.控制反转:对象的创建控制权由程序自身转到外部(容器) 2.依赖注入:容器为程序提供运行时所依赖的资源 Bean对象:IOC容器中创建,关联的对象,称之为be…
阅读更多...
生活中的洪特规则

生活中的洪特规则

不知道你还记不记得高中物理所学的一个奇特的物理规则&#xff1a;洪特规则。 洪特规则是德国人弗里德里希洪特&#xff08;F.Hund&#xff09;根据大量光谱实验数据总结出的一个规律&#xff0c;它指出电子分布到能量简并的原子轨道时&#xff0c;优先以自旋相同的方式分别占…
阅读更多...
JavaWeb-登录校验

JavaWeb-登录校验

会话技术 浏览器使用的是http协议&#xff0c;多次请求间数据是不能共享的&#xff0c;例如我们要去访问用户数据的接口&#xff0c;但这时候用户是否已经登入了呢&#xff1f;是不知道的&#xff0c;为了解决这个问题&#xff0c;于是引入了会话跟踪技术。 会话&#xff1a;…
阅读更多...
Windows如何安装JDK

Windows如何安装JDK

JDK和JRE简介 JDK&#xff1a;Java Development ToolKit java开发工具包&#xff0c;包含JRE针对java程序开发者 JRE&#xff1a;Java Runtime Environment java程序的运行环境针对java使用者来说 下载JDK&#xff0c;进入官网下载 Oracle官网 双击下载好之后的exe文件&#…
阅读更多...
论文笔记：Are Human-generated Demonstrations Necessary for In-context Learning?

论文笔记：Are Human-generated Demonstrations Necessary for In-context Learning?

iclr 2024 reviewer 评分 6668 1 intro 大型语言模型&#xff08;LLMs&#xff09;已显示出在上下文中学习的能力 给定几个带注释的示例作为演示&#xff0c;LLMs 能够为新的测试输入生成输出然而&#xff0c;现行的上下文学习&#xff08;ICL&#xff09;范式仍存在以下明显…
阅读更多...
最新文章

Copyright @ 2022~2023