【35天从0开始备战蓝桥杯 -- Day8】
🫧个人主页：小年糕是糕手
💫个人专栏：《C++》《Linux》《数据结构》《C语言》
🎨你不能左右天气，但你可以改变心情；你不能改变过去，但你可以决定未来！
目录
数据结构其实还有一部分前言这里我们不过多概述了要是感兴趣的家人可以去找一本数据结构的书籍然后看看他的前言部分了解一下逻辑结构与存储结构。
我们学编程经常会听别人说算法或者学习的时候经常会看到网课老师教我们要好好学习算法，那到底什么是算法呢？
算法其实就是我们通过一些列程序将一个输入结果转成我们的输出结果，其实算法是一种很常见的东西不需要给他想的多么高大上，但是好的算法确实是很多程序员的追求，好的算法就离不开时间复杂度和空间复杂度，那这两个词是什么意思呢？下面我们就来进行讲解：
一、复杂度
1.1、时间复杂度
在计算机科学中，算法的时间复杂度是一个函数式 T(N)，它定量描述了该算法的运行时间，这个 T(N) 函数式计算了程序中语句的执行次数。
下面给出一个案例，计算一下fun中++count语句总共执行了多少次？
void fun(int N) { int count = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ++count; // 执⾏次数是 n*n，也就是 n^2 } } for (int k = 0; k < 2 * N; k++) { ++count; // 执⾏次数是 2*n } int M = 10; while (M--) { ++count; // 执⾏次数 10 } } 如果每次都这样计算我们的时间复杂度未免有点太过于麻烦了，而且也不好表示，我不能和别人比较时间复杂度的时候我的是T(N)是N，他的是N+1我就说我的算法比他好，这显然有点荒谬了，下面有几种方法可以帮助我们解决这种问题：
1°大O表示法
在上述案例中，对 N 取值进行分析，随着 N 的增大，对结果影响最大的一项是N^2，2×N 和 10 可以忽略不计，算法执行时间的增长率与 T(N) 中的 N^2 的增长率基本一致。
因此，在计算时间复杂度的时候，一般会把 T(N) 中对结果影响不大的项忽略掉，该种表示时间复杂度的方式称为大O渐进时间复杂度 - 粗略的估计方式，只看影响时间开销最大的一项。
所以对于上述fun函数，其时间复杂度为O(T(N))=O(N^2+2N+10)，取最高阶项最终为：O(N^2)
推导大O 渐进时间复杂度的规则：时间复杂度函数式 T(N) 中，只保留最高阶项，去掉那些低阶项；如果最高阶项存在且不是 1，则去除这个项目的常数系数；T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。
练习：根据下面各个算法时间复杂度的函数式，写出它大O表示下的时间复杂度。T(N)=6×N+9×N^3+10000T(N)=4950T(N)=3×N+5×N+9604T(N)=3×logN+123
这里练习的答案很明显了，1.O(N^3)；2.O(1)；3.O(N)；4.O(logN)
这里为大家总结一下就是：找最高次数项，去掉系数；没有 N 相关项就写 O (1)
2°最优、平均和最差时间复杂度
下面我们依旧来看一个案例：
在n个整形元素数组中，检测x是否存在，若存在返回其在数组中的下标，否则返回-1：
int find(int a[], int n, int x) { for (int i = 0; i < n; i++) { if (a[i] == x) return i; } return -1; } 
3°时间复杂度案例
下面有一篇博客里面有很多关于时间复杂度的案例大家可以自己尝试去解决：
1.2、空间复杂度
在算法竞赛中，空间复杂度就是整个程序在解决这个问题时，一共使用了多少空间。相比较于时间复杂度，空间复杂度就没那么受关注，因为多数情况下题目所给的内存限制是非常宽裕的，而且随着现代计算机的发展其实空间的关注度反而没有这么多了，大家现在第一考虑的都是时间效率，但是这并不代表着空间复杂度不重要了
上述的博客也有对空间复杂度的讲解大家可以参考学习一下，这里不过多赘述
1.3、STL
STL（标准模板库） 是 C++ 内置的一套超级高效、现成、通用的代码工具集合，不用自己手写数组、链表、队列、排序等功能，直接调用即可快速实现数据存储、查找、排序等操作，核心包含容器、算法、迭代器三大组件：容器负责存放数据（如 vector 动态数组、string 字符串、map 键值对），算法提供现成操作（如 sort 排序、find 查找），迭代器作为桥梁让算法能操作容器，它极大简化了代码编写，提升开发效率与程序稳定性，是 C++ 编程最核心、最常用的工具库。
下面的章节及博客我会为大家来慢慢讲解
二、顺序表
2.1、初识顺序表
我们学习顺序表前我们要先来了解一下什么是线性表：
线性表是数据元素按先后顺序排成一列、除首尾外每个元素都只有一个前驱和一个后继的线性结构
方框排成一排，每个格子存一个数据，前后依次相连，就是线性表👇
📦 1 → 📦 2 → 📦 3 → 📦 4 → 📦 5
特点：只有前后关系一个接一个排成一条线除了头尾，每个元素只有一个前驱、一个后继
线性表和顺序表又是什么关系呢？
线性表的顺序存储就是顺序表，如果下图中的方格代表内存中的存储单元，那么存储顺序表中a1~a5这个5元素就是放在连续的位置上：
相信大家不难发现这是很像通过数组来实现的，因为数组完全符合上述的特性，答案也正是如此，那么下面我们就来尝试来模拟实现一下顺序表：
2.2、模拟实现
在模拟实现顺序表前我希望大家知道，我们在学习数据结构的时候一般都是了解增删查改清这五个组件（其实还可以多一个初始化，但是静态顺序表可以采用全局变量，这里不过多赘述），增就是增加元素，也叫插入元素，可以在头部插入，也可以在尾部插入，也可以在指定位置插入，删就是删除，也是同上，查就是查找元素，查找元素也是分为按照下标查找和按值查找的，改就是修改元素，清就是清空我们这个顺序表，其实我觉得叫释放更加合理，首先我们申请数组的时候其实就有很大的区别，我们可以申请动态的和静态的，这里有一篇我写的博客是关于动态顺序表的（下面还会有对动态顺序表的讲解）：
【数据结构】顺序表0基础知识讲解 + 实战演练-ZEEKLOG博客https://blog.ZEEKLOG.net/2501_91731683/article/details/151793507在算法竞赛中，我们主要关心的其实是时间开销，空间上是基本够用的。因此，定义一个超大的静态数组来解决问题是完全可以接受的。因此，关于顺序表，采用的就是静态实现的方式（下面部分只给出关键代码，最后总结会给出完整代码）：
1°增（插入）
//其实这三个函数是有bug的,数组存满了就不能再存了 //当然我们一般不去管这个判断怎么写,因为我们调用的时候会自己判断合不合法 //如果不合法我们是不会调用 //尾插 //时间复杂度 -- O(1) void push_back(int x) { n++; a[n] = x; } //头插 //时间复杂度 -- O(N) void push_front(int x) { for (int i = n; i >= 1; i--) { a[i + 1] = a[i]; } a[1] = x; n++; } //在p位置插入一个新元素(p的位置一定要合法) //时间复杂度 -- O(N) void insert(int p, int x) { for (int i = n; i >= p; i--) { a[i + 1] = a[i]; } a[p] = x; n++; }我们来解释一下这块代码，我们首先定义了一个很大的数组我们用来表示顺序表，然后我们这里是想从下标为1开始去操作这个顺序表，我们首先来看尾插代码，我们定义一个void函数，传入参数x(x是我们想要插入的值)，我们尾插也就是下标为n+1(因为在n的位置插入的话就会占用n位置的元素，n表示的是元素个数)的位置去插入，我们可以直接让n++，这样就表示我们找到最后一个元素的后面一个元素，然后我们可以arr[n]=x，让这个尾部的元素改为x相当于插入；下面我们来看看头插，头插需要我们将后面一个元素依次存储到再后面一个数组空间的位置上，所有我们就要通过循环来遍历，我们肯定是要从n开始遍历的，因为我们要从后往前存储元素值，不然就会造成元素覆盖，我们这里就是arr[n+1]=arr[i]，循环依次遍历最后我们会空出一个arr[1]，这时候我们直接给他的值赋x即可，最后元素的个数自增一；最后我们看看再任意位置插入其实这和头插思路是一样的，头插我们是移动全部，这里我们是移动p后面的位置，将p的位置空出来，然后元素自增一即可
2°删（删除）
//删除前也需要判断函数中是否有元素,没有元素删除就没有意义了 //尾删 //时间复杂度 -- O(1) void pop_back() { //这就相当于数组的元素个数减一,减掉的就是最后一个元素 n--; } //头删 //时间复杂度 -- O(N) void pop_front() { for (int i = 2; i <= n; i++) { a[i - 1] = a[i]; } n--; } //在p位置删除一个元素(p的位置一定要合法) //时间复杂度 -- O(N) void erase(int p) { for (int i = p; i <= n; i++) { a[i] = a[i + 1]; } n--; } 我们依旧来解释上述的这段代码：这里尾删其实就很简单，我们只需要给数组元素个数减一即可，这样就代表最后一个元素不被打印出来；头删就是删除第一个元素，我们只需要将第二个元素放到第一个元素的位置，第三个放到第二个...依照上诉的规律就可以实现删除第一个元素，最后元素个数减一即可；在指定位置删除其实与头删也是非常相似的，一个是删除第一个元素，一个是指定位置，我们从p开始遍历将后面元素前移即可，最后元素个数自减一即可
3°查（查找）
//查找分为两种,分别是按值查找和按位查找 //按值查找 -- 查找值返回下标 //时间复杂度 -- O(N) int find(int x)//x代表我们要查找的元素数值 { for (int i = 1; i <= n; i++) { if (a[i] == x) return i; } return 0;//我们定义的顺序表0下标不表示任何元素 } //按位查找 -- 给一个元素的下标我们去查找对应的值 //时间复杂度 -- O(1) int at(int p)//这里p表示我们要查找的元素的位置 { return a[p]; }查找这段代码其实对比插入和删除就明显简单了许多，我们要查找C++的内容就学习过循环遍历即可，这里需要注意的是按位查找，我们直接返回即可，按值查找才需要我们去循环遍历
4°改（修改）
//修改元素 -- p要合法 //时间复杂度 -- O(1) void change(int p, int x) { //将p位置的元素改为x a[p] = x; }修改元素依旧简单，数组是有下标的我们只需要给数组指定下标位置的元素值更改即可
在最后我们不用数据表肯定要清理，毕竟我们是开拓空间的，而且也花了时间的代价：
5°清（清空）
//清空顺序表 //时间复杂度 -- O(1) void clear() { //直接将有效元素个数清空为0 n = 0; } 2.3、总结
#include<iostream> using namespace std; //根据实际情况来创建 const int N = 1e6 + 10; //全局变量默认为0 //创建顺序表 int a[N];//用足够大的数组来模拟 int n;//n表示当前有多少个元素 //我们给顺序表第一个位置也就是下标为0位置空出来,从下标为1的位置开始存储 //打印顺序表 void print() { for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; } //其实这三个函数是有bug的,数组存满了就不能再存了 //当然我们一般不去管这个判断怎么写,因为我们调用的时候会自己判断合不合法 //如果不合法我们是不会调用 //尾插 void push_back(int x) { n++; a[n] = x; } //头插 void push_front(int x) { for (int i = n; i >= 1; i--) { a[i + 1] = a[i]; } a[1] = x; n++; } //在p位置插入一个新元素(p的位置一定要合法) void insert(int p, int x) { for (int i = n; i >= p; i--) { a[i + 1] = a[i]; } a[p] = x; n++; } //删除前也需要判断函数中是否有元素,没有元素删除就没有意义了 //尾删 void pop_back() { //这就相当于数组的元素个数减一,减掉的就是最后一个元素 n--; } //头删 void pop_front() { for (int i = 2; i <= n; i++) { a[i - 1] = a[i]; } n--; } //在p位置删除一个元素(p的位置一定要合法) void erase(int p) { for (int i = p; i <= n; i++) { a[i] = a[i + 1]; } n--; } //查找分为两种,分别是按值查找和按位查找 //按值查找 -- 查找值返回下标 int find(int x)//x代表我们要查找的元素数值 { for (int i = 1; i <= n; i++) { if (a[i] == x) return i; } return 0;//我们定义的顺序表0下标不表示任何元素 } //按位查找 -- 给一个元素的下标我们去查找对应的值 int at(int p)//这里p表示我们要查找的元素的位置 { return a[p]; } //修改元素 -- p要合法 void change(int p, int x) { //将p位置的元素改为x a[p] = x; } //清空顺序表 void clear() { //直接将有效元素个数清空为0 n = 0; } int main() { //插入 push_back(1); print(); push_back(2); print(); push_back(0); print(); push_back(6); print(); push_front(6416); print(); insert(3, 7); print(); //删除 pop_back(); print(); pop_front(); print(); erase(4); print(); //查找 //直接打印我要查找元素的下标 cout << find(7) << endl; //直接打印我们要查找位置对应元素的数值 cout << at(2) << endl; //修改元素 change(2, 8); print(); clear(); print(); return 0; }这里我们还有一个问题就是我们可能一个顺序表不能解决问题，这时候又该怎么办，这时候肯定有人会想到我们去创建好几个顺序表，这样其实是可行的，简述代码：
#include <iostream> using namespace std; const int N = 1e6 + 10; // 根据实际情况⽽定 // 创建顺序表 // int a[N]; // ⽤⾜够⼤的数组来模拟顺序表 // int n; // 标记顺序表⾥⾯有多少个元素 // 需要多个顺序表，才能解决问题 int a1[N], n1; int a2[N], n2; int a3[N], n3; // 打印顺序表 void print() { for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl << endl; }但是其实这样是比较麻烦的，我们可以借用我们之前学过的类和结构体来封装帮助我们解决这个问题：
#include <iostream> using namespace std; const int N = 1e5 + 10; // 将顺序表的创建以及增删查改封装在⼀个类中 class SqList { int a[N]; int n; public: // 构造函数，初始化 SqList() { n = 0; } // 尾插 void push_back(int x) { a[++n] = x; } // 尾删 void pop_back() { n--; } // 打印 void print() { for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; } }; int main() { SqList s1, s2; // 创建了两个顺序表 for (int i = 1; i <= 5; i++) { // 直接调⽤ s1 和 s2 ⾥⾯的 push_back s1.push_back(i); s2.push_back(i * 2); } s1.print(); s2.print(); for (int i = 1; i <= 2; i++) { s1.pop_back(); s2.pop_back(); } s1.print(); s2.print(); return 0; } 但其实竞赛中我们经常只会使用几个，所有我们最常用的方法还是STL，这样会更加方便
三、容器vector及常用的成员函数
3.1、创建动态顺序表 - vector
因为涉及空间申请和释放的new和delete效率不高，在算法竞赛中使用会有超时的风险。而且实现一个动态顺序表代码量很大，我们不可能在竞赛中傻乎乎的实现一个动态顺序表来解决问题，如果需要用动态顺序表，有更好的方式：C++的STL提供了一个已经封装好的容器 - vector，有的地方也叫作可变长的数组。vector的底层就是一个会自动扩容的顺序表，其中创建以及增删查改等等的逻辑已经实现好了，并且也完成了封装，下面我们就来看看vector的创建：
#include<iostream> #include<vector> using namespace std; const int N = 10; struct node { int a, b; string s; }; int main() { //1，创建 vector vector<int>a1;//创建了一个名字为a1的空的可变长数组,数组里面存放的是整型数据(里面的值默认为0) vector<int>a2(N);//创建了一个的名字为a2大小为10的可变长数组,数组里面存放的是整型数据(里面的值默认为0) //vector<int> a(N) → 1 个 vector，装 N 个数 vector<int>a3(N, 2);//创建了一个大小为10的可变长数组,里面的值都初始化为2 vector<int>a4 = { 1,2,3,4,5 };//初始化列表的创建方式 // <>里面可以存放任意类型的数据,这就体现了模板的作用 //这样vector⾥⾯就可以放我们接触过的任意数据类型,甚⾄是STL vector<string> a5; // 放字符串 vector<node> a6; // 放⼀个结构体 vector<vector<int>> a7; // 甚⾄可以放⼀个⾃⼰,当成⼀个⼆维数组来使⽤.并且每⼀维都是可变的 vector<int> a8[N]; // 创建了10个为空的vector数组(可变长数组),大家要注意和方法二区分开 //vector<int> a[N] → N 个 vector，每个都是空的 return 0; }大家可以先混个脸熟，先了解一下我们通过下面的成员函数操作来慢慢熟悉
3.2、size / empty
size：返回实际元素的个数；empty：返回顺序表是否为空，因此是一个bool类型的返回值。a. 如果为空：返回trueb. 否则，返回false
时间复杂度：O(1)。
#include<iostream> #include<vector> using namespace std; void test_size() { //创建一个一维数组,大小为6,里面的元素初始化为8 vector<int>a1(6, 8); for (int i = 0; i < a1.size(); i++) { cout << a1[i] << " "; } cout << endl << endl;; //创建一个3行4列的二维vector,所有元素默认都是5 vector<vector<int>>a2(3, vector<int>(4, 5)); for (int i = 0; i < a2.size(); i++)//一共有三行 { //这⾥的a2[i]相当于⼀个vector<int>a(4,5) //也就是我们有1行,有4个元素,每个都是5 -- 4列 for (int j = 0; j < a2[i].size(); j++) { cout << a2[i][j] << " "; } cout << endl; } cout << endl << endl; } void test_empty() { //创建一个一维数组,大小为3,里面的元素为空 vector<int>a3(3); if(a3.empty()) cout<<"这个变长数组不为空"<<endl; else cout<<"这个变长数组为空"<<endl; } int main() { test_size(); test_empty(); return 0; }
3.3、begin / end
begin：返回起始位置的迭代器（左闭）；end：返回终点位置的下一个位置的迭代器（右开）；
利用迭代器可以访问整个vector，存在迭代器的容器就可以使用范围for遍历。
#include<iostream> #include<vector> using namespace std; void test() { //创建了一个大小为10的数组,初始化为1; vector<int>a(10, 1); //迭代器类型是vector<int>::iterator //这里写起来比较麻烦我们一般使用auto简化 for (vector<int>::iterator it = a.begin(); it != a.end(); i++) { cout << *it << " "; } cout << endl << endl; //使用语法糖 -- 范围for去遍历 for (auto e : a) { cout << e << " "; } cout << endl << endl; } int main() { test(); return 0; }
3.4、push_back / pop_back
push_back：尾部添加一个元素pop_back：尾部删除一个元素
当然还有insert与erase。不过由于时间复杂度过高，尽量不使用。
时间复杂度：O(1)。
#include<iostream> #include<vector> using namespace std; void print(vector<int>& a) { for (auto e : a) { cout << e << " "; } cout << endl; } void test() { vector<int>a; //尾插 a.push_back(1); a.push_back(2); a.push_back(0); a.push_back(6); a.push_back(416); print(a); //尾删 a.pop_back(); a.pop_back(); a.pop_back(); print(a); } int main() { test(); return 0; }
在vector<int>& a的主要目的是避免拷贝整个 vector。
详细原因：提高效率：如果使用传值（vector<int> a），函数调用时会触发vector的拷贝构造函数，将整个vector的所有元素复制一份。当vector很大时（例如包含数万个元素），这种拷贝会消耗大量内存和时间。而使用引用传递，函数直接操作原始对象，不需要任何复制，效率极高。保持语义：vector的内容，并不需要修改它。使用引用（最好是const引用）可以清晰地表明函数不会修改实参，同时避免了拷贝。符合惯用法：在 C++ 中，对于非基本类型的参数（尤其是容器、字符串等），如果不需要修改且希望避免拷贝，通常传递const引用。虽然本例中没有加const，但依然使用了引用，已经避免了拷贝。补充说明：更规范的写法应该是void print(const vector<int>& a)，这样既能避免拷贝，又能防止函数内部意外修改原数据。但即使不加const，使用引用也比传值要高效得多。
大家记住这样是为了提高效率即可
3.5、front / back
front：返回首元素；back：返回尾元素；
时间复杂度：O(1)。
#include<iostream> #include<vector> using namespace std; void test() { vector<int>a(5); for (int i = 0; i < 5; i++) { a[i] = i + 1; } cout << a.front() << " " << a.back() << endl; } int main() { test(); return 0; }
3.6、resize
修改vector的大小。如果大于原始的大小，多出来的位置会补上默认值，一般是0。如果小于原始的大小，相当于把后面的元素全部删掉。
时间复杂度：O(N)。
#include<iostream> #include<vector> using namespace std; void print(vector<int>& a) { for (auto e : a) { cout << e << " "; } cout << endl; } void test_resize() { vector<int>a(5, 1); a.resize(10);//扩大 print(a); a.resize(3);//缩小 print(a); } int main() { test_resize(); return 0; }
3.7、clear
清空vector
底层实现的时候，会遍历整个元素，一个一个删除，因此时间复杂度：O(N)
#include<iostream> #include<vector> using namespace std; void print(vector<int>& a) { for (auto e : a) { cout << e << " "; } cout << endl; } void test_clear() { vector<int>a(5, 1); print(a); a.clear(); cout << a.size() << endl; print(a); } int main() { test_clear(); return 0; }
vector中的接口还有很多，但是，其余的接口要么不常用；要么时间复杂度较高，比如insert和erase，算法竞赛中不能频繁的调用。因此，在这里以及往后，介绍的都是常用以及高效的接口
3.8、pair（补充）
因为刷题中碰到所有这里只做一个简单展示，让大家可以先去了解，后续题中碰到我们可以理解即可：
pair是 C++ 标准库中的一个模板类，用于将两个值组合成一个单一对象，通常用于存储键值对或返回多个值。它有两个公有成员first和second，分别表示第一个值和第二个值。
我们可以把pair理解成 C++ 为我们提供一个结构体，里面有两个变量：
使用的时候，可以指定first和second为我们想要的任意类型。指定的方式为pair<第一个关键字的类型，第二个关键字的类型>，比如：
不过，一般使用pair的时候，上述方式要写很多代码，我们一般会typedef一下：
后续补充内容我们遇到题目再来讨论
3.9、算法题
下面给出这一节的算法练习，大家可以自己尝试，会面我的C / C++刷题集专栏中也会更新这些题目，感谢大家的支持
UVA101 The Blocks Problem - 洛谷
四、链表
4.1、初识链表
这里也有两篇链表相关的博客供大家参考，大家也可以直接看后面的内容：
【数据结构】单链表“0”基础知识讲解 + 实战演练-ZEEKLOG博客https://blog.ZEEKLOG.net/2501_91731683/article/details/151900038【数据结构】双向链表“0”基础知识讲解 + 实战演练-ZEEKLOG博客https://blog.ZEEKLOG.net/2501_91731683/article/details/153750952我们上面学习了什么是顺序表，我们说过顺序表是线性表的顺序存储，那什么是链表呢？
线性表的链式存储结构就是链表。链表与顺序表最大的区别在于：链表的每个结点除了数据域，还包含一个指针域，通过指针将结点连接起来，从而让相邻元素产生逻辑上的后继关系；而顺序表的元素在物理上连续存放，元素本身是独立存储的，不携带指向其他元素的指针
链表也有静态和动态：动态实现是通过 new 申请结点，然后通过 delete 释放结点的形式构造链表。这种实现方式最能体现链表的特性；静态实现是利用两个数组配合来模拟链表。第一次接触可能比较抽象，但是它的运行速度很快，在算法竞赛中会经常会使用到。
4.2、模拟实现单链表
链表的模拟的模拟实现我们从创增删查这四步来完成，大家不要觉得很难其实他们每一步都是有关联的，实现起来也是非常简单的（我们依旧来看静态实现，动态实现在之前的博客中为大家实现过了，感兴趣的可以自己去看看，但是竞赛中我们关注静态实现即可）：
1°创（创建）
两个足够大的数组，一个用来存数据，一个用来存下一个结点的位置变量h，充当头指针，表示头结点的位置变量id，为新来的结点分位置
这里其实有一点就是这个e和ne是要结合使用的，假设我们现在有ABC三个元素在e中了，我们想在B和C中间去插入一个D，我们只需要去更改ne即可，e中只需要继续存D就好了，所以此时e中的元素就是ABCD，但是实际上是ABDC，我们可以通过下面的ne数组去建立联系
const int N = 1e5 + 10; //创建 //全局变量默认初始化是0 int h; // 头指针 int id; // 下⼀个元素分配的位置 int e[N], ne[N]; // 数据域和指针域 // 下标 0 位置作为哨兵位 // 其中 ne 数组全部初始化为 0，其中 ne[i] = 0 就表⽰空指针，后续没有结点 // 当然，也可以初始化为 -1 作为空指针 我们依旧给出核心代码最后总结部分给出完整代码
2°增（插入）
//头插 //时间复杂度-- O(1) void push_front(int x) { //先让e数组往后走一格 id++; e[id] = x;//存数据 mp[x] = id;//标记x的存储位置 //修改指针 //先让新结点指向头结点的下一个位置 //然后让头结点指向新来的结点 ne[id] = ne[h]; ne[h] = id; } //在p位置后面插入元素x //时间复杂度 -- O(1) void insert(int p, int x) { id++; e[id] = x; ne[id] = ne[p]; ne[p] = id; } 3°查（查找）
//创建 //全局变量默认初始化是0 int h; // 头指针 int id; // 下⼀个元素分配的位置 int e[N], ne[N]; // 数据域和指针域 int mp[N];//mp[i]，表示i这个数存储的位置 //头插 //时间复杂度-- O(1) void push_front(int x) { //先让e数组往后走一格 id++; e[id] = x;//存数据 mp[x] = id;//标记x的存储位置 //修改指针 //先让新结点指向头结点的下一个位置 //然后让头结点指向新来的结点 ne[id] = ne[h]; ne[h] = id; } //在p位置后面插入元素x //时间复杂度 -- O(1) void insert(int p, int x) { id++; e[id] = x; mp[x] = id; ne[id] = ne[p]; ne[p] = id; } //按值查找 -- 查找链表中是否存在元素x,如果存在返回该元素的存储下标 //时间复杂度 -- O(N) int find(int x) { for (int i = ne[h]; i != 0; i = ne[i]) { if (e[i] == x) return i; } return 0; } //我们也可以创建一个新的数组我们用空间替代时间 //时间复杂度 -- O(1) int find(int x) { return mp[x]; }但是方法二很明显具有局限性，数据的值如果特别大的话，我们就不能开辟这么大的数组，这样就得不偿失了，并且链表中如果有重复的数，就无法标记了（除非题目告诉我们链表没有重复的数），我们不知道要去找哪一个下标，所以大家还是要先去掌握方法一，方法二后续会有优化
4°删（删除）
//删除存储位置为 p 后⾯的元素 //时间复杂度 -- O(1) void erase(int p) // 注意 p 表⽰元素的位置 { if (ne[p]) { mp[e[ne[p]]] = 0; // 将 p 后⾯的元素从 mp 中删除 ne[p] = ne[ne[p]]; // 指向下⼀个元素的下⼀个元素 } }5°总结
#include <iostream> using namespace std; const int N = 1e5 + 10; // 创建 int e[N], ne[N], h, id; int mp[N]; // mp[i] 表⽰ i 这个数存储的位置 // 遍历链表 void print() { for (int i = ne[h]; i; i = ne[i]) { cout << e[i] << " "; } cout << endl << endl; } // 头插 void push_front(int x) { id++; e[id] = x; mp[x] = id; // 标记 x 存储的位置 // 先让新结点指向头结点的下⼀个位置 // 然后让头结点指向新来的结点 ne[id] = ne[h]; ne[h] = id; } // 按值查找 int find(int x) { // // 解法⼀：遍历链表 // for(int i = ne[h]; i; i = ne[i]) // { // if(e[i] == x) return i; // } // return 0; // 解法⼆：⽤ mp 数组优化 return mp[x]; } // 在任意位置 p 之后，插⼊⼀个新的元素 x void insert(int p, int x) { id++; e[id] = x; mp[x] = id; ne[id] = ne[p]; ne[p] = id; } // 删除任意位置 p 后⾯的元素 void erase(int p) { if (ne[p]) // 当 p 不是最后⼀个元素的时候 { mp[e[ne[p]]] = 0; // 把标记清空 ne[p] = ne[ne[p]]; } } int main() { for (int i = 1; i <= 5; i++) { push_front(i); print(); } //cout << find(1) << endl; //cout << find(5) << endl; //cout << find(6) << endl; // insert(1, 10); // print(); // insert(2, 100); // print(); erase(2); print(); erase(4); print(); return 0; } 4.3、模拟实现双向链表
我们依旧从静态链表的方式来实现，如果对动态感兴趣的依旧可以参考上述的博客链接内容：双向链表无非就是在单链表的基础上加上一个指向前驱的指针，我们其实可以直接再来一个数组，充当指向前驱的指针域即可，双向链表也就是在单链表的基础上进行简单修改：
1°创（创建）
const int N = 1e5 + 10; //创建双向链表 int e[N];//指向值域 int ne[N];//后继结点 int pre[N];//前驱结点 int h; // 头结点 int id; // 下⼀个元素分配的位置 
2°增（插入）
//头插 //时间复杂度 -- O(1) void push_front(int x) { id++; //首先先存储新的元素 e[id] = x; mp[x] = id; //该新元素的前驱和后继结点指向 pre[id] = h; ne[id] = ne[h]; //他的前驱和后继与他连接 // 先修改头结点的指针，再修改哨兵位，顺序不能颠倒 pre[ne[h]] = id; ne[h] = id; } //在存储位置为p的元素后面，插⼊⼀个元素x //时间复杂度 -- O(1) void insert_back(int p, int x) { id++; e[id] = x; mp[x] = id; // 存⼀下 x 这个元素的位置 // 先左指向 p，右指向 p 的后继 pre[id] = p; ne[id] = ne[p]; // 先让 p 的后继的左指针指向 id // 再让 p 的右指针指向 id pre[ne[p]] = id; ne[p] = id; } //在存储位置为 p 的元素前面，插⼊⼀个元素 x //时间复杂度 -- O(1) void insert_front(int p, int x) { id++; e[id] = x; mp[x] = id; // 存⼀下 x 这个元素的位置 // 先左指针指向 p 的前驱，右指针指向 p pre[id] = pre[p]; ne[id] = p; // 先让 p 的前驱的右指针指向 id // 再让 p 的左指针指向 id ne[pre[p]] = id; pre[p] = id; } 3°查（查找）
//按值查找 //我们使用mp数组来优化 //时间复杂度 -- O(1) int find(int x) { return mp[x]; } 4°删（删除）
//删除下标为 p 的元素 //时间复杂度 -- O(1) void erase(int p) { mp[e[p]] = 0; // 从标记中移除 ne[pre[p]] = ne[p]; pre[ne[p]] = pre[p]; }5°总结
#include<iostream> using namespace std; const int N = 1e5 + 10; //创建双向链表 int e[N];//指向值域 int ne[N];//后继结点 int pre[N];//前驱结点 int mp[N];//用来便于查找 int h; // 头结点--哨兵位 int id; // 下⼀个元素分配的位置 //打印链表 //时间复杂度 -- O(N) void print() { for (int i = ne[h]; i; i = ne[i]) { cout << e[i] << " "; } cout << endl << endl; } //头插 //时间复杂度 -- O(1) void push_front(int x) { id++; //首先先存储新的元素 e[id] = x; mp[x] = id; //该新元素的前驱和后继结点指向 pre[id] = h; ne[id] = ne[h]; //他的前驱和后继与他连接 // 先修改头结点的指针，再修改哨兵位，顺序不能颠倒 pre[ne[h]] = id; ne[h] = id; } //在存储位置为p的元素后面，插⼊⼀个元素x //时间复杂度 -- O(1) void insert_back(int p, int x) { id++; e[id] = x; mp[x] = id; // 存⼀下 x 这个元素的位置 // 先左指向 p，右指向 p 的后继 pre[id] = p; ne[id] = ne[p]; // 先让 p 的后继的左指针指向 id // 再让 p 的右指针指向 id pre[ne[p]] = id; ne[p] = id; } //在存储位置为 p 的元素前面，插⼊⼀个元素 x //时间复杂度 -- O(1) void insert_front(int p, int x) { id++; e[id] = x; mp[x] = id; // 存⼀下 x 这个元素的位置 // 先左指针指向 p 的前驱，右指针指向 p pre[id] = pre[p]; ne[id] = p; // 先让 p 的前驱的右指针指向 id // 再让 p 的左指针指向 id ne[pre[p]] = id; pre[p] = id; } //删除下标为 p 的元素 //时间复杂度 -- O(1) void erase(int p) { mp[e[p]] = 0; // 从标记中移除 ne[pre[p]] = ne[p]; pre[ne[p]] = pre[p]; } //按值查找 //我们使用mp数组来优化 //时间复杂度 -- O(1) int find(int x) { return mp[x]; }4.4、循环链表
循环链表其实是最简单的，我们之前实现的单链表0表示空指针，但其实哨兵位就在0位置，所有的结构正好成环，所以我们之前就已经模拟实现过了循环链表，大家不难发现循环链表和单链表其实没什么区别，只不过是让最后一个元素指向表头即可，构成一个环的结构，这就是循环链表，大家可以自己去刷这章的算法题来加深对循环链表的理解
五、动态链表 -- list
在STL里面的list的底层就是动态实现的双向循环链表，增删会涉及new和delete，效率不高，而且STL中很多容器都是通用的，我们只要会一种就可以很快学习其他的，下面我们就在学了vector的基础上来学习一下list（容器间基本都是通用的，我们这里只展示部分成员函数的用法，其余可以对比vector来自己进行实现，也可以参考C++相关资料）：
5.1、创建list
#include<iostream> #include<list> #include<vector> using namespace std; int main() { vector<int> lt1;//创建一个存储int类型的变长数组 list<int> lt2;//创建一个存储int类型的链表 return 0; }5.2、push_front / push_back
push_front：头插；push_back：尾插。
时间复杂度：O(1)。
#include<iostream> #include<list> #include<vector> using namespace std; void print(list<int>& lt) { for (auto e : lt) { cout << e << " "; } cout << endl; } int main() { vector<int> lt1;//创建一个存储int类型的变长数组 list<int> lt;//创建一个存储int类型的链表 //尾插 for (int i = 1; i <= 5; i++) { lt.push_back(i); print(lt); } //头插 for (int i = 1; i <= 5; i++) { lt.push_front(i); print(lt); } return 0; }
5.3、pop_front / pop_back
pop_front：头删pop_back：尾删
时间复杂度：O(1)。
#include<iostream> #include<list> #include<vector> using namespace std; void print(list<int>& lt) { for (auto e : lt) { cout << e << " "; } cout << endl; } int main() { vector<int> lt1;//创建一个存储int类型的变长数组 list<int> lt;//创建一个存储int类型的链表 //尾插 for (int i = 1; i <= 5; i++) { lt.push_back(i); print(lt); } //头插 for (int i = 1; i <= 5; i++) { lt.push_front(i); print(lt); } //头删 for (int i = 1; i <= 3; i++) { lt.pop_front(); } print(lt); //尾删 for (int i = 1; i <= 3; i++) { lt.pop_back(); } print(lt); return 0; }
