C_单链表的实现 —— 创建一个链表、打印链表的函数、申请新结点、尾插、头插、尾删、头删、查找、在指定位置之前和之后分别插入数据、删除pos或pos之后的结点、销毁链表- 惊觉

一、单链表

1、概念与结构

1.结点

2.链表的性质

3.链表的打印

2、单链表的实现

1.创建一个链表（一般不会这样使用，了解就好）

一、单链表

1、概念与结构

概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。（单链表：Single List —> SList）

1.结点

与顺序表不同的是，链表里的每个空间，我们称之为“结点/节点”。

结点的组成主要有两个部分：当前结点、下⼀个结点的地址（指针变量）。

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

注意：结点的地址不一定是连续的。

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

2.链表的性质

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

结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：

假设当前保存的结点为整型：

struct SListNode
{
    int data; //结点数据
    struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。当我们想要从第⼀个结点走到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。

重点：

在链表中，没有增容（realloc）的概念，需要插入新的数据时，直接申请（malloc）一个结点大小的空间就可以了。

3.链表的打印

给定的链表结构中，实现结点从头到尾的打印，步骤如下：

思考：当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时，该如何修改？

答：可以使用typedef定义类型来方便后面的一键替换，如下代码：

typedef int LTDataType;
//可修改数据类型，进行一键替换

struct SListNode
{
    LTDataType data; //结点数据
    struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

2、单链表的实现

1.创建一个链表（一般不会这样使用，了解就好）

void createSList()
{
	//链表是由一个一个的结点组成的
	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;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

}

具体的链表通过next指针连接，如下图所示：

通过调试后的监视窗口可知成功创建一个链表：

2.打印链表的函数

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

打印链表的函数，有一层循环，时间复杂度为O(n)。

测试用例运行结果：

思路分析：

pcur = pcur->next表示的是直接将下一个结点的地址赋值给pcur，这就使pcur往后走打印。

打印不需要改变*pphead，所以不需要使用传址和二级指针。

重点：

为了防止找不到头结点，定义一个指针变量pcur来代替phead进行操作，pcur的变化不会影响头结点的地址。

3.申请新结点（最为重要的一步）

//申请新结点（最为重要的一步）
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;
	//新申请的结点初始化默认指向为空

	return node;
}

思路分析：

（1）使用malloc函数来增容开辟可用空间；

（2）开辟完后再判断该新增的结点空间地址是否为NULL，若为NULL，则增容失败，退出程序；

（3）若不为新结点地址不为NULL，则将初始化后的data和指向下一结点的地址存进新结点中。

注意：空指针是不能对其进行解引用的；无循环遍历，时间复杂度为O(1)。

4.尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//pphead -> &plist
	// *pphead -> plist
	//申请新的结点
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾结点
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		//pcur newnode
		pcur->next = newnode;
	}
}

尾插这段代码中有一层循环，时间复杂度为O(n)。

思路分析：

（1）assert断言传的形参pphead（即头结点的地址的地址）是否为空，若为空则断言报错，否则正常运行；

（2）通过SLTBuyNode函数申请新的结点，将新的结点的地址用newnode表示；

（3）判断头结点的地址是否为NULL，若为NULL直接将newnode的地址赋给*pphead，使新申请的结点成为头结点；

（4）若不为NULL则进行找尾结点的操作，首先将头结点的地址保存到pcur这个指针变量中，再用pcur来循环遍历，循环条件为当pcur->next不为NULL时，将pcur->next这个地址赋值给pcur这个指针变量，使pcur指针往后走，直到找到尾结点；

（5）若找到尾结点，即pcur->next为NULL，跳出循环，让newnode赋值给pcur->next，完成尾插。

注意：

只传一级指针是传不成功的（传值），此时形参的改变不会影响实参，所以不发生改变，调试时可以看出来，打印出来的全是NULL，如下：

形参的改变要影响实参，必须传实参的地址，所以要对实参一级指针plist取地址操作，即&plist；形参即变为用二级指针（SLTNode** pphead）来接收（传址）。

所有改变头结点（*pphead）的操作，都需要传址，和使用二级指针。

测试用例运行结果成功，如下：

尾插时，必须加上assert断言判断头结点是否为空，传址为空的话则断言报错：

5.头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请新的结点
	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}

头插这段代码中没有循环，时间复杂度为O(1)。

思路分析：

（1）assert断言传的形参pphead（即头结点的地址的地址）是否为空，若为空则断言报错，否则正常运行；

（2）通过SLTBuyNode函数申请新的结点，将新的结点的地址用newnode表示；

（3）单链表头插直接将头结点的地址赋给newnode->next，让newnode->next指向*pphead；

（4）最后将newnode这个指针变量当成头结点的地址，即newnode赋给*pphead。

测试用例运行结果：

6.尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表为空：不可以删除
	assert(pphead && *pphead);
	//处理只有一个结点的情况：要删除的就是头结点
	if ((*pphead)->next == NULL)//此处要加小括号的原因是箭头的解引用操作符的优先级高于*解引用操作符
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找 prev  ptail
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

尾删这段代码中有一层循环，时间复杂度为O(n)。

思路分析：

（1） assert断言传的形参pphead（即头结点的地址的地址）和*pphead（头结点的地址）是否为空，若为空则断言报错，不可以删除，否则正常运行；

（2）首先要考虑处理只有一个结点的情况，即要删除的就是头结点，我们可以判断(*pphead)->next是否为NULL，若为NULL，则直接free释放掉，再将*pphead置为空。

（3）若不为NULL，我们可以通过ptail的前驱结点prev的地址遍历来找尾结点ptail的地址，首先初始化将ptail的地址赋为*pphead（头结点的地址），从头开始遍历，所以此时prev为NULL，置为空。

（4）通过循环条件ptail->next判断是否为NULL，若不为NULL，则prev走到此时ptail的位置，ptail走到此时ptail->next的位置，以此类推；

（5）若为NULL，则表示，ptail的下一个结点就为空，此时ptail所指向的结点就为尾结点，跳出循环，将prev->next指向NULL，同时释放ptail这个结点，将ptail结点置为空。

注意：

若不判断处理只有一个结点的情况的话，就会使尾删到prev->next = NULL时触发异常，终端报错：

报错分析：

因为prev此时自己本身为NULL，即无前驱结点，所以不能对自己解引用，即不能prev->next = NULL，会诱发异常报错。

测试用例正常运行结果：

若就此基础再尾删一次的话，也会因为是空指针NULL断言报错：

7.头删

第一种写法：先释放再改头结点。

//头删
//第一种写法：先释放再改头结点。
void SLTPopFront(SLTNode** pphead) 
{
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	//*pphead --> next
	free(*pphead);
	*pphead = next;
}

第二种写法：先改头结点，再释放。

//第二种写法：先改头结点，再释放。
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}

头删这段代码中没有循环，时间复杂度为O(1)。

思路分析：

第一种写法：

（1）assert断言传的形参pphead（即头结点的地址的地址）和*pphead（头结点的地址）是否为空，若为空则断言报错，不可以删除，否则正常运行；

（2）将(*pphead)->next的地址命名为next指针变量，然后直接释放*pphead，再重新将next当作为头结点的地址。

第二种写法：

（1）assert断言传的形参pphead（即头结点的地址的地址）和*pphead（头结点的地址）是否为空，若为空则断言报错，不可以删除，否则正常运行；

（2）将头结点的地址*pphead赋给del，作为指针变量来变换，将(*pphead)->next地址赋给*pphead，使*pphead往后走，再释放del，置为NULL。

测试用例正常运行结果：

若就此基础再尾删一次的话，会因为是空指针NULL断言报错：

8.查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

查找这段代码中有一层遍历循环，时间复杂度为O(n)。

思路分析：

（1）assert断言传的形参phead（即头结点的地址），是否为空，若为空则断言报错，否则运行成功；

（2）传头结点地址到pcur这个指针变量中去，通过while循环条件判断pcur是否为空，若为不为空，则继续进行判断pcur->data是否为x，若是，则返回pcur（地址），若不是所想查找的该值，则跳出if语句执行pcur=pcur->next，使pcur往后走。若while循环条件判断pcur为空，则直接返回NULL（表示没有找到）。

测试用例运行结果：

9.在指定位置之前插入数据

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		//找prev：pos的前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev  newnode --> pos
		newnode->next = pos;
		prev->next = newnode;
	}
}

在指定位置之前插入数据，有一层循环，所以时间复杂度为O(n)。

思路分析：

（1）assert断言传的形参pphead（即头结点的地址的地址）和pos（指定位置的地址），是否为空，若为空则断言报错，否则运行成功；

（2）首先判断pos结点地址是否等于*pphead（头结点地址），若是，则此情况为在头结点前插入数据，所以调用单链表头插函数即可；

（3）新申请下来的结点地址放到指针变量newnode中，将*pphead头结点地址保存在指针变量prev中，使prev指针从头开始遍历；

（4）进入while循环条件进行判断，若prev->next不为pos，则prev往后走，以此类推继续对比判断；若prev->next为pos，则跳出循环，让newnode->next指向下一个结点pos，再使prev->next指向下一个结点newnode。

测试用例正常运行结果：

以下代码为没有考虑到当pos为第一个结点时的情况：

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	//找prev：pos的前一个结点
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev  newnode --> pos
	newnode->next = pos;
	prev->next = newnode;
}

若将测试用例改成在当pos为第一个结点时，在其之前插入数据，头结点是没有前一个结点的，则会因为一直再找while循环中的条件prev->next != pos，从而造成死循环，因此报错：

所以我们要考虑到当pos为第一个结点时的情况，头结点是没有前一个结点的，这个情况跟头插一致，即我们可以直接调用头插的方法来解决此报错问题，正确测试用例结果如下：

10.在指定位置之后插入数据

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
//因为在指定位置之后插⼊数据用不到头结点（用不到前驱结点），只需用pos->next,所以没有**pphead这个形参
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	//pos newnode-->pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}

在指定位置之后插入数据，无循环，所以时间复杂度为O(1) 。

思路分析：

（1）assert断言判断pos这个地址是否为NULL，若为空则断言报错，不为空则继续运行；

（2）将申请的新结点地址赋值到newnode这个指针变量中去，让newnode->next指向pos->next的位置，再让pos->next指向newnode这个结点。

注意：

在指定位置之后插入数据中，与头结点无关（*pphead），而且当pos->next是NULL时，该代码也照样成立，不需要另辟蹊径，所以可将newnode直接插入到pos之后。

测试用例运行结果：

11.删除pos结点

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);

	//头删
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除pos结点这段代码中有一层遍历循环，时间复杂度为O(n)。

思路分析：

（1）assert断言传的形参pphead（即头结点的地址的地址）和*pphead（头结点的地址）和pos结点（地址）是否为空，若为空则断言报错，不可以删除，否则正常运行；

（2）首先判断pos是否为*pphead，若是，则为pos在头结点的情况，符合单链表头删这种情况，直接调用单链表头删函数；

（3）若pos不为*pphead，则将头结点的地址（*pphead）保存到prev指针变量中去，prev作为前驱结点，从头开始遍历；

（4）在while循环的判断条件中，判断prev->next是否等于pos，若不等于pos，则prev往后走，直到找到pos；若等于pos，则跳出循环，使prev->next指向pos->next这个结点，再释放pos这个结点，同时置为NULL。

注意：

若没有考虑到pos是头结点的情况，则会使prev此时为NULL，在while循环语句中就无法对prev这个pos的前驱结点进行解引用操作，如下：

测试用例运行结果：

12.删除pos之后的结点

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);

	//pos pos->next pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
}

删除pos之后的结点这段代码中没有遍历循环，时间复杂度为O(1)。

思路分析：

（1）assert断言判断pos和pos->next这两地址是否为空，若为空则报错，不为空则继续运行；

（2）将pos->next赋值到del中，先让pos->next往后走一个结点，再释放del结点。

测试用例运行结果：

13.销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

销毁链表这段代码中有一层遍历循环，时间复杂度为O(n)。

思路分析：

（1）assert断言判断pphead（头结点的地址的地址）和*pphead（头结点的地址）这两地址是否为空，若为空则报错，不为空则继续运行；

（2）保存头结点地址为pcur，通过while的循环条件判断pcur是否为空，若不为空则进入循环；

（3）进入循环后，将pcur->next赋值给next这个指针变量，再释放pcur这个结点空间，同时将pcur后移到下一个结点；

（4）若while的循环条件判断pcur为空，则跳出循环，直接将头结点置为NULL。

根据调试监视窗口一步一步的进行，可知链表的成功销毁：

测试用例运行结果：

二、完整实现单链表的三个文件

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义链表（结点）的结构

//typedef定义类型。方便后期一键替换
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//打印链表的函数
void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDestroy(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(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = NULL;
	//新申请的结点初始化默认指向为空

	return node;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//pphead -> &plist
	// *pphead -> plist
	//申请新的结点
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾结点
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		//pcur newnode
		pcur->next = newnode;
	}
}


//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//申请新的结点
	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表为空：不可以删除
	assert(pphead && *pphead);
	//处理只有一个结点的情况：要删除的就是头结点
	if ((*pphead)->next == NULL)//此处要加小括号的原因是箭头的解引用操作符的优先级高于*解引用操作符
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找 prev  ptail
		SLTNode* ptail = *pphead;
		SLTNode* prev = NULL;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}


//头删
//第一种写法：先释放再改头结点。
void SLTPopFront(SLTNode** pphead) 
{
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;
	//*pphead --> next
	free(*pphead);
	*pphead = next;
}

//第二种写法：先改头结点，再释放。
//void SLTPopFront(SLTNode** pphead)
//{
//	assert(pphead && *pphead);
//
//	SLTNode* del = *pphead;
//	*pphead = (*pphead)->next;
//	free(del);
//	del = NULL;
//}


//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}


//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		//找prev：pos的前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev  newnode --> pos
		newnode->next = pos;
		prev->next = newnode;
	}
}


//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
//因为在指定位置之后插⼊数据用不到头结点（用不到前驱结点），只需用pos->next,所以没有**pphead这个形参
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	//pos newnode-->pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}


//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);

	//头删
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);

	//pos pos->next pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
}


//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include<SList.h>
//创建一个链表，并打印链表

void createSList()
{
	//链表是由一个一个的结点组成的
	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;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	//第一个结点的地址作为参数传递过去
	SLTNode* plist = node1;
	SLTPrint(plist);
	//也可以直接这样写：SLTPrint(node1);
}

void SListTest01()
{
	//尾插
	//SLTNode* plist = NULL;
	//SLTPushBack(&plist, 1);
	//SLTPrint(plist);//1->NULL
	//SLTPushBack(&plist, 2);
	//SLTPushBack(&plist, 3);
	//SLTPrint(plist);//1->2->3->NULL

	//SLTPushBack(NULL, 3);

	//头插
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);//4->3->2->1->NULL

	//尾删
	//SLTPopBack(&plist);
	//SLTPrint(plist);//4->3->2->NULL
	//SLTPopBack(&plist);
	//SLTPrint(plist);//4->3->NULL
	//SLTPopBack(&plist);
	//SLTPrint(plist);//4->NULL
	//SLTPopBack(&plist);
	//SLTPrint(plist);

	//SLTPopBack(&plist);
	//SLTPrint(plist);

	//头删
	/*SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);*/

	//查找
	SLTNode* find = SLTFind(plist, 4);
	//if (find == NULL)
	//{
	//	printf("未找到！\n");
	//}
	//else
	//{
	//	printf("找到了！\n");
	//}
	// 在指定位置之前插入数据
	//SLTInsert(&plist, find, 11);
	//SLTPrint(plist);//11->4->3->2->1->NULL

	//在指定位置之后插入数据
	//SLTInsertAfter(find, 11);
	//SLTPrint(plist);//4->3->2->1->11->NULL

	//删除pos结点
	/*SLTErase(&plist, find);*/
	/*SLTEraseAfter(find);
	SLTPrint(plist);*/

	//销毁链表
	SListDestroy(&plist);
	SLTPrint(plist);
}

int main()
{
	//createSList();
	SListTest01();
	return 0;
}

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2302_80871796/article/details/142616739

C_单链表的实现 —— 创建一个链表、打印链表的函数、申请新结点、尾插、头插、尾删、头删、查找、在指定位置之前和之后分别插入数据、删除pos或pos之后的结点、销毁链表

一、单链表

1、概念与结构

1.结点

2.链表的性质

3.链表的打印

2、单链表的实现

1.创建一个链表（一般不会这样使用，了解就好）

2.打印链表的函数

3.申请新结点（最为重要的一步）

4.尾插

5.头插

6.尾删

7.头删

8.查找

9.在指定位置之前插入数据

10.在指定位置之后插入数据

11.删除pos结点

12.删除pos之后的结点

13.销毁链表

二、完整实现单链表的三个文件

SList.h

SList.c

test.c

评论

评论列表

微信小程序

QQ小程序

关于作者