做垂直平台网站项目管理软件 project教程

背景知识

链表

与数组不同，链表的元素存储可以是连续的，也可以是不连续的，每个数据除了存储本身的信息（data数据域）之外，还存储一个指示着下一个元素的地址的信息（next指针域），给人的感受就好像这些元素是通过一条“链”串起来的。
链表的第一个节点的存储位置被称为头指针，然后通过next指针域找到下一个节点，直到找到最后一个节点，最后一个节点的next指针域并不存在，也就是“空”的，在C++中，用null来表示这个空指针。

1、虚拟头节点(dummyNode)

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

头指针是链表指向第一个节点的指针，访问链表的入口，经常使用头指针表示链表，头指针是链表必须的
头节点是为了方便操作添加的，不存储实际数据，头节点不一定是链表必须的

2、定义链表节点

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

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

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

3、链表的插入

链表的插入至少应该包括以下操作：
1）创建一个新的链表节点，初始化它的值为val
2）将新的节点放入到链表的尾部，接入链表，也就是当前链表的尾部的next指向新节点
3）新接入的链表节点变为链表的尾部

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

练习题目

链表的基础操作I

题目描述：

构建一个单向链表，链表中包含一组整数数据。输出链表中的所有元素。
要求：

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 <= n <= 1000;

具体代码实现

#include <iostream>
using namespace std;typedef struct ListNode {int val; // 元素值ListNode *next; ListNode(int x) : val(x), next(nullptr) {} // 通过构造函数进行初始化
}ListNode;int main()
{int n;ListNode *dummyNode = new ListNode(0); // 创建哑节点，用于标志链表头while (cin >> n) {int val; // 用于接收链表元素值ListNode *cur = dummyNode; // 创建临时节点，指向哑节点while (n--) {cin >> val;ListNode *newNode = new ListNode(val); // 创建新节点cur->next = newNode; // 当前节点的下一个节点，指向新节点cur = cur->next; // 将新节点作为当前节点}cur = dummyNode; // 将临时节点，再次指向哑节点，用于遍历链表while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}return 0;
}

小白寄语

扎根，做好手头的事，精进。

诗词共勉

人生若只如初见，何事秋风悲画扇。
等闲变却故人心，却道故人心易变。
-----------纳兰性德