第1章 程序测试与运行时间度量

1.1 程序的规格说明与测试

1.1.1 程序的规格说明

1.1.2 编程练习：排序函数的规格说明

1.1.3 程序测试

1.1.4 编程练习：排序的测试

1.1.5 随机数的生成

1.1.6 自动化测试

1.1.7 编程练习：排序的自动测试

1.2 程序的运行时间度量

1.2.1 取得CPU时间

1.2.2 统计排序函数的运行时间

1.2.3 编程练习：排序的运行时间度量

1.2.4 理解算法的时间复杂度

1.2.5 编程练习：最大连续子序列和算法运算时间的比较

小结

第2章 线性表和串的实现及其应用

2.1 标准库数据结构vector和list的使用

2.1.1 标准库数据结构vector

2.1.2 线性表vector的应用

2.1.3 编程练习：vector的应用

2.1.4 标准库数据结构list

2.1.5 线性表的应用

2.1.6 编程练习：线性表的应用

2.1.7 编程练习：多项式的表示和运算

2.1.8 编程练习：集合运算

2.2 抽象数据类型线性表的实现及其测试

2.2.1 线性表抽象数据类型定义

2.2.2 编程练习：使用数组表示线性表

2.2.3 使用单链表表示线性表

2.2.4 编程练习：熟悉单链表

2.2.5 编程练习：线性表的单链表实现

2.3 串的应用

2.3.1 数据结构串string

2.3.2 编程练习：索引表的生成

2.3.3 编程练习：一个行编辑器的实现

小结

第3章 栈与队列的实现和应用

3.1 标准库栈的使用

3.1.1 STL模板类stack

3.1.2 编程练习：熟悉栈的操作和栈的应用

3.2 栈的实现

3.2.1 栈的定义

3.2.2 编程练习：栈的实现

3.3 队列的应用

3.3.1 STL模板队列queue

3.3.2 队列应用例子

3.4 队列的实现

3.4.1 队列的定义

3.4.2 编程练习：队列的实现

3.5 栈和队列的应用

3.5.1 车厢调度问题

3.5.2 编程练习：车厢调度问题

3.5.3 编程练习：服务队列模拟问题

小结

第4章 递归

4.1 递归算法

4.1.1 递归函数的例子

4.1.2 一摞烙饼的排序

4.1.3 编程练习：递归

4.2 分治法

4.2.1 汉诺塔

4.2.2 归并排序

4.2.3 编程练习：归并排序的实现

4.2.4 递归算法的分析

4.3 回溯

4.3.1 八皇后问题

4.3.2 迷宫问题

4.3.3 编程练习：回溯

小结

第5章 二叉树的实现和应用

5.1 二叉树的表示

5.1.1 二叉链表

5.1.2 二叉链表的构造

5.1.3 编程练习：二叉树的二叉链表表示

5.1.4 编程练习：二叉树的输出

5.1.5 二叉树的顺序结构

5.2 二叉树的遍历

5.2.1 二叉树的深度优先遍历

5.2.2 编程练习：二叉树的遍历和构造

5.2.3 编程练习：二叉树的构造

5.2.4 二叉树的广度优先遍历

5.2.5 编程练习：树的层次遍历

5.3 Huffman编码的实现及其应用

5.3.1 Huffman编码及其无损压缩

5.3.2 实现基于Huffman编码的压缩和解压缩

小结

第6章 查找的实现与应用

6.1 顺序查找

6.1.1 简单查找

6.1.2 编程练习：顺序查找的应用和实现

6.1.3 条件查找

6.1.4 函数对象

6.1.5 编程练习：条件查找的应用

6.2 二分查找的应用

6.2.1 返回存在性的二分查找

6.2.2 编程练习：二分查找的应用和实现

6.2.3 返回位置的二分查找

6.2.4 编程练习：查找中间数

6.3 二叉查找树

6.3.1 二叉查找树的插入

6.3.2 编程练习：二叉查找树的插入

6.3.3 二叉查找树的查找

6.3.4 编程练习：二叉查找树的查找

6.3.5 二叉查找树的删除

6.3.6 编程练习：二叉查找树的删除

6.4 平衡二叉查找树

6.4.1 AVL树的归纳定义

6.4.2 AVL树的表示和插入

6.5 线索二叉树

6.5.1 线索二叉树的表示

6.5.2 编程练习：线索二叉树的遍历和插入

6.6 散列表

小结

第7章 排序的实现与应用

7.1 快速排序

7.2 稳定排序

7.3 部分排序

7.4 堆排序

7.5 归并排序

小结

第8章 图算法及其应用

8.1 图的邻接矩阵表示

8.1.1 图的邻接矩阵——C风格

8.1.2 图的邻接矩阵——C++风格

8.1.3 编程练习：图的邻接矩阵表示

8.2 图的邻接表表示

8.2.1 邻接表——C风格

8.2.2 邻接表——C++风格

8.2.3 编程练习：图的邻接表表示

8.3 拓扑排序

8.3.1 拓扑排序算法

8.3.2 拓扑排序应用举例

8.4 广度优先遍历

8.4.1 广度优先遍历算法

8.4.2 广度优先遍历应用举例

8.5 深度优先遍历

8.5.1 深度优先遍历算法

8.5.2 深度优先遍历应用举例

8.6 最小生成树

8.6.1 最小生成树算法

8.6.2 最小生成树应用举例

8.6.3 编程练习：最小生成树

8.7 最短路径——从算法到代码

8.7.1 Dijkstra算法

8.7.2 Dijkstra算法的细化

8.7.3 Dijkstra算法的C/C++实现

8.7.4 编程练习：最短路径

8.8 图论应用项目

8.8.1 TSP问题

8.8.2 医院选址问题

8.8.3 地铁建设问题

8.8.4 地铁乘车指引问题

小结

第9章 标准模板库STL简介

9.1 容器

9.1.1 容器的概念

9.1.2 顺序容器

9.1.3 联合容器

9.1.4 优先队列

9.2 迭代器

9.2.1 C++标准库迭代器简介

9.2.2 迭代器的使用

9.2.3 编程练习：容器的应用

9.3 算法

9.3.1 不改变容器的算法

9.3.2 改变容器的算法

9.3.3 排序算法

9.3.4 堆运算

9.3.5 集合运算

9.3.6 最大最小运算

9.4 函数对象

9.4.1 遍历算法for_each的函数对象

9.4.2 排序算法sort中的函数对象

9.4.3 顺序查找算法中的函数对象

9.4.4 编程练习：函数对象

9.4.5 二分查找中的函数对象

9.4.6 编程练习：通用查找函数

9.4.7 预定义函数对象

9.4.8 可转换函数对象

9.4.9 编程练习：可转换函数对象的应用

小结

附录A 问题和软装置列表

A1 线性表和字符串的实现和应用

A2 栈与队列的实现和应用

A3 递归

A4 二叉树的实现和应用

A5 查找的实现与应用

A6 排序的实现与应用

A7 图算法及其应用

附录B 实验报告参考格式

附录C 部分参考程序

参考文献

索引