C++详解如何实现单链表

下面我就来为大家详细讲解C++如何实现单链表。

创建链表节点

在C++中,我们通常使用结构体来表示链表节点,结构体中包括了数据域和指向下一个节点的指针域。代码如下:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

在上面的代码中,val为节点中存储的数据,next为指向下一个节点的指针。我们使用一个构造函数来初始化节点,将参数x赋值给val,将next初始化为空指针。

添加节点

要向链表中添加节点,我们需要先找到链表的尾部,然后将新节点插入到尾部后面。具体代码如下:

void addNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* cur = head;
    while (cur->next != nullptr) {
        cur = cur->next;
    }
    cur->next = newNode;
}

在上面的代码中,&head表示head是一个指针的引用,即我们可以通过修改head指针的值来改变链表的头节点。newNode是即将被插入到链表中的新节点。如果链表为空,那么直接将头指针指向新节点即可。如果链表不为空,则需找到链表的尾部,将指向新节点的指针赋值给尾节点的next指针。

删除节点

要删除链表中的一个节点,我们需要先找到目标节点,并记录其前驱节点。然后将前驱节点的next指针指向目标节点的下一个节点即可。需要注意的是,对于头节点的删除,我们需要特殊处理,代码如下:

void deleteNode(ListNode* &head, int val) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* cur = head;
    ListNode* pre = dummy;
    while (cur != nullptr) {
        if (cur->val == val) {
            pre->next = cur->next;
            if (head == cur) head = cur->next; // 对于头节点的删除
            break;
        }
        pre = cur;
        cur = cur->next;
    }
    head = dummy->next;
    delete dummy;
}

在上面的代码中,我们使用一个虚拟节点来记录头指针的前驱节点。如果另外使用一个指针指向头节点的话,头节点的删除操作会比较麻烦。if (head == cur) head = cur->next;是对于头节点的特殊处理,如果发现要删除的节点是头节点,那么需要修改头指针为新的头节点。

示例说明

下面给出两个示例,分别是向链表中添加节点和从链表中删除节点。代码如下:

ListNode* head = nullptr;
addNode(head, 1);
addNode(head, 2);
addNode(head, 3);

在上述示例中,我们首先定义了一个空链表,然后依次添加了值为1、2、3的三个节点。最终链表的头节点指向值为1的节点,链表中有3个元素。

ListNode* head = nullptr;
addNode(head, 1);
addNode(head, 2);
addNode(head, 3);
deleteNode(head, 2);

在上述示例中,我们仍然首先定义了一个空链表,并添加了值为1、2、3的三个节点。然后我们删除了值为2的节点,最终链表中有两个元素,头节点为值为1的节点,尾节点为值为3的节点。

以上就是C++实现单链表的详细攻略。需要注意的是,为了防止内存泄漏,我们在删除节点时需要手动释放内存,即调用delete函数。如有疑问,欢迎继续探讨。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++详解如何实现单链表 - Python技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • Win10系统共享打印机0x000003ec连接失败怎么办?(附解决方法)

    Win10系统共享打印机0x000003ec连接失败怎么办?(附解决方法) 问题描述 在 Win10 系统中,尝试连接共享打印机时,可能会遇到错误提示 0x000003ec,即“Windows 无法安装该打印机”。此时需要解决该问题,才能成功连接共享打印机。 解决方法 方法一:重置打印机池服务 按下快捷键 Win + R 打开运行窗口; 输入 service…

    C 2023年5月23日
    00
  • mysql(5.6及以下)解析json的方法实例详解

    mysql(5.6及以下)解析json的方法实例详解 背景 在以往的开发中,我们通常使用MySQL来存储数据,然而在数据中存在着大量的json类型的数据,如何快速、便捷的解析json数据就变得尤为重要。本文将介绍Mysql(5.6及以下)中解析json类型数据的方法及实例。 操作步骤 使用JSON_EXTRACT()方法解析json数据 JSON_EXTRA…

    C 2023年5月23日
    00
  • win10无法开机提示0xc0000098错误代码怎么办 疑难杂症快速修复

    Win10无法开机提示0xc0000098错误代码怎么办?疑难杂症快速修复 当你遇到win10无法开机提示0xc0000098错误代码时,不要惊慌。以下是针对这种情况的一些快速修复方法。 解决方法1:修复启动记录 如果win10无法开机提示0xc0000098错误代码,可能是启动记录出现了一些问题。我们可以使用 bcdedit 命令进行修复。 步骤 在启动时…

    C 2023年5月23日
    00
  • C++中new和delete匹配使用过程详解

    C++中new和delete匹配使用过程详解 什么是new和delete 在C++中使用new和delete可以动态地分配和释放内存。 new运算符从堆中分配一块大小的内存,而delete运算符则将分配的内存释放。 new的使用 我们可以使用new运算符动态地分配堆内存。其中,new会在堆中分配指定大小的内存,并返回该内存的地址,方便我们进行后续的使用。 以…

    C 2023年5月22日
    00
  • C++实现停车场管理系统的示例代码

    首先我们需要了解C++实现停车场管理系统需要哪些功能。一般来说,停车场管理系统需要实现以下几个功能: 车辆入场、出场登记,记录车辆基本信息。 管理停车场内的车辆信息,如车位数量、车位状态、收费标准等。 计算车辆停留时间和收费金额。 下面我会针对这些功能,提供一个示例代码: 功能1:车辆入场、出场登记 首先,需要定义一个车辆信息的结构体: // 车辆信息结构体…

    C 2023年5月23日
    00
  • C语言实现猜数游戏

    C语言实现猜数游戏攻略 一、简介 C语言实现猜数游戏是一种比较简单的小项目,它可以帮助初学C语言的程序员更好地理解C语言的基本语法,提升程序设计能力。本攻略将介绍实现猜数游戏的完整过程,并提供两个示例。 二、游戏规则 猜数游戏的规则非常简单,程序先生成一个1~100之间的随机整数,玩家需要在规定的次数内猜出这个数字。每次猜数后,程序会根据玩家的猜测结果给出提…

    C 2023年5月23日
    00
  • C语言实现对文件进行操作的示例详解

    下面我将详细讲解“C语言实现对文件进行操作的示例详解”的完整攻略。 一、概述 在C语言中,我们可以通过文件操作来实现对文件的读写、创建、删除等操作。文件操作可以帮助我们读取和保存数据到文件中,以便在程序结束后可以有持久化的数据存储。 文件I/O(输入输出)是通过流来完成的,流是流向的抽象。在文件 I/O 中,数据流是指数据的读入和写出方向。所有的文件 I/O…

    C 2023年5月23日
    00
  • Python中常见的数据类型小结

    让我来为您详细讲解“Python中常见的数据类型小结”的攻略。 一、Python常见的数据类型 Python中常见的数据类型包括数字、字符串、列表、元组、字典和集合,下面分别详细介绍。 1. 数字(Number) 在Python中,数字可以分为整数(int)、浮点数(float)、布尔值(bool)和复数(complex)4种类型。在Python中,数字类型…

    C 2023年5月22日
    00
合作推广
合作推广
分享本页
返回顶部