数据结构与算法

虽然第一次学习是在 C++笔记中

第二次复习是在 2023-10-23 ~ 2023-12-18

2026-4-7：当时是先看 hello-algo 学习的，因此这些图片也是从这里截取的
我也推荐你们去 https://www.hello-algo.com/ 去看一下，不知道还能不能找到我的评论

一、什么是算法与数据结构

算法:计算方法

「算法 algorithm」是在有限时间内解决特定问题的一组指令或操作步骤

分为：

• 暴力解答（选择优秀的方法来暴力，如深度还是广度优先还是其他等）

• 公式解答（先计算出公式，以大量节约时间空间）

• 或一起用上面的方法

数据结构：简洁的存储数据的结构

「数据结构 data structure」是计算机中组织和存储数据的方式

数据结构设计是一个充满权衡的过程。如果想要在某方面取得提升，往往需要在另一方面作出妥协。

它们的关系

相互依存的


它们是独立于编程语言的，所有只要会不同语言的语法后，就会一通百通

它们共同简称为算法

二、复杂度分析

2.1 算法效率评估

在算法设计中，一般要先后满足以下目标

• 找到问题解法

• 找到最优解（又快又省）

  • 时间效率高

  • 空间效率高

评估效率有两种方法

• 实际测试 - 输入不同数据量的数据来测试

• 理论估算 - 复杂度分析 （在极大数据量下更优）

复杂度分析：

• 分析所要消耗的时间或空间资源

• 反映了数据量与运行效率之比

• 反映了时间或空间增长的快慢（k 值）

2.2 迭代与递归

重复执行某个任务与算法复杂度密切相关

想要重复执行，常用两种基本结构——迭代与递归

2.2.1 迭代

1. for 循环

它是最常见的迭代形式之一，适合预先知道迭代次数时使用

其的时间复杂度为$O(n)$

2. while 循环

先检查条件是否满足，再执行循环或结束循环当然，c++中还有do...while

for 的代码更紧凑清晰，while 的代码更自由灵活

3. 嵌套循环

循环中内嵌套一个循环

时间复杂度为$O(n^2)$， 其中每嵌套一次循环，时间复杂度增加一次方$O(n^x)$

2.2.2 递归

「递归 recursion」通过函数调用自身来解决问题

1. 递：不断深入的调用自身，将参数传递给下一层，直到达到终止条件
2. 归：从终止条件中，从最终层逐层返回，汇聚每一层的结果

其中包含

• 终止条件：决定何时从“递”到“归”

• 递归调用：对应“递”，通常传入简化/小的参数

• 返回结果：对应“归”

/* 递归 */int recur(int n){    // 终止条件    if (n == 1)    {return 1;}    // 递：递归调用    int res = recur(n - 1);  // resule(结果)的简称    // 归：返回结果    return n + res;} 


递归与迭代分别代表了两种完全不同的思考与解决问题的方式

• 迭代：“自下而上”地解决问题，从最基础开始重复/累加，直到达成条件

• 递归：“自上而下”地解决问题，将原问题分成更小的子问题，它们都有相同的形式，直到基本情况/达成条件/获得已知解后，停止

例：求和 $f(n)=1+2+...+n$

• 迭代：在循环中模拟求和的过程，从一遍历到，直到获得 $f(n)$

• 递归：将问题分解成相同的子问题 $f(n)=n+f(n-1)$ ，不断（递归的）分解下去，直到基本情况 $f(1)=1$ 时终止

1. 调用栈

递归每次调用自身时，需要系统额外分配内存空间，用于储存局部变量，调用地址和其他信息等，因此：

• 函数数据会储存到“栈帧空间”的内存区域中，直到结束才释放，让递归通常比迭代更费内存空间

• 它调用函数时会额外耗时间，使递归通常比迭代的时间效率更低

如下，递归深度为 $n$

在实际中，过深的递归可能会导致栈溢出报错

2. 尾递归

如果函数只有在最后一步才进行递归调用，则它前面的步骤可能被编译器优化到空间效率 $≈$ 递归的，这时被称为「尾递归 tail recursion」

• 普通递归：当函数返回上一层的函数后，需要继续执行代码，因此需要保存上一层调用的上下文

• 尾递归，只有最后一步才调用，且返回上一层后不做其他操作，因此不用保存上一层的上下文

/* 尾递归 */int tail_recur(int n, int res){    // 终止条件    if (n == 0)    {return res;}    // 尾递归调用    return tail_recur(n - 1, res + n);} 

对比上下的图，可以发现：

• 普通递归：求和是在“归”中进行的，返回时都要执行一次求和操作

• 尾递归：求和是在“递”中进行的，“归”时只要返回结果


注：像是Python是默认不支持尾递归优化的，PyPy3可以

3. 递归树

当处理“分治”相关的算法问题时，递归往往比迭代的思路更加直观，代码更加易读，

以“斐波拉契数列”为例：

给一个斐波那契数列$0,1,1,2,3,5,8,13,…$，求该数列的第 $n$ 个数字

解：

• 设第$n$个数字为$f(n)$，则

  • $f(1)=0$ 和$f(2)=1$

  • $f(n)=f(n-1)+f(n-2)$

• 因此：

  C++

  /* 斐波那契数列：递归 */int fib(int n) {	//fibonacci sequence    // 终止条件 f(1) = 1, f(2) = 1    // 注：有些题的fib是 0、1、1、2、3、5，从0开始的    if (n == 1 || n == 2)    {return 1;}    // 递归调用 f(n) = f(n-1) + f(n-2)    int res = fib(n - 1) + fib(n - 2);    // 返回结果 f(n)    return res;}

可发现，我们调用了两个函数，这说明每一次调用会产生两个调用分治，直到产生一个层数为 $n$ 的递「递归树 recursion tree」


从中可以看到递归的本质——“将问题分解成更小的子问题”的思维，这种分治策略是很重要的

• 从算法来看，搜索、排序、回溯、分治、动态规划等算法都直接间接的使用了这种思维方式

• 从数据结构来看，递归天然适合处理链表、树、图的相关问题，因为它们非常适合使用分治思想进行分析

2.2.3 两者对比

内在联系——栈

可以使用“栈”来使用递归模拟递归

/* 使用迭代模拟递归 */int forLoopRecur(int n){    // 使用一个显式的栈来模拟系统调用栈    stack<int> stack;    int res = 0;    // 递：递归调用    for (int i = n; i > 0; i--)    {        // 通过“入栈操作”模拟“递”        stack.push(i);    }    // 归：返回结果    while (!stack.empty())    {        // 通过“出栈操作”模拟“归”        res += stack.top();        stack.pop();    }    // res = 1+2+3+...+n    return res;} 

但这会导致：

• 可读性差

• 模拟耗费的时间空间高，高于原生的（都有了原生的递归方法，还模拟干嘛）

总的来说，选择哪种方法还是要看问题的性质

2.3 时间复杂度

想要获取算法的运行时间，就要

1. 确定运行平台，不同的硬件、编程软件、系统环境都会影响运行效率
2. 评估各种操作所需的运行时间，例如：加法操作 + 需要 1 ns ，乘法操作 * 需要 10 ns ，打印操作 print() 需要 5 ns 等（Python）
3. 统计所有的计算操作

例：输入的数据大小为 $n$

// 在某运行平台下void algorithm(int n){    int a = 2;  // 1 ns    a = a + 1;  // 1 ns    a = a * 2;  // 10 ns    // 循环 n 次    for (int i = 0; i < n; i++) // 1 ns，每轮都要执行 i++    {cout << 0 << endl;}   	    // 5 ns}

可知运行时间 $(6n+12)$ ns

$$1+1+10+(1+5)×n=6n+12$$

但在实际上不能用这种方法，因为各种平台（硬件）不同，编程软件不同等，因此需要其他的方法

2.3.1 统计时间增长趋势

因为统计准确的时间不行，所以我们可以通过统计变化率或大数据来估计

时间复杂度就是分析统计算法的运行时间随数据量变大时的增长趋势，而不是算法运行时间

例：输入的数据大小为 $n$

// 算法 A 的时间复杂度：常数阶void algorithm_A(int n){    cout << 0 << endl;}// 算法 B 的时间复杂度：线性阶void algorithm_B(int n){    for (int i = 0; i < n; i++)    {cout << 0 << endl;}}// 算法 C 的时间复杂度：常数阶void algorithm_C(int n){    for (int i = 0; i < 1000000; i++)    {cout << 0 << endl;}} 

其中：

• 算法A和算法C与输入的 $n$ 无关，因此它们的时间复杂度为 “常数阶”

• 算法B的运行时间随 $n$ 的增大呈线性增长，因此称为 “线性阶”


时间复杂度，相比于直接统计算法的运行时间的特点：

• 能够有效评估算法效率，可以比较在不同 $n$ 的情况下算法的优劣

• 推算方法更加简便，在计算时，将所有计算和执行时间都视为相同的 "单位时间"，从而将“计算操作的运行时间的统计”转换成“数量的统计”，降低了难度

• 但也有局限性，当 $n$ 比较小时，就不好比了，比如A和C，它们在时间复杂度上相同

2.3.2 函数渐进上界

输入的数据大小为 $n$

void algorithm(int n){    int a = 1;  // +1    a = a + 1;  // +1    a = a * 2;  // +1    // 循环 n 次    for (int i = 0; i < n; i++) // +1（每轮都执行 i ++）    {cout << 0 << endl;}	    // +1 } 

设这个算法的操作数量是一个关于 $n$ 的函数，记为 $T(n)$ ，因此：

$$T(n)=3+2n$$

这个一次函数的时间复杂度是线性阶，

我们将线性阶的时间复杂度记为 $O(n)$

这个数学符号称为「大$O$记号 big-$O$notation」，表示函数 $T(n)$ 的「渐近上界 asymptotic upper bound」

时间复杂度分析本质上是计算“操作数量函数 $T(n)$ ”的渐近上界，其具有明确的数学定义。

定义：若存在正实数 $c$ 和实数 $n\_0$ ，使得对于所有的 $n>n\_0$ ，均有 $T(n)≤c · f(n)$ ，则可认为 $f(n)$ 给出了 $T(n)$ 的一个渐近上界，记为 $T(n)=O(f(n))$ 。

如下图所示，计算渐进上界就是寻找一个函数 $f(n)$ 比如: $n^2$、$\log\_{2}{n}$、$1$ 等等，是的当 $n→+∞$ 时，$T(n)$ 和 $f(n)$ 处于相同的增长级别，仅相差一个常数项 $c$ 的倍数


2.3.3 推算方法

由上可知，推算时间复杂度的方法就是找到渐进上界 $f(n)$

第一步：统计操作数量 $T(n)$

1. 忽略常数项 如：$n+1$ 的 $1$

2. 忽略所有系数 如：$3n$ 的 $3$

3. 循环嵌套时使用乘法

   C++

   void algorithm(int n){    int a = 1;  // +0（技巧 1）    a = a + n;  // +0（技巧 1）    // +n（技巧 2）    for (int i = 0; i < 5 * n + 1; i++)    {cout << 0 << endl;}    // +n*n（技巧 3）    for (int i = 0; i < 2 * n; i++)    {        for (int j = 0; j < n + 1; j++)        {cout << 0 << endl;}    }}

   如上，

   $$\begin{aligned} T(n) & = 2n(n + 1) + (5n + 1) + 2 & \text{完整统计 } \newline & = 2n^2 + 7n + 3 \newline T(n) & = n^2 + n & \text{技巧统计} \end{aligned}$$

第二步：判断渐进上界 $O(n)$

时间复杂度由多项式 $T(n)$ 中最高阶的项来决定

因为当 $n→+∞$ 时，最高阶的项将发挥主导作用，其他的就可以忽略了

如上，最后推出时间复杂度为 $O(n^2)$

2.3.4 常见类型

$$\begin{aligned} O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!) \newline \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{线性对数阶} < \text{平方阶} < \text{指数阶} < \text{阶乘阶} \end{aligned}$$

1. 常数阶 $O(1)$

与 $n$ 无关

/* 常数阶 */int constant(int n){    int count = 0;    int size = 100000;    for (int i = 0; i < size; i++)  // size与n无关    {count++;}    return count;}

2. 线性阶 $O(n)$

随 $n$ 以线性增长

常见的有遍历数组和遍历链表，$n$ 为数组或链表的长度

/* 线性阶 */int linear(int n){    int count = 0;    for (int i = 0; i < n; i++)    {count++;}    return count;}

3. 平方阶 $O(n^2)$

随 $n$ 以平方级别增长

常出现在嵌套循环中，内层和外层循环都是 $O(n)$ ，因此总体是 $O(n^2)$

/* 平方阶 */int quadratic(int n){    int count = 0;    // 循环次数与数组长度成平方关系    for (int i = 0; i < n; i++)    {        for (int j = 0; j < n; j++)        {count++;}    }    return count;}

以冒泡排序为例，外层循环执行 $n - 1$ 次，内层循环执行 $n-1、n-2、/dots、2、1$ 次，平均为 $n / 2$ 次，因此时间复杂度为 $O((n - 1) n / 2) = O(n^2)$

/* 平方阶（冒泡排序） */int bubbleSort(vector<int> &nums){    int count = 0; // 计数器    // 外循环：未排序区间为 [0, i]    for (int i = nums.size() - 1; i > 0; i--)    {        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端        for (int j = 0; j < i; j++)        {            if (nums[j] > nums[j + 1])            {                // 交换 nums[j] 与 nums[j + 1]                int tmp = nums[j];                nums[j] = nums[j + 1];                nums[j + 1] = tmp;                count += 3; // 元素交换包含 3 个单元操作            }        }    }    return count;}

4. 指数阶 $O(2^n)$

其常在穷举法（暴力搜索、回溯等）中比较常见，对应数据较大的问题，指数阶是不可接受的，通常要用动态规划或贪心等算法来解决

比如细胞分裂

/* 指数阶（循环实现） */int exponential(int n){    int count = 0, base = 1;    // 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)    for (int i = 0; i < n; i++)    {        for (int j = 0; j < base; j++)        {count++;}        base *= 2;    }    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1    return count;} 


其常出现在递归函数中

如下递归地一分为二，直到 $n$ 次后才停止的代码

/* 指数阶（递归实现） */int expRecur(int n){    if (n == 1)    {return 1;}    return expRecur(n - 1) + expRecur(n - 1) + 1;}

5. 对数阶 $O(\log n)$

与指数阶刚好相反，对数阶是“每轮缩减到一半”的情况，由于此，让循环的次数是 $\log\_{2}{n}$（简称 $\log n$），即 $2^n$ 的反函数

/* 对数阶（循环实现） */int logarithmic(float n){    int count = 0;    while (n > 1)    {        n = n / 2;        count++;    }    return count;}


与指数阶类似，对数阶也常出现在递归函数中，

如下是一个高度为 $\log\_2n$ 的递归树：

/* 对数阶（递归实现） */int logRecur(float n){    if (n <= 1)    {return 0;}    return logRecur(n / 2) + 1;} 

对数阶常出现在基于分治策略的算法中，体现了 “一分为多” 和 “化繁为简” 的算法思想。它增长缓慢，是仅次于常数阶的理想的时间复杂度

$O(\log n)$ 的底数是多少？

准确来说，“一分为 $m$”对应的时间复杂度是 $O(\log\_m n)$ 。而通过对数换底公式，我们可以得到具有不同底数的、相等的时间复杂度：

$$O(\log\_m n) = O(\log\_k n / \log\_k m) = O(\log\_k n)$$

也就是说，底数 $m$ 可以在不影响复杂度的前提下转换。因此我们通常会省略底数 $m$ ，将对数阶直接记为 $O(\log n)$ 。

6. 线性对数阶 $O(n \log n)$

其常出现在嵌套循环中，如下两层循环的时间复杂度分别为 $O(\log n)$ $O(n)$

/* 线性对数阶 */int linearLogRecur(float n){    if (n <= 1)    {return 1;}    int count=linearLogRecur(n/2)+linearLogRecur(n/2);    for (int i = 0; i < n; i++)    {count++;}    return count;}


常见主流的排序算法的时间复杂度通常为 $O(n \log n)$，如：快速排序、归并排序、堆排序等

7. 阶乘阶 $O(n!)$

常见的有 “全排列” 问题

$$n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$$

阶层常用递归实现，如下

/* 阶乘阶（递归实现） */int factorialRecur(int n){    if (n == 0)    {return 1;}    int count = 0;    // 从 1 个分裂出 n 个    for (int i = 0; i < n; i++)    {count += factorialRecur(n - 1);}    return count;} 


因为当 $n≥4$ 时恒有 $n!＞2^n$ ，所以阶层阶会比指数阶增长的更快，在 n 较大时最好寻找其他方法

2.3.5 最差、最佳、平均 时间复杂度

算法的时间效率往往不是固定的，而是与输入数据的分布有关

比如要在一个不重复随机打乱的数组中寻找到 $1$

如果 $1$ 在末尾，则达到了最差时间复杂度 $O(n)$

如果 $1$ 在首个，则达到了最佳时间复杂度 $\Omega(1)$

其中，最差的对应函数的渐近上界，使用 $O$ 表示；最佳的对应函数的渐近下界，用 $\Omega$ 表示

/* 生成一个数组，元素为 { 1, 2, ..., n }，顺序被打乱 */vector<int> randomNumbers(int n){    vector<int> nums(n);    // 生成数组 nums = { 1, 2, 3, ..., n }    for (int i = 0; i < n; i++)    {nums[i] = i + 1;}    // 使用系统时间生成随机种子    unsigned seed = chrono::system_clock::now().time_since_epoch().count();    // 随机打乱数组元素    shuffle(nums.begin(),nums.end() , default_random_engine(seed));    return nums;} /* 查找数组 nums 中数字 1 所在索引 */int findOne(vector<int> &nums){    for (int i = 0; i < nums.size(); i++)    {        // 当元素 1 在数组头部时，达到最佳时间复杂度 O(1)        // 当元素 1 在数组尾部时，达到最差时间复杂度 O(n)        if (nums[i] == 1)        {return i;}    }    return -1;} 

因为最佳的情况很少才能发生，所以常用最差的，用于给出一个效率的安全值，让我们放心的使用算法

因为最佳与最差的情况的概率都很小，所以常用平均时间复杂度

平均时间复杂度可以体现栓发在睡觉输入数据下的运行效率，使用 $\Theta$ 记号

（ $\theta$ 的大写）

平均时间复杂度在上述中为 $\Theta(n / 2) =\Theta({1\over 2} n) = \Theta(n)$

因为 $O$ 相比于 $\Theta$ 好读又好写，因此常直接用 $O$ 表示 $\Theta$

2.4 空间复杂度

和时间的一样，只是将“运行时间”替换成“占用内存空间”

2.4.1 算法相关空间

主要包括以下几种：

• 输入空间：用于存储算法的输入数据

• 暂存空间：用于存储运行时的变量、对象、函数上下文等空间

  • 暂存数据：用于保存各种常量、变量、对象等

  • 栈帧空间：用于保存调用函数的上下文数据 系统在每次调用函数时都会在栈顶创建一个栈帧，当函数返回后，这个栈帧空间就会被释放

  • 指令空间：用于保存编译后的程序命令，在实际统计中常忽略不计

• 输出空间：用于存储算法的输出数据

一般，空间复杂度只统计 “暂存空间” + “输出空间”再细分可以分为：统计 “暂存数据”、“栈帧空间” 和 ”输出数据“ 三部分


如：

/* 结构体 */struct Node{    int val;    Node *next;    Node(int x) : val(x), next(nullptr) {}}; /* 函数 */int func(){    // 执行某些操作...    return 0;} int algorithm(int n)		  // 输入数据{    const int a = 0;          // 暂存数据（常量）    int b = 0;                // 暂存数据（变量）    Node* node = new Node(0); // 暂存数据（对象）    int c = func();           // 栈帧空间（调用函数）    return a + b + c;         // 输出数据}

2.4.2 推算方法

统计对象从 ”操作数量“ 转为 ”使用空间大小“

但区别是，我们通常只关注最差空间复杂度，因为内存空间是硬性要求，需要确保有足够的内存空间预留

如下，有两种最差的情况：

1. 以最差输入数据为准：当 $n < 10$ 时，空间复杂度为 $O(1)$ ；但当 $n > 10$ 时，初始化的数组 nums 占用 $O(n)$ 空间；因此最差空间复杂度为 $O(n)$
2. 以算法运行中的峰值内存为准：例如，程序在执行最后一行之前，占用 $O(1)$ 空间；当初始化数组 nums 时，程序占用 $O(n)$ 空间；因此最差空间复杂度为 $O(n)$

void algorithm(int n){    int a = 0;               // O(1)    vector<int> b(10000);    // O(1)    if (n > 10)    {vector<int> nums(n);}   // O(n)}

在递归函数中，需要注意统计栈帧空间。

如下：

• 函数 loop() 在循环中调用了 $n$ 次 function() ，每轮中的 function() 都返回并释放了栈帧空间，因此空间复杂度仍为 $O(1)$

• 递归函数 recur() 在运行过程中会同时存在 $n$ 个未返回的 recur() ，从而占用 $O(n)$ 的栈帧空间

int func(){    // 执行某些操作    return 0;}/* 循环 O(1) */void loop(int n){    for (int i = 0; i < n; i++)    {func();}}/* 递归 O(n) */void recur(int n){    if (n == 1) {return;}    return recur(n - 1);}

2.4.3 常见类型

$$\begin{aligned} O(1) < O(\log n) < O(n) < O(n^2) < O(2^n) \newline \text{常数阶} < \text{对数阶} < \text{线性阶} < \text{平方阶} < \text{指数阶} \end{aligned}$$

1. 常数阶 $O(1)$

常见于数量与输入的数据大小 $n$ 无关的常量、变量、对象

/* 函数 */int func(){    // 执行某些操作    return 0;} /* 常数阶 */void constant(int n){    // 常量、变量、对象占用 O(1) 空间    const int a = 0;    int b = 0;    vector<int> nums(10000);    ListNode node(0);    // 循环中的变量占用 O(1) 空间    for (int i = 0; i < n; i++)    {int c = 0;}    // 循环中的函数占用 O(1) 空间    for (int i = 0; i < n; i++)    {func();}}

因为上面循环中初始化变量和调用函数而占用的内存，在进入下一轮循环后就被释放了，因此不会积累占用空间，所以空间复杂度仍然为 $O(1)$

2. 线性阶 $O(n)$

其常见于数组、链表、栈、队列等

/* 线性阶 */void linear(int n){    // 长度为 n 的数组占用 O(n) 空间    vector<int> nums(n);    // 长度为 n 的列表占用 O(n) 空间    vector<ListNode> nodes;    for (int i = 0; i < n; i++)    {nodes.push_back(ListNode(i));}    // 长度为 n 的哈希表占用 O(n) 空间    unordered_map<int, string> map;    for (int i = 0; i < n; i++)    {map[i] = to_string(i);}} 

如下的递归深度为 $n$ ，即同时存在 $n$ 个未返回的 linear_recur() 函数，使用了 $O(n)$ 大小的栈帧空间

/* 线性阶（递归实现） */void linearRecur(int n){    cout << "递归 n = " << n << endl;    if (n == 1)    {return;}    linearRecur(n - 1);}

3. 平方阶 $O(n^2)$

常见于二维数组、矩阵、图等，元素数量与 $n$ 成平方关系

/* 平方阶 */void quadratic(int n){    // 二维列表占用 O(n^2) 空间    vector<vector<int>> numMatrix;    for (int i = 0; i < n; i++)    {        vector<int> tmp;        for (int j = 0; j < n; j++)        {tmp.push_back(0);}        numMatrix.push_back(tmp);    }} 

如下，该函数的递归深度为 $n$ ,在每个递归函数中都初始化了一个数组，长度分别为 $n、n-1、…、2、1$，平均长度为 $n/2$ ，因此总体占用 $O(n^2)$ 的空间

/* 平方阶（递归实现） */int quadraticRecur(int n){    if (n <= 0)    {return 0;}    vector<int> nums(n);    cout << "递归 n = " << n << " 中的 nums 长度 = " << nums.size() << endl;    return quadraticRecur(n - 1);} 

4. 指数阶 $O(2^n)$

常见于二叉树

如下一个高度为 $n$ 的 “满二叉树” 的节点数量为 $2^n-1$ ，占用 $O(2^n)$ 空间

/* 指数阶（建立满二叉树） */TreeNode *buildTree(int n){    if (n == 0)    {return nullptr;}    TreeNode *root = new TreeNode(0);    root->left = buildTree(n - 1);    root->right = buildTree(n - 1);    return root;} 


5. 对数阶 $O(\log n)$

常见于分治算法，

比如：

• 归并排序，输入长度为 $n$ 的数组，每轮递归将数组从中点划分为两半，形成高度为 $\log n$ 的递归树，使用了 $O(\log n)$ 的空间

• 将数组转化为字符串，输入一个正整数 $n$ ，它的位数为 $\log\_{10}{n}+1$ ，因此空间复杂度为 $O(\log\_{10}{n})=O(\log n)$

2.4.4 权衡时间与空间

理想情况下，都想要时空复杂度达到最优，但实际上这是很困难的

一般而言，降低时间复杂度通常要以提升空间复杂度为代价的，反之亦然。

常称这种方法叫：“以空间换时间” 或 “以时间换空间”

一般而言，时间比空间宝贵，因此常用 “以空间换时间” ，当然了也不是绝对的，比如数量量很大时

2.5 Q & A

过程式编程（函数），面向对象编程（方法）

C C++ / Python Java / C#

函数（function）可以被独立执行，所有参数都以显式传递。方法（method）与一个对象关联，被隐式传递给调用它的对象，能够对类的实例中包含的数据进行操作。

下面以几个常见的编程语言来说明。

• C 语言是过程式编程语言，没有面向对象的概念，所以只有函数。但我们可以通过创建结构体（struct）来模拟面向对象编程，与结构体相关联的函数就相当于其他语言中的方法。

• Java 和 C# 是面向对象的编程语言，代码块（方法）通常都是作为某个类的一部分。静态方法的行为类似于函数，因为它被绑定在类上，不能访问特定的实例变量。

• C++ 和 Python 既支持过程式编程（函数），也支持面向对象编程（方法）。

三、数据结构

3.1 数据结构分类

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，它们可以从 “逻辑结构” 和 “物理结构” 两个维度进行分类

3.1.1 逻辑结构：线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系

有些是线性关系，有些是祖先与后代的派生关系，有些是网络关系

• 线性数据结构：数组、链表、栈、队列、哈希表

• 非线性数据结构：树、堆、图、哈希表


还可以按照对应关系来分：

• 线性结构：数组、链表、队列、栈、哈希表，元素之间是一对一的顺序关系

• 树形结构：树、堆、哈希表，元素之间是一对多的关系

• 网状结构：图，元素之间是多对多的关系

3.1.2 物理结构：连续与分散

计算机中，主要用硬盘和内存来存储数据

• 硬盘：长期存储，容量较大（TB 级别），速度较慢

• 内存：暂存数据，容量较小（GB 级别），速度较快

在算法运行过程中，相关数据都存储在内存中

系统通过内存地址来访问目标位置的数据。每个内存空间都有唯一的内存地址


内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。

比如：算法所占用的内存峰值不应超过系统剩余空闲内存；如果缺少连续大块的内存空间，那么所选用的数据结构必须能够存储在分散的内存空间内。

物理结构翻译了数据在计算机内存中的存储方式，

可分为：

• 连续空间存储（数组） 连续空间，时间较短

• 分散空间存储（链表） 分散空间，时间较长

物理结构从底层决定了数据的访问、更新、增删等操作方法，同时在时间与空间效率上存在互补的特点


注意：所有的数据结构都是基于数组、链表或两者的组合实现的

例如：栈和队列可以使用数组实现，也可基于链表实现，而哈希表的实现可能同时包含数组和链表

• 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度$≥3$ 的多维数组）等

• 基于链表可实现：栈、队列、哈希表、树、堆、图等

基于数组实现的数据结构被称为 “静态数据结构” ，意味着此类数据结构在初始化后长度不可变

基于链表实现的数据结构被称为 “动态数据结构” ，它们在初始化后，长度仍可以改变

3.2 基本数据类型

像是文本、图片、3D 模型等各种形式都是由各种基本数据类型构成的

**基本数据类型是 CPU 可以进行运算的类型，**在算法中直接被使用，主要包括以下几种类型

• 整数类型：byte、short、int、long

• 浮点类型：float、double，用于表示小数

• 字符类型：char，用于表示包括表情符号等的符号

• 布尔类型：bool，用于表示 “是” 与 "否" 判断

注：不同编程语言可能使用不同的符号来表示这些数

**基本数据类型以二进制的形式存储在计算机中。**一个二进制位（一位）为 $1$ 比特。一般 $1$ 字节（byte）＝ $8$ 比特（bits）

基本数据类型的取值范围取决于其占用空间的大小，

以 Java 为例：

• 整数类型 byte 占用 $1$ byte = $8$ bits ，可以表示 $2^8$ 个数字。

• 整数类型 int 占用 $4$ bytes = $32$ bits ，可以表示 $2^32$ 个数字。

注：

• C/C++中没有明确基本数据类型的大小，根据平台各异

• 字符 char 在 C/C++中为 $1$ 字节，其他语言中要看字符的编码方法

• 布尔类型虽然只要 $1$ 位（$0$ 或 $1$），但在内存中常被存储为 $1$ 字节，因为现代计算机的 CPU 常将 $1$ 字节作为最小寻址内存单元

基本数据类型与数据结构的关系：

数据结构是在计算机中组织与存储数据的方式。它的主语是 “结构” 而非 “数据”，换句话说，基本数据类型提供了数据的 “内容类型”，而数据结构提供了数据的 “组织方式”

// 使用多种基本数据类型来初始化数组int numbers[5];float decimals[5];char characters[5];bool bools[5];

3.3 数字编码

3.3.1 整数编码

由上可知，byte 的取值范围是 ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲-128，127]

因为内存存储分为原码、反码、补码

数字是以“补码”的形式存储在计算机中的

• **原码：**将数字的二进制表示的最高位视为符号位。 $0$ 表示正数，$1$ 表示负数，其余表示数字的值

• **反码：**正数的反码 $=$ 其原码，负数的反码是 $=$ 其原码除符号位以外的位取反

• **补码：**正数的补码 $=$ 其原码，负数的补码 $=$ 其反码+1

「原码 true form」的优点是直观，缺点是负数的原码不能用于运算

例如计算：$1+(−2)$

$$\begin{aligned} & 1 + (-2) \newline & \rightarrow 0000 ; 0001 + 1000 ; 0010 \newline & = 1000 ; 0011 \newline & \rightarrow -3 \end{aligned}$$

因此引入了「反码 1's complement code」，这样就可以计算了

例如计算：$1+(−2)$

$$\begin{aligned} & 1 + (-2) \newline & \rightarrow 0000 ; 0001 ; \text{(原码)} + 1000 ; 0010 ; \text{(原码)} \newline & = 0000 ; 0001 ; \text{(反码)} + 1111 ; 1101 ; \text{(反码)} \newline & = 1111 ; 1110 ; \text{(反码)} \newline & = 1000 ; 0001 ; \text{(原码)} \newline & \rightarrow -1 \end{aligned}$$

但缺点是 $0$ 有 $+0$ 和 $-0$ 两种表示方式，会在比如条件判断中没有区分的话判错

$$\begin{aligned} +0 & \rightarrow 0000 ; 0000 \newline -0 & \rightarrow 1000 ; 0000 \end{aligned}$$

因此引入了「补码 2's complement code」

ParseError: KaTeX parse error: Expected group as argument to '\=' at position 73: …码)} \newline \= ̲; & 1111 ; 1111…

因为 byte 的长度只有 8 位，溢出的第九位就被舍弃了，因此负零的补码为 $0000 ; 0000$ ，与正零的补码相同，该问题也得到了解决

但补码 $1000 ; 0000$ 没有对应的原码，根据转换方法它的原码是 $0000;0000$ 即 $0$ ，因此人为定义它为 $-128$ 。因为 $(-1) + (-127)$ 在补码中的计算结果就是 $-128$

$$\begin{aligned} & (-127) + (-1) \newline & \rightarrow 1111 ; 1111 ; \text{(原码)} + 1000 ; 0001 ; \text{(原码)} \newline & = 1000 ; 0000 ; \text{(反码)} + 1111 ; 1110 ; \text{(反码)} \newline & = 1000 ; 0001 ; \text{(补码)} + 1111 ; 1111 ; \text{(补码)} \newline & = 1000 ; 0000 ; \text{(补码)} \newline & \rightarrow -128 \end{aligned}$$

计算机内部的硬件电路主要是基于加法运算设计的，因为它硬件实现起来简单，更容易并行化处理。当然，也可以将加法与基本逻辑运算结合，这样就能够实现各种其他的数学运算，比如 $a-b$ 转换为 $a+(-b)$ 或多次加法变为乘法，计算多次减法变为除法。

因此，设计补码的根本原因是可以简化正数与负数的加法，不用设计特殊的硬件电路来处理减法与 ±0 歧义问题，简化了硬件设计，提高了运算效率

3.3.2 浮点数编码

浮点数 float 使用了与 int 不同的编码方式，用了 IEEE 754 编码标准

设一个 32-bit 长度的二进制数为：

$$b\_{31} b\_{30} b\_{29} \ldots b\_2 b\_1 b\_0$$

根据其标准，它由以下三部分组成：

• 符号位 $S$ ：占 1 bit ， 对应 $b\_{31}$

• 指数位 $E$ ：占 8 bits， 对应 $b\_{30} b\_{29} \ldots b\_{23}$

• 分数位 $N$ ：占 23 bits，对应 $b\_{22} b\_{21} \ldots b\_0$

因此二进制数 float 对应的值 val 的计算方法是：

$$\text {val(2)} = (-1)^{b\_{31}} \times 2^{\left(b\_{30} b\_{29} \ldots b\_{23}\right)_2-127} \times\left(1 . b_{22} b\_{21} \ldots b\_0\right)\_2$$

转化到十进制的计算公式是：

$$\text {val(10)}=(-1)^{\mathrm{S}} \times 2^{\mathrm{E} -127} \times (1 + \mathrm{N}) \newline \newline \text {val(10)}=(-1)^{\mathrm{S;的十进制}} \times 2^{\mathrm{E;的十进制} -127} \times (1 + \mathrm{N;的十进制})$$

其中各项的取值范围是：

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 163: …^{-i}) \subset \̲[̲1, 2 - 2^{-23}]…

其他：

• 改变指数位的符号就可以得到负数

• float 通过指数位提高了取值范围，但也导致了其精度被牺牲了它的数值越大，相邻的两个数字之间的差值也就会趋向越大

• 指数位 $E=0$ 和 $E=255$ 有特殊含义，用于表示 $0$，$±∞$、$NaN$
  （ $NaN$ 没有的数/未定义的数/无效的数/非法操作得到的数）

次正规数显著的提高了浮点数的精度，因为次正规数就是小数部分，它本身就有 $10^{-7}$ 的精度，再乘以指数部分得到正规数的话，精度就更高了

最小的正 正规数为 $2^{-126} ;(2)$ ，最小的正 次正规数为 $2^{-126} \times 2^{-23} ;(2)$ （$2^{-23} \approx 1.19209 \times 10^{-7}$)

次正规数是指浮点数中，两个相邻的浮点数之间的距离最小的那个数（两个数之间的精度）正规数是指浮点数中，相邻两个浮点数之间的距离相等的一组数。换句话说，正规数是浮点数表示法中能够被准确表示的所有实数的集合。

它俩的区别就是：正规数的精准度比次正规数的精度更高一些

double 的也和 float 的表示方法一样，只是位数变多了，精度变大了

3.4 字符编码

为了在计算机中通过二进制表示字符，因此人们建立了一套 “字符集” ，来表示字符——通过查表查询每个字符与二进制之间的关系，来表示它

3.4.1 ASCII 字符集

「ASCII 码」是最早出现的字符集，全称是 “美国信息交换标准代码”，它使用了一个字节的低 7 位标识一个字符（最高位一直是 0 ）。通过这种方式，可以标识 128 种不同的字符，包括英文字母的大小写、数字 0~9、一些标点符号和控制字符（包括换行符或制表符）

因为 ASCII 码只能表示英文，因此人们通过将首位的 0，改为 1 ，新增了后 128 位用于表示其他字符 其叫「EASCII」。它在每个公司或每个国家的定义都不同，以适应不同语言的需求

3.4.2 GBK 字符集

因为 EASCII 码仍然无法满足许多语言的字符数量要求。比如汉字大约有近 10 万个，因此在 1980 年诞生了「GB2312」字符集（GB 为中国国家标准）

其收录了 6763 个汉字和其他的一些字符，它也是 ASCII 码的扩展

但在之后诞生了「GBK」字符集，以满足处理罕见字与生僻字的需要，共包含了 21886 个汉字，还有一些其他的字符。因为它是由 GB2312 扩展出来的，因此可以直接兼容它。

在 GBK 中，ASCII 字符使用一个字节表示，汉字使用两个直接表示

当然，在后面 2000 年的时候，出现了以 GBK 扩展而来的 GB18030，其包括 2.7 万个汉字

3.4.3 Unicode 字符集

为了统一字符集与编码标准，解决跨语言环境传输与乱码问题，人们推出了一个足够完整的字符集，将世界范围内的所有语言和符号都收录其中，其叫 “Unicode”

「Unicode」的全称为“统一字符编码”，最多可容纳 100 多万个字符，现在它已包含 14 万个字符，包括各种语言的字符、符号、表情包等，也包含了 8 万多个汉字。在其中，常用的字符占用 2 字节，生僻的字符占 3 或 4 字节

因为 Unicode 它只是一种字符集标准，只是给每个字符分配一个编号（称为“码点”）的一张表，但它并没有规定在计算机中如何存储这些字符码点，因此出现了很多种编码标准用于解析字符

其中一种最简单的方法（Unicode 默认编码）就是将所有字符存储为等长的编码，占 1 字节的在 2 字节中就高位填 0

因为上面的编码方法太占内存空间了，因此出现了更加高效的不同的编码方法

3.4.4 UTF-8 编码

目前，它是最广泛使用的 Unicode 编码方法，它是一种可变长的编码，使用 1 到 4 个字符来表示一个字符，更据字符的复杂度来变

ASCII 字符只需要 1 个字节，拉丁字母和希腊字母需要 2 个字节，常用的中文字符需要 3 个字节，其他的一些生僻字符需要 4 个字节。

其通过下面的方式来编码：

• 对于长度为 1 字节的字符，将最高位设置为 $0$、其余 7 位设置为 Unicode 码点。值得注意的是，ASCII 字符在 Unicode 字符集中占据了前 128 个码点。也就是说，UTF-8 编码可以向下兼容 ASCII 码。这意味着我们可以使用 UTF-8 来解析年代久远的 ASCII 码文本。

• 对于长度为 $n$ 字节的字符（其中 $n > 1$），将首个字节的高 $n$ 位都设置为 $1$、第 $n + 1$ 位设置为 $0$ ；从第二个字节开始，将每个字节的高 $2$ 位都设置为 $10$ ；其余所有位用于填充字符的 Unicode 码点。

  这种方法的绿色，最高 $n$ 位都被设置为 $1$ ，因此系统可以通过读取最高位 $1$ 的个数来解析出字符的长度为 $n$ 。

  它的蓝色，也就是 $10$ 是校验符，之所以将 $10$ 当作校验符，是因为在 UTF-8 编码规则下，不可能有字符的最高两位是 $10$ 。这个结论可以用反证法来证明：假设一个字符的最高两位是 $10$ ，说明该字符的长度为 $1$ ，对应 ASCII 码。而 ASCII 码的最高位应该是 $0$ ，与假设矛盾。

因为 UTF-8 编码的前 128 位为 ASCII 码，因此UTF-8 编码可以向下兼容 ASCII 码

除了 UTF-8 之外，还有两种常用的编码方法：

• **UTF-16 编码：**使用 2 或 4 个字节来表示一个字符，ASCII 字符和常用的字符都使用 2 字节表示，其他的使用 4 字节表示，对于 2 字节的字符，UTF-16 编码和 Unicode 码点相等

• **UTF-32 编码：**所有字符都使用 4 个字节表示，相比于上面的编码，缺点就是更占用空间

相比之下，UTF-8 表示英文更高效 并且通用性更佳，UTF-16 表示中文等更高效（UTF-16 中文 2 字节，UTF-8 可能要三字节）

3.4.5 编程语言的字符编码

UTF-16 或 UTF-32 这类等长的编码的优点：它们可以将字符串看作数组来处理，这种做法的优点是：

• **随机访问：**因为它们不是可变长编码。因此，要找到第 $i$ 个字符，只需要计算就好了。但 UTF-8 的话，要重头开始遍历到第 $i$ 个字符，这需要 $O(n)$ 的时间

• **字符计数：**同上，计算长度只要 $O(n)$，但 UTF-8 看要遍历整个字符串

• **字符串操作：**很多字符串操作（如分割、连接、插入、删除等）都更容易进行，但 UTF-8 中要额外的计算，以保证不会产生无效的 UTF-8 编码

一些常见的编程语言的编码：

• C/C++ 没有默认编码

• Java 它的String 类型使用 UTF-16 编码。因为它在设计之初时，就认为 16 位已经够用了，因此，当超过 16 位时，会用两个（一对）16 位的值表示（简称 “代理对” ）

• JavaScript 和 TypeScript使用了 UTF-16 编码，它们与 Java 的理由类似

• C# 使用 UTF-16 编码，因为 .NET 平台是由 Microsoft 设计的，而它的很多技术，包括 Windows 系统，都广泛使用了 UTF-16 编码

由于以上编程语言对字符数量的低估，它们不得不采取“代理对”的方式来表示超过 16 位长度的 Unicode 字符。这是一个不得已为之的无奈之举。一方面，包含代理对的字符串中，一个字符可能占用 2 字节或 4 字节，从而丧失了等长编码的优势。另一方面，处理代理对需要增加额外代码，这增加了编程的复杂性和 Debug 难度。

因此，其他的语言使用了其他的方法：

• Python 中的 str 使用 Unicode 编码，但按照每个字符串的最大长度来决定使用 1 个字节，还是 2 或 4 个字节

• Go 语言的 string 类型在内部使用 UTF-8 编码。它还提供 rune 类型，用于表示单个 Unicode 码点

• Rust 语言的 str 和 String 类型（不可变和可变类型）在内部使用 UTF-8 编码，它还提供 char 类型，用于表示单个 Unicode 码点

但以上只是在编程语言中打开、运行时的存储方式，在网络传输或文件中存储时，会使用 UTF-8 编码，以节约空间、提高传输效率

四、数组与链表

数据结构的世界如同一堵厚实的砖墙。

数组的砖块整齐排列，逐个紧贴。链表的砖块分散各处，连接的藤蔓自由地穿梭于砖缝之间。

4.1 数组

「数组 array」是一种线性数据结构，它的本质是将相同类型的元素存储在连续的内存空间中。常将元素在数组中的位置称为该元素的「索引 index」

4.1.1 数组常用操作

1. 初始化数组

可以通过两种方法初始化数组

• 无初始值 （有的会默认为 0，有点会含有垃圾值）

• 给定初始值

/* 初始化数组 */// 存储在栈上int arr[5];int nums[5] = { 1, 3, 2, 5, 4 };// 存储在堆上（需要手动释放空间）int* arr1 = new int[5];int* nums1 = new int[5] { 1, 3, 2, 5, 4 };

2. 访问元素

因为数组元素是被存储在连续的内存空间中，因此只要知道数组内存地址（首元素的内存地址）和某个元素的索引，就可以使用以下的公式得到该元素的内存地址，从而直接访问此元素

数组首个元素的索引为 $0$ ，因为索引的本质是内存地址的偏移量

在数组中访问元素是非常高效的，可以在 $O(1)$ 的时间内随机访问数组中任意一个元素

/* 随机访问元素 */int randomAccess(int[] nums) {    // 在区间 [0, nums.length) 中随机抽取一个数字    int randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length);    // 获取并返回随机元素    int randomNum = nums[randomIndex];    return randomNum;}

3. 插入元素

因为数组在内存中是“紧挨着的”，因此想要在数组中插入一个元素，则需要将该元素后的索引元素向后移动一位，灾后再把元素赋值给该索引

因为数组的长度是固定的，因此若数组末尾没有提前留下额外空间，则插入一个元素，必定导致数组尾部的元素“丢失”

/* 在数组的索引 index 处插入元素 num */void insert(int *nums, int size, int num, int index) {    // 把索引 index 以及之后的所有元素向后移动一位    for (int i = size - 1; i > index; i--) {        nums[i] = nums[i - 1];    }    // 将 num 赋给 index 处元素    nums[index] = num;}

4. 删除元素

同理，要想删除索引 $i$ 处的元素，就将 $i$ 之后的元素都向前移动一位

/* 删除索引 index 处元素 */void remove(int *nums, int size, int index) {    // 把索引 index 之后的所有元素向前移动一位    for (int i = index; i < size - 1; i++) {        nums[i] = nums[i + 1];    }}

数组的插入与删除有以下缺点

• 时间复杂度高，平均都为 $O(n)$，$n$ 为数组长度

• 丢失元素，插入后丢失末尾元素

• 内存浪费，无论是初始一个长数组，只用前面，已防止丢失元素，还是删除元素后后的空余元素，都会造成内存空间的浪费

5. 遍历数组

我们可以通过索引遍历数组，也可以直接遍历获取数组中的每一个元素

/* 遍历数组 */void traverse(int *nums, int size){    int count = 0;    // 通过索引遍历数组    for (int i = 0; i < size; i++)    {        count++;    }    // 直接遍历数组    for (auto num : nums)    {        count++;    }}// 以上只是一个示例，并没有展示如何处理数组元素。// 实际情况通常会在循环中对数组元素进行读取或处理，而不仅仅是增加一个意义不明的计数器。

6. 查找元素

因为数组是线性数据结构，因此在数组中通过遍历数组来查找指定元素的方法叫 “线性查找”

/* 在数组中查找指定元素 */int find(int[] nums, int target){    for (int i = 0; i < nums.length; i++)    {        if (nums[i] == target)        {return i;}    }    return -1;}

7. 扩容数组

在大多数编程语言中，数组的长度是不可变的

想要扩容数组，就要新建一个更大的数组，然后把原数组元素依次复制到新数组中。时间复杂度为 $O(n)$

/* 扩展数组长度 */int *extend(int *nums, int size, int enlarge) {    // 初始化一个扩展长度后的数组    int *res = new int[size + enlarge];    // 将原数组中的所有元素复制到新数组    for (int i = 0; i < size; i++)    {        res[i] = nums[i];    }    // 释放内存    delete[] nums;    // 返回扩展后的新数组    return res;} 

4.1.2 数组的优缺点

因为数组的元素类型相同，且在连续的内存空间中，因此

优点：

• 空间效率高：数组是连续的内存块，无需额外的结构开销

• 支持随机访问：数组可以在 $O(1)$ 的时间内访问任何元素

• 缓存局部性（局部性原理）：因为缓存的工作方式中有一点是会将之后可能访问的附近的元素放到高速缓存中，因此在访问数组的元素时，它周围的其他数据也会被计算机缓存到高速缓存中，可以立即被访问，提升执行速度

但连续空间也是双刃剑

缺点：

• 插入删除效率低：当数组中元素较多时，插入或删除操作要移动大量的元素

• 长度不可变：扩容数组要将所有数据复制到新数组中，开销很大

• 空间浪费：若数组分配的空间超过了实际所需，那么多余的空间就被浪费了

数组要求同类型是因为可以对齐，可以通过计算偏移量来计算对应元素位置

4.1.3 数组的典型应用

其频繁的应用于各类算法，或用于实现各种复杂的数据结构

• 随机访问：如果要随机抽取一些样本，可以通过数组将这些样本存储，并生成一个随机序列，然后根据索引实现样本的随机抽取

• 排序与搜索：像是快速排序、归并排序、二分查找等都主要在数组上进行

• 查找表：当我们需要查找一个元素，或查找一个元素的对应关系时（键值对），可以使用数组的快速访问特性作为查找表。

• 机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构

• 数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

4.2 链表

因为内存空间是所有程序的公共资源，在开启了很多的程序后，空闲的内存空间可能散落在内存各处。又因为当没有足够大的连续空间用于在内存中存储数组时，链表的灵活性就体现出来了

「链表 linked list」也是一种线性数据结构，其中的每个元素都是一个节点的对象，各个节点通过 “引用（指针）” 相连接。“引用” 就是指向一个变量或对象的别名，这里是指向下一个节点的指针（内存地址）（以下都叫指针了，而不叫引用），通过它可以从当前节点访问到下一个节点

因此，它的各个节点可以被分散到内存的各处，而不用连续的内存空间


如上，链表的组成单位是「节点 node」对象。每个节点都包含两项数据：节点的 “值” 和指向下一节点的 “指针” 。

• 链表的首个节点叫 “头节点” ，最后一个节点叫 “尾节点”

• 尾节点指向的是 “空” ，它在 Java、C++、Python 中分别被标记为 $\text{null}$、$\text{nullptr}$ 和 $\text{None}$。

  C++

  TreeNode *cur = root;while (cur != nullptr)	//这就是指向空的意思{    /*我是代码*/}// 注：nullptr是C++11新增的，用于替代“NULL”，防止出现问题，当然，使用“NULL”也可以

• 除了非支持 “指针” 的语言外，都叫 “引用”

因为链表除了要包含一个值以外，还要包含一个指针，因此在相同的数据量的情况下，链表比数组会占用更多的内存空间

/* 链表节点结构体 */struct ListNode{    int val;         // 当前节点的值    ListNode *next;  // 指向下一节点的指针    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数，用于初始化节点的数值，并将下一个节点的指针初始化为空};

4.2.1 链表常用操作

1. 初始化链表

建立链表分为两步

• 初始化各个节点的对象

• 构建指针指向下一节点的关系

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */// 初始化各个节点ListNode* n0 = new ListNode(1);ListNode* n1 = new ListNode(3);ListNode* n2 = new ListNode(2);ListNode* n3 = new ListNode(5);ListNode* n4 = new ListNode(4);// 构建引用指向n0->next = n1;n1->next = n2;n2->next = n3;n3->next = n4;

数组整体是一个变量，比如数组a 包含a[0] 、a[1] 等

而链表因为是由多个独立的节点组成的，因此我们通常将头节点当作链表的代称，比如上述链表可记为 “链表n0”

2. 插入节点

如果在两个相邻的节点 n0 和 n1 中要插入一个新节点 p ，则只需要改变两个节点的指针即可，时间复杂度为 $O(1)$

相比之下，数组插入一个元素的时间复杂度为 $O(n)$ ，若数据量大则效率低


/* 在链表的节点 n0 之后插入节点 P */void insert(ListNode *n0, ListNode *P){    ListNode *n1 = n0->next;    P->next = n1;    n0->next = P;}

3. 删除节点

删除节点同理，只需要改变一个节点的指针即可

如下图，只是删除了 n0 指向 p 的指针，改成了指向 n1 的，虽然没有删除 p 指向 n1 的，但遍历此链表时，已经无法访问 p 了，因此可认为 p 已经不属于当前链表了


/* 删除链表的节点 n0 之后的首个节点 */void remove(ListNode *n0){    if (n0->next == nullptr)        return;    // n0 -> P -> n1    ListNode *P = n0->next;    ListNode *n1 = P->next;    n0->next = n1;    // 释放内存    delete P;}

有些语言上面的 p 是会自动当作垃圾回收的，但有些不会

4. 访问节点

因为在链表访问节点的效率较低，要访问第 $i$ 个节点要循环遍历前面的节点一共 $i-1$ 轮，因此时间复杂度为 $O(n)$

但数组只要 $O(1)$

/* 访问链表中索引为 index 的节点 */ListNode *access(ListNode *head, int index){    for (int i = 0; i < index; i++)    {        if (head == nullptr)        {return nullptr;}        head = head->next;    }    return head;}

5. 查找节点

也和上面一样，是线性查找，和数组的时间复杂度一样，为 $O(n)$

/* 在链表中查找值为 target 的首个节点 */int find(ListNode *head, int target){    int index = 0;    {        if (head->val == target)        {return index;}        head = head->next;        index++;    }    return -1;}

4.2.2 数组 VS 链表

添加是 $O(1)$ 但，如果先查找再添加就不是 $O(1)$ 了，是 $O(n)$

4.2.3 常见的链表类型

• **单向链表：**即上述介绍的链表，首个节点称为头节点，最后一个叫尾节点，指向空

• **环形链表：**首尾相连，任意一个节点都可以视为头节点

• **双向链表：**每个节点指向了两个前后方向的节点（前驱节点和后继节点）的指针，它相比于单向链表更灵活，但更费空间

/* 双向链表节点结构体 */struct ListNode{    int val;         // 节点值    ListNode *next;  // 指向后继节点的指针    ListNode *prev;  // 指向前驱节点的指针    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // 构造函数};

4.2.4 链表的典型应用

单向链表：

• **栈与队列：**当插入和删除在链表的同一端进行时，它表现就是先进后出的特性，对应栈；当插入与删除分别在链表的两端进行时，他表现出先进先出的特性，对应队列

• **哈希表：**使用 “链地址法” 是解决哈希冲突的主流方案之一

• 图：比如邻接表，在其中，图的每一个顶点都与一个链表相连，链表中的每个元素都代表与该顶点相连的其他顶点

**双向链表：**常用于要快速查找前后项的场景

• **高级数据结构：**比如红黑树、B 树中，可以通过在每个元素中都保存一个指向父节点的指针来实现，类似双向链表

• **浏览器历史：**当点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页，通过双向链表可以让实现变得很容易

• **LRU 算法：**即缓存淘汰算法，其需要快速找到最近最少使用的数据，以及支持快速地添加和删除节点，这时用双向链表就非常合适

**循环链表：**常用于要周期性的操作

• **时间片轮调度算法：**是一种常见的 CPU 调度算法，将每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环的操作就可以通过循环链表来实现。

• **数据缓冲区：**比如歌单循环播放

4.3 列表（动态数组）

「列表 list」是一個抽象的数据结构概念，它表示元素的有序集合，无需考虑容量限制问题。列表可以基于链表或数组实现

• 链表天然可以被看作是一个列表

• 数组因长度不可变，只能被看作是一个举要长度限制的列表

因此使用数组来实现，会因长度不可变让其的实用性降低，所以我们通常使用「动态数组 dynamic array」来实现列表

像是 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List 等的列表都是基于动态数组实现的（但不是唯一实现策略，长度大了，有一些可能使用红黑树等等来扩容），因此 “列表” 和 “动态数组” 可简单视为是同一种概念（至少在下面，列表都只动态数组）

C++中：<list>用于表示双向链表（doubly linked list）

4.3.1 列表的常用操作

1. 初始化列表

常用 “有初始值” 和 “无初始值（默认为 0）” 这两种初始化方法

/* 初始化列表 */// 需注意，C++ 中 vector 即是本文描述的 nums// 无初始值vector<int> nums1;// 有初始值vector<int> nums = { 1, 3, 2, 5, 4 };

2.访问元素

因为列表本质是数组（大多数语言中），因此可以在 $O(1)$ 时间访问和更新元素，效率很高

/* 访问元素 */int num = nums[1];  // 访问索引 1 处的元素 /* 更新元素 */nums[1] = 0;  // 将索引 1 处的元素更新为 0

3. 插入与删除元素

在列表尾部添加元素的时间复杂度为 $O(1)$ ，但插入和删除元素的效率仍然和数组相同，为 $O(n)$

但如果要先扩容再插入到尾部就不是 $O(1)$ 了，而是 $O(n)$

/* 清空列表 */nums.clear(); /* 尾部添加元素 */nums.push_back(1);nums.push_back(3);nums.push_back(2);nums.push_back(5);nums.push_back(4); /* 中间插入元素 */nums.insert(nums.begin() + 3, 6);  // 在索引 3 处插入数字 6 /* 删除元素 */nums.erase(nums.begin() + 3);      // 删除索引 3 处的元素

4. 遍历列表

与数组一样，可以用索引或直接遍历各元素

/* 通过索引遍历列表 */int count = 0;for (int i = 0; i < nums.size(); i++){    count++;} /* 直接遍历列表元素 */count = 0;for (int num : nums){    count++;}

5. 拼接列表

可以将一个列表拼接到原列表的尾部（C++是用插入的方式拼接的）

/* 拼接两个列表 */vector<int> nums1 = { 6, 8, 7, 10, 9 };// 将列表 nums1 拼接到 nums 之后nums.insert(nums.end(), nums1.begin(), nums1.end());

6. 排序列表

当排序完列表后，我们便可以使用在数组类算法题中经常考察的 “二分查找” 和 “双指针” 算法

/* 排序列表 */sort(nums.begin(), nums.end());  // 排序后，列表元素从小到大排列sort(nums.rbegin(), nums.rend());  // 排序后，列表元素从大到小排列

4.3.2 手动实现列表

非用一个编程语言自带的，而是手动实现

要设计一个简易版的列表，以下三个是重点

• 初始容量：要选取一个合理是数组初始容量，以下选取 10 作为初始容量

• 数量记录：我们声明一个变量 size ,用于记录当前列表的元素数量，并随着元素插入和删除实时更新，因此我们也可以定位列表尾部，以及判断是否需要扩容

• 扩容机制：先按照倍数（如 2 倍）创建一个更大的数组，然后在将旧数组移动到新数组中（因此可能与初始内容小于初始容量一样，导致内存空间浪费）

/* 列表类简易实现 */class MyList {  private:    int *arr;             // 数组（存储列表元素）    int arrCapacity = 10; // 列表容量    int arrSize = 0;      // 列表长度（即当前元素数量）    int extendRatio = 2;   // 每次列表扩容的倍数   public:    /* 构造方法 */    MyList() {        arr = new int[arrCapacity];    }     /* 析构方法 */    ~MyList() {        delete[] arr;    }     /* 获取列表长度（即当前元素数量）*/    int size() {        return arrSize;    }     /* 获取列表容量 */    int capacity() {        return arrCapacity;    }     /* 访问元素 */    int get(int index) {        // 索引如果越界则抛出异常，下同        if (index < 0 || index >= size())            throw out_of_range("索引越界");        return arr[index];    }     /* 更新元素 */    void set(int index, int num) {        if (index < 0 || index >= size())            throw out_of_range("索引越界");        arr[index] = num;    }     /* 尾部添加元素 */    void add(int num) {        // 元素数量超出容量时，触发扩容机制        if (size() == capacity())            extendCapacity();        arr[size()] = num;        // 更新元素数量        arrSize++;    }     /* 中间插入元素 */    void insert(int index, int num) {        if (index < 0 || index >= size())            throw out_of_range("索引越界");        // 元素数量超出容量时，触发扩容机制        if (size() == capacity())            extendCapacity();        // 将索引 index 以及之后的元素都向后移动一位        for (int j = size() - 1; j >= index; j--) {            arr[j + 1] = arr[j];        }        arr[index] = num;        // 更新元素数量        arrSize++;    }     /* 删除元素 */    int remove(int index) {        if (index < 0 || index >= size())            throw out_of_range("索引越界");        int num = arr[index];        // 索引 i 之后的元素都向前移动一位        for (int j = index; j < size() - 1; j++) {            arr[j] = arr[j + 1];        }        // 更新元素数量        arrSize--;        // 返回被删除元素        return num;    }     /* 列表扩容 */    void extendCapacity() {        // 新建一个长度为原数组 extendRatio 倍的新数组        int newCapacity = capacity() * extendRatio;        int *tmp = arr;        arr = new int[newCapacity];        // 将原数组中的所有元素复制到新数组        for (int i = 0; i < size(); i++) {            arr[i] = tmp[i];        }        // 释放内存        delete[] tmp;        arrCapacity = newCapacity;    }     /* 将列表转换为 Vector 用于打印 */    vector<int> toVector() {        // 仅转换有效长度范围内的列表元素        vector<int> vec(size());        for (int i = 0; i < size(); i++) {            vec[i] = arr[i];        }        return vec;    }}; 

4.4 内存与缓存

数组与链表这两种基础且重要的数据结构，它们分别代表了“连续存储” 和“分散存储”两种物理结构

实际上，物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。

4.4.1 计算机存储设备

计算机中包括三种类型的存储设备：「硬盘 hard disk」、「内存 random-access memory, RAM」、「缓存 cache memory」。表 4-2 展示了它们在计算机系统中的不同角色和性能特点。

我们可以将计算机存储系统想象为下图所示的金字塔结构。越靠近金字塔顶端的存储设备的速度越快、容量越小、成本越高。这种多层级的设计并非偶然，而是计算机科学家和工程师们经过深思熟虑的结果。

• 硬盘难以被内存取代。首先，内存中的数据在断电后会丢失，因此它不适合长期存储数据；其次，内存的成本是硬盘的几十倍，这使得它难以在消费者市场普及。

• 缓存的大容量和高速度难以兼得。随着 L1、L2、L3 缓存的容量逐步增大，其物理尺寸会变大，与 CPU 核心之间的物理距离会变远，从而导致数据传输时间增加，元素访问延迟变高。在当前技术下，多层级的缓存结构是容量、速度和成本之间的最佳平衡点。

计算机的存储层次结构体现了速度、容量和成本三者之间的精妙平衡。实际上，这种权衡普遍存在于所有工业领域（所有工程问题），它要求我们在不同的优势和限制之间找到最佳平衡点。

总的来说，硬盘用于长期存储大量数据，内存用于临时存储程序运行中正在处理的数据，而缓存则用于存储经常访问的数据和指令，以提高程序运行效率。三者共同协作，确保计算机系统高效运行。

如下图所示，在程序运行时，数据会从硬盘中被读取到内存中，供 CPU 计算使用。缓存可以看作 CPU 的一部分，它通过智能地从内存加载数据，给 CPU 提供高速的数据读取，从而显著提升程序的执行效率，减少对较慢的内存的依赖。


4.4.2 数据结构的内存效率

在内存空间利用方面，数组和链表各自具有优势和局限性。

一方面，内存是有限的，且同一块内存不能被多个程序共享，因此我们希望数据结构能够尽可能高效地利用空间。数组的元素紧密排列，不需要额外的空间来存储链表节点间的引用（指针），因此空间效率更高。然而，数组需要一次性分配足够的连续内存空间，这可能导致内存浪费，数组扩容也需要额外的时间和空间成本。相比之下，链表以“节点”为单位进行动态内存分配和回收，提供了更大的灵活性。

另一方面，在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。数组由于其连续的存储方式，相对不容易导致内存碎片化。相反，链表的元素是分散存储的，在频繁的插入与删除操作中，更容易导致内存碎片化。

所以说在物理上，内存中通常是使用数组的形式存储的。如果是动态内存等的话就是链表了（链表中也可以包含数组呀，当然，反过来也是可以的（哈希表））

4.4.3 数据结构的缓存效率

缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生「缓存未命中 cache miss」，此时 CPU 不得不从速度较慢的内存中加载所需数据。

显然，“缓存未命中”越少，CPU 读写数据的效率就越高，程序性能也就越好。我们将 CPU 从缓存中成功获取数据的比例称为「缓存命中率 cache hit rate」，这个指标通常用来衡量缓存效率。

为了尽可能达到更高的效率，缓存会采取以下数据加载机制。

• 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。

• 预取机制：处理器会尝试预测数据访问模式（例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。

• 空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。

• 时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。

实际上，数组和链表对缓存的利用效率是不同的，主要体现在以下几个方面。

• 占用空间：链表元素比数组元素占用空间更多，导致缓存中容纳的有效数据量更少。

• 缓存行：链表数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。

• 预取机制：数组比链表的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。

• 空间局部性：数组被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。

总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。这使得在解决算法问题时，基于数组实现的数据结构往往更受欢迎。

需要注意的是，高缓存效率并不意味着数组在所有情况下都优于链表。实际应用中选择哪种数据结构，应根据具体需求来决定。例如，数组和链表都可以实现“栈”数据结构，但它们适用于不同场景。

• 在做算法题时，我们会倾向于选择基于数组实现的栈，因为它提供了更高的操作效率和随机访问的能力，代价仅是需要预先为数组分配一定的内存空间。

• 如果数据量非常大、动态性很高、栈的预期大小难以估计，那么基于链表实现的栈更加合适。链表能够将大量数据分散存储于内存的不同部分，并且避免了数组扩容产生的额外开销。

4.5 其他

数组存储在栈上和存储在堆上，对时间效率和空间效率是否有影响？

存储在栈上和堆上的数组都被存储在连续内存空间内，数据操作效率是基本一致的。然而，栈和堆具有各自的特点，从而导致以下不同点。

1. 分配和释放效率：栈是一块较小的内存，分配由编译器自动完成；而堆内存相对更大，可以在代码中动态分配，更容易碎片化。因此，堆上的分配和释放操作通常比栈上的慢。
2. 大小限制：栈内存相对较小，堆的大小一般受限于可用内存。因此堆更加适合存储大型数组。
3. 灵活性：栈上的数组的大小需要在编译时确定，而堆上的数组的大小可以在运行时动态确定。

C++ STL 里面的 std::list 已经实现了双向链表，但好像一些算法的书上都不怎么直接用这个，是不是有什么局限性呢?

一方面，我们往往更青睐使用数组实现算法，而只有在必要时才使用链表，主要有两个原因。

• 空间开销：由于每个元素需要两个额外的指针（一个用于前一个元素，一个用于后一个元素），所以 std::list 通常比 std::vector 更占用空间。

• 缓存不友好：由于数据不是连续存放的，std::list 对缓存的利用率较低。一般情况下，std::vector 的性能会更好。

另一方面，必要使用链表的情况主要是二叉树和图。栈和队列往往会使用编程语言提供的 stack 和 queue ，而非链表。

在 Python 中初始化 n = [1, 2, 3] 后，这 3 个元素的地址是相连的，但是初始化 m = [2, 1, 3] 会发现它们每个元素的 id 并不是连续的，而是分别跟 n 中的相同。这些元素地址不连续，那么 m 还是数组吗？

假如把列表元素换成链表节点 n = [n1, n2, n3, n4, n5] ，通常情况下这五个节点对象也是被分散存储在内存各处的。然而，给定一个列表索引，我们仍然可以在 �(1) 时间内获取到节点内存地址，从而访问到对应的节点。这是因为数组中存储的是节点的引用，而非节点本身。

与许多语言不同的是，在 Python 中数字也被包装为对象，列表中存储的不是数字本身，而是对数字的引用。因此，我们会发现两个数组中的相同数字拥有同一个 id ，并且这些数字的内存地址是无须连续的。

在删除节点中，需要断开该节点与其后继节点之间的引用指向吗？

从数据结构与算法（做题）的角度看，不断开没有关系，只要保证程序的逻辑是正确的就行。从标准库的角度看，断开更加安全、逻辑更加清晰。如果不断开，假设被删除节点未被正常回收，那么它也会影响后继节点的内存回收。

五、栈与队列

栈如同叠猫猫，而队列就像猫猫排队

两者分别代表着先入后出和先入先出的逻辑关系

5.1 栈

「栈 stack」是一种遵循先入后出的逻辑的线性数据结构

如下图，是一些栈的规则、名词


5.1.1 栈的常用操作

如下所示，具体的名称还要根据所使用的编程语言决定

如果编程语言内置了栈，则可以直接使用，但如果没有（如Python），则可以将数组或链表当作栈来使用，并再程序逻辑上忽略与栈无关的操作