第1章 绪论 1
1.1 数据结构研究的内容和方法 1
1.1.1 数据结构的含义 1
1.1.2 数据结构研究的内容 2
1.1.3 研究数据结构的方法 6
1.2 抽象数据类型的表示与实现 7
1.3 学习数据结构的目的 8
1.3.1 数据结构的发展简史及在计算机科学中的地位 8
1.3.2 学习数据结构的目的 9
1.4 算法和算法分析 9
1.4.1 算法的定义 9
1.4.2 算法的性质 9
1.4.3 算法的设计目标 11
1.4.4 算法效率的度量 11
习题1 14
第2章 线性表 16
2.1 线性表的定义及其基本操作 16
2.1.1 线性表的定义 16
2.1.2 线性表的逻辑结构和特征 16
2.1.3 线性表的抽象数据类型表示 17
2.2 线性表的顺序存储结构 19
2.2.1 顺序表 20
2.2.2 顺序表上的基本操作 20
2.2.3 顺序存储结构的基本特点 23
2.3 线性表的链式存储结构 24
2.3.1 单链表 24
2.3.2 单链表中的基本操作 26
2.3.3 单向循环链表 31
2.3.4 双向链表 32
2.3.5 静态链表 34
2.3.6 链式存储结构的特点 37
2.4 线性表应用举例 38
2.4.1 Josephu问题 38
2.4.2 一元多项式的表示与相加 41
本章小结 45
习题2 45
第3章 栈与队列 47
3.1 栈 47
3.1.1 栈的定义及其操作 47
3.1.2 栈的顺序存储结构 49
3.1.3 栈的链式存储结构 51
3.2 栈应用举例 52
3.2.1 数制转换 53
3.2.2 行编辑处理 54
3.2.3 表达式求值 56
3.3 栈与递归函数 61
3.3.1 递归定义与递归函数 61
3.3.2 递归函数到非递归函数的转化 64
3.4 队列 66
3.4.1 队列的定义及其操作 66
3.4.2 队列的顺序存储结构 67
3.4.3 队列的链式存储结构 70
3.5 队列应用实例 72
3.5.1 迷宫问题 72
3.5.2 离散事件模拟 75
3.5.3 有序事件模拟 80
本章小结 82
习题3 83
第4章 串 84
4.1 串的定义及其操作 84
4.1.1 串的定义 84
4.1.2 串的抽象数据类型 85
4.2 串的存储结构 87
4.2.1 串的静态存储结构 87
4.2.2 串的动态存储结构 93
4.3 串模式匹配 98
4.4 串应用举例 101
4.4.1 文本编辑 101
4.4.2 建立词索引表 104
本章小结 106
习题4 106
第5章 数组和广义表 107
5.1 数组的定义及其操作 107
5.1.1 数组的定义 107
5.1.2 数组的抽象数据类型 108
5.2 数组的存储结构 109
5.2.1 数组的静态存储方式 109
5.2.2 数组的动态存储方式 112
5.3 矩阵的压缩存储 113
5.3.1 特殊矩阵的压缩存储 113
5.3.2 稀疏矩阵的压缩存储 116
5.4 广义表的定义及其操作 120
5.4.1 广义表的定义 120
5.4.2 广义表的抽象数据类型 121
5.5 广义表的存储结构 122
5.5.1 广义表的链式存储 122
5.5.2 广义表基本操作的递归算法 124
本章小结 127
习题5 127
第6章 树 129
6.1 树的基本概念 129
6.1.1 树的定义及基本操作 130
6.1.2 树的性质 133
6.2 二叉树 135
6.2.1 二叉树的定义及基本操作 135
6.2.2 二叉树的性质 137
6.2.3 二叉树的存储结构 139
6.3 二叉树的遍历 142
6.3.1 二叉树的遍历算法 142
6.3.2 二叉树遍历算法的非递归形式 144
6.3.3 二叉树遍历的应用 148
6.4 线索二叉树 151
6.4.1 线索二叉树的概念 151
6.4.2 建立线索二叉树 153
6.4.3 线索二叉树的遍历 154
6.4.4 线索二叉树的更新 155
6.5 树和森林 156
6.5.1 树的存储结构 156
6.5.2 森林和二叉树的转换 160
6.5.3 树和森林的遍历 161
6.6 二叉树应用举例 162
6.6.1 Huffman树及其构造算法 162
6.6.2 Huffman编码及译码 166
本章小结 169
习题6 169
第7章 图 171
7.1 图的定义及操作 171
7.1.1 图的定义 171
7.1.2 图的抽象数据类型 175
7.2 图的存储结构 177
7.2.1 数组表示法 177
7.2.2 邻接表表示法 179
7.2.3 十字链表表示法 181
7.2.4 邻接多重表表示法 183
7.3 图的遍历 184
7.3.1 深度优先搜索算法 184
7.3.2 广度优先搜索算法 186
7.3.3 求连通分量的算法 187
7.4 最小生成树 188
7.4.1 Prim算法 189
7.4.2 Kruskal算法 191
7.5 最短路径问题 193
7.5.1 Dijkstra算法 193
7.5.2 Floyd算法 197
7.6 图的应用实例 199
7.6.1 拓扑排序 200
7.6.2 关键路径 204
本章小结 208
习题7 209
第8章 查找 211
8.1 查找概述 211
8.2 顺序表的静态查找 212
8.2.1 顺序查找算法 213
8.2.2 折半查找算法 214
8.2.3 分块查找算法 216
8.3 树表的动态查找 219
8.3.1 二叉排序树和平衡二叉排序树 219
8.3.2 B-树 232
8.3.3 B＋树和B＊树 240
8.4 Hash表的查找 241
8.4.1 Hash表的含义 241
8.4.2 Hash函数的构造方法 243
8.4.3 处理冲突的方法 246
8.4.4 Hash表的查找及分析 248
本章小结 251
习题8 252
第9章 排序 253
9.1 排序概述 253
9.2 插入排序 255
9.2.1 直接插入排序 255
9.2.2 折半插入排序 258
9.2.3 链表插入排序 259
9.2.4 Shell排序 261
9.3 交换排序 262
9.3.1 起泡排序 262
9.3.2 快速排序 264
9.4 选择排序 266
9.4.1 直接选择排序 267
9.4.2 堆选择排序 268
9.5 归并排序 274
9.6 基数排序 276
9.7 各种内排序方法的比较讨论 280
9.8 外排序概述 281
习题9 283
第10章 算法设计基础 284
10.1 穷举法 284
10.1.1 算法概述 284
10.1.2 穷举法解决背包问题 285
10.2 贪心法 287
10.2.1 算法概述 287
10.2.2 贪心法解决背包问题 288
10.3 分治法 289
10.3.1 分治策略 289
10.3.2 应用实例：大整数乘法 291
10.4 动态规划法 292
10.4.1 算法概述 292
10.4.2 动态规划法解决背包问题 293
10.5 回溯法 294
10.5.1 算法概述 294
10.5.2 回溯法解决背包问题 295
本章小结 296
习题10 296
参考文献 298