【数据结构初阶】单链表

Ne0inhk

— 8 min read
【数据结构初阶】单链表
在这里插入图片描述

文章目录

单链表

1. 链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。

在这里插入图片描述

链表的结构跟火车厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？
最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。
在链表⾥，每节“⻋厢”是什么样的呢？

在这里插入图片描述

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点”
节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来保存下⼀个节点的位置？
链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：

structSListNode{int data;//节点数据 structSListNode* next;//指针变量⽤保存下⼀个节点的地址 };

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数
据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。
给定的链表结构中，如何实现节点从头到尾的打印？

在这里插入图片描述

2. 单链表的实现

1.定义结点

typedefint SLTDataType;typedefstructSListNode//s single{ SLTDataType data;structSListNode* next;}SLTNode;

2.打印数据

voidSLTPrint(SLTNode* phead){ SLTNode* pcur = phead;while(pcur)//pcur!=NULL{printf("%d->", pcur->data); pcur = pcur->next;}printf("NULL\n");}

3.申请新的节点

SLTNode*SLTBuyNode(SLTDataType x){ SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if(newnode ==NULL){perror("malloc fail!");exit(1);}//申请成功 newnode->data = x; newnode->next =NULL;return newnode;}

4.尾插

voidSLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);//pphead不能为空 不能对空指针解引用//空链表和非空链表 SLTNode* newnode =SLTBuyNode(x);if(*pphead ==NULL){*pphead = newnode;}else{//找尾 SLTNode* ptail =*pphead;while(ptail->next){ ptail = ptail->next;}//ptail指向尾节点 ptail->next = newnode;}}

5.头插

voidSLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead); SLTNode* newnode =SLTBuyNode(x); newnode->next =*pphead;*pphead = newnode;}

6.尾删

//尾删voidSLTPopBack(SLTNode** pphead){//链表不能为空assert(pphead&&*pphead);if((*pphead)->next ==NULL)//->的优先级高于* 所以要加括号{free(*pphead);*pphead =NULL;}else{//找尾 SLTNode* prev =*pphead;//要删除的前一个 SLTNode* ptail =*pphead;//要删除的while(ptail->next){ prev = ptail; ptail = ptail->next;}//prev ptaifree(ptail); ptail =NULL; prev->next =NULL;}}

7.头删

voidSLTPopFront(SLTNode** pphead){//链表不能为空assert(pphead &&*pphead); SLTNode* next=(*pphead)->next;//记得加括号free(*pphead);*pphead = next;}

8.查找

SLTNode*SLTFind(SLTNode* phead, SLTDataType x){ SLTNode* pcur = phead;while(pcur)//pcur != NULL{if(pcur->data == x){return pcur;} pcur = pcur->next;}//pcur == NULLreturnNULL;}

9.指点位置之前插入

voidSLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead &&*pphead);//若*pphead为空 则pos也为空assert(pos); SLTNode* newnode =SLTBuyNode(x);if(pos ==*pphead){SLTPushFront(pphead,x);}else{ SLTNode* prev =*pphead;//找pos前一个节点while(prev->next != pos){ prev = prev->next;}//prev newnode pos prev->next = newnode; newnode->next = pos;}}

10.指定位置后插入

voidSLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos); SLTNode* newnode =SLTBuyNode(x); newnode->next = pos->next;//为什么顺序不能交换 pos->next = newnode;}

11.指定位置前删除

voidSLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead &&*pphead); SLTNode* prev =*pphead;//找pos前一个节点if(pos ==*pphead){//头删SLTPopFront(pphead);}while(prev->next != pos){ prev = prev->next;}//prev pos pos->next prev->next = pos->next;free(pos); pos =NULL;}

12.指定位置后删除

voidSLTEraseAfter(SLTNode* pos){assert(pos&&pos->next); SLTNode* del = pos->next; pos->next = pos->next->next;free(del); del->next =NULL;}

13.链表的销毁

voidSLTDestroy(SLTNode** pphead){assert(pphead); SLTNode* pcur =*pphead;while(pcur){ SLTNode* next =(*pphead)->next;free(pcur); pcur = next;}//pcur 为空*pphead =NULL;}

3.程序源码

共分三个文件

SLTist.h函数的声明

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>//定义节点结构//数据+指向下一个节点的指针typedefint SLTDataType;typedefstructSListNode//s single{ SLTDataType data;structSListNode* next;}SLTNode;voidSLTPrint(SLTNode* phead);//尾插voidSLTPushBack(SLTNode** pphead, SLTDataType x);//头插voidSLTPushFront(SLTNode** pphead, SLTDataType x);//尾删voidSLTPopBack(SLTNode** pphead);//头删voidSLTPopFront(SLTNode** pphead);//查找 SLTNode*SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入voidSLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在头节点前插入，头节点可能改变//在指定位置之后插入数据voidSLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点voidSLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点voidSLTEraseAfter(SLTNode* pos);//销毁链表voidSLTDestroy(SLTNode** pphead);

SList.c函数的实现

#define_CRT_SECURE_NO_WARNINGS#include"SList.h"voidSLTPrint(SLTNode* phead){ SLTNode* pcur = phead;while(pcur)//pcur!=NULL{printf("%d->", pcur->data); pcur = pcur->next;}printf("NULL\n");} SLTNode*SLTBuyNode(SLTDataType x){ SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if(newnode ==NULL){perror("malloc fail!");exit(1);}//申请成功 newnode->data = x; newnode->next =NULL;return newnode;}//尾插voidSLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);//pphead不能为空 不能对空指针解引用//空链表和非空链表 SLTNode* newnode =SLTBuyNode(x);if(*pphead ==NULL){*pphead = newnode;}else{//找尾 SLTNode* ptail =*pphead;while(ptail->next){ ptail = ptail->next;}//ptail指向尾节点 ptail->next = newnode;}}voidSLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead); SLTNode* newnode =SLTBuyNode(x); newnode->next =*pphead;*pphead = newnode;}//尾删voidSLTPopBack(SLTNode** pphead){//链表不能为空assert(pphead&&*pphead);if((*pphead)->next ==NULL)//->的优先级高于* 所以要加括号{free(*pphead);*pphead =NULL;}else{//找尾 SLTNode* prev =*pphead;//要删除的前一个 SLTNode* ptail =*pphead;//要删除的while(ptail->next){ prev = ptail; ptail = ptail->next;}//prev ptaifree(ptail); ptail =NULL; prev->next =NULL;}}//头删voidSLTPopFront(SLTNode** pphead){//链表不能为空assert(pphead &&*pphead); SLTNode* next=(*pphead)->next;//记得加括号free(*pphead);*pphead = next;}//查找 SLTNode*SLTFind(SLTNode* phead, SLTDataType x){ SLTNode* pcur = phead;while(pcur)//pcur != NULL{if(pcur->data == x){return pcur;} pcur = pcur->next;}//pcur == NULLreturnNULL;}voidSLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead &&*pphead);//若*pphead为空 则pos也为空assert(pos); SLTNode* newnode =SLTBuyNode(x);if(pos ==*pphead){SLTPushFront(pphead,x);}else{ SLTNode* prev =*pphead;//找pos前一个节点while(prev->next != pos){ prev = prev->next;}//prev newnode pos prev->next = newnode; newnode->next = pos;}}voidSLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos); SLTNode* newnode =SLTBuyNode(x); newnode->next = pos->next;//为什么顺序不能交换 pos->next = newnode;}voidSLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead &&*pphead); SLTNode* prev =*pphead;//找pos前一个节点if(pos ==*pphead){//头删SLTPopFront(pphead);}while(prev->next != pos){ prev = prev->next;}//prev pos pos->next prev->next = pos->next;free(pos); pos =NULL;}voidSLTEraseAfter(SLTNode* pos){assert(pos&&pos->next); SLTNode* del = pos->next; pos->next = pos->next->next;free(del); del->next =NULL;}voidSLTDestroy(SLTNode** pphead){assert(pphead); SLTNode* pcur =*pphead;while(pcur){ SLTNode* next =(*pphead)->next;free(pcur); pcur = next;}//pcur 为空*pphead =NULL;}

test.c用来测试

#define_CRT_SECURE_NO_WARNINGS#include"SList.h"voidSListTest01(){//链表是由一个一个的节点组成 SLTNode* node1 =(SLTNode*)malloc(sizeof(SLTNode)); node1->data =1; SLTNode* node2 =(SLTNode*)malloc(sizeof(SLTNode)); node2->data =2; SLTNode* node3 =(SLTNode*)malloc(sizeof(SLTNode)); node3->data =3; SLTNode* node4 =(SLTNode*)malloc(sizeof(SLTNode)); node4->data =4;//将四个节点连接起来 node1->next = node2; node2->next = node3; node3->next = node4; node4->next =NULL;//调用链表的打印 SLTNode* plist = node1;SLTPrint(plist);}voidTest02(){ SLTNode* plist =NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);SLTPrint(plist);//SLTPushFront(&plist, 5);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist); SLTNode* find =SLTFind(plist,3);/*if (find == NULL) { printf("没有找到\n"); } else { printf("找到了！\n"); }*///SLTInsert(&plist, find,11);SLTInsertAfter(find,9);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTEraseAfter(find);SLTDestroy(&plist);SLTPrint(plist);}intmain(){//SListTest01();Test02();return0;}

Read more

数据结构：顺序表讲解（1）

数据结构：顺序表讲解（1）

目录 前言  一、顺序表介绍 介绍： 1.线性表 线性表：逻辑结构的统称 2.顺序表概念与结构 二、顺序表分类 介绍： 1.静态顺序表 2.动态顺序表 核心特点 三、动态顺序表的实现 讲解 1.初始化： SLinit 2.顺序表的尾插 3.顺序表的头插 4.顺序表的尾删 5.顺序表的头删 四、尾插，头插，尾删，头删时间复杂度对比： 1.尾插入： 2.头插入： 3.尾删： 4.头删：    总结 前言    本篇文章将讲解顺序表介绍，顺序表分类，

By Ne0inhk
【数据结构入坑指南（二.1）】--《数据结构与算法精讲：从数组到顺序表，如何让数据管理变得强大而优雅？》​​

【数据结构入坑指南（二.1）】--《数据结构与算法精讲：从数组到顺序表，如何让数据管理变得强大而优雅？》​​

🔥@晨非辰Tong：个人主页  👀专栏：《C语言》、《数据结构与算法》 💪学习阶段：C语言、数据结构与算法初学者 ⏳“人理解迭代，神理解递归。” 引言：掌握了复杂度的衡量标尺，现在，让我们用它来审视第一个真正意义上的数据结构——顺序表。本文将亲手实现动态顺序表，并分析其各项操作的效率，为下一篇博客对顺序表的继续分享打通前路。 目录 一、线性表 二、顺序表 2.1  什么是顺序表？ 2.2  顺序表类别 2.2.1  静态顺序表 2.2.2  动态顺序表 三、动态顺序表的实现（三文件协同） SeqList.h SeqList.c test.c（测试文件） 四、动态顺序表的应用（初）

By Ne0inhk
生物启发算法：模仿人类司机的认知机制

生物启发算法：模仿人类司机的认知机制

生物启发算法：模仿人类司机的认知机制 * 前言 * 一、生物启发算法的基础概念 * 1.1 什么是生物启发算法 * 1.2 生物启发算法的特点 * 1.3 常见的生物启发算法 * 二、人类司机的认知机制 * 2.1 感知阶段 * 2.2 决策阶段 * 2.3 执行阶段 * 三、模仿人类司机认知机制的生物启发算法设计 * 3.1 基于感知阶段的算法模块设计 * 3.2 基于决策阶段的算法模块设计 * 3.3 基于执行阶段的算法模块设计 * 四、算法的实现与验证 * 4.1 开发环境与工具 * 4.2 算法的代码实现 * 4.3 算法的验证方法 * 4.4 验证结果分析

By Ne0inhk
21届智能车雁过留痕备战指南｜龙邱科技STC+神眼摄像头处理 高效搜线算法思路分享

21届智能车雁过留痕备战指南｜龙邱科技STC+神眼摄像头处理 高效搜线算法思路分享

今年STC单片机首次增设摄像头组别，相信不少备战的同学想要知道这颗新U是否能够快速上手并能够像传统摄像头组别一样，高效完成图像处理，提高车模控制系统上限。 其中最突出的痛点的是：有同学搭建完核心算法组合后，可能感觉到略微卡顿或系统延迟，影响车模调试上限，我们第一次搭建完经过测试单帧处理耗时高达20多ms，这导致车辆运行稳定性和反应速度受限、甚至可能有冲出赛道的情况发生，导致调试陷入瓶颈，提速困难，短时间内难以找到有效突破方向。 针对这一高频痛点，我们结合备战同学的实际调试场景，经过反复测试、迭代优化，整理出一套实用性极强的帧率优化思路，实测验证有效，优化后单帧处理耗时可稳定降至9-11ms，彻底解决卡顿难题，这里将图像处理和以西优化思路分享给大家，希望能够帮助到更多的同学！ 实测数据对比，直观呈现优化效果 图像处理方案单帧采集+处理耗时未优化（采集+处理）20ms-25ms（能感觉到慢，上限较低）优化后（采集+处理）9ms-11ms（流畅稳定，提高了上限） 同学们遇到的卡顿问题，核心症结主要集中在两点：一是内存资源不足，二是算法计算耗时过长。在拆解具体优化方法前，我

By Ne0inhk