算法设计与分析

第1章 算法分析基本概念

1.1 主要算法及程序实现

1.1.1 二分搜索

1.1.2 合并两个已排序的表

1.1.3 选择排序法

1.1.4 插入排序法

1.1.5 自底向上合并排序法

1.2 习题答案

1.3 上机实习题

1.3.1 选择排序法实现

1.3.2 自底向上合并排序法实现

第2章 堆和不相交集数据结构

2.1 主要算法及程序实现

2.1.1 堆上的运算

2.1.2 创建堆

2.1.3 堆排序法

2.1.4 Union-Find算法

2.2 习题答案

2.3 上机实习题

2.3.1 插入排序法实现

2.3.2 堆排序法实现

第3章 归纳法

3.1 主要算法及程序实现

3.1.1 选择排序法

3.1.2 插入排序法

3.1.3 基数排序法

3.2 习题答案

3.3 上机实习题

3.3.1 基数排序法实现

3.3.2 汉诺塔问题实现

第4章 分治法

4.1 主要算法及程序实现

4.1.1 寻找最大值和最小值

4.1.2 二分搜索

4.1.3 合并排序法

4.1.4 寻找中项和第k小元素

4.1.5 划分算法

4.1.6 快速排序法

4.2 习题答案

4.3 上机实习题

第5章 动态规划法

5.1 主要算法及程序实现

5.1.1 最长公共子序列问题

5.1.2 所有点对的最短路径问题

5.1.3 背包问题

5.2 习题答案

5.3 上机实习题

5.3.1 最长公共子序列问题实现

5.3.2 所有点对的最短路径问题实现

5.3.3 背包问题实现

第6章 贪心法

6.1 主要算法及程序实现

6.1.1 最短路径问题

6.1.2 最小耗费生成树（Kruskal算法）

6.1.3 最小耗费生成树（Prim算法）

6.1.4 文件压缩

6.2 习题答案

6.3 上机实习题

6.3.1 最短路径问题实现

6.3.2 最小耗费生成树（Prim算法）实现

6.3.3 Huffman算法实现

第7章 回溯法

7.1 主要算法及程序实现

7.1.1 图的3着色问题

7.1.2 4皇后问题

7.2 习题答案

7.3 上机实习题

7.3.1 图的3着色问题实现

7.3.2 4皇后问题实现

参考文献

本书根据课程教学要求编写，内容包括算法分析基本概念、堆和不相交集数据结构、归纳法、分治法、动态规划法、贪心法和回溯法。各章的主要算法（包括算法说明、算法伪代码描述、算法分析和算法实现程序）、习题解答和上机题以及书中出现的所有源程序均可以从清华大学出版社网站(www.tup.com.cn)下载。本书既可作为“算法设计与分析”课程的主讲教材，也可作为其辅助教材，还可以作为软件工程师学习算法设计的参考教材。