目录 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.3抽象数据类型 9
1.4类C语言描述 11
1.5算法和算法分析 14
1.5.1算法的定义及算法设计的要求 14
1.5.2算法与数据结构和程序 16
1.5.3算法性能分析与度量 16
1.5.4复杂度函数的增长率 19
1.5.5复杂度分析的例子 20
第2章线性表 23
2.1线性表的类型定义 23
2.1.1线性表的概念 23
2.1.2线性表的抽象数据类型 24
2.1.3线性表的例子 25
2.2线性表的顺序表示和实现 27
2.2.1线性表的顺序表示 27
2.2.2顺序表操作的实现 28
2.3线性表的链式表示和实现 31
2.3.1单链表的表示 32
2.3.2线性链表操作的实现 33
2.4线性表实现方法的比较 38
2.5循环链表 39
2.6双链表 40
2.7静态链表 41
*2.8算法设计举例 43
第3章栈和队列 47
3.1栈 47
3.1.1栈的类型定义 47
3.1.2栈的表示和实现 48
3.1.3顺序栈和链栈的比较 51
3.2队列 52
3.2.1队列的类型定义 52
3.2.2循环队列 53
和实现 56
3.2.3链队——队列的链式表示 56
*3.3递归 57
3.3.1递归的定义 57
3.3.2递归的实现 59
3.3.3递归和迭代 64
3.3.4递归的消除 65
*3.4算法设计举例 68
第4章 串 73
4.1串的类型定义 73
4.2串的表示和实现 74
4.2.1串的顺序存储结构 75
4.2.2串的链式存储结构 76
*4.3串的模式匹配 77
4.3.1朴素的模式匹配算法 77
4.3.2首尾模式匹配算法 78
4.3.3 KMP算法 79
4.4串的应用举例 82
*4.5算法设计举例 83
第5章 数组和广义表 85
5.1数组的概念及其基本操作 85
5.2数组的顺序存储 86
5.3.1特殊矩阵 88
5.3矩阵的压缩存储 88
5.3.2稀疏矩阵 90
*5.4广义表 98
5.4.1 广义表的定义 98
5.4.2广义表的存储结构 99
*5.5算法设计举例 101
第6章树 105
6.1树的概念及操作 105
6.2 叉树 107
6.2.1二叉树的概念及操作 108
6.2.2二叉树的性质 109
6.2.3二叉树的存储结构 111
6.3二叉树的遍历 112
*6.4线索二叉树 116
6.5树和森林 121
6.5.1树的存储结构 121
6.5.2森林、树、二叉树 124
的相互转换 124
6.5.3树和森林的遍历 126
6.6.1最优二叉树（哈夫曼树） 127
6.6哈夫曼树及其应用 127
6.6.2哈夫曼编码 129
*6.7算法设计举例 132
第7章 图 137
7.1图的定义和术语 137
7.2图的存储结构 140
7.2.1数组表示法 140
7.2.2邻接表 141
*7.2.3十字链表 143
*7.2.4邻接多重表 144
7.3.1深度优先搜索 145
7.3图的遍历 145
7.3.2 广度优先搜索 146
7.4图的连通性问题 147
7.4.1图的连通分量和生成树 147
7.4.2最小生成树 149
7.5有向无环图及其应用 151
7.5.1拓扑排序 151
*7.5.2关键路径 154
7.6最短路径 158
7.6.1从某个源点到其他各顶点的最短路径 158
7.6.2每一对顶点之间的最短路径 161
*7.7网络流问题 163
*7.8算法设计举例 167
*第8章 动态存储管理 171
8.1概述 171
8.2可利用空间表及分配方法 172
8.3边界标识法 176
8.4伙伴系统 181
第9章集合 187
9.1概述 187
9.2线性表上的查找 188
9.2.1顺序表的查找 189
9.2.2有序表的查找 190
9.3索引表上的查找 196
9.4树表上的查找 197
9.4.1二叉排序树 197
9.4.2平衡二叉树 203
*9.4.3 B-树 210
*9.4.4键树 216
9.5哈希表 217
9.5.1哈希表查找的基本概念 217
9.5.2构造哈希函数的方法 218
9.5.3哈希冲突的解决方法 220
9.5.4哈希表的查找及分析 223
*9.6算法设计举例 225
第10章 排序 229
10.1概述 229
10.2插入排序 230
10.2.1直接插入排序 230
10.2.2折半插入排序 232
*10.2.3二路插入排序 232
*10.2.4表插入排序 234
10.2.5希尔排序 236
10.3交换排序 237
10.3.1起泡排序 237
10.3.2快速排序 238
10.4选择排序 241
10.4.1直接选择排序 241
10.4.2树形选择排序 242
10.4.3堆排序 243
10.5归并排序 246
10.6分配排序 247
10.7各种内部排序方法的比较 250
10.8外部排序 252
10.8.1文件管理 252
10.8.2外部排序的方法 253
10.8.3多路平衡归并排序 255
10.8.4置换选择排序 257
*10.8.5最佳归并树 261
*10.8.6磁带排序 262
*10.9算法设计举例 263
11.1文件的基本概念 267
第11章文件 267
11.2顺序文件 269
11.3索引文件 272
11.4索引顺序文件 273
11.4.1 ISAM文件 274
*11.4.2 VSAM 文件 276
11.5散列文件 278
*11.6多关键字文件 279
11.6.1多重表文件 279
11.6.2倒排文件 280
参考书目 282