数据结构-单链表
单链表
概念与结构
概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
逻辑结构：线性
物理结构（存储结构）：不一定是线性的
链表就类似一个火车，车头是哨兵位（可有可无），车厢是节点
- 将火车里的某节车厢去掉或加上，不会影响其他车厢，每节车厢都是独立存在的。
在链表⾥，每节“车厢”是什么样的呢？ \color{red}{在链表⾥，每节“车厢”是什么样的呢？} 在链表⾥，每节“车厢”是什么样的呢？
结点
与顺序表不同的是，链表⾥的每节"车厢"都是独立申请下来的空间，我们称之为“结点/结点结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
链表的性质
1、链式机构在逻辑上是连续的，在物理结构上不一定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：
假设当前保存的结点为整型：
structSListNode{int data;//结点数据structSListNode* next;//指针变量⽤保存下⼀个结点的地址};当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存 \color{green}{当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存} 当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存
下⼀个结点的地址（当下⼀个结点为空时保存的地址为空） \color{green}{下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）} 下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）
当我们想要从第⼀个结点走到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。 \color{green}{当我们想要从第⼀个结点走到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。} 当我们想要从第⼀个结点走到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。
链表的打印
实现单链表
头文件
- SList.h
#include<stdio.h>#include<stdlib.h>#include<assert.h>//链表的结构typedefint SLTDataType;typedefstructSListNode{ SLTDataType data;structSListNode* next;//指向下一个节点的地址}SLTNode;//typedef struct SListNode 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);//销毁链表voidSListDestroy(SLTNode** pphead);源文件
- SList.c
单链表的打印
voidSLTPrint(SLTNode * phead){ SLTNode* pcur = phead;while(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);//申请新节点 SLTNode* newnode =SLTBuyNode(x);//链表为空if(*pphead ==NULL){*pphead = newnode;}else{ SLTNode* ptail =*pphead;while(ptail->next !=NULL){ ptail = ptail->next;}//找到了尾结点 ptail newnode ptail->next = newnode;}}传址调用，SLTNode** pphead，不然无法修改SLTNode* phead结构体指针需要做出特殊判断，当链表为空的时候
头插
//头插voidSLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead); SLTNode* newnode =SLTBuyNode(x);//newnode *pphead newnode->next =*pphead;*pphead = newnode;}尾删
//尾删voidSLTPopBack(SLTNode** pphead){//链表为空不能删除assert(pphead &&*pphead);//链表只有一个节点的情况if((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}else{ SLTNode* prev =NULL; SLTNode* ptail =*pphead;while(ptail->next){ prev = ptail; ptail = ptail->next;}//prev ptail prev->next =NULL;free(ptail); ptail =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){if(pcur->data == x){return pcur;} pcur = pcur->next;}//未找到returnNULL;}不需要传二级指针了
在指定位置之前插入数据
//在指定位置之前插⼊数据voidSLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead && pos); SLTNode* newnode =SLTBuyNode(x);//pos指向头结点if(pos ==*pphead){//头插SLTPushFront(pphead, x);}else{//找pos的前一个节点 SLTNode* prev =*pphead;while(prev->next != pos){ prev = prev->next;}//prev newnode pos prev->next = newnode; newnode->next = pos;}}pos不能为空指针特殊情况，pos指向头结点
在指定位置之后插入数据
//在指定位置之后插入数据voidSLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos); SLTNode* newnode =SLTBuyNode(x);//pos newnode pos->next newnode->next = pos->next; pos->next = newnode;}删除pos结点
//删除pos结点voidSLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && pos);//pos刚好就是头结点——头删if(pos ==*pphead){SLTPopFront(pphead);}else{ SLTNode* prev =*pphead;while(prev->next != pos){ prev = prev->next;}//prev pos pos->next prev->next = pos->next;free(pos); pos =NULL;}}pos不能为空指针特殊情况，pos刚好就是头结点—头删
删除pos之后的结点
//删除pos之后的结点voidSLTEraseAfter(SLTNode* pos){assert(pos && pos->next);//pos del del->next SLTNode* del = pos->next; pos->next = del->next;free(del); del =NULL;}销毁链表
//销毁链表voidSListDestroy(SLTNode** pphead){assert(pphead); SLTNode* pcur =*pphead;while(pcur){ SLTNode* next = pcur->next;free(pcur); pcur = next;}*pphead =NULL;}链表的分类
链表的结构⾮常多样，以下情况组合起来就有 8 种（ 2 x 2 x 2 ）链表结构 \color{green}{链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构} 链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构
- 链表说明：
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表
1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
代码地址
感谢大佬们三连，你的鼓励就是对我创作的激励！！！ \color{purple}{感谢大佬们三连，你的鼓励就是对我创作的激励！！！} 感谢大佬们三连，你的鼓励就是对我创作的激励！！！
