简要 目录

第1章 绪论 1

§1.1§1.1§1.1§1.1 计算机与法 计算机与法 ________________ 2

§1.2§1.2§1.2§1.2 复杂度量 复杂度量 _________________ 8

§1.3§1.3§1.3§1.3 复杂度分析 复杂度分析 ________________ 11

§1.4§1.4§1.4§1.4 *递归 ______________________ 16

§1.5§1.5§1.5§1.5 抽象数据类型 抽象数据类型 _______________ 26 第2章 向量 27

§2.1§2.1§2.1§2.1 从数组到向量 从数组到向量 _______________ 28

§2 .2 接口 ______________________ 29

§2.3§2.3§2.3§2.3 构 造与析构 造与析________________ 32

§2.4§2.4§2.4§2.4 动态空间管理 动态空间管理 _______________ 33

§2.5§2.5§2.5§2.5 常规向量 __________________ 37

§2.6§2.6§2.6§2.6 有序向量 __________________ 44

§2.7§2.7§2.7§2.7 *排序与下界 排序与下界 ________________ 57

§2.8§2.8§2.8§2.8 排序器 ____________________ 59 第3章 列表 65

§3.1§3.1§3.1§3.1 从向量到列表 从向量到列表 _______________ 66

§3.2§3.2§3.2§3.2 接口 ______________________ 67

§3.33.33.3 列表 ______________________ 71

§3.4§3.4§3.4§3.4 有序列表 __________________ 77

§3.5§3.5§3.5§3.5 排序器 ____________________ 78 第4章 栈与队列 栈与队列 85

§4.1§4.1§4.1§4.1 栈 ________________________ 86

§4.2§4.2§4.2§4.2 栈与递归 __________________ 88

§4.3§4.3§4.3§4.3 栈的典型应用 栈的典型应用 _______________ 90

§4.4§4.4§4.4§4.4 *试探回溯法 试探回溯法 ________________ 99

§4.5§4.5§4.5§4.5 队列 _____________________ 105

§4.6§4.6§4.6§4.6 队列应用 _________________ 107 第5章 二叉树 109

§5.1§5.1§5.1§5.1 二叉树及其表示 二叉树及其表示 ____________ 110

§5.2§5.2§5.2§5.2 编码树 ___________________ 114

§5.3§5.3§5.3§5.3 二叉树的实现 二叉树的实现 ______________ 117

§5.4§5.4§5.4§5.4 遍历 _____________________ 124

§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman§5.5 Huffman编码 ______________ 136 第6章 图 149

§6.1§6.1§6.1§6.1 概述 _____________________ 150

§6.2§6.2§6.2§6.2 抽象数据类型 抽象数据类型 ______________ 153

§6.3§6.3§6.3§6.3 邻接矩阵 _________________ 155

§6.4§6.4§6.4§6.4 邻接表 ___________________ 158

§6.5§6.5§6.5§6.5 图遍历算法概述 图遍历算法概述 ____________ 159

§6.6§6.6§6.6§6.6 广度优先搜索 广度优先搜索 ______________ 159

§6.7§6.7§6.7§6.7 深度 优先搜索 优先搜索 ______________ 162

§6.8§6.8§6.8§6.8 拓扑排序 _________________ 165

§6.9§6.9§6.9§6.9 *双连通域分解 双连通域分解 _____________ 168

§6.10§6.10§6.10§6.10§6.10 优先级搜索 优先级搜索 ______________ 172

§6.11§6.11§6.11§6.11§6.11 最小支撑树 最小支撑树 ______________ 174

§6.12§6.12§6.12§6.12§6.12 最短路径 最短路径 ________________ 178 第7章 搜索树 181

§7.1§7.1§7.1§7.1 查找 _____________________ 183

§7.2§7.2§7.2§7.2 二叉搜索树 二叉搜索树 _______________ 184

§7.3§7.3§7.3§7.3 平衡二叉搜索树 平衡二叉搜索树 ____________ 191

§7.4 AVL§7.4 AVL§7.4 AVL§7.4 AVL§7.4 AVL§7.4 AVL§7.4 AVL§7.4 AVL树 ____________________ 194 第8章 高级搜索树 高级搜索树 203

§8.1§8.1§8.1§8.1 伸展树 ___________________ 204

§8.2 B§8.2 B§8.2 B§8.2 B§8.2 B§8.2 B-树 _____________________ 212

§8.3§8.3§8.3§8.3 *红黑树 ___________________ 227

§8.4§8.4§8.4§8.4 *kd -树 ___________________ 239 第9章 词典 245

§9.1§9.1§9.1§9.1 词典 ADTADTADT __________________ 247

§9.2§9.2§9.2§9.2 *跳转表 ___________________ 249

§9.3§9.3§9.3§9.3 散列表 ___________________ 259

§9.4§9.4§9.4§9.4 *散列应用 散列应用 _________________ 277 第10章 优先级队列 优先级队列 281

§10.1§10.1§10.1§10.1§10.1 优先级队列 优先级队列 ADT ___________ 282

§10.2§10.2§10.2§10.2§10.2 堆 ______________________ 286

§10.3§10.3§10.3§10.3§10.3 *左式堆 __________________ 297 第11章 串 305

§11.1§11.1§11.1§11.1§11.1 串及匹配 串及匹配 ______________ 306

§11.2§11.2§11.2§11.2§11.2 蛮力算法 蛮力算法 ________________ 309

§11.3 KMP§11.3 KMP§11.3 KMP§11.3 KMP§11.3 KMP§11.3 KMP§11.3 KMP§11.3 KMP§11.3 KMP算法 _________________ 311

§11.4§11.4§11.4§11.4§11.4 *BM 算法 _________________ 317

§11.5§11.5§11.5§11.5§11.5 *KarpKarpKarpKarp-RabinRabinRabinRabinRabin算法 _________ 327 第12章 排序 333

§12.1§12.1§12.1§12.1§12.1 快速排序 快速排序 ________________ 334

§12.2§12.2§12.2§12.2§12.2 *选取与中位数 选取与中位数 ____________ 341

§12.3§12.3§12.3§12.3§12.3 *希尔排序 希尔排序 ________________ 350 附录 357

参考文献 ______________________ 358

插图索引 ______________________ 362

表格索引 ______________________ 369

算法索引 ______________________ 370

代码索引 ______________________ 371

关键词索引 ____________________ 377