目　录

第 1章　绪论　1
1.1　预备知识　1
1.1.1　集合的笛卡儿积　1
1.1.2　二元关系　2
1.1.3　二元关系的基本性质和几种重要关系　3
1.2　什么是数据结构　4
1.2.1　从实际问题理解数据结构　4
1.2.2　数据结构所讨论的内容　6
1.2.3　如何表示数据结构　9
1.3　抽象数据类型　10
1.3.1　什么是抽象数据类型　10
1.3.2　抽象数据类型的定义与实现　12
1.4　算法与算法分析　13
1.4.1　什么是算法　13
1.4.2　算法描述　15
1.4.3　常用的算法设计方法　16
1.4.4　算法分析　21
习题　24
上机练习题　26

第 2章　线性表的顺序存储及其运算　27
2.1　线性表的概念　27
2.1.1　 什么是线性表　27
2.1.2　线性表的抽象数据类型　29
2.2　顺序表及其运算实现　30
2.2.1　线性表的顺序存储——顺序表　30
2.2.2　顺序表的基本运算　31
2.2.3　顺序表应用例——求子集　36
2.3　栈　36
2.3.1　什么是栈　37
2.3.2　栈的抽象数据类型　39
2.3.3　顺序栈及其运算　39
2.4　栈应用　42
2.4.1　栈在优先级处理中的应用　42
2.4.2　栈与分治法　48
2.4.3　栈与回溯法　50
2.4.4　栈与递归　55
2.5　队列　63
2.5.1　队列及其抽象数据类型　63
2.5.2　顺序队列及其运算　64
2.5.3　队列应用例　68
* 2.5.4　优先队列　72
2.6　数组与特殊矩阵的表示　74
2.6.1　数组的顺序存储　74
2.6.2　规则矩阵的压缩存储　76
* 2.6.3　稀疏矩阵的三列二维数组表示——三元组顺序表　78
习题　81
上机练习题　82

第3章　链表　83
3.1　线性表的链式存储——线性链表　83
3.1.1　线性链表的结构特点　83
3.1.2　线性链表的运算　84
3.2　链式栈与链式队列　91
3.2.1　栈的链式存储——链式栈　91
3.2.2　队列的链式存储——链式队列　95
3.3　循环链表　98
3.3.1　循环链表的结构特点　98
3.3.2　循环链表的基本运算　99
3.3.3　链表应用例　103
*3.4　多重链表　109
3.4.1　多重链表结构　109
3.4.2　双向链表　110
*3.5　广义表　112
3.5.1　什么是广义表　113
3.5.2　广义表的存储表示　114
3.5.3　广义表的基本运算　116
习题　120
上机练习题　121

第4章　树与二叉树　122
4.1　树的基本概念　122
4.1.1　 什么是树　122
4.1.2　树的性质　127
4.2　二叉树　128
4.2.1　什么是二叉树　128
4.2.2　二叉树的基本性质　128
4.2.3　二叉树的抽象数据类型　131
4.2.4　二叉树的存储结构　131
4.2.5　二叉树的遍历及其他运算　133
* 4.2.6　线索二叉树　138
4.3　二叉树应用　141
4.3.1　表达式线性化　141
4.3.2　**优二叉树　143
4.3.3　二叉搜索树　148
4.3.4　堆　154
* 4.3.5　二叉树与减治法　160
4.4　树的运算　163
4.4.1　树的抽象数据类型　163
4.4.2　树的存储结构　164
4.4.3　树的遍历　165
* 4.4.4　树的其他运算　167
* 4.5　树与回溯法　170
4.5.1　问题解的描述——解空间树　171
4.5.2　回溯法的求解过程分析——遍历解空间树　172
4.5.3　回溯法求解问题的形式化描述　174
* 4.6　森林的遍历　176
4.6.1　森林与二叉树的转换　176
4.6.2　森林的遍历　177
习题　178
上机练习题　179

第5章　图　180
5.1　图的基本概念　180
5.1.1　图的定义和概念　180
5.1.2　图的抽象数据类型　184
*5.1.3　欧拉路径　185
5.2　图的存储结构　186
5.2.1　图的邻接矩阵表示　186
5.2.2　图的邻接表表示　189
*5.2.3　图的其他表示方法　192
5.3　图的遍历　195
5.3.1　图的深度优先遍历　195
5.3.2　图的广度优先遍历　197
5.3.3　图遍历的应用　198
*5.3.4　图的连通性　200
*5.4　有向图与有向无环图　201
5.4.1　有向图的连通性和传递闭包　202
*5.4.2　有向无环图和拓扑排序　204
*5.4.3　关键路径　207
5.5　**小生成树　208
5.5.1　图的生成树与**小生成树　209
5.5.2　普里姆(Prim)算法　210
5.5.3　克鲁斯卡尔(Kruskal)算法　213
5.5.4　贪心算法　215
5.6　**短路径问题　218
5.6.1　单源**短路径　218
5.6.2　全源**短路径　220
5.6.3　动态规划算法　223
5.7　图应用例——城市间公路交通网问题　227
5.7.1　问题描述　227
5.7.2　问题求解思路　228
习题　228
上机练习题　230

第6章　查找　231
6.1　线性查找表　231
6.1.1　顺序查找　232
6.1.2　折半查找　232
*6.1.3　斐波那契查找　234
6.1.4　线性查找表的性能比较　234
6.2　二叉搜索树查找性能　235
6.3　AVL树　236
6.3.1　BST的旋转操作　237
6.3.2　AVL树的插入和平衡化旋转　238
*6.3.3　AVL树的删除　240
*6.3.4　AVL树的性能　241
6.4　B-树　242
6.4.1　多路动态搜索树　242
6.4.2　B-树的查找　243
6.4.3　B-树的插入　244
*6.4.4　B-树的删除　245
6.5　散列方法　246
6.5.1　散列技术　246
6.5.2　散列函数　247
6.5.3　冲突处理　250
6.5.4　散列的删除　252
6.5.5　散列的性能　252
6.6　静态索引结构　253
6.6.1　索引查找　253
6.6.2　索引存储方式　254
*6.6.3　索引文件结构　255
6.7　模式匹配　258
6.7.1　字符串及其ADT　258
6.7.2　字符串的存储表示　259
6.7.3　字符串的模式匹配及简单匹配算法　259
6.7.4　字符串匹配的KMP算法　260
习题　263
上机练习题　264

第7章　排序　265
7.1　排序的概念及算法性能分析　265
7.2　基本排序方法　266
7.2.1　冒泡排序　267
7.2.2　插入排序　268
7.2.3　直接选择排序　272
7.2.4　基本排序方法的比较　273
7.3　快速排序　274
7.3.1　快速排序的过程　274
7.3.2　快速排序的性能分析　275
7.4　归并排序　276
7.4.1　二路归并　276
7.4.2　自底向上的归并排序　276
7.4.3　自顶向下的归并排序　278
*7.5　锦标赛排序　279
7.6　堆排序　280
7.6.1　堆排序的思想　280
7.6.2　堆排序的实现　282
7.7　内排序方法分析　283
*7.7.1　排序方法的下界　283
7.7.2　内排序方法的比较　284
7.8　线性时间复杂度的排序算法　285
*7.8.1　计数排序　285
7.8.2　基数排序　287
7.9　外部排序　290
7.9.1　外部排序方法　290
*7.9.2　基于败者树的k路归并方法　291
*7.9.3　排序——归并的改进　292
习题　296
上机练习题　297

实验指导　298
实验一　顺序表及其应用　299
实验二　求解迷宫问题　301
实验三　简单算术表达式的处理　302
实验四　求解简单背包问题　303
实验五　链表及其应用　304
实验六　实验室机时机位的管理　305
实验七　实现Huffman编码　307
实验八　文件管理的模拟　309
实验九　求网络站点间的**短连接　312
实验十　查找**高分与次高分　314
实验十一　比赛日程安排与成绩统计　316