【C语言入门数据结构3】链表之单链表
1、链表
- 顺序表(数组)的缺陷及思考 缺陷：
- 中间/头部插入删除，需要移动的元素很多，浪费算力，时间复杂度为O(N)，
- 扩容需要申请新空间（尤其是异地扩容）可能会有空间的浪费，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。而多次少量扩容，又会使程序复杂化。
由于数组的这些缺点，自然而然的就产生链表的思想了。 链表通过不连续的储存方式，自适应内存大小，以及指针的灵活使用，巧妙的简化了上述的内容。
1.1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
- 数据构成：
数据域：存放数据本身的信息。 指针域：存放指向下个结点的地址（指向直接后继的指针）。 结点：数据元素的存储映像。由数据域和指针域两部分组成。 n个结点通过指针域相互链接，组成一个链表。 如图：
①头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。 ②头结点：一个不存任何数据的空结点，通常作为链表的第一个结点，它的数据域一般不存放数据。（头结点不是必须的。） ③首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。
- 逻辑结构：
- 物理结构：
实际中，是没有上面的箭头的
如图，n1,n2,n3,n4是指针变量，接收了开辟的结点，现在要将结点链接起来，就要把n2给了n1的next，依次类推。 注意： 1、链式结构在逻辑上是连续的，但在物理上不一定连续 2、现实中的结点一般都是从堆上申请出来的 3、从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
1.3简单实现链表链接：
- 定义结点 ：
- 测试部分：
- BuySLTNode 开辟空间函数封装：
由于上面创建结点，n1,n2,n3,n4需要一个一个创建，比较复杂，故我们封装一个函数,使得可以创建n个结点：
- CreateSList创建结点函数封装
- 打印链表中的data和next指向的地址：
- 使用函数栈帧整体介绍：
phead和ptail存了第一个结点的地址， phead为了方便返回，ptail为了方便链接 ptail->next指向下一个结点，存放该结点的地址， 然后ptail指向新的结点 最后，phead指向头结点，ptail指向尾结点 当CreateSList函数调用结束后,该函数的栈帧销毁，局部变量phead，ptail随之销毁 这样就找不到链表了，但是phead在销毁前，返回了，将指向的内容拷贝给了plist，这样plist就指向了链表的首结点，就可以找到链表了。 plist传参给新的phead，为了方便区分定义了一个指针变量cur，同样的SLPrint函数调用结束后，函数栈帧销毁，phead和cur随之一起销毁。 由此我们可以得出结论： 使用链表的时候一直保持一个指针指向头节点，链表的关键使头结点，顺序表的关键是结构。
2、单链表（single linked list）程序：
经过上面简单的单链表链接，想必你已经对单链表有了些许认识，下面让我们来实现单链表吧！！
1、结构体定义结点
typedef int SLTDataType;//重定义数据类型，方便切换数据类型
typedef struct SListNode//定义单链表结构 32位环境下共8个字节，
{
SLTDataType data;//定义数据
struct SListNode* next;//指向下一个结构的指针，指向同类
//SLTNode* next;
}SLTNode;//重定义 缩写，在本行之后起效，在结构体中不能使用注意：这里重定义的结构名，只能在定义之后使用，不能在结构体中使用。
2、尾插
tail->next是结构体指针指向结构体成员next，而next存放的是下一个结点的地址，next指向下一个结点。
初始代码：
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* tail = phead;
//找尾
while (tail->next)
{
tail = tail->next;//不是结尾，tail向后移动。
}
tail->next = newnode;//是结尾，tail->next链接新结点
}测试：
void TestSList2()
{
SLTNode* plist = CreateSList(5);
SLTPushBack(plist, 100);
SLTPushBack(plist, 200);
SLTPushBack(plist, 300);
SLTPrint(plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SLTPushBack(plist, 100);
SLTPushBack(plist, 200);
SLTPushBack(plist, 300);
SLTPrint(plist);
}
int main()
{
TestSList2();
//TestSList3();
return 0;
}调用TestSList2时：
调用TestSList3时：
此时，我们插入的数据并没有插进去，所以要考虑到链表为空的情况。
改进代码：
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (phead == NULL)
{
phead = newnode;
}
else
{
SLTNode* tail = phead;
//找尾
while (tail->next)
{
tail = tail->next;//不是结尾，tail向后移动。
}
tail->next = newnode;//是结尾，tail->next链接新结点
}
}
如图，还是没插入进来 这里就要注意，phead是plist的拷贝，phead的改变不会影响plist，phead出作用域销毁，plist此时还是NULL。 这就涉及到实参传给形参，形参是实参的临时拷贝，形参的改变不会影响实参 举一个经典的例子：
如图： 1、改变int，传递int给形参，解引用形参进行交换改变。 2、改变int，传递int**给形参，解引用形参进行交换改变。
所以需要进行修改，这里的pphead是为了方便区分，也可以直接使用phead。
左图代码phead的改变是无法影响plist的值的，所以我们用到二级指针做如下改变（函数栈帧）：
注意：想要改变结构体，只需要使用结构体的指针tail->next，无需使用二级指针。
正确代码：
//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (*phead == NULL)
{
*phead = newnode;
}
else
{
SLTNode* tail = *phead;
//找尾
while (tail->next)
{
tail = tail->next;//不是结尾，tail向后移动。
}
tail->next = newnode;//是结尾，tail->next链接新结点
}
}3、尾删
经典错误：
当我们将tail释放时，d2->next还指向tail，这就形成了野指针。 tail是局部变量，不需要置空。
改进方法：
方法一：
如图，在tail往下走之前，我们可以将tail赋值给一个新的变量prev，从而找到最后一个结点之前的结点，释放tail之后，再使用结构体指针将前一个结点的指针域置为空。
void SLTPopBack(SLTNode* phead)
{
SLTNode* tail = phead;
SLTNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}方法二：
如图,当tail指向d1时，tail->next->next就是d2->next不为空，tail指d2，此时tail->next->next为空，tail->next为d2->next，将其释放并置为空。
void SLTPopBack(SLTNode* phead)
{
SLTNode* tail = phead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}但是上面代码并不完善，当我们进行多次删除打印，错误就会暴露出来，如下图，我们进行了四次打印，但却只输出了3次。
如图，当删除tail后面的两个结点后，tail->next为空，这时就再去使用tail->next就是错误的。
初步改进：
void SLTPopBack(SLTNode* phead)
{
if (phead->next == NULL)
{
free(phead);
phead = NULL;
}
else
{
SLTNode* tail = phead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
分析原因，我们发现phead的改变不会影响plist，而我们这里释放了phead并且将phead置为了空，所以尾删也得用二级指针。 注意：链表为空不能删除，所以我们需要assert断言
正确代码：
void SLTPopBack(SLTNode** phead)
{
assert(*phead);//链表为空，不可删除，为空直接报错，终止
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
SLTNode* tail = *phead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
4、头插
如图，我们看出头插相对比较简单，我们只需要将newnode->next指向原来的开始结点，再将phead指针指向新的开始，也不必考虑空的情况：
正确代码：
//头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *phead;
*phead = newnode;
}5、头删
当链表为空时，不能进行头删，所以这里同样需要断言。 头删不能直接删，直接删会导致找不到链表
先创建一个变量next间接指向下一个结点，再释放前一个结点，最后再将phead指向next，保证第一个节点的指针。
//头删
void SLTPopFront(SLTNode** phead)
{
assert(*phead);
SLTNode* next = (*phead)->next;
free(*phead);
*phead = next;
}链表的优势在于头删，又快又简洁。
6、查找数据指定位置pos
在查找时，最好用一个变量来接收phead，保证phead在过程中一直指向链表的开始。
经典错误：
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur->next != NULL)
{
if (cur->data == x)
{
return cur;
}
cur=cur->next;
}
}问题： 1、当链表为空时，进行查找，此时phead为空，cur也为空，那么cur->next,解引用失败，程序就会崩。 2、这样会漏掉最后一个结点，如下图，当cur->next为空时，循环结束，最后一个结点的data没有查找到。
所以最好不要写这样的代码。
最终代码：
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
}7、在指定位置pos之后插入x
和顺序表的最大区别：给的位置不再是下标，而是结点的指针
经典错误：
如图，将pos->next先指向了新节点newnode，此时无法找到4的位置，所以newnode->next又指向了自己，形成了带环链表。此时程序是死循环：
此时，我们可以先保存4的位置，再进行链接，或者直接将上面的两步跌倒。 这里只写第二种：
最终代码：
注意这里需要检查pos是否为空
如图，先将newnode和4链接，再进行前面的链接就不会出现上面的错误，代码如下：
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
这里改变的是结构体成员，有结构体的指针足以，不需要二级指针。
8、在指定位置pos之前插入x
如图，分析可知有下面两种情况：
//在pos位置之前插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (*phead == pos)//头插
{
SLTPushFront(phead, x);//复用
}
else
{
SLTNode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}9、删除指定位置pos之后的值
可能遇到两种情况： 1、pos指向最后一个结点，pos之后的值为空，适合用温柔的检查（如下if语句） 2、pos在中间，直接链接3和5会找不到4，从而无法释放造成内存泄漏。所以需要将4的位置给一个新的变量nextNode以便释放。 经过分析，
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
/*free(pos->next);
pos->next = pos->next->next;*///错误，释放了后一个结点，这个空间被置为随机值，找不到后面的结点
SLTNode* nextNode = pos->next;
pos->next = nextNode->next;
free(nextNode);
}
}10、删除指定位置pos的值
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (pos == *phead)
{
SLTPopFront(phead);
}
else
{
SLTNode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}11、释放单链表
//单链表的释放
void SLTDestory(SLTNode** phead)
{
SLTNode* cur = *phead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*phead = NULL;//plist置空，防止释放后再调用
}总代码：
1、SList.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//相当于下面的重定义
//struct SListNode
//{
// STLDataType data;
// struct SListNode* next;
//};
//typedef struct SListNode SLTNode;
//void SLTPushBack(SLTDataType x)
//{
// SLTNode node;//这样定义的结点出作用域销毁
//}
typedef int SLTDataType;//重定义数据类型，方便切换数据类型
typedef struct SListNode//定义单链表结构 32位环境下共8个字节，
{
SLTDataType data;//定义数据
struct SListNode* next;//指向下一个结构的指针，指向同类
//SLTNode* next;
}SLTNode;//重定义 缩写，在本行之后起效，在结构体中不能使用
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);
//尾插尾删
void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPopBack(SLTNode** phead);
//头插头删
void SLTPushFront(SLTNode** phead, SLTDataType x);
void SLTPopFront(SLTNode** phead);
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);
//在pos位置之前插入x
void SListInsert(SLTNode** phead,SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//单链表的释放
void SLTDestory(SLTNode** phead);2、SList.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//直接用malloc需要自行赋值，检查空，很烦，所以封装一个函数
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//未开辟成功，结束程序
}
newnode->data = x;
newnode->next = NULL;//最后一个结点默认为空
return newnode;
}
SLTNode* CreateSList(int n)
{
SLTNode* phead = NULL, * ptail = NULL;
/*int x = 0;*/
for (int i = 0; i < n; ++i)
{
/*scanf("%d", &x);
SLTNode* newnode = BuySLTNode(x);*/
SLTNode* newnode = BuySLTNode(i);
if (phead == NULL)
{
ptail = phead = newnode;
}
else
{
ptail->next = newnode;
ptail = newnode;
}
}
return phead;
}
//打印函数封装
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("[%d|%p]->", cur->data,cur->next);
cur = cur->next;
}
printf("NULL\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
//找尾
while (tail->next)
{
tail = tail->next;//不是结尾，tail向后移动。
}
tail->next = newnode;//是结尾，tail->next链接新结点
}
}
//尾删
//void SLTPopBack(SLTNode* phead)
//{
// SLTNode* tail = phead;
// SLTNode* prev = NULL;
// while (tail->next)
// {
// prev = tail;
// tail = tail->next;
// }
// free(tail);
// prev->next = NULL;
//}
//尾删
void SLTPopBack(SLTNode** phead)
{
assert(*phead);
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
SLTNode* tail = *phead;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *phead;
*phead = newnode;
}
//头删
void SLTPopFront(SLTNode** phead)
{
assert(*phead);
SLTNode* next = (*phead)->next;
free(*phead);
*phead = next;
}
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
}
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//在pos位置之前插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
assert(pos);
if (*phead == pos)
{
SLTPushFront(phead, x);
}
else
{
SLTNode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
/*free(pos->next);
pos->next = pos->next->next;*///错误，释放了后一个，这个空间被置为随机值，找不到后面的结点
SLTNode* nextNode = pos->next;
pos->next = nextNode->next;
free(nextNode);
}
}
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos)
{
assert(pos);
if (pos == *phead)
{
SLTPopFront(phead);
}
else
{
SLTNode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
//单链表的释放
void SLTDestory(SLTNode** phead)
{
SLTNode* cur = *phead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*phead = NULL;//plist置空，防止释放后再调用
}3、test.c测试文件
#include"SList.h"
void TestSList1()
{
//SLTNode* n1 = malloc();//直接用malloc需要自行赋值，检查空，很烦，所以封装一个函数
SLTNode* n1 = BuySLTNode(1);
SLTNode* n2 = BuySLTNode(2);
SLTNode* n3 = BuySLTNode(3);
SLTNode* n4 = BuySLTNode(4);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
//SLTNode n1;//为什么不直接定义结构体变量
//SLTNode n2;
//n1.next = &n2;//这样也可以链接，但是不可行
//SLTNode* plist = CreateSList(5);
//SLTPrint(plist);
}
//初始测试代码
void TestSList2()
{
SLTNode* plist = CreateSList(5);
SLTPushBack(&plist, 100);
SLTPushBack(&plist, 200);
SLTPushBack(&plist, 300);
SLTPrint(plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 100);
SLTPushBack(&plist, 200);
SLTPushBack(&plist, 300);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
void TestSList4()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 100);
SLTPushFront(&plist, 200);
SLTPushFront(&plist, 300);
SLTPushFront(&plist, 400);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
void TestSList5()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushBack(&plist, 5);
SLTPrint(plist);
SLTNode* pos = SListFind(plist, 3);
SListInsertAfter(pos, 30);
pos = SListFind(plist, 2);
SListInsert(&plist, pos, 200);
SLTPrint(plist);
// if (pos)
// {
// SListInsertAfter(pos, 30);//找到之后在后面插入30
// printf("找到了\n");
//
// }
// else
// {
// printf("找不到\n");
// }
// SLTPrint(plist);
}
void TestSList6()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushBack(&plist, 5);
SLTPrint(plist);
SLTNode* pos = SListFind(plist, 3);
SListEraseAfter(pos);
SLTPrint(plist);
pos = SListFind(plist, 3);
SListErase(&plist,pos);
pos = NULL;
SLTPrint(plist);
SLTDestory(&plist);
SLTPrint(plist);
}
int main()
{
//TestSList1();
//TestSList2();
//TestSList3();
//TestSList4();
//TestSList5();
TestSList6();
return 0;
}
二级指针经典例子
//void Swap1(int* p1, int* p2)
//{
// int tmp = *p1;
// *p1 = *p2;
// *p2 = tmp;
//}
//void Swap2(int** pp1, int** pp2)
//{
// int tmp = *pp1;
// *pp1 = *pp2;
// *pp2 = tmp;
//}
//
//int main()
//{
// int a = 0, b = 1;
// swap1(&a, &b);
//
// int* ptr1 = &a, * ptr2 = &b;
// swap2(&ptr1, &ptr2);
//
// return 0;
//
//}注意： 如果不用二级指针，我们可以用返回值，但是每次返回得接收，c++中可以用引用 不需要修改头指针就用一级，需要修改就用二级，必须将实参的地址传给形参
结语：
这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。希望以上内容对大家有所帮助👀，如有不足望指出🙏