动画算法与数据结构

本书是一本借助演示动画来讲解算法和数据结构的入门书。书中首先介绍阅读本书所需的最低限度的编程知识和基本概念。然后针对各个算法和数据结构，在指出其解决的问题后，通过空间结构、数据、时间结构（算法流程）、计算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