目录
1. 链表
1.1 链表的概念及结构
概念：链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链 接 次序实现的 。
个人理解为：链表有两种结构，为逻辑结构和物理结构。
逻辑结构：链表是链式结构在逻辑上是连续的，它们之间用指针连接起来，上一个节点的next存储下一个节点的地址，一次类推，最后一个节点的next指向NULL。我们可以类比为一列火车(如图1-1)，依次链接起来的(如图1-2)。
物理结构：链式结构在逻辑上连续但是在物理结构上不一定连续，也就是说这些结点在内存中不一定是连续存储的。两次申请的空间可能连续可能不连续。
注意：现实中的节点一般都是从堆上申请出来的，从堆上申请的空间，是按照一定的策略分配的，两次申请的空间可能连续可能不连续（如图1-3）。
1.2链表的分类
?2、带头或者不带头
?3、循环或者非循环
?虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构:无头单向非循环链表(本篇文章所实现）和带头双循环链表。
1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结 构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
1.3接口
//不会改变链表的头指针，传一级指针
//打印
void SListPrint(SLTNode* plist);
//可能会改变链表的头指针，传二级指针
//尾插
void SListPushBack(SLTNode** pplist, SLTDataType x);
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);
//头删
void SListPopFront(SLTNode** pplist);
//尾删
void SListPopBack(SLTNode** pplist);
//查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x);
//在pos位置之前插入
void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x);
//在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos);
//删除pos后面的值
void SListEraseAfter(SLTNode** pplist, SLTNode* pos);
//销毁
void SListDestroy(SLTNode** pplist);
本篇文章我们将实现以上这些接口。
2. 接口实现
2.1 节点的创建
struct SListNode
{
SLTDataType data;
struct SListNode* next; //指向下一个指针(结构体类型)
};data表示该节点的值，next表示指向下一个指针(仍然是结构体类型，是一个结构体指针)。
2.2 打印链表
void SListPrint(SLTNode* plist);void SListPrint(SLTNode* plist)
{
SLTNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}?
?2.3 创建新节点
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}新节点包括数据data，next我们默认置NULL
2.4?尾插
void SListPushBack(SLTNode** pplist, SLTDataType x);void SListPushBack(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
//找尾节点的指针
//*pplist = plist
if (*pplist == NULL)
{
*pplist = newnode; //形参的改变不会影响实参
}
else
{
//找尾
SLTNode* tail = *pplist;//tail是局部变量
while (tail->next != NULL)
{
tail = tail->next;
}
//尾节点链接新节点
tail->next = newnode;
}
}尾插的核心是寻找尾结点，寻找的关键要点是尾结点的next指针指向空，因为我们只需要判断尾指针的下一个指针是否为空则可以找到尾。
注意：
我们学过函数知道，形参的改变不影响实参，要改变实参就要传地址，用指针接收，因此我们改变的是结构体指针的地址，我们需要二级指针来接收。
2.5?头插
//头插
void SListPushFront(SLTNode** pplist, SLTDataType x);void SListPushFront(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode; //形参的改变不会影响实参
}头插相对来说比较简单。得到新节点后，让新节点的next指向头结点，头结点再被改为newnode即可。
2.6 尾删
//尾删
void SListPopBack(SLTNode** pplist);//尾删
void SListPopBack(SLTNode** pplist)
{
assert(pplist);
//1.空
if (*pplist == NULL)
{
return;
}
//2.一个结点
else if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
//3.多个结点
SLTNode* prev = NULL;
SLTNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
//SLTNode* tail = *pplist;
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}
}尾删需要考虑链表的节点个数，分为空链表，一个节点，多个几点这三类。
1、如果为空链表，直接return。
2、如果有一个节点，我们直接讲这个节点free释放，再将头结点置空即可。
3、如果有多个节点，我们首先还是要找尾，但是这次我们不仅要找尾，还要找尾结点的上一个节点，因此我们可以有两种方法来解决
第一种方法：
创建两个临时结构体指针，一个找尾，一个找尾的上一个节点，找到后只需要free掉尾结点，再将上一个节点的next指位NULL
第二种方法：
只需创建一个临时结构体指针，我们通过next的next找尾，next找尾的上一个节点，也可实现尾删。
2.7 头删
void SListPopFront(SLTNode** pplist);void SListPopFront(SLTNode** pplist)
{
assert(pplist);
//1.空
if (*pplist == NULL)
{
return;
}
//2.非空 单节点与多节点可合并
else
{
SLTNode* head = (*pplist)->next;
free(*pplist);
*pplist = head;
}
}头删也要分为两种情况，链表为空和非空
1、链表为空，直接return。
2、链表不为空，我们找到第二个节点，释放掉第一个节点，再将第二个节点的地址给头结点即可。
2.8?查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
SLTNode* cur = plist;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}查找是比较简单的，只需要注意的是，查找返回的是具体数值的地址，若为空，则返回NULL。
2.9?在pos位置之前插入
void SListInsertBefore(SLTNode** pplist,SLTNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
assert(pplist);
assert(pos);
//1.头插 pos是第一个节点
if (pos == *pplist)
{
SListPushFront(pplist, x);
}
//2. pos不是第一个节点
else
{
SLTNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}在写之前一定要判断该链表和该位置是否为空，如果都不存在链表和该位置，插值也是无稽之谈。
这是我们也要分为pos位第一个位置和pos不是第一个位置两种情况：
1、如果pos在第一个位置，相当于头插的作用，我们只需要调用头插接口即可。
2、如果pos不在第一个位置，我们先找到pos位置的上一个节点prev，prev的next保存newnode的地址，newnode的next保存pos位置的地址即可。
2.10?在pos位置之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
//存一份pos下一位的地址
SLTNode* next = pos->next;
SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = next;
}首先仍然需要对pos位置进行断言
接下来这一步非常关键，我们必须要创建一个next指针来保存pos的next指针的地址，因为只有pos位置才能访问到pos的next指针，创建newnode后，只需要将pos的next保存newnode的地址，再让newnode的next保存刚刚创建的next的指针的地址即可。
2.11 删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos);
//删除pos位置
void SListErase(SLTNode** pplist, SLTNode* pos)
{
assert(pplist);
assert(pos);
//1.pos是第一个 相当于头删
if (*pplist == pos)
{
SListPopFront(pplist);
}
//2.
else
{
SLTNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}删除操作一定要对链表进行断言
这里我们依然要分为pos位置是第一个节点和pos位置不是第一个节点两种情况：
1、pos位置是第一个节点，相当于头删，调用头删接口即可
2、pos位置不是第一个节点，我们需要找到pos位置的前一个节点prev，然后将prev的next保存pos的next的地址，再将pos位置free，再置空即可。
2.12?删除pos后面的值
void SListEraseAfter(SLTNode** pplist, SLTNode* pos);
void SListEraseAfter(SLTNode** pplist, SLTNode* pos)
{
assert(pplist);
assert(pos);
SLTNode* next = pos->next;
if (next)
{
pos->next = next->next;
free(next);
}
}这个比较简单，只需要创建临时指针next保存pos的next地址，再让pos的next保存next的next的地址，再释放掉next即可。
3.菜单
#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void menu()
{
printf("************************************\n");
printf("***** 1.尾插 *****\n");
printf("***** 2.头插 *****\n");
printf("***** 3.尾删 *****\n");
printf("***** 4.头删 *****\n");
printf("***** 5.查找 x *****\n");
printf("***** 6.在pos位置之前插入 *****\n");
printf("***** 7.在pos位置之后插入 *****\n");
printf("***** 8.删除pos位置的元素 *****\n");
printf("***** 9.删除pos之后的元素 *****\n");
printf("***** 10.打印单链表 *****\n");
printf("***** -1.退出 *****\n");
printf("************************************\n");
}
int main()
{
SLTNode* plist = NULL;
int option = -1;
menu();
do
{
printf("请输入选项:> ");
scanf("%d", &option);
if (option == 1)
{
int x = 0;
printf("请输入你要尾插的数字:>");
scanf("%d", &x);
SListPushBack(&plist, x);
}
else if (option == 2)
{
int x = 0;
printf("请输入你要头插的数字:>");
scanf("%d", &x);
SListPushFront(&plist, x);
}
else if (option == 3)
{
SListPopBack(&plist);
}
else if (option == 4)
{
SListPopFront(&plist);
}
else if (option == 5)
{
int x = 0;
printf("请输入你要查找的值x:>");
scanf("%d", &x);
SLTNode* cur = SListFind(plist, x);
if (cur != NULL)
{
printf("存在数字%d\n",x);
}
else
{
printf("未找到数字%d", x);
}
}
else if (option == 6)
{
int x = 0;
int y = 0;
printf("请分别输入pos值x和pos前所插入的值y:>");
scanf("%d %d", &x,&y);
SLTNode* pos = SListFind(plist, x);
if (pos != NULL)
{
SListInsertBefore(&plist, pos, y);
}
else
{
printf("该链表不存在%d\n",x);
}
}
else if (option == 7)
{
int x = 0;
int y = 0;
printf("请分别输入pos值x和pos后所插入的值y:>");
scanf("%d %d", &x, &y);
SLTNode* pos = SListFind(plist, x);
if (pos != NULL)
{
SListInsertAfter(pos, y);
}
else
{
printf("该链表不存在%d\n",x);
}
}
else if (option == 8)
{
int x = 0;
printf("请输入要删除pos位置的值:>");
scanf("%d", &x);
SLTNode* pos = SListFind(plist, x);
SListErase(&plist, pos);
}
else if (option == 9)
{
int x = 0;
printf("请输入要删除pos位置之后的值:>");
scanf("%d", &x);
SLTNode* pos = SListFind(plist, x);
SListEraseAfter(&plist, pos);
}
else if (option == 10)
{
SListPrint(plist);
}
} while (option != -1);
SListDestroy(&plist);
return 0;
}
完整代码在我的Gitte：2022_03_10 链表/2022_03_10 链表 · 李兴宇/数据结构 - 码云 - 开源中国 (gitee.com)
（本篇完）