第1章 绪论

1.1计算机与算法

1.1.1古埃及人的绳索

1.1.2欧几里得的尺规

1.1.3起泡排序

1.1.4算法

1.1.5算法效率

1.2复杂度度量

1.2.1时间复杂度

1.2.2渐进复杂度

1.2.3空间复杂度

1.3复杂度分析

1.3.1常数0（1）

1.3.2对数0（logn）

1.3.3线性0（n）

1.3.4多项式0（polynomial（n））

1.3.5指数0（2n）

1.3.6复杂度层次

1.3.7输入规模

1.4递归

1.4.1线性递归

1.4.2递归分析

1.4.3递归模式

1.4.4递归消除

1.4.5二分递归

1.5抽象数据类型

第2章 向量

2.1从数组到向量

2.1.1数组

2.1.2向量

2.2接口

2.2.1 ADT接口

2.2.2操作实例

2.2.3 Vector模板类

2.3构造与析构

2.3.1默认构造方法

2.3.2基于复制的构造方法

2.3.3析构方法

2.4动态空间管理

2.4.1静态空间管理

2.4.2可扩充向量

2.4.3扩容

2.4.4分摊分析

2.4.5缩容

2.5常规向量

2.5.1直接引用元素

2.5.2置乱器

2.5.3判等器与比较器

2.5.4无序查找

2.5.5插入

2.5.6删除

2.5.7唯一化

2.5.8遍历

2.6有序向量

2.6.1比较器

2.6.2有序性甄别

2.6.3唯一化

2.6.4查找

2.6.5二分查找（版本A）

2.6.6 Fibonacci查找

2.6.7二分查找（版本B）

2.6.8二分查找（版本C）

2.7排序与下界

2.7.1有序性

2.7.2排序及其分类

2.7.3下界

2.7.4比较树

2.7.5估计下界

2.8排序器

2.8.1统一入口

2.8.2起泡排序

2.8.3归并排序

第3章 列表

3.1从向量到列表

3.1.1从静态到动态

3.1.2由秩到位置

3.1.3列表

3.2接口

3.2.1列表节点

3.2.2列表

3.3列表

3.3.1头、尾节点

3.3.2默认构造方法

3.3.3由秩到位置的转换

3.3.4查找

3.3.5插入

3.3.6基于复制的构造

3.3.7删除

3.3.8析构

3.3.9唯一化

3.3.10遍历

3.4有序列表

3.4.1唯一化

3.4.2查找

3.5排序器

3.5.1统一入口

3.5.2插入排序

3.5.3选择排序

3.5.4归并排序

第4章 栈与队列

4.1栈

4.1.1 ADT接口

4.1.2操作实例

4.1.3 Stack模板类

4.2栈与递归

4.2.1函数调用栈

4.2.2避免递归

4.3栈的典型应用

4.3.1逆序输出

4.3.2递归嵌套

4.3.3延迟缓冲

4.3.4逆波兰表达式

4.4试探回溯法

4.4.1试探与回溯

4.4.2八皇后

4.4.3迷宫寻径

4.5队列

4.5.1概述

4.5.2 ADT接口

4.5.3操作实例

4.5.4 Queue模板类

4.6队列应用

4.6.1循环分配器

4.6.2银行服务模拟

第5章 二叉树

5.1二叉树及其表示

5.1.1树

5.1.2二叉树

5.1.3多叉树

5.2编码树

5.2.1二进制编码

5.2.2二叉编码树

5.3二叉树的实现

5.3.1二叉树节点

5.3.2二叉树节点操作接口

5.3.3二叉树

5.4遍历

5.4.1递归式遍历

5.4.2迭代版先序遍历

5.4.3迭代版中序遍历

5.4.4迭代版后序遍历

5.4.5层次遍历

5.5 Huffman编码

5.5.1 PFC编码及解码

5.5.2最优编码树

5.5.3 Huffman编码树

5.5.4 Huffman编码算法

第6章 图

6.1概述

6.2抽象数据类型

6.2.1操作接口

6.2.2 Graph模板类

6.3邻接矩阵

6.3.1原理

6.3.2实现

6.3.3时间性能

6.3.4空间性能

6.4邻接表

6.4.1原理

6.4.2复杂度

6.5图遍历算法概述

6.6广度优先搜索

6.6.1策略

6.6.2实现

6.6.3实例

6.6.4复杂度

6.6.5应用

6.7深度优先搜索

6.7.1策略

6.7.2实现

6.7.3实例

6.7.4复杂度

6.7.5应用

6.8拓扑排序

6.8.1应用

6.8.2有向无环图

6.8.3算法

6.8.4实现

6.8.5实例

6.8.6复杂度

6.9双连通域分解

6.9.1关节点与双连通域

6.9.2蛮力算法

6.9.3可行算法

6.9.4实现

6.9.5实例

6.9.6复杂度

6.10优先级搜索

6.10.1优先级与优先级数

6.10.2基本框架

6.10.3复杂度

6.11最小支撑树

6.11.1支撑树

6.11.2最小支撑树

6.11.3歧义性

6.11.4蛮力算法

6.11.5 Prim算法

6.12最短路径

6.12.1最短路径树

6.12.2 Dijkstra算法

第7章 搜索树

7.1查找

7.1.1循关键码访问

7.1.2词条

7.1.3序与比较器

7.2二叉搜索树

7.2.1顺序性

7.2.2中序遍历序列

7.2.3 BST模板类

7.2.4查找算法及其实现

7.2.5插入算法及其实现

7.2.6删除算法及其实现

7.3平衡二叉搜索树

7.3.1树高与性能

7.3.2理想平衡与适度平衡

7.3.3等价变换

7.3.4旋转调整

7.4 AVL树

7.4.1定义及性质

7.4.2节点插入

7.4.3节点删除

7.4.4统一重平衡算法

第8章 高级搜索树

8.1伸展树

8.1.1局部性

8.1.2逐层伸展

8.1.3双层伸展

8.1.4伸展树的实现

8.2 B-树

8.2.1多路平衡查找

8.2.2 ADT接口及其实现

8.2.3关键码查找

8.2.4性能分析

8.2.5关键码插入

8.2.6上溢与分裂

8.2.7关键码删除

8.2.8下溢与合并

8.3红黑树

8.3.1概述

8.3.2红黑树接口定义

8.3.3节点插入算法

8.3.4节点删除算法

8.4 kd-树

8.4.1范围查询

8.4.2 kd-树

8.4.3基于2d-树的范围查询

第9章 词典

9.1词典ADT

9.1.1操作接口

9.1.2操作实例

9.1.3接口定义

9.1.4实现方法

9.2跳转表

9.2.1 Skiplist模板类

9.2.2总体逻辑结构

9.2.3四联表

9.2.4查找

9.2.5空间复杂度

9.2.6时间复杂度

9.2.7插入

9.2.8删除

9.3散列表

9.3.1完美散列

9.3.2装填因子与空间利用率

9.3.3散列函数

9.3.4散列表

9.3.5冲突及其排解

9.3.6闭散列策略

9.3.7查找与删除

9.3.8插入

9.3.9更多闭散列策略

9.3.10散列码转换

9.4散列应用

9.4.1桶排序

9.4.2最大间隙

9.4.3基数排序

第10章 优先级队列

10.1优先级队列ADT

10.1.1优先级与优先级队列

10.1.2关键码、比较器与偏序关系

10.1.3操作接口

10.1.4操作实例：选择排序

10.1.5接口定义

10.1.6应用实例：Huffman编码树

10.2堆

10.2.1完全二叉堆

10.2.2元素插入

10.2.3元素删除

10.2.4建堆

10.2.5就地堆排序

10.3左式堆

10.3.1堆合并

10.3.2单侧倾斜

10.3.3 PQ_LeftHeap模板类

10.3.4空节点路径长度

10.3.5左倾性与左式堆

10.3.6最右侧通路

10.3.7合并算法

10.3.8实例

10.3.9合并操作merge（）的实现

10.3.10复杂度

10.3.11基于合并的插入和删除

第11章 串

11.1串及串匹配

11.1.1串

11.1.2串匹配

11.1.3测评标准与策略

11.2蛮力算法

11.2.1算法描述

11.2.2算法实现

11.2.3时间复杂度

11.3 KMP算法

11.3.1构思

11.3.2 next表

11.3.3 KMP算法

11.3.4 next[0]=-1

11.3.5 next[j+1]

11.3.6构造next表

11.3.7性能分析

11.3.8继续改进

11.4 BM算法

11.4.1思路与框架

11.4.2坏字符策略

11.4.3好后缀策略

11.4.4 GS[]表构造算法

11.4.5算法纵览

11.5 Karp-Rabin算法

11.5.1构思

11.5.2算法与实现

第12章 排序

12.1快速排序

12.1.1分治策略

12.1.2轴点

12.1.3快速排序算法

12.1.4快速划分算法

12.1.5复杂度

12.1.6应对退化

12.2选取与中位数

12.2.1概述

12.2.2众数

12.2.3归并向量的中位数

12.2.4基于优先级队列的选取

12.2.5基于快速划分的选取

12.2.6 k-选取算法

12.3希尔排序

12.3.1递减增量策略

12.3.2增量序列

附录

参考文献

插图索引

表格索引

算法索引

代码索引

关键词索引