第1章 概论 1
1.1什么是数据结构 1
1.2数据结构的基本概念和术语 3
1.3抽象数据类型及其表示与实现 6
1.4算法和算法分析 9
1.4.1算法的定义及特性 9
1.4.2算法的设计要求 9
1.4.3算法效率的衡量方法及其准则 10
1.4.4算法的存储空间需求 13
1.5类C语言描述 14
习题 15
第2章 线性表 17
2.1线性表的类型定义 17
2.1.1线性表的概念 17
2.1.2线性表的抽象数据类型 18
2.2线性表的顺序表示和实现 21
2.2.1线性表的顺序表示 21
2.2.2顺序表上基本运算的实现 21
2.3线性表的链式表示和实现 25
2.3.1单链表的表示 25
2.3.2单链表操作的实现 27
2.4线性表实现方法的比较 33
2.5循环链表 34
2.6双链表 35
2.7静态链表 36
2.8算法设计举例 38
习题 42
第3章 栈和队列 44
3.1栈 44
3.1.1栈的类型定义 44
3.1.2栈的表示和实现 45
3.2栈的应用举例 49
3.3栈与递归 51
3.3.1如何实现递归 52
3.3.2采用递归算法解决的问题 52
3.3.3将递归转换为非递归 54
3.4队列 56
3.4.1队列的类型定义 56
3.4.2循环队列——队列的顺序存储结构 57
3.4.3链队列——队列的链式表示和实现 60
3.5算法设计举例 62
习题 64
第4章 串 67
4.1串的类型定义 67
4.2串的表示和实现 68
4.2.1串的顺序存储结构 69
4.2.2串的链式存储结构 70
4.3串的模式匹配 71
4.3.1朴素的模式匹配算法 71
4.3.2 KMP算法 72
4.4串的应用举例 74
4.5算法设计举例 75
习题 77
第5章 数组和广义表 79
5.1数组的概念及其基本操作 79
5.2数组的顺序存储 80
5.3矩阵的压缩存储 81
5.3.1特殊矩阵 81
5.3.2稀疏矩阵 83
5.4广义表 91
5.4.1广义表的定义 91
5.4.2广义表的存储结构 92
5.5算法设计举例 94
习题 96
第6章 树 98
6.1树的概念及操作 98
6.2二叉树 100
6.2.1二叉树的概念及操作 100
6.2.2二叉树的性质 102
6.2.3二叉树的存储结构 104
6.3二叉树的遍历 105
6.4线索二叉树 108
6.4.1线索二叉树的概念 108
6.4.2遍历线索二叉树 110
6.5树和森林 112
6.5.1树的存储结构 112
6.5.2森林、树、二叉树的相互转换 114
6.5.3树和森林的遍历 116
6.6哈夫曼树及其应用 117
6.6.1最优二叉树（哈夫曼树） 117
6.6.2哈夫曼编码 119
6.7算法设计举例 121
习题 124
第7章 图 128
7.1图的定义和术语 128
7.2图的存储结构 131
7.2.1邻接矩阵表示法（数组表示法） 131
7.2.2邻接表 132
7.2.3十字链表 134
7.2.4邻接多重表 135
7.3图的遍历 136
7.3.1深度优先遍历 136
7.3.2广度优先遍历 138
7.4图的连通性问题 139
7.4.1图的连通分量和生成树 139
7.4.2最小生成树 140
7.5有向无环图及其应用 144
7.5.1拓扑排序 144
7.5.2关键路径 146
7.6最短路径 150
7.6.1从某个源点到其他各顶点的最短路径 150
7.6.2每一对顶点之间的最短路径 152
7.7算法设计举例 154
习题 157
第8章 动态存储管理 160
8.1概述 160
8.1.1问题的提出 160
8.1.2内存分配处理 161
8.2可利用空间表及分配办法 161
8.2.1可利用空间表的三种不同的结构形式 162
8.2.2可利用空间表的三种分配策略 163
8.3边界标识法 164
8.3.1可利用空间表的结构 164
8.3.2分配算法 165
8.3.3回收算法 167
8.4伙伴系统 169
8.4.1可利用空间表的结构 169
8.4.2分配算法 170
8.4.3回收算法 171
习题 171
第9章 查找 173
9.1静态查找表上的查找 174
9.1.1顺序表的查找 174
9.1.2折半查找 175
9.1.3斐波那契查找 178
9.1.4插值查找 179
9.1.5分块查找 180
9.2动态查找表上的查找 182
9.2.1二叉排序树 182
9.2.2平衡二叉树 186
9.2.3 B-树 194
9.2.4键树 199
9.3散列表上的查找 199
9.3.1散列表的概念 199
9.3.2构造散列函数的方法 200
9.3.3解决冲突的方法 202
9.3.4散列表的查找性能分析 206
9.3.5闭散列法与开散列法的比较 207
9.4算法设计举例 207
习题 210
第10章 排序 213
10.1概述 213
10.2插入排序 214
10.2.1直接插入排序 214
10.2.2折半插入排序 216
10.2.3二路插入排序 216
10.2.4表插入排序 218
10.2.5希尔排序 220
10.3交换排序 221
10.3.1起泡排序 221
10.3.2快速排序 222
10.4选择排序 224
10.4.1直接选择排序 225
10.4.2树形选择排序 226
10.4.3堆排序 226
10.5归并排序 229
10.6分配排序 230
10.7各种内部排序方法的比较 234
10.8外部排序 235
10.8.1文件管理 235
10.8.2外部排序的方法 236
10.8.3多路平衡归并排序 237
10.8.4置换选择排序 239
10.8.5最佳归并树 242
10.8.6磁带排序 243
10.9算法设计举例 244
习题 246
第11章 文件 249
11.1基本概念 249
11.2顺序文件 251
11.3索引文件 253
11.4索引顺序文件 254
11.4.1 ISAM文件 254
11.4.2 VSAM文件 257
11.5散列文件 259
11.6多关键字文件 259
11.6.1多重表文件 260
11.6.2倒排文件 260
习题 261
附录 上机实验题目 262
参考文献 264