本书系统地介绍了一些常用算法及若干常用的数据结构, 这些常用的算法包括选择算法、查找算
法、排序算法; 详细地介绍了字符串匹配和图论中的一些经典算法, 数据结构的内容包括线性结构、
树形结构、哈希结构等; 还详细地分析了各种算法的时间复杂度, 对一些经典算法给出了平摊复杂度
分析.
本书可以作为高校计算机专业算法与数据结构课程的教材, 亦可以作为计算机工作者的参考书.
第1 章绪论1
第2 章算法分析6
2.1 无穷大的阶以及若干序列的渐进分析 6
2.2 基本定理10
2.3 时间复杂度与空间复杂度16
2.4 平均复杂度与平摊复杂度25
2.5 习题40
第3 章线性表49
3.1 向量49
3.2 单链表60
3.3 堆栈63
3.4 队列77
3.5 其他形式的链表87
3.6 习题90
第4 章二叉树、树与森林95
4.1 二叉树95
4.2 二叉树的遍历105
4.3 树与森林123
4.4 二叉树、树、森林等的存储表示法127
4.5 并查集及其应用132
4.6 习题. 141
第5 章选择144
5.1 小顶堆、大顶堆、双顶堆与d 叉堆145
5.2 置换选择152
5.3 左堆与斜堆154
5.4 二项式堆与Fibonacci 堆160
5.5 配对堆166
5.6 Hu.man 压缩168
5.7 习题172
第6 章查找175
6.1 顺序查找176
6.2 哈希表177
6.3 二分查找186
6.4 排序二叉树189
6.5 AVL 树与红黑树196
6.6 排序二叉树202
6.7 Splay 树205
6.8 B 树、数字查找树208
6.9 习题213
第7 章排序215
7.1 插入排序与Shell 排序216
7.2 选择排序与堆排序221
7.3 快速排序224
7.4 归并排序228
7.5 基数排序与计数排序237
7.6 磁盘文件排序. 239
7.7 习题243
第8 章图 244
8.1 图的定义与存储244
8.2 图的遍历及其应用248
8.3 有向无圈图255
8.4 无向图的小代价生成树.259
8.5 加权短路径262
8.6 二分图 270
8.7 流 275
8.8 小费用流279
8.9 习题285
第9 章模式匹配算法287
9.1 字符集与字符串287
9.2 单模式串匹配292
9.3 多模式串匹配305
9.4 带通配符的模式匹配312
9.5 正则表达式匹配314
9.6 近似匹配 316
9.7 习题322
参考文献323
索引324
精品教材 更多
