当前位置: 首页 > article >正文

数据结构-单链表-详解-2

数据结构-单链表-详解-2

  • 1.前言
  • 2.创建新结点
  • 3.头插与尾插
    • 3.1头插
    • 3.2尾插
      • 空链表
      • 找尾
  • 4.头删与尾删
    • 4.1头删
    • 4.2尾删

1.前言

在数据结构-单链表-详解-1中,我们不仅了解了单链表的基本概念,还掌握了如何创建和打印单链表。
今天,我将详细讲解如何对单链表进行头尾部的插入、删除。

2.创建新结点

在后续插入的过程中,都需要创建新的结点,因此直接将该过程封装为一个函数,便于操作。
SList.c

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

这段代码定义了一个名为BuySListNode的函数,它接受一个数据值作为参数,并返回一个新的链表结点。函数首先使用malloc来分配内存,然后初始化结点的数据成员和指向下一个结点的指针。

3.头插与尾插

链表的一个重要特性是可以在任意位置插入新元素,这使得链表非常适合动态数据集合的处理。
下面我将分别介绍如何实现头插和尾插操作。

3.1头插

  • 链表不为空:
2.断开
1.连接
2.连接
phead
结点一
结点二
...
NULL
newlist
  • 链表为空:
2.断开
1.连接
2.连接
phead
NULL
newlist

可以发现,头插时,链表为不为空操作相同。
SList.h

void SListPushFront(SListNode** pphead, SLTDataType x);

SList.c

void SListPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

这段代码定义了一个名为SListPushFront的函数,它接受指向链表头结点的二级指针和一个数据值作为参数。
首先,调用CreateSLTNode来创建一个新结点,并将其next指针设置为原来的头结点。
最后,更新头指针使其指向新结点。
现在可以测试一下:
test.c:

void TestSList1()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
}
int main()
{
	TestSList1();
	return 0;
}

运行结果:
在这里插入图片描述

3.2尾插

空链表

在尾插中,如果链表为空,则需改变头指针,因此,我们传入二级指针。
SList.h

void SListPushBack(SListNode** pphead, SLTDataType x);

SList.c

void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySlistNode(x);
	*pphead = newnode;
}

找尾

SListNode* tail = *pphead;

尾插的实现比头插更复杂,想要在尾部插入数据,首先得找到尾部。
错误写法:

while (tail != NULL)
{
	tail = tail->next;
}
tail = newnode;

分析一下,循环的结束条件是tail等于NULL,而下一步则把新结点赋值给了NULL,因此错误。
链表的链接是让上一个结点有下一个结点的地址,因此,尾插的本质是:原尾结点中要存储新尾结点的地址。
完整写法:
SList.c

void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newnode = BuySlistNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	SListNode* tail = *pphead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}

这段代码首先创建一个新结点。
如果链表为空,则直接插入新结点并更新头指针。
否则,初始化一个指针tail从头结点开始,并遍历链表直到找到最后一个结点。
最后,将新结点插入到链表的尾部。

4.头删与尾删

删除的条件是链表不为空,因此该处的函数开头应该assert断言。

4.1头删

两个以上的结点:

1.断开
1.连接
phead
结点一
结点二
...
NULL
2.free结点一

一个结点:

1.断开
1.连接
phead
结点一
NULL
2.free结点一

SList.h

void SListPopFront(SListNode** pphead);

SList.c

void SListPopFront(SListNode** pphead)
{
	assert(*pphead);
	SListNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

这段代码定义了一个名为SListPopFront的函数,它接受指向链表头结点的二级指针作为参数。
函数首先使用assert来确保链表不为空,然后保存当前的头结点,并更新头指针使其指向下一个结点。
最后,释放原来头结点占用的内存,并将指针设为NULL以避免野指针。

4.2尾删

  • 单个结点:
    同头删
  • 多个结点:
    由于需要删除的是最后一个结点,因此,找尾时应该找倒数第二个结点。
    SList.h
void SListPopBack(SListNode** pphead);

SList.c

void SListPopBack(SListNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

这段代码定义了一个名为SListPopBack的函数,它接受指向链表头结点的二级指针作为参数。
函数首先使用assert来确保链表不为空。
如果链表只有一个结点,则直接释放该结点并更新头指针。
否则,初始化一个指针tail从头结点开始,并遍历链表直到找到倒数第二个结点。
最后,释放尾结点占用的内存,并更新倒数第二个结点的next指针使其指向NULL
现在可以测试一下:
test.c:

void TestSList3()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
}

运行结果:
在这里插入图片描述


通过以上的介绍和代码实现,我们掌握了如何对单链表进行头尾部的插入、删除。希望这些内容能帮助你更好地理解单链表,并激发你进一步探索数据结构的兴趣!
本人仅是个C语言初学者,如果你有任何疑问或建议,欢迎随时留言讨论!让我们一起学习,共同进步!


http://www.kler.cn/news/284315.html

相关文章:

  • 彩漩科技亮相第一届人工智能教育应用论坛,荣获AI教育科技产品TOP30奖项
  • 数字化转型升级探索(一)
  • 【奇某信-注册_登录安全分析报告】
  • 鸿蒙高级开发者认证题库(2)
  • RKNPU2从入门到实践 --- 【4】RKNN 模型构建【使用pycharm一步一步搭建RKNN模型】
  • GO Date数据处理
  • Python知识点:如何使用Selenium进行自动化Web测试
  • python-矩阵交换行
  • AI学习指南深度学习篇-长短时记忆网络python实践
  • 使用uniapp制作录音功能(VUE3)
  • 鸿蒙OS试题(4)
  • DSP48E2使用以及FIR滤波器定点设计实现与优化
  • 小琳AI课堂:生成对抗网络(GANs)
  • HarmonyOS开发实战( Beta5版)Web组件开发性能提升指导
  • 处理.NET Core中的时区转换问题
  • 帕金森患者在运动时有哪些类型的运动推荐?
  • SpringWeb后端开发-登录认证
  • CSS中的`z-index`属性是如何工作(注意事项)
  • (苍穹外卖)day03菜品管理
  • 5Kg负重30分钟长航时多旋翼无人机详解
  • MySQL简介和管理
  • 为什么我的手机卡需要快递员给激活?这到底安全吗?
  • Web攻击-XSS、CSRF、SQL注入
  • SimpleTranslationAIAgent:基于C#与LLM的翻译AI Agent
  • 国产游戏行业的技术进步与未来展望
  • Java | Leetcode Java题解之第385题迷你语法分析器
  • Linux 配置wireshark 分析thread 使用nRF-Sniffer dongle
  • kafak推送消息。
  • jenkins安装k8s插件发布服务
  • 项目中Redis常见的一些问题(缓存穿透,缓存雪崩,内存耗尽等)