[数据结构与算法]数据结构篇----单链表的增删查改

前言

本文重点讲述单链表的增删查改，有喜欢的老铁留下你们的三连！！

链表基本概念

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

每一个节点就相当于一个火车的车厢，指针就相当于火车之间的挂钩，通过指针将这些原本不连续的空间联系起来

链表的创建

typedef int SLTDateType; //链表数据类型
typedef struct SListNode
{
	SLTDateType data;//数据
	struct SListNode* next;//指向下一个结点的指针
}SLTNode;

链表所需的功能函数

void SListPrint(SLTNode* phead);//打印链表
SLTNode* BuySListNode(SLTDateType x); // 动态申请一个节点
void SListPushBack(SLTNode** phead, SLTDateType x);//尾插
void SListPushFront(SLTNode** phead, SLTDateType x);//头插
void SListPopBack(SLTNode** phead);//尾删
void SListPopFront(SLTNode** phead);//头删
SLTNode* SListFind(SLTNode* phead, SLTDateType x);//单链表查找
void SListInsertAfter(SLTNode* pos, SLTDateType x);// 单链表在pos位置之后插入x
void SListInsertBefor(SLTNode*phead,SLTNode* pos, SLTDateType x);// 单链表在pos位置之后插入x
void SListEraseAfter(SLTNode* pos);//单链表删除pos后面的值
void SListEraseBefor(SLTNode** phead,SLTNode* pos);//单链表删除pos前面的值
void SListDestory(SLTNode* phead);// 单链表的销毁

函数的具体实现

1.打印链表

这个很简单，就是遍历而已，重点就是phead = phead->next，这是将phead赋值成下一个结点，有同学会问，这里传的指针那你不改变了头结点的位置了嘛，那不就都混了嘛？？（重点）

我们首先得明白结点是用的指针表示的也就是一级指针，那我们要想改变一级指针指向的地址，那我们得用二级指针来控制，不然不会改变一级指针指向的结点！！！

void SListPrint(SLTNode* phead)//打印链表
{
	assert(phead);
	while (phead!= NULL)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

2.动态申请一个节点

这个由于后续函数都要申请新节点，所以我们直接封装一个新函数

SLTNode* BuySListNode(SLTDateType x)// 动态申请一个节点
{
	
	SLTNode* newnext = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnext);
	newnext->data = x;
	newnext->next = NULL;
	return newnext;
}

3.尾插

void SListPushBack(SLTNode** phead, SLTDateType x)//尾插
//通过二级指针来改变头结点地址
{
	SLTNode* newnext = BuySListNode(x);
	SLTNode* cur = *phead;//标记
	if (*phead == NULL)
	{
		*phead = newnext;//这里就是二级指针的重点，通过二级指针来改变一级指针的值,因为这里是要改变的是一级指针的地址而不是一级指针指向的值
	}
	else
	{
		while (cur->next != NULL)//获取最后一个节点
		{
			cur = cur->next;
		}
		cur->next = newnext;//让最后一个节点指向新节点
	}

}

4.头插

void SListPushFront(SLTNode** phead, SLTDateType x)//头插
{
	SLTNode* newnext = BuySListNode(x);
	newnext->next = *phead;//新节点作为的next指向头结点
	*phead = newnext;//将新节点作为头结点
}

5.尾删

void SListPopBack(SLTNode** phead)//尾删
{
	assert(*phead);
	if (( * phead)->next == NULL)//只有一个节点
	{
		free(*phead);
		*phead = NULL;//这里就是二级指针的重点，通过二级指针来改变一级指针的值,因为这里是要改变的是一级指针的地址而不是一级指针指向的值
	}
	else
	{
	//法一
		//SLTNode* tail = *phead;
		//SLTNode* tailprev = NULL;//每次遍历节点的前一个节点
		//while ((tail)->next != NULL)
		//{
		//	tailprev = tail;
		//	tail = tail->next;
		//}
		//free(tail);
		//tailprev->next = NULL;
	//法二
		SLTNode* tail = *phead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next=NULL;
	}
}

6.头删

void SListPopFront(SLTNode** phead)//头删
{
	assert(*phead);
	SLTNode* cur = (*phead)->next;//获取第二个节点
	free(*phead);//释放第一个节点
	*phead = cur;//将第二个节点作为头节点	
}

7.单链表查找

SLTNode* SListFind(SLTNode* phead, SLTDateType x)//单链表查找
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

8.单链表在pos位置之后插入x

void SListInsertAfter(SLTNode* pos, SLTDateType x)// 单链表在pos位置之后插入x
{
		assert(pos);
		SLTNode* next = pos->next;//记录pos下一个结点
		SLTNode *newnext=BuySListNode(x);
		pos->next = newnext;
		newnext->next = next;
}

9.单链表在pos位置之后插入x

void SListInsertBefor(SLTNode**phead,SLTNode* pos, SLTDateType x)// 单链表在pos位置之后插入x
{
		assert(pos);
		
//法一
		
		if (pos == *phead)//一个结点的情况
		{
			SListPushFront(phead,x);//头插
		}
		else
		{
			SLTNode* newnext = BuySListNode(x);
			SLTNode* posprev = *phead;
			while (posprev->next != pos)
			{
				posprev = posprev->next;
			}
			posprev->next = newnext;
			newnext->next = pos;
		}


//法二		
	//if (*phead == pos)
	//{
	//  SListPushFront(phead, x);//头插
	//}
	//else
	//{
	// 	SLTNode* newnext = BuySListNode(x);	
	//	SLTNode* tail = *phead;
	//	while (tail->next->next != pos)
	//	{
	//		tail = tail->next;
	//	}
	//	newnext->next = pos;
	//	tail->next->next = newnext;
	//}

}

10.单链表删除pos后面的值

void SListEraseAfter(SLTNode* pos)//单链表删除pos后面的值
{
	assert(pos);
	SLTNode* next = pos->next;//记录删除的结点
	if (pos->next != NULL)
	{
		pos->next = pos->next->next;			
		free(next);
	}
	/*SLTNode* next = pos->next;

	if (next != NULL)
	{
		SLTNode* nextnext = next->next;//这里创建变量是直接记录pos下下个结点的，计算机不在乎这点内存，然而这方便我们理解
		free(next);
		pos->next = nextnext;
	}*/
}

11.单链表删除pos前面的值

void SListEraseBefor(SLTNode** phead, SLTNode* pos)//单链表删除pos前面的值
{
	assert(pos&&(pos!=*phead));
	if ((*phead)->next == pos)
		{
			SListPopFront(phead);
		}
	else
		{
		SLTNode* tail = *phead;
		while (tail->next->next != pos)
		{	
			tail = tail->next;
		}
		SLTNode* next = tail->next;
		tail->next = pos;
		free(next);
	}

}

12.单链表的销毁

void SListDestory(SLTNode* phead)// 单链表的销毁
{
	SLTNode* next = phead->next;//用来记录销毁节点的下一个结点
	while (phead != NULL)
	{
		free(phead);
		phead = next;
		if(next!=NULL)
		next = next->next;
	}
}

函数总汇

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void SListPrint(SLTNode* phead)//打印链表
{
	assert(phead);
	while (phead!= NULL)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}
SLTNode* BuySListNode(SLTDateType x)// 动态申请一个节点
{
	
	SLTNode* newnext = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnext);
	newnext->data = x;
	newnext->next = NULL;
	return newnext;
}
void SListPushBack(SLTNode** phead, SLTDateType x)//尾插
//通过二级指针来改变头结点地址
{
	SLTNode* newnext = BuySListNode(x);
	SLTNode* cur = *phead;//标记
	if (*phead == NULL)
	{
		*phead = newnext;//这里就是二级指针的重点，通过二级指针来改变一级指针的值,因为这里是要改变的是一级指针的地址而不是一级指针指向的值
	}
	else
	{
		while (cur->next != NULL)//获取最后一个节点
		{
			cur = cur->next;
		}
		cur->next = newnext;//让最后一个节点指向新节点
	}

}
void SListPushFront(SLTNode** phead, SLTDateType x)//头插
{
	SLTNode* newnext = BuySListNode(x);
	newnext->next = *phead;//新节点作为的next指向头结点
	*phead = newnext;//将新节点作为头结点
}
void SListPopBack(SLTNode** phead)//尾删
{
	assert(*phead);
	if (( * phead)->next == NULL)//只有一个节点
	{
		free(*phead);
		*phead = NULL;//这里就是二级指针的重点，通过二级指针来改变一级指针的值,因为这里是要改变的是一级指针的地址而不是一级指针指向的值
	}
	else
	{
		//SLTNode* tail = *phead;
		//SLTNode* tailprev = NULL;//每次遍历节点的前一个节点
		//while ((tail)->next != NULL)
		//{
		//	tailprev = tail;
		//	tail = tail->next;
		//}
		//free(tail);
		//tailprev->next = NULL;
		SLTNode* tail = *phead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next=NULL;
	}
}
void SListPopFront(SLTNode** phead)//头删
{
	assert(*phead);
	SLTNode* cur = (*phead)->next;//获取第二个节点
	free(*phead);//释放第一个节点
	*phead = cur;//将第二个节点作为头节点
	
}
SLTNode* SListFind(SLTNode* phead, SLTDateType x)//单链表查找
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}
void SListInsertAfter(SLTNode* pos, SLTDateType x)// 单链表在pos位置之后插入x
{
		assert(pos);
		SLTNode* next = pos->next;//记录pos下一个结点
		SLTNode *newnext=BuySListNode(x);
		pos->next = newnext;
		newnext->next = next;
}
void SListInsertBefor(SLTNode**phead,SLTNode* pos, SLTDateType x)// 单链表在pos位置之后插入x
{
		assert(pos);
		
//法一
		
		if (pos == *phead)//一个结点的情况
		{
			SListPushFront(phead,x);//头插
		}
		else
		{
			SLTNode* newnext = BuySListNode(x);
			SLTNode* posprev = *phead;
			while (posprev->next != pos)
			{
				posprev = posprev->next;
			}
			posprev->next = newnext;
			newnext->next = pos;
		}


//法二		
	//if (*phead == pos)
	//{
	//  SListPushFront(phead, x);//头插
	//}
	//else
	//{
	// 	SLTNode* newnext = BuySListNode(x);	
	//	SLTNode* tail = *phead;
	//	while (tail->next->next != pos)
	//	{
	//		tail = tail->next;
	//	}
	//	newnext->next = pos;
	//	tail->next->next = newnext;
	//}

}
void SListEraseAfter(SLTNode* pos)//单链表删除pos后面的值
{
	assert(pos);
	SLTNode* next = pos->next;//记录删除的结点
	if (pos->next != NULL)
	{
		pos->next = pos->next->next;			
		free(next);
	}
	/*SLTNode* next = pos->next;

	if (next != NULL)
	{
		SLTNode* nextnext = next->next;//这里创建变量是直接记录pos下下个结点的，计算机不在乎这点内存，然而这方便我们理解
		free(next);
		pos->next = nextnext;
	}*/
}

void SListEraseBefor(SLTNode** phead, SLTNode* pos)//单链表删除pos前面的值
{
	assert(pos&&(pos!=*phead));
	if ((*phead)->next == pos)
		{
			SListPopFront(phead);
		}
	else
		{
		SLTNode* tail = *phead;
		while (tail->next->next != pos)
		{	
			tail = tail->next;
		}
		SLTNode* next = tail->next;
		tail->next = pos;
		free(next);
	}

}
void SListDestory(SLTNode* phead)// 单链表的销毁
{
	SLTNode* next = phead->next;//用来记录销毁节点的下一个结点
	while (phead != NULL)
	{
		free(phead);
		phead = next;
		if(next!=NULL)
		next = next->next;
	}
}

ps：学习链表要学会多画图，因为这东西对于初学者来说比较抽象，还有一个点就是为什么总是要创建中间变量来存储结点，这是因为你讲前面一个结点和后面一个结点联系起来了，如果没有用中间变量提前存储的话，会导致你调用不了这个结点

看图：


这里想要删除2，是不是要先将2这个结点保存下来呀，不保存就找不到了，然后再free掉它！！
还有同学问 我不能先free掉2然后让1指向3吗，这里因为2被free了所以1不能通过2找到3了 ，所以还是不行，就相当于下图一样中间没联系了

本文结束，有疑问的老铁欢迎留言！！

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖