C语言中单链表的基本操作(创建、销毁、增删查改等)_开发_开发者

链表分类

链表主要有下面三种分类方法：

单向或者双向
带头或者不带头
循环或者非循环综合来看链表有八种类型，本文主要针对的是不带头节点的非循环单链表。

单链表的介绍

typedef struct SListNode
{
	DataType data;//数据域
	struct SListNode *next;//结构体指针，指向下一个节点
}SListNode;//类型别名

如图

C语言中单链表的基本操作(创建、销毁、增删查改等)

链表的每一个节点由数据域和指针域构成，数据域存放数据，指针域中的指针指向下一个节点。

plist表示链表的指针，指向链表的第一个节点，最后一个节点的指针为空。

单链表的基本操作

创建

创建单链表有几点需注意：

链表与顺序表的区别是，顺序表是物理空间上连续的，而链表只在逻辑上连续，所以链表申请空间时是使用一个申请一个，顺序表则是一次申请一段空间，空间不足时进行扩容。
如果在栈上申请空间，在函数调用结束后会释放，所以需要在堆区申请空间。
每次申请一个节点都要存入数据，所以链表总是满的，而顺序表则可能有一段空间没有利用。
函数的返回值是指向节点的结构体类型的指针

SListNode* BuySListNode(DataType x)
{
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	if (plist == NULL)
	{
		return NULL;//判断是否申请成功
	}
	plist->data = x;
	plist->next = NULL;
	return plist;
}

打印

遍历链表，进行打印

void SListPrint(SListNode* plist)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d-->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

尾插

C语言中单链表的基本操作(创建、销毁、增删查改等)

尾插的操作步骤：

若链表为空，*pplist指向新插入的节点
链表不为空则遍历链表，找到最后一个节点
令最后一个节点的next指向新插入的节点
新插入的节点next指向NULL

注意事项：

因为插入元素要改变原链表中指针的指向，故传参时要传入二级指针。
assert(pplist)是判断链表是否存在，因为pplist是指向链表的指针的地址，若pplist为空，说明链表的地址不存在，即链表不存在；而如果(*pplist)为空，表示的是该链表是空链表。

void SListPushBack(SListNode** pplist, DataType x)
{
	//改变指针指向，参数传二级指针
	assert(pplist);//判断链表是否存在,与链表是否为空不同
	//1.若链表为空，*pplist指向插入的节点
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	else {
		//2.链表不为空，指针移动到链表最后一个节点，其next指向插入的节点
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;//cur的next为空时，cur指向最后一个节点
		}
		cur->next = BuySListNode(x);
	}
}

头插

C语言中单链表的基本操作(创建、销毁、增删查改等)

头插操作顺序：

申请一个新节点
新节点的next指向原来的第一个节点，即*pplist
改变*pplist指向，使其指向新增的节点

进行头插时，要注意各个步骤的顺序，如果直接令*pplist指向了新增的的节点，会导致原有的第一个节点无法找；另外，链表为空时的操作方法与链表非空时代码可以合并，不用再分开写各种情况。

void SListPushFront(SListNode** pplist, DataType x)
{
	assert(pplist);
	//if (NULL == *pplist)
	//{
	//	//链表为空
	//	*pplist = BuySListNode(x);
	//}
	//else
	//{
	//	SListNode* temp = *pplist;//temp指向链表原来的第一个节点
	//	*pplist = BuySListNode(x);//plist指向新增的节点
	//	(*pplist)->next = temp;//新增的节点指向原来的第一个节点
	//}
	//上面两种情况代码可以合并
	SListNode* node = BuySListNode(x);//申请一个新节点
	node->next = *pplist;//新增的节点的next指向原来的第一个节点
	*pplist = node;//*pplist指向新增的节点
}

尾删

C语言中单链表的基本操作(创建、销毁、增删查改等)

尾删步骤：

判断链表是否为空或只有一个结点
遍历找到最后一个节点的前驱结点prev
令prev的next指向NULL
释放原来最后一个节点申请的空间

注意事项：

区分链表为空、单个结点、多个结点各种情况
不能找到最后一个节点并将其置空，而是要找到其前驱节点，断开与最后一个节点的连接
删除节点后要释放空间，避免内存泄漏

void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	//1.链表为空
	if (NULL== *pplist)
	{
		return;
	}
	//2.链表只有一个元素
	else if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//3.链表有多个元素
	else
	{
		SListNode* prev = NULL; 
		SListNode* cur = *pplist;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;//循环结束时cur指向最后一个节点
		}
		//cur= NULL;//这里不能写cur=NULL,需要找到cur的前一个节点，将其next置空\
		否则前一个结点的next依然指向原来的最后一个节点
		prev->next = NULL;//prev成为最后一个节点
		free(cur);//释放原来最后一个节点的空间
	}

头删

C语言中单链表的基本操作(创建、销毁、增删查改等)

头删的操作步骤：

保存第一个节点的指针信息
令*pplist指向第二个节点
释放原来的第一个节点的空间

同样的，头删也要注意保存原来第一个节点的位置，否则*pplist指向改变后，原来的第一个节点就找不到了，会无法释放空间造成内存泄漏。

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	//1.单链表为空
	if (NULL == *pplist)
	{
		return;
	}
	2.单链表有一个节点
	//else if (NULL == (*pplist)->next)
	//{
	//	*pplist = NULL;//删除后链表为空
	//}
	3.单链表有多个节点
	//else
	//{
	//*pplist= (*pplist)->next;
	//}
	
	//两种情况可以合并，只有一个节点时，*pplist的next为空
	else
	{
		SListNode* delNode = *pplist;
		*pplist = delNode->next;
		free(delNode);//释放删除节点的空间
	}
}

查找

用于查找某一元素是否存在于链表中，若存在则返回其第一次出现在链表中的位置，不存在则返回NULL。

遍历时注意循环条件。

SListNode* SListFind(SListNode* plist, DataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return	NULL;
}

任意位置插入

C语言中单链表的基本操作(创建、销毁、增删查改等)

pos节点后插入的步骤：

申请一个新的节点
新增节点的next指向原pos的next
pos的next指向新增的节点

注意事项

任意位置的插入操作只能在给定节点的后面插入，前面的节点无法同通过给出的节点找到。
要注意插入的操作顺序，否则原来链表pos后的节点可能会找不到

void SListInsertAfter(SListNode* pos, DataType x)
{
	assert(pos);//指针合法性校验
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

任意位置删除

与任意位置的插入相同，只能删除给定节点pos后面的节点

void SListDeleteAfter(SListNode* pos)
{
	assert(pos);
	 //1.链表有一个节点
	if (NULL == pos->next)
	{
		return;
	}
	//2.链表有多个节点
	eljsse
	{
		SListNode* temp = pos->next;
		pos->next = temp->next;
		free(temp);
	}
}

销毁

链表的销毁，遍历一遍，逐个释放空间

void SListDestroy(SListNode** pplist)
{
	assert(pplist);//链表是否存在
	//1.链表为空
	if (NULL == *pplist)
	{
		return;
	}
	else
	{
		SListNode* cur = NULL;
		while (*pplist)
		{
			cur = *pplist;
			*pplist = (*pplist)->next;
			free(cur);
		}
	}
}

完整代码

work.h

头文件包含，函数声明，定义结构体

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

typedef int DataType;
typedef struct SListNode
{
	DataType data;//数据域
	struct SListNode *next;//结构体指针，指向下一个节点
}SListNode;//类型别名

//函数声明
SListNode* BuySListNode(DataType x);//节点申请
void SListPrint(SListNode* pst);//单链表遍历打印
void SListPushBack(SListNode** pplist, DataType x);//单链表尾插
void SListPushFront(SListNode** pplist, DataType x);//单链表头插
void SListPopBack(SListNode** pplist);//单链表尾删
void SListPopFront(SListNode** pplist);//单链表头删
SListNode* SListFind(SListNode* plist, DataType x);//单链表查找
void SListInsertAfter(SListNode* pos, DataType x);//pos后位置的插入
void SListDeleteAfter(SListNode* pos);//pos后位置的删除
void SListDestroy(SListNode** pplist);//释放链表空间

work.c

各操作函数的具体实现

#include"work.h"

//链表与顺序表的区别是，顺序表是物理空间上连续的
//而链表只在逻辑上连续，所以链表申请空间时是使用一个申请一个
//顺序表则是一次申请一段空间
SListNode* BuySListNode(DataType x)
{
	//若在栈申请内存函数调用结束后会释放，所以使用动态申请
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	if (plist == NULL)
	{
		return NULL;//判断是否申请成功
	}
	plist->data = x;
	plist->next = NULL;
	return plist;
}

void SListPrint(SListNode* plist)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d-->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//尾插法
void SListPushBack(SListNode** pplist, DataType x)
{
	//改变指针指向，参数传二级指针
	assert(pplist);//判断链表是否存在,与链表是否为空不同

	//1.若链表为空，*pplist指向插入的节点
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	else {
		//2.链表不为空，指针移动到链表最后一个节点，其next指向插入的节点
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;//cur的next为空时，cur指向最后一个节点
		}
		cur->next = BuySListNode(x);
	}
}

//头插法
void SListPushFront(SListNode** pplist, DataType x)
{
	assert(pplist);
	//if (NULL == *pplist)
	//{
	//	//链表为空
	//	*pplist = BuySListNode(x);
	//}
	//else
	//{
	//	SListNode* temp = *pplist;//temp指向链表原来的第一个节点
	//	*pplist = BuySListNode(x);//plist指向新增的节点
	//	(*pplist)->next = temp;//新增的节点指向原来的第一个节点
	//}

	//链表为空的情况可以和不为空合并
	SListNode* node = BuySListNode(x);//申请一个新节点
	node->next = *pplist;//新增的节点的next指向原来的第一个节点
	*pplist = node;//*pplist指向新增的节点

}

//尾删法？
void SListPopBack(SListNode** pplist)
{
	assert(pplist);

	//1.链表为空
	if (NULL== *pplist)
	{
		return;
	}
	//2.链表只有一个元素
	else if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//3.链表有多个元素
	编程else
	{
		SListNode* prev = NULL; 
		SListNode* cur = *pplist;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;//循环结束时cur指向最后一个节点
		}
		//cur= NULL;//这里不能写cur=NULL,需要找到cur的前一个节点，将其next置空\
		否则前一个结点的next依然指向原来的最后一个节点
		prev->next = NULL;//prev最后一个节点
		free(cur);//释放原来最后一个节点的空间
	}
}

//头删
void SListPopFront(SListNode** pplis开发者_C培训t)
{
	assert(pplist);
	//1.单链表为空
	if (NULL == *pplist)
	{
		return;
	}
	2.单链表有一个节点
	//else if (NULL == (*pplist)->next)
	//{
	//	*pplist = NULL;//删除后链表为空
	//}
	3.单链表有多个节点
	//else
	//{
	//*pplist= (*pplist)->next;
	//}
	
	//两种情况可以合并，只有一个节点时，*pplist的next为空
	else
	{
		SListNode* delNode = *pplist;
		*pplist = delNode->next;
		free(delNode);//释放删除节点的空间
	}
}

//单链表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return	NULL;
	
}
//任意位置的插入
//只能在pos的后面插入
void SListInsertAfter(SListNode* pos, DataType x)
{
	assert(pos);//指针合法性校验
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
		

//任意位置的删除
//只能删除给定的pos后面的节点
void SListDeleteAfter(SListNode* pos)
{
	assert(pos);
	 //1.链表有一个节点
	if (NULL == pos->next)
	{
		return;
	}
	//2.链表有多个节点
	else
	{
		SListNode* temp = pos->next;
		pos->next = temp->next;
		free(temp);
	}
}

// 链表空间释放
void SListDestroy(SListNode** pplist)
{
	assert(pplist);//链表是否存在
	//1.链表为空
	if (NULL == *pplist)
	{
		return;
	}
	else
	{
		SListNode* cur = NULL;
		while (*pplist)
		{
			cur = *pplist;
			*pplist = (*pplist)->next;
			free(cur);
		}
	}
}

main.c

程序入口，测试用例

#include"work.h"
void Test()
{
	SListNode* node = NULL;//定义一个结构体指针
	//尾插法插入五个节点
	SListPushBack(&node, 1)android;
	SListPushBack(&node, 2);
	SListPushBack(&node, 3);
	SListPushBack(&node, 4);
	SListPushBack(&node, 5);python
	SListPrint(node);//遍历打印
	SListPushFront(&node, 0);//头插一个节点
	SListPrint(node);//遍历打印
	SListPopBack(&node);//尾删最后一个节点
	SListPrint(node);//遍历打印
	SListPopFront(&node);//头删第一个节点
	SListPrint(node);//遍历打印
	printf("%p\n",  SListFind(node, 4));//查找3在链表中的位置
	printf("%p\n",  SListFind(node, 99));//查找99在链表中的位置
	SListInsertAfter(SListFind(node, 4), 99);//4后面插入一个节点99
	SListPrint(node);//遍历打印
android	SListDeleteAfter(SListFind(node, 4));//删除4的下一个节点
	SListPrint(node);//遍历打印
}

int main()
{
	Test();
	system("pause");
	return 0;
}

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

C语言中单链表的基本操作(创建、销毁、增删查改等)

目录

链表分类

单链表的介绍

单链表的基本操作

创建

打印

尾插

头插

尾删

头删

查找

任意位置插入

任意位置删除

销毁

完整代码

总结

精彩评论

关注公众号

热门标签

图文推荐

C语言中单链表的基本操作(创建、销毁、增删查改等)

目录

链表分类

单链表的介绍

单链表的基本操作

创建

打印

尾插

头插

尾删

头删

查找

任意位置插入

任意位置删除

销毁

完整代码

总结

更多 开发 相关资讯：

精彩评论

关注公众号

热门标签

图文推荐

更多开发相关资讯：