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

2024-08-31 14:20
文章标签 详解 数据结构 单链

本文主要是介绍数据结构-单链表-详解-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语言初学者,如果你有任何疑问或建议,欢迎随时留言讨论!让我们一起学习,共同进步!

这篇关于数据结构-单链表-详解-2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1124149

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语