第1章 绪论 1
1.1引言 1
1.2基本概念与术语 5
1.3数据的逻辑结构与存储结构 6
1.4数据类型与抽象数据类型 10
1.4.1数据类型 10
1.4.2抽象数据类型 10
1.5算法和算法分析 11
1.5.1算法定义与特性 12
1.5.2算法描述 13
1.5.3算法定量分析与评价 14
1.6习题 19
第2章 线性表 20
2.1线性表的逻辑结构 20
2.1.1线性表的定义与特征 20
2.1.2线性表的基本操作 21
2.2线性表的顺序存储结构 21
2.2.1顺序表定义与存储结构 21
2.2.2顺序表上基本运算的实现 23
2.2.3顺序表应用 28
2.3线性表的链式存储 30
2.3.1单链表 30
2.3.2单链表上基本运算的实现 32
2.3.3循环链表 42
2.3.4双向链表 44
2.3.5静态链表 46
2.3.6单链表应用 50
2.4顺序表和链表的比较 57
2.5习题 58
第3章 栈和队列 59
3.1栈 59
3.1.1栈的定义及基本操作 59
3.1.2顺序栈及基本操作的实现 61
3.1.3链栈 66
3.2栈的应用 68
3.3队列 73
3.3.1队列的定义及基本运算 73
3.3.2顺序队列及基本运算 74
3.3.3链队列 79
3.4队列应用 82
3.5习题 87
第4章 字符串与模式匹配 88
4.1串及其基本运算 88
4.1.1串的基本概念 88
4.1.2串的基本运算 89
4.2串的存储及基本运算 90
4.2.1串的定长顺序存储 90
4.2.2串的堆分配存储 93
4.2.3串的块链式存储 96
4.3模式匹配 97
4.3.1简单的模式匹配算法BF 98
4.3.2模式匹配算法KMP 99
4.4习题 103
第5章 数组和广义表 104
5.1数组的定义与存储 104
5.1.1数组的定义 104
5.1.2数组的顺序存储结构 105
5.2特殊矩阵的压缩存储 107
5.2.1对称矩阵的压缩存储 107
5.2.2三角矩阵的压缩存储 108
5.2.3对角矩阵的压缩存储 109
5.3稀疏矩阵 110
5.3.1三元组表示法 110
5.3.2稀疏矩阵的十字链表存储 116
5.4广义表 121
5.4.1广义表的定义 121
5.4.2广义表的基本操作 122
5.4.3广义表的存储结构 122
5.4.4广义表基本操作的实现 125
5.5习题 127
第6章 树与二叉树 129
6.1树 129
6.1.1树的定义 129
6.1.2树的逻辑表示法 130
6.1.3树的基本术语 131
6.1.4树形结构的逻辑特征 132
6.2二叉树 133
6.2.1二叉树概念 133
6.2.2二叉树的性质 134
6.3二叉树的存储结构 138
6.3.1顺序存储结构 138
6.3.2链式存储结构 140
6.4二叉树的遍历 141
6.4.1二叉树的遍历方法及递归实现 141
6.4.2二叉树非递归遍历 144
6.4.3二叉树的基本操作 148
6.4.4遍历线性序列恢复二叉树 152
6.5线索二叉树 153
6.5.1线索二叉树的定义及结构 153
6.5.2线索二叉树的基本运算 157
6.6哈夫曼树—最优二叉树 162
6.6.1哈夫曼树的有关概念 162
6.6.2哈夫曼树的构造 163
6.6.3哈夫曼算法的实现 165
6.6.4哈夫曼编码 167
6.7树与森林 171
6.7.1树、森林到二叉树的转换 171
6.7.2树的存储结构 174
6.7.3树的遍历 176
6.8习题 177
第7章图 178
7.1图的概念与相关术语 178
7.2图的存储表示 181
7.2.1邻接矩阵 182
7.2.2邻接表 184
7.2.3十字链表 187
7.2.4邻接多重表 189
7.3图的遍历 190
7.3.1深度优先搜索 191
7.3.2广度优先搜索 195
7.4图的连通性 198
7.4.1无向图的连通性 198
7.4.2有向图的连通性 199
7.4.3生成树和生成森林 199
7.4.4关结点和重连通分量 201
7.5最小生成树 204
7.5.1最小生成树的基本概念 204
7.5.2普利姆（Prim）算法 205
7.5.3 Kruskal算法 208
7.6最短路径 210
7.6.1从一个源点到其他各点的最短路径 210
7.6.2每一对顶点之间的最短路径 213
7.7有向无环图及其应用 215
7.7.1有向无环图的概念 215
7.7.2 AOV网与拓扑排序 216
7.7.3 AOE图与关键路径 220
7.8习题 224
第8章 查找 226
8.1基本概念与术语 226
8.2静态查找表 227
8.2.1顺序查找 227
8.2.3有序表的折半查找 228
8.2.3分块查找 231
8.3动态查找表 232
8.3.1二叉排序树定义 233
8.3.2二叉排序树运算 234
8.3.3平衡二叉树（AVL树） 238
8.3.4 B—树和B＋树 245
8.4哈希查找 251
8.4.1哈希表 251
8.4.2常用的哈希函数 252
8.4.3处理冲突的方法 253
8.4.4哈希表的查找分析 256
8.5习题 257
第9章 排序 259
9.1排序的基本概念 259
9.2插入排序 261
9.2.1直接插入排序 261
9.2.2折半插入排序 263
9.2.3希尔排序 264
9.3交换排序 266
9.3.1冒泡排序 266
9.3.2快速排序 267
9.4选择排序 270
9.4.1直接选择排序 270
9.4.2树形选择排序 272
9.4.3堆排序 272
9.5归并排序 279
9.5.1两路归并排序 279
9.5.2归并排序 280
9.6分配排序 282
9.6.1箱排序 282
9.6.2桶排序 282
9.6.3基数排序 284
9.7排序方法的比较 288
9.8外排序 290
9.8.1外部排序的方法 290
9.8.2多路平衡归并的实现 291
9.9习题 294
参考文献 295