【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能(2)

简介: 【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能(2)

一.无头链表的实现

  • 我们上回链表的接口功能实现到了尾插和尾删,我们下面接着上回的内容继续我们链表的学习。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType Data;
    struct SListNode * next;
}SLTNode;
//打印链表
void SLTPrint(SLTNode* phead);
//初始化链表
SLTNode* BuySListNode(SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
// 找某个数
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//修改pos位置的值
void SLTModify(SLTNode**pphead, SLTNode* pos, SLTDataType x);
// 单链表的销毁
void SListDestroy(SLTNode** pphead);

1.查找某个节点 SLTFind以及修改某个节点的数 SLTModify

查找某个节点是否存在

//找某个节点是否存在
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->Data == x)
            return cur;
        cur = cur->next;
    }
    printf("该节点不存在\n");
    return NULL;
}
  • 对于查找来说,我们只需要遍历一下链表依次比较一下每个节点存放的Data是否与我要找的x相等即可,如果到最后都不相等,说明链表中没有该节点

修改某个节点的数

//修改某个节点的值
void SLTModify(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    pos->Data = x;
}
  • 这个与上面的查找函数联动即可,我先找到这个节点是否存在,如果能找到,我就把该节点的Data改为我想要的x就行。
  • 示例如下:
void TestSList2()
{
    int n = 0;
    int x = 0;
    printf("请输入需要定义的链表的长度:\n");
    scanf("%d", &n);
    printf("请输入需要放入链表中的元素,中间用空格隔开\n");
    SLTNode* plist = NULL;
    int val = 0;
    for (size_t i = 0; i < n; i++)
    {
        scanf("%d", &val);
        SLTPushBack(&plist, val);
    }
    SLTPrint(plist);
    //SLTFind(plist, 5);
    printf("请输入要修改的值\n");
    scanf("%d", &x);
    SLTNode* pos = SLTFind(plist, x);
    if (pos)
    {
        int m;
        printf("请输入要把该节点修改成什么值:\n");
        scanf("%d", &m);
        SLTModify(&plist, pos, m);
    }
    SLTPrint(plist);
}

2.在pos之前插入值 SLTInsert与在pos之后插入值 SLTInsertAfter

在pos之前插入值

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    SLTNode* cur = *pphead;
    SLTNode* newnode = BuySListNode(x);
    //如果没有节点时就得头插
    assert(pphead);
    assert(pos);
    if (pos == *pphead)
    {
        SLTPushFront(pphead, x);
    }
    else {
        while (cur->next)
        {
            if (cur->next->Data == pos->Data)
            {
                cur->next = newnode;
                newnode->next = pos;
            }
            cur = cur->next;
        }
    }
}
  • 特殊情况的分析:
  • 在pos之前插入我们得考虑这些地方:1,pos是否合法? 2.pphead是否为空
  • 当我们判断完上面两个后,我们现在就要考虑pos的特殊插入了,如果我们pos就在链表头部时,
  • 此时我们的pos之前插入就相当于我们的头插,如果不是,我们来通过逻辑图分析一下一般情况

在pos后插入x

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    SLTNode* cur = BuySListNode(x);
    cur->next = pos->next;
    pos->next = cur;
}
  • 这部分就比较简单啦,我们通过与之前的SLTFind找到pos的位置,把它next里下一个节点的地址给我们要插入的cur,再让pos的next指向cur就行了。

3.删除pos位置的值 SLTErase以及删除pos下一位的值 SLTEraseAfter

删除pos位置的值

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    SLTNode* cur = *pphead;
    assert(pos);
    assert(pphead);
    if (pos == *pphead)
    {
        SLTPopFront(pphead);
    }
    else
    {
        while (cur)
        {
            if (cur->next == pos)
            {
                cur->next = pos->next;
                free(pos);
            }
            cur = cur->next;
        }
    }
}
  • 对于断言的分析同上这里不赘述,我们这里是删除,当pos在表头时,删除这个节点,就是我们的头删,当一般情况时,逻辑分析图如下:

删除pos后一位的值

// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
    assert(pos);
    //检查是否是尾节点
    assert(pos->next);
    pos->next = pos->next->next;
    free(pos->next);
    pos->next = NULL;
}
  • 这个我们既然知道pos了,想删除pos的下一个直接把pos的next指向下一个节点的next即可,最后再free(pos->next),然后置空。

4.单链表的销毁

  • 当我们的链表用完后,由于我们的单链表是动态开辟的,所以也需要free释放一下然后置空。
// 单链表的销毁
void SListDestroy(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* cur = *pphead;
    while (cur)
    {
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}
  • 通过遍历的方式把每个节点都给free释放,最后把头指针置空,链表销毁。

总结

  • 由于篇幅有限,今天的内容到这里就结束了,本篇我们把剩下没讲的接口讲完了,之后会再带大家做几道oj题让大家更加熟悉链表的实际应用。
  • 相信如果你能一直跟着坚持下去那么你链表这一块的初阶知识就一定没什么问题啦!切记要自己上手敲敲代码哦!
  • 好了,如果你有任何疑问欢迎在评论区或者私信我提出,大家下次再见啦!


目录
相关文章
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
240 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
384 25
|
9月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
386 5
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
11月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
332 5
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
110 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
149 2
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
183 1

热门文章

最新文章