【数据结构】——拿捏链表 ( 无头单向不循环链表 )2

简介: 【数据结构】——拿捏链表 ( 无头单向不循环链表 )2

✨4.删除结点

单链表的头删

头删较为简单,若为空表,则不必做处理;若不为空表,则直接让头指针指向第二个结点,然后释放第一个结点的内存空间即可。

【数据结构】——拿捏链表 ( 无头单向不循环链表 )_数据结构_11

//头删
void SListPopFront(SListNode** pplist)
{
    if (*pplist == NULL)//判断是否为空表
    {
        return;
    }
    else
    {
        SListNode* tmp = *pplist;//记录第一个结点的位置
        *pplist = (*pplist)->next;//让头指针指向第二个结点
        free(tmp);//释放第一个结点的内存空间
        tmp = NULL;//及时置空
    }
}

单链表的尾删

尾删相对麻烦一些,我们需要考虑三种不同的情况:

1、当链表为空时,不做处理。
2、当链表中只有一个结点时,直接释放该结点,然后将头指针置空。
3、当链表中有多个结点时,我们需要先找到最后一个结点的前一个结点,然后将最后一个结点释放,将前一个结点的指针域置空,使其成为新的尾结点。

4、注意:删除尾部的数据还要把尾部的前一个结点的指针域置为NULL空指针,否则我们下次删除就找不到尾了。

【数据结构】——拿捏链表 ( 无头单向不循环链表 )_数据结构_12

//尾删
void SListPopBack(SListNode** pplist)
{
    if (*pplist == NULL)//判断是否为空表
    {
        return;
    }
    else if ((*pplist)->next == NULL)//判断是否只有一个结点
    {
        free(*pplist);//释放该结点
        *pplist = NULL;//及时置空
    }
    else
    {
        SListNode* prev = *pplist;//接收头指针
        SListNode* tail = (*pplist)->next;//接收第一个结点的地址
        while (tail->next != NULL)//当tail指向最后一个结点时停止循环
        {
            prev = tail;//使prev始终指向tail的前一个结点
            tail = tail->next;//tail指针后移
        }
        free(tail);//释放最后一个结点
        tail = NULL;//及时置空
        prev->next = NULL;//将倒数第二个结点的指针域置空,使其成为新的尾节点
    }
}

删除给定位置之后的结点

要删除给定位置之后的值,我们首先判断传入地址是否为最后一个结点的地址,若是,则不做处理,因为最后一个结点后面没有结点可删除。若不是最后一个结点,我们首先让地址为pos的结点指向待删除结点的后一个结点,然后将待删除结点释放即可。

【数据结构】——拿捏链表 ( 无头单向不循环链表 )_C语言_13

//删除给定位置之后的值
void SListErasetAfter(SListNode* pos)
{
    assert(pos);//确保传入地址不为空
    if (pos->next == NULL)//判断传入地址是否为最后一个结点的地址
    {
        return;
    }
    SListNode* after = pos->next;//待删除的结点
    pos->next = after->next;//让pos结点指向待删除的结点的下一个结点
    free(after);//释放结点
    after = NULL;//及时置空
}

删除给定位置的结点

要删除给定位置的结点,我们首先要判断该结点是否为第一个结点,若是,则操作与头删相同;若不是,我们就需要先找到待删除结点的前一个结点,然后让其指向待删除结点的后一个结点,最后才能释放待删除的结点。

这个有2种情况:
1、删除的是不是第一个结点
2、删除的是第一个结点
因为删除当前位置数据有可能是第一个结点,所以我们统一传二级指针来实现。

【数据结构】——拿捏链表 ( 无头单向不循环链表 )_无头单向不循环链表_14

//删除给定位置的值
void SListErasetCur(SListNode** pplist, SListNode* pos)
{
    assert(pos);//确保传入地址不为空
    if (pos == *pplist)//判断待删除的结点是否为第一个结点
    {
        *pplist = pos->next;//让头指针指向第二个结点
        free(pos);//释放第一个结点
        pos=NULL;//及时置空
    }
    else
    {
        SListNode* prev = *pplist;//接收头指针
        while (prev->next != pos)//找到待删除结点的前一个结点
        {
            prev = prev->next;
        }
        prev->next = pos->next;//让待删除的结点的前一个结点指向待删除结点的后一个结点
        free(pos);//释放待删除结点
        pos = NULL;//及时置空
    }
}

⛵5.查找数据

查找数据相对于前面的来说就非常简单了,我们只需要遍历一遍链表,在遍历的过程中,若找到了目标结点,则返回结点的地址;若遍历结束也没有找到目标结点,则直接返回空指针。

//查找数据
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
    SListNode* cur = plist;//接收头指针
    while (cur != NULL)//遍历链表
    {
        if (cur->data == x)//判断结点是否为待找结点
            return cur;//返回目标结点的地址
        cur = cur->next;//指针后移
    }
    return NULL;//没有找到数据为x的结点
}

⌚6.修改数据

修改数据,嗯…其实我觉得根本不用写出来,但是链表的一般功能就是增、删、查、改嘛,为了完整性,还是加上吧。

//修改数据
void SListModify(SListNode* pos, SLTDataType x)
{
    pos->data = x;//将结点的数据改为目标数据
}

【数据结构】——拿捏链表 ( 无头单向不循环链表 )_C语言_15


目录
相关文章
|
19天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
39 0
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1月前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
20 0
|
1月前
数据结构的带头,双向,循环链表来咯
数据结构的带头,双向,循环链表来咯
15 0
|
1月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
6月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
5月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
5月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
54 2
|
6月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
53 1