【数据结构】——拿捏链表 ( 无头单向不循环链表 )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


目录
相关文章
|
7天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
28天前
|
存储 Java 索引
【数据结构】链表从实现到应用,保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同,其元素在内存中非连续分布,通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念,包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表,说明了其拥有前后两个指针的特点,并展示了相关操作的代码实现。最后,对比了ArrayList与LinkedList的不同之处,包括它们底层实现、时间复杂度以及适用场景等方面。
42 10
【数据结构】链表从实现到应用,保姆级攻略
|
2月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
34 0
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
2月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现(赋源码)
因为头结点的存在,plist指针始终指向头结点,不会改变。
|
5月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
31 2
|
5月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
45 1