第一章 引论 1
第一节 抽象数据类型 1
一、程序设计的一个基本原则是抽象 1
二、抽象数据类型 1
第二节 数据结构 2
一、基本术语 3
二、数据的逻辑结构 3
三、数据的存储结构 4
第三节 算法的概念 4
第四节 算法设计基本技术 6
一、分治法 6
二、贪心法 7
三、动态规划法 8
四、基本检索与遍历技术 8
五、回溯法 9
第五节 算法分析 9
一、算法复杂度 9
二、时间复杂度 9
三、空间复杂度 17
四、分析算法的意义 17
习题 18
第二章 线性表 22
第一节 线性表 22
一、线性表的逻辑结构 22
二、线性表抽象数据类型 23
第二节 线性表的顺序存储结构 23
一、顺序表 24
二、顺序表类的实现 25
三、顺序存储结构的特点 29
第三节 线性表的链式存储结构 30
一、单链表 30
二、单链表类的实现 32
三、循环链表 39
四、双向链表 40
五、链式存储结构的特点 43
第四节 线性表的应用 44
一、一元多项式相加 44
二、约瑟夫问题 49
习题 51
第三章 栈和队列 54
第一节 栈 54
一、栈的基本概念 54
二、栈的顺序存储结构 55
三、栈的链式存储结构 57
四、顺序栈和链栈的比较 59
五、栈的应用 59
第二节 递归和递归消除 67
第三节 队列 71
一、队列的基本概念 71
二、队列的顺序存储 72
三、队列的链式存储 76
习题 82
第四章 串 84
第一节 基本概念 84
第二节 字符串的存储结构 85
一、顺序存储 85
二、链式存储 86
第三节 串类的实现 88
一、顺序串类的实现 88
二、链串类的实现 99
习题 101
第五章 数组和广义表 103
第一节 数组的逻辑结构定义 103
第二节 数组的顺序存储 104
第三节 矩阵的存储 106
一、特殊矩阵 106
二、稀疏矩阵 108
第四节 广义表的定义 111
第五节 广义表的存储 112
第六节 广义表的递归算法 113
一、广义表的深度 114
二、复制广义表 115
习题 115
第六章 树 118
第一节 树的基本概念 118
一、树的定义 118
二、树的逻辑表示方法 119
三、树的基本术语 120
四、树的性质 122
第二节 树的存储结构 122
—、双亲表示法 122
二、孩子表示法 123
三、孩子兄弟表示法 124
第三节 二叉树 125
一、二叉树的定义 125
二、二叉树的抽象数据类型 125
三、二叉树的性质 126
四、二叉树的存储结构 128
第四节 树、森林与二叉树的转换 131
第五节 树的遍历 134
一、二叉树的遍历 135
二、二叉树遍历的应用 142
三、树和森林的遍历 143
第六节 线索二叉树 145
一、中序线索树的建立 147
二、在中序线索树中查找某结点的直接前趋 148
三、在中序线索树中查找某结点的直接后继 148
四、中序线索树的遍历 149
五、在中序线索树中插入结点 149
第七节 树的应用 151
习题 158
第七章 图 161
第一节 图的定义和有关术语 161
第二节 图的存储结构 165
一、邻接矩阵 165
二、邻接表 167
第三节 图的遍历 170
一、深度优先遍历 171
二、广度优先遍历 172
第四节 生成树和最小生成树 173
一、无向连通图的生成树 173
二、带权无向连通图的最小生成树 174
第五节 最短路径 178
一、单源最短路径 178
二、每对顶点之间的最短路径 181
第六节 拓扑排序 183
一、拓扑排序 183
二、拓扑排序算法 184
第七节 关键路径 185
习题 187
第八章 集合与查找 190
第一节 集合及其运算 190
第二节 线性表及其查找 192
一、顺序查找 192
二、二分查找 192
三、其他线性表的查找 193
第三节 树结构的查找 194
一、二叉检索树 194
二、平衡二叉检索树 199
第四节 散列存储与散列查找 202
一、散列存储 202
二、散列函数 203
三、解决冲突 205
四、散列查找的效率 210
第五节 索引存储 211
习题 213
第九章 内部排序 214
第一节 基本概念 214
第二节 插入排序 215
一、直接插入排序 215
二、折半插入排序 217
三、希尔排序 218
第三节 选择排序 220
一、直接选择排序 220
二、堆排序 222
第四节 交换排序 229
一、冒泡排序 229
二、快速排序 231
第五节 归并排序 235
第六节 分配排序 238
一、桶排序 238
二、基数排序 240
第七节 内部排序方法的比较与选择 243
习题 244
第十章 文件与外排序 247
第一节 磁盘与文件管理 247
一、磁盘 247
二、文件的操作系统视图 248
三、文件 249
第二节 文件的组织技术 250
—、输入顺序文件 250
二、散列文件 250
三、线性结构索引文件 251
四、树结构索引文件 255
第三节 外排序 258
一、外排序过程概述 258
二、多路归并 259
三、置换-选择排序和最优归并 261
习题 264
第十一章 算法分析技术 266
第一节 对数与级数求和 266
一、对数 266
二、级数求和 266
第二节 递归过程与递归方程 268
一 、递归过程的分析 268
二、一类递归方程的解 268
第三节 算法复杂性分析示例 271
一、二分查找的时间复杂度 271
二、以比较为基础的检索的时间下界 272
三、快速排序的分析 272
四、排序算法的时间下界 274
五、二叉树遍历的复杂度 275
习题 275
第十二章 多项式时间可计算性 277
第一节 易解的问题和难解的问题 277
第二节 P与NP问题类 277
一、不确定性算法 277
二、P与NP问题类 280
第三节 NP完全性和COOK定理 280
一、多项式归约 280
二、NP困难和NP完全问题 280
三、S．A．COOK定理 281
第四节 若干NP完全问题 281
一、命题逻辑的可满足性问题和重言式问题 281
二、无向图的完全图(团集)问题、离集问题和顶点覆盖问题 282
三、有向图的回路的边集、顶集问题 282
四、H回路问题和旅行销售员问题 283
五、O-1整数规划问题 283
六、集合族的粘连问题、隔衬问题、集合覆盖问题 283
七、着色问题和离集、团集覆盖问题 284
八、集合的恰当覆盖及由它推出的一些NP完全性问题 284
九、装包问题、排序问题、等分问题及最大分割问题 285
习题 286
参考文献 287