第1章 数据结构和算法 1
1.1 数据和数据类型 1
1.1.1 数据和数据元素 1
1.1.2 数据类型 2
1.1.3 抽象数据类型 4
1.1.4 抽象数据类型程序应用实例 5
1.1.5 数据对象 6
1.2 数据结构 6
1.2.1 数据的逻辑结构 6
1.2.2 数据元素的存储结构 8
1.2.3 常用的数据运算 10
1.3 算法描述工具——C语言 12
1.3.1 指针类型与指针变量 13
1.3.2 结构类型与结构变量 15
1.3.3 函数与参数 17
1.3.4 递归定义和递归函数 18
1.3.5 动态存储分配 19
1.3.6 文件操作 21
1.3.7 程序测试与测试集 23
1.3.8 测试数据的设计 23
1.3.9 程序调试问题 25
1.4 算法和算法评价 25
1.4.1 算法的概念 25
1.4.2 算法的性质 27
1.4.3 算法的评价标准 28
1.5 算法性能分析 29
1.5.1 算法的时间性能分析 29
1.5.2 算法的空间性能分析 33
小结 33
习题 34
第2章 顺序表及其应用 38
2.1 顺序表的基本概念 38
2.1.1 顺序表的定义 38
2.1.2 顺序表的数据结构分析 38
2.1.3 顺序表的数据类型描述 39
2.2 顺序表基本算法 40
2.3 顺序表基本算法性能分析 43
2.3.1 时间性能分析 43
2.3.2 空间性能分析 44
2.4 顺序表的应用1——查找问题 44
2.4.1 查找的概念 44
2.4.2 简单顺序查找算法 45
2.4.3 有序表的二分查找算法 47
2.4.4 分块查找算法 51
2.4.5 3种查找算法的性能比较 52
2.5 顺序表的应用2——排序问题 53
2.5.1 排序的概念 53
2.5.2 顺序表的数据类型 54
2.5.3 插入排序——直接插入排序算法 54
2.5.4 插入排序——希尔排序算法 57
2.5.5 交换排序——冒泡排序算法 59
2.5.6 交换排序——快速排序算法 61
2.5.7 选择排序——直接选择排序算法 65
2.5.8 归并排序算法 67
2.5.9 排序算法的性能分析与比较 71
2.6 顺序表的应用3——字符处理问题 71
2.6.1 串和顺序串的定义及相关概念 71
2.6.2 顺序串的数据结构分析 72
2.6.3 顺序串的基本运算 72
2.6.4 顺序串的数据类型定义 74
2.6.5 顺序串的基本运算算法 74
2.6.6 串的模式匹配算法 77
小结 78
习题 78
第3章 链表及其应用 83
3.1 链表的基本概念 83
3.1.1 链表的定义 83
3.1.2 链表的逻辑结构 83
3.1.3 链表的存储结构 84
3.1.4 静态链表和动态链表 85
3.1.5 链表基本运算 86
3.2 单链表的数据结构 86
3.2.1 单链表的逻辑结构 86
3.2.2 单链表的存储结构 86
3.3 单链表基本算法 88
3.3.1 单链表的基本算法 88
3.3.2 单链表基本算法性能分析 93
3.4 循环链表 94
3.4.1 单循环链表 94
3.4.2 双向循环链表 95
3.4.3 双向循环链表的结点插入算法 96
3.4.4 双向循环链表的结点删除算法 97
3.5 链表的应用 98
3.5.1 多项式相加问题 98
3.5.2 两个链表的归并问题 101
3.5.3 箱子排序问题 103
3.5.4 链表在字符处理方面的应用——链串 105
小结 107
习题 107
第4章 堆栈及其应用 112
4.1 堆栈的基本概念 112
4.1.1 堆栈的定义 112
4.1.2 堆栈的逻辑结构 112
4.1.3 堆栈的基本算法 113
4.2 顺序栈及其基本算法 113
4.2.1 顺序栈的概念及数据类型 113
4.2.2 顺序栈的基本算法 114
4.2.3 顺序栈基本算法性能分析 115
4.3 链栈及其基本算法 116
4.3.1 链栈的概念及数据类型 116
4.3.2 链栈的基本算法 117
4.3.3 链栈基本算法性能分析 118
4.4 堆栈的应用 118
4.4.1 数制转换问题 118
4.4.2 简单的文字编辑器问题 119
4.4.3 表达式计算问题 120
4.4.4 括号匹配问题 126
4.4.5 汉诺塔问题 128
4.4.6 火车车厢重排问题 132
4.4.7 开关盒布线问题 136
4.4.8 离线等价类问题 139
4.4.9 迷宫老鼠问题 142
小结 145
习题 146
第5章 队列及其应用 149
5.1 队列的基本概念 149
5.1.1 队列的定义 149
5.1.2 队列的逻辑结构 150
5.1.3 队列的基本算法 150
5.2 顺序队列及其基本算法 150
5.2.1 顺序队列的概念及数据类型 150
5.2.2 顺序循环队列 151
5.2.3 循环队列基本算法 153
5.2.4 循环队列基本算法性能分析 154
5.3 链队列及其基本算法 155
5.3.1 链队列的概念及数据类型 155
5.3.2 链队列基本算法 156
5.3.3 链队列基本算法性能分析 157
5.4 基数排序问题 157
5.4.1 多关键字排序问题 158
5.4.2 链式基数排序算法思想 158
5.4.3 链式基数排序算法实现的技术要点 160
5.4.4 链表基数排序算法及其性能分析 160
5.5 火车车厢重排问题 162
5.5.1 问题分析及算法思想 162
5.5.2 火车车厢重排算法设计 162
5.5.3 火车车厢重排算法及其性能分析 163
5.6 电路布线问题 165
5.6.1 电路布线问题分析 165
5.6.2 电路布线问题算法思想 165
5.6.3 电路布线问题算法设计 166
5.6.4 电路布线问题算法及其性能分析 166
5.7 识别图元问题 168
5.7.1 识别图元问题分析 168
5.7.2 识别图元算法设计 168
5.7.3 识别图元算法及其分析 169
5.8 工厂仿真问题 170
5.8.1 工厂仿真问题分析 170
5.8.2 工厂仿真问题算法设计 171
5.8.3 工厂仿真问题算法及其性能分析 173
小结 174
习题 174
第6章 特殊矩阵、广义表及其应用 178
6.1 数组与矩阵 178
6.1.1 数组与矩阵的概念及其相互关系 178
6.1.2 数组的存储结构 179
6.2 特殊矩阵的压缩存储 180
6.2.1 对称矩阵及其存储结构 181
6.2.2 三角矩阵及其存储结构 181
6.2.3 对角矩阵及其存储结构 182
6.2.4 稀疏矩阵及其存储结构和建表算法 183
6.3 矩阵的应用实例 187
6.3.1 稀疏矩阵的转置问题 187
6.3.2 稀疏矩阵的加法运算问题 189
6.4 广义表 193
6.4.1 广义表的概念 193
6.4.2 广义表的存储结构 194
6.4.3 广义表的应用——m元多项式的表示 196
小结 198
习题 198
第7章 二叉树及其应用 201
7.1 二叉树的基本概念 201
7.1.1 二叉树的定义 201
7.1.2 二叉树的基本术语 202
7.1.3 两种特殊的二叉树 202
7.1.4 二叉树的性质 203
7.2 二叉树的存储结构 205
7.2.1 二叉树的顺序存储结构 205
7.2.2 二叉树的链接存储结构 205
7.2.3 建立二叉树的算法 206
7.3 二叉树的遍历算法 208
7.3.1 二叉树遍历的概念 208
7.3.2 二叉树遍历递归算法 209
7.3.3 二叉树先序遍历非递归算法 211
7.3.4 二叉树中序遍历非递归算法 212
7.3.5 二叉树后序遍历非递归算法 213
7.4 线索二叉树 214
7.4.1 线索二叉树的概念 214
7.4.2 二叉树的线索化 215
7.4.3 线索二叉树的查找算法 216
7.5 二叉树的应用1——基本算法 217
7.6 二叉树的应用2——哈夫曼树 220
7.6.1 基本概念 220
7.6.2 哈夫曼树 221
7.6.3 哈夫曼树的构造过程 221
7.6.4 哈夫曼树的存储结构及哈夫曼算法 222
7.6.5 哈夫曼算法 223
7.6.6 哈夫曼树的应用——哈夫曼编码 223
7.7 二叉树的应用3——二叉排序树 225
7.7.1 二叉排序树及其性质 225
7.7.2 二叉排序树的存储结构 226
7.7.3 二叉排序树的结点查找算法 226
7.7.4 二叉排序树的结点插入算法 227
7.7.5 二叉排序树的生成算法 228
7.7.6 二叉排序树的结点删除算法 229
7.7.7 二叉排序树结点查找算法性能分析 231
7.7.8 平衡二叉排序树 232
7.8 二叉树的应用4——堆和堆排序 239
7.8.1 堆和堆排序的概念 239
7.8.2 堆的调整算法 240
7.8.3 建堆 242
7.8.4 堆排序算法及性能分析 243
小结 244
习题 244
第8章 树和森林及其应用 253
8.1 树和森林的基本概念 253
8.1.1 树和森林的定义 253
8.1.2 树的性质 254
8.1.3 树和森林的遍历 255
8.1.4 树、森林与二叉树的关系 256
8.2 树的存储结构 258
8.2.1 树的顺序存储结构 258
8.2.2 树的链接存储结构 259
8.3 树的基本算法及性能分析 261
8.3.1 树转换为二叉树算法及性能分析 261
8.3.2 森林转换为二叉树算法及性能分析 262
8.3.3 二叉树转换为树算法及性能分析 263
8.3.4 二叉树转换为森林算法及性能分析 265
8.3.5 树的遍历算法 265
8.3.6 森林的遍历算法 266
8.4 树的应用——B树 267
8.4.1 B树的概念 267
8.4.2 B树的数据存储类型 267
8.4.3 B树的查找算法 268
8.4.4 B树的插入算法 270
8.4.5 B树的删除算法及实例 275
小结 278
习题 278
第9章 散列结构及其应用 282
9.1 散列结构的基本概念 282
9.1.1 散列结构的概念 282
9.1.2 散列存储结构——散列表 283
9.1.3 散列函数 284
9.1.4 冲突处理方法——开放定址法 287
9.1.5 冲突处理方法——链地址法 289
9.2 线性探测散列算法 290
9.2.1 线性探测散列算法的数据类型 290
9.2.2 线性探测散列基本算法 290
9.3 链地址法散列算法 293
9.3.1 链地址散列算法的数据类型 293
9.3.2 链地址散列基本算法 294
9.4 散列结构的查找性能分析 295
9.5 散列结构应用1——LZW压缩问题 296
9.5.1 LZW压缩问题 296
9.5.2 LZW压缩算法及其算法性能分析 297
9.5.3 LZW解压缩问题 298
9.5.4 LZW解压缩算法及其算法性能分析 299
9.6 散列结构应用2——直接存取文件 300
9.6.1 基本概念 300
9.6.2 直接存取文件的存储结构及类型 301
9.6.3 文件操作1——查找结点算法 301
9.6.4 文件操作2——增加结点算法 302
9.6.5 文件操作3——删除结点算法 303
小结 304
习题 304
第10章 图及其应用 307
10.1 图的概念 307
10.1.1 图的定义 307
10.1.2 图的基础知识 308
10.1.3 图的基本运算 311
10.2 图的存储结构及其基本算法 312
10.2.1 邻接矩阵及其数据类型 312
10.2.2 邻接矩阵的基本算法 314
10.2.3 邻接表及其数据类型 315
10.2.4 邻接表的基本算法 317
10.2.5 逆邻接表 318
10.2.6 十字链表及其数据类型 319
10.2.7 十字链表的基本算法 320
10.2.8 邻接多重表及其数据类型 321
10.2.9 邻接多重表的基本算法 322
10.3 图的遍历及算法 323
10.3.1 深度优先搜索遍历 324
10.3.2 深度优先搜索遍历算法 324
10.3.3 广度优先搜索遍历 325
10.3.4 广度优先搜索遍历算法 326
10.4 有向图的连通性和最小生成树 327
10.4.1 有向图的连通性分析 327
10.4.2 连通网的最小生成树问题——通信网络问题 328
10.5 图的（最小）生成树问题 328
10.5.1 图的生成树 328
10.5.2 最小生成树算法——普利姆算法 329
10.5.3 最小生成树算法——克鲁斯卡尔算法 331
10.6 非连通图的生成森林算法 332
10.7 最短路径 335
10.7.1 最短路径问题 335
10.7.2 从某源点到其余各项点之间的最短路径问题——迪杰斯特拉算法 336
10.7.3 每一对顶点之间的最短路径问题——弗洛伊德算法 338
10.8 有向无环图及其应用 340
10.8.1 有向无环图及其应用问题实例 340
10.8.2 AOV网及其特性 342
10.8.3 拓扑排序及其算法 343
10.8.4 AOE网 345
10.8.5 关键路径及有关概念 345
10.8.6 关键路径求解及其算法思想 346
10.8.7 AOE网关键路径求解算法的数据类型 347
10.8.8 AOE网中求解关键路径的算法 347
10.8.9 关键路径求解算法分析 349
小结 350
习题 351
第11章 算法性能分析和算法设计方法简介 357
11.1 算法和程序 357
11.1.1 算法与程序分析 357
11.1.2 空间复杂性分析 358
11.1.3 时间复杂度分析 359
11.2 再谈算法性能问题 360
11.2.1 时间复杂度的上限值 361
11.2.2 定理11.2的证明 361
11.2.3 时间复杂度的下限值 362
11.2.4 有关渐进符号的计算 362
11.3 算法性能测量问题 363
11.3.1 算法性能测量问题分析 363
11.3.2 算法性能测量实例 363
11.4 算法设计方法简介 364
11.4.1 分而治之算法设计方法 365
11.4.2 最优化问题简介 365
11.4.3 贪婪算法设计方法 366
11.4.4 回溯算法设计方法 368
11.5 NP问题简介 369
11.6 散列表查找性能 370
11.7 讨论题 371
附录A 本书算法源程序 373
参考文献 414