【数据结构】图文并茂,通过逻辑图带你轻松拿捏链表,实现各种接口功能(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题让大家更加熟悉链表的实际应用。
  • 相信如果你能一直跟着坚持下去那么你链表这一块的初阶知识就一定没什么问题啦!切记要自己上手敲敲代码哦!
  • 好了,如果你有任何疑问欢迎在评论区或者私信我提出,大家下次再见啦!


目录
相关文章
|
12月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
116 1
|
12月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
262 4
|
搜索推荐 C++
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(一)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
138 5
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
127 4
|
数据采集 JavaScript 前端开发
使用 TypeScript 接口优化数据结构
使用 TypeScript 接口优化数据结构
190 11
【初阶数据结构】深入解析队列:探索底层逻辑
【初阶数据结构】深入解析队列:探索底层逻辑
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
135 1
|
12月前
【数据结构】二叉搜索树的功能实现详解
【数据结构】二叉搜索树的功能实现详解
103 0
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(三)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理