C语言单链表

 

 链表详解

🍐链表的概念

概念:链表是一种物理存储结构非连续、非顺序的存储结构,但链表在逻辑上连续的,顺序的,而数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

此时链表就像一个火车,由一个个节点连接起来,且节点是无序的,每一个车厢可以切换和插入去除(节点的插入和删除)。

 

 🍉链表的结构组成:节点

🔑链表是由一个个节点组成的。

🔑节点由俩个部分组成。

▶一部分用来存储数据,

▶另一部分用来存储下一个节点的地址。

🔑注意:节点在内存中是散乱分布的,它们是通过地址来寻找下一个节点。这和数组的连续存储有着很大的区别。

 

 🍓链表节点的连接(逻辑结构与物理结构的区分)

💦链表的逻辑结构图:

注意:此时的链表是我们人为想象出来的,是为了让大家更好的去理解链表,现实中并不存在箭头,并且现实中每一个节点的地址都不一定连续,而且可能会离得很远。

💦链表的物理结构图:

总结:通过上面两个结构图,我们清楚的了解到,链表其实是通过指针地址来依次找到每一个节点。这也就是大家经常说的链表只在逻辑结构上连续(方便理解)在物理结构上不连续(实际情况)。

 

 🍌链表的分类

1、单向或者双向

2、带头或者不带头

3、循环或者非循环

注意:我们经常使用的链表主要是单链表带头双向循环链表,一个结构最简单,一个结构最复杂

这里就给打击简单介绍一下这两种链表的特点以及用处:

无头单向非循环链表:也就是我们俗称的单链表。其结构简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构,如哈希桶、栈的链式结构等。因为单链表本身有缺陷,所以为常见的考核点之一

带头双向循环链表:结构最复杂,一般用来单独存储数据。实际使用的链表,大多都是带头双向循环链表。虽然这种链表结构最复杂,但是其实有很多优势,并且在一定程度上对单链表的缺陷做出了一定的纠正。

这里先从结构最简单的单链表开始讲解!

 

🍊单链表各个接口的实现

这里先建立三个文件:

1️⃣ :SList.h文件,用于函数声明

2️⃣ :SList.c文件,用于函数的定义

3️⃣ :Test.c文件,用于测试函数

建立三个文件的目的: 将单链表作为一个项目来进行书写,方便我们的学习与观察。

 ⭕接口1:定义结构体SLTNode

🔑单链表的结构体由两个部分组成:

▶一部分用来存储数据,

▶另一部分用来存储下一个节点的地址。

typedef int SLTDataType;   //数据类型
typedef struct SListNode 
{
	int data;                 // 每一个节点上存储的数据
	struct SListNode* next;   // 在结构体内定义指针,用的时候需要开辟新的空间 ,在堆上开辟新的空间
	// 注意:这个 next指向的是结构体本身 的地址  ----> 在链表里面 此时 next 指向下一个结构体的地址。
}SLTNode;

 ⭕接口2:创建一个新的节点(SLTNode* BuySLTNode

🔑函数原理:在堆上开辟一个新的空间,用于存放新的数据和下一个节点的地址

// 单链表创建一个新节点
// 此时返回的是 newnode (newnode是结构体指针,所以函数名为:SLNode* BuySLTNode(int x)) 
// 此时是一个传值调用(函数的形参与实参的转换)
SLTNode* BuySLTNode(SLTDataType x)
{
	// 1.开辟出结构本身的 内存空间   将空间地址 存放在 指针变量(结构体指针)newnode 中
	// 2.此时每一个结构体的 地址就完成了赋值
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); // 为这个结构体开辟空间并将首地址传递给结构体指针
	if (newnode == NULL)   // 如果为空,表示申请失败
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;    // 将这个节点的值,存放进去
	newnode->next = NULL; // 将这个节点的地址先设置为空,为后续的 节点二做准备(因为一般情况下next里面存放的是下一个节点的地址)
	return newnode;       // 返回开辟的结构体本身的地址 
}

 ⭕接口3:单链表创建连续的节点(SLTNode* CreateSlist

🔑函数原理:根据接口2,形成一个完成的单链表

// 单链表创建连续的节点
SLTNode* CreateSlist(int n)
{
	SLTNode* phead = NULL;
	SLTNode* ptail = NULL;  //用于保存头节点
	for (int i = 0; i < n; i++)
	{
		SListNode* newnode = BuySLTNode(i);  //创建一个新的节点
		if (phead == NULL)
		{
			ptail = phead = newnode;    //开始在头节点的时候将    结构体指针 ptail,phead都指向 第一个创建的节点 
		}
		else                            // 当判断此时这个节点不是头节点的时候
		{
			ptail->next = newnode;      // 先把此时这个节点的 新地址mewnode 传给next  以便于他们连接起来
			ptail = newnode;            // 再把指针ptail 转移到这个节点,依次往后推,就形成了一条来链子一样的链表 
		}
	}
	return phead;   // 返回头指针
}    // 注意 :在局部变量里面的 phead 和 ptail 出了局部变量之后就会被销毁

 ⭕接口4:单链表的尾插(SLTPushBack

🔑函数原理:在链表的尾部插入数据们需要考虑两点,当链表为空时直接插入。若链表不为空,先找到尾部在进行插入。

// 尾插
// 传址调用
// &plist=pphead  *(&plist)=*pphead=plist  *(*(&plist))=**pphead
// 注意:pphead 是 plist 的拷贝 ------ pphead 的改变plist是不会改变的
void SLTPushBack(SLTNode** pphead, SLTDataType x)   // pphead 是 plist的地址   ,*pphead 就是 plist, **pphead就是plist地址里面存放的东西
{
	// assert(phead);  此处不能进行断言,因为空链表也可以进行尾插
	SLTNode* newnode = BuySLTNode(x); //新插入的数据,和数据的地址
	if (*pphead == NULL)   //判断是头节点是否为空
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;  // 找尾巴
		while (tail->next != NULL)  // 注意:我们此时寻找的是 指向下一个地址的 next 
		{
			tail = tail->next;     // tail向后移动一位
		}
		tail->next = newnode;   // 将新的节点插入在尾部 同时 BuySTLNode(x) 将会是最后一个 next 指向空.
	}
}

注意:此时需要大家重视的是函数的二级指针传参问题,大家可以参考我上一篇文章,对函数的形参,实参的的深度理解。

⭕接口5:单链表的尾删(SLTPopBack

🔑函数原理:和单链表的尾插一样分两步进行

//  尾删
void SLTPopBack(SLTNode** pphead)
{
	// 暴力检查
	assert(*pphead);     // 防止链表已经删除完了,继续删除(空链表就不能尾删了)
 
	//温柔检查
	/*if (*pphead = NULL)
	{
		return;
	}*/
	if ((* pphead)->next == NULL)  //只有一个节点单独处理
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;      
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);   //删除尾节点,将其从空间中除去
		tail->next = NULL;  // 防止野指针的出现
	}
}

⭕接口6:单链表的头插(SLTPushFront

🔑函数原理:创建一个新的节点,接在原有的链表上即可

// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);  //创建一个新的节点
	newnode->next = *pphead;           //把原来的头节点给与next
	*pphead = newnode;                 //把新创建得节点变成头节点
}

 ⭕接口7:单链表的头删( SLTPopFront

🔑函数原理:需要进行断言,判断函数头节点是否为空,同时保存第二个节点的地址

// 头删         注意:插入都不需要断言,删除需要断言,防止要删除得第一个为空
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead); //断言
	SLTNode* next = (*pphead)->next; //先保存第二个节点得地址
	free(*pphead);
	*pphead = next;  //将第二个节点地址,变为头节点地址
}

⭕接口8:单链表的节点查找( SLTNode* SLTFind

🔑函数原理:进行链表的遍历查找即可

// 链表的查找  ---- 返回一个地址
// 有返回值,此时是传值调用
// 因为返回值是结构体里面的成员,所以返回函数为SLTNode* SLFind()
// 实参传过来的是一个头节点地址,所以接收也是用指针形参接收
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;  //保存头节点
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

⭕接口9:单链表在pos位置之后插入数据x( SLTInsertAfter

🔑函数原理:根据接口9先找到pos的位置,在进行插入即可

// 单链表在pos位置之后插入x
// 注意:此时改变的是结构体的成员--->next地址,并没有改变实际的数值
void SLTInsertAfter(SLTNode* p, SLTDataType x) //此时这里的 *p 是pos节点的地址
{
	assert(p);  //检查 p 是否为空
	SLTNode* newnode = BuySLTNode(x);  // 创建一个新的节点
	newnode->next = p->next;           // 把原本pos下一个节点的位置传给newnode->next
	p->next = newnode;                 // 再把newnode设置为pos位置的next
}

⭕接口10:单链表在pos位置之前插入数据x( SLTInsert

🔑函数原理:此时需要判断Pos的位置是否在头节点处,分情况处理

//在pos之前插入x
// &plist=pphead  *(&plist)=*pphead=plist  *(*(&plist))=**pphead
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);  // 判断pos是否存在
	if(*pphead==pos)  //如果pos就是头节点
	{
		SLTPushFront(pphead, x);  //头插函数
	}
	else    //pos不是头节点
	{
		SLTNode* prev = *pphead; //保存头节点
		while (prev->next != pos)  //找到pos之前的位置
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);  //新建一个节点
		prev->next = newnode;
		newnode->next = pos;
	}
}

⭕接口11:删除单链表中pos位置之后的数据( SLTEraseAfter

🔑函数原理:找到pos位置,进行删除即可

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);   // 检查pos位置是否存在
	if (pos->next == NULL)  //判断pos位置之后是否为空
	{
		return;   //若是空,什么都不做
	}
	else
	{
		SLTNode* nextNode = pos->next;  //此时需要将pos的next的地址换掉
		pos->next = nextNode->next;
		free(nextNode);
	}
}

 ⭕接口12:删除单链表中pos位置的数据( SLTErase

🔑函数原理:需要进行判断pos是否在头节点,分情况进行

//删除pos位置
// &plist=pphead  *(&plist)=*pphead=plist  *(*(&plist))=**pphead
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);   //判断pos是否存在
	if (pos == *pphead)    //如果pos位置在头部就是头删
	{
		SLTPopFront(pphead);
	}
	else
	{ 
		SLTNode* prev = *pphead;  //保存头节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

⭕接口13:单链表的数值打印( SLTPrint

// 单链表的数值打印
void SLTPrint(SLTNode* phead)   // 这里的phead 与上边的phead 是不一样的
{
	// assert(phead);  此处不能进行断言,因为空链表也可以进行打印
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		//printf("%d-> ", cur->data);  //打印出头节点的值
		//printf("\n");
		printf("%d->", cur->data);
		// 继续走向下一个节点
		// 因为每一个节点的 next 都是指向下一个节点的地址
		// 所以此时,将第一个节点的 next 传给 cur 就走向了下一个节点,直到最后一个节点 next 为空结束
		cur = cur->next;
	}
	printf("NULL\n");
}

⭕接口14:单链表的销毁( SLTDestory

// 单链表的销毁
// 注意:顺序表是申请的一大块空间,销毁时就直接销毁了
// 注意:但是单链表是一个节点一个节点申请的,所以释放的时候也需要一个一个释放
// &plist=pphead  *(&plist)=*pphead=plist   *(*(&plist))=**pphead
void SLTDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;   //保存头节点
	while (cur != NULL)
	{
		SLTNode* next = cur->next; //先保存下一个地址,在释放,防止到不到下一个地址
		free(cur);
		cur = next;
	}
	*pphead = NULL;  // 将头指针制空,防止野指针出现,虽然释放了,但是地址依然存在,防止继续访问野指针
}

 三、单链表的完整代码

🍇SList.h

#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
 
typedef int SLTDataType; //数据类型
typedef struct SListNode 
{
	int data;                 // 每一个节点上存储的数据
	struct SListNode* next;   // 在结构体内定义指针,用的时候需要开辟新的空间  ,在堆上开辟新的空间
	// 注意:这个 next指向的是结构体本身 的地址  ----> 在链表里面 此时 next 指向下一个结构体的地址。
}SLTNode;
 
void SLTDestory(SLTNode** pphead); // 单链表的销毁
 
SLTNode* BuySLTNode(SLTDataType x);  // 将数据放在节点中,并返回节点的地址-----创建一个新节点.
 
SLTNode* CreateSlist(int n);        // 创建做需要的 节点个数 
 
void SLTPrint(SLTNode* phead);   // 打印输出单链表中的节点
 
void SLTPushBack(SLTNode** pphead, SLTDataType x);  // 尾插
 
void SLTPushFront(SLTNode** pphead, SLTDataType x); // 头插
 
void SLTPopBack(SLTNode** pphead);       // 尾删
 
void SLTPopFront(SLTNode** pphead);     // 头删
 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);  //单链表的查找
 
// 分析思考为什么不在pos位置之前插入呢?
void SLTInsertAfter(SLTNode* pos, SLTDataType x); //单链表在pos位置之后插入x
 
// 分析思考为什么不删除pos位置
void SLTEraseAfter(SLTNode* pos); //单链表删除pos位置之后的值
 
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);  //在pos之前插入x
 
void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos位置
 
// 总结:1.改变int,传递int* 给形参,*形参进行交换改变
//      2.改变int*,传递给int**给形参,*形参进行交换改变
 
//在数组中 [] 其实是解引用的意思

🍋SList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
 
// 什么时候用到二级指针 :当需要改写时候进行使用
// 当程序只是进行 读 的时候就不需要用到二级指针
 
// 单链表的销毁
// 注意:顺序表是申请的一大块空间,销毁时就直接销毁了
// 注意:但是单链表是一个节点一个节点申请的,所以释放的时候也需要一个一个释放
// &plist=pphead  *(&plist)=*pphead=plist   *(*(&plist))=**pphead
void SLTDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;   //保存头节点
	while (cur != NULL)
	{
		SLTNode* next = cur->next; //先保存下一个地址,在释放,防止到不到下一个地址
		free(cur);
		cur = next;
	}
	*pphead = NULL;  // 将头指针制空,防止野指针出现,虽然释放了,但是地址依然存在,防止继续访问野指针
}
 
// 单链表创建一个新节点
// 此时返回的是 newnode (newnode是结构体指针,所以函数名为:SLNode* BuySLTNode(int x)) 
// 此时是一个传值调用(函数的形参与实参的转换)
SLTNode* BuySLTNode(SLTDataType x)
{
	// 1.开辟出结构本身的 内存空间   将空间地址 存放在 指针变量(结构体指针)newnode 中
	// 2.此时每一个结构体的 地址就完成了赋值
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); // 为这个结构体开辟空间并将首地址传递给结构体指针
	if (newnode == NULL)   // 如果为空,表示申请失败
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;    // 将这个节点的值,存放进去
	newnode->next = NULL; // 将这个节点的地址先设置为空,为后续的 节点二做准备(因为一般情况下next里面存放的是下一个节点的地址)
	return newnode;       // 返回开辟的结构体本身的地址 
}
 
// 单链表创建连续的节点
SLTNode* CreateSlist(int n)
{
	SLTNode* phead = NULL;
	SLTNode* ptail = NULL;  //用于保存头节点
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);  //创建一个新的节点
		if (phead == NULL)
		{
			ptail = phead = newnode;    //开始在头节点的时候将    结构体指针 ptail,phead都指向 第一个创建的节点 
		}
		else                            // 当判断此时这个节点不是头节点的时候
		{
			ptail->next = newnode;      // 先把此时这个节点的 新地址mewnode 传给next  以便于他们连接起来
			ptail = newnode;            // 再把指针ptail 转移到这个节点,依次往后推,就形成了一条来链子一样的链表 
		}
	}
	return phead;   // 返回头指针
}    // 注意 :在局部变量里面的 phead 和 ptail 出了局部变量之后就会被销毁
 
// 单链表的数值打印
void SLTPrint(SLTNode* phead)   // 这里的phead 与上边的phead 是不一样的
{
	// assert(phead);  此处不能进行断言,因为空链表也可以进行打印
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		//printf("%d-> ", cur->data);  //打印出头节点的值
		//printf("\n");
		printf("%d->", cur->data);
		// 继续走向下一个节点
		// 因为每一个节点的 next 都是指向下一个节点的地址
		// 所以此时,将第一个节点的 next 传给 cur 就走向了下一个节点,直到最后一个节点 next 为空结束
		cur = cur->next;
	}
	printf("NULL\n");
}
 
// 尾插
// 传址调用
// &plist=pphead  *(&plist)=*pphead=plist  *(*(&plist))=**pphead
// 注意:pphead 是 plist 的拷贝 ------ pphead 的改变plist是不会改变的
void SLTPushBack(SLTNode** pphead, SLTDataType x)   // pphead 是 plist的地址   ,*pphead 就是 plist, **pphead就是plist地址里面存放的东西
{
	// assert(phead);  此处不能进行断言,因为空链表也可以进行尾插
	SLTNode* newnode = BuySLTNode(x); //新插入的数据,和数据的地址
	if (*pphead == NULL)   //判断是头节点是否为空
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;  // 找尾巴
		while (tail->next != NULL)  // 注意:我们此时寻找的是 指向下一个地址的 next 
		{
			tail = tail->next;     // tail向后移动一位
		}
		tail->next = newnode;   // 将新的节点插入在尾部 同时 BuySTLNode(x) 将会是最后一个 next 指向空.
	}
}
 
//  尾删
void SLTPopBack(SLTNode** pphead)
{
	// 暴力检查
	assert(*pphead);     // 防止链表已经删除完了,继续删除(空链表就不能尾删了)
 
	//温柔检查
	/*if (*pphead = NULL)
	{
		return;
	}*/
	if ((* pphead)->next == NULL)  //只有一个节点单独处理
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;      
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);   //删除尾节点,将其从空间中除去
		tail->next = NULL;  // 防止野指针的出现
	}
}
 
// ******* 单链表的优势就在于 头删和头插 **********
//  注意:插入都不需要断言,删除需要断言,防止要删除得第一个为空
// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);  //创建一个新的节点
	newnode->next = *pphead;           //把原来的头节点给与next
	*pphead = newnode;                 //把新创建得节点变成头节点
}
 
// 头删         注意:插入都不需要断言,删除需要断言,防止要删除得第一个为空
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead); //断言
	SLTNode* next = (*pphead)->next; //先保存第二个节点得地址
	free(*pphead);
	*pphead = next;  //将第二个节点地址,变为头节点地址
}
 
// 链表的查找  ---- 返回一个地址
// 有返回值,此时是传值调用
// 因为返回值是结构体里面的成员,所以返回函数为SLTNode* SLFind()
// 实参传过来的是一个头节点地址,所以接收也是用指针形参接收
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;  //保存头节点
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
// 单链表在pos位置之后插入x
// 注意:此时改变的是结构体的成员--->next地址,并没有改变实际的数值
void SLTInsertAfter(SLTNode* p, SLTDataType x) //此时这里的 *p 是pos节点的地址
{
	assert(p);  //检查 p 是否为空
	SLTNode* newnode = BuySLTNode(x);  // 创建一个新的节点
	newnode->next = p->next;           // 把原本pos下一个节点的位置传给newnode->next
	p->next = newnode;                 // 再把newnode设置为pos位置的next
}
 
//在pos之前插入x
// &plist=pphead  *(&plist)=*pphead=plist  *(*(&plist))=**pphead
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);  // 判断pos是否存在
	if(*pphead==pos)  //如果pos就是头节点
	{
		SLTPushFront(pphead, x);  //头插函数
	}
	else    //pos不是头节点
	{
		SLTNode* prev = *pphead; //保存头节点
		while (prev->next != pos)  //找到pos之前的位置
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);  //新建一个节点
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
//单链表删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);   // 检查pos位置是否存在
	if (pos->next == NULL)  //判断pos位置之后是否为空
	{
		return;   //若是空,什么都不做
	}
	else
	{
		SLTNode* nextNode = pos->next;  //此时需要将pos的next的地址换掉
		pos->next = nextNode->next;
		free(nextNode);
	}
}
 
//删除pos位置
// &plist=pphead  *(&plist)=*pphead=plist  *(*(&plist))=**pphead
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);   //判断pos是否存在
	if (pos == *pphead)    //如果pos位置在头部就是头删
	{
		SLTPopFront(pphead);
	}
	else
	{ 
		SLTNode* prev = *pphead;  //保存头节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

🥝Test.c

#define  _CRT_SECURE_NO_WARNINGS 1
// -------   单链表  ----------//
 
// 顺序表的缺陷:
// 1. 空间不够,需要扩容 (realloc)
// 扩容 (尤其是异地扩容) 是有一定的代价的。
// 其次还可能存在一定的空间浪费
// 2.头部或者中部的插入删除,需要挪动数据,效率低下.
 
// 改进优化: (链表的出现)
// 1. 按需申请释放.(按照需求去申请释放)(用指针将他们连接起来)
// 2. 不要挪动数据.
// 3. 存储数据的空间叫做节点(结点)
 
#include "SList.h"
 
// 创建一个链表----进行每一个节点的测试
void TestSList1()
{
	// BuySLTNode()函数 :求出每一个节点的地址
	// SLTNode * n :表示指针变量,将每个节点的地址传给指针变量
	// 也就是说,每次都是不同的结构体,但是每一个结构体的类型都是相同的
	/*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;*/
 
	// 例如创建一个 n 个节点的链表
	SLTNode* plist = CreateSlist(4);   // 此时就创建了 一个链表 有4个链子
	SLTPrint(plist);  // 0->1->2->3->NULL
}
 
// 创建一个链表,并且进行尾插的测试
void TestSList2()
{
	SLTNode* plist = CreateSlist(4);   // 此时就创建了 一个链表 有4个链子
	SLTPushBack(&plist, 100);
	SLTPrint(plist);  // 0->1->2->3->100->NULL
	SLTDestory(&plist); //进行销毁单链表
	SLTPrint(plist);
}
// 不创建链表,直接进行尾插.
void TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPrint(plist);
}
 
// 尾删.
void TestSList4()
{
	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 TestSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPrint(plist);
 
	SLTPushFront(&plist, 20);
	SLTPrint(plist);
}
// 头删  (头删是单链表的优势).
void TestSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPrint(plist);
 
	SLTPopFront(&plist);
    SLTPrint(plist);
}
// 单链表的查找.
void TestSList7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPrint(plist);
 
	SLTNode* pos = SLTFind(plist, 300);
	if (pos != NULL)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
	SLTPrint(pos);
}
// 单链表在pos位置之后插入数据.
void TestSList8()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPrint(plist);
 
	SLTNode* pos = SLTFind(plist, 200);
	if (pos != NULL)
	{
		SLTInsertAfter(pos, 30);  // 插入数据30.
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
	SLTPrint(plist);
}
// 单链表在pos位置之前插入数据.
void TestSList9()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPushBack(&plist, 500);
	SLTPrint(plist);
 
	SLTNode* pos = SLTFind(plist, 300);
	if (pos != NULL)
	{
		SLTInsert(&plist,pos, 30);  // 插入数据30.
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
	SLTPrint(plist);
}
// 单链表删除pos位置之后的节点.
void TestSList10()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPushBack(&plist, 500);
	SLTPrint(plist);
 
	SLTNode* pos = SLTFind(plist, 500);
	if (pos != NULL)
	{
		SLTEraseAfter(pos);  // 删除pos位置之后的数据.
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
	SLTPrint(plist);
}
// 单链表中删除pos位置
void TestSList11()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPushBack(&plist, 500);
	SLTPrint(plist);
 
	SLTNode* pos = SLTFind(plist, 300);
	if (pos != NULL)
	{
		SLTErase(&plist, pos);  // 删除pos位置之后的数据.
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
	SLTPrint(plist);
}
void menu()
{
	printf("***********************************************************\n");
	printf("1、头插节点                          2、头删节点   \n");
	printf("\n");
	printf("3、尾插节点                          4、尾删节点   \n");
	printf("\n");
	printf("5、在单链表中查找pos数据             6、在单链表pos位置之后插入一个新的节点\n");
	printf("\n");
	printf("7、删除单链表pos位置之后的节点       8、在单链表pos位置之前插入新的节点 \n");
	printf("\n");
	printf("9、在单链表中删除pos位置的数据       10、打印数据   \n");
	printf("\n");
	printf("-1、退出                                             \n");
	printf("***********************************************************\n");
 
}
int main()
{
	printf("***************  欢迎大家来到单链表的测试  ****************\n");
	int option = 0;
	SLTNode* plist = NULL;
	SLTNode* pos = NULL;
	do
	{
		menu();
		printf("请输入你的操作:>");
		scanf("%d", &option);
		int sum = 0;  
		int x = 0;
		int y = 0;
		int z = 0;
		int w = 0;
		int a = 0;
		int b = 0;
		int c = 0;
		int d = 0;
		switch (option)
		{
		case 1:
			printf("请依次输入你要尾插的数据:,以-1结束\n");
			scanf("%d", &sum);
			while (sum != -1)
			{
				SLTPushBack(&plist, sum);    // 1.头插
				scanf("%d", &sum);
			}
			break;
		case 2:
			SLTPopFront(&plist);            // 2.头删
			break;
		case 3:
			printf("请输入想要尾插的数据:");
			scanf("%d", &x);                // 3.尾插
			SLTPushBack(&plist, x);
			break;
		case 4:
			SLTPopBack(&plist);             // 4.尾删
			break;
		case 5:         
			printf("请输入想要查找的pos数据:");
			scanf("%d", &y);
		    pos = SLTFind(plist, y);
			if (pos != NULL)                // 5.在单链表中查找pos数据
			{
				printf("找到了\n");
			}
			else
			{
				printf("找不到pos位置\n");
			}
			break;
		case 6:                             // 6.在单链表pos位置后插入一个新的节点
			printf("请输入想要查找的pos数据:");
			scanf("%d", &z);
		    pos = SLTFind(plist, z);
			if (pos != NULL)
			{
				printf("请输入想要在pos位置后插入的数据:");
				scanf("%d", &w);
				SLTInsertAfter(pos, w);  // 插入数据w.
			}
			else
			{
				printf("找不到pos位置,无法插入\n");
			}
			break;
		case 7:
			printf("请输入想要查找的pos数据:");
			scanf("%d", &a);
			pos = SLTFind(plist, a);    
			if (pos != NULL)
			{
				SLTEraseAfter(pos);  // 7.删除pos位置之后的数据.
			}
			else
			{
				printf("找不到pos位置,无法删除\n");
			}
			break;
		case 8:
			printf("请输入想要查找的pos数据:");
			scanf("%d", &b);
		     pos = SLTFind(plist, b);
			if (pos != NULL)
			{
				printf("请输入想要在pos位置后插入的数据:");
				scanf("%d", &c);
				SLTInsert(&plist, pos, c);  // 在单链表pos位置之前插入数据c.
			}
			else
			{
				printf("找不到pos位置,无法插入\n");
			}
			break;
		case 9:
			printf("请输入想要查找的pos数据:");
			scanf("%d", &d);
			 pos = SLTFind(plist, d);
			if (pos != NULL)
			{
				SLTErase(&plist, pos);  // 删除pos位置的数据.
			}
			else
			{
				printf("找不到pos位置,无法删除\n");
			}
		case 10:
			SLTPrint(plist);
			break;
		default:
			if (option == -1)
			{
				exit(0);  // 退出程序 
			}
			else
			{
				printf("输入错误,请重新输入\n");
			}
			break;
		}
	} while (option != -1);
	return 0;
}

🍍代码运行的菜单界面

以下就是我对单链表的理解,如果有发现问题和见解的小伙伴,欢迎在评论区指出!

阅读剩余
THE END