数据结构与算法设计

出版者的话
前言
教学方案设计
第1章　引论1
　1.1　算法及其复杂性的概念1
　　1.1.1　算法与程序1
　　1.1.2　算法复杂性的概念2
　　1.1.3　算法复杂性的渐近性态3
　1.2　算法的表达与数据表示4
　　1.2.1　问题求解4
　　1.2.2　表达算法的抽象机制5
　1.3　抽象数据类型8
　　1.3.1　抽象数据类型的基本概念8
　　1.3.2　使用抽象数据类型的好处9
　1.4　数据结构和抽象数据类型10
　1.5　用C语言描述数据结构与算法11
　　1.5.1　变量和指针11
　　1.5.2　函数与参数传递12
　　1.5.3　结构13
　　1.5.4　动态存储分配14
　本章小结14
　习题15
　算法实验16
　　算法实验题1.1　哥德巴赫猜想问题16
　　算法实验题1.2　连续整数和问题16
第2章　表17
　2.1　表的基本概念17
　2.2　用数组实现表18
　2.3　用指针实现表22
　2.4　用间接寻址方法实现表25
　2.5　用游标实现表27
　2.6　循环链表32
　2.7　双链表34
　2.8　表的搜索游标37
　　2.8.1　用数组实现表的搜索游标38
　　2.8.2　单循环链表的搜索游标38
　2.9　应用40
　本章小结41
　习题41
　算法实验43
　　算法实验题2.1　向量分类问题43
　　算法实验题2.2　条形图轮廓问题43
第3章　栈45
　3.1　栈的基本概念45
　3.2　用数组实现栈46
　3.3　用指针实现栈48
　3.4　应用50
　本章小结52
　习题52
　算法实验54
　　算法实验题3.1　车皮编序问题54
　　算法实验题3.2　单柱Hanoi塔问题55
　　算法实验题3.3　多栈模拟问题55
　　算法实验题3.4　亲兄弟问题56
第4章　队列57
　4.1　队列的基本概念57
　4.2　用指针实现队列58
　4.3　用循环数组实现队列60
　4.4　应用64
　本章小结66
　习题66
　算法实验67
　　算法实验题4.1　组队列问题67
　　算法实验题4.2　双栈队列问题68
　　算法实验题4.3　猴子分桃问题69
　　算法实验题4.4　逆序表问题69
第5章　递归71
　5.1　递归的概念71
　5.2　递归程序设计76
　　5.2.1　分治与递归76
　　5.2.2　动态规划77
　　5.2.3　回溯与递归83
　5.3　模拟递归85
　5.4　应用87
　本章小结89
　习题89
　算法实验90
　　算法实验题5.1　删数问题90
　　算法实验题5.2　最优服务次序问题91
　　算法实验题5.3　最大k乘积问题91
　　算法实验题5.4　字符串比较问题92
第6章　排序与选择93
　6.1　简单排序算法93
　　6.1.1　冒泡排序94
　　6.1.2　插入排序94
　　6.1.3　选择排序95
　　6.1.4　简单排序算法的计算复杂性95
　6.2　快速排序算法96
　　6.2.1　算法基本思想及实现96
　　6.2.2　算法的性能97
　　6.2.3　随机快速排序算法98
　　6.2.4　非递归快速排序算法98
　　6.2.5　三数取中划分算法99
　　6.2.6　三划分快速排序算法100
　6.3　合并排序算法101
　　6.3.1　算法基本思想及实现101
　　6.3.2　对基本算法的改进102
　　6.3.3　自底向上的合并排序算法102
　　6.3.4　自然合并排序103
　　6.3.5　链表结构的合并排序算法103
　6.4　线性时间排序算法104
　　6.4.1　计数排序104
　　6.4.2　桶排序105
　6.5　中位数与第k小元素106
　　6.5.1　平均情况下的线性时间选择算法107
　　6.5.2　最坏情况下的线性时间选择算法108
　6.6　应用109
　本章小结110
　习题111
　算法实验112
　　算法实验题6.1　交换排序问题112
　　算法实验题6.2　DNA排序问题112
　　算法实验题6.3　输油管道问题113
　　算法实验题6.4　最优服务次序问题114
第7章　树115
　7.1　树的定义115
　7.2　树的遍历117
　7.3　树的表示法119
　　7.3.1　父结点数组表示法119
　　7.3.2　儿子链表表示法119
　　7.3.3　左儿子右兄弟表示法120
　7.4　二叉树120
　7.5　ADT二叉树122
　7.6　二叉树的实现123
　　7.6.1　二叉树的顺序存储结构123
　　7.6.2　二叉树的结点度表示法124
　　7.6.3　用指针实现二叉树124
　7.7　线索二叉树128
　7.8　应用129
　本章小结132
　习题133
　算法实验135
　　算法实验题7.1　层序列表问题135
　　算法实验题7.2　最近公共祖先问题135
　　算法实验题7.3　子树问题136
　　算法实验题7.4　同构二叉树问题136
　　算法实验题7.5　后序中序遍历问题137
第8章　集合138
　8.1　以集合为基础的抽象数据类型138
　　8.1.1　集合的定义和记号138
　　8.1.2　定义在集合上的基本运算139
　8.2　用位向量实现集合140
　8.3　用链表实现集合142
　8.4　应用145
　本章小结146
　习题146
　算法实验147
　　算法实验题　半数集问题147
第9章　符号表148
　9.1　实现符号表的简单方法148
　9.2　用散列表实现符号表149
　　9.2.1　开散列150
　　9.2.2　闭散列151
　　9.2.3　散列函数及其效率155
　　9.2.4　闭散列的重新散列技术156
　9.3　应用156
　本章小结157
　习题158
　算法实验158
　　算法实验题9.1　伪随机排列问题158
　　算法实验题9.2　字符串散列问题159
　　算法实验题9.3　英文文本分析问题159
　　算法实验题9.4　最长模式串问题160
第10章　字典161
　10.1　字典的定义161
　10.2　用数组实现字典162
　10.3　用二叉搜索树实现字典162
　10.4　AVL树169
　　10.4.1　AVL树的定义和性质169
　　10.4.2　旋转变换170
　　10.4.3　AVL树的插入运算173
　　10.4.4　AVL树的删除运算174
　10.5　应用177
　本章小结179
　习题179
　算法实验180
　　算法实验题10.1　装箱问题180
　　算法实验题10.2　电路板连线问题181
　　算法实验题10.3　辞典问题182
第11章　优先队列183
　11.1　优先队列的定义183
　11.2　用字典实现优先队列184
　11.3　优先级树和堆184
　11.4　用数组实现堆186
　11.5　可并优先队列188
　　11.5.1　左偏树的定义188
　　11.5.2　用左偏树实现可并优先队列189
　11.6　应用192
　本章小结195
　习题195
　算法实验196
　　算法实验题11.1　多机调度问题196
　　算法实验题11.2　整数字典问题197
　　算法实验题11.3　最小权语言问题197
　　算法实验题11.4　二叉搜索堆问题198
第12章　并查集199
　12.1　并查集的定义及其简单实现199
　12.2　用父结点数组实现并查集200
　12.3　应用203
　本章小结204
　习题204
　算法实验205
　　算法实验题12.1　二进制方程问题205
　　算法实验题12.2　网络连通问题206
　　算法实验题12.3　朋友问题206
　　算法实验题12.4　无向图的连通分支问题207
第13章　图208
　13.1　图的基本概念208
　13.2　抽象数据类型图211
　13.3　图的表示法211
　　13.3.1　邻接矩阵表示法211
　　13.3.2　邻接表表示法212
　　13.3.3　紧缩邻接表213
　13.4　用邻接矩阵实现图213
　　13.4.1　用邻接矩阵实现赋权有向图213
　　13.4.2　用邻接矩阵实现赋权无向图215
　　13.4.3　用邻接矩阵实现有向图216
　　13.4.4　用邻接矩阵实现无向图216
　13.5　用邻接表实现图217
　　13.5.1　用邻接表实现有向图217
　　13.5.2　用邻接表实现无向图219
　　13.5.3　用邻接表实现赋权有向图220
　　13.5.4　用邻接表实现赋权无向图222
　13.6　图的遍历223
　　13.6.1　广度优先搜索223
　　13.6.2　深度优先搜索225
　13.7　最短路径226
　　13.7.1　单源最短路径226
　　13.7.2　所有顶点对之间的最短路径229
　13.8　最小支撑树230
　　13.8.1　最小支撑树性质230
　　13.8.2　Prim算法231
　　13.8.3　Kruskal算法233
　13.9　图匹配234
　本章小结236
　习题237
　算法实验238
　　算法实验题13.1　图的2着色问题238
　　算法实验题13.2　赋权有向图中心问题239
　　算法实验题13.3　最长简单路径问题239
　　算法实验题13.4　计算机网络问题240
　　算法实验题13.5　差分约束问题240
　　算法实验题13.6　有截止时间的工作排序问题241
参考文献243