【数据结构】链表

【数据结构】 链表

1.链表的概念及结构

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域

在这里插入图片描述

2.链表的分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

1.单向或者双向

在这里插入图片描述

2.带头或者不带头

在这里插入图片描述

3.循环或者非循环

在这里插入图片描述

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:

无头单向非循环链表带头双向循环链表

在这里插入图片描述

  1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

3.无头单向非循环链表的实现

初始化链表

链表是由一个个结点链接而成,创建一个链表之前,我们首先要创建一个结点类型,该类型由两部分组成:数据域指针域

typedef int SLDataType;typedef struct SListNode {SLDataType data;struct SListNode *next;
} SListNode

打印链表

打印链表时,我们需要从头指针指向的位置开始,依次向后打印,直到指针指向NULL时,结束打印。

// 单链表打印
void SListPrint(SListNode *plist) {// 不用assert  单链表为NULL 打印NULL即可SListNode *cur = plist;   //接收头指针while (cur)// cur!=NULL{printf("%d->", cur->data);cur = cur->next;    //更新结点,走下一个结点}printf("NULL\n");
}

增加结点

仔细想想,每当我们需要增加一个结点之前,我们必定要先申请一个新结点,然后再插入到相应位置,于是我们可以将该功能封装成一个函数。

// 动态申请一个节点
SListNode *BuySListNode(SLDataType x) {SListNode *newnode = (SListNode *) malloc(sizeof(SListNode));//申请空间if (newnode == NULL) {perror("malloc fail");exit(-1);} else {newnode->data = x;   //将数据赋值到新结点的数据域newnode->next = NULL;//将新结点的指针域置空return newnode;}
}

链表的头插

头插时,我们只需要先让新结点的指针域指向头指针指向的位置(即原来的第一个结点),然后让头指针指向新结点即可。这里头插会修改原始指针,原始指针是一个一级指针,对他进行修改需要二级指针。

// 单链表的头插
void SListPushFront(SListNode **pplist, SLDataType x) {SListNode *newnode = BuySListNode(x);//申请一个新结点// 头插不用判断是否为空,如果为空,那么newnode->next就为空newnode->next = *pplist;//新结点指向头结点*pplist = newnode;      //在更新头结点,这里修改了原始指针,所以需要使用二级指针,才会改变实参
}

注:这两步操作的顺序不能颠倒,若先让头指针指向新结点,那么就无法找到原来第一个结点的位置了。

链表的尾插

尾插的时候我们需要先判断链表是否为空,若为空,则直接让头指针指向新结点即可;若不为空,我们首先需要利用循环找到链表的最后一个结点,然后让最后一个结点的指针域指向新结点。

// 单链表尾插
void SListPushBack(SListNode **pplist, SLDataType x) {SListNode *newnode = BuySListNode(x);//如果链表为NULL,那么新插入的结点就是头结点if (*pplist == NULL) {*pplist = newnode;} else {//遍历找最后的结点SListNode *tail = *pplist;while (tail->next)// 注意:这里是找下一个,在尾插的前一个结点要设置next{tail = tail->next;}tail->next = newnode;}
}

注:新结点创建的时候指针域就已经置空,所以尾插时不需要再将新结点的指针域置空。

在给定位置之后插入

在给定位置后插入结点也只需要两步:先让新结点的指针域指向该位置的下一个结点,然后再让该位置的结点指向新结点即可。

// x插入到pos位置之后
void SListInsertAfter(SListNode *pos, SLDataType x) {// pos不能为NULLassert(pos);SListNode *newnode = BuySListNode(x);// 将创建的新结点插入到pos之后newnode->next = pos->next;pos->next = newnode;
}

注:这两步操作也不能颠倒顺序,理由与头插时相同。

在给定位置之前插入

要想在给定位置的前面插入一个新结点,我们首先还是要找到该位置之前的一个结点,然后让新结点的指针域指向地址为pos的结点,让前一个结点指向新结点即可。需要注意的是,当给定位置为头指针指向的位置时,相当于头插。

// x插入到pos位置之前
void SListInsert(SListNode **pplist, SListNode *pos, SLDataType x) {assert(pos);// 如果pos的位置在头结点的位置,逻辑就为头插,否则就插入到前面// 同样的这里的原始指针可能被重新赋值,需要传递二级指针if (*pplist == pos) {SListPushFront(pplist, x);} else {// 创建一个开始的结点,然后判断prev的next是否为pos  是的话,就连接prev和newnodeSListNode *prev = *pplist;while (prev->next != pos) {prev = prev->next;}SListNode *newnode = BuySListNode(x);newnode->next = prev->next;prev->next = newnode;}
}

删除结点

链表的头删

头删较为简单,若为空表,则不必做处理;若不为空表,则直接让头指针指向第二个结点,然后释放第一个结点的内存空间即可。

// 头删
// 删除会影响原始指针,所以依然传递二级指针
void SListPopFront(SListNode **pplist) {assert(*pplist);// 为NULL直接assert,不为空直接将头结点删除,下一个结点变成头结点SListNode *nextnode = (*pplist)->next;free(*pplist);*pplist = nextnode;
}

链表的尾删

尾删相对麻烦一些,我们需要考虑三种不同的情况:

1、当链表为空时,不做处理。
2、当链表中只有一个结点时,直接释放该结点,然后将头指针置空。
3、当链表中有多个结点时,我们需要先找到最后一个结点的前一个结点,然后将最后一个结点释放,将前一个结点的指针域置空,使其成为新的尾结点。

// 尾删
void SListPopBack(SListNode **pplist) {assert(*pplist);// 创建两个结点一个指向第一个,一个指向第二个,因为删除结点要找到前一个结点的next赋值SListNode *prev = NULL;SListNode *tail = *pplist;// 1.只有一个节点// 2.两个及以上的节点if (tail->next == NULL) {free(tail);*pplist = NULL;} else {while (tail->next)// 如果下一个结点为空,就删除当前结点,在将prev结点的next赋值为NULL{prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

删除给定位置之后的结点

要删除给定位置之后的值,我们首先判断传入地址是否为最后一个结点的地址,若是,则不做处理,因为最后一个结点后面没有结点可删除。若不是最后一个结点,我们首先让地址为pos的结点指向待删除结点的后一个结点,然后将待删除结点释放即可。

// 删除pos之后结点
void SListEraseAfter(SListNode *pos) {assert(pos);if (pos->next == NULL) {return;} else {// 记录pos的后一个结点SListNode *nextnode = pos->next;pos->next = nextnode->next;free(nextnode);}
}

删除给定位置的结点

要删除给定位置的结点,我们首先要判断该结点是否为第一个结点,若是,则操作与头删相同;若不是,我们就需要先找到待删除结点的前一个结点,然后让其指向待删除结点的后一个结点,最后才能释放待删除的结点。

// 删除pos位置结点
void SListErase(SListNode **pplist, SListNode *pos) {assert(pos);assert(*pplist);// 如果删除pos位置等于头结点,就相当于头删,不是的话就正常删除if (pos == *pplist) {SListPopFront(pplist);} else {SListNode *prev = *pplist;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);}
}

查找数据

查找数据相对于前面的来说就非常简单了,我们只需要遍历一遍链表,在遍历的过程中,若找到了目标结点,则返回结点的地址;若遍历结束也没有找到目标结点,则直接返回空指针。

// 单链表查找
SListNode *SListFind(SListNode *plist, SLDataType x) {SListNode *cur = plist;while (cur) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}

修改数据

//修改数据
void SListModify(SListNode* pos, SLDataType x){pos->data = x;//将结点的数据改为目标数据
}

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

**无头单向非循环链表:**结构简单,一般不会用来存储数据。实际上更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
**带头双向循环链表:**结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外,这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。

初始化链表

首先,我们还是需要先定义一个结点类型,与单向链表相比,双向链表的结点类型中需要多出一个前驱指针,用于指向前面一个结点,实现双向。

typedef int LTDataType;//存储的数据类型typedef struct ListNode {LTDataType data;      //数据域struct ListNode *prev;//前驱指针struct ListNode *next;//后继指针
} ListNode;

然后我们需要一个初始化函数,对双向链表进行初始化,在初始化的过程中,需要申请一个头结点,头结点的前驱和后继指针都指向自己,使得链表一开始便满足循环。

在这里插入图片描述

//创建一个新结点
ListNode *BuyListNode(LTDataType x) {ListNode *node = (ListNode *) malloc(sizeof(ListNode));if (node == NULL) {printf("malloc fail\n");exit(-1);}node->data = x;//新结点赋值node->prev = NULL;node->next = NULL;return node;//返回新结点
}//初始化链表
ListNode *ListInit() {ListNode *phead = BuyListNode(-1);//申请一个头结点,头结点不存储有效数据//起始时只有头结点,让它的前驱和后继都指向自己phead->prev = phead;phead->next = phead;return phead;//返回头结点
}

销毁链表

销毁链表,从头结点的后一个结点处开始向后遍历并释放结点,直到遍历到头结点时,停止遍历并将头结点也释放掉。

//销毁链表
void ListDestroy(ListNode *phead) {assert(phead);ListNode *cur = phead->next;//从头结点后一个结点开始释放空间ListNode *next = cur->next; //记录cur的后一个结点位置while (cur != phead) {free(cur);cur = next;next = next->next;}free(phead);//释放头结点
}

打印双向链表

打印双向链表时也是从头结点的后一个结点处开始向后遍历并打印,直到遍历到头结点处时便停止遍历和打印(头结点数据不打印)。

//打印双向链表
void ListPrint(ListNode *phead) {assert(phead);ListNode *cur = phead->next;//从头结点的后一个结点开始打印while (cur != phead)        //当cur指针指向头结点时,说明链表以打印完毕{printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

查找元素

给定一个值,在链表中寻找与该值相同的结点,若找到了,则返回结点地址;若没有找到,则返回空指针(NULL)。

//查找元素
ListNode *ListFind(ListNode *phead, LTDataType x) {assert(phead);ListNode *cur = phead->next;//从头结点的后一个结点开始查找while (cur != phead)        //当cur指向头结点时,说明链表已遍历完毕{if (cur->data == x) {return cur;//返回目标结点的地址}cur = cur->next;}return NULL;//没有找到目标结点
}

增加结点

头插

头插,即申请一个新结点,将新结点插入在头结点和头结点的后一个结点之间即可。

在这里插入图片描述

//头插
void ListPushFront(ListNode *phead, LTDataType x) {assert(phead);ListNode *newnode = BuyListNode(x);//申请一个结点,数据域赋值为xListNode *nextnode = phead->next;  //记录头结点的后一个结点位置//建立新结点与头结点之间的双向关系phead->next = newnode;newnode->prev = phead;//建立新结点与front结点之间的双向关系newnode->next = nextnode;nextnode->prev = newnode;
}

尾插

尾插,申请一个新结点,将新结点插入到头结点和头结点的前一个结点之间即可。因为链表是循环的,头结点的前驱指针直接指向最后一个结点,所以我们不必遍历链表找尾。

在这里插入图片描述

//尾插
void ListPushBack(ListNode *phead, LTDataType x) {assert(phead);ListNode *newnode = BuyListNode(x);//申请一个结点,数据域赋值为xListNode *tail = phead->prev;      //记录头结点的前一个结点的位置//建立新结点与头结点之间的双向关系newnode->next = phead;phead->prev = newnode;//建立新结点与tail结点之间的双向关系tail->next = newnode;newnode->prev = tail;
}

在指定位置插入结点

在指定位置插入结点,准确来说,是在指定位置之前插入一个结点。我们只需申请一个新结点插入到指定位置结点和其前一个结点之间即可。

//在指定位置插入结点
void ListInsert(ListNode *pos, LTDataType x) {assert(pos);ListNode *before = pos->prev;      //记录pos指向结点的前一个结点ListNode *newnode = BuyListNode(x);//申请一个结点,数据域赋值为x//建立新结点与before结点之间的双向关系before->next = newnode;newnode->prev = before;//建立新结点与pos指向结点之间的双向关系newnode->next = pos;pos->prev = newnode;
}

删除结点

头删

头删,即释放头结点的后一个结点,并建立头结点与被删除结点的后一个结点之间的双向关系即可。

在这里插入图片描述

//头删
void ListPopFront(ListNode *phead) {assert(phead);assert(phead->next != phead);ListNode *cur = phead->next;   //记录头结点的后一个结点ListNode *nextnode = cur->next;//记录cur结点的后一个结点//建立头结点与nextnode结点之间的双向关系phead->next = nextnode;nextnode->prev = phead;free(cur);//释放cur结点
}

尾删

尾删,即释放最后一个结点,并建立头结点和被删除结点的前一个结点之间的双向关系即可。

在这里插入图片描述

//尾删
void ListPopBack(ListNode *phead) {assert(phead);assert(phead->next != phead);ListNode *tail = phead->prev;  //记录头结点的前一个结点ListNode *newtail = tail->prev;//记录tail结点的前一个结点//建立头结点与newtail结点之间的双向关系newtail->next = phead;phead->prev = newtail;free(tail);//释放tail结点
}

删除指定位置结点

删除指定位置结点,释放掉目标结点后,建立该结点前一个结点和后一个结点之间的双向关系即可。

//删除指定位置结点
void ListErase(ListNode *pos) {assert(pos);ListNode *before = pos->prev;//记录pos指向结点的前一个结点ListNode *after = pos->next; //记录pos指向结点的后一个结点//建立before结点与after结点之间的双向关系before->next = after;after->prev = before;free(pos);//释放pos指向的结点
}

链表判空

链表判空,即判断头结点的前驱或是后驱指向的是否是自己即可。

//链表判空
bool ListEmpty(ListNode *phead) {assert(phead);return phead->next == phead;//当链表中只有头结点时为空
}

获取链表中的元素个数

获取链表中的元素个数,即遍历一遍链表,统计结点的个数(头结点不计入)并返回即可。

//获取链表中的元素个数
int ListSize(ListNode *phead) {assert(phead);int count = 0;              //记录元素个数ListNode *cur = phead->next;//从头结点的后一个结点开始遍历while (cur != phead)        //当cur指向头结点时,遍历完毕,头结点不计入总元素个数{count++;cur = cur->next;}return count;//返回元素个数
}

链表判空

链表判空,即判断头结点的前驱或是后驱指向的是否是自己即可。

//链表判空
bool ListEmpty(ListNode *phead) {assert(phead);return phead->next == phead;//当链表中只有头结点时为空
}

获取链表中的元素个数

获取链表中的元素个数,即遍历一遍链表,统计结点的个数(头结点不计入)并返回即可。

//获取链表中的元素个数
int ListSize(ListNode *phead) {assert(phead);int count = 0;              //记录元素个数ListNode *cur = phead->next;//从头结点的后一个结点开始遍历while (cur != phead)        //当cur指向头结点时,遍历完毕,头结点不计入总元素个数{count++;cur = cur->next;}return count;//返回元素个数
}

5.顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持O(N)
任意位置插入删除元素可能需要挪动元素,效率低O(N)只需要修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C# void 关键字学习

C#中void关键字是System.Void的别名; 可以将 void 用作方法(或本地函数)的返回类型来指定该方法不返回值; 如果C#方法中没有参数,则不能将void用作参数;这是与C语言不同的,C语言有…

rk3568 SDK的buildroot添加package

开发源码工程 首先进入<SDK>/app 目录下&#xff0c;在该目录下创建一个名为“mypackage”的文件夹。 在 mypackage 目录下创建一个.c 源文件 main.c&#xff0c;以及一个 Makefile 文件。 大家可以自己在 main.c 源文件中编写一个简单的测试代码&#xff0c;譬如打印一…

设计模式-建造者(生成器)模式

文章目录 简介建造者模式的核心概念产品&#xff08;Product&#xff09;建造者&#xff08;Builder&#xff09;指挥者&#xff08;Director&#xff09;建造者模式与其他设计模式的关系工厂模式和建造者模式uml对比 建造者模式的实现步骤建造者模式的应用场景spring中应用 建…

RabbtiMQ的安装与使用

一、安装Erlang与Rabbitmq 安装教程本教程是在centos8下试验的&#xff0c;其实linux系统的都差不多RabbitMQ官方&#xff1a;Messaging that just works — RabbitMQRabbitMQ是开源AMQP实现&#xff0c;服务器端用Erlang语言编写&#xff0c;Python、Ruby、 NET、Java、JMS、c…

软件架构之前后端分离架构服务器端高并发演进之路

软件架构之前后端分离架构&服务器端高并发演进之路 前后端分离架构从业务角度从质量属性从性能角度 服务器端关于不同并发量的演进之路1. 单体架构2. 第一次演进&#xff1a;应用服务器和数据库服务器分开部署3. 第二次演进&#xff1a;引入本地缓存和分部署缓存4. 第三次演…

录屏没有声音?录制声音,3招教你搞定

在录制屏幕内容时&#xff0c;声音是不可或缺的要素之一&#xff0c;可以有效地增强录制视频的表现力和传达效果。然而&#xff0c;有时候可能会遇到录屏没有声音的情况&#xff0c;这可能会让录制的视频失去一部分重要信息。本文将为您介绍录屏录声音的3种方法&#xff0c;帮助…

nios里面打开eclipse遇到Unresolved inclusion: “system.h“等问题

问题&#xff1a;在Nios中打开软核部分代码时&#xff0c;遇到一堆Unresolved inclusion: "system.h"等问题报错 原因&#xff1a;bsp文件和软核没关联&#xff0c;导致找不到头文件地址&#xff0c;关联一下就好 解决步骤&#xff1a; 右键bsp文件&#xff0c;点击…

肖sir__设计测试用例方法之等价类02_(黑盒测试)

设计测试用例方法之等价类02_&#xff08;黑盒测试&#xff09; 一、掌握常用的设计方法: 黑盒测试方法&#xff1a;等价类、边界值&#xff0c;状态迁移法、场景法、判定表、因果图、正交表&#xff0c;&#xff08;7种&#xff09; 经验测试方法&#xff1a;错误推测法、异常…

[数据集][目标检测]裸土识别裸土未覆盖目标检测数据集VOC格式857张2类别

数据集格式&#xff1a;Pascal VOC格式(不包含分割路径的txt文件和yolo格式的txt文件&#xff0c;仅仅包含jpg图片和对应的xml) 图片数量(jpg文件个数)&#xff1a;857 标注数量(xml文件个数)&#xff1a;857 标注类别数&#xff1a;2 标注类别名称:["luotu","n…

数学建模:相关性分析

&#x1f506; 文章首发于我的个人博客&#xff1a;欢迎大佬们来逛逛 数学建模&#xff1a;相关性分析 文章目录 数学建模&#xff1a;相关性分析相关性分析两变量的相关分析PearsonSpearmanKendall tua-b 双变量关系强度测量的指标相关系数的性质代码实现example偏相关分析 相…

尚硅谷SpringMVC (9-13)

九、HttpMessageConverter HttpMessageConverter &#xff0c;报文信息转换器&#xff0c;将请求报文转换为 Java 对象&#xff0c;或将 Java 对象转换为响应报文 HttpMessageConverter提供了两个注解和两个类型&#xff1a; RequestBody &#xff0c; ResponseBody &#xff…

使用Docker安装和部署RabbitMQ

&#x1f680; 1 拉取RabbitMQ Docker镜像 首先&#xff0c;使用Docker命令从Docker Hub拉取RabbitMQ官方镜像。打开终端并运行以下命令&#xff1a; docker pull rabbitmq&#x1f680; 2 创建RabbitMQ容器 一旦镜像下载完成&#xff0c;使用以下命令创建RabbitMQ容器&…

linux复习笔记01(小滴课堂)

1.安装CentOs7系统 点击下一步在自定义硬件中&#xff1a; 我们可以删除我们不使用的&#xff0c;后续如果需要再加上即可。 然后我们就可以开启这台虚拟机了。 我们可以进行下载cetos7. 这里选择简体中文就可以。 时间的设置。 可以开启下网络。 在这里选择设置root密码&#…

高忆管理:证券账户国债逆回购怎么操作?

国债逆回购的本质就是一种短期贷款&#xff0c;个人经过国债回购商场把自己的资金借出去&#xff0c;取得固定的利息收益&#xff0c;那么&#xff0c;证券账户国债逆回购怎样操作&#xff1f;怎样在股票账户上买国债逆回购&#xff1f;下面高忆管理为我们准备了相关内容&#…

嵌入式面试笔试刷题(day14)

文章目录 前言一、进程控制块1.PCB控制块的作用2.PCB的存储位置 二、进程的三级映射三、return , exit, pthread_exit四、pthread_join作用五、互斥锁和信号量的区别六、怎么判断链表是否有环总结 前言 本篇文章继续我们的刷题之路。 一、进程控制块 这里只讲解进程的PCB控制…

内网隧道代理技术(二十)之 CS使用HTTP代理上线不出网机器

CS使用HTTP代理上线不出网机器 CS工具自带上线不出网机器 如图A区域存在一台中转机器,这台机器可以出网,这种是最常见的情况。我们在渗透测试的过程中经常是拿下一台边缘机器,其有多块网卡,边缘机器可以访问内网机器,内网机器都不出网。这种情况下拿这个边缘机器做中转,…

Laravel 表单验证器的常用的2种使用方法

1、使用控制器的 validate 方法进行参数验证 场景一&#xff1a;前后端未分离 /*** 保存一篇新的博客文章。** param Request $request* return Response*/ public function store(Request $request) {$this->validate($request, [title > required|unique:posts|max:2…

基于神经网络结合紫外差分光谱的二氧化硫浓度定量预测

基于神经网络结合紫外差分光谱的二氧化硫浓度定量预测 前言一、代码运行1. 解压数据2. 导包3. 读取数据4. 构建网络5. 设置优化器6. 模型训练7. 可视化loss8. 模型验证 二、结果展示三、总结作者简介 前言 二氧化硫&#xff08;SO2&#xff09;是一种常见的环境污染物&#xff…

电梯五方对讲接口说明 Sip五方对讲使用说明

1.2/4线接线模块输出接口;接4方对讲设备:12V&#xff0c;2/4线接线模块供电输入 -:GND&#xff0c;接地 R二/四线R Li二四线L 2.RS-485接口:预留援口&#xff0c;可接读卡器、楼层控制器、探头&#xff0c;需要软件额外开发实现。 3.短路输出接口2:对应短路输入接口&#x…

【C++】DICOM医学影像工作站PACS源码

PACS即影像存档与传输系统&#xff0c;是医学影像、数字化图像技术、计算机技术和网络通讯技术相结合的产物&#xff0c;是处理各种医学影像信息的采集、存储、报告、输出、管理、查询的计算机应用程序。 PACS是基于DICOM标准的医学影像管理系统&#xff0c;其模块覆盖了从影像…