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

11 程序的规格说明与测试 1

111 程序的规格说明 1

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

113 程序测试 2

114 编程练习：排序的测试 2

115 随机数的生成 3

116 自动化测试 3

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

12 程序的运行时间度量 4

121取得CPU时间 4

122 统计排序函数的运行时间5

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

124 理解算法的时间复杂度 5

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

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

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

211标准库数据结构vector 8

212线性表vector的应用 12

213编程练习：vector的应用 12

214标准库数据结构list 13

215 线性表的应用 14

216 编程练习：线性表的应用 15

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

218 编程练习：集合运算 17

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

221 线性表抽象数据类型定义18

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

223 使用单链表表示线性表24

224 编程练习：熟悉单链表 24

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

23 串的应用 27

231数据结构串string 27

232 编程练习：索引表的生成 32

233 编程练习：一个行编辑器的实现34 小结 40

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

31 标准库栈的使用 41

311STL模板类stack 41

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

32 栈的实现 43

321 栈的定义 43

322 编程练习：栈的实现 44

33 队列的应用 45

331STL模板队列queue 45

332 队列应用例子 46

34 队列的实现 49

341 队列的定义 49

342 编程练习：队列的实现 50

35 栈和队列的应用 51

351 车厢调度问题 51

352 编程练习：车厢调度问题 54

353 编程练习：服务队列模拟问题 55 小结 56

第4 章递归 57

41 递归算法 57

411 递归函数的例子 57

412 一摞烙饼的排序 57

413 编程练习：递归 59

42 分治法 59

421 汉诺塔 59

422 归并排序 60

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

424 递归算法的分析 62

43 回溯 62

431 八皇后问题 62

432 迷宫问题 65

433 编程练习：回溯 67

小结 67

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

51 二叉树的表示68

511 二叉链表 68

512 二叉链表的构造 68

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

514 编程练习：二叉树的输出 70

515 二叉树的顺序结构 70

52 二叉树的遍历71

521 二叉树的深度优先遍历71

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

523 编程练习：二叉树的构造 74

524 二叉树的广度优先遍历74

525 编程练习：树的层次遍历 75

53 Human 编码的实现及其应用 75

531 Human 编码及其无损压缩 75

532实现基于Human编码的压缩和解压缩 75 小结 78

第6 章查找的实现与应用 79

61 顺序查找 79

611 简单查找 79

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

613 条件查找 81

614 函数对象 83

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

62 二分查找的应用 85

621 返回存在性的二分查找85

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

623 返回位置的二分查找 87

624 编程练习：查找中间数 90

63 二叉查找树 92

631 二叉查找树的插入 92

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

633 二叉查找树的查找 94

634 编程练习：二叉查找树的查找 95

635 二叉查找树的删除 96

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

64 平衡二叉查找树 98

641AVL树的归纳定义 98

642AVL树的表示和插入 98

65 线索二叉树 100

651 线索二叉树的表示100

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

66 散列表 102 小结 104

第7 章排序的实现与应用 105

71 快速排序 105

72 稳定排序 106

73 部分排序 106

74 堆排序 108

75 归并排序 109 小结 112

第8 章图算法及其应用 113

81 图的邻接矩阵表示 113

811图的邻接矩阵——C风格113

812图的邻接矩阵——C++风格 114

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

82 图的邻接表表示 119

821邻接表——C风格 119

822邻接表——C++风格120

823 编程练习：图的邻接表表示 121

83 拓扑排序 121

831 拓扑排序算法 121

832 拓扑排序应用举例122

84 广度优先遍历124

841 广度优先遍历算法124

842 广度优先遍历应用举例 125

85 深度优先遍历126

851 深度优先遍历算法126

852 深度优先遍历应用举例 127

86 最小生成树 129

861 最小生成树算法 129

862 最小生成树应用举例130

863 编程练习：最小生成树 133

87最短路径——从算法到代码 133

871 Dijkstra 算法 133

872 Dijkstra 算法的细化 133

873Dijkstra算法的C/C++实现 134

874 编程练习：最短路径 135

88 图论应用项目136

881 TSP 问题 136

882 医院选址问题 136

883 地铁建设问题 137

884 地铁乘车指引问题138 小结 139

第9章标准模板库STL简介 140

91 容器 140

911 容器的概念 140

912 顺序容器 141

913 联合容器 142

914 优先队列 146

92 迭代器 147

921C++标准库迭代器简介 148

922 迭代器的使用 150

923 编程练习：容器的应用 157

93 算法 157

931 不改变容器的算法159

932 改变容器的算法 162

933 排序算法 166

934 堆运算 169

935 集合运算 171

936 最大最小运算 173

94 函数对象 174

941遍历算法foreach的函数对象 174

942排序算法sort中的函数对象177

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

944 编程练习：函数对象 181

945 二分查找中的函数对象 182

946 编程练习：通用查找函数 183

947 预定义函数对象 183

948 可转换函数对象 185

949 编程练习：可转换函数对象的应用 188 小结 188

附录A问题和软装置列表189 A1 线性表和字符串的实现和应用 189 A2 栈与队列的实现和应用 189 A3 递归 189 A4 二叉树的实现和应用 190 A5 查找的实现与应用 190 A6 排序的实现与应用 190 A7 图算法及其应用 191

附录B实验报告参考格式192

附录C部分参考程序 193

参考文献 215

索引 216