• 【C语言入门数据结构3】链表之单链表

    👉系列专栏：【C语言–大佬之路】
    🙈个人主页：阿伟@t
    🎈今日心语：你所看到的惊艳，都曾被平庸所历练。

    前言：

    继【数据结构基础】顺序表 ，我们来介绍链表的相关内容。

    目录：

    1、链表

    • 顺序表(数组)的缺陷及思考
      缺陷：
    1. 中间/头部插入删除，需要移动的元素很多，浪费算力，时间复杂度为O(N)，
    2. 扩容需要申请新空间（尤其是异地扩容）可能会有空间的浪费，拷贝数据，释放旧空间。会有不小的消耗。
    3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。而多次少量扩容，又会使程序复杂化。

    image.png
    由于数组的这些缺点，自然而然的就产生链表的思想了。
    链表通过不连续的储存方式，自适应内存大小，以及指针的灵活使用，巧妙的简化了上述的内容。

    1.1 链表的概念及结构

    image.png
    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

    • 数据构成：

    数据域：存放数据本身的信息。
    指针域：存放指向下个结点的地址（指向直接后继的指针）。
    结点：数据元素的存储映像。由数据域和指针域两部分组成。
    n个结点通过指针域相互链接，组成一个链表。
    如图：
    image.png
    ①头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。
    ②头结点：一个不存任何数据的空结点，通常作为链表的第一个结点，它的数据域一般不存放数据。（头结点不是必须的。）
    ③首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

    image.png

    • 逻辑结构：

    image.png

    • 物理结构：

    实际中，是没有上面的箭头的
    image.png如图，n1,n2,n3,n4是指针变量，接收了开辟的结点，现在要将结点链接起来，就要把n2给了n1的next，依次类推。
    注意：
    1、链式结构在逻辑上是连续的，但在物理上不一定连续
    2、现实中的结点一般都是从堆上申请出来的
    3、从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

    1.2 链表的分类

    实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

    1. 单向或者双向

    image.png

    1. 带头或者不带头

    image.png

    1. 循环或者非循环

    image.png
    虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
    image.png

    1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

    1.3简单实现链表链接：

    • 定义结点 ：

    image.png

    • 测试部分：

    image.png

    • BuySLTNode 开辟空间函数封装：

    image.png
    由于上面创建结点，n1,n2,n3,n4需要一个一个创建，比较复杂，故我们封装一个函数,使得可以创建n个结点：

    • CreateSList创建结点函数封装

    image.png

    • 打印链表中的data和next指向的地址：

    image.png

    • 使用函数栈帧整体介绍：

    image.png
    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;//重定义 缩写，在本行之后起效，在结构体中不能使用

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    注意：这里重定义的结构名，只能在定义之后使用，不能在结构体中使用。

    2、尾插

    image.png
    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链接新结点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    测试：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    调用TestSList2时：
    image.png
    调用TestSList3时：
    image.png
    此时，我们插入的数据并没有插进去，所以要考虑到链表为空的情况。

    改进代码：

    //尾插
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链接新结点
	}
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    image.png
    如图，还是没插入进来
    这里就要注意，phead是plist的拷贝，phead的改变不会影响plist，phead出作用域销毁，plist此时还是NULL。
    这就涉及到实参传给形参，形参是实参的临时拷贝，形参的改变不会影响实参
    举一个经典的例子：
    image.png

    如图：
    1、改变int，传递int给形参，解引用形参进行交换改变。
    2、改变int    ，传递int**给形参，解引用形参进行交换改变。

    所以需要进行修改，这里的pphead是为了方便区分，也可以直接使用phead。
    image.png
    左图代码phead的改变是无法影响plist的值的，所以我们用到二级指针做如下改变（函数栈帧）：
    image.png
    image.png
    注意：想要改变结构体，只需要使用结构体的指针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链接新结点
	}
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    3、尾删

    经典错误：

    image.png
    当我们将tail释放时，d2->next还指向tail，这就形成了野指针。
    tail是局部变量，不需要置空。

    改进方法：

    方法一：
    image.png
    如图，在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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    方法二：
    image.png
    如图,当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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    但是上面代码并不完善，当我们进行多次删除打印，错误就会暴露出来，如下图，我们进行了四次打印，但却只输出了3次。
    image.png

    image.png
    如图，当删除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;
	}
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    image.png

    分析原因，我们发现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;
	}
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    image.png

    4、头插

    image.png
    如图，我们看出头插相对比较简单，我们只需要将newnode->next指向原来的开始结点，再将phead指针指向新的开始，也不必考虑空的情况：

    正确代码：

    //头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5、头删

    当链表为空时，不能进行头删，所以这里同样需要断言。
    头删不能直接删，直接删会导致找不到链表
    image.png
    先创建一个变量next间接指向下一个结点，再释放前一个结点，最后再将phead指向next，保证第一个节点的指针。

    //头删
void SLTPopFront(SLTNode** phead)
{
	assert(*phead);

	SLTNode* next = (*phead)->next;
	free(*phead);
	*phead = next;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    链表的优势在于头删，又快又简洁。

    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    问题：
    1、当链表为空时，进行查找，此时phead为空，cur也为空，那么cur->next,解引用失败，程序就会崩。
    2、这样会漏掉最后一个结点，如下图，当cur->next为空时，循环结束，最后一个结点的data没有查找到。
    image.png
    所以最好不要写这样的代码。

    最终代码：

    
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    7、在指定位置pos之后插入x

    和顺序表的最大区别：给的位置不再是下标，而是结点的指针

    经典错误：

    image.png
    如图，将pos->next先指向了新节点newnode，此时无法找到4的位置，所以newnode->next又指向了自己，形成了带环链表。此时程序是死循环：
    image.png
    此时，我们可以先保存4的位置，再进行链接，或者直接将上面的两步跌倒。
    这里只写第二种：

    最终代码：

    注意这里需要检查pos是否为空
    image.png
    如图，先将newnode和4链接，再进行前面的链接就不会出现上面的错误，代码如下：

    //在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    image.png
    这里改变的是结构体成员，有结构体的指针足以，不需要二级指针。

    8、在指定位置pos之前插入x

    如图，分析可知有下面两种情况：

    image.png

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    9、删除指定位置pos之后的值

    可能遇到两种情况：
    1、pos指向最后一个结点，pos之后的值为空，适合用温柔的检查（如下if语句）
    2、pos在中间，直接链接3和5会找不到4，从而无法释放造成内存泄漏。所以需要将4的位置给一个新的变量nextNode以便释放。
    经过分析，
    image.png

    //删除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);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    10、删除指定位置pos的值

    image.png

    //删除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);
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    11、释放单链表

    image.png

    //单链表的释放
void SLTDestory(SLTNode** phead)
{
	SLTNode* cur = *phead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;//plist置空，防止释放后再调用
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    总代码：

    1、SList.h文件

    #define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include
#include
#include

	 
//相当于下面的重定义
//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);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    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置空，防止释放后再调用
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168

    注意：
    如果不用二级指针，我们可以用返回值，但是每次返回得接收，c++中可以用引用
    不需要修改头指针就用一级，需要修改就用二级，必须将实参的地址传给形参

    结语：

    这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。希望以上内容对大家有所帮助👀，如有不足望指出🙏

    前路漫漫！努力变强💪💪 吧！！

  • 相关阅读:
    亚马逊云科技 Build On 2022 - AIot 第二季物联网专场实验心得
    元素和尺寸
    java 线程安全问题 三种线程同步方案 线程通信（了解）
    算法框架-LLM-1-Prompt设计（一）
    雪花算法记录
    python-爬虫-urllib3
    安卓基础学习 Day17|网格布局+计算器界面
    SaaS案例分享：成功构建销售渠道的实战经验
    buildadmin+tp8表格操作（7）表格的事件监听
    java基于springboot酒店客房预定管理系统ssm
  • 原文地址：https://blog.csdn.net/qq_72069067/article/details/128096262