第一章 引论 1
第一节 抽象数据类型、算法和C 1
一、抽象数据类型 1
二、ADT的描述 2
三、算法 4
四、算法的描述 5
第二节 数据的逻辑结构和存储结构 9
一、逻辑结构 9
二、存储结构 11
第三节 软件工程简介 13
一、分析阶段 14
二、设计阶段 16
三、实现阶段 25
四、维护阶段 26
第四节 算法的复杂性 26
一、算法的度量 26
二、算法的时间复杂性 28
第五节 递归算法设计与分析 31
一、递归算法设计 31
二、递归算法分析 34
小结 37
习题 37
第一节 一般的表 41
一、表的定义 41
第二章 线性数据结构 41
二、表的抽象运算 42
第二节 表的存储设计 44
一、表的链式存储 44
二、表的连续设计 46
第三节 表的实现 48
一、链接表的动态实现 48
二、链接表的静态实现 49
三、表的连续实现 50
四、其他形式的链表 55
第四节 表的应用 58
一、特长整数相加 58
二、多项式运算 60
第五节 栈 62
一、ADT栈 63
二、栈的设计与实现 64
三、栈的应用 70
第六节 队列 80
一、队列的设计 80
二、队列的存储设计 80
第七节 串 88
一、串的概念 88
二、串的设计 90
三、模式匹配 90
三、广义表的递归算法 98
二、存储设计 98
第八节 广义表 98
一、广义表的概念 98
小结 99
习题 100
上机题 101
第三章 树 102
第一节 树的概念 102
一、树的定义 102
二、树的实现 104
第二节 二叉树 106
一、二叉树的定义 106
二、二叉树的性质 108
三、二叉树的表示 109
第三节 二叉树的遍历 112
一、遍历算法 112
二、遍历算法的应用 114
第四节 线索二叉树 116
一、二叉树的线索化 117
二、线索二叉树的维护 119
三、一种新的二叉树存储表示 121
第五节 树、森林与二叉树 122
一、树、森林到二叉树的转换 122
二、树和森林的遍历 123
一、通讯编码问题 125
第六节 哈夫曼树及其应用 125
二、哈夫曼算法 126
三、编码和译码 128
小结 128
习题 129
上机题 130
第四章 集合 131
第一节 集合概述 131
一、用位向量实现集合 133
二、用链接表实现集合 133
三、数组表示 134
二、优先队列的实现 136
第二节 优先队列 136
一、优先队列概述 136
第三节 具有操作Merge和Find的集合 139
一、并查集合 140
二、等价问题 140
第四节 二叉查找树 144
一、二叉查找树概述 144
二、平衡的二叉查找树 148
三、B-树 154
第五节 字典与散列表 159
一、开散列 161
二、闭散列 163
三、散列函数效率的估计 165
小结 167
习题 167
上机题 168
第五章 图 169
第一节 图的概念 169
一、基本概念 169
二、图的抽象数据类型 171
第二节 图的表示 172
一、邻接矩阵 172
二、邻接表 172
第三节 图的遍历 173
一、深度优先遍历法 174
二、广度优先遍历法 175
第四节 最小代价生成树 176
一、生成树 176
二、最小代价生成树 177
第五节 最短路径 180
一、从某个顶点到其余各顶点的最短路径 180
二、求每一对顶点之间的最短路径 183
第六节 拓扑排序 184
一、拓扑排序概述 185
一、关键路径概述 187
第七节 关键路径 187
二、拓扑算法 187
二、求关键路径 188
第八节 网络流的算法 191
一、网络与流 192
二、可行流与最大流 193
三、可改进路P 193
四、寻找最大流的标号法 195
小结 197
习题 198
上机题 199
第一节 选择排序 200
第六章 排序技术 200
第二节 堆排序 204
第三节 冒泡排序 209
第四节 插入排序 210
第五节 快速排序 211
第六节 归并排序 215
第七节 基数排序 218
小结 221
习题 222
上机题 222
第七章 外排序和文件的组织 223
第一节 磁盘排序的方法 223
二、缓冲区的并行处理 224
一、多路平衡归并的实现 224
三、生成初始归并段 228
第二节 磁带归并 231
一、磁带归并段的分布 231
二、归并段的非均匀分布 232
第三节 文件的组织 234
一、文件的概念 234
二、文件的组织 235
小结 240
习题 240
一、直接具有递归特性 241
二、分析建立递归模型 241
第一节 递归技术 241
第八章 算法设计方法 241
第二节 分治算法 243
一、分治算法的基本思想 243
二、算法举例 243
第三节 动态规划法 247
一、动态规划法思想 247
二、算法举例 247
第四节 贪心法 252
一、贪心算法实例 252
二、贪心法的基本内容 254
一、回溯法的设计思路 255
第五节 回溯法 255
二、回溯法的解 256
小结 259
习题 259
第九章 并行算法设计与分析 260
第一节 并行模型 260
一、并行计算模型 260
二、并行算法的描述和性能分析 263
第二节 并行算法设计 264
一、广播与求前缀和 264
二、并行选择算法 265
—、图灵机 268
第一节 图灵机和非确定图灵机 268
第十章 NP-完全性 268
二、随机存取计算机 271
三、非确定图灵机 272
第二节 语言、P和NP、多项式转换和NP-完全问题类 274
一、语言、P和NP问题 274
二、多项式转换 274
三、可满足性问题是NP-完全的 276
第三节 NP完全问题的求解 279
一、确定NP-完全问题 279
二、穷举法 279
三、求次优解 282
参考文献 286