1引论 1
1.1什么是算法 1
1.2分析算法的准则 2
1.3描述算法的语言和基本的数据结构 5
思考题与习题 7
2分治与递归 9
2.1折半查找 10
2.2搜索二叉排序树 12
2.2.1二叉排序树的定义 13
2.2.2搜索二叉排序树 13
2.2.3向二叉排序树中插入新结点 14
2.2.4从二叉排序树中删除一个结点 16
2.2.5平衡的二叉排序树 16
2.3快速排序 19
2.4归并排序 22
2.5大整数乘法 24
2.6矩阵乘积的Strassen算法 27
思考题与习题 30
3贪心算法 32
3.1最小生成树 32
3.2单源最短路径 35
3.3旅行商问题 38
思考题与习题 41
4动态规划 43
4.1动态规划在最短路径中的应用 44
4.2矩阵连乘积问题 48
4.3求最长公共子序列 52
4.4凸多边形的最优三角形剖分 54
4.5旅行商问题 57
思考题与习题 60
5回溯法 63
5.1树的深度优先遍历 64
5.2数的全排列 65
5.3八皇后问题 69
5.4 0-1背包问题 72
5.5旅行商问题 75
思考题与习题 77
6分支限界法 78
6.1最小耗费搜索 79
6.2背包问题 83
6.3旅行商问题 85
思考题与习题 88
7.1.1字符串的概念 89
7.1 串概念及简单串匹配算法 89
7字符串 89
7.1.2串的匹配 90
7.1.3简单串模式匹配算法 91
7.2 Knuth-Morris-Pratt（KMP）算法 92
7.2.1 KMP算法 92
7.2.2改进的KMP算法 97
7.3 Boyer-Moore算法 98
7.3.1 Boyer-Moore算法 98
7.4 Karp-Rabin串匹配随机算法 99
思考题与习题 102
8 NP完全问题与近似算法 103
8.1确定型图灵机 104
8.2非确定型图灵机 107
8.3 Cook定理和NP完全理论 108
8.3.1 NP完全理论 110
8.3.2Cook定理 112
8.3.3若干NP完全问题 116
8.4 NP完全问题的近似算法 119
8.4.1 0-1背包问题 120
8.4.2旅行商问题 121
思考题与习题 124
9概率算法 126
9.1随机抽样 128
9.2判定素数的概率算法 130
9.2.1 Fermat素数测试法 130
9.2.2 Miller-Rabin素数判定概率算法 131
思考题与习题 132
10数据压缩算法 133
10.1 ASCII码压缩算法 134
10.2哈夫曼编码 135
10.3字典法 139
10.4 LZ算法 140
10.4.1 LZ77算法 141
10.4.2LZ78算法 143
10.4.3 LZW算法 145
思考题与习题 147
11公钥密码学基础 148
11.1公钥密码体制的应用与基本思想 149
11.2背包公钥密码 151
11.3 RSA公钥密码体制 152
10.4数字签名和Hash算法 154
思考题与习题 155
参考文献 156