动画算法与数据结构

本书是一本借助演示动画来讲解算法和数据结构的入门书。书中首先介绍阅读本书所需的最低限度的编程知识和基本概念。然后针对各个算法和数据结构，在指出其解决的问题后，通过空间结构、数据、时间结构（算法流程）、计算4个方面详细讲解。最后介绍相关的伪代码和应用示例。本书涉及的算法与数据结构较为全面，通过基于动画的可视化、详细的介绍和伪代码三方面进行讲解，帮助读者直观掌握各算法和数据结构的动作原理。

渡部有隆，出生于1979年，计算机理工学博士。日本会津大学计算机理工学部信息系统学部门副教授。专业领域为可视化编程语言。AIZU ONLINE JUDGE开发者。Mirenkov Nikolay，历任会津大学教授、会津大学副校长、会津大学特聘荣誉教授。

第 1章 编程的基本要素 3

1.1 变量和赋值运算 4

1.2 基本运算 6

1.3 控制结构 8

1.4 函数 12

第 2章 编程的应用要素 15 

2.1 命名规则 16

2.2 区间的表示方法 17

2.3 递归 18

2.4 类19

2.5 指针 21

第3章 算法设计的准备 25

3.1 大O表示法 26

3.2 问题的约束条件 28

第4章 空间结构概述31

4.1 空间结构：概述 32

4.2 数组 34

4.3 图35

4.4 树37

第5章 数组 39

5.1 单节点40

5.2 一维数组 41

5.3 二维数组 42

第6章 树 43

6.1 二叉树44

6.2 完全二叉树46

6.3 满二叉树 48

6.4 森林 49

第7章 图 5

7.1 无向图52

7.2 有向图54

第8章 点群 55

8.1 二维点群 56

第9章 动态结构 57

9.1 链表 58

9.2 动态二叉树60

第 10章 入门Getting Started 63

10.1 交换 64

10.2 最大值67

10.3 交换排序 71

第 11章 对数组的基本查询 Basic Query on Array 75

11.1 和76

11.2 最小值80

11.3 最小值的位置 84

第 12章 搜索Search 89

12.1 线性搜索 90

12.2 二分搜索 93

第 13章 对数组元素进行排序Rearranging Array Elements 99

13.1 反转 100

13.2 插入 103

13.3 合并 108

13.4 分割 113

第 14章 慢速排序Slow Sort 119

14.1 冒泡排序 120

14.2 选择排序 125

14.3 插入排序 129

第 15章 与整数相关的算法Integer Algorithms 133

15.1 埃拉托色尼筛法 134

15.2 欧几里得算法 138

第 16章 基本数据结构 1Elementary Data Structure 1 143

16.1 栈144

16.2 队列 148

第 17章 对数组的计算Computation on Array 153

17.1 累积和154

17.2 一维累积和158

17.3 二维累积和163

第 18章 堆 Heap 169

18.1 向上调整堆170

18.2 向下调整堆174

18.3 构建堆178

18.4 优先队列 183

第 19章 二叉树 Binary Tree 189

19.1 前序遍历 190

19.2 后序遍历 194

19.3 中序遍历 198

19.4 层序遍历 202

第 20章 排序 Sort 207

20.1 合并排序 208

20.2 快速排序 213

20.3 堆排序217

20.4 计数排序 222

20.5 谢尔排序 227

第 21章 基本数据结构 2Elementary Data Structure 2 235

21.1 双向链表 236

21.2 哈希表242

第 22章 广度优先搜索Breadth First Search 249

22.1 广度优先搜索 250

22.2 使用BFS计算最短距离255

22.3 Kahn算法259

第 23章 深度优先搜索Depth First Search 265

23.1 深度优先搜索 266

23.2 使用DFS进行连通分量分解 273

23.3 使用DFS进行环检测 277

23.4 Tarjan算法283

第 24章 合并查找树Union-Find Tree 287

24.1 按秩合并 288

24.2 路径压缩 292

24.3 合并查找树295

第 25章 求最小生成树的算法Algorithms for MST 303

25.1 普里姆算法304

25.2 克鲁斯卡尔算法 309

第 26章 求最短路径的算法Algorithms for Shortest Path 315

26.1 迪杰斯特拉算法 316

26.2 迪杰斯特拉算法（优先队列）321

26.3 贝尔曼-福特算法328

26.4 Floyd-Warshall算法334

第 27章 计算几何学Computational Geometry 339

27.1 礼品包装算法 340

27.2 Graham扫描法 345

27.3 安德鲁算法352

第 28章 线段树Segment Tree 361

28.1 线段树：RMQ 362

28.2 线段树：RSQ370

第 29章 搜索树Search Tree 375

29.1 二叉查找树376

29.2 旋转 381

29.3 树堆 385

参考文献 391

本书是一本借助演示动画来讲解算法和数据结构的入门书。书中首先介绍阅读本书所需的最低限度的编程知识和基本概念。然后针对各个算法和数据结构，在指出其解决的问题后，通过空间结构、数据、时间结构（算法流程）、计算4个方面详细讲解。最后介绍相关的伪代码和应用示例。本书涉及的算法与数据结构较为全面，通过基于动画的可视化、详细的介绍和伪代码三方面进行讲解，帮助读者直观掌握各算法和数据结构的动作原理。

渡部有隆，出生于1979年，计算机理工学博士。日本会津大学计算机理工学部信息系统学部门副教授。专业领域为可视化编程语言。AIZU ONLINE JUDGE开发者。Mirenkov Nikolay，历任会津大学教授、会津大学副校长、会津大学特聘荣誉教授。