程序员经验分享-hwhale

基础数据结构：单链表

2023-05-16

定义

单链表是一种线性数据结构，用一组地址任意存储单元来存储数据，存储单元分散在内存任意地址上，存储单元之间用指针连接。

单链表一般有两种：

  • 带头结点的，头结点不存放数据，只是为了操作方便。
  • 不带头结点的。

链表只要得到头指针就可以操作每一个结点。

示例

定义

//数据结点
template <typename T>struct linkeNode
{
    T data;
    linkeNode * next{nullptr};
};

template <typename T> class singlyLinkedList
{
public:
    singlyLinkedList()
    {
    }
    ~singlyLinkedList()
    {
        freeAllNode();
    }
    void append(const T &data);//在末尾插入
    void freeOneNode(linkeNode<T> *node);//清空一个结点
    void freeAllNode();//清空所有结点
    void traverseSequenceList();//遍历
    void insert(const unsigned int index, const T &data);//在index处插入一个结点
    void removeOne(const unsigned int index);//移除index处的结点

private:
    linkeNode<T> * header{nullptr};//首结点指针
};

清除一个结点

//清除一个结点
template <typename T> void singlyLinkedList<T>::freeOneNode(linkeNode<T> * node)
{
    node->next = nullptr;
    free(node);
}

清除所有结点

//清除所有结点
template <typename T> void singlyLinkedList<T>::freeAllNode()
{
    if(header)
    {
        linkeNode<T> * thisNode = header;
        while (thisNode)
        {
            linkeNode<T> * p = thisNode->next;
            freeOneNode(thisNode);
            thisNode = p;
        }
        header = nullptr;
    }
}

在末尾插入 

//在末尾插入
template <typename T> void singlyLinkedList<T>::append(const T & data)
{
    if(!header)
    {
        header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
        header->data = data;
        header->next = nullptr;
        return;
    }

    linkeNode<T> * thisNode = header;
    while (thisNode)
    {
        if(thisNode->next)
        {
            thisNode = thisNode->next;
        }
        else
        {
            linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
            node->data = data;
            node->next = nullptr;
            thisNode->next = node;
            break;
        }
    }
}

遍历 

//遍历
template <typename T> void singlyLinkedList<T>::traverseSequenceList()
{
    if(header)
    {
        linkeNode<T> * thisNode = header;
        int index = {0};
        while (thisNode)
        {
            qDebug()<<"index = "<<index<< thisNode->data;
            if(!thisNode->next)
            {
                break;
            }
            thisNode = thisNode->next;

            ++index;
        }
    }
}

在index处插入 

//在index处插入
template <typename T> void singlyLinkedList<T>::insert(const unsigned int index, const T &data)
{
    if(!header)
    {
        header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
        header->data = data;
        header->next = nullptr;
        return;
    }

    linkeNode<T> * thisNode = header;
    int currentIndex = {1};
    while (thisNode)
    {
        if(currentIndex == index)
        {
            linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
            node->data = data;
            linkeNode<T> * newNodeNext = thisNode->next;
            thisNode->next = node;
            node->next = newNodeNext;
            break;
        }
        thisNode = thisNode->next;
        ++currentIndex;
    }
}

删除index处的数据 

//删除index处的数据
template <typename T> void singlyLinkedList<T>::removeOne(const unsigned int index)
{
    if(!header)
    {
        return;
    }
    if(index == 0)
    {
        linkeNode<T> * headerNextNode = header->next;
        freeOneNode(header);
        header = headerNextNode;
        return;
    }

    linkeNode<T> * thisNode = header;
    linkeNode<T> * lastNode = nullptr;
    int currentIndex = {0};
    while (thisNode)
    {
        if(currentIndex == index)
        {
            linkeNode<T> * willRemoveNode = thisNode;
            lastNode->next = thisNode->next;
            freeOneNode(willRemoveNode);
            break;
        }
        lastNode = thisNode;
        thisNode = thisNode->next;
        ++currentIndex;
    }
}

汇总

#include <QDebug>

//数据结点
template <typename T>struct linkeNode
{
    T data;
    linkeNode * next{nullptr};
};

template <typename T> class singlyLinkedList
{
public:
    singlyLinkedList()
    {
    }
    ~singlyLinkedList()
    {
        freeAllNode();
    }
    void append(const T &data);//在末尾插入
    void freeOneNode(linkeNode<T> *node);//清空一个结点
    void freeAllNode();//清空所有结点
    void traverseSequenceList();//遍历
    void insert(const unsigned int index, const T &data);//在index处插入一个结点
    void removeOne(const unsigned int index);//移除index处的结点

private:
    linkeNode<T> * header{nullptr};//首结点指针
};

//清除一个结点
template <typename T> void singlyLinkedList<T>::freeOneNode(linkeNode<T> * node)
{
    node->next = nullptr;
    free(node);
}

//清除所有结点
template <typename T> void singlyLinkedList<T>::freeAllNode()
{
    if(header)
    {
        linkeNode<T> * thisNode = header;
        while (thisNode)
        {
            linkeNode<T> * p = thisNode->next;
            freeOneNode(thisNode);
            thisNode = p;
        }
        header = nullptr;
    }
}

//在末尾插入
template <typename T> void singlyLinkedList<T>::append(const T & data)
{
    if(!header)
    {
        header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
        header->data = data;
        header->next = nullptr;
        return;
    }

    linkeNode<T> * thisNode = header;
    while (thisNode)
    {
        if(thisNode->next)
        {
            thisNode = thisNode->next;
        }
        else
        {
            linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
            node->data = data;
            node->next = nullptr;
            thisNode->next = node;
            break;
        }
    }
}

//遍历
template <typename T> void singlyLinkedList<T>::traverseSequenceList()
{
    if(header)
    {
        linkeNode<T> * thisNode = header;
        int index = {0};
        while (thisNode)
        {
            qDebug()<<"index = "<<index<< thisNode->data;
            if(!thisNode->next)
            {
                break;
            }
            thisNode = thisNode->next;

            ++index;
        }
    }
}

//在index处插入
template <typename T> void singlyLinkedList<T>::insert(const unsigned int index, const T &data)
{
    if(!header)
    {
        header = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
        header->data = data;
        header->next = nullptr;
        return;
    }

    linkeNode<T> * thisNode = header;
    int currentIndex = {1};
    while (thisNode)
    {
        if(currentIndex == index)
        {
            linkeNode<T> * node = static_cast<linkeNode<T>*>(malloc(sizeof (linkeNode<T>)));
            node->data = data;
            linkeNode<T> * newNodeNext = thisNode->next;
            thisNode->next = node;
            node->next = newNodeNext;
            break;
        }
        thisNode = thisNode->next;
        ++currentIndex;
    }
}

//删除index处的数据
template <typename T> void singlyLinkedList<T>::removeOne(const unsigned int index)
{
    if(!header)
    {
        return;
    }
    if(index == 0)
    {
        linkeNode<T> * headerNextNode = header->next;
        freeOneNode(header);
        header = headerNextNode;
        return;
    }

    linkeNode<T> * thisNode = header;
    linkeNode<T> * lastNode = nullptr;
    int currentIndex = {0};
    while (thisNode)
    {
        if(currentIndex == index)
        {
            linkeNode<T> * willRemoveNode = thisNode;
            lastNode->next = thisNode->next;
            freeOneNode(willRemoveNode);
            break;
        }
        lastNode = thisNode;
        thisNode = thisNode->next;
        ++currentIndex;
    }
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

基础数据结构：单链表 的相关文章

随机推荐

  • FreeRTOS 任务设计注意事项

    1 FreeRTOS中程序运行的上下文包括 xff1a 中断服务函数普通任务空闲任务 1 xff09 中断服务函数是一种需要特别注意的上下文环境 xff0c 它运行在非任务的执行环境下 xff08 一般为芯片的一种特殊运行模式 xff08

  • 2022，程序员应该如何找工作

    最近找工作面了不少公司 xff0c 也有不少感悟和心得 xff0c 今天在这里分享给大家 1 想清楚自己为什么离职 每个人离职都有自己的理由 xff0c 这里列举了一些离职理由 钱给的不够干的不开心没有发展前途加班太严重回老家发展领导不好不

  • 我的四轴飞行器经验总结(一)

    从我看到了TED的演讲和不断冒出来大疆的无人机产品新闻开始 xff0c 我开始爱上了做四轴飞行器 xff0c 有的人可能只当做是一个电子产品制作或者DIY什么的 xff0c 可是我觉的我对四轴飞行器有着更加深的感情 xff0c 就连我的桌面

  • 环境变量设置后不生效

    不需要重启系统 xff0c 只需要重启VS

  • mac os上编译vlc视频库的踩坑之旅

    mac os上编译vlc视频库的踩坑之旅 mac os上编译vlc视频库的踩坑之旅 开始编译VLC视频库 一前期准备工作二参照官方编译文档安装软件三开始编译vlc四踩一些坑五总结 新项目开始目涉及媒体播放 xff0c 在android上多媒

  • 【JAVA】Eclipse保存时出现“Save could not be completed”问题

    问题 xff1a Save could not be completed 原因 xff1a eclipse的默认编译语言是 34 ISO 8859 1 34 xff0c 这个语言不支持中文 xff0c 所以如果编辑的程序含有中文而且编译语言

  •  MX-Linux：在distrowatch上的排名，为什么能够做到第一？

    个人观点 xff1a MX Linux 很好 MX Linux 桌面操作系统的成功 xff0c 主要有以下这几个因素 xff1a A 技术因素 xff1a 1 关键因素 xff1a MX snapshots工具 xff1b 2 次要因素 x

  • Qt 出现“程序异常结束”问题可能的解决思路

    第三方库的编译有问题 请注意 xff0c 出现此种问题绝不止这一个原因 xff0c 还包括其它很多原因 xff0c 这些原因可能千奇百怪 xff0c 需要你的开发经验去积累去发掘 在这里 xff0c 根据我自己的经验 xff0c 总结几种可

  • Qt 中如何在主窗口中添加子窗口

    方法 原理其实简单 和在窗口上动态 代码的形式 添加控件的方法一样 但需要设置一下子窗口的属性 在子窗口构造函数中添加代码 setWindowFlags Qt FramelessWindowHint 作用 隐藏子窗口的标题栏和边框 如果不隐

  • Qt5 自定义字体修改: 字体、大小以及颜色（部分要点已实测）

    Qt设置字体类型及添加字体文件 Qt 添加字体文件 1 设置支持的字体 QFont font font setFamily 34 填写字体名称 34 2 通过字体文件来设置字体 字体的名称可以是自带的 xff0c 也可以是外部的 xff0c

  • Qt QTableWidget 表格自适应 高度和宽度

    1 在MainWindow中设置 对被嵌入的子窗口进行设置 xff0c 去除子窗口的一些影响到嵌入的部件 pTable gt setWindowFlags Qt CustomizeWindowHint Qt FramelessWindowH

  • 互斥信号量和二值信号量的区别

    详解互斥信号量的概念和运行 https blog csdn net weichushun article details 122744773 互斥信号量的主要作用是对资源实现互斥访问 xff0c 使用二值信号量也可以实现互斥访问的功能 xf

  • Qt QTableWidget设置表头、菜单 背景色，以及不成功的原因

    Qt QTableWidget设置表头背景色不成功的原因 QTableWidget没有设置背景色的函数 xff0c 通过Qss样式来设置背景色 m pTable gt horizontalHeader gt setStyleSheet 34

  • Qt记住上次窗口的位置和状态

    include lt QCloseEvent gt include lt QShowEvent gt void MainWindow showEvent QShowEvent event restoreGeometry config gt

  • git-cola 使用方法

    目录 git cola 的用法实践记录 git cola 是 git的图形界面管理工具 因此 xff0c 在安装 git cola之前 xff0c 一般首先需要安装 git 官网地址 xff1a http git cola github i

  • Qt中的 DEPENDPATH 和 INCLUDEPATH 的区别

    在Qt中添加库文件的时候 xff0c Qt会自动在pro文件里生成三行配置 INCLUDEPATH 43 61 dir DEPENDPATH 43 61 dir LIBS 43 61 Ldir llibxxx includepath 和 l

  • STM32--MPU内存保护单元(一)

    先说明一下MPU xff0c MPU有很多含义 xff0c 我们常见的有 xff1a MPU xff1a Memory Protection Unit xff0c 内存保护单元 xff08 本文描述的内容 xff09 xff1b MPU x

  • Qt .pro 官方手册 Creating Project Files （*）

    Creating Project Files Qt 6 5 Creating Project Files qmake Manual Creating Project Files Qt 5 14 Qt 5 14 qmake Manual Cr

  • 感悟 编程思想：Rust，不同于面向过程思想与面向对象思想 （**）

    编程思想的演变 面向过程思想 xff1f 面向对象思想 xff1f Rust语言 xff0c 据说既有面向过程的特征 xff0c 又有面向对象的特点 xff1f 不要过分地拘泥于在一个项目中采用面向过程思想与面向对象思想 实际上 xff0c

  • 基础数据结构：单链表

    定义 单链表是一种线性数据结构 xff0c 用一组地址任意存储单元来存储数据 xff0c 存储单元分散在内存任意地址上 xff0c 存储单元之间用指针连接 单链表一般有两种 xff1a 带头结点的 xff0c 头结点不存放数据 xff0c

热门标签