第1章 引论 1
1.1算法及其复杂性的概念 1
算法与程序 1
算法复杂性的概念 2
算法复杂性的渐近性态 3
1.2算法的表达与数据表示 5
问题求解 5
表达算法的抽象机制 5
1.3抽象数据类型 8
抽象数据类型的基本概念 8
使用抽象数据类型的好处 10
1.4数据结构、数据类型和抽象数据类型 10
1.5用C语言描述数据结构与算法 11
变量和指针 11
函数与参数传递 12
结构 13
动态存储分配 14
本章小结 16
习题 16
第2章 表 18
2.1 ADT表 18
2.2用数组实现表 19
2.3用指针实现表 24
2.4用间接寻址方法实现表 28
2.5用游标实现表 31
2.6循环链表 37
2.7双链表 40
2.8表的搜索游标 44
用数组实现表的搜索游标 45
单循环链表的搜索游标 46
2.9应用 48
本章小结 49
习题 49
第3章 栈 52
3.1 ADT栈 52
3.2用数组实现栈 53
3.3用指针实现栈 56
3.4应用 58
本章小结 61
习题 61
第4章 队列 63
4.1 ADT队列 63
4.2用指针实现队列 64
4.3用循环数组实现队列 67
4.4应用 71
本章小结 75
习题 75
第5章 递归 77
5.1递归的概念 77
5.2递归程序设计 83
分治与递归 83
动态规划 84
回溯与递归 91
5.3模拟递归 93
5.4应用 96
本章小结 99
习题 99
第6章 排序与选择 101
6.1简单排序算法 101
冒泡排序 102
插入排序 103
选择排序 103
简单排序算法的计算复杂性 104
6.2快速排序算法 105
算法基本思想及实现 105
算法的性能 106
随机快速排序算法 107
非递归快速排序算法 107
三数取中划分算法 109
三划分快速排序算法 110
6.3合并排序算法 111
算法基本思想及实现 111
对基本算法的改进 112
自底向上的合并排序算法 113
自然合并排序 113
链表结构的合并排序算法 114
6.4线性时间排序算法 115
计数排序 116
桶排序 117
6.5中位数与第k小元素 118
平均情况下的线性时间选择算法 118
最坏情况下的线性时间选择算法 119
6.6应用 121
本章小结 123
习题 123
第7章 树 125
7.1树的定义 125
7.2树的遍历 127
7.3树的表示法 129
父结点数组表示法 129
儿子链表表示法 130
左儿子右兄弟表示法 130
7.4二叉树 131
7.5 ADT二叉树 133
7.6二叉树的实现 133
二叉树的顺序存储结构 133
二叉树的结点度表示法 135
用指针实现二叉树 135
7.7线索二叉树 140
7.8应用 142
本章小结 146
习题 146
第8章 集合 148
8.1以集合为基础的抽象数据类型 148
集合的定义和记号 148
定义在集合上的基本运算 149
8.2用位向量实现集合 150
8.3用链表实现集合 153
8.4应用 157
本章小结 158
习题 158
第9章 符号表 160
9.1实现符号表的简单方法 160
9.2用散列表实现符号表 162
开散列 162
闭散列 164
散列函数及其效率 169
闭散列的重新散列技术 170
9.3应用 170
本章小结 172
习题 172
第10章 字典 174
10.1字典的定义 174
10.2用数组实现字典 175
10.3用二叉搜索树实现字典 175
10.4 AVL树 183
AVL树的定义和性质 184
旋转变换 185
AVL树的插入运算 188
AVL树的删除运算 191
10.5应用 194
本章小结 196
习题 196
第11章 优先队列 198
11.1优先队列的定义 198
11.2用字典实现优先队列 199
11.3优先级树和堆 199
11.4用数组实现堆 201
11.5可并优先队列 204
左偏树的定义 204
用左偏树实现可并优先队列 205
11.6应用 209
本章小结 213
习题 213
第12章 并查集 215
12.1并查集的定义及其简单实现 215
12.2用父亲数组实现并查集 217
12.3应用 220
本章小结 222
习题 222
第13章图 224
13.1图的基本概念 224
13.2抽象数据类型ADT图 227
13.3图的表示法 228
邻接矩阵表示法 228
邻接表表示法 229
紧缩邻接表 229
13.4用邻接矩阵实现图 230
用邻接矩阵实现赋权有向图 230
用邻接矩阵实现赋权无向图 233
用邻接矩阵实现有向图 233
用邻接矩阵实现无向图 234
13.5用邻接表实现图 235
用邻接表实现有向图 235
用邻接表实现无向图 238
用邻接表实现赋权有向图 239
用邻接表实现赋权无向图 243
13.6图的遍历 244
广度优先搜索 244
深度优先搜索 246
13.7最短路径 248
单源最短路径 248
所有顶点对之间的最短路径 251
13.8最小支撑树 253
最小支撑树性质 253
Prim算法 253
Kruskal算法 256
13.9图匹配 258
本章小结 260
习题 260
参考文献 263