【卡码网C++基础课 13.链表的基础操作1】

2024-08-26 22:52
文章标签 基础 c++ 链表 操作 13 基础课 卡码

本文主要是介绍【卡码网C++基础课 13.链表的基础操作1】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 题目描述与分析
  • 一、指针
  • 二、链表
  • 三、定义链表节点
  • 四、链表的插入
  • 五、代码编写

题目描述与分析

题目描述：
构建一个单向链表，链表中包含一组整数数据。输出链表中的所有元素。
要求：
1.使用自定义的链表数据结构
2.提供一个 linkedList 类来管理链表，包含构建链表和输出链表元素的方法
3.在 main 函数中，创建一个包含一组整数数据的链表，然后调用链表的输出方法将所有元素打印出来

输入描述：
包含多组测试数据，输入直到文件尾结束。
每组的第一行包含一个整数 n，表示需要构建的链表的长度。
接下来一行包含 n 个整数，表示链表中的元素。

输出描述：
每组测试数据输出占一行。
按照顺序打印出链表中的元素，每个元素后面跟一个空格。

输入示例：

5
1 2 3 4 5
6
3 4 5 6 7 8

输出示例:

1 2 3 4 5
3 4 5 6 7 8

在之前的学习中，我们接触到了字符串和数组这两种结构，它们具有着以下的共同点:
1.元素按照一定的顺序来排列
2.可以通过索引来访问数组中的元素和字符串中的字符

但是它们也都有着一些缺点：
1.固定大小：数组的大小通常是固定的，一旦分配了内存空间，就难以动态地扩展或缩小，如果需要存储的元素数量超出了数组的大小，就需要重新分配更大的数组，并将原来数组的内容复制过去，需要执行很多额外的操作。
2.内存是连续的：正是因为元素按照一定的顺序来排列，它们在计算机内存中的存储也是连续的，这也就意味着，当需要存储一些需要占用空间较大的内容，也只能找一些大块的内存区域，而空间比较小的内存区域就被浪费了，从而导致了内存资源浪费。
3.固定的数据类型：数组要求所有元素具有相同的数据类型，字符串存储的都是字符，如果需要存储不同类型的数据，数组和字符串就显得无能为力了。

还有重要的一点是，如果我们想要往数组中新增加或者删除一个元素，会特别麻烦！
比如下面的图例，想要往数组中删除第三个元素，当完成删除后，还需要从删除元素位置遍历到最后一个元素位置，分别将它们都向前移动一个位置，也就是说后续的所有元素都要改变自己的位置，这是十分耗时的操作。
在这里插入图片描述
那有没有什么数据结构能够解决上面的问题呢？
那就是我们这节课中将要学习到的链表!

一、指针

在 C++ 中，指针是基本的数据类型，用于存储变量的内存地址。通过指针，你可以直接访问和操作存储在内存中的数据。

声明指针： 指针的声明需要指定指针指向的数据类型，以便解引用时知道内存中应读取多少字节以及如何解释它。

int *ptr; // 声明一个指向整数的指针
// 也可以这样写
int* ptr;

初始化指针： 指针应当被初始化为某个变量的地址，使用取地址符 &。

int var = 10;
int* p = &var;  // p 现在指向 var

使用指针：
1.解引用（使用 * 运算符）允许你访问指针指向的内存地址中的数据。
2.指针算术，比如增加指针（指针移动到下一个数据元素）。

int value = *p;  // 读取 p 指向地址中的值，此处为 10
*p = 20;         // 修改 p 指向的地址中存储的值，var 现在为 20

指针类型：
1.指向基本数据类型的指针：如 int*, char* 等。
2.指向数组的指针：可以使用指针来遍历数组。
3.指向指针的指针（多级指针）：例如，int** 是一个指向 int* 的指针。
4.指向函数的指针：可以用来存储函数的地址，用于回调函数等。

指针与数组密切相关。数组名本质上是指向数组第一个元素的指针。

int arr[3] = {10, 20, 30};
int* ptr = arr;  // 指向数组的第一个元素
for (int i = 0; i < 3; ++i) {cout << *(ptr + i) << " ";  // 输出: 10 20 30
}

指针还可以执行加法、减法等算术操作，以访问内存中的不同位置。

int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // 指向数组的第一个元素
int value = *(ptr + 2); // 获取数组的第三个元素（值为3）

除此之外，还有一个特殊的空指针值，通常表示为nullptr，用于表示指针不指向任何有效的内存地址。

int *ptr = nullptr; // 初始化为空指针

二、链表

链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表提供了在任何位置快速插入和删除节点的能力，这使得它在需要频繁修改的场景下非常有用，例如实现队列、栈和其他复杂的数据结构。
在这里插入图片描述
链表的第一个节点的存储位置被称为头指针，然后通过next指针域找到下一个节点，直到找到最后一个节点，最后一个节点的next指针域并不存在，也就是“空”的，在C++中，用null来表示这个空指针。

为了简化链表的插入和删除操作，我们经常在链表的第一个节点前添加一个节点，称为虚拟头节点(dummyNode)，头节点的数据域可以是空的，但是指针域指向第一个节点的指针。

头指针是链表指向第一个节点的指针，访问链表的入口，经常使用头指针表示链表，头指针是链表必须的

头节点是为了方便操作添加的，不存储实际数据，头节点不一定是链表必须的

链表的类型
单向链表：每个节点只包含一个指向下一个节点的指针。
双向链表：每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。
循环链表：链表的尾部不是指向 nullptr，而是指回链表的头部。

基本操作
链表的基本操作通常包括插入节点、删除节点和遍历链表：
插入节点：可以在链表的头部、尾部或任何指定节点后插入新节点。
删除节点：可以删除链表中的任何节点，需要调整前一个节点的指针以绕过被删除的节点。
遍历链表：从头节点开始，通过节点中的指针移动到链表的尾部。

三、定义链表节点

传统的定义变量的方式只能使用一种数据类型，无法处理链表这种既包含数据域名、又包含指针域的复合结构，这就需要使用到struct结构体，结构体是一种用户自定义的数据类型，比如想要定义一个Person的结构体

// Person结构体
struct Person {// 使用 数据类型 成员变量的形式来定义int age; // int类型的年龄std::string name; // string类型的名字
}

结构体可以组合多个不同类型的成员变量，成员变量可以是各种数据类型，包括整数、浮点数、字符串、其他结构体等，所以你可以根据需要定义自己的结构体来组织数据。

// 链表节点结构体
struct ListNode {int val;  // 存储节点的数据ListNode *next; // 下一个节点也是链表节点，所以也是ListNode类型，*表示指针（地址），next是名称
}

但结构体只是个“模具”，创建的Person结构体虽然具有age、name，但它只是一个Person的概念，无法表示具体的人，只有将其“初始化”，比如"张三，18", “李四、20”，才能真正的使用。

初始化结构体的方式有很多，这里我们使用构造函数的方式来进行，构造函数的名称与结构体的名称相同，和其他函数不一样的是，构造函数没有返回类型，除此之外类似于其他的函数，构造函数也有一个（可能为空）的参数列表和一个函数体（可能为空）。链表结构体的构造函数代码如下：

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

这里的ListNode(int x)表示定义一个接收整数参数 x的名称为ListNode的构造函数（名称和结构体相同），:表示初始化列表的开始，val(x)表示链表数据域的值被初始化为传递的参数 x ，next(nullptr)则表示next指针被初始化为nullptr，表示没有下一个节点。

下面的完整代码定义了一个名为ListNode的结构体，用于表示链表中的一个节点，包含存储节点数据的数据域和存储下一个节点地址的指针域。

// 链表节点结构体
struct ListNode {int val;  // 存储节点的数据ListNode *next; // 指向下一个节点的指针	// 构造函数，用于初始化节点， x接收数据作为数据域，next(nullptr)表示next指针为空ListNode(int x) : val(x), next(nullptr) {}
};

四、链表的插入

上面我们完成了定义链表节点的操作，那应该完成怎样的操作将链表节点插入到链表的尾端，从而形成一个完整的链表呢？至少应该包括以下操作：

创建一个新的链表节点，初始化它的值为val；
将新的节点放入到链表的尾部，接入链表，也就是当前链表的尾部的next指向新节点；
接入的链表节点变为链表的尾部。

假设我们用cur来表示当前链表的尾节点
在这里插入图片描述
上面的操作用代码来表示如下：

ListNode *newNode = new ListNode(val); // 通过new构造一个新的节点,节点的值为val
cur -> next = newNode; // cur节点的next节点是新节点，从而将新节点接入链表
cur = cur -> next;      // 新插入的节点变更为新的尾节点，即cur发生了变更

这里有两个新的语法：new运算符和箭头语法->

new是一个运算符，它的作用就是在堆内存中动态分配内存空间，并返回分配内存的地址，使用方式一般为指针变量 = new 数据类型, 比如下面的代码

int *arr = new int[5]; // 分配一个包含5个整数的数组的内存空间，并返回一个地址，指针arr指向这个地址

箭头语法（->）：用于通过指针访问指针所指向的对象的成员，cur 是一个指向 ListNode 结构体对象的指针，而 next 是 ListNode 结构体内部的一个成员变量（指向下一个节点的指针）。使用 cur->next 表示访问 cur 所指向的节点的 next 成员变量。

五、代码编写

按照题目要求，先把基础的代码结构给写出来

#include <iostream>
using namespace std;
// 定义一个链表节点
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};
int main() { }

一般都会为链表创建一个虚拟头节点

ListNode *dummyHead = new ListNode(0); // 定义了虚拟头结点，dummyNode指向它的地址

之后我们需要根据输入的值构建链表，每组的第一行包含一个整数 n，表示需要构建的链表的长度。

while(cin >> n) {}

可以定义一个指向当前节点的指针 cur，刚开始指向虚拟头结点。

ListNode *cur = dummyHead; // 指针cur指向虚拟头节点

构建一个链表需要以下几步：
接收输入的值，并根据读取的值val创建一个新的链表节点，初始化它的值也为val；
将新的节点放入到链表的尾部，接入链表，也就是当前链表的尾部的next指向新节点；
新接入的链表节点变为链表的尾部；

for (int i = 0; i < n; i++) { // 或者使用while(n--)cin >> val; // 输入链表节点的val值ListNode *newNode = new ListNode(val); // 根据val值构造一个新的节点cur -> next = newNode; // 当前指针的下一个节点为新节点，从而将新节点接入链表cur = cur -> next;      // cur 指向下一个节点（也就是新创建的节点）
}

当输入结束时，链表也就构建完成了，想要输出链表的节点需要从头开始重新遍历, 所以需要将cur重新指向链表的虚拟头节点，循环输出链表可以使用while循环，但是什么时候才可以退出循环呢？

那就是当cur指向最后一个节点的时候，此时cur->next是空指针，也就是说只要cur->next != null就可以一直循环下去，直到cur->next == null退出循环，在循环过程中需要做两件事情：
输出链表节点的值
将cur指向下一个节点

  // 此时构造链表完毕,输出链表节点需要从头遍历
cur = dummyHead;
// 只要cur->next != NULL，说明链表还没有遍历完
while (cur->next != NULL) {// 输入cur的next指针的val值cout << cur->next->val << " ";// 将cur指向下一个节点cur = cur -> next;
}
cout << endl;

链表输出完成后，输出一个换行符，换行输出下一组链表。

cout << endl;

完整代码如下：

#include <iostream>
using namespace std;
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};
int main() {int n, val;ListNode *dummyHead = new ListNode(0); // 定义了虚拟头结点while (cin >> n) {ListNode *cur = dummyHead; // 定义一个临时变量来构建链表for (int i = 0; i < n; i++) { // 或者使用while(n--)cin >> val;ListNode *newNode = new ListNode(val); // 根据读取的值 val 创建一个新的链表节点，并初始化它的值为 valcur -> next = newNode; // 将新节点接入链表cur = cur -> next;      // cur 指向下一个节点}cur = dummyHead;// 遍历链表节点并逐个输出while (cur->next != NULL) {cout << cur->next->val << " ";cur = cur -> next;}cout << endl;}
}

这篇关于【卡码网C++基础课 13.链表的基础操作1】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1109916。

相关文章

Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2