第1章 概论 1
1.1 什么是数据结构 1
1.2 数据抽象和抽象数据类型 4
1.3 数据结构的描述 6
1.4 算法和算法分析 8
1.4.1 算法及其性能标准 8
1.4.2 算法的时间复杂度 9
1.4.3 渐近时间复杂度 11
1.4.4 最坏、最好和平均情况时间复杂度 12
1.4.5 算法的空间复杂度 12
小结 13
习题1 13
第2章 两种基本数据结构 15
2.1 结构与联合 15
2.1.1 结构 15
2.1.2 联合 16
2.2 数组 17
2.2.1 一维数组 17
2.2.2 二维数组 17
2.2.3 多维数组 19
2.3 链表 19
2.3.1 指针 19
2.3.2 单链表 23
2.3.3 带表头结点的单链表 29
2.3.4 循环链表 30
2.3.5 双向链表 31
小结 32
习题2 33
第3章 堆栈和队列 34
3.1 堆栈 34
3.1.1 堆栈 ADT 34
3.1.2 堆栈的顺序表示 35
3.1.3 堆栈的链接表示 37
3.2 队列 38
3.2.1 队列 ADT 38
3.2.2 队列的顺序表示 39
3.2.3 队列的链接表示 42
3.3＊ 表达式的计算 42
3.3.1 表达式 42
3.3.2 中缀表达式转换为后缀表达式 43
3.3.3 计算后缀表达式的值 46
3.4＊ 递归和递归过程 49
3.4.1 递归的概念 49
3.4.2 递归的实现 50
3.5＊ 演示和测试 52
小结 54
习题3 54
第4章 线性表和数组 56
4.1 线性表 56
4.1.1 线性表 ADT 56
4.1.2 线性表的顺序表示 57
4.1.3 线性表的链接表示 61
4.1.4 两种存储表示的比较 64
4.2＊ 多项式的算术运算 65
4.2.1 多项式 ADT 65
4.2.2 多项式的链接表示 65
4.2.3 多项式的输入和输出 66
4.2.4 多项式相加 68
4.3 数组作为抽象数据类型 70
4.4 特殊矩阵 71
4.4.1 对称矩阵 71
4.4.2＊ 带状矩阵 72
4.5 稀疏矩阵 73
4.5.1 稀疏矩阵 ADT 73
4.5.2 稀疏矩阵的顺序表示 74
4.5.3 稀疏矩阵转置 75
4.5.4＊ 稀疏矩阵相乘 77
4.5.5 稀疏矩阵的正交链表表示 80
4.5.6＊ 建立正交链表 83
4.5.7＊ 打印正交链表 84
小结 85
习题4 85
第5章 字符串和广义表 87
5.1 字符串 87
5.1.1 字符串 ADT 87
5.1.2 字符串的存储表示 88
5.1.3 简单模式匹配算法 89
5.1.4＊ 模式匹配的 KMP 算法 92
5.2＊ 广义表 96
5.2.1 广义表的概念 96
5.2.2 广义表 ADT 97
5.2.3 广义表的存储表示 98
5.2.4 广义表的算法 99
小结 99
习题5 100
第6章 树 101
6.1 树的基本概念 101
6.1.1 树的定义 101
6.1.2 基本术语 102
6.2 二叉树 103
6.2.1 二叉树的定义和性质 103
6.2.2 二叉树 ADT 105
6.2.3 二叉树的存储表示 106
6.2.4 二叉树的遍历 110
6.2.5＊ 二叉树遍历的非递归算法 114
6.2.6＊ 二叉树遍历的应用实例 116
6.2.7＊ 线索二叉树 118
6.3 树和森林 122
6.3.1 森林与二叉树的转换 122
6.3.2 树和森林的存储表示 123
6.3.3 树和森林的遍历 125
6.4＊ 堆和优先权队列 126
6.4.1 堆 126
6.4.2 优先权队列 129
6.5 哈夫曼树和哈夫曼编码 132
6.5.1 树的路径长度 132
6.5.2 哈夫曼树和哈夫曼算法 133
6.5.3 哈夫曼编码 135
6.6＊ 并查集和等价关系 137
6.6.1 并查集 137
6.6.2 并查集的实现 138
6.6.3 集合按等价关系分组 140
小结 141
习题6 141
第7章 集合和搜索 144
7.1 集合及其表示 144
7.1.1 集合和搜索 144
7.1.2 集合 ADT 145
7.1.3 集合的表示 146
7.2 顺序搜索 146
7.3 二分搜索 149
7.3.1 对半搜索 149
7.3.2＊ 二叉判定树 150
7.3.3＊ 斐波那契搜索 152
7.4＊ 搜索算法的时间下界 154
小结 155
习题7 155
第8章 搜索树 156
8.1 二叉搜索树 156
8.1.1 二叉搜索树的定义 156
8.1.2 二叉搜索树的搜索 157
8.1.3 二叉搜索树的插入 158
8.1.4 二叉搜索树的删除 159
8.1.5＊ 二叉搜索树的高度 162
8.2＊ 二叉平衡树 162
8.2.1 二叉平衡树的定义 163
8.2.2 二叉平衡树的平衡旋转 163
8.2.3 二叉平衡树的插入 169
8.2.4 二叉平衡树的删除 172
8.2.5 二叉平衡数的高度 175
8.3 B-树 176
8.3.1 m 叉搜索树 176
8.3.2 B-树的定义 178
8.3.3 B-树的高度 178
8.3.4 B-树的搜索 179
8.3.5 B-树的插入 179
8.3.6 B-树的删除 182
8.4＊ 键树 184
8.4.1 键树的定义 184
8.4.2 双链树 185
8.4.3 Trie 树 185
8.5＊ 伸展树 186
小结 189
习题8 189
第9章 跳表和散列表 191
9.1 字典 191
9.2＊ 跳表 191
9.2.1 什么是跳表 192
9.2.2 跳表的搜索 195
9.2.3 跳表的插入 196
9.2.4 跳表的删除 197
9.3 散列表 198
9.3.1 散列技术 198
9.3.2 散列函数 199
9.3.3 解决冲突的拉链法 201
9.3.4 解决冲突的线性探查法 202
9.3.5 解决冲突的其他开地址法 206
9.3.6 性能分析 208
小结 208
习题9 209
第10章 图 210
10.1 图的基本概念 210
10.1.1 图的定义与术语 210
10.1.2 图 ADT 213
10.2 图的存储结构 214
10.2.1 矩阵表示法 214
10.2.2 邻接表表示法 217
10.2.3＊ 多重表表示法 220
10.3 图的遍历 221
10.3.1 深度优先遍历 221
10.3.2 宽度优先遍历 223
10.4 拓扑排序和关键路径 225
10.4.1 拓扑排序 225
10.4.2＊ 关键路径 228
10.5 最小代价生成树 232
10.5.1 普里姆算法 233
10.5.2＊ 克鲁斯卡尔算法 234
10.6＊ 最短路径 236
10.6.1 单源最短路径 237
10.6.2 所有顶点之间的最短路径 240
小结 243
习题10 243
第11章 内排序 246
11.1 排序的基本概念 246
11.2 插入排序 247
11.2.1 直接插入排序 247
11.2.2＊ 希尔排序 251
11.3 交换排序 252
11.3.1 冒泡排序 253
11.3.2 快速排序 254
11.4 合并排序 259
11.4.1 两路合并排序 259
11.4.2 合并排序的迭代算法 260
11.4.3＊ 链表上的合并排序 261
11.5 选择排序 265
11.5.1 简单选择排序 265
11.5.2＊ 堆排序 266
11.6＊ 排序算法的时间下界 267
11.7＊ 基数排序 269
小结 272
习题11 272
第12章 文件和外排序 274
12.1＊ 辅助存储器简介 274
12.1.1 主存储器和辅助存储器 274
12.1.2 磁盘存储器 274
12.2 文件 276
12.2.1 文件的基本概念 276
12.2.2 文件的组织方式 276
12.2.3 C 语言文件 280
12.3 文件的索引结构 281
12.3.1 静态索引结构 281
12.3.2 动态索引结构 282
12.4＊ 外排序 283
12.4.1 外排序的基本过程 283
12.4.2 初始游程的生成 283
12.4.3 多路合并 286
12.4.4 最佳合并树 288
小结 289
习题12 289
附录 A 软件工程概述 290
一、软件开发方法学 290
二、系统测试方法 292
附录 B 实习要求和实习题 294
一、实习目的 294
二、实习要求 294
三、实习步骤 294
四、实习报告 295
五、实习题 296
附录 C 专用名词中英文对照表 298
参考文献 304