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

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

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


前言

千万不要放弃 最好的东西 总是压轴出场
本章是关于数据结构中的链表之单链表(中)


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

一、单链表(中)

1.1 头删

对于头删要考虑没有节点、一个节点、多个节点等问题

  • 对于一个节点:没有删的必要所以可以采用两种方法来解决
//第一种:断言
assert(*pphead)

//第二种:if语句
if(*pphead==NULL)
{
	return;
}
  • 对于一个节点:只需要将这个空间释放置空
if((*pphead)->next==NULL)
{
	free(*pphead);
	*pphead=NULL;
}
  • 对于多个节点:保存下一个节点,释放当前节点
    在这里插入图片描述
SLTNode* del = *pphead;
*pphead = del->next;
free(del);

1.2尾删

1.2.1第一种方法:

void SLPopBack(SLTNode** pphead)
{
	SLTNode* prev = NULL;
	SLTNode* tail = *pphead;
	//找尾
	while (tail->next == NULL)//或者写成while(tail->next)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}

在这里插入图片描述

注意:
下面这段代码存在两个问题:

  • 野指针
    把tail置空倒数第二个节点中的next指向的是最后一个节点的地址它置空所以就出现了野指针问题
    在这里插入图片描述

  • 只是对局部变量做了修改没有改变plist
    局部变量,将局部变量置空是不管用的出了作用域就会销毁单链表规定尾节点是空的所以应该是倒数第二个节点的tail->next置空而不是tail置空,倒数第二个节点tail->next置空就不会再链接最后那一个节点所以应该改找倒数第二个节点而不是尾节点
    在这里插入图片描述

void SLPopBack(SLTNode** pphead)
{
	SLTNode* tail = *pphead;
	//找尾
	while (tail->next == NULL)//或者写成while(tail->next)
	{
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
}

1.2.2第二种方法:

void SLPopBack(SLTNode** pphead)
{
	/*SLTNode* prev = NULL;*/
	SLTNode* tail = *pphead;
	while (tail->next->next != NULL)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;
}

在这里插入图片描述

1.2.3多因素考虑

对于尾删要考虑没有节点、一个节点、多个节点等问题所以上述代码是需要完善的

  • 对于一个节点:没有删的必要所以可以采用两种方法来解决
//第一种:断言
assert(*pphead)

//第二种:if语句
if(*pphead==NULL)
{
	return;
}
  • 对于一个节点:只需要将这个空间释放置空
if((*pphead)->next==NULL)
{
	free(*pphead);
	*pphead=NULL;
}
  • 对于多个节点:我们就可以采用最上面的两种方法

二、完整版代码

2.1 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);

2.2 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;
	}
}

2.3 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);
}

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

总结

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

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