前言页 1
前言 1
第1章 绪论 1
本章要点 1
1.1 数据结构的概念及分类 1
1.1.1 数据与数据结构 1
1.1.2 数据结构的分类 2
1.2 抽象数据类型及面向对象概念 4
1.2.1 数据类型 4
1.2.2 数据抽象与抽象数据类型 5
1.2.3 面向对象的概念 6
1.2.4 用于描述数据结构的语言 7
1.3 算法定义 7
1.4.1 算法的性能标准 9
1.4 算法性能分析与度量 9
1.4.2 算法的后期测试 10
1.4.3 算法的事前估计 11
1.4.4 渐进的时间复杂度 16
1.4.5 渐进的空间复杂度 19
小结 19
习题 20
第2章 数组 23
本章要点 23
2.1 作为抽象数据类型的数组 23
2.1.1 在C++中数组的定义和初始化 23
2.1.2 作为抽象数据类型的数组 24
2.1.3 数组的顺序存储方式 26
2.2 顺序表 28
2.2.1 线性表的概念 28
2.2.2 顺序表的定义和特点 29
2.2.3 顺序表的搜索、插入和删除 32
2.2.4 作为抽象数据类型，使用顺序表的事例 33
2.3 稀疏矩阵 34
2.3.1 稀疏矩阵的抽象数据类型 34
2.3.2 稀疏矩阵的压缩表示 35
2.4 字符串 36
2.4.1 字符串抽象数据类型和类定义 36
2.4.2 字符串操作的实现 37
小结 40
习题 41
第3章 链表 45
本章要点 45
3.1 单链表 45
3.1.1 单链表的概念 45
3.1.2 单链表的类定义 46
3.1.3 单链表中的插入与删除 47
3.1.4 带表头结点的单链表 49
3.1.5 单链表的模板类 50
3.1.6 静态链表 54
3.2 循环链表 55
3.3 多项式及其相加 56
3.3.1 多项式抽象数据类型与*this指针 56
3.3.2 多项式的表示 57
3.3.3 多项式的加法 59
3.4 双向链表 61
3.4.1 双向链表的概念 61
3.4.2 带表头结点的双向循环链表 62
3.4.3 双向循环链表的搜索、插入和删除算法 63
3.5 稀疏矩阵 65
小结 67
习题 68
第4章 栈和队列 71
本章要点 71
4.1 栈 71
4.1.1 栈的定义 71
4.1.2 顺序栈--栈的数组存储表示 71
4.1.3 链式栈--栈的链接存储表示 74
4.2 表达式的计算 76
4.2.1 表达式 76
4.2.2 应用后缀表示计算表达式的值 77
4.2.3 中缀表示与其他表示之间转换 80
4.3 队列 83
4.3.1 队列的定义 83
4.3.2 循环队列--队列的顺序存储表示 83
4.3.3 链式队列--队列的链接存储表示 86
4.3.4 队列的应用举例--打印二项展开式(a+b)的系数 87
4.4 优先级队列 89
4.4.1 优先级队列的定义 89
4.4.2 优先级队列的存储表示和实现 90
小结 91
习题 92
第5章 递归 94
本章要点 94
5.1 递归的概念 94
5.2 递归过程与递归工作栈 98
5.2.1 递归工作栈 98
5.2.2 用栈实现递归过程的非递归算法 99
5.2.3 用迭代法实现递归过程 101
5.3 用回潮法求解迷宫问题 103
5.4 广义表 107
5.4.1 广义表的概念 108
5.4.2 广义表的表示及操作 109
5.4.3 广义表存储结构的实现 110
5.4.4 广义表的递归算法 114
小结 121
习题 121
第6章 树与森林 124
本章要点 124
6.1 树和森林的概念 124
6.1.1 树的定义 124
6.1.2 树的术语 125
6.1.3 树的抽象数据类型 126
6.2 二叉树 126
6.2.1 二叉树的定义 126
6.2.2 二叉树的性质 127
6.2.3 二叉树的抽象数据类型 128
6.2.4 二叉树的表示 129
6.3 遍历二叉树 134
6.3.1 遍历二叉树的递归算法 135
6.3.2 应用遍历二叉树的事例 136
6.3.3 遍历二叉树的非递归算法 138
6.3.4 二叉树的计数 141
6.4 线索化二叉树 144
6.4.1 线索 144
6.4.2 中序线索化二叉树 144
6.5 堆 150
6.5.1 堆的定义 150
6.5.2 堆的建立 151
6.5.3 堆的插入与删除 153
6.6 树与森林 154
6.6.1 树的存储表示 155
6.6.2 森林与二叉树的转换 157
6.6.3 树的遍历 158
6.6.4 森林的遍历 160
6.7 霍夫曼树 161
6.7.1 路径长度 161
6.7.2 霍夫曼树 162
6.7.3 霍夫曼编码 164
小结 165
习题 166
第7章 集合与搜索 169
本章要点 169
7.1 集合及其表示 169
7.1.1 集合基本概念 169
7.1.2 用位向量实现集合抽象数据类型 169
7.1.3 用有序链表实现集合的抽象数据类型 172
7.1.4 并查集 177
7.2 静态搜索表 180
7.2.1 搜索的概念 180
7.2.2 静态搜索结构 181
7.2.3 顺序搜索 183
7.2.4 基于有序顺序表的折半搜索 185
7.3 二叉搜索树 188
7.3.1 定义 188
7.3.2 二叉搜索树上的搜索 189
7.3.3 二叉搜索树的插入 191
7.3.4 二叉搜索树的删除 192
7.3.5 二叉搜索树的搜索效率 194
7.4 AVL树 196
7.4.1 AVL树的定义 196
7.4.2 平衡化旋转 197
7.4.3 AVL树的插入和删除 200
7.4.4 AVL树的高度 203
小结 203
习题 204
第8章 图 207
本章要点 207
8.1 图的基本概念 207
8.1.1 图的基本概念 207
8.1.2 图的抽象数据类型 210
8.2 图的存储表示 210
8.2.1 邻接矩阵 211
8.2.2 邻接表 213
8.2.3 邻接多重表 217
8.3 图的遍历与连通性 219
8.3.1 深度优先搜索 220
8.3.2 广度优先搜索 221
8.3.3 连通分量 222
8.3.4 重连通分量 224
8.3.5 图的遍历举例：欧拉回路问题 225
8.4 最小生成树 227
8.4.1 克鲁斯卡尔算法 228
8.4.2 普里姆算法 230
8.5 单源最短路径问题 232
8.6 活动网络(activity network) 235
8.6.1 用顶点表示活动的网络 235
8.6.2 用边表示活动的网络 239
小结 243
习题 244
本章要点 247
9.1 概述 247
第9章 排序 247
9.2 插入排序 249
9.2.1 直接插入排序 249
9.2.2 折半插入排序 251
9.2.3 链表插入排序 251
9.2.4 希尔排序 253
9.3 交换排序 255
9.3.1 起泡排序 255
9.3.2 快速排序 256
9.4 选择排序 259
9.4.1 直接选择排序 260
9.4.2 锦标赛排序 261
9.4.3 堆排序 261
9.5.1 归并 264
9.5 归并排序 264
9.5.2 迭代的归并排序算法 265
9.5.3 递归的链表归并排序 267
9.6 基数排序 268
9.6.1 多排序码排序 269
9.6.2 链式基数排序 270
9.7 外排序 272
9.7.1 外排序的基本过程 272
9.7.2 k路平衡归并与败者树 274
9.7.3 初始归并段的生成 277
9.7.4 最佳归并树 279
小结 281
习题 282
10.1 静态索引结构 285
10.1.1 线性索引 285
本章要点 285
第10章 索引与散列 285
10.1.2 倒排表 287
10.1.3 m路静态搜索树 288
10.2 动态索引结构 289
10.2.1 动态的m路搜索树 289
10.2.2 B树 291
10.2.3 B树的插入 293
10.2.4 B树的删除 295
10.2.5 B+树 297
10.3 散列 300
10.3.1 词典的抽象数据类型 300
10.3.2 散列表与散列方法 301
10.3.3 散列函数 302
10.3.4 处理冲突的闭散列方法 305
10.3.5 处理冲突的开散列方法--链地址法 310
10.3.6 散列表分析 312
10.4 可扩充散列 313
10.4.1 二叉Trie树 313
10.4.2 将二叉Trie树转换为目录表 314
10.4.3 目录表扩充与收缩 316
10.4.4 性能分析 317
小结 318
习题 318
附录A 用C++描述面向对象程序 322
A.1 用模板定义C++中的类 322
A.2 类中成员函数的实现 323
A.3 函数名重载和操作符重载 327
A.4 C++中的主函数 328
附录B 教学进度与习题安排参考 329
附录C 词汇索引 330
参考文献 337