第1章 绪论 1
1.1 问题求解 1
1.2 算法表达中的抽象机制 1
1.3 抽象数据类型 4
1.3.1 抽象数据类型的基本概念 4
1.3.2 使用抽象数据类型的好处 6
1.3.3 数据结构、数据类型和抽象数据类型 6
1.4 用C++描述数据结构与算法 7
1.4.1 变量、指针和引用 7
1.4.2 函数与参数传递 8
1.4.3 C++的类 9
1.4.4 类的对象 10
1.4.5 构造函数与析构函数 11
1.4.6 运算符重载 11
1.4.7 友元函数 11
1.4.8 内联函数 12
1.4.9 结构 12
1.4.10 联合 12
1.4.11 异常 12
1.4.13 动态存储分配 13
1.4.12 模板 13
1.5 算法复杂性分析 15
1.5.1 算法与程序 15
1.5.2 算法复杂性的概念 15
1.5.3 算法复杂性的渐近性态 16
习题一 18
第2章 表 20
2.1 ADT表 20
2.2 用数组实现表 21
2.3 用指针实现表 25
2.4 用间接寻址方法实现表 31
2.5 用游标实现表 34
2.6 循环链表 41
2.7 双链表 45
习题二 50
第3章 栈 54
3.1 ADT栈 54
3.2 用数组实现栈 55
3.3 用指针实现栈 58
3.4 等价类划分问题 61
习题三 63
4.2 用指针实现队列 66
4.1 ADT队列 66
第4章 队列 66
4.3 用循环数组实现队列 69
4.4 电路布线问题 74
习题四 77
第5章 串 79
5.1 ADT串 79
5.2 用数组实现串 80
5.3 用指针实现串 85
5.6 模式匹配 86
5.6.1 朴素的模式匹配算法 86
5.5 串的堆结构 86
5.4 串的块链表示法 86
5.6.2 模式匹配的KMP算法 88
习题五 93
第6章 排序与选择 95
6.1 简单排序算法 95
6.1.1 冒泡排序 95
6.1.2 插入排序 96
6.1.3 选择排序 97
6.1.4 简单排序算法的计算复杂性 97
6.2.1 算法基本思想及实现 98
6.2 快速排序算法 98
6.2.2 算法的性能 100
6.2.3 随机快速排序算法 100
6.3 合并排序算法 101
6.3.1 算法基本思想及实现 101
6.3.2 消除递归 101
6.3.3 自然合并排序 103
6.4 线性时间排序算法 103
6.4.1 计数排序 103
6.4.2 桶排序 105
6.5.1 平均情况下的线性时间选择算法 106
6.5 中位数与第k小元素 106
6.5.2 最坏情况下的线性时间选择算法 107
习题六 109
第7章 树 111
7.1 树的定义 111
7.2 树的遍历 113
7.3 树的表示法 115
7.3.1 父结点数组表示法 115
7.3.2 儿子链表表示法 116
7.3.3 左儿子右兄弟表示法 116
7.4 二叉树 117
7.5 ADT二叉树 119
7.6.1 二叉树的顺序存储结构 120
7.6 二叉树的实现 120
7.6.2 二叉树的结点度表示法 121
7.6.3 用指针实现二叉树 122
7.7 线索二叉树 126
习题七 128
第8章 图 131
8.1 图的基本概念 131
8.2 抽象数据类型ADT图 134
8.3.1 邻接矩阵表示法 135
8.3 图的表示法 135
8.3.2 邻接表表示法 136
8.3.3 紧缩邻接表 136
8.4 用邻接矩阵实现图 137
8.4.1 用邻接矩阵实现赋权有向图 137
8.4.2 用邻接矩阵实现赋权无向图 140
8.4.3 用邻接矩阵实现有向图 141
8.4.4 用邻接矩阵实现无向图 141
8.5 用邻接表实现图 141
8.5.1 邻接表基类 141
8.5.2 用邻接表实现有向图 143
8.5.3 用邻接表实现无向图 144
8.5.4 用邻接表实现赋权有向图 145
8.5.5 用邻接表实现赋权无向图 148
8.6 图的遍历 149
8.6.1 图的搜索游标 150
8.6.2 广度优先搜索 152
8.6.3 深度优先搜索 154
8.7 最短路径 155
8.7.1 单源最短路径 155
8.7.2 所有顶点对之间的最短路径 159
8.8.1 最小生成树性质 160
8.8 最小生成树 160
8.8.2 Prim算法 161
8.8.3 Kruskal算法 163
8.9 图匹配 166
习题八 168
第9章 集合 170
9.1 以集合为基础的抽象数据类型 170
9.1.1 集合的定义和记号 170
9.1.2 定义在集合上的基本运算 171
9.1.3 集合的简单表示法 171
9.2.1 实现字典的简单方法 179
9.2 字典 179
9.2.2 用散列表实现字典 180
9.3 有序字典 189
9.3.1 有序字典的定义 189
9.3.2 用数组实现有序字典 189
9.3.3 用二叉搜索树实现有序字典 190
9.3.4 AVL树 199
9.3.5 红黑树 209
9.4 优先队列 218
9.4.1 优先队列的定义 218
9.4.3 优先级树和堆 219
9.4.2 用字典实现优先队列 219
9.4.4 用数组实现堆 221
9.4.5 可并优先队列 224
9.5 并查集 229
9.5.1 并查集的定义及其简单实现 229
9.5.2 用父亲数组实现并查集 230
习题九 233
第10章 算法设计策略 236
10.1 递归与分治策略 236
10.1.1 递归的概念 236
10.1.2 分治法的基本思想 238
10.1.3 二分搜索技术 239
10.1.4 棋盘覆盖问题 240
10.2 动态规划 242
10.2.1 矩阵连乘问题 243
10.2.2 动态规划算法的基本要素 247
10.2.3 最大子段和问题 250
10.3 贪心算法 256
10.3.1 活动安排问题 256
10.3.2 贪心算法的基本要素 258
10.3.3 哈夫曼编码算法 261
10.4.1 回溯法的算法框架 265
10.4 回溯法 265
10.4.2 符号三角形问题 270
10.4.3 圆排列问题 273
10.4.4 连续邮资问题 275
10.4.5 回溯法的效率分析 277
10.5 分支限界法 280
10.5.1 分支限界法的基本思想 280
10.5.2 装载问题 282
10.5.3 批处理作业调度问题 290
习题十 295
参考文献 299