第一章 绪论 1
1.1 数据结构概念 1
1.2 面向对象程序设计OOP与抽象数据类型ADT 3
1.3 算法概念和算法描述语言 5
第二章 算法分析基础 9
2.1 引论 9
2.2 算法时间复杂性的分析方法 11
2.3 时间与空间分析 15
习题 16
第三章 面向对象程序设计与C++语言 18
3.1 类和对象 18
3.1.1 类声明 18
3.1.2 类实现 19
3.1.3 对象声明 20
3.2 C++语言的基本操作 21
3.2.1 输入输出的C++实现 21
3.2.2 友元函数(friend function) 23
3.2.3 参数传递 24
3.2.4 多态性 25
3.2.5 动态存储分配 28
3.3 模板 29
3.3.1 模板函数 29
3.3.2 模板类 31
3.4 继承 32
习题 34
第四章 线性表、堆栈、队列 35
4.1 线性表的定义和基本操作 35
4.2 线性表的存储结构 36
4.2.1 顺序存储结构 36
4.2.2 链接存储结构--单链表 36
4.2.3 循环链表 47
4.2.4 双向循环链表 49
4.3 堆栈和队列 53
4.3.1 定义和主要操作 53
4.3.2 顺序存储 56
4.3.3 链接存储 63
4.3.4 应用--算术表达式求值 65
习题 68
第五章 数组、字符串和集合类 71
5.1 数组 71
5.1.1 顺序存储的数组 71
5.1.2 静态数组与动态数组 73
5.1.3 稀疏矩阵 77
5.2 字符串 84
5.2.1 定义和主要操作 84
5.2.2 存储方式 85
5.2.3 模式匹配算法 86
5.3 整型集合 90
习题 94
第六章 树 98
6.1 基本概念 98
6.2 二叉树 99
6.2.1 主要性质和定义 99
6.2.2 二叉树的实现 102
6.2.3 二叉树的遍历 108
6.2.4 复制二叉树 110
6.3 线索二叉树 111
6.4 树和森林 119
6.4.1 树的顺序存储结构 119
6.4.2 树的链接存储结构 121
6.4.3 森林与二叉树的转换 125
6.4.4 树和森林的遍历 126
6.5 压缩与哈夫曼树 131
习题 135
第七章 图 137
7.1 概念和定义 137
7.2 图的存储结构与类Graph 139
7.2.1 存储结构 139
7.2.2 Graph类 141
7.3 遍历函数的实现 153
7.3.1 深度优先遍历 153
7.3.2 广度优先遍历 155
7.4 拓扑排序 156
7.5 关键路径 159
7.6 最短路径问题 163
7.6.1 无权最短路径问题 163
7.6.2 正权最短路径问题 165
7.6.3 负权最短路径问题 168
7.6.4 每对顶点之间的最短路径 171
7.7 最小支撑树 173
7.8 应用 178
7.8.1 可及性与Warshall算法 178
7.8.2 连通分量 180
习题 182
第八章 递归 186
8.1 什么是递归 186
8.2 基本递归过程 188
8.3 递归过程的实现：堆栈与递归 191
8.4 递归到非递归的转换 196
8.5 递归的应用 203
8.5.1 应用实例1：算术表达式求值 203
8.5.2 应用实例2：回溯 205
习题 210
第九章 排序 211
9.1 插入排序 212
9.2 交换排序 217
9.2.1 冒泡排序 217
9.2.2 分划交换排序 222
9.3 选择排序 231
9.3.1 直接选择排序 231
9.3.2 堆排序 232
9.4 合并排序 238
9.5 排序下界 242
9.6 分布排序 243
9.6.1 基数分布 244
9.6.2 值分布 247
9.7 外排序 249
9.7.1 外存储器 249
9.7.2 磁带排序 250
9.7.3 磁盘排序 260
习题 266
第十章 查找 269
10.1 线性表查找 269
10.1.1 顺序查找 270
10.1.2 有序表的查找 271
10.2 二叉查找(搜索)树 278
10.2.1 定义和基本操作 278
10.2.2 静态树 281
10.2.3 动态树 289
10.3 数字查找树 320
10.4 杂凑 322
10.4.1 杂凑表的定义和主要操作 322
10.4.2 杂凑函数 323
10.4.3 冲突调节 326
10.5 (a,b)-树、B树和B’树 334
习题 341
第十一章 内存管理 344
11.1 均匀大小记录的管理和废料收集方法 344
11.1.1 访问计数器法 345
11.1.2 废料收集 346
11.2 不同大小记录的查找分配和压缩分配 350
11.2.1 查找分配 351
11.2.2 压缩分配 357
11.3 伙伴系统 362
11.4 C++中的动态内存分配 368
习题 369
第十二章 复杂数据结构 371
12.1 优先级队列 371
12.1.1 类声明 371
12.1.2 优先级队列的应用：长归并段 372
12.2 不相交集合类 378
12.2.1 等价关系 378
12.2.2 动态等价 379
12.2.3 快速查找算法 383
12.2.4 快速合并算法 384
12.2.5 C++实现 390
12.2.6 最坏情况下的归并和路径压缩 391
第十三章 文件 393
13.1 文件结构概论 393
13.2 顺序文件 396
13.2.1 串行处理文件 396
13.2.2 顺序处理文件 399
13.2.3 增补文件 400
13.3 杂凑(散列)文件 402
13.3.1 杂凑文件的设计 402
13.3.2 可扩充的杂凑文件 405
13.4 索引文件 410
13.4.1 动态索引结构和静态索引结构 414
13.4.2 索引顺序文件 414
13.4.3 B’索引文件 418
13.5 倒排文件和多重链表文件 422
习题 430
第十四章 应用 432
14.1 事件驱动模拟(Event-Driven Simulation) 432
14.1.1 模拟设计 432
14.1.2 模拟建立 436
14.1.3 运行模拟 437
14.2 在线等价类 443
14.2.1 树形描述 443
14.2.2 操作 444
14.2.3 性能评价 445
14.2.4 性能改进 445
14.3 残缺棋盘 451
14.4 图像压缩 454
参考文献 461