1. 单链表1.1 概念、结构链表也是线性表的一种。

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

1.2 结点每节"车厢"都是独立申请下来的空间，我们称之为“节点/结点”。

结点的组成主要有两个部分：

1. 当前结点要保存的数据

2. 保存下⼀个结点的地址（指针变量）。

上图指针变量 plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0。

链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下一个结点。

对应实现结点的结构体代码：

1.2.1 链表的性质链式机构在逻辑上是连续的，在物理结构上不一定连续；结点⼀般是从堆上申请的；从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续2. 链表的打印

结点创建

代码语言：javascript复制void SLTTest01()

{

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;

将4个节点连接起来

node1->next = node2;

node2->next = node3;

node3->next = node4;

node4->next = NULL;

SLTPrint(plist);

}

显然我们每次都要一个接一个创建结点，并让结点连接起来过于麻烦。因此，我们可以考虑封装成一个函数，这个函数用来创建结点。

3. 尾插、头插创建结点需要进行尾插，头插的操作首先需要创建结点

尾插在尾插的时候需要考虑以下几点：

如果为空链表该如何处理如何让两个结点相连如何找到尾部结点

头插相比于尾插，头插不需要考虑链表是否为空的情况，因为只要让新的结点头插到NULL即可

4. 尾删、头删尾删进行尾删操作需要考虑以下因素：

链表是否为空，空的话不能进行尾删遍历链表找到尾结点保存尾结点的前一个结点释放尾结点，让前一个结点指向NULL

头删头删需要考虑以下因素：

链表是否为空保存第二个有效结点释放第一个有效结点，让pphead指向第二个有效结点

5. 查找指定结点6. 指定位置之前、之后插入数据指定位置之前插入数据链表是否为空指定位置值的结点是否存在如果指定位置的结点时头节点，则头插即可遍历链表找到指定结点的前一个结点

指定位置之后插入数据7. 删除指定位置结点链表是否为空指定位置结点是否存在指定位置结点是否是头结点遍历链表找到pos结点的前一个结点释放pos结点

7.1 删除指定位置之后结点8. 链表的销毁9. 单链表代码实现

Slist.h

代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1

#include

#include

#include

//针对顺序表:中间/头部插入效率低下、增容降低运行效率、增容造成空间浪费

//因此有了单链表

//链表也是线性表的一种

//链表是由一个一-个的节点组成

//组成:数据 指向下一个节点的指针

typedef int DataType;//可能存储整形，字符型等等

typedef struct SlistNode

{

DataType data;//节点数据

struct SlistNode* next;//指向下一个节点的指针

}SLTNode;

//链表的打印

void SLTPrint(SLTNode* phead);

//创建节点

SLTNode* SLTBuyNode(DataType x);

//尾插

void SLTPushBack(SLTNode** pphead, DataType x);

//头插

void SLTPushFront(SLTNode** pphead, DataType x);

//尾删

void SLTPopBack(SLTNode** pphead);

//头删

void SLTPopFront(SLTNode** pphead);

//查找

SLTNode* SLTFind(SLTNode* phead, DataType x);

//在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x);

//在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, DataType x);

//删除pos节点

void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos后节点

void SLTEraseAfter(SLTNode* pos);

//销毁链表

void SLTDesTroy(SLTNode** pphead); Slist.c

代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1

#include"Slist.h"

//链表的打印

void SLTPrint(SLTNode* phead)

{

SLTNode* pcur = phead;

while (pcur)

{

printf("%d->", pcur->data);

pcur = pcur->next;

}

printf("NULL\n");

}

//创建节点

SLTNode* SLTBuyNode(DataType x)

{

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

if (newnode == NULL)

{

perror("malloc fail!");

exit(1);

}

//创建成功

newnode->data = x;

newnode->next = NULL;

return newnode;

}

//尾插

void SLTPushBack(SLTNode** pphead, DataType x)

{

assert(pphead);

//空链表和非空链表

SLTNode* newnode = SLTBuyNode(x);

//如果是空链表

if (*pphead == NULL)

{

*pphead = newnode;

}

else {

//找尾节点

SLTNode* ptail = *pphead;

while (ptail->next)

{

ptail = ptail->next;

}

//ptail指向的就是尾节点

ptail->next = newnode;

}

}

//头插

void SLTPushFront(SLTNode** pphead, DataType x)

{

assert(pphead);

SLTNode* newnode = SLTBuyNode(x);

newnode->next = *pphead;

*pphead = newnode;

}

//尾删

void SLTPopBack(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;

}

free(ptail);

ptail = NULL;

prev->next = NULL;

}

}

//头删

void SLTPopFront(SLTNode** pphead)

{

assert(pphead && *pphead);

SLTNode* next = (*pphead)->next;

free(*pphead);

*pphead = next;

}

//查找

SLTNode* SLTFind(SLTNode* phead, DataType x)

{

SLTNode* pcur = phead;

while (pcur)

{

if (pcur->data == x)

{

return pcur;

}

pcur = pcur->next;

}

//pcur == NULL

return NULL;

}

//在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x)

{

assert(pphead && *pphead);

assert(pos);

SLTNode* newnode = SLTBuyNode(x);

//若pos == *pphead 说明是头插

if (pos == *pphead)

{

SLTPushFront(pphead, x);

}

else {

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

newnode->next = pos;

prev->next = newnode;

}

}

//在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, DataType x)

{

assert(pos);

SLTNode* newnode = SLTBuyNode(x);

//先连接后面在前面

newnode->next = pos->next;

pos->next = newnode;

}

//删除pos节点

void SLTErase(SLTNode** pphead, SLTNode* pos)

{

assert(pphead && *pphead);

assert(pos);

//pos是头节点

if (pos == *pphead)

{

SLTNode* next = (*pphead)->next;

free(*pphead);

*pphead = next;

}

else

{

//pos不是头节点

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

prev->next = pos->next;

free(pos);

pos = NULL;

}

}

//删除pos后节点

void SLTEraseAfter(SLTNode* pos)

{

assert(pos && pos->next);

SLTNode* del = pos->next;

pos->next = del->next;

free(del);

del = NULL;

}

//销毁链表

void SLTDesTroy(SLTNode** pphead)

{

assert(pphead && *pphead);

SLTNode* pcur = *pphead;

while (pcur)

{

SLTNode* next = pcur->next;

free(pcur);

pcur = next;

}

//pcur为NULL

*pphead = NULL;

} test.c

代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS 1

#include"Slist.h"

//链表是由一个一个的节点组成

//创建几个节点

//第一个节点 *plist <---> **pphead

//指向第一个节点的指针 plist <---> *pphead

//指向第一个节点的指针的地址 &plist <---> pphead

void SLTTest01()

{

//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;

//将4个节点连接起来

//node1->next = node2;

//node2->next = node3;

//node3->next = node4;

//node4->next = NULL;

//调用链表的打印

SLTNode* plist = NULL;

SLTPushBack(&plist, 1);

SLTPushBack(&plist, 2);

SLTPushBack(&plist, 3);

SLTPushBack(&plist, 4);

SLTPushFront(&plist, 5);

SLTPrint(plist);

//SLTPopBack(&plist);

//SLTPopBack(&plist);

//SLTPopBack(&plist);

SLTPopBack(&plist);

SLTPopBack(&plist);

//SLTPrint(plist);

//SLTPopFront(&plist);

//SLTPopFront(&plist);

SLTPrint(plist);

//测试查找

SLTNode* find = SLTFind(plist, 5);

if (find == NULL)

{

printf("没有找到\n");

}

else {

printf("找到了\n");

}

SLTInsert(&plist, find, 6);

//SLTErase(&plist, find);

//SLTEraseAfter(find);

//SLTErase(&plist, find);

SLTPrint(plist);

SLTDesTroy(&plist);

SLTPrint(plist);

}

int main()

{

SLTTest01();

return 0;

}