第一章绪论 1
1.1为什么要学习数据结构 1
1.2数据结构概念 2
1.2.1数据的逻辑结构 3
1.2.2数据的存储结构 4
1.2.3对数据结构的操作 6
1.2.4数据结构示例 6
1.3算法 6
1.3.1算法及其特性 6
1.3.2算法的描述 7
1.3.3算法的评价准则 9
1.4算法的正确性证明 10
1.5算法分析基础 13
1.5.1算法时间复杂性的分析方法 13
1.5.2复杂性函数的渐近表示 16
1.5.3算法时间与空间分析 18
1.5.4计算复杂性和算法的效率 19
小结 20
参考文献与推荐读物 21
习题 22
第二章线性表、堆栈和队列 24
2.1线性表的定义和基本操作 24
2.2线性表的顺序存储结构 24
2.3线性表的链接存储结构 27
2.3.1单链表 27
2.3.2循环链表 32
2.3.3双向链表 33
2.4复杂性分析 36
2.5堆栈 36
2.5.1堆栈的定义和基本操作 36
2.5.2顺序栈 37
2.5.3链式栈 39
2.5.4顺序栈与链式栈的比较 40
2.5.5堆栈应用——括号匹配 41
2.6队列 42
2.6.1队列的定义和基本操作 42
2.6.2顺序队列 43
2.6.3链式队列 45
2.6.4顺序队列与链式队列的比较 47
2.6.5 队列与堆栈的扩展 47
小结 48
参考文献与推荐读物 48
习题 49
第三章数组和字符串 52
3.1数组 52
3.1.1数组的存储和寻址 52
3.1.2一维数组类 54
3.2矩阵 55
3.2.1矩阵类 55
3.2.2特殊矩阵 57
3.2.3三元组表 59
3.2.4十字链表 61
3.3字符串 64
3.3.1字符串的定义与字符串类 64
3.3.2模式匹配算法 67
小结 71
参考文献与推荐读物 72
习题 73
第四章树 76
4.1树的基本概念 76
1.1.1树的定义 76
4.1.2树的相关术语 77
4.2二叉树 79
4.2.1二叉树定义和主要性质 79
4.2.2二叉树顺序存储 83
4.2.3二叉树链接存储 84
4.2.4二叉树遍历 86
4.2.5创建二叉树 92
4.2.6复制二叉树 93
4.3线索二叉树 94
4.3.1线索二叉树定义 94
4.3.2线索二叉树存储 95
4.3.3线索二叉树基本算法 97
4.4树和森林 104
4.4.1树与二叉树的转换 104
4.4.2树的顺序存储 108
4.4.3树的链接存储 110
4.4.4树和森林的遍历 115
4.5压缩与哈夫曼树 117
4.5.1文件编码 117
4.5.2扩充二叉树 118
4.5.3哈夫曼树和哈夫曼编码 119
4.6应用 122
4.6.1表达式求值 122
4.6.2分类与决策树 124
小结 128
参考文献与推荐读物 128
习题 129
第五章图 131
5.1图的基本概念 132
5.2图的存储结构与类定义 134
5.2.1存储结构 134
5.2.2Graph类 137
5.3图的遍历算法 140
5.3.1深度优先遍历 140
5.3.2广度优先遍历 142
5.5.4拓扑排序 143
5.5关键路径 147
5.6最短路径问题 152
5.6.1无权最短路径问题 153
5.6.2正权最短路径问题 154
5.6.3每对顶点之间的最短路径 158
5.7最小支撑树 160
5.7.1普里姆算法 161
5.7.2克鲁斯卡尔算法 164
5.8图的应用 165
5.8.1可及性与Warshall算法 165
5.8.2连通分量 166
5.8.3图在网络分析和信息检索中的应用 167
小结 171
参考文献与推荐读物 172
习题 173
第六章递归 177
6.1递归的定义 177
6.2基本递归过程 180
6.3递归过程实现与堆栈 182
6.4递归法求解问题 186
6.4.1委员会问题 186
6.4.2回溯 188
6.5递归的效率 191
小结 193
参考文献与推荐读物 194
习题 194
第七章排序 198
7.1排序问题的基本概念 198
7.2插入排序 200
7.2.1直接插入排序 200
7.2.2Shell排序 202
7.3交换排序 204
7.3.1冒泡排序 204
7.3.2快速排序 207
7.4选择排序 215
7.4.1直接选择排序 215
7.4.2堆排序 215
7.5合并排序 220
7.6基于关键词比较的排序算法分析 223
7.6.1平方阶排序算法及改进算法 223
7.6.2线性对数阶排序算法 223
7.6.3分治排序的一般方法 225
7.6.4基于关键词比较的排序算法下界 226
7.7分布排序 227
7.7.1基数分布 228
7.7.2值分布 230
7.8外排序 231
7.8.1外存储器 231
7.8.2磁带排序 232
7.8.3磁盘排序 241
小结 245
参考文献与推荐读物 246
习题 247
第八章查找 253
8.1顺序查找 254
8.1.1无序表的顺序查找 254
8.1.2有序表的顺序查找 256
8.2基于关键词比较的查找 256
8.2.1对半查找 257
8.2.2.致对半查找 260
8.2.3斐波那契查找 263
8.2.4插值查找 266
8.3二叉查找树 268
8.3.1基本概念和性质 268
8.3.2查找、插入和删除 269
8.3.3平均情况时间分析 273
8.4最优二叉查找树 274
8.4.1访问频率 274
8.4.2最优二叉查找树 275
8.4.3近似最优树的构造 281
8.5平衡树 284
8.5.1高度平衡树 285
8.5.2重量平衡树 294
8.6红黑树 300
8.6.1红黑树的性质 300
8.6.2旋转 301
8.6.3插入 303
8.6.4删除 306
8.7B树及其变形树 311
8.7.1多叉树 311
8.7.2 B树 312
8.7.3 B树变形树 318
8.8数字查找 323
8.8.1检索结构查找 323
8.8.2数字树查找 330
8.9散列 332
8.9.1散列函数 333
8.9.2冲突调节 337
8.9.3删除 346
8.9.4重量平衡树的应用——按位置查找 347
小结 347
参考文献与推荐读物 349
习题 353
第九章 内存管理 357
9.1概述 357
9.2均匀大小记录的分配和回收算法 359
9.2.1记录分配算法 359
9.2.2访问计数器法 360
9.2.3 废料收集方法 362
9.3不同大小记录的分配和回收算法 367
9.3.1查找分配策略 368
9.3.2边界标识法 371
9.3.3压缩分配 374
9.4伙伴系统 376
9.4.1伙伴系统概述 376
9.4.2分配记录和释放记录算法 379
小结 381
参考文献与推荐读物 383
习题 385
第十章 文件 388
10.1文件的基本概念 388
10.1.1文件及其分类 388
10.1.2文件的逻辑结构与存储结构 390
10.2顺序文件 391
10.2.1顺序无序文件 393
10.2.2顺序有序文件 396
10.2.3增补文件 397
10.3散列文件 398
10.3.1散列文件 398
10.3.2可扩充的散列文件 399
10.4索引文件 403
10.4.1动态索引结构和静态索引结构 404
10.4.2ISAM文件 405
10.4.3VSAM文件 409
10.5多关键字文件 412
10.5.1多重链表文件 413
10.5.2倒排文件 416
小结 416
参考文献与推荐读物 417
习题 417
第十一章随机数 419
11.1生成随机数 419
11.1.1均匀分布随机数 420
11.1.2其他分布随机数 427
11.2随机数检验 429
11.2.1.般检验方法 430
11.2.2经验检验方法 434
11.3随机排列与随机组合 436
11.3.1随机排列 436
11.3.2随机组合 437
11.4应用 439
11.4.1随机算法 439
11.1.2使用随机数的快速排序算法 441
小结 441
参考文献与推荐读物 441
习题 442
附录 444
附录1各章算法的C++实现 444
附录2习题参考答案或解题思路 579