【数据结构】线性表之单链表（讲解实现——带动图理解）

单链表

• 单链表的优点

1.头部和中间插入或删除数据效率高，无需挪动。

2.按照需求申请释放空间，无需担心空间不够用。

• 单链表的缺点

1.不可以进行下标随机访问。

2.复杂度是O(n)

3.反向遍历困难

单链表是线性表的一种，单链表是链式存储的线性表，不同于单链表，链表在内存空间中不连续，而是由结构体内的next指针下一条数据进行链接🧐

PS:需要源码直接通过目录跳转到最后

单链表主体结构

默认大小与扩容大小还有类型都可以是任意大小或类型

typedef int LLDataType;				//数据类型

typedef struct LinkedList
{
	LLDataType data;					//用于存放数据
	struct LinkedList* next;			//指向下一个数据
}LinkedList;

单链表操作函数介绍

1. void printLL(LinkedList* Phead); //打印单链表
2. void LLPushBack(LinkedList** PPhead, LLDataType x); //尾插
3. void LLPushFront(LinkedList** PPhead, LLDataType x); //头插
4. void LLPopBack(LinkedList** PPhead); //尾删
5. void LLPopFront(LinkedList** PPhead); //尾插
6. LinkedList* LListFind(LinkedList* phead, LLDataType x); //查找
7. void SListInsertAfter(LinkedList* pos, LLDataType x); //在指定位置后插入
8. void SListEraseAfter(LinkedList* pos); //删除指定位置后的一个表
9. void SListDestroy(LinkedList** Phead); //销毁单链表
10. void SListInsertFront(LinkedList** Phead, LinkedList* pos, LLDataType x); //在指定位置前插入
11. void SListErase(LinkedList** PPhead, LinkedList* pos); //删除指定位置数据

为了代码方便阅读，讲单链表操作函数全部放在LinkedList.c文件中，将头文件放在LinkedList.h，测试文件test.c 😮

单链表操作函数实现

为了方便调试，建议每写完1-2个函数就进行测试，初始化之后，首先实现print函数可以方便我们进行调试。

单链表的初始化：

LinkedList *Phead = NULL;	//未进行插入之前，头结点指针指向NULL

必须先进性初始化，讲链表指向NULL避免野指针问题。

打印函数

写完插入立马写打印，方便进行调试

void printLL(LinkedList* Phead)
{
	while (Phead!=NULL)
	{
		printf("%d->", Phead->data);
		Phead = Phead->next;
	}
	printf("NULL");
}

单链表插入函数：

头插

头插将新结点插入到头结点

1.如果头结点不为空，头结点改为新插入的结点，原本的第一个位置的结点需要连接到新结点的next。

2.如果头结点为空，那么直接将新结点给到头结点指针phead

• 既然有插入就一定会有空间不够用的问题，这里用到检查空间是否够用的一个函数

LinkedList* BuyNewNode(LLDataType x)		//申请一个新结点并将next指向空
{
	LinkedList* ret = (LinkedList*)malloc(sizeof(LinkedList));
	if (ret == NULL)
	{
		perror("Malloc:");
		return NULL;
	}
	ret->data = x;
	ret->next = NULL;
	return ret;
}

void LLPushFront(LinkedList** PPhead, LLDataType x)
 // 使用二级指针是因为我们要改变头结点，所有必须要使用头结点的指针来改变。
{
	assert(PPhead);			
	LinkedList* NewNode = BuyNewNode(x);
	if (*PPhead == NULL)
	{
		*PPhead = NewNode;
	}
	else
	{
		NewNode->next = *PPhead;
		*PPhead = NewNode;
	}
}

头结点为空

• 如果头结点为空，那么直接将新结点给到头结点指针phead

头结点不为空

• 如果头结点不为空，头结点改为新插入的结点，原本的第一个位置的结点需要连接到新结点的next。

尾插

从最后一个结点后面插入新结点

• 尾插也会用到申请新结点的函数，这里不重复了

void LLPushBack(LinkedList** PPhead, LLDataType x)
// 使用二级指针是因为我们要改变头结点，所有必须要使用头结点的指针来改变。
{
	assert(PPhead);
	LinkedList* NewNode = BuyNewNode(x);	//也用到了上面的BugNode不重复了
	if (*PPhead == NULL)
	{
		*PPhead = NewNode;
	}
	else
	{
		LinkedList* tail = *PPhead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

头结点不为空

• 如果头结点不为空，先找到最后一个结点（指向NULL的就是最后一个结点），然后将新结点插入到最后一个结点的后面

头结点为空

• 如果头结点为空，那么直接将新结点给到头结点指针phead(与上面头插头结点为空相同)

指定结点后插入和查找函数

相对上面两个简单，下面插入函数都需搭配查找结点函数使用，查找函数就是遍历，找到返回地址，比较简单，就不多描述了。

LinkedList* LListFind(LinkedList* phead, LLDataType x)
{
	assert(phead);
	LinkedList *ret = phead;
	while (ret->data != x)
	{
		if (ret == NULL)
		{
			return NULL;
		}
		ret = ret->next;
	}
	return ret;
}

void SListInsertAfter(LinkedList* pos, LLDataType x)
{
	assert(pos);
	LinkedList *newnode = BuyNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

单链表结点之前插入数据

void SListInsertFront(LinkedList** PPhead, LinkedList* pos, LLDataType x)
{
	assert(pos);
	assert(PPhead);
	if (*PPhead == NULL||*PPhead==pos)
	{
		LLPushFront(PPhead, x);
	}
	else
	{
		LinkedList* cur = *PPhead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		LinkedList* newnode = BuyNewNode(x);
		newnode->next = cur->next;
		cur->next = newnode;
	}
}

• 头结点为空或插入结点就是头结点指向的结点，直接复用头插函数即可

• 头结点不为空或插入结点就是头结点指向的结点，找到pos前一个结点进行插入

单链表删除函数

头删

从头部删除数据，将头结点位置删除，将头结点的下一个位置指向头结点

void LLPopFront(LinkedList** PPhead)
{
	assert(PPhead);
	assert(*PPhead);
	LinkedList* temp = (*PPhead)->next;
	free(*PPhead);			//释放掉删除的结点
	*PPhead = temp;
}

尾删

void LLPopBack(LinkedList** PPhead)
{
	assert(PPhead);
	assert(*PPhead);
	if ((*PPhead)->next == NULL)
	{
		*PPhead = NULL;
	}
	else
	{
		LinkedList* tail = *PPhead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

• 如果头结点为空，不能进行删除。
• 如果头结点下一个为空，直接进行删除
• 如果头结点和头结点的下一个都不为空，删除下一个结点为空的结点，那就需要找到头结点下一个结点的下一个结点为空的结点

指定结点后删除

后面的数据依次向前移动

void SListEraseAfter(LinkedList* pos)
{
	if (pos == NULL)
	{
		printf("没发现此数据");
		return;
	}
	if (pos->next == NULL)
	{
		printf("链表后面已经为空了\n");
		return;
	}
	LinkedList* temp = pos->next;
	pos->next = pos->next->next;
	free(temp);
}

• 如果pos为空或pos->next为空则提示并返回

指定结点删除

删除指定结点，将指定结点的next连接到指定结点前面的next结点，然后释放指定的结点。

void SListErase(LinkedList**PPhead,LinkedList* pos)
{
	assert(pos);
	assert(PPhead);
	assert(*PPhead);
	if (pos == *PPhead)
	{
		LLPopFront(PPhead);
		return;
	}
	LinkedList* cur = *PPhead;
	while (cur->next != pos)
	{
		cur = cur->next;
	}
	cur->next = cur->next->next;
	free(pos);
}

• 头结点指针指向的结点等于pos，复用尾插函数

销毁单链表

将每个结点依次释放。最后将头结点制空。

void SListDestroy(LinkedList** PPhead)
{
	assert(*PPhead);
	if (*PPhead == NULL)
	{
		printf("已经是空链表了\n");
		return;
	}
	while ((*PPhead)->next != NULL)
	{
		LinkedList* tep = (*PPhead)->next;
		(*PPhead)->next = (*PPhead)->next->next;
		free(tep);
	}
	free(*PPhead);
	*PPhead = NULL;
}

文件分类

🌞🌞为了使代码更有阅读性，我们不建议把所有函数写在一个文件里，所以这里分成三个文件，模块化管理

test.c

测试文件

#include "LinkedList.h"

int main()
{
	LinkedList *Phead = NULL;
	LLPushFront(&Phead, 8);
	LLPushBack(&Phead,2);
	LLPushBack(&Phead,3);
	LLPushBack(&Phead,4);
	LLPushBack(&Phead,5);
	//LLPopBack(&Phead);
	//LLPopFront(&Phead);
	//LLPopBack(&Phead);
	//LLPopFront(&Phead);
	//LLPopFront(&Phead);
	LinkedList* temp = LListFind(Phead, 3);
	SListInsertAfter(temp,88);
	temp = LListFind(Phead, 4);
	SListEraseAfter(temp);
	temp = LListFind(Phead, 4);

	SListInsertFront(&Phead,temp, 99);
	printLL(Phead);
	temp = LListFind(Phead, 99);
	SListErase(&Phead, temp);
	SListDestroy(&Phead);
}

LinkedList.c

将所有单链表需要的函数封装在此文件下⭐

#include "LinkedList.h"

LinkedList* BuyNewNode(LLDataType x)
{
	LinkedList* ret = (LinkedList*)malloc(sizeof(LinkedList));
	if (ret == NULL)
	{
		perror("Malloc:");
		return NULL;
	}
	ret->data = x;
	ret->next = NULL;
	return ret;
}

void LLPushBack(LinkedList** PPhead, LLDataType x)
{
	assert(PPhead);
	LinkedList* NewNode = BuyNewNode(x);
	if (*PPhead == NULL)
	{
		*PPhead = NewNode;
	}
	else
	{
		LinkedList* tail = *PPhead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

void LLPushFront(LinkedList** PPhead, LLDataType x)
{
	assert(PPhead);
	LinkedList* NewNode = BuyNewNode(x);
	if (*PPhead == NULL)
	{
		*PPhead = NewNode;
	}
	else
	{
		NewNode->next = *PPhead;
		*PPhead = NewNode;
	}
}

void LLPopBack(LinkedList** PPhead)
{
	assert(PPhead);
	assert(*PPhead);
	if ((*PPhead)->next == NULL)
	{
		*PPhead = NULL;
	}
	else
	{
		LinkedList* tail = *PPhead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

void LLPopFront(LinkedList** PPhead)
{
	assert(PPhead);
	assert(*PPhead);
	LinkedList* temp = (*PPhead)->next;
	free(*PPhead);
	*PPhead = temp;
}

void printLL(LinkedList* Phead)
{
	while (Phead!=NULL)
	{
		printf("%d->", Phead->data);
		Phead = Phead->next;
	}
	printf("NULL");
}

LinkedList* LListFind(LinkedList* phead, LLDataType x)
{
	assert(phead);
	LinkedList *ret = phead;
	while (ret->data != x)
	{
		if (ret == NULL)
		{
			return NULL;
		}
		ret = ret->next;
	}
	return ret;
}

void SListInsertAfter(LinkedList* pos, LLDataType x)
{
	assert(pos);
	LinkedList *newnode = BuyNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SListInsertFront(LinkedList** PPhead, LinkedList* pos, LLDataType x)
{
	assert(pos);
	assert(PPhead);
	if (*PPhead == NULL||*PPhead==pos)
	{
		LLPushFront(PPhead, x);
	}
	else
	{
		LinkedList* cur = *PPhead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		LinkedList* newnode = BuyNewNode(x);
		newnode->next = cur->next;
		cur->next = newnode;
	}
}

void SListEraseAfter(LinkedList* pos)
{
	if (pos == NULL)
	{
		printf("没发现此数据");
		return;
	}
	if (pos->next == NULL)
	{
		printf("链表后面已经为空了\n");
		return;
	}
	LinkedList* temp = pos->next;
	pos->next = pos->next->next;
	free(temp);
}


void SListErase(LinkedList**PPhead,LinkedList* pos)
{
	assert(pos);
	assert(PPhead);
	assert(*PPhead);
	if (pos == *PPhead)
	{
		LLPopFront(PPhead);
		return;
	}
	LinkedList* cur = *PPhead;
	while (cur->next != pos)
	{
		cur = cur->next;
	}
	cur->next = cur->next->next;
	free(pos);
}
 
//void SListDestroy(LinkedList** Phead)
//{
//	assert(Phead);
//	if (*Phead == NULL)
//	{
//		printf("已经是空链表了");
//		return;
//	}
//	while ((*Phead) != NULL)
//	{
//		LinkedList* temp = *Phead;
//		*Phead = (*Phead)->next;
//		free(temp);
//	}
//}

void SListDestroy(LinkedList** PPhead)
{
	assert(*PPhead);
	if (*PPhead == NULL)
	{
		printf("已经是空链表了\n");
		return;
	}
	while ((*PPhead)->next != NULL)
	{
		LinkedList* tep = (*PPhead)->next;
		(*PPhead)->next = (*PPhead)->next->next;
		free(tep);
	}
	free(*PPhead);
	*PPhead = NULL;
}

LinkedList.h

将主程序所需要的函数全部在头文件中声明，增加代码阅读性⭐

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int LLDataType;

typedef struct LinkedList
{
	LLDataType data;
	struct LinkedList* next;
}LinkedList;

void printLL(LinkedList* Phead);
void LLPushBack(LinkedList** PPhead, LLDataType x);
void LLPushFront(LinkedList** PPhead, LLDataType x);
void LLPopBack(LinkedList** PPhead);
void LLPopFront(LinkedList** PPhead);
LinkedList* LListFind(LinkedList* phead, LLDataType x);
void SListInsertAfter(LinkedList* pos, LLDataType x);
void SListEraseAfter(LinkedList* pos);
void SListDestroy(LinkedList** Phead);
void SListInsertFront(LinkedList** Phead, LinkedList* pos, LLDataType x);
void SListErase(LinkedList** PPhead, LinkedList* pos);

撒花

这就是实现单链表的全部内容了，创作不易，还请各位小伙伴多多点赞👍关注收藏⭐，以后也会更新各种关于c语言，数据结构的博客，撒花！文章来源地址https://www.toymoban.com/news/detail-458583.html

到了这里，关于【数据结构】线性表之单链表（讲解实现——带动图理解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！