《算法设计和分析》求取 ⇩

第一章算法设计和分析的原则1

1.1 引言1

1.2 分析算法的若干准则2

算法一览表5

1.3搜索有序表——MEMBER（x,L）8

1.4 在一个表中找最大元和次大元12

1.5 在一个表中找最大元和最小元13

1.6 分治法，递推方程和递推不等式15

习题18

注解和参考文献21

第二章整序22

2.1 整序问题22

2.2 一些比较整序算法23

2.2.1 选择整序（selection sort）23

2.2.2 插入整序（jnsertion sort）24

2.2.3 冒泡整序（bubble sort）24

2.2.4 歇尔整序（Shell sort）25

2.2.5 快速整序（quick sort）26

2.2.6 堆整序（heap sort）29

2.3 比较整序的下界32

2.4 归并整序（merge sorting）34

2.5.1 带有足够大缓冲工作区（buffer）的线性时间算法37

2.5 一个稳定的最优时空界限的整序算法——Z算法37

2.5.2 非线性的原地归并算法39

2.5.3 稳定的线性最优空间归并算法——Z算法41

2.6 基数整序44

2.6.1 桶整序44

2.6.2 基数整序45

2.6.3＊ 不等长字符串的字典整序46

2.7 外部整序49

2.7.1 归并整序49

2.7.2 多路归并和替换选择53

2.7.3 初始归并段的生成55

2.7.4 多步归并整序57

2.7.5 广义斐波拉奇数列58

习题59

注解和参考文献60

3.1 二叉树搜索61

第三章搜索61

3.2 2-3-4树67

3.3 红-黑树69

习题72

注解和参考文献73

第四章集合运算74

4.1 引言74

4.2 散列76

4.3 二叉树上实现集合操作79

4.4 Union-Find程序83

4.5 平衡树模式90

4.6 字典与优先队列91

4.7 可并堆93

4.8 可毗连队列94

习题96

注解和参考文献98

第五章图的算法99

5.1 基本概念99

5.2 计算机中图的表示100

5.3 图的遍历101

5.4 强连通分支106

5.5 双连通分支108

5.6 两个中国人算法——回路判定113

5.7 最小生成树115

5.8 单源最短路径119

5.9 所有点对之间的最短路径121

510 传递闭包122

习题125

注解和参考文献126

6.1 概述127

第六章串匹配127

6.2 KMP算法128

6.3 BM算法132

6.4 RK算法135

习题137

注解和参考文献138

第七章几何问题算法139

7.1 一些初等几何问题的算法139

7.1.1 直线相交139

7.1.2 倾角计算140

7.1.3 是否包含在多边形内部141

7.2 求凸包142

7.2.1 卷包裹法143

7.2.2 Graham扫描法144

7.2.3 Floyed方法146

7.3.1 水平与垂直线的相交问题147

7.3 几何体相交问题147

7.3.2 一般的直线相交问题148

7.4 最近邻点问题149

7.5 Voronoi图152

习题153

注解和参考文献154

第八章算法设计技术155

8.1 分治法（Divide and Conquer）155

8.2 贪心法（Greedy）159

8.3 动态规划（Dynamic Programming）162

8.4 回溯法（Backtracking）169

8.5 分枝限界法（Branch and Bound）174

习题179

注解和参考文献181

第九章N？完全问题与近似算法183

9.1 图灵机（Turing Machine）183

9.2 不确定图灵机（Nondeterministic Turing Machine）187

9.3 ？与N？类191

9.4 COOK定理和N？完全问题196

9.5 N？完全问题的近似算法202

习题209

注解和参考文献210

第十章概率算法和算法的概率分析211

10.1 引言211

10.2 概率算法的定义212

10.3 求平面点集上最近点对的概率算法212

10.4 判定素数的概率算法217

10.4.1 概述217

10.4.2 求二个整数的最大公约数的欧几里德辗转相除法218

10.4.3 Fermat素数测试法220

10.4.4 Miller和Rabin素数测试概率算法221

10.5 ？222

10.6 Karp的有关算法概率分析的概念222

习题224

注解和参考文献224

第十一章VLSI中的并行算法225

11.1 脉动方式的并行处理225

11.2 分治方式的并行处理233

11.3 计算模型和下界理论241

习题249

注解和参考文献249

中文参考文献250

Bibliograph251