1. 回顾
字符串和数组这两种结构，它们具有着以下的共同点
元素按照一定的顺序来排列可以通过索引来访问数组中的元素和字符串中的字符
但是它们也都有着一些缺点：
固定大小：数组的大小通常是固定的，一旦分配了内存空间，就难以动态地扩展或缩小，如果需要存储的元素数量超出了数组的大小，就需要重新分配更大的数组，并将原来数组的内容复制过去，需要执行很多额外的操作。内存是连续的：正是因为元素按照一定的顺序来排列，它们在计算机内存中的存储也是连续的，这也就意味着，当需要存储一些需要占用空间较大的内容，也只能找一些大块的内存区域，而空间比较小的内存区域就被浪费了，从而导致了内存资源浪费。固定的数据类型：数组要求所有元素具有相同的数据类型，字符串存储的都是字符，如果需要存储不同类型的数据，数组和字符串就显得无能为力了。
还有重要的一点是，如果我们想要往数组中新增加或者删除一个元素，会特别麻烦！
比如下面的图例，想要往数组中删除第三个元素，当完成删除后，还需要从删除元素位置遍历到最后一个元素位置，分别将它们都向前移动一个位置，也就是说后续的所有元素都要改变自己的位置，这是十分耗时的操作。
2. 指针
指针就像是一个地址的引用，它帮助你访问和操作存储在计算机内存中的数据。
可以先把它理解为一个指示牌，这张指示牌上写着某个地方的地址。这个地址指向计算机内存中的一个特定位置，那里存储了一些数据。
想要声明指针，需要使用*符号，比如下面的代码。
// 声明一个指向整数的指针
int *ptr;
// 也可以这样写
int* ptr;
指针想要存放某个变量的地址，需要先使用取地址符&获取地址
int x = 10;
int *ptr = &x; // 将指针初始化为变量x的地址
想要获取这个地址值，需要使用*符号来访问， 这个过程称为解引用
int value = *ptr; // 获取ptr指针指向的值（等于x的值，即10）
指针和数组之间有密切的关系，数组名本质上是一个指向数组第一个元素的指针。
int arr[3] = {1, 2, 3};
int *ptr = arr; // 数组名arr就是指向arr[0]的指针
指针还可以执行加法、减法等算术操作，以访问内存中的不同位置。
int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // 指向数组的第一个元素
int value = *(ptr + 2); // 获取数组的第三个元素（值为3）
除此之外，还有一个特殊的空指针值，通常表示为nullptr，用于表示指针不指向任何有效的内存地址。
// 初始化为空指针
int *ptr = nullptr;
3. 链表
链表的元素存储可以是连续的，也可以是不连续的，每个数据元素处理存储本身的信息（data数据域）之外，还存储一个指示着下一个元素的地址的信息（next指针域）。
1）头指针
链表的第一个节点的存储位置被称为头指针，然后通过next指针域找到下一个节点，直到找到最后一个节点，最后一个节点的next指针域并不存在，也就是“空”的，在C++中，用null来表示这个空指针。
头指针是链表指向第一个节点的指针，访问链表的入口，经常使用头指针表示链表，头指针是链表必须的
2）虚拟头结点
为了简化链表的插入和删除操作，我们经常在链表的第一个节点前添加一个节点，称为虚拟头节点(dummyNode)，头节点的数据域可以是空的，但是指针域指向第一个节点的指针。
头节点是为了方便操作添加的，不存储实际数据，头节点不一定是链表必须的
3）结构体
struct结构体，结构体是一种用户自定义的数据类型
结构体可以组合多个不同类型的成员变量，成员变量可以是各种数据类型，包括整数、浮点数、字符串、其他结构体等，所以你可以根据需要定义自己的结构体来组织数据。
结构体只是个“模具”，创建的Person结构体虽然具有age、name，但它只是一个Person的概念，无法表示具体的人，只有将其“初始化”，比如"张三，18", "李四、20"，才能真正的使用。
4）构造函数
初始化结构体的方式有很多，这里我们使用构造函数的方式来进行，构造函数的名称与结构体的名称相同，和其他函数不一样的是，构造函数没有返回类型，除此之外类似于其他的函数，构造函数也有一个参数列表（可能为空）和一个函数体（可能为空）。
5）⭐定义链表节点
定义一个名为ListNode的结构体，用于表示链表中的一个节点，包含存储节点数据的数据域和存储下一个节点地址的指针域。
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x) , next(nullptr) {}
};
// 定义一个名为ListNode的结构体，用于表示链表中的一个节点，
// 包含存储节点数据的数据域和存储下一个节点地址的指针域。
// 链表节点结构体
struct ListNode
{
// 存储节点的数据
int val;
// 下一个节点也是链表节点，所以也是ListNode类型，*表示指针（地址），next是名称
// 指向下一个节点的指针
ListNode *next;
// 构造函数，用于初始化节点
// x接收数据作为数据域，next(nullptr)表示next指针为空
// ListNode(int x)表示定义一个接收整数参数x的名称为ListNode的构造函数（名称与结构体相同）
// :表示初始化列表的开始
// val(x)表示链表数据域的值被初始化为传递的参数x
// next(nullptr)表示next指针被初始化为nullptr，表示没有下一个节点
ListNode(int x) : val(x), next(nullptr) {}
};
6）⭐链表的插入
怎样将链表节点插入到链表的尾端，从而形成一个完整的链表呢？
用cur来表示当前链表的尾节点
创建一个新的链表节点，初始化它的值为val 将新的节点放入到链表的尾部，接入链表，也就是当前链表的尾部的next指向新节点 新接入的链表节点变为链表的尾部
// 插入链表尾节点
// 通过new构造一个新的节点，节点的值为val
ListNode *newNode = new ListNode(val);
// cur节点的next节点是新节点，从而将新节点接入链表
cur -> next = newNode;
// 更新链表的尾节点cur。新插入的节点变为新的尾节点。
cur = cur -> next;
7）new运算符
new是一个运算符，它的作用就是在堆内存中动态分配内存空间，并返回分配内存的地址，
使用方式一般为：指针变量 = new 数据类型
// 分配一个包含5个整数的数组的内存空间，并返回一个地址，指针arr指向这个地址
int *arr = new int[5];
8）箭头语法->
用于通过指针
访问指针所指向的对象的成员
cur 是一个指向 ListNode 结构体对象的指针，而 next 是 ListNode 结构体内部的一个成员变量（指向下一个节点的指针）
使用 cur->next 表示
访问 cur 所指向的节点的 next 成员变量
。
9）⭐构建链表
构建一个链表需要以下几步
接收输入的值，并根据读取的值val创建一个新的链表节点，初始化它的值也为val 将新的节点放入到链表的尾部，接入链表，也就是当前链表的尾部的next指向新节点 新接入的链表节点变为链表的尾部
// 为链表创建一个虚拟头节点
ListNode *headNode = new ListNode(0);
// 定义一个指向当前节点的指针 cur，刚开始指向虚拟头结点
// 指针cur指向虚拟头节点
ListNode *cur = headNode;
// 构建链表
while(n--)
{
// 输入链表节点的val值
cin >> val;
// 根据val值构造一个新的节点
ListNode *newNode = new ListNode(val);
// 当前指针的下一个节点为新节点，从而将新节点接入链表
cur -> next = newNode;
// 更新尾节点
cur = cur -> next;
}
10）⭐输出链表的节点
输出链表的节点需要从头开始重新遍历。
需要
将cur重新指向链表的虚拟头节点，循环输出链表
可以使用while循环。
什么时候才可以退出循环呢？
当cur指向最后一个节点的时候，此时cur->next是空指针，也就是说只要cur->next != null就可以一直循环下去，直到cur->next == null退出循环。
在循环过程中需要做两件事情
输出链表节点的值更新尾节点cur（将cur指向下一个节点）
// 输出链表节点需要从头遍历
cur = headNode;
while(cur -> next != nullptr)
{
// 输出cur的next指针的val值
cout << cur->next->val << " ";
// 更新尾节点cur
cur = cur -> next;
}
cout << endl;
4.总结
#include
using namespace std;
// 1.定义链表节点
struct ListNode
{
int val;
ListNode *next;
// 2.初始化节点
ListNode(int x) : val(x), next(nullptr) {}
};
int main()
{
int n, val;
// 3.定义虚拟头结点，数据域为空
ListNode *headNode = new ListNode(0);
// 持续输入n。多组测试数据，需要输入多个n
while(cin >> n)
{
// 4.让当前节点指向虚拟头结点，开始构建链表
ListNode *cur = headNode;
// 5.构建链表中
while(n--)
{
cin >> val;
// 构建一个新节点
// 根据读取的值 val 创建一个新的链表节点，并初始化它的值为val
ListNode *newNode = new ListNode(val);
// 将新节点接入链表，让当前节点指向新节点
cur -> next = newNode;
// 更新尾节点，cur指向下一个节点
cur = cur -> next;
}
// 6.构建完毕，从虚拟头结点开始遍历输出链表的值
cur = headNode;
// 7.遍历链表节点并逐个输出
// 注意点：判断条件为尾节点指针域是否为空
while(cur -> next != nullptr)
{
// 输出虚拟头节点指向的第一个节点的值（数据域）
cout << cur->next->val <<" ";
// 更新尾节点
cur = cur -> next;
}
cout << endl;
}
return 0;
}
推荐链接
发表评论