您现在的位置是:首页 >技术交流 >【单链表】的增删查改网站首页技术交流

【单链表】的增删查改

Djx_hmbb 2023-05-22 20:00:02
简介【单链表】的增删查改

🖊作者 : Djx_hmbb
📘专栏 : 数据结构
😆今日分享 : “Onc in a blu moon” : “罕见的,千载难逢的” (出现在19世纪,指的是"在一个月内出现的第二次圆月”,这种现象每隔32个月发生一次。)
在这里插入图片描述

✔单链表的功能实现:

🔎申请一个结点空间 :

//为单链表申请一个结点空间
SLT* SLTBuy(SLTdataType x)
{
	SLT* newNode = (SLT*)malloc(sizeof(SLT));
	if (newNode == NULL) 
	{
		perror("malloc fail:");
		exit(-1);
	}
	else
	{
		newNode->data = x;
		newNode->next = NULL;
	}
	return newNode;
}

🔎构建n个链表 :

//构建n个链表
SLT* SLTCreate(SLTdataType x)
{
	SLT* phead = NULL, * ptail = NULL;
	for (int i = 0; i < x; i++)
	{
		SLT* newNdoe = SLTBuy(i);
		if (phead == NULL)
		{
			phead = ptail = newNdoe;
		}
		else 
		{
			ptail->next = newNdoe;
			ptail = newNdoe;
		}
	}
	return phead;
}

🔎打印链表 :

//打印链表
void SLTPrint(SLT* phead)
{
	SLT* cur = phead;
	while (cur != NULL)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}
	 puts("NULL
");
}

🔎尾插 :

//尾插!!!!!!!!!!!!!!!!!!要用取地址!!!!!!!!!!!
void SLTPushBack(SLT** pphead, SLTdataType x) 
{
	SLT* newNode=SLTBuy(x);
	
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		SLT* ptail = *pphead;
		//找尾结点
		while (ptail->next)
		{
		//移动指针
			ptail = ptail->next;
		}
		//将新建的结点插入尾结点
		ptail->next = newNode;
	}
	
}

🔎尾删 :

//尾删
void SLTPopBack(SLT** pphead)
{
	assert(*pphead);//检查链表头结点是否为空

	//法一:
	SLT* ptail = (*pphead)->next;
	SLT* cur = *pphead;
	//判断头结点是否为空
	 if(*pphead != NULL)
	 {
	//判断第二个节点是否为空(ptail)
		 if ((*pphead)->next != NULL)
		 { //找尾
			 //SLT* ptail = (*pphead)->next;
			 while (ptail->next)
			{
				cur = ptail;
				ptail = ptail->next;
			}
	//找到尾后,释放空间,并将前面的一个结点置为空
			free(ptail);
			cur->next = NULL;
		 }
		 else
		 {
			 free(*pphead);
			 *pphead = NULL;
		 }
	 }
	 else
	 {
		 free(*pphead);
		 *pphead = NULL;
	 }
	
	

	法二:
	//SLT* ptail = *pphead;
	找尾
	//if (ptail->next)
	//{
	//	while (ptail->next->next)
	//{
	//	ptail = ptail->next;
	//}
	找到尾后,释放空间,并将前面的一个结点值为空
	//free(ptail->next);
	//ptail->next = NULL;
	//}
	//else
	//{
	//	free(*pphead);
	//	*pphead = NULL;
	//}
	
}

🔎头插 :

//头插
void SLTPushFront(SLT** pphead, SLTdataType x)
{
	SLT* newNode = SLTBuy(x);
	if (*pphead==NULL)
	{
		*pphead = newNode;
	}
	else
	{
		SLT* ptail = (*pphead);
		//SLT* cur = (*pphead)->next;
		*pphead = newNode;
		newNode->next = ptail;
		ptail = *pphead;
	}
}

🔎头删 :

//头删
void SLTPopFront(SLT** pphead)
{
	if (*pphead == NULL)
	{//释放原空间
		free(*pphead);
		(*pphead) = NULL;
	}
	else
	{//删除
		SLT* ptail = (*pphead)->next;
		if (ptail != NULL)
		{
			(*pphead) = ptail;
		}
		else
		{
			free(*pphead);
			(*pphead) = NULL;
		}
	}
}

🔎查找 :

//查找
SLT* SLTFind(SLT* phead, SLTdataType x)
{
	assert(phead);
	SLT* cur = phead;
	while (cur != NULL)
	{
		//找x
		while (cur->data != x)
		{
		cur = cur->next;
		}
		//找到后,返回地址
		return cur;
	}
	return NULL;
}

🔎在pos位置后插入x :

//在pos位置后插入x
void SLTInsertAfter(SLT* pos, SLTdataType x)
{
	assert(pos);//判断pos位置是否存在
	SLT* newNode = SLTBuy(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

🔎在pos位置前插入x :

//在pos位置前插入x
void SLTInsertFront(SLT** pphead, SLT* pos, SLTdataType x)
{
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLT* prev = *pphead;
		//找到pos的前一个结点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//找到后,添加节点
		SLT* newNode = SLTBuy(x);
		prev->next = newNode;
		newNode->next = pos;
	}
}

🔎删除pos位置后一个指针 :

//删除pos位置后一个指针
void SLTDeleteAfter(SLT* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return ;
	}
	else
	{
		pos->next = pos->next->next;
	}
}

🔎删除pos位置的指针 :

//删除pos位置的指针
void SLTDPosDelete(SLT** pphead, SLT* pos)
{
	//assert(*pphead);//不用断言,如果plist为空,则pos一定为空;可是plist不为空,但是pos可能为空!!!
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLT* prev = *pphead;
		//找到pos前一个节点
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//删除pos结点
		prev->next = pos->next;
		free(pos);
		//pos = NULL;//不用置空,无意义:置空的是形参
	}
}

🔎释放空间 :

//释放空间
void SLTDestory(SLT** pphead)
{
	//结点是一个一个申请的,所以释放的时候也需要一个一个释放!!!
	// 错误示范:
	//free(*pphead);
	//(*pphead)->next = NULL;

	//正确:
	SLT* cur = *pphead;
	while (cur != NULL)
	{
		SLT* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;//头指针此时为野指针,需要置空
}

✔头文件(详情):

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

#define SLTdataType int

//定义结构体
typedef struct SLTnode
{
	SLTdataType data;
	struct  SLTnode* next;
}SLT; 

//为结点申请一个空间
SLT* SLTBuy(SLTdataType x);

//构建n个链表
SLT* SLTCreate(SLTdataType x);

//打印链表
void SLTPrint(SLT* phead);

//尾插
void SLTPushBack(SLT** pphead,SLTdataType x);

//尾删
void SLTPopBack(SLT** pphead);

//头插
void SLTPushFront(SLT** pphead, SLTdataType x);

//头删
void SLTPopFront(SLT** pphead);

//查找
SLT* SLTFind(SLT* phead, SLTdataType x);

//在pos位置后插入x
void SLTInsertAfter(SLT* pos, SLTdataType x);

//在pos位置前插入x
void SLTInsertFront(SLT** pphead,SLT* pos, SLTdataType x);

//删除pos位置后一个指针
void SLTDeleteAfter(SLT* pos);

//删除pos位置的指针
void SLTDPosDelete(SLT** pphead, SLT* pos);

//释放空间
void SLTDestory(SLT** pphead);

✔测试文件(详情):

#define _CRT_SECURE_NO_WARNINGS
#include"SLTNode.h"



test01()
{
	SLT* b1 = SLTBuy(1);
	SLT* b2 = SLTBuy(2);
	SLT* b3 = SLTBuy(3);
	b1->next = b2;
	b2->next = b3;
	SLTPrint(b1);
}

test02()
{
	SLT* plist= SLTCreate(3);
	SLTPrint(plist);
}

test03()
{
	SLT* plist=SLTCreate(3);//0 1 2
	/*int x = 0;
	printf("请输入尾插的数字:");
	scanf("%d",&x);
	SLTPushBack(&plist,x);
	SLTPrint(plist);*/
	//SLTPopBack(&plist);//0 1
	//SLTPrint(plist);
	//SLTPopBack(&plist);//0
	//SLTPrint(plist);
	//SLTPopBack(&plist);//NULL
	//SLTPrint(plist);
}
test04()
{
	SLT* plist = SLTCreate(3);//0 1 2
	//int x = 0;
	//printf("请输入头插的值:");
	//scanf("%d",&x);
	SLTPushFront(&plist,3);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);//0 1 2
	SLTPopFront(&plist);
	SLTPrint(plist);//1 2
	SLTPopFront(&plist);
	SLTPrint(plist);// 2
	SLTPopFront(&plist);
	SLTPrint(plist);//NULL
}
test05()
{
	SLT* plist = NULL;
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 0);
	SLTPrint(plist);//0 1 2 3 NULL

	SLT* pos = SLTFind(plist,3);
	printf("%p
",pos);//000002866BDFE0E0

	SLTInsertAfter(pos,12);
	SLTPrint(plist);//0 1 2 3 12 NULL
	SLTInsertFront(&plist,pos,11);
	SLTPrint(plist);//0 1 2 11 3 12 NULL

	SLTDeleteAfter(pos);
	SLTPrint(plist);//0 1 2 11 3 NULL

	pos = SLTFind(plist,0);
	SLTDPosDelete(&plist,pos);
	SLTPrint(plist);//0 1 2 11 NULL

}
main()
{
	test05();
	system("pause");
	return 0;
}

感谢家人的阅读,若有不准确的地方 欢迎在评论区指正!

家人们,点个请添加图片描述再走呗~

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。