图解算法

第1部分 预备知识 第1章 概述 .....................................................................9 数据结构简介 ........................................................................................................10 算法简介 ............................................................................................................... 11 小酌软件工程 ........................................................................................................14 如何使用本书 ........................................................................................................15 第2章 指针操作 ............................................................ 16 指针基础 ...............................................................................................................17 存储空间分配 ........................................................................................................18 数据集合与指针的算术运算..................................................................................20 作为函数参数的指针.............................................................................................22 泛型指针与类型转换.............................................................................................25 函数指针 ...............................................................................................................28 问与答 ...................................................................................................................28 相关主题 ...............................................................................................................30 第3章 递归 ................................................................... 31 基本递归 ...............................................................................................................32 尾递归 ...................................................................................................................35ii ｜ 目录 问与答 ...................................................................................................................37 相关主题 ...............................................................................................................39 第4章 算法分析 ............................................................ 40 最坏情况分析 ........................................................................................................41 O表示法 ................................................................................................................41 计算的复杂度 ........................................................................................................43 实例分析： 插入排序.............................................................................................46 问与答 ...................................................................................................................47 相关主题 ...............................................................................................................48 第2部分 数据结构 第5章 链表 ................................................................... 51 单链表介绍............................................................................................................52 单链表接口的定义.................................................................................................53 单链表的实现与分析.............................................................................................56 使用链表的例子： 页帧管理..................................................................................61 双向链表介绍 ........................................................................................................63 双向链表接口的定义.............................................................................................64 双向链表的实现与分析 .........................................................................................67 循环链表介绍 ........................................................................................................73 循环链表接口的定义.............................................................................................74 循环链表的实现与分析 .........................................................................................76 使用循环链表的例子： 第二次机会页面置换法....................................................79 问与答 ...................................................................................................................82 相关主题 ...............................................................................................................84 第6章 栈和队列 ............................................................ 85 栈的描述 ...............................................................................................................86 栈的接口定义 ........................................................................................................87 栈的实现与分析 ....................................................................................................88目录 | iii 队列的描述............................................................................................................91 队列的接口定义 ....................................................................................................91 队列的实现与分析.................................................................................................93 队列示例： 事件处理.............................................................................................95 问与答 ...................................................................................................................96 相关主题 ...............................................................................................................97 第7章 集合 ................................................................... 98 集合介绍 ...............................................................................................................99 集合的性质..........................................................................................................100 集合接口的定义 ..................................................................................................102 集合抽象数据类型的实现和分析 ........................................................................105 Set示例： 集合覆盖 ............................................................................................. 112 问与答 ................................................................................................................. 116 相关主题 ............................................................................................................. 117 第8章 哈希表.............................................................. 119 链式哈希表的描述...............................................................................................121 链式哈希表的接口定义 .......................................................................................124 链式哈希表的实现与分析 ...................................................................................126 链式哈希表的例子： 符号表................................................................................131 开地址哈希表的描述...........................................................................................133 开地址哈希函数的接口定义................................................................................136 开地址哈希表的实现与分析................................................................................138 问与答 .................................................................................................................144 相关主题 .............................................................................................................145 第9章 树 .................................................................... 146 二叉树介绍..........................................................................................................148 二叉树的接口定义...............................................................................................151 二叉树的实现与分析...........................................................................................155 二叉树示例： 表达式处理 ...................................................................................161 二叉搜索树介绍 ..................................................................................................165iv ｜ 目录 二叉搜索树的接口定义 .......................................................................................166 二叉搜索树的实现与分析 ...................................................................................168 问与答 .................................................................................................................185 相关主题 .............................................................................................................187 第10章 堆和优先队列.................................................. 188 堆的描述 .............................................................................................................189 堆的接口定义 ......................................................................................................190 堆的实现与分析 ..................................................................................................191 优先队列的描述 ..................................................................................................199 优先队列的接口定义...........................................................................................199 优先队列的实现与分析 .......................................................................................201 优先队列的示例： 包裹分拣................................................................................202 问与答 .................................................................................................................203 相关主题 .............................................................................................................205 第11章 图................................................................... 206 图的描述 .............................................................................................................207 图的接口定义 ......................................................................................................214 图的实现与分析 ..................................................................................................217 关于图的应用举例： 计算网络跳数 ....................................................................225 关于图的应用举例： 拓扑排序 ............................................................................229 问与答 .................................................................................................................232 相关主题 .............................................................................................................234 第3部分 算法 第12章 排序和搜索 ..................................................... 237 插入排序的描述 ..................................................................................................239 插入排序的接口定义...........................................................................................239 插入排序的实现与分析 .......................................................................................240 快速排序的描述 ..................................................................................................242目录 | v 快速排序的接口定义...........................................................................................243 快速排序的实现与分析 .......................................................................................243 快速排序的例子： 目录列表................................................................................247 归并排序的描述 ..................................................................................................249 归并排序的接口定义...........................................................................................249 归并排序的实现与分析 .......................................................................................250 计数排序的描述 ..................................................................................................254 计数排序的接口定义...........................................................................................254 计数排序的实现与分析 .......................................................................................254 基数排序的描述 ..................................................................................................257 基数排序的接口定义...........................................................................................257 基数排序的实现与分析 .......................................................................................258 二分查找的描述 ..................................................................................................260 二分查找的接口定义...........................................................................................260 二分查找的实现与分析 .......................................................................................261 二分查找的例子： 拼写检查器 ............................................................................263 问与答 .................................................................................................................264 相关主题 .............................................................................................................266 第13章 数值计算 ........................................................ 267 多项式插值法 ......................................................................................................268 多项式插值的接口定义 .......................................................................................272 多项式插值的实现与分析 ...................................................................................272 最小二乘估计法 ..................................................................................................274 最小二乘估计的接口定义 ...................................................................................276 最小二乘估计的实现和分析................................................................................276 方程求解介绍 ......................................................................................................277 方程求解的接口定义...........................................................................................281 方程求解的实现与分析 .......................................................................................282 问与答 .................................................................................................................283 相关主题 .............................................................................................................284vi ｜ 目录 第14章 数据压缩 ........................................................ 285 位操作的描述 ......................................................................................................288 位操作的接口定义...............................................................................................288 位操作的实现与分析...........................................................................................289 霍夫曼编码的描述...............................................................................................292 霍夫曼编码的接口定义 .......................................................................................295 霍夫曼编码的分析与实现 ...................................................................................296 霍夫曼编码的例子： 网络优化 ............................................................................306 LZ77的描述.........................................................................................................308 LZ77的接口定义 ................................................................................................. 311 LZ77的实现与分析..............................................................................................312 问与答 .................................................................................................................321 相关主题 .............................................................................................................322 第15章 数据加密 ........................................................ 324 DES算法介绍 ......................................................................................................326 DES的接口定义...................................................................................................334 DES算法的实现和分析 .......................................................................................334 DES应用举例： 分组加密模式 ............................................................................341 RSA算法介绍 ......................................................................................................344 RSA的接口定义 ..................................................................................................347 RSA算法的实现与分析 .......................................................................................348 问与答 .................................................................................................................350 相关主题 .............................................................................................................352 第16章 图算法............................................................ 354 最小生成树的描述...............................................................................................357 最小生成树的接口定义 .......................................................................................358 最小生成树的实现与分析 ...................................................................................359 最短路径的描述 ..................................................................................................363 最短路径的接口定义...........................................................................................364 最短路径的实现与分析 .......................................................................................365目录 | vii 最短路径的例子： 路由表 ...................................................................................369 旅行商问题的描述...............................................................................................372 旅行商问题的接口定义 .......................................................................................374 旅行商问题的实现与分析 ...................................................................................374 问与答 .................................................................................................................377 相关主题 .............................................................................................................378 第17章 几何算法 ........................................................ 380 测试线段是否相交...............................................................................................382 测试线段是否相交的标准方法 ............................................................................383 检测线段是否相交的接口定义 ............................................................................385 检测线段是否相交的实现与分析 ........................................................................385 凸包简介 .............................................................................................................387 Jarvis’s March......................................................................................................387 凸包的接口定义 ..................................................................................................389 凸包的实现与分析...............................................................................................389 球面弧长 .............................................................................................................392 求解球面弧长的接口定义 ...................................................................................395 求解球面弧长的实现和分析................................................................................395 球面弧长的应用举例： 地球上两点之间的近似距离 ..........................................396 问与答 .................................................................................................................398 相关主题 .............................................................................................................400