第1章 概述 1
1.1基本概念 1
1.1.1数据结构的概念 1
1.1.2抽象数据类型 3
1.1.3算法的概念 5
习题1.1 6
1.2算法的描述和评价 6
1.2.1算法的描述 6
1.2.2算法的评价标准和评价方法 11
1.2.3计算时间复杂性的一般方法 15
习题1.2 17
内容小结 19
综合习题 20
第2章 表结构 21
2.1基本概念和顺序表 21
2.1.1基本概念 21
2.1.2顺序表的插入和删除 28
2.1.3顺序表的查找 30
习题2.1 34
2.2链表 38
2.2.1基本概念和链表种类 38
2.2.2链表的构造 45
2.2.3链表的遍历 48
2.2.4链表的插入和删除 50
2.2.5静态链表 56
习题2.2 63
2.3栈和队 72
2.3.1基本概念 72
2.3.2进栈和退栈算法 75
2.3.3进队和出队算法 78
2.3.4应用举例 82
习题2.3 85
2.4矩阵和字符串 90
2.4.1矩阵的基本概念和存储方法 90
2.4.2稀疏矩阵运算示例 94
2.4.3字符串的基本概念和简单匹配算法 99
2.4.4.其他匹配算法 102
习题2.4 111
2.5散列表 113
2.5.1散列函数 113
2.5.2散列表的处理算法 117
2.5.3散列表的性能分析 120
习题2.5 122
2.6广义表 124
习题2.6 126
2.7表结构的类实现示例 126
习题2.7 135
内容小结 137
综合习题 139
第3章 树结构 144
3.1基本概念和存储方法 144
3.1.1普通树的基本概念 144
3.1.2二叉树的基本概念 148
3.1.3普通树与二叉树的相互转换 152
3.1.4树的存储方法 154
习题3.1 157
3.2二叉树的遍历和构造 160
3.2.1二叉树的遍历 160
3.2.2遍历序列的前驱和后继 164
3.2.3遍历的应用示例 165
3.2.4二叉树的构造 169
3.2.5非递归的遍历算法 172
习题3.2 175
3.3检索树 183
3.3.1检索树的查找 183
3.3.2检索树的插入和构造 184
3.3.3检索树的删除 186
3.3.4最优检索树 190
习题3.3 195
3.4平衡树 196
3.4.1 AVL树 196
3.4.2红黑树 203
习题3.4 212
3.5B树和Trie树 213
3.5.1B树 213
3.5.2B＋树 216
3.5.3 Trie树 221
习题3.5 222
3.6几个实用树结构 222
3.6.1哈夫曼树 222
3.6.2判定树 226
3.6.3 union-find树 229
习题3.6 233
3.7树结构的类实现示例 234
习题3.7 239
内容小结 239
综合习题 241
第4章 图结构 246
4.1基本概念和存储方法 246
4.1.1图的定义和有关术语 246
4.1.2图的存储方法 250
习题4.1 256
4.2图的遍历和应用示例 259
4.2.1先深搜索 259
4.2.2先广搜索 266
4.2.3无向图的关节点 268
习题4.2 273
4.3最小生成树和最短路径 276
4.3.1 Kruskal算法 276
4.3.2 Prim算法 281
4.3.3 Dijkstra算法 284
4.3.4 Floyd算法 288
习题4.3 290
4.4有向无回路图 292
4.4.1基本概念 292
4.4.2拓扑排序 294
4.4.3关键路径 297
习题4.4 301
4.5图结构的类实现示例 302
习题4.5 305
内容小结 305
综合习题 306
第5章 排序 308
5.1基本概念 309
习题5.1 310
5.2插入排序 310
5.2.1直接插入排序 310
5.2.2二分插入排序 313
5.2.3希尔排序 314
习题5.2 318
5.3交换排序 319
5.3.1冒泡排序 319
5.3.2快速排序 322
习题5.3 327
5.4选择排序 330
5.4.1一般原理和效率分析 330
5.4.2树选排序 331
5.4.3堆排序 332
习题5.4 338
5.5合并排序 340
5.5.1递归的合并排序 340
5.5.2非递归的合并排序 342
习题5.5 345
5.6基数排序 346
5.6.1基本原理和示例 346
5.6.2算法的实现和分析 349
习题5.6 352
5.7外部排序 354
5.7.1文件的组织结构 354
5.7.2顺串的合并 358
5.7.3初始顺串的生成 367
5.7.4最佳合并树 369
5.7.5磁带排序 371
习题5.7 373
内容小结 374
综合习题 375
第6章 问题的固有难度和算法设计的一般方法简介 377
6.1问题的固有难度和分类 377
6.1.1算法的重要地位 377
6.1.2问题的固有难度 379
6.1.3不确定性算法 381
6.1.4三大重要的问题类 383
习题6.1 385
6.2算法设计的一般方法 386
6.2.1集合运算的数据结构选取 386
6.2.2递归、分治和平衡 388
6.2.3贪心法 394
6.2.4动态规划法 396
6.2.5搜索-回溯法 399
习题6.2 402
内容小结 403
综合习题 404
参考文献 405