本支持页面包含《动画算法与数据结构》一书中创建的符号、动画和伪代码。有关详细解释，请参阅《动画算法与数据结构》书籍内容。

第1部分 准备篇

第3章 算法设计的准备

常数 常数
对数 对数
线性 线性
线性、对数 线性、对数
二次函数 二次函数
三次函数 三次函数

第2部分 空间结构

第4～9章

单节点 单节点
一维数组 一维数组
二维数组 二维数组
二叉树 二叉树
完全二叉树 完全二叉树
满二叉树 满二叉树
无向图 无向图
有向图 有向图
森林 森林
二维点群 二维点群
链表 链表
动态二叉树 动态二叉树

第3部分 算法和数据结构

第10章 入门

2023/12/01
交换
交换
请交换两个不同变量的值。
交换 | 输入 交换 | 输出
动画
2023/12/01
最大値
最大值
请从给定的两个整数中选择大的那个。
最大値 | 输入 最大値 | 输出
动画
2023/12/01
交换排序
交换排序
请按照从小到大的顺序排列三个整数。
交换排序 | 输入 交换排序 | 输出
动画

第11章 对数组的基本查询

2023/12/01
和
和
请求出给定的N个整数的和。
和 | 输入 和 | 输出
动画
2023/12/01
最小值
最小值
请从给定的N个整数中求出最小值。
最小值 | 输入 最小值 | 输出
动画
2023/12/01
最小值的位置
最小值的位置
请从给定的有N个整数的数列中找出最小值的位置。
最小值的位置 | 输入 最小值的位置 | 输出
动画

第12章 探索

2023/12/01
线性搜索
线性搜索
请在数组中寻找给定的值。
线性搜索 | 输入 线性搜索 | 输出
动画
2023/12/01
二分搜索
二分搜索
请在一个元素按升序排序的数组中找到给定的值。
二分搜索 | 输入 二分搜索 | 输出
动画

第13章 对数组元素进行排序

2023/12/01
反转
反转
请按颠倒顺序排列整数列的元素。
反转 | 输入 反转 | 输出
动画
2023/12/01
插入
插入
请在保持升序的前提下，向已升序排序的整数列添加整数。
插入| 输入 插入| 输出
动画
2023/12/01
合并
合并
请将两个都按升序排列的整数列合并为一个按升序排列的整数列。
合并 | 输入 合并 | 输出
动画
2023/12/01
分割
分割
请以数组中某个元素为基准，将数组分成比基准小的元素组和比基准大的元素组。
分割 | 输入 分割 | 输出
动画

第14章 慢速排序

2023/12/01
冒泡排序
冒泡排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
冒泡排序 | 输入 冒泡排序 | 输出
动画
2023/12/01
选择排序
选择排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
选择排序 | 输入 选择排序 | 输出
动画
2023/12/01
插入排序
插入排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
插入排序 | 输入 插入排序 | 输出
动画
* 书中未介绍该算法。2023/12/01
双向冒泡排序
双向冒泡排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
双向冒泡排序 | 输入 双向冒泡排序 | 输出
动画

第15章 与整数相关的算法

2023/12/01
埃拉托色尼筛法
埃拉托色尼筛法
请创建一个素数表，如果整数 i 是素数，表中的第 i 个元素值为 1；如果整数 i 是合数，表中的第i 个元素值为 0。
埃拉托色尼筛法 | 输入 埃拉托色尼筛法 | 输出
动画
2023/12/01
欧几里得算法
欧几里得算法
请求出两个整数的最大公因数。
欧几里得算法 | 输入 欧几里得算法 | 输出
动画

第16章 基本数据结构1

2023/12/01
栈
栈
请实现遵循优先取出最后插入的数据的 Last-In-First-Out（LIFO）规则的数据结构。
栈 | 输入
栈 | 输出
动画
2023/12/01
队列
队列
请实现遵循优先取出最先插入的数据 First-In-First-Out (FIFO) 规则的数据结构。
队列 | 输入
队列 | 输出
动画

第17章 对数组的计算

2023/12/01
累積和
累积和
给定一个整数列和数列上的Q 个区间。请求出各区间的和。
累積和 | 输入 累積和 | 输出
动画
2023/12/01
一维累积和
一维累积和
给定多条线段，请求出在每个坐标处叠加的线段的数量。
一维累积和 | 输入 一维累积和 | 输出
动画
2023/12/01
二维累积和
二维累积和
给定多个矩形，请求出每个坐标上叠加的（一个或多个）矩形的数量。
二维累积和 | 输入 二维累积和 | 输出
动画
* 书中未介绍该算法。2023/12/01
网格中的动态规划
网格中的动态规划
有一个格子状的道路网。请计算从最西北的十字路口到最东南的十字路口的最短路径数，其中正在施工的十字路口不能通行。
网格中的最短路径数 | 输入 网格中的最短路径数 | 输出
动画

第18章 堆

2023/12/01
向上调整堆
向上调整堆
为提高优先级，最大堆的某个节点的值已更新。请重新构建最大堆。
向上调整堆| 输入 向上调整堆| 输出
动画
2023/12/01
向下调整堆
向下调整堆
为降低优先级，最大堆的某个节点的值已更新。请重新构建最大堆。
向下调整堆 | 输入 向下调整堆 | 输出
动画
2023/12/01
构建堆
构建堆
请基于任意的整数列构建最大堆。
构建堆 | 输入 构建堆 | 输出
动画
2023/12/01
优先队列
优先队列
请实现按优先级从高到低的顺序取出数据（这里假定值越大，优先级越高）的数据结构。
优先队列 | 输入
优先队列 | 输出
动画

基本数据结构比较表

数据结构 时间复杂度 规则 用到的技术
栈 栈 定数 后进先出 (LIFO: Last-In-First-Out)
队列 队列 定数 先进先出 (FIFO: First-In-First-Out)
优先队列 优先队列 対数 高优先级的数据先出 ヒープ

第19章 二叉树

2023/12/01
前序遍历
前序遍历
请遵循此要求来访问二叉树的节点 ：优先访问父节点而不是子节点。
前序遍历 | 输入 前序遍历 | 输出
动画
2023/12/01
后序遍历
后序遍历
请遵循此要求来访问二叉树的节点：优先访问子节点而不是父节点。
后序遍历 | 输入 后序遍历 | 输出
动画
2023/12/01
中序遍历
中序遍历
请遵循此要求来访问二叉树的节点：按照左子节点的子孙、父节点、右子节点的子孙的顺序访问。
中序遍历 | 输入 中序遍历 | 输出
动画
2023/12/01
层序遍历
层序遍历
请遵循此要求来访问二叉树的节点：在访问深度为k 的节点之前，完成对所有深度为k-1 的节点 的访问。
层序遍历 | 输入 层序遍历 | 输出
动画

第20章 排序

2023/12/01
合并排序
合并排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
合并排序 | 输入 合并排序 | 输出
动画
2023/12/01
快速排序
快速排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
快速排序 | 输入 快速排序 | 输出
动画
2023/12/01
堆排序
堆排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
堆排序 | 输入 堆排序 | 输出
动画
2023/12/01
计数排序
计数排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
计数排序 | 输入 计数排序 | 输出
动画
2023/12/01
谢尔排序
谢尔排序
请按从小到大的顺序对整数列{a0, a1, ..., aN-1}进行排序。
谢尔排序 | 输入 谢尔排序 | 输出
动画

排序算法比较表

算法 时间复杂度 是否稳定 是否原地排序 用到的技术 特点
冒泡排序 冒泡排序 二次函数 〇 〇

交换
× 不实用
选择排序 选择排序 二次函数 × 〇

交换
 
最小值的位置
× 不实用
插入排序 插入排序 二次函数 〇 〇

插入
〇对接近升序的数据是高效的
双向冒泡排序 双向冒泡排序 二次函数 〇 〇

交换
〇对接近升序的数据是高效的
合并排序 合并排序 线性、对数 〇 ×

合并
后序遍历
〇 稳定且高效
× 需要额外的内存
快速排序 快速排序 二次函数 线性、对数 × 〇

分割
前序遍历
× 基准选不好会导致低效
〇 原地排序且高效
堆排序 堆排序 线性、对数 × 〇

向下调整堆
× 在某些系统下实际的速度会变慢
谢尔排序 谢尔排序 二次函数 线性、对数 × 〇

插入排序
× 间距选不好会导致低效
计数排序 计数排序 线性、对数 〇 ×

累积和
× 元素的值有上限限制

第21章 基本数据结构 2

2023/12/01
双向链表
双向链表
请实现能够插入、搜索和删除元素的数据结构。
双向链表 | 输入
双向链表 | 输出
动画
2023/12/01
哈希表
哈希表
请实现提供字典功能的数据结构，包括数据搜索、添加和删除操作的实现。
字典 | 输入
字典 | 输出
动画

第22章　广度优先搜索

2023/12/01
广度优先搜索
广度优先搜索
请从任意起点出发，系统地访问图的所有节点。
广度优先搜索 | 输入 广度优先搜索 | 输出
动画
2023/12/01
使用 BFS 计算最短距离
使用 BFS 计算最短距离
请求出每个节点与起点间的最短距离。这里的距离指的是经过的边的个数。
BFSによる最短距離 | 输入 BFSによる最短距離 | 输出
动画
2023/12/01
Kahn 算法
Kahn 算法
请从表示任务和依赖关系的有向图中，求出任务的处理顺序。
拓扑排序 | 输入 拓扑排序 | 输出
动画

第23章　深度优先搜索

2023/12/01
深度优先搜索
深度优先搜索
请从任意起点出发，系统地访问图的所有节点。
深度优先搜索 | 输入 深度优先搜索 | 输出
动画
2023/12/01
連結成分分解
使用 DFS 进行连通分量分解
请将图分解成连通分量，并将同一个连通分量内的节点涂上同一种颜色。
連結成分分解 | 输入 連結成分分解 | 输出
动画
2023/12/01
使用 DFS 进行环检测
使用 DFS 进行环检测
请检查有向图中是否存在环。
閉路検知 | 输入 閉路検知 | 输出
动画
2023/12/01
Tarjan 算法
Tarjan 算法
请从表示任务和依赖关系的有向图中，求出任务的处理顺序。
拓扑排序 | 输入 拓扑排序 | 输出
动画

第24章　合并查找树

2023/12/01
按秩合并
按秩合并
给定森林和森林中多个树的根，请使用这些根来合并树，并重新构建森林。
木の合併 | 输入 木の合併 | 输出
动画
2023/12/01
路径压缩
路径压缩
请将森林中的树变形，降低树的高度。
路径压缩 | 输入 路径压缩 | 输出
动画
2023/12/01
合并查找树
合并查找树
请实现管理不相交集合的数据结构。
Union-Find | 输入
Union_Find | 输出
动画

第25章　求最小生成树的算法

2023/12/01
普里姆算法
普里姆算法
请求出加权无向图的最小生成树。
最小生成树 | 输入 最小生成树 | 输出
动画
2023/12/01
克鲁斯卡尔算法
克鲁斯卡尔算法
请求出加权无向图的最小生成树。
最小生成树 | 输入 最小生成树 | 输出
动画

第26章　求最短路径的算法

2023/12/01
迪杰斯特拉算法
迪杰斯特拉算法
基于给定的加权图、起点、终点信息，求从起点到终点的最短路径。
最短路径问题 | 输入 最短路径问题 | 输出
动画
2023/12/01
迪杰斯特拉算法
迪杰斯特拉算法（优先队列）
基于给定的加权图、起点、终点信息，求从起点到终点的最短路径。
最短路径问题 | 输入 最短路径问题 | 输出
动画
2023/12/01
贝尔曼-福特算法
贝尔曼-福特算法
基于给定的加权图、起点、终点信息，求从起点到终点的最短路径。
最短路径（负权边） | 输入 最短路径（负权边） | 输出
动画
2023/12/01
Floyd-Warshall 算法
Floyd-Warshall 算法
请从加权有向图的邻接矩阵中求出表示所有节点对的最短距离的矩阵。
全节点对之间的最短路径 | 输入 全节点对之间的最短路径 | 输出
动画

最短路径算法比较表

算法 时间复杂度 距离 用到的技术
广度优先搜索 广度优先搜索 线性 从一个起点到所有节点的最短路径
（边的数量） 		队列
队列
迪杰斯特拉算法 迪杰斯特拉算法
（线性搜索） 		二次函数 从一个起点到所有节点的最短路径
* 不能有负权边
迪杰斯特拉算法 迪杰斯特拉算法 线性、对数 从一个起点到所有节点的最短路径
* 不能有负权边 		优先队列
优先队列
贝尔曼-福特算法 贝尔曼-福特算法 三次函数 从一个起点到所有节点的最短路径
* 可以有负权边
* 可检测出负环
Floyd-Warshall 算法 Floyd-Warshall 算法 三次函数 全节点对之间的最短路径
* 可以有负权边
* 可检测出负环

第27章　计算几何学

2023/12/01
礼品包装算法
礼品包装算法
请求出给定点的集合的凸包。
凸包 | 输入 凸包 | 输出
动画
2023/12/01
Graham 扫描法
Graham 扫描法
请求出给定点的集合的凸包。
凸包 | 输入 凸包 | 输出
动画
2023/12/01
安德鲁算法
安德鲁算法
请求出给定点的集合的凸包。
凸包 | 输入 凸包 | 输出
动画

第28章　线段树

2023/12/01
线段树:RMQ
线段树: RMQ
请实现一个数据结构，对于给定的整数列进行单个元素的更新和区间最小值的检索。
Range Minimum Query | 输入
Range Minimum Query | 输出
动画
2023/12/01
线段树:RSQ
线段树: RSQ
请实现一个数据结构，对于给定的整数列进行单个元素的加法操作，并计算区间的和。
Range Sum Query | 输入
Range Sum Query | 输出
动画

第29章　搜索树

2023/12/01
二叉查找树
二叉查找树
请实现在数据的搜索、添加、删除之外，能够管理和提供已排序元素的字典数据结构。
排序字典 | 输入
排序字典 | 输出
动画
2023/12/01
旋转
旋转
请对子树进行变形，但是变形前后，中序遍历得到的节点的访问顺序必须相同。
旋转 | 输入 旋转 | 输出
动画
2023/12/01
树堆
树堆
请实现在数据的搜索、添加、删除之外，能够管理和提供已排序元素的字典数据结构。
排序字典 | 输入
排序字典 | 输出
动画

字典数据结构比较表

数据结构 时间复杂度 内存效率是否良好 是否有顺序 应用
列表 双向链表 线性 〇 〇有顺序 列表、字典
哈希 哈希表 定数 × × 字典
二叉查找树 二叉查找树 线性 対数 〇 〇已排序 字典、集合、
优先队列、最大堆、最小堆
树堆 树堆 対数 〇 〇已排序 字典、集合、
优先队列、最大堆、最小堆