第1章 概论 1
1.1 问题求解方法 1
1.1.1 问题和问题求解 1
1.1.2 问题求解过程 1
1.1.3 计算机求解问题的过程 2
1.2 什么是数据结构 2
1.2.1 算法与数据结构 2
1.2.2 数据结构基本概念 3
1.2.3 数据的逻辑结构 4
1.2.4 数据的存储表示 5
1.2.5 数据结构的操作 6
1.3 数据抽象和抽象数据类型 7
1.3.1 数据抽象和过程抽象 7
1.3.2 模块化、封装与信息隐蔽 7
1.3.3 数据类型和抽象数据类型 8
1.4 面向对象方法 10
1.4.1 面向对象方法的由来 10
1.4.2 面向对象方法的基本思想 10
1.4.3 面向对象方法的基本要素 11
1.4.4 抽象数据类型和面向对象方法 12
1.4.5 C＋＋语言对抽象数据类型的支持 13
1.5 描述数据结构和算法 13
1.5.1 数据结构的规范 13
1.5.2 实现数据结构 14
1.6 算法分析的基本方法 15
1.6.1 算法及其性能标准 15
1.6.2 算法的时间复杂度 16
1.6.3 渐近时间复杂度 18
1.6.4 最好、最坏和平均情况时间复杂度 19
1.6.5 算法按时间复杂度分类 19
1.6.6 算法的空间复杂度 19
本章小结 20
习题1 20
第2章 数组和链表 22
2.1 两种基本的存储表示方式 22
2.2 结构和类 22
2.2.1 结构 22
2.2.2 结构表示元素 23
2.3 指针和动态存储分配 24
2.3.1 指针 24
2.3.2 动态存储分配 25
2.3.3 静态变量和动态变量 26
2.4 数组 26
2.4.1 一维数组 26
2.4.2 二维数组 27
2.4.3 多维数组 28
2.4.4 数组和指针 28
2.4.5 固定长度数组和可变长度数组 28
2.5 链表 29
2.5.1 指向结构的指针 30
2.5.2 单链表 30
2.5.3 带表头结点的单链表 33
2.5.4 单循环链表 33
2.5.5 双向链表 33
2.6 采用模拟指针的链表 35
2.6.1 结点结构 35
2.6.2 可用空间表 35
2.7 异常处理 37
本章小结 38
习题2 38
第3章 栈和队列 40
3.1 栈 40
3.1.1 栈ADT 40
3.1.2 栈的顺序表示 41
3.1.3 栈的链接表示 44
3.2 队列 47
3.2.1 队列ADT 47
3.2.2 队列的顺序表示 48
3.2.3 队列的链接表示 51
3.3 表达式计算 51
3.3.1 表达式 51
3.3.2 中缀表达式转换为后缀表达式 52
3.3.3 计算后缀表达式的值 55
3.4 演示与测试 58
本章小结 61
习题3 61
第4章 递归 63
4.1 递归和递归算法 63
4.1.1 递归的概念 63
4.1.2 递归算法示例 64
4.2 归纳证明 66
4.3 递推关系 67
4.4 实现递归 67
4.4.1 函数调用和系统栈 68
4.4.2 递归函数的性能 69
4.4.3 尾递归 69
4.4.4 消去递归 70
本章小结 70
习题4 70
第5章 线性表和串 72
5.1 线性表 72
5.1.1 线性表ADT 72
5.1.2 线性表的顺序表示 73
5.1.3 线性表的链接表示 76
5.1.4 两种存储表示的比较 79
5.2 一元多项式算术运算 80
5.2.1 多项式ADT 80
5.2.2 多项式的链接表示 80
5.2.3 项结点类 81
5.2.4 多项式类 82
5.2.5 多项式的输入和输出 83
5.2.6 多项式相加 84
5.2.7 多项式相乘 85
5.2.8 重载运算符 86
5.3 串 86
5.3.1 串ADT 86
5.3.2 串的存储表示 87
5.3.3 串运算的实现 88
5.3.4 简单模式匹配算法 89
5.3.5 KMP算法 91
本章小结 95
习题5 95
第6章 数组和广义表 97
6.1 数组作为抽象数据类型 97
6.1.1 数组ADT 97
6.1.2 一维数组的C＋＋类 98
6.2 矩阵 99
6.2.1 矩阵的概念 99
6.2.2 矩阵ADT 99
6.2.3 矩阵的二维数组表示 100
6.3 特殊矩阵 101
6.3.1 对称矩阵 101
6.3.2 带状矩阵 102
6.4 稀疏矩阵 103
6.4.1 稀疏矩阵的三元组表 103
6.4.2 稀疏矩阵转置 105
6.4.3 稀疏矩阵相加 107
6.4.4 稀疏矩阵相乘 108
6.5 稀疏矩阵的正交链表 109
6.5.1 正交链表结构 109
6.5.2 正交链表结点类 110
6.5.3 正交链表类 111
6.5.4 建立正交链表 111
6.5.5 输出正交链表 113
6.6 广义表 113
6.6.1 广义表的概念 113
6.6.2 广义表ADT 114
6.6.3 广义表的存储表示 115
6.6.4 广义表算法 116
本章小结 116
习题6 117
第7章 树 118
7.1 树的基本概念 118
7.1.1 树的定义 118
7.1.2 基本术语 119
7.2 二叉树 120
7.2.1 二叉树的定义 120
7.2.2 二叉树的性质 121
7.2.3 二叉树ADT 122
7.2.4 二叉树的存储表示 123
7.2.5 二叉树类 123
7.2.6 实现二叉树的基本操作 124
7.3 二叉树的遍历 126
7.3.1 二叉树遍历算法 126
7.3.2 二叉树遍历的递归算法 128
7.3.3 二叉树遍历的应用实例 129
7.4 二叉树遍历的非递归算法 131
7.4.1 遍历器类 131
7.4.2 中序遍历器类 132
7.4.3 后序遍历器类 134
7.5 二叉线索树 136
7.5.1 二叉线索树的定义 136
7.5.2 构造中序线索树 137
7.5.3 遍历中序线索树 138
7.6 树和森林 139
7.6.1 森林与二叉树的转换 139
7.6.2 树和森林的存储表示 141
7.6.3 树和森林的遍历 142
本章小结 143
习题7 143
第8章 树的应用 145
8.1 堆 145
8.1.1 堆的定义 145
8.1.2 堆的顺序表示 145
8.1.3 向下调整和建堆操作 145
8.2 优先权队列 147
8.2.1 优先权队列ADT 147
8.2.2 优先权队列类 148
8.2.3 实现优先权队列 148
8.3 哈夫曼树和哈夫曼编码 150
8.3.1 树的路径长度 151
8.3.2 哈夫曼算法 152
8.3.3 哈夫曼树类 152
8.3.4 构造哈夫曼树 153
8.3.5 哈夫曼编码 155
8.3.6 哈夫曼编码算法 156
8.4 并查集和等价关系 156
8.4.1 并查集ADT 157
8.4.2 并查集的存储表示 157
8.4.3 并查集类 158
8.4.4 Union和Find函数 159
8.4.5 改进的Union和Find函数 159
8.4.6 按等价关系分组 160
本章小结 161
习题8 161
第9章 字典和查找 162
9.1 字典及其表示 162
9.1.1 字典 162
9.1.2 字典查找 163
9.1.3 字典ADT 163
9.1.4 字典的存储表示 164
9.2 顺序查找 165
9.2.1 无序表的顺序查找 165
9.2.2 有序表的顺序查找 165
9.2.3 平均查找长度 166
9.2.4 自组织表 166
9.3 二分查找 167
9.3.1 二分查找算法 167
9.3.2 对半查找算法 168
9.3.3 二叉判定树 169
9.3.4 斐波那契查找算法 170
9.3.5 插值查找 172
9.4 分块查找 172
9.5 查找算法的时间复杂度下界 173
本章小结 174
习题9 174
第10章 二叉查找树 175
10.1 二叉查找树表示字典 175
10.1.1 二叉查找树的定义 175
10.1.2 二叉查找树的查找操作 176
10.1.3 二叉查找树的插入操作 177
10.1.4 二叉查找树的删除操作 178
10.1.5 二叉查找树的高度 179
10.2 二叉平衡树 179
10.2.1 二叉平衡树的定义 179
10.2.2 二叉平衡树类 180
10.2.3 二叉平衡树的平衡旋转 181
10.2.4 二叉平衡树的插入操作 185
10.2.5 二叉平衡树的删除操作 187
10.2.6 二叉平衡树的高度 189
10.3 伸展树 190
10.3.1 自调节树和伸展树 190
10.3.2 伸展树的伸展操作 191
10.3.3 伸展树类 193
10.3.4 旋转的实现 193
10.3.5 伸展树的插入操作 194
10.3.6 分摊时间分析 195
10.4 红黑树 195
10.4.1 红黑树的定义 195
10.4.2 红黑树的查找操作 196
10.4.3 红黑树的插入操作 196
10.4.4 红黑树的删除操作 199
10.4.5 红黑树的高度 199
本章小结 199
习题10 199
第11章 多叉查找树 201
11.1 m叉查找树 201
11.2 Bˉ树 202
11.2.1 Bˉ树的定义 203
11.2.2 Bˉ树的高度 203
11.2.3 Bˉ树的查找操作 203
11.2.4 Bˉ树的插入操作 204
11.2.5 Bˉ树的删除操作 206
11.2.6 Bˉ树类 207
11.2.7 Bˉ树的查找函数 208
11.2.8 Bˉ树的插入函数 209
11.2.9 Bˉ树的删除函数 210
11.3 键树 212
11.3.1 键树的定义 212
11.3.2 双链树 213
11.3.3 Trie树 214
11.3.4 Trie树的查找操作 216
11.3.5 Trie树的插入操作 216
11.3.6 Trie树的删除操作 217
11.3.7 Trie树性能分析 218
本章小结 218
习题11 218
第12章 跳表和散列表 219
12.1 跳表 219
12.1.1 跳表的概念 219
12.1.2 跳表类 221
12.1.3 跳表的查找函数 222
12.1.4 跳表的插入函数 223
12.1.5 跳表的删除函数 224
12.1.6 跳表性能分析 224
12.2 散列表 224
12.2.1 散列技术 225
12.2.2 散列函数 226
12.2.3 拉链法 227
12.2.4 开地址法 228
12.2.5 线性探查法 228
12.2.6 其他开地址法 231
12.2.7 散列表性能分析 233
本章小结 233
习题12 233
第13章 图 235
13.1 图的基本概念 235
13.1.1 图的定义与术语 235
13.1.2 图的抽象数据类型 237
13.2 图的存储结构 238
13.2.1 图的矩阵表示 238
13.2.2 图的邻接矩阵实现 239
13.2.3 图的邻接表表示 241
13.2.4 图的邻接表实现 242
13.2.5 有向图的正交链表表示 245
13.2.6 无向图的邻接多重表表示 245
13.3 图的遍历 246
13.3.1 扩充的图类 246
13.3.2 深度优先遍历 247
13.3.3 广度优先遍历 248
13.3.4 基本遍历方法 249
13.4 拓扑排序 250
13.4.1 AOV网络 250
13.4.2 拓扑排序算法 252
13.4.3 拓扑排序算法实现 252
13.5 关键路径 254
13.5.1 AOE网 254
13.5.2 关键路径算法 255
13.5.3 关键路径算法实现 257
13.6 最小代价生成树 258
13.6.1 基本概念 258
13.6.2 普里姆算法 258
13.6.3 克鲁斯卡尔算法 260
13.6.4 算法正确性 262
13.7 单源最短路径 262
13.7.1 最短路径问题 262
13.7.2 迪杰斯特拉算法 263
13.7.3 数据结构选择 263
13.7.4 迪杰斯特拉算法实现 264
13.8 所有顶点之间的最短路径 266
13.8.1 弗洛伊德算法 266
13.8.2 弗洛伊德算法实现 267
本章小结 268
习题13 268
第14章 内排序 270
14.1 基本概念 270
14.2 插入排序 271
14.2.1 直接插入排序 271
14.2.2 顺序表的直接插入排序 272
14.2.3 单链表的直接插入排序 273
14.2.4 希尔排序 274
14.2.5 对半插入排序 276
14.3 选择排序 276
14.3.1 简单选择排序 276
14.3.2 堆排序 277
14.4 交换排序 278
14.4.1 冒泡排序 278
14.4.2 快速排序 280
14.4.3 快速排序性能分析 281
14.5 两路合并排序 283
14.5.1 合并两个有序序列 284
14.5.2 两路合并排序迭代算法 284
14.5.3 两路合并排序递归算法 285
14.5.4 单链表两路合并排序 285
14.6 排序算法的时间复杂度下界 287
14.7 基数排序 288
14.7.1 分配排序 289
14.7.2 基数排序算法 289
14.7.3 基数排序实现 290
本章小结 292
习题14 292
第15章 文件和外排序 294
15.1 辅助存储器简介 294
15.1.1 主存储器和辅助存储器 294
15.1.2 磁盘存储器 294
15.2 文件 295
15.2.1 文件的基本概念 295
15.2.2 文件的组织方式 296
15.3 文件的索引结构 298
15.3.1 静态索引结构 298
15.3.2 动态索引结构 299
15.4 外排序 300
15.4.1 外排序的基本过程 300
15.4.2 初始游程的生成 300
15.4.3 多路合并 302
15.4.4 最佳合并树 304
本章小结 304
习题15 305
第16章 实习指导和实习题 306
16.1 实习目的、要求和步骤 306
16.2 面向对象表示法 307
16.3 实习报告和范例 308
16.3.1 实习报告 308
16.3.2 实习题范例 309
16.3.3 实习报告范例 309
16.4 实习题 312
实习1 C＋＋语言的类及模板的使用 312
实习2 数组和链表操作 313
实习3 栈、队列及表达式计算 313
实习4 线性表的操作及应用 314
实习5 一元多项式的相加和相乘 314
实习6 对称矩阵和稀疏矩阵的压缩存储 315
实习7 串操作和文本处理 315
实习8 二叉树操作和哈夫曼编码 315
实习9 有序表查找 316
实习10 Bˉ树检索 317
实习11 散列表查找 317
实习12 图的操作及应用 318
实习13 内排序算法及其性能比较 318
实习14 置换选择和K路合并的外排序算法 318
附录A 程序测试和调试 319
A.1 面向对象程序测试 319
A.2 程序测试步骤 319
A.3 测试方法 320
A.4 程序调试 321
附录B 2019年计算机考研大纲与教材内容对照 323
B.1 2019年计算机考研大纲 323
B.2 教材内容对2019年计算机考研大纲的适应性 324
参考文献 326
