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


目录
相关文章
|
1月前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
23天前
|
算法 Java
Java数据结构与算法:循环链表
Java数据结构与算法:循环链表
|
24天前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
8 0
|
24天前
|
存储 算法 前端开发
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
13 0
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
|
23天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
18天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
24天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
28 5
|
23天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)