第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 部分参考程序 参考文献 索引