数据结构与算法实验实践教程PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与算法实验实践教程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 标准库数据结构vector8

2.1.2 线性表vector的应用12

2.1.3 编程练习：vector的应用12

2.1.4 标准库数据结构list13

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 数据结构串string27

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

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

小结40

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

3.1 标准库栈的使用41

3.1.1 STL模板类stack41

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

3.2 栈的实现43

3.2.1 栈的定义43

3.2.2 编程练习：栈的实现44

3.3 队列的应用45

3.3.1 STL模板队列queue45

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