您现在的位置是：首页 >其他 >【数据结构】- 链表之单链表(下)网站首页其他

【数据结构】- 链表之单链表(下)

不喜欢吃鱼. 2023-06-04 08:00:02
简介【数据结构】- 链表之单链表(下)

文章目录

前言

未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散
本章是关于数据结构中的链表之单链表(下)

提示：以下是本篇文章正文内容，下面案例可供参考

一、单链表(下)

1.1 查找+修改

//SList.h
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//SList.c
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//Test.c
void TestSList()
{
	SLTNode* plist = NULL;
	SLPushFornt(&plist, 1);
	SLPushFornt(&plist, 2);
	SLPushFornt(&plist, 3);
	SLPushFornt(&plist, 4);
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		pos->data = 30;
	}
	SLTPrint(plist);
}

在这里插入图片描述

1.2 在任意位置插入

1.2.1 在pos位置插入(也就是pos位置之前)

//SList.h
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
//SList.c
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLPushFornt(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//Test.c
void TestSList()
{
	SLTNode* plist = NULL;
	SLPushFornt(&plist, 1);
	SLPushFornt(&plist, 2);
	SLPushFornt(&plist, 3);
	SLPushFornt(&plist, 4);
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		SLInsert(&plist, pos, 30);
	}
}

流程图

  • 多个节点

在这里插入图片描述

  • 一个节点
    在这里插入图片描述

1.2.2 在pos位置之后插入

//SList.h
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
//SList.c
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//Test.c
void TestSList()
{
	SLTNode* plist = NULL;
	SLPushFornt(&plist, 1);
	SLPushFornt(&plist, 2);
	SLPushFornt(&plist, 3);
	SLPushFornt(&plist, 4);
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 2);
	if (pos)//判断是否为空
	{
		SLInsertAfter(pos, 30);
	}
	SLTPrint(plist);
}

流程图：
在这里插入图片描述
注意：
下面这种写法就存在了问题newnode指向了它自己造成了错误

void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyTNode(x);
	pos->next=newnode;
	newnode->next=pos->next;
}

流程图：
在这里插入图片描述

1.3 在任意位置删除

1.3.1 删除pos位置得值

//SList.h
void SLErase(SLTNode** pphead, SLTNode* pos);
//SList.c
void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPopFornt(pphead);//头删
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
//Test.c
void TestSList()
{
	SLTNode* plist = NULL;
	SLPushFornt(&plist, 1);
	SLPushFornt(&plist, 2);
	SLPushFornt(&plist, 3);
	SLPushFornt(&plist, 4);
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		SLErase(&plist, pos);
	}
	SLTPrint(plist);
}

流程图：
在这里插入图片描述

1.3.2 删除pos位置后面的值

//SList.h
void SLEraseAfter(SLTNode* pos);
//SList.c
void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}
//Test.c
void TestSList()
{
	SLTNode* plist = NULL;
	SLPushFornt(&plist, 1);
	SLPushFornt(&plist, 2);
	SLPushFornt(&plist, 3);
	SLPushFornt(&plist, 4);
	SLTPrint(plist);
		SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		SLEraseAfter(pos);
	}
	SLTPrint(plist);
}

流程图：
在这里插入图片描述

二、完整代码

//SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);
void SLPushFornt(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);

void SLPopFornt(SLTNode** pphead);
void SLPopBack(SLTNode** pphead);


SLTNode* STFind(SLTNode* phead, SLTDataType x);

//任意位置插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos之前插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);//在pos之后插入
void SLErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的值
void SLEraseAfter(SLTNode* pos);//删除pos位置的值





//SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL
");
}

SLTNode* BuyTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SLPushFornt(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyTNode(x);
	newnode->next  = *pphead;
	*pphead = newnode;
}

void SLPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuyTNode(x);
	//空链表
	if(*pphead==NULL)
	{
		*pphead = newnode;
	}
	//非空链表
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SLPopFornt(SLTNode** pphead)
{
	//空链表
	assert(*pphead);
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个节点:保存下一个节点，释放当前节点
	else
	{
		SLTNode* del = *pphead;
		*pphead = del->next;
		free(del);
	}
}

void SLPopBack(SLTNode** pphead)
{
	//空链表
	assert(*pphead);
	//有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	有多个节点
	else
	{
	SLTNode* prev = NULL;
	SLTNode* tail = *pphead;
	//找尾
	while (tail->next == NULL)//或者写成while(tail->next)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLPushFornt(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuyTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPopFornt(pphead);//头删
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

//删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
}




//Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

void TestSList()
{
	SLTNode* plist = NULL;
	SLPushFornt(&plist, 1);
	SLPushFornt(&plist, 2);
	SLPushFornt(&plist, 3);
	SLPushFornt(&plist, 4);
	SLTPrint(plist);
	SLPushBack(&plist, 5);
	SLPopFornt(&plist);
	SLTPrint(plist);
	SLPopFornt(&plist);
	SLTPrint(plist);
	SLPopFornt(&plist);
	SLTPrint(plist);
	SLPopFornt(&plist);
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		SLInsert(&plist, pos, 30);
	}
	SLTNode* pos = STFind(plist, 2);
	if (pos)//判断是否为空
	{
		SLInsertAfter(pos, 30);
	}
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		SLErase(&plist, pos);
	}
	SLTPrint(plist);
	SLTNode* pos = STFind(plist, 3);
	if (pos)//判断是否为空
	{
		SLEraseAfter(pos);
	}
	SLTPrint(plist);
}


int main()
{
	TestSList();
	return 0;
}

总结

Ending,今天的链表之单链表(下)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧，一键三连哦 ~

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

站长推荐