目录 1
第一章 绪论 1
§1.1 数据结构和算法 1
§1.2 类PASCAL语言 2
第二章 线性表和向量 5
§2.1 线性表及其存贮结构 5
§2.1.1 线性表 5
§2.1.2 向量 6
§2.1.3 线性表的插入和删除运算 6
§2.1.4 线性表的应用实例——仑库管理系统 8
§2.2 栈和队列 12
§2.2.1 栈 12
§2.2.2 栈的应用举例 14
Ⅰ 学生业务档案系统 14
Ⅱ 计算表达式 16
§2.2.3 队 20
§2.3 数组 23
§2.3.1 数组及其存贮结构 23
§2.3.2 稀疏矩阵 24
习题 31
第三章 链表 33
§3.1 单链表 33
§3.1.1 单链表 33
§2.1.2 单链表的插入和删除运算 34
§3.1.3 单链表的应用实例——仑库管理系统 38
§3.2 循环链表 42
§3.3 多项式的算术运算 43
Ⅰ 利用单链表结构 43
Ⅱ 利用循环链表结构 46
§3.4 双向链表 48
§3.5 链表的应用实例——自动订飞机票系统 50
§3.6 稀疏矩阵的十字链表结构 54
§3.7 广义表和多重链表 57
习题 58
第四章 树 61
§4.1 基本术语 61
§4.2 树的存贮结构 62
§4.3 二叉树 62
§4.3.1 二叉树的定义 62
§4.3.2 二叉树的基本性质 63
§4.3.3 二叉树的存贮结构 64
§4.4 递归与二叉树遍历 66
§4.4.1 先序遍历 66
§4.4.2 中序遍历 68
§4.4.3 后序遍历 70
§4.5 线索树 72
§4.6.1 树的二叉树表示 75
§4.6 树的二叉树表示和运算 75
§4.6.2 树的插入和删除 77
§4.7 树的应用 82
§4.7.1 二叉排序树 82
§4.7.2 哈夫曼树 83
§4.7.3 判定树 86
§4.8 二叉树的应用实例——银行财务实时处理系统 87
第五章 图 93
§5.1 基本术语 93
§5.2 图的存贮结构 94
§5.2.1 邻接矩阵 95
§5.2.2 邻接表 95
习题 96
§5.2.3 邻接多重表 97
§5.3 图的遍历和求图的连通分量 98
§5.3.1 深度优先搜索 99
§5.3.2 宽度优先搜索 101
§5.3.3 求图的连通分量 102
§5.4 生成树和最小花费生成树 103
§5.5 最短路径 106
§5.5.1 从某个源点到其余各顶点的最短路径 106
§5.5.2 每一对顶点之间的最短路径 109
§5.6 AOV—网与拓扑分类 112
§5.7 AOE—网与关键路径 116
§5.8 寻求关键路径的应用举例 119
习题 128
第六章 集合操作 130
§6.1 对集合的基本操作 130
§6.2 链表结构与顺序搜索 130
§6.3 二元搜索与二元搜索树 131
§6.4 最佳二元搜索树 133
§6.5 UNION——FIND操作 138
§6.6 字典和优先队 143
§6.7 Hash（杂凑）技术 148
§6.7.1 Hash函数的构造方法 150
§6.7.2 冲突的处理 152
习题 156
第七章 内部分类 158
§7.1 插入分类 158
§7.2 选择分类 160
§7.3 冒泡分类 161
§7.4 比较分类 163
§7.5 堆积分类 164
§7.6 2路归并分类 167
§7.7 快速分类 169
§7.8 基数分类 172
习题 174
第八章 外部分类 175
§8.1 外部分类的主要过程 175
§8.2 磁盘分类 176
§8.2.1 k路归并 176
§8.2.2 并行操作的缓冲区处理 179
§8.2.3 初始归并段的产生 186
§8.3 磁带分类 191
§8.3.1 平衡归并分类 191
§8.3.2 多步归并分类 193
习题 194
第九章 算法分析技术 195
§9.1 算法分析简介 195
§9.2 循环程序的分析 196
§9.3 递归算法的分析 197
§9.3.1 递归方程 197
§9.3.2 递归算法的分析 199
习题 202
第十章 算法设计技术 203
§10.1 分割求解法 203
求集合的最大、最小元 203
§10.2 动态规划 206
单源路径问题 206
§10.3 子目标法 209
吉普车问题 209
§10.4 探索法 211
旅游花费问题 211
§10.5 回溯法 213
组合锁问题 213
§10.6 分枝与限界 215
货郎担问题 215
习题 226