1.单链表
1.1 概念与结构
概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。
1.1.1 结点
与顺序表不同的是，链表⾥的每节"车厢"都是独立申请下来的空间，我们称之为“结点”
结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。
图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望
plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012bc00。
链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
1.1.2 链表的性质
1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
1.1.3先了解一下重难点
2.单链表的实现以及增删查改
同顺序表一样，还是建立三个文件，slist.c ,slist.h ,test.c
话不多说，上代码！
这是.h文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int sltype;
//定义链表结构
typedef struct SListnode
{sltype data;struct SListnode* next;//这里应该是SL
}SLTNode;void slprint(SLTNode* phead);
void sltpushback(SLTNode** pphead, sltype x); //尾插
void sltpushfront(SLTNode** pphead, sltype x); //头插
void sltpopfront(SLTNode** pphead); //头删
void sltpopback(SLTNode** pphead); //尾删
SLTNode* sltfind(SLTNode* phead, sltype x); //查找
void sltinsert(SLTNode** pphead, SLTNode* pos, sltype x); //在指定位置之前插⼊数据
void sltinsertafter(SLTNode* pos, sltype x); //在指定位置之后插⼊数据
void slterase(SLTNode** pphead, SLTNode* pos); //删除pos结点
void slteraseafter(SLTNode* pose); //删除Pos之后的结点
void sltdestroy(SLTNode** pphead); //销毁链表这是slist.c文件
#include"slist.h"
void slprint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ", pcur->data); //可以简单理解为pcur就是Phead的代理人，一般不用幕后老 板去执行任务pcur = pcur->next; //链表是相连的，打完这个数据就要去打下一个了，把地址传 过去}printf("NULL\n"); //一个完整的链表是一点都不能少的
}
//创建结点
SLTNode* sltbuynode(sltype x)
{//开辟空间SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));assert(node);node->data = x; //由于node是我们前面开辟的链表结构指针变量，故可以用-> 访问node->next = NULL;return node;
}
//尾插
void sltpushback(SLTNode** pphead, sltype x)
{assert(pphead);SLTNode* newnode = sltbuynode(x); //先把要尾插的小结点做好，方便之后链接//如果链表为空的话if (*pphead == NULL){*pphead = newnode;}//如果原链表不为空else{SLTNode* ptail = *pphead; //指挥权交给ptail，让ptail去找链表的结尾所在while (ptail->next != NULL){ptail = ptail->next; //不为空就不是尾巴，往后找}//此刻ptail已经找到链表的尾部了，准备链接ptail->next = newnode;}
}
//头插
void sltpushfront(SLTNode** pphead, sltype x)
{assert(pphead);SLTNode* newnode = sltbuynode(x);newnode->next = *pphead;*pphead = newnode; //别忘了将插入的结点设置为头结点
}
//头删
void sltpopfront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next; //->优先级高于* ；；此举是将未来的“头”取出先保存上free(*pphead);*pphead = next; //第一个结点已经删了，先将第二个结点当做“头”
}
//尾删
void sltpopback(SLTNode** pphead)
{//由于在尾删过程中，涉及关于对NULL的设定，因此我们要讨论一下要删的链表是否只有一个结点assert(pphead && *pphead);if ((*pphead)->next == NULL) //->优先级高于*{free(*pphead);*pphead = NULL;}else //有多个结点{//由于我们要删最后一个结点，故需要对最后一个结点的next指针做NULL处理，所以我们要去锁定其 位置SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}//出循环时已经找到末尾了free(ptail);ptail = NULL;prev->next = NULL;}
}
//查找
SLTNode* sltfind(SLTNode* phead, sltype x)
{SLTNode* pcur = phead;while (pcur != NULL){if (pcur->data == x) //让pcur逐一遍历链表 这里应该是=={return pcur;}pcur = pcur->next;}return NULL;
}
//在指定位置之前插入数据
void sltinsert(SLTNode** pphead, SLTNode* pos, sltype x)
{assert(pphead && pos);//当pos就是头结点时，相当于头插if (pos == *pphead){sltpushfront(pphead, x);}else{SLTNode* newnode = sltbuynode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}
//在指定位置之后插入数据
void sltinsertafter(SLTNode* pos, sltype x)
{assert(pos);SLTNode* newnode = sltbuynode(x);newnode->next = pos->next;pos->next = newnode;
}
//删除pos之后的结点
void slteraseafter(SLTNode* pose)
{assert(pose && pose->next); SLTNode* del = pose->next; //要删除的结点pose->next = del->next; //重新链接free(del);del = NULL;
}
//删除Pose结点
void slterase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);//由于删除Pose结点的过程中，会对pos前后的“链子”都进行修整，故要讨论是否为头结点if (pos == *pphead){//是就头删sltpopfront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos) //找pos{prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
//销毁链表
void sltdestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next; //从头到尾逐步释放free(pcur);pcur = next;}*pphead = NULL;
}
最后是test.c
#include"slist.h"
void test()
{SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));//往里头传数据node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node5->data = 5;//将各个节点连接起来node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = NULL;SLTNode* plist = node1; //准备打印了，plist相当于燃放鞭炮的导火线slprint(plist);
}
void test01() {//尾插SLTNode* plist = NULL;sltpushback(&plist, 1);slprint(plist);sltpushback(&plist, 2);slprint(plist);sltpushback(&plist, 3);slprint(plist);sltpushback(&plist, 4);slprint(plist);//头插sltpushfront(&plist, 6);slprint(plist);sltpushfront(&plist, 5);slprint(plist);sltpushfront(&plist, 4);slprint(plist);//头删sltpopfront(&plist);slprint(plist);sltpopfront(&plist);slprint(plist);sltpopfront(&plist);slprint(plist);//尾删sltpopback(&plist);slprint(plist);//查找SLTNode* find = sltfind(plist, 3);if (find == NULL){printf("没找到！\n");}else{printf("找到啦！\n");}//指定位置之前插入sltinsert(&plist, find, 88);slprint(plist);//指定位置之后插入sltinsertafter(find, 66);slprint(plist);//删除Pose之后的结点slteraseafter(find);slprint(plist);//删除Pose的结点slterase(&plist, find);slprint(plist);//销毁sltdestroy(&plist);slprint(plist);
}
int main()
{//test();test01();return 0;
}代码写的有点乱，如有不便，敬请谅解 ！