第一章 绪论 1
1.1 什么是数据结构 1
1.2 为什么要学习数据结构 3
1.3 数据的逻辑结构 4
1.4 数据的存储结构 5
1.5 数据的运算 7
第二章 顺序表和链表 11
2.1 顺序表的逻辑结构 11
2.2 顺序表的存储结构 12
2.3 顺序表的运算 12
2.4 Josephus问题 15
2.5 单链表 17
2.6 单链表的运算 19
2.7 循环链表 21
2.8 双向链表 22
2.9 多项式相加 24
习题 26
第三章 栈与队列 28
3.1 栈的定义 28
3.2 栈的表示及实现 28
3.3 表达式求值 31
3.4 队列的定义及其基本运算 35
3.5 链式队列 38
3.6 限制存取点的表 39
习题 40
第四章 串 41
4.1 串的逻辑特性 41
4.2 串的存储表示 42
4.3 串的运算 45
4.4 串运算的实现 47
4.5 模式匹配 49
习题 56
第五章 数组和广义表 58
5.1 数组 58
5.2 数组的顺序存储结构和寻址公式 59
5.3 矩阵的压缩存储 61
5.4 数组的应用举例 69
5.5 广义表的定义 75
5.6 广义表的存储结构 76
习题 79
第六章 树 82
6.1 树的概念 82
6.2 二叉树 84
6.3 遍历二叉树 89
6.4 线索二叉树 96
6.5 树和森林 103
6.6 哈夫曼(Huffman)树及其应用 114
6.7 计算二叉树的数目 121
6.8 树的应用 124
习题 128
第七章 图 131
7.1 图的定义和基本术语 131
7.2 图的存储结构 134
7.3 图的遍历和求图的连通分量 140
7.4 生成树和最小(代价)生成树 144
7.5 最短路径和传递闭包 150
7.6 拓扑排序 159
7.7 关键路径 164
习题 169
第八章 查找 171
8.1 线性查找 172
8.2 折半查找 173
8.3 分块查找 176
8.4 二叉排序树查找 178
8.5 最佳二叉排序树 182
8.6 平衡二叉排序树 188
8.7 B—树和B+树 191
8.8 数字查找树 196
8.9 Hash查找法 199
习题 209
第九章 内部排序 211
9.1 基本概念 211
9.2 插入排序 212
9.3 选择排序 217
9.4 交换排序 226
9.5 归并排序 232
9.6 基数排序 235
习题 239
第十章 外部排序 241
10.1 外部排序的主要过程 241
10.2 K路归并 242
10.3 并行操作的缓冲区处理 246
10.4 初始归并段的生成 253
10.5 最佳归并树 258
10.6 磁带归并排序 261
习题 264
第十一章 文件 266
11.1 文件的基本概念 266
11.2 顺序文件 268
11.3 索引文件 270
11.4 索引顺序文件 271
11.5 散列文件 276
11.6 链接文件和多重链表文件 283
11.7 倒排文件 285
习题 286
第十二章 抽象数据类型概述 288
12.1 数据抽象的背景与动机 288
12.2 抽象数据类型的定义 292
12.3 数据抽象和模块 297
参考书目 303