第1章 概论 1
1.1 引子 1
1.2 数据结构 7
1.2.1 定义 7
1.2.2 抽象数据类型 8
1.3 算法 9
1.3.1 定义 9
1.3.2 算法复杂度 10
1.3.3 渐进表示法 12
1.4 应用实例：最大子列和问题 15
本章小结 21
习题 21
第2章 数据结构实现基础 23
2.1 引子 23
2.2 数据存储基础 26
2.2.1 数组 26
2.2.2 类型定义typedef 28
2.2.3 指针 28
2.2.4 结构 30
2.2.5 链表 32
2.3 流程控制基础 37
2.3.1 分支控制 37
2.3.2 循环控制 39
2.3.3 函数与递归 42
本章小结 50
习题 50
第3章 线性结构 52
3.1 引子 52
3.2 线性表的定义与实现 55
3.2.1 线性表的定义 55
3.2.2 线性表的顺序存储实现 56
3.2.3 线性表的链式存储实现 60
3.2.4 广义表与多重链表 66
3.3 堆栈 70
3.3.1 堆栈的定义 70
3.3.2 堆栈的实现 73
3.3.3 堆栈应用：表达式求值 78
3.4 队列 83
3.4.1 队列的定义 83
3.4.2 队列的实现 83
3.5 应用实例 88
3.5.1 多项式加法运算 88
3.5.2 迷宫问题 90
本章小结 95
习题 96
第4章 树 98
4.1 引子 98
4.1.1 问题的提出 98
4.1.2 查找 99
4.2 树的定义、表示和术语 103
4.3 二叉树 106
4.3.1 二叉树的定义及其逻辑表示 106
4.3.2 二叉树的性质 106
4.3.3 二叉树的存储结构 107
4.3.4 二叉树的操作 110
4.4 二叉搜索树 125
4.4.1 二叉搜索树的定义 125
4.4.2 二叉搜索树的动态查找 126
4.4.3 二叉搜索树的插入 128
4.4.4 二叉搜索树的删除 130
4.5 平衡二叉树 133
4.5.1 平衡二叉树的定义 134
4.5.2 平衡二叉树的调整 134
4.6 树的应用 141
4.6.1 堆及其操作 141
4.6.2 哈夫曼树 151
4.6.3 集合及其运算 159
本章小结 163
习题 164
第5章 散列查找 166
5.1 引子 166
5.2 基本概念 169
5.3 散列函数的构造方法 172
5.3.1 数字关键词的散列函数构造 172
5.3.2 字符串关键词的散列函数构造 175
5.4 处理冲突的方法 176
5.4.1 开放定址法 176
5.4.2 分离链接法 183
5.5 散列表的性能分析 188
5.6 应用实例 189
本章小结 195
习题 196
第6章 图 198
6.1 引子 198
6.2 图的基本概念 199
6.2.1 图的定义和术语 199
6.2.2 图的抽象数据类型 205
6.3 图的存储结构 205
6.3.1 邻接矩阵 206
6.3.2 邻接表 210
6.4 图的遍历 215
6.4.1 迷宫探索 215
6.4.2 深度优先搜索 218
6.4.3 广度优先搜索 220
6.5 最小生成树 223
6.5.1 生成树的构建与最小生成树的概念 223
6.5.2 构造最小生成树的Prim算法 225
6.5.3 构造最小生成树的Kruskal算法 232
6.6 最短路径 235
6.6.1 单源最短路径 236
6.6.2 每一对顶点之间的最短路径 241
6.7 拓扑排序 244
6.8 关键路径计算 249
6.9 应用实例 252
6.9.1 六度空间理论 252
6.9.2 六度分隔理论的验证 253
本章小结 257
习题 258
第7章 排序 263
7.1 引子 263
7.2 选择排序 264
7.2.1 简单选择排序 264
7.2.2 堆排序 265
7.3 插入排序 268
7.3.1 简单插入排序 268
7.3.2 希尔排序 269
7.4 交换排序 271
7.4.1 冒泡排序 271
7.4.2 快速排序 272
7.5 归并排序 276
7.6 基数排序 279
7.6.1 桶排序 279
7.6.2 基数排序 279
7.6.3 单关键字的基数分解 280
7.7 外部排序 284
7.8 排序的比较和应用 285
7.8.1 排序算法的比较 285
7.8.2 排序算法应用案例 287
本章小结 288
习题 288
第8章 综合应用案例分析 290
8.1 银行排队问题 290
8.1.1 单队列多窗口服务 290
8.1.2 单队列多窗口＋VIP服务 296
8.2 畅通工程问题 301
8.2.1 建设道路数量问题 301
8.2.2 最低成本建设问题 304
本章小结 309
习题 309
附录 PTA使用说明 310
参考文献 315