数据结构是存储和组织数据的方式，通过提高存取效率、节省内存和支持复杂操作来提高算法性能和程序性能。 常见的数据结构包括数组、链表、栈、队列、哈希表、二叉树等。

• 操作速度按步数计算，即时间复杂度（衡量操作步数随输入规模的变化）。核心操作：读取、查找、插入、删除。

• 算法运行时所需的额外内存，即空间复杂度（衡量所需的额外内存空间随输入规模变化）。

大 O 记法

• 大 O 默认 最坏情况。

• 平均情况：更贴近实际。
  • 插入排序：适合基本有序的数据。
  • 选择排序：适合逆序数据。
• 有序数组：插入需要查找位置；查找可更快。
• 二分查找 vs 线性查找
  • 100 个元素：线性查找需 100 步，二分查找需 7 步。
• 规律：数组长度 ×2，二分查找最多步数 +1。

各数据结构对比

散列表（哈希表）

• 核心思想：键 → 散列函数 → 索引格子。
• 插入、查找、删除：平均 O(1)。
• 冲突处理：分离链接（链表）等。
• 负载因子 ≈ 0.7 最佳。
• 缺点：不保持顺序。

栈与队列

• 栈 (Stack)：LIFO（后进先出）。操作限制在栈顶。
• 队列 (Queue)：FIFO（先进先出）。插入在尾，删除在头。
• 应用：函数调用栈、任务调度。

递归与快速排序

• 递归：用调用栈实现，必须有基准情形。
• 快速排序：分区 → 递归子数组 → O(N log N) 平均效率。

链表

• 单链表：结点 = 数据 + 指针。
  • 插入表头：O(1)。
  • 查找/遍历：O(N)。
• 双向链表：结点有前后指针。
  • 队列实现可做到插入、删除都是 O(1)。

二叉树

• 二叉搜索树 (BST)：
  • 左子树 < 根 < 右子树。
  • 查找、插入、删除：平均 O(log N)。
• 缺点：若输入有序 → 树退化为链表 → O(N)。
• 删除规则：无子结点 / 单子结点 / 两子结点（用后继替代）。

图

• 图：处理关系型数据。
• 遍历方式：
  • BFS（广度优先搜索，用队列）。
  • DFS（深度优先搜索，用栈或递归）。
• 加权图：边带有权重。

C版实现

数组

#include <stdio.h>

int main() 
{
    // 初始化数组和元素个数
    int arr[100] = {10, 20, 30, 40, 50}; // 数组初始值
    int n = 5; // 当前数组元素个数
    int i;

    // 1️⃣ 读取（遍历数组）
    printf("数组元素：");
    for (i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]); // 依次打印每个元素
    }
    printf("\n");

    // 2️⃣ 查找（找到元素的位置）
    int target = 30; // 要查找的元素
    int pos = -1;    // 用于记录找到的位置，-1表示未找到
    for (i = 0; i < n; i++) 
    {
        if (arr[i] == target) 
        { // 如果当前元素等于目标
            pos = i;            // 记录位置
            break;              // 找到后退出循环
        }
    }
    if (pos != -1)
        printf("元素 %d 在位置 %d\n", target, pos);
    else
        printf("未找到元素 %d\n", target);

    // 3️⃣ 插入（在位置 2 插入 25）
    int insertPos = 2; // 插入位置
    int value = 25;    // 要插入的值
    // 将插入位置及之后的元素右移一位
    for (i = n; i > insertPos; i--) 
    {
        arr[i] = arr[i - 1];
    }
    arr[insertPos] = value; // 插入新元素
    n++; // 元素数量增加
    printf("插入后数组：");
    for (i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    // 4️⃣ 删除（删除位置 3 的元素）
    int deletePos = 3; // 要删除的元素位置
    // 将删除位置之后的元素左移一位覆盖
    for (i = deletePos; i < n - 1; i++) 
    {
        arr[i] = arr[i + 1];
    }
    n--; // 元素数量减少
    printf("删除后数组：");
    for (i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
};

================================================================

《数据结构与算法图解 (杰伊•温格罗, 袁志鹏译) (Z-Library).pdf》

第1章　数据结构为何重要

◆ 本章接下来将会分析两种数据结构：数组和集合

◆ 一般数据结构都有以下 4 种操作（或者说用法）​。 读取：查看数据结构中某一位置上的数据。对于数组来说，这意味着查看某个索引所指的数据值。例如，查看索引 2 上有什么食品，就是一种读取。 查找：从数据结构中找出某个数据值的所在。对于数组来说，这意味着检查其是否包含某个值，如果包含，那么还得给出其索引。例如，检查”dates”是否存在于食品清单之中，给出其对应的索引，就是一种查找。 插入：给数据结构增加一个数据值。对于数组来说，这意味着多加一个格子并填入一个值。例如，往购物清单中多加一项”figs”，就是一种插入。 删除：从数据结构中移走一个数据值。对于数组来说，这意味着把数组中的某个数据项移走。例如，把购物清单中的”bananas”移走，就是一种删除。

◆ 本书的第一个重要理论：操作的速度，并不按时间计算，而是按步数计算。

1.1.1　读取

◆ 因此，衡量步数是分析速度的关键。 此外，操作的速度，也常被称为时间复杂度。在本书中，我们会提到速度、时间复杂度、效率、性能，但它们其实指的都是步数。

◆ 首先看看读取，即查看数组中某个索引所指的数据值。这只要一步就够了，因为计算机本身就有跳到任一索引位置的能力

1.1.2　查找

◆ 计算机之所以在读取数组中某个索引所指的值时，能直接跳到那个位置上，是因为它具备以下条件。(1) 计算机可以一步就跳到任意一个内存地址上。​（就好比，要是你知道大街 123 号在哪儿，那么就可以直奔过去。​）(2) 数组本身会记有第一个格子的内存地址，因此，计算机知道这个数组的开头在哪里。(3) 数组的索引从 0 算起。

◆ 这种逐个格子去检查的做法，就是最基本的查找方法—线性查找。

1.1.4　删除

◆ 一个含有 N 个元素的数组，其插入数据的最坏情况会花费 N + 1 步。即插入在数组开头，导致 N 次移动，加上一次插入。

◆ 可以推出，对于含有 N个元素的数组，删除操作最多需要 N 步。

1.2　集合：一条规则决定性能

◆ 集合。它是一种不允许元素重复的数据结构。

1.3　总结

◆ 在 N 个元素的集合中进行插入的最好情况需要 N + 1 步—N 步去确认被插入的值不在集合中，加上最后插入的 1 步。

◆ 最坏的情况则是在集合的开头插入，这时计算机得检查 N 个格子以保证集合不包含那个值，然后用 N 步来把所有值右移，最后再用 1步来插入新值。总共 2N + 1 步。

第2章　算法为何重要

◆ 在计算机的世界里，算法则是指某项操作的过程。上一章我们研究了 4 种主要操作，包括读取、查找、插入和删除。这一章我们还是会经常提到它们，而且一种操作可能会有不止一种做法。也就是说，一种操作会有多种算法的实现。

◆ 有序数组跟上一章讨论的数组几乎一样，唯一区别就是有序数组要求其值总是保持有序（你猜对了）。即每次插入新值时，它会被插入到适当的位置，使整个数组的值仍然按顺序排列。常规的数组则并不考虑是否有序，直接把值加到末尾也没问题。

2.2　查找有序数组

◆ 可以看到，往有序数组中插入新值，需要先做一次查找以确定插入的位置。这是它跟常规数组的关键区别（在性能方面）之一。 虽然插入的性能比不上常规数组，但在查找方面，有序数组却有着特殊优势。

2.4　二分查找与线性查找

◆ 对于长度太小的有序数组，二分查找并不比线性查找好多少。但我们来看看更大的数组。

◆ 2025/04/30发表想法

2^7=128>100

原文：对于拥有 100 个值的数组来说，两种查找需要的最多步数如下所示。
线性查找：100 步
二分查找：7 步

◆ 对于拥有 100 个值的数组来说，两种查找需要的最多步数如下所示。 线性查找：100 步 二分查找：7 步

2.5　总结

◆ 规律就是，每次有序数组长度乘以 2，二分查找所需的最多步数只会加 1。

◆ 如之前所述，比较算法的方式就是比较各自的步数。

第3章　大O记法

◆ 量化线性查找效率的更准确的方式应该是：对于具有 N 个元素的数组，线性查找最多需要 N步

3.2　常数时间与线性时间

◆ 大 O 解答的是这样的问题：当数据增长时，步数如何变化？

◆ 从图中可以看出，O(N)呈现为一条对角线。当数据增加一个单位时，算法也随之增加一步。也就是说，数据越多，算法所需的步数就越多。O(N)也被称为线性时间。 相比之下，O(1)则为一条水平线，因为不管数据量是多少，算法的步数都恒定。所以，O(1)也被称为常数时间。

◆ 因为大 O 主要关注的是数据量变动时算法的性能变化

◆ 简单来说，O(1)就是用来表示所有数据增长但步数不变的算法。

3.3　同一算法，不同场景

◆ 但若无特别说明，大 O 记法一般都是指最坏情况。

3.5　对数

◆ O(log N) 我将其读作“O log N”。归于此类的算法，它们的时间复杂度都叫作对数时间。

◆ 简单来说，O(log N)意味着该算法当数据量翻倍时，步数加 1。

3.6　解释O(log N)

◆ 现在回到大 O 记法。当我们说 O(log N)时，其实指的是 O(log2 N)，不过为了方便就省略了 2而已。

第4章　运用大O来给代码提速

◆ 排序算法是计算机科学中被广泛研究的一个课题。历时多年，它发展出了数十种算法，这些算法都着眼于一个问题：如何将一个无序的数字数组整理成升序？

4.5　二次问题

◆ O(N 2)也被叫作二次时间。

◆ 大 O 测量的是步数与数据量的关系。

◆ 毫无疑问，嵌套循环算法的效率就是 O(N2)。一旦看到嵌套循环，你就应该马上想到 O(N 2)。

5.5　忽略常数

◆ 还记得我们说过，大 O 记法用来表示步数与数据量的关系。所以你可能会以为步数约为 N 2 [插图]但事实上，选择排序的大 O 记法为 O(N2)，跟冒泡排序一样。这是因为大 O 记法的一条重要规则我们至今还没提到： 大 O 记法忽略常数。

5.7　一个实例

◆ 这就是大 O 记法忽略常数的原因。大 O 记法只表明，对于不同分类，存在一临界点，在这一点之后，一类算法会快于另一类，并永远保持下去。至于这个点在哪里，大 O 并不关心。 因此，不需要写成 O(100N)，归类到 O(N)就好了。

◆ 因此，大 O 记法非常适合用于不同大 O 分类下的算法的对比，对于大 O 同类的算法，我们还需要进一步的解析才能分辨出具体差异。

5.8　总结

◆ 不过在对比算法时，还需要考虑一个重要因素。至今我们关注的都是最坏情况下算法会跑得多慢，但其实最坏情况并不总会发生。没错，我们遇到的大都是平均情况。下一章，我们会学习怎样顾及所有情况。

第6章　乐观地调优

◆ 顾及最坏情况以外的场景将是多么有用。

6.4　插入排序的效率

◆ 插入排序包含 4 种步骤：移除、比较、平移和插入。

◆ 对于有 N 个元素的数组，大约需要 N2/ 2 次比较（102/ 2 是 50，202/ 2是 200）。

◆ 大 O 的另一条重要规则： 大 O 只保留最高阶的 N。

6.5　平均情况

◆ 确实，在最坏情况里，选择排序比插入排序快。但是我们还应该考虑平均情况。

◆ 最坏情况是所有数据都要比较和平移；最好情况是每轮一次比较、零次平移；对于平均情况，总的来看，是比较和平移一半的数据。

◆ 选择排序是无论何种情况，最坏、平均、最好，都要 N2 / 2 步。 因为这个算法没有提早结束某一轮的机制，不管遇到什么，每一轮都得比较所选索引右边的所有值。

◆ 那么哪种算法更好？选择排序还是插入排序？答案是：看情况。对于平均情况（数组里的值随机分布），它们性能相近。如果你确信数组是大致有序的，那么插入排序比较好。如果是大致逆序，则选择排序更快。如果你无法确定数据是什么样，那就算是平均情况了，两种都可以。

6.7　总结

◆ break 可以中断内部循环，节省步数和时间。

◆ 一种跟数组类似的数据结构，它的一些特点使其在某些场景中的性能优于数组。

第7章　查找迅速的散列表

◆ 查找迅速的散列表

◆ 大多数编程语言都自带散列表这种能够快速读取的数据结构。但在不同的语言中，它有不同的名字，除了散列表，还有散列、映射、散列映射、字典、关联数组。

◆ 散列表由一对对的数据组成。一对数据里，一个叫作键，另一个叫作值。键和值应该具有某种意义上的关系。

7.2　用散列函数来做散列

◆ 将字符串转为数字串的过程就是散列，其中用于对照的密码，就是散列函数。

◆ 当然散列函数不只是这一种，例如对各字母匹配的数字求和的过程，也可以作为散列函数。

◆ 散列函数也可以是对各字母匹配的数字求积的过程。这样的话，BAD 就会得出 8。

◆ 本章剩余部分将会采用最后一种散列函数。虽然现实世界中的散列函数比这复杂得多，但以简单的乘法函数为例会比较易懂。

◆ 一个散列函数需满足以下条件才有效：每次对同一字符串调用该散列函数，返回的都应是同一数字串。如果每次都返回不一样的结果，那就无效。

7.4　处理冲突

◆ 这下你应该明白为什么从散列表里读取数据只需要 O(1)了吧，因为其过程所花的时间是恒定的。它总是先计算出键的散列值，然后根据散列值跳到对应的格子去。

◆ 不过，散列表也会带来一些麻烦。

◆ 往已被占用的格子里放东西，会造成冲突。幸好，我们有解决办法。 一种经典的做法就是分离链接。当冲突发生时，我们不是将值放到格子里，而是放到该格子所关联的数组里。

◆ 该数组又以子数组构成，每个子数组含两个元素，第一个是被检索的词，后一个是其相应的同义词。

◆ 线性地

7.5　找到平衡

◆ 如果数据都刚好存在同一个格子里，那么查找就相当于在数组上进行。因此散列表的最坏情况就是 O(N)。

◆ 归根到底，散列表的效率取决于以下因素。  要存多少数据。  有多少可用的格子。  用什么样的散列函数。

7.6　一个实例

◆ 所以，一个好的散列函数，应当能将数据分散到所有可用的格子里去。

◆ 使用散列表时所需要权衡的：既要避免冲突，又要节约空间。 要想解决这个问题，可参考计算机科学家研究出的黄金法则：每增加 7 个元素，就增加 10个格子。 如果要保存 14 个元素，那就得准备 20 个格子，以此类推。 数据量与格子数的比值称为负载因子。把这个术语代入刚才的理论，就是：理想的负载因子是 0.7（7 个元素 / 10 个格子）。

◆ 很多时候，我们都可以把散列表当成集合来用。 把数组作为集合的话，数据是直接放到格子里的。用散列表时，则是将数据作为键，值可以为任何形式，例如数字 1，或者布尔值 true 也行。

◆ 这样每次插入新值，都只需花 O(1)的时间，而不是线性查找的 O(N)。即使数据已存在时也是这个速度。 set[“banana”] = 1; 再次插入”banana”时，我们并不需要检查它存在与否，因为即使存在，也只是将其对应的值重写成 1。

◆ 散列表确实非常适用于检查数据的存在性。

7.7　总结

◆ 因为其 O(1)的读取和插入带来了无与伦比的性能优势。

◆ 下一章就研究两种能帮助改善代码可读性和可维护性的数据结构

第8章　用栈和队列来构造灵巧的代码

◆ 本章你将会学习两种新的数据结构：栈和队列。事实上它们并不是全新的东西，只不过是多加了一些约束条件的数组而已

◆ 具体一点说，栈和队列都是处理临时数据的灵活工具。在操作系统、打印任务、数据遍历等各种需要临时容器才能构造出美妙算法的场景，它们都大有作为。

◆ 栈存储数据的方式跟数组一样，都是将元素排成一行。只不过它还有以下 3 条约束。 只能在末尾插入数据。 只能读取末尾的数据。 只能移除末尾的数据。

◆ 绝大部分计算机科学家都把栈的末尾称为栈顶，把栈的开头称为栈底。

8.2　栈实战

◆ 压栈和出栈可被形容为 LIFO（last in，first out）后进先出。解释起来就是最后入栈的元素，会最先出栈。

8.3　队列

◆ 我们会类似地用栈去跟踪函数的调用，那也是递归的核心思想。

◆ 套用到队列上，就是首先加入队列的，将会首先从队列移出。因此计算机科学家都用缩写“FIFO”（first in, first out）先进先出，来形容它。

◆ 与栈类似，队列也有 3 个限制（但内容不同）。  只能在末尾插入数据（这跟栈一样）。  只能读取开头的数据（这跟栈相反）。  只能移除开头的数据（这也跟栈相反）。

9.3　阅读递归代码

◆ (1) 找出基准情形。 (2) 看该函数在基准情形下会做什么。 (3) 看该函数在到达基准情形的前一步会做什么。 (4) 就这样往前推，看每一步都在做什么。

9.4　计算机眼中的递归

◆ 计算机是用栈来记录每个调用中的函数。这个栈就叫作调用栈。

9.5　递归实战

◆ 有趣的是，无限递归（如本章开头的例子）的程序会一直将同一方法加到调用栈上，直到计算机的内存空间不足，最终导致栈溢出的错误。

◆ 此脚本遍历给定目录下的所有文件

◆ 打印了当前目录的直属子目录的名字

9.6　总结

◆ 正如文件系统的例子所示，递归十分适用于那些无法预估计算深度的问题。

第10章　飞快的递归算法

◆ 快速排序依赖于一个名为分区的概念

10.2　快速排序

◆ 快速排序严重依赖于分区

◆ (1) 把数组分区。使轴到正确的位置上去。(2) 对轴左右的两个子数组递归地重复第 1、2 步，也就是说，两个子数组都各自分区，并形成各自的轴以及由轴分隔的更小的子数组。然后也对这些子数组分区，以此类推。(3) 当分出的子数组长度为 0 或 1 时，即达到基准情形，无须进一步操作。

10.6　总结

◆ 其实能递归的不只有算法，还有数据结构。后面几章将要接触的链表、二叉树以及图，就利用了自身递归的特性，给我们提供了迅速的数据操作方式。

11.2　实现一个链表

◆ 与数组不同的是，组成链表的格子不是连续的。它们可以分布在内存的各个地方。这种不相邻的格子，就叫作结点。

◆ 这就是链表的关键了：每个结点除了保存数据，它还保存着链表里的下一结点的内存地址。

◆ 因为每个结点都需要 2 个格子，头一格用作数据存储，后一格用作指向下一结点的链（最后一个结点的链是 null，因为它是终点）​，所

11.3　读取

◆ 既然知道了链表是什么，那么接下来做个它跟数组的性能对比，观察它们在读取、查找、插入和删除上有何优劣。

11.4　查找

◆ 所谓查找就是从列表中找出某个特定值所在的索引

11.5　插入

◆ 在某些情况下，链表的插入跟数组相比，有着明显的优势。回想插入数组的最坏情况：当插入位置为索引 0 时，因为需要先将插入位置右侧的数据都右移一格，所以会导致 O(N)的时间复杂度。然而，若是往链表的表头进行插入，则只需一步，即 O(1)。

◆ 链表的插入效率为 O(N)，与数组一样。

11.6　删除

◆ 删除链表的最后一个结点，其实际的删除动作只需 1 步—令倒数第二的结点的链指向 null。然而，要找出倒数第二的结点，得花 N 步，因为我们依然只能从第一个结点顺着链往下一个个地找。

11.7　链表实战

◆ 高效地遍历单个列表并删除其中多个元素，是链表的亮点之一。

11.8　双向链表

◆ 链表的另一个引人注目的应用，就是作为队列的底层数据结构。

◆ 那么用链表来代替数组有什么好处呢？

◆ 再强调一次，队列插入数据只能在末尾。如上文所述，在数组的末尾插入是极快的，时间复杂度为O(1)。链表则要 O(N)。所以在插入方面，选择数组比链表更好。

◆ 但到了删除的话，就是链表更快了，因为它只要 O(1)，而数组是 O(N)。基于以上分析，似乎用数组还是链表都无所谓。因为它们总有一种操作是 O(1)，另一种是 O(N)：数组的插入是 O(1)，删除是 O(N)；链表则反过来，分别是 O(N)和 O(1)。然而，要是采用双向链表这一链表的变种，就能使队列的插入和删除都为 O(1)。双向链表跟链表差不多，只是它每个结点都含有两个链—一个指向下一结点，另一个指向前一结点。此外，它还能直接访问第一个和最后一个结点。

第12章　让一切操作都更快的二叉树

◆ 有序数组存在着另一个问题。

◆ 有序数组的插入和删除是缓慢的。

◆ 散列表能以 O(1)的效率进行查找、插入和删除，但它又有另一明显的不足：不保持顺序。

◆ 既要保持顺序，又要快速查找、插入和删除，看来有序数组和散列表都不行。那还有什么数据结构可以选择？看看二叉树吧。

◆ 树也是基于结点的数据结构，但树里面的每个结点，可以含有多个链分别指向其他多个结点。

◆ 最上面的那一结点（此例中的“j”​）被称为根。是的，图中的根位于树的顶端

◆ 二叉树是一种遵守以下规则的树。 每个结点的子结点数量可为 0、1、2。 如果有两个子结点，则其中一个子结点的值必须小于父结点，另一个子结点的值必须大于父结点。

12.2　查找

◆ 因为二叉树具有这样独特的结构，所以我们能在其中非常快速地进行查找操作

◆ 二叉树的查找算法先从根结点开始。(1) 检视该结点的值。(2) 如果正是所要找的值，太好了！(3) 如果要找的值小于当前结点的值，则在该结点的左子树查找。(4) 如果要找的值大于当前结点的值，则在该结点的右子树查找。

◆ 二叉树查找的时间复杂度是 O(log N)

◆ 因为每行进一步，我们就把剩余的结点排除了一半（不过很快就能看到，只在最好情况下，即理想的平衡二叉树才有这样的效率）​。

◆ 再与二分查找比较，它也是每次尝试会排除一半可能性的 O(log N)算法，可见二叉树查找跟有序数组的二分查找拥有同样的效率。要说二叉树哪里比有序数组更亮眼，那应该是插入操作。

12.3　插入

◆ 插入这 1 步总是发生在查找之后，所以总共 log N + 1 步。按照忽略常数的大 O 来说，就是 O(log N)步。

◆ 有序数组的插入则是 O(N)，因为该过程中除了查找，还得移动大量的元素来给新元素腾出空间。

◆ 这就是二叉树的高效之处。有序数组查找需要 O(log N)，插入需要 O(N)，而二叉树都是只要 O(log N)。当你估计应用会发生许多数据改动时，这一比较将有助你做出正确选择。

◆ 注意，只有用随意打乱的数据创建出来的树才有可能是比较平衡的。要是插入的都是已排序的数据，那么这棵树就失衡了，它用起来也会比较低效。

12.4　删除

◆ 至此，删除操作遵循以下规则。 如果要删除的结点没有子结点，那直接删掉它就好。 如果要删除的结点有一个子结点，那删掉它之后，还要将子结点填到被删除结点的位置上。

◆ 如果要删除的结点有两个子结点，则将该结点替换成其后继结点。一个结点的后继结点，就是所有比被删除结点大的子结点中，最小的那个。

◆ 以下为二叉树的删除算法的所有规则。 如果要删除的结点没有子结点，那直接删掉它就好。 如果要删除的结点有一个子结点，那删掉它之后，还要将子结点填到被删除结点的位置上。 如果要删除的结点有两个子结点，则将该结点替换成其后继结点。一个结点的后继结点，就是所有比被删除结点大的子结点中，最小的那个。 如果后继结点带有右子结点，则在后继结点填补被删除结点以后，用此右子结点替代后继结点的父节点的左子结点。

◆ 跟查找和插入一样，平均情况下二叉树的删除效率也是 O(log N)。因为删除包括一次查找，以及少量额外的步骤去处理悬空的子结点。有序数组的删除则由于需要左移元素去填补被删除元素产生的空隙，最终导致 O(N)的时间复杂度。

12.5　二叉树实战

◆ 二叉树在查找、插入和删除上引以为傲的 O(log N)效率，使其成为了存储和修改有序数据的一大利器。它尤其适用于需要经常改动的数据，虽然在查找上它跟有序数组不相伯仲，但在插入和删除方面，它迅速得多。

◆ 访问数据结构中所有元素的过程，叫作遍历数据结构。

12.6　总结

◆ 二叉树是一种强大的基于结点的数据结构，它既能维持元素的顺序，又能快速地查找、插入和删除。尽管比它的近亲链表更为复杂，但它更有用。值得一提的是，树形的数据结构除了二叉树以外还有很多种，包括堆、B 树、红黑树、2-3-4树等。它们也各有自己适用的场景。

◆ 图是社交网络和地图软件等复杂应用的核心组成部分，强大且灵活。

第13章　连接万物的图

◆ 图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的。

13.2　广度优先搜索

◆ 广度优先搜索

◆ 图有两种经典的遍历方式：广度优先搜索和深度优先搜索。

◆ 广度优先搜索算法需要用队列（参见第 8 章）来记录后续要处理哪些顶点。该队列最初只含有起步的顶点（对本例来说，就是 Alice）​。于

◆ 将算法的步骤分为两类之后，我们可以看出图的广度优先搜索的效率。 让顶点出队，将其设为当前顶点。 访问每个顶点的邻接点。

13.4　加权图

◆ 还有一种图叫作加权图

◆ 它跟普通的图类似，但边上带有信息。

13.6　总结

◆ 我们知道了图是处理关系型数据的强大工具，它除了能让代码跑得更快，还能帮忙解决一些复杂的问题。学习至今，我们关注的主要是代码运行的速度。我们以时间和算法的步数来衡量代码的性能。然而，性能的衡量方法不止这些。在某些情况下，还有比速度更重要的东西，比如我们可能更关心一种数据结构或算法会消耗多少内存。下一章，我们就来学习如何分析一段代码在空间上的效率。

第14章　对付空间限制

◆ 在分析各种算法的效率时，我们只关注了它们的时间复杂度。换句话说，就是它们运行得有多快。但有些时候，我们还得以另一种名为空间复杂度的度量方式，去估计它们会消耗多少内存

◆ 当内存有限时，空间复杂度便会成为选择算法的一个重要的参考因素。

◆ 还是用描述时间复杂度的大 O 记法来描述空间复杂度。

◆ 至今我们一直这样用大 O 记法来描述一个算法的速度：当所处理的数据有 N 个元素时，该算法所需的步数相对于元素数量是多少。例如，O(N)算法就是处理 N 个元素需要 N 步的算法。 O(N 2)算法就是处理 N 个元素需要 N2步的算法。类似地，我们也可以用大 O 来描述一个算法需要多少空间：当所处理的数据有 N 个元素时，该算法还需额外消耗多少元素大小的内存空间。

◆ 记住，时间复杂度的O(1)意味着一个算法无论处理多少数据，其速度恒定。相似地，空间复杂度的 O(1)则意味着一个算法无论处理多少数据，其消耗的内存恒定。

◆ 空间复杂度是根据额外需要的内存空间（也叫辅助空间）来算的，也就是说原本的数据不纳入计算。

– 来自微信读书