【数据结构】手搓链表

一、定义

typedef struct node_s
{
    int _data;
    struct node_s *_next;
} node_t;

typedef struct list_s
{
    node_t *_head;
    node_t *_tail;
} list_t;
  1. 节点结构体(node_s)

    • int _data;存储节点中的数据
    • struct node_s *_next;:指向 node_s 类型的指针,用来指向链表中的下一个节点
  2. 链表结构体(list_s)

    • node_t *_head;:这是一个指向 node_s 类型的指针,用来指向链表的第一个节点,即头节点。如果链表为空,那么 _head 应该指向 NULL
    • node_t *_tail;:这是一个指向 node_s 类型的指针,用来指向链表的最后一个节点,即尾节点。如果链表为空,那么 _tail 也应该指向 NULL

链表的结构图如下:

初始化:

头尾结点指针均置为空

void init(list_t *l)
{
    l->_head = NULL;
    l->_tail = NULL;
}

 二、插入

1、头插法

由于函数需要更改pHead的指向,而pHead是指向Head结点的指针类型为node_t *,所以函数需要传入pHead的地址即:node_t **二级指针,如图所示传入ppHead和ppTail

  • 若链表为空,则头尾指针均指向新节点
  • 若不为空,则新结点与pHead指向相同,即指向Head,再将pHead前移

void headInsert(node_t **ppHead, node_t **ppTail, int data)
{
    node_t *pNew = (node_t *)malloc(sizeof(node_t));
    bzero(pNew, sizeof(node_t));
    pNew->_data = data;
    if (*ppHead == NULL)
    {
        *ppHead = pNew;
        *ppTail = pNew;
    }
    else
    {
        pNew->_next = *ppHead;
        *ppHead = pNew;
    }
}

2、尾插法

参数与头插法相同

  • 若链表为空,则头尾指针均指向新节点
  • 若不为空,则pTail指向的Tail结点的_next指向新节点,再将pTail后移
void tailInsert(node_t **ppHead, node_t **ppTail, int data)
{
    node_t *pNew = (node_t *)malloc(sizeof(node_t));
    bzero(pNew, sizeof(node_t));
    pNew->_data = data;
    if (*ppHead == NULL)
    {
        *ppHead = pNew;
        *ppTail = pNew;
    }
    else
    {
        (*ppTail)->_next = pNew;
        *ppTail = pNew;
    }
}

三、遍历

void visit(node_t *pHead)
{
    node_t *pCur = pHead;
    while (pCur)
    {
        printf("%d ", (*pCur)._data);
        pCur = pCur->_next;
    }
    printf("\n");
}

四、测试

1、头插法

list_t list;
init(&list);
for (int i = 0; i < 10; i++)
{
    headInsert(&list._head, &list._tail, i);
    visit(list._head);
}

运行结果: 

2、尾插法

list_t list;
init(&list);
for (int i = 0; i < 10; i++)
{
    tailInsert(&list._head, &list._tail, i);
    visit(list._head);
}
return 0;

运行结果: 

五、使用C++对其封装

class List
{
public:
    List();
    ~List();
    void push_back(int data);
    void push_front(int data);
    void visit();

private:
    typedef struct node_s
    {
        int _data;
        struct node_s *_next;
    } node_t;

    node_t *_pHead;
    node_t *_pTail;
};
List::List()
{
    _pHead = nullptr;
    _pTail = nullptr;
}
List::~List()
{
    node_t *pCur = _pHead;
    node_t *temp = nullptr;
    while (pCur)
    {
        temp = pCur;
        pCur = pCur->_next;
        delete temp;
        temp = nullptr;
    }
}
void List::push_back(int data)
{
    node_t *pNew = new node_t();
    pNew->_data = data;
    pNew->_next = nullptr;
    if (_pHead == nullptr)
    {
        _pHead = pNew;
        _pTail = pNew;
    }
    else
    {
        pNew->_next = _pHead;
        _pHead = pNew;
    }
}
void List::push_front(int data)
{
    node_t *pNew = new node_t();
    pNew->_data = data;
    pNew->_next = nullptr;
    if (_pHead == nullptr)
    {
        _pHead = pNew;
        _pTail = pNew;
    }
    else
    {
        _pTail->_next = pNew;
        _pTail = pNew;
    }
}
void List::visit()
{
    node_t *pCur = _pHead;
    while (pCur)
    {
        std::cout << (*pCur)._data << " ";
        pCur = pCur->_next;
    }
    std::cout << "\n";
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/929210.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Win11的Bug】无法在文件夹中创建txt文件

问题 右键只能新建文件夹 , 无法新建txt文本文档 解决办法 将注册表中的一个参数从1改为0即可. 具体内容: WinR输入regeditHKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System 将1改为0(下面这张图我已改过) 4.然后重新启动电脑即可 小技…

基于Matlab三点雨流计数法的载荷时间历程分析与循环疲劳评估

随着工程领域中机械设备和结构系统的复杂性不断增加&#xff0c;疲劳分析成为评估其可靠性与使用寿命的关键环节。载荷时间历程数据在疲劳分析中扮演着重要角色&#xff0c;而雨流计数法作为经典的循环计数方法&#xff0c;能够有效地从载荷时间历程中提取疲劳载荷循环信息。本…

二、部署docker

二、安装与部署 2.1 安装环境概述 Docker划分为CE和EE&#xff0c;CE为社区版&#xff08;免费&#xff0c;支持周期三个月&#xff09;&#xff0c;EE为企业版&#xff08;强调安全&#xff0c;付费使用&#xff09;。 Docker CE每月发布一个Edge版本&#xff08;17.03&…

python + PPT

ppt转化为word 对于PPT中的文本内容&#xff0c;如何转化为word内容呢&#xff1f;下面的代码可以实现如下功能 代码如下&#xff1a; from pptx import Presentation from docx import Documentdef clean_text(text):"""清理文本&#xff0c;移除控制字符&quo…

linux运维命令

防火墙相关命令 防火墙规则查看 firewall-cmd --list-all 禁ping firewall-cmd --permanent --add-rich-rulerule protocol valueicmp drop firewall-cmd --reload 执行完以上命令后&#xff0c;通过firewall-cmd --list-all查看规则生效情况 firewall-cmd --list-all 其…

论文笔记:Asymptotic Midpoint Mixup for Margin Balancing and Moderate Broadening

1. Motivation 在特征空间中&#xff0c;特征之间的collapse会导致representation learning 中的关键问题&#xff0c;这是因为特征之间不可区分。基于线性插值的增强方法&#xff08;例如 mixup&#xff09;已经显示出它们在缓解类间塌陷&#xff08;称为inter-class collaps…

Elasticsearch之索引的增删改查(6.x版本)-yellowcong

1. 节点信息查看 #查看集群健康情况 curl -X GET localhost:9200/_cat/health?v&pretty#查看节点信息 curl -X GET localhost:9200/_cat/nodes?v&pretty 2. 索引管理 在es中&#xff0c;索引就相当于是mysql中的库了。 #查看索引列表 curl -X GET localhost:9200/…

Linux红帽认证有哪些等级?RHCE含金量如何?

工 仲 好&#xff1a;IT运维大本营哈喽&#xff0c;大家好&#xff01; 红帽认证&#xff0c;作为一个备受瞩目的认证体系&#xff0c;其完善程度在行业内有口皆碑。 它清晰地划分为三个等级&#xff0c;分别是初级、中级和高级&#xff0c;每个等级都具有独特的要求和价值。…

ArcGIS求取多个点距离线要素的最近距离以及距离倒数

本文介绍在ArcMap软件中&#xff0c;对于点要素中的每一个点&#xff0c;求取其距离最近的道路的距离、距离倒数的方法。 首先&#xff0c;看一下本文的需求。现在已知一个点要素&#xff0c;其中含有多个点&#xff0c;假设每一个点表示城市中的一家商店&#xff1b;同时&…

大数据实验E5HBase:安装配置,shell 命令和Java API使用

实验目的 熟悉HBase操作常用的shell 命令和Java API使用&#xff1b; 实验要求 掌握HBase的基本操作命令和函数接口的使用&#xff1b; 实验平台 操作系统&#xff1a;Linux&#xff08;建议Ubuntu16.04或者CentOS 7 以上&#xff09;&#xff1b;Hadoop版本&#xff1a;3…

跑一下pyapp

文档&#xff1a;How-to - PyApp 首先没有rust要安装 安装 Rust - Rust 程序设计语言 查看是否安装成功 然后clone下pyapp https://github.com/ofek/pyapp/releases/latest/download/source.zip -OutFile pyapp-source.zip 进入目录中&#xff0c;cmd&#xff0c;设置环境…

Python_Flask01

所有人都不许学Java了&#xff0c;都来学Python&#xff01; 如果不来学的话请网爆我的老师---蔡老师 Flask的前世姻缘 我不知道&#xff0c;没啥用&#xff0c;要学好这个框架&#xff0c;其实多读书&#xff0c;多看报就行了&#xff0c;真心想了解的话&#xff01; Welcom…

Unity性能优化---动态网格组合(一)

网格组合是将 Unity 中的多个对象组合为一个对象的技术。因此&#xff0c;在多物体的场景中&#xff0c;使用网格组合&#xff0c;会有效的减少小网格的数量&#xff0c;最终将得到一个包含许多小网格的大网格游戏对象&#xff0c;这将提高游戏或模拟器的性能。在Unity 的 “St…

Docker 逃逸突破边界

免责声明 本博客文章仅供教育和研究目的使用。本文中提到的所有信息和技术均基于公开来源和合法获取的知识。本文不鼓励或支持任何非法活动&#xff0c;包括但不限于未经授权访问计算机系统、网络或数据。 作者对于读者使用本文中的信息所导致的任何直接或间接后果不承担任何…

Kafka知识体系

一、认识Kafka 1. kafka适用场景 消息系统&#xff1a;kafka不仅具备传统的系统解耦、流量削峰、缓冲、异步通信、可扩展性、可恢复性等功能&#xff0c;还有其他消息系统难以实现的消息顺序消费及消息回溯功能。 存储系统&#xff1a;kafka把消息持久化到磁盘上&#xff0c…

vue-cli创建项目报错:command failed: npm install --loglevel error

网上解决方法有很多&#xff0c;对于我都没用。 最后用这个方法起了作用&#xff1a; 尝试将npm源设置为HTTP&#xff0c;慎用&#xff0c;可能不安全 npm config set registry http://registry.npm.taobao.org/ 改为http就顺利创建项目了。

STL算法之sort

STL所提供的各式各样算法中&#xff0c;sort()是最复杂最庞大的一个。这个算法接受两个RandomAccessIterators(随机存取迭代器)&#xff0c;然后将区间内的所有元素以渐增方式由小到大重新排列。还有一个版本则是允许用户指定一个仿函数代替operator<作为排序标准。STL的所有…

Spring Shell如何与SpringBoot集成并快速创建命令行界面 (CLI) 应用程序

Spring Shell 介绍 Spring Shell 是一个强大的工具&#xff0c;可用于构建命令行应用程序&#xff0c;提供了简单的方式来创建和管理交互式 CLI。它适合那些希望通过命令行与 Java 应用程序进行交互的开发者&#xff0c;尤其是在需要自动化、交互式输入或与 Spring 生态系统集…

圣桥ERP queryForString.dwr SQL注入漏洞复现

0x01 产品描述: 杭州圣乔科技有限公司主要研发全套工业企业ERP系列软件产品,现在公司已经形成ERP 软件、OA办公管理、等四大系列二十小类软件产品。致力于为政府、教育、医疗卫生、文化事业、公共事业(电、水、气等)、交通、住建、应急、金融、电信运营商、企业等用户提供专…

SystemUI修改状态栏电池图标样式为横屏显示(以Android V为例)

SystemUI修改状态栏电池图标样式为横屏显示(以Android V为例) 1、概述 在15.0的系统rom产品定制化开发中&#xff0c;对于原生系统中SystemUId 状态栏的电池图标是竖着显示的&#xff0c;一般手机的电池图标都是横屏显示的 可以觉得样式挺不错的&#xff0c;所以由于产品开发…