数据结构与算法实验实践教程PDF电子书下载

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

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

1.1.1 程序的规格说明 1

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

1.1.3 程序测试 2

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

1.1.5 随机数的生成 3

1.1.6 自动化测试 3

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

1.2 程序的运行时间度量 4

1.2.1 取得CPU时间 4

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

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

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

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

小结 7

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

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

2.1.1 标准库数据结构vector 8

2.1.2 线性表vector的应用 12

2.1.3 编程练习：vector的应用 12

2.1.4 标准库数据结构list 13

2.1.5 线性表的应用 14

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

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

2.1.8 编程练习：集合运算 17

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

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

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

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

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

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

2.3 串的应用 27

2.3.1 数据结构串string 27

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

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

小结 40

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

3.1 标准库栈的使用 41

3.1.1 STL模板类stack 41

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

3.2 栈的实现 43

3.2.1 栈的定义 43

3.2.2 编程练习：栈的实现 44

3.3 队列的应用 45

3.3.1 STL模板队列queue 45

3.3.2 队列应用例子 46

3.4 队列的实现 49

3.4.1 队列的定义 49

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

3.5 栈和队列的应用 51

3.5.1 车厢调度问题 51

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

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

小结 56

第4章 递归 57

4.1 递归算法 57

4.1.1 递归函数的例子 57

4.1.2 一摞烙饼的排序 57

4.1.3 编程练习：递归 59

4.2 分治法 59

4.2.1 汉诺塔 59

4.2.2 归并排序 60

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

4.2.4 递归算法的分析 62

4.3 回溯 62

4.3.1 八皇后问题 62

4.3.2 迷宫问题 65

4.3.3 编程练习：回溯 67

小结 67

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

5.1 二叉树的表示 68

5.1.1 二叉链表 68

5.1.2 二叉链表的构造 68

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

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

5.1.5 二叉树的顺序结构 70

5.2 二叉树的遍历 71

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

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

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

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

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

5.3 Huffman编码的实现及其应用 75

5.3.1 Huffman编码及其无损压缩 75

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

小结 78

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

6.1 顺序查找 79

6.1.1 简单查找 79

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

6.1.3 条件查找 81

6.1.4 函数对象 83

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

6.2 二分查找的应用 85

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

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

6.2.3 返回位置的二分查找 87

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

6.3 二叉查找树 92

6.3.1 二叉查找树的插入 92

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

6.3.3 二叉查找树的查找 94

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

6.3.5 二叉查找树的删除 96

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

6.4 平衡二叉查找树 98

6.4.1 AVL树的归纳定义 98

6.4.2 AVL树的表示和插入 98

6.5 线索二叉树 100

6.5.1 线索二叉树的表示 100

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

6.6 散列表 102

小结 104

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

7.1 快速排序 105

7.2 稳定排序 106

7.3 部分排序 106

7.4 堆排序 108

7.5 归并排序 109

小结 112

第8章 图算法及其应用 113

8.1 图的邻接矩阵表示 113

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

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

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

8.2 图的邻接表表示 119

8.2.1 邻接表——C风格 119

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

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

8.3 拓扑排序 121

8.3.1 拓扑排序算法 121

8.3.2 拓扑排序应用举例 122

8.4 广度优先遍历 124

8.4.1 广度优先遍历算法 124

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

8.5 深度优先遍历 126

8.5.1 深度优先遍历算法 126

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

8.6 最小生成树 129

8.6.1 最小生成树算法 129

8.6.2 最小生成树应用举例 130

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

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

8.7.1 Dijkstra算法 133

8.7.2 Dijkstra算法的细化 133

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

8.7.4 编程练习：最短路径 135

8.8 图论应用项目 136

8.8.1 TSP问题 136

8.8.2 医院选址问题 136

8.8.3 地铁建设问题 137

8.8.4 地铁乘车指引问题 138

小结 139

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

9.1 容器 140

9.1.1 容器的概念 140

9.1.2 顺序容器 141

9.1.3 联合容器 142

9.1.4 优先队列 146

9.2 迭代器 147

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

9.2.2 迭代器的使用 150

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

9.3 算法 157

9.3.1 不改变容器的算法 159

9.3.2 改变容器的算法 162

9.3.3 排序算法 166

9.3.4 堆运算 169

9.3.5 集合运算 171

9.3.6 最大最小运算 173

9.4 函数对象 174

9.4.1 遍历算法for_each的函数对象 174

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

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

9.4.4 编程练习：函数对象 181

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

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

9.4.7 预定义函数对象 183

9.4.8 可转换函数对象 185

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

小结 188

附录A 问题和软装置列表 189

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

A2 栈与队列的实现和应用 189

A3 递归 189

A4 二叉树的实现和应用 190

A5 查找的实现与应用 190

A6 排序的实现与应用 190

A7 图算法及其应用 191

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

附录C 部分参考程序 193

参考文献 215

索引 216