数据结构之单链表(超详解)

---

---

1. 单链表

1.1 概念、结构

链表也是线性表的一种。

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

1.2 结点

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

结点的组成主要有两个部分：
1. 当前结点要保存的数据
2. 保存下⼀个结点的地址（指针变量）。

上图指针变量 plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点，如果我们希望plist“指向”第二个结点时，只需要修改plist保存的内容为0x0012FFA0。
链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下一个结点。

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

1.2.1 链表的性质

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

2. 链表的打印

结点创建

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. 尾插、头插

创建结点

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

尾插

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

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

头插

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

4. 尾删、头删

尾删

进行尾删操作需要考虑以下因素：

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

头删

头删需要考虑以下因素：

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

5. 查找指定结点

6. 指定位置之前、之后插入数据

指定位置之前插入数据

1. 链表是否为空
2. 指定位置值的结点是否存在
3. 如果指定位置的结点时头节点，则头插即可
4. 遍历链表找到指定结点的前一个结点
   

指定位置之后插入数据

7. 删除指定位置结点

1. 链表是否为空
2. 指定位置结点是否存在
3. 指定位置结点是否是头结点
4. 遍历链表找到pos结点的前一个结点
5. 释放pos结点
   

7.1 删除指定位置之后结点

8. 链表的销毁

9. 单链表代码实现

Slist.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
//针对顺序表:中间/头部插入效率低下、增容降低运行效率、增容造成空间浪费
//因此有了单链表
//链表也是线性表的一种
//链表是由一个一-个的节点组成
//组成:数据  指向下一个节点的指针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

#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 == NULLreturn 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

#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;
}

---

---