第1章 概论 1
1.1引子 1
1.2数据结构 6
1.2.1定义 6
1.2.2抽象数据类型 7
1.3算法 8
1.3.1定义 8
1.3.2算法复杂度 9
1.3.3渐近表示法 10
1.4应用实例：最大子列和问题 14
本章小结 19
习题 20
第2章 数据结构实现基础 21
2.1引子 21
2.2数据存储基础 24
2.2.1数组 24
2.2.2指针 25
2.2.3结构 27
2.2.4链表 29
2.2.5类型定义typedef 33
2.3流程控制基础 34
2.3.1分支控制 34
2.3.2循环控制 36
2.3.3函数与递归 38
本章小结 47
习题 47
第3章 线性结构 49
3.1引子 49
3.2线性表的定义与实现 52
3.2.1线性表的定义 52
3.2.2线性表的顺序存储实现 53
3.2.3线性表的链式存储实现 56
3.2.4广义表与多重链表 61
3.3堆栈 65
3.3.1堆栈的定义 65
3.3.2堆栈的实现 68
3.3.3堆栈应用：表达式求值 72
3.4队列 75
3.4.1队列的定义 75
3.4.2队列的实现 76
3.5应用实例 80
3.5.1多项式加法运算 80
3.5.2迷宫问题 82
本章小结 87
习题 87
第4章树 89
4.1引子 89
4.1.1问题的提出 89
4.1.2查找 90
4.2树的定义、表示和术语 95
4.3二叉树 97
4.3.1二叉树的定义及其逻辑表示 97
4.3.2二叉树的性质 98
4.3.3二叉树的存储结构 99
4.3.4二叉树的操作 101
4.4二叉搜索树 117
4.4.1二叉搜索树的定义 117
4.4.2二叉搜索树的动态查找 117
4.4.3二叉搜索树的插入 120
4.4.4二叉搜索树的删除 121
4.5平衡二叉树 125
4.5.1平衡二叉树的定义 126
4.5.2平衡二叉树的调整 127
4.6树的应用 133
4.6.1堆及其操作 133
4.6.2哈夫曼树 142
4.6.3集合及其运算 150
本章小结 153
习题 154
第5章 散列查找 156
5.1引子 156
5.2基本概念 160
5.3散列函数的构造方法 162
5.3.1数字关键字的散列函数构造 163
5.3.2字符串关键字的散列函数构造 165
5.4处理冲突的方法 167
5.4.1开放定址法 167
5.4.2分离链接法 174
5.5散列表的性能分析 180
5.6应用实例 182
本章小结 187
习题 188
第6章图 190
6.1引子 190
6.2图的基本概念 191
6.2.1图的定义和术语 191
6.2.2图的抽象数据类型 197
6.3图的存储结构 198
6.3.1邻接矩阵 199
6.3.2邻接表 202
6.4图的遍历 205
6.4.1迷宫探索 205
6.4.2深度优先搜索 209
6.4.3广度优先搜索 211
6.5最小生成树 213
6.5.1生成树的构建与最小生成树的概念 214
6.5.2构造最小生成树的Prim算法 216
6.5.3构造最小生成树的Kruskal算法 221
6.6最短路径 225
6.6.1单源最短路径 226
6.6.2每一对顶点之间的最短路径 230
6.7拓扑排序 234
6.8关键路径计算 238
6.9应用实例 241
6.9.1六度空间理论 241
6.9.2六度空间理论的验证 243
本章小结 245
习题 247
第7章 排序 251
7.1引子 251
7.2选择排序 252
7.2.1简单选择排序 252
7.2.2堆排序 253
7.3插入排序 256
7.3.1简单插入排序 256
7.3.2希尔排序 257
7.4交换排序 259
7.4.1冒泡排序 259
7.4.2快速排序 260
7.5归并排序 263
7.6基数排序 266
7.6.1桶排序 266
7.6.2基数排序 267
7.6.3单关键字的基数分解 267
7.7外部排序 270
7.8排序的比较和应用 271
7.8.1排序算法的比较 271
7.8.2排序算法应用案例 273
本章小结 274
习题 274
第8章 综合应用案例分析 276
8.1银行排队问题 276
8.1.1单队列多窗口服务 276
8.1.2单队列多窗口+VIP服务 282
8.2畅通工程问题 287
8.2.1建设道路数量问题 287
8.2.2最低成本建设问题 290
本章小结 294
习题 294
参考文献 295