关于单链表的增删查改等操作（c语言版）

1、关于单链表

2.单链表的优缺点

3.单链表的初始化

4.申请新结点

5.关于单链表的插入（尾插）

6.单链表的头插

7.单链表的尾删

7.单链表的头删

8.单链表的查找

9.在某一的数字的前面插入新数据

10.在某一结点之后插入数据

11.删除某个结点

12.打印单链表

13.销毁单链表

完整代码如下（含菜单）

后言

1、关于单链表
顺序表的插入删除操作需要移动大量的元素，影响了运行效率，因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

2.单链表的优缺点
优点：1.按需申请空间，不用则释放，较为灵活。

2.相较于顺序表，对于头/中部的数据插入删除操作无需移动数据。

缺点：1.每有一个数据都需要一指针链接之后的结点。

2.不支持随机访问。

3.单链表的初始化

typedef int SListData;//重定义数据类型，便于不同类型数据的存储

typedef struct SListNode
{
	SListData data;//数据域
	SListNode* next;//指针域，存储下一结点的地址

}SListNode;

4.申请新结点

由于对单链表插入数据时，总需要向内存动态申请一块空间存储数据及下一结点的地址，所以将的的此操作封装成函数，便于代码的简洁易读。

SListNode* BuySListNode()//申请一块空间并返回结点的指针
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//动态申请内存
	if (newnode == NULL)
	{
		printf(" SListPushBack::%s", strerror(errno));
		exit(-1);//申请空间失败，错误退出
	}
	newnode->data = 0;
	newnode->next = NULL;
	return newnode;
}

函数动作内容：动态申请内存后返回结点的指针，并将该结点的数据域初始化为零，指针域

初始化为NULL。

5.关于单链表的插入（尾插）

void SListPushBack(SListNode** pphead, int data)//单链表尾插
{
	SListNode* tail = *pphead;//将*p拷贝一份，便于可读性

	assert(pphead);//断言p不能为空，否则错误退出

	SListNode* newnode=BuySListNode();
	newnode->data = data;//完成新结点数据域的更新

	if (tail == NULL)//此时链表为空
	{
		*pphead = newnode;
	}
	else//单链表不为空
	{
		while (tail->next != NULL)//循环找到tail的指针域为空的结点
		{
			tail = tail->next;
		}
		tail->next = newnode;//将找到的tail指针域链接新申请的newnode
	}
}

assert：断言函数，若参数为假则中断程序并报错。pphead作为二级指针，在传递参数正确时不可能为NULL，一旦发生错误，则为传参错误，便于检验。

尾插可分两种情况讨论，第一：单链表为空，此时直接申请一块空间作为单链表的头部，此时链表的头指针需要发生变化为新申请的结点地址，为了保存新地址，因此我们需要二级指针作为参数来记忆新地址。第二：单链表不为空，则直接找到单链表的尾部，即指针域为NULL的结点，将新申请的newnode结点链接到单链表末尾。

6.单链表的头插

此操作较为简单，对于空表和有数据的单链表来说，头插只需要先将新申请的结点newnode指针域赋值于原始头指针，再将原来的头指针更新为新申请的空间即可（注意更新顺序，否则要在申请变量存储原始的头指针，防止数据的更新导致找不到原来的头结点）。

void SListPushFront(SListNode** pphead, int data)//单链表头插
{
	assert(pphead);

	SListNode* newnode = BuySListNode();//申请新结点后直接完成数据更新和链接即可
	newnode->data = data;
	newnode->next = *pphead;
	*pphead = newnode;
}

7.单链表的尾删

单链表的尾删要考虑三种情况。

第一：单链表为空，此时没有数据可以删除

第二：单链表只有一个结点，此时删除节点后，头结点释放并置空，因此要传入二级指针作为参数（传值和传址的区别）来记忆数据的更新。

第三：普通的多个结点的情况，此时只需要找到指针域为NULL的结点，但注意，我们需要的是删除最后一个结点，即倒数第二个结点的指针域需要置NULL来作为新的表尾。因此，我们需要利用定义一个指针来记住倒数第二个结点的pos。

void SListPopBack(SListNode** pphead)//单链表尾删
{
	assert(pphead);

	SListNode* tail = *pphead;
	if (tail == NULL)//表空的情况
	{
		printf("表空，无法删除n");
		return;
	}
//  assert(*pphead);//此时采取暴力的方式，即当表空时直接报错退出程序无法删除
	else
	{
		if (tail->next == NULL)//表中只有一个结点的情况
		{
			free(*pphead);
			*pphead = NULL;
			return;
		}
		else
		{
			SListNode* cur = 0;
			while (tail->next)
			{
				cur = tail;//以一个新的指针记住上一个结点的pos
				tail = tail->next;
			}
			free(tail);//释放最后一个结点
			tail = NULL;
			cur->next = NULL;//倒数第二个结点指针域置NULL
		}
	}
}

7.单链表的头删

我们对比单链表的头插就可知道，我们仅需要保证单链表不为空，即有数据可以删除时，只需要更新头结点的指针，并将原来的头结点释放即可。

void SListPopFront(SListNode** pphead)//单链表头删
{
	assert(pphead);

	SListNode* head = *pphead;
	if (head == NULL)//也可以利用assert暴力判断表空则程序错误退出报错
	{
		printf("表空，头删失败n");
		return;
	}
	else
	{
		*pphead = (*pphead)->next;//更新头结点
		free(head);
		head = NULL;
	}
}

8.单链表的查找

查找有两种返回值设置，一是返回所查找数据结点的位序，二是返回数据结点的指针，为了便于删除指定数据的接口设置，我们采用第二种方式。

第二，我们要注意当单链表中有多个相同数据时，我们设置一个printf函数来打印从查找的位置开始还存在多少个相同的数据。每次返回第一个该数据的指针，若需要查找下一个相同数字，则输入参数需要更正为第一个返回结点的下一个结点，没有找到则返回NULL。如图

SListNode* SListFind(SListNode* phead, int data)//查找某一个数字
{
	int count = 0;
	
	SListNode* least = NULL;
	SListNode* cur = phead;
	while(cur)
	{
		if (cur->data == data)
		{
			count++;
			if (count == 1)
				least = cur;
		}
		cur = cur->next;
	}
	if (count == 0)
		printf("未找到该数据%dn", data);
	else
		printf("共找到%d个%dn", count, data);
	return least;
}

9.在某一的数字的前面插入新数据

此时我们就需要复用查找接口找到pos，就可以较为简单的进行数据的插入了。

要考虑当pos位置在第一个结点时即头插，此时复用头插接口即可，其他情况则找到pos结点的位置，完成新结点的链接和上一节点指针域的更新就可以了。

使用方式如图：

void SListInsertFront(SListNode** pphead, SListNode* pos, int data)//连用定义的查找函数，在结点之前插入数据
{
	//已寻到结点，则链表不可能为空，也不可能插入不了，不用考虑多余的情况
	assert(pphead);

	SListNode* Front = *pphead;
	if (Front == pos)//即结点位置与链表头结点位置相同，即头插
	{
		SListPushFront(pphead, data);
		return;
	}

	SListNode* newnode= BuySListNode();//其他情况
	newnode->next = pos;//完成新结点的链接
	newnode->data = data;

	while (Front->next != pos)
	{
		Front = Front->next;
	}

	Front->next = newnode;//完成前一结点指针域的更新
	
}

10.在某一结点之后插入数据

由于存在结点，所以单链表不为空，即仅需要考虑找到指针域为NULL的结点，在链接上新申请的结点即可。

void SListInsertBack(SListNode** pphead, SListNode* pos, int data)//连用定义的查找函数，在结点之后插入数据
{
	//存在结点，则不考虑链表为空的情况
	//由于是在结点之后插入新结点，尾插的情况和在中间插入的情况时一样的
	SListNode* newnode = BuySListNode();
	newnode->data = data;
	
	newnode->next = pos->next;//即指针域置NULL（直接赋值NULL效果一样）
	pos->next = newnode;//简单的相互链接即可

}

11.删除某个结点

复用查找接口找到需要删除的结点，注意结点是否为第一个，此时为头删（原头指针要更新），否则直接进行链接即可（跳过指定结点的链接），并释放内存。

void SListErase(SListNode** pphead, SListNode* pos)//删除pos结点的数据
{
	//存在结点，不考虑无法删除的情况
	SListNode* cur = *pphead;
	
	if (pos== cur)//结点在第一位，进行头删
	{
		SListPopFront(pphead);
	}
	else//其他情况时，pphead都不会改变
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next= cur->next->next;
		free(pos);
		pos = NULL;
	}

12.打印单链表

遍历打印即可，注意表空的情况；

void SListPrint(SListNode* phead)//打印单链表
{
    if (phead == NULL)//表为空
	{
		printf("表空，无法打印n");
		return;
	}
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
    printf("NULLn");
}

13.销毁单链表

遍历释放每一个结点，头结点指针要改变，所以应该传参二级指针最好。

void SListDistroy(SListNode** pphead)//销毁单链表
{
	assert(pphead);//传参错误时直接错误退出 
	
	SListNode* end = *pphead;
	while (end)
	{
		SListNode* end1 = end;
		end = end->next;
		free(end1);
		end1 = NULL;
	}
	//printf("销毁成功n");
}

完整代码如下（含菜单）

Siglist.h

#include
#include
#include
#include
#include

enum
{
    exit1,
    pushback,
    pushfront,
    popback,
    popfront,
    find,
    insertfront,
    insertback,
    erase,
    print,
    distroy
};
typedef int SListData;

typedef struct SListNode
{
	SListData data;
	SListNode* next;

}SListNode;

SListNode* BuySListNode();//申请一块空间,返回新结点的地址

void SListPushBack(SListNode** pphead, int data);//单链表尾插

void SListPushFront(SListNode** pphead, int data);//单链表头插

void SListPopBack(SListNode** pphead);//单链表尾删

void SListPopFront(SListNode** pphead);//单链表头删

SListNode* SListFind(SListNode* phead, int data);//查找某一个数字，并返回其结点(若多个则返回多个结点并标识)，查找失败则返回NULL;
                                                 //若查找成功仅返回第一次出现时的结点，若查找多个，则再次调用本函数，且传入的参
                                                 //数为上一次查找成功返回结点的next成员(即从该结点的下一结点开始查找);

void SListInsertFront(SListNode** pphead, SListNode* pos, int data);//连用定义的查找函数，在结点之前插入数据
                                                                    //注：也可以通过复用查找函数的方式在某一个具体位置插入数据
                                                                    //    此时第二个参数可设置为(int num);

void SListInsertBack(SListNode** pphead, SListNode* pos, int data);//连用定义的查找函数，在结点之后插入数据(较为简单，直接插入即可)

void SListErase(SListNode** pphead, SListNode* pos);//删除pos结点的数据

void SListPrint(SListNode* phead);//打印单链表

void SListDistroy(SListNode** pphead);//销毁单链表

text.c

void menu()
{
	printf("**************************************************n");
	printf("*****0.退出并销毁链表1.尾插     2.头插    ********n");
	printf("********3.尾删       4.头删     5.查找    ********n");
	printf("********6.pos前插    7.pos后插  8.删除pos    *****n");
	printf("********9.打印             ***********************n");
}
int main()
{
	SListNode* sl= NULL;
	int input = 0;
	do
	{
		menu();
		printf("请选择:>");
		scanf("%d", &input);
		switch (input)
		{
		case exit1:
			SListDistroy(&sl);
			printf("退出成功n");
			break;
		case pushback:
		{
			SListData data = 0;
			printf("请输入想要尾插入的数据:>");
			scanf("%d", &data);
			SListPushBack(&sl, data);
			SListPrint(sl);
			break;
		}
		case pushfront:
		{
			SListData data = 0;
			printf("请输入想要头插入的数据:>");
			scanf("%d", &data);
			SListPushFront(&sl, data);
			SListPrint(sl);
			break;
		}
		case popback:
		{

			SListPopBack(&sl);
			SListPrint(sl);
			break;
		}
		case popfront:
		{
			SListPopFront(&sl);
			SListPrint(sl);
			break;
		}
		case find:
		{
			SListData data = 0;
			printf("请输入想要查找的数据:>");
			scanf("%d", &data);
			SListFind(sl, data);
			SListPrint(sl);
			break;
		}
		case insertfront:
		{
			int n = 0;
			int count = 0;
			SListData data = 0;
			SListData data1 = 0;
			printf("请输入你要输入的数据：n");
			printf("数据:>");
			scanf("%d", &data);
			printf("在什么数据前插入:>");
			scanf("%d", &data1);
			printf("第几个%d前面插入数据%d:>", data1, data);
			scanf("%d", &count);
			SListNode* pos = sl;
			while (count--)
			{
				if (n == 0)
					pos = SListFind(pos, data1);
				else
					pos = SListFind(pos->next, data1);
				n += 1;
			}
			SListInsertFront(&sl, pos, data);
			break;
		}
		case insertback:
		{
			int n = 0;
			int count = 0;
			SListData data = 0;
			SListData data1 = 0;
			printf("请输入你要输入的数据：n");
			printf("数据:>");
			scanf("%d", &data);
			printf("在什么数据后插入:>");
			scanf("%d", &data1);
			printf("第几个%d后面插入数据%d:>", data1, data);
			scanf("%d", &count);
			SListNode* pos = sl;
			while (count--)
			{
				if (n == 0)
					pos = SListFind(pos, data1);
				else
					pos = SListFind(pos->next, data1);
				n += 1;
			}
			SListInsertBack(&sl, pos, data);
			break;
		}
		case erase:
		{
			int count = 0;

			SListData data1 = 0;

			int n = 0;
			printf("请输入需要删除的结点数据:>");
			scanf("%d", &data1);
			printf("需要删除第几个%d:>", data1);
			scanf("%d", &count);
			SListNode* pos = sl;
			while (count--)
			{
				if (n == 0)
					pos = SListFind(pos, data1);
				else
					pos = SListFind(pos->next, data1);
				n += 1;
			}
			SListErase(&sl, pos);
			break;
		}
		case print:
			SListPrint(sl);
			break;
		
		default:
			printf("输入非法，请重新输入n");
			break;
		}
	} while (input);
}

Siglist.c

#include "SigList.h"

SListNode* BuySListNode()//申请一块空间并返回结点的指针
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//动态申请内存
	if (newnode == NULL)
	{
		printf(" SListPushBack::%s", strerror(errno));
		exit(-1);//申请空间失败，错误退出
	}
	newnode->data = 0;
	newnode->next = NULL;
	return newnode;
}

void SListPushBack(SListNode** pphead, int data)//单链表尾插
{
	SListNode* tail = *pphead;//将*p拷贝一份，便于可读性

	assert(pphead);//断言p不能为空，否则错误退出

	SListNode* newnode=BuySListNode();
	newnode->data = data;

	if (tail == NULL)//此时链表为空
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SListNode** pphead, int data)//单链表头插
{
	assert(pphead);

	SListNode* newnode = BuySListNode();
	newnode->data = data;
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopBack(SListNode** pphead)//单链表尾删
{
	assert(pphead);

	SListNode* tail = *pphead;
	if (tail == NULL)//表空的情况
	{
		printf("表空，无法删除n");
		return;
	}
	else
	{
		if (tail->next == NULL)//表中只有一个结点的情况
		{
			free(*pphead);
			*pphead = NULL;
			return;
		}
		else
		{
			SListNode* cur = 0;
			while (tail->next)
			{
				cur = tail;
				tail = tail->next;
			}
			free(tail);
			tail = NULL;
			cur->next = NULL;
		}
	}
}

void SListPopFront(SListNode** pphead)//单链表头删
{
	assert(pphead);

	SListNode* head = *pphead;
	if (head == NULL)
	{
		printf("表空，头删失败n");
		return;
	}
	else
	{
		*pphead = (*pphead)->next;
		free(head);
		head = NULL;
	}
}


SListNode* SListFind(SListNode* phead, int data)//
{
	int count = 0;
	
	SListNode* least = NULL;
	SListNode* cur = phead;
	while(cur)
	{
		if (cur->data == data)
		{
			count++;
			if (count == 1)
				least = cur;
		}
		cur = cur->next;
	}
	if (count == 0)
		printf("未找到该数据%dn", data);
	else
		printf("共找到%d个%dn", count, data);
	return least;
}

void SListPrint(SListNode* phead)//打印单链表
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("NULLn");


	//if (phead == NULL)//表为空
	//{
	//	printf("表空，无法打印n");
	//	return;
	//}
	//else
	//{
	//	while (1)
	//	{
	//		printf("%d -> ", phead->data);
	//		if (phead->next == NULL)
	//		{
	//			printf("NULLn");
	//			break;
	//		}
	//		phead = phead->next;
	//	}
	//}

}

void SListInsertFront(SListNode** pphead, SListNode* pos, int data)//连用定义的查找函数，在结点之前插入数据
{
	//已寻到结点，则链表不可能为空，也不可能插入不了，不用考虑多余的情况
	assert(pphead);

	SListNode* Front = *pphead;
	if (Front == pos)//即结点位置与链表头结点位置相同，即头插
	{
		SListPushFront(pphead, data);
		return;
	}

	SListNode* newnode= BuySListNode();
	newnode->next = pos;
	newnode->data = data;

	while (Front->next != pos)
	{
		Front = Front->next;
	}

	Front->next = newnode;
	
}

void SListInsertBack(SListNode** pphead, SListNode* pos, int data)//连用定义的查找函数，在结点之后插入数据
{
	//存在结点，则不考虑链表为空的情况
	//由于是在结点之后插入新结点，尾插的情况和在中间插入的情况时一样的
	SListNode* newnode = BuySListNode();
	newnode->data = data;
	
	newnode->next = pos->next;
	pos->next = newnode;//简单的相互链接即可

}

void SListErase(SListNode** pphead, SListNode* pos)//删除pos结点的数据
{
	//存在结点，不考虑无法删除的情况
	SListNode* cur = *pphead;
	
	if (pos== cur)//结点在第一位，进行头删
	{
		SListPopFront(pphead);
	}
	else//其他情况时，pphead都不会改变
	{
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next= cur->next->next;
		free(pos);
		pos = NULL;
	}
	
}

void SListDistroy(SListNode** pphead)//销毁单链表
{
	assert(pphead);//传参错误时直接错误退出 
	
	SListNode* end = *pphead;
	while (end)
	{
		SListNode* end1 = end;
		end = end->next;
		free(end1);
		end1 = NULL;
	}
	//printf("销毁成功n");
}

关于单链表的增删查改等操作（c语言版）

2.单链表的优缺点
优点：1.按需申请空间，不用则释放，较为灵活。

2.相较于顺序表，对于头/中部的数据插入删除操作无需移动数据。

缺点：1.每有一个数据都需要一指针链接之后的结点。

2.不支持随机访问。

3.单链表的初始化
typedef int SListData;//重定义数据类型，便于不同类型数据的存储 typedef struct SListNode { SListData data;//数据域 SListNode* next;//指针域，存储下一结点的地址 }SListNode;

12.打印单链表
遍历打印即可，注意表空的情况；

void SListPrint(SListNode* phead)//打印单链表 { if (phead == NULL)//表为空 { printf("表空，无法打印n"); return; } SListNode* cur = phead; while (cur) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULLn"); }

后言
新手上路，水平有限，可能会有未知bug,感谢指正。

C/C++/C#相关栏目本月热门文章

关于单链表的增删查改等操作（c语言版）

2.单链表的优缺点 优点：1.按需申请空间，不用则释放，较为灵活。 2.相较于顺序表，对于头/中部的数据插入删除操作无需移动数据。 缺点：1.每有一个数据都需要一指针链接之后的结点。 2.不支持随机访问。

3.单链表的初始化 typedef int SListData;//重定义数据类型，便于不同类型数据的存储 typedef struct SListNode { SListData data;//数据域 SListNode* next;//指针域，存储下一结点的地址 }SListNode;

12.打印单链表 遍历打印即可，注意表空的情况； void SListPrint(SListNode* phead)//打印单链表 { if (phead == NULL)//表为空 { printf("表空，无法打印n"); return; } SListNode* cur = phead; while (cur) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULLn"); }

后言 新手上路，水平有限，可能会有未知bug,感谢指正。

C/C++/C#相关栏目本月热门文章

2.单链表的优缺点
优点：1.按需申请空间，不用则释放，较为灵活。

2.相较于顺序表，对于头/中部的数据插入删除操作无需移动数据。

缺点：1.每有一个数据都需要一指针链接之后的结点。

2.不支持随机访问。

3.单链表的初始化
typedef int SListData;//重定义数据类型，便于不同类型数据的存储 typedef struct SListNode { SListData data;//数据域 SListNode* next;//指针域，存储下一结点的地址 }SListNode;

12.打印单链表
遍历打印即可，注意表空的情况；

void SListPrint(SListNode* phead)//打印单链表 { if (phead == NULL)//表为空 { printf("表空，无法打印n"); return; } SListNode* cur = phead; while (cur) { printf("%d -> ", cur->data); cur = cur->next; } printf("NULLn"); }

后言
新手上路，水平有限，可能会有未知bug,感谢指正。