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

第1章“数据结构与算法”教学实施方案 1

1.1“数据结构与算法”的理论体系 1

1.1.1课程的基本定位 2

1.1.2知识体系 3

1.2“数据结构与算法”学习重点 6

1.2.1概论 7

1.2.2线性表 9

1.2.3栈与队列 10

1.2.4字符串 12

1.2.5二叉树 13

1.2.6树 15

1.2.7图 17

1.2.8内排序 20

1.2.9文件与外排序 23

1.2.10检索 24

1.2.11索引 25

1.2.12高级数据结构 27

第2章 面向对象程序设计与C+++概述 30

2.1面向对象程序设计概述 30

2.1.1面向对象程序设计：类和对象 30

2.1.2面向对象程序设计的特点 32

2.2 C+++编程概述 33

2.2.1 C+++中的类和对象 33

2.2.2对象的定义 35

2.2.3类的成员函数 36

2.2.4构造函数和析构函数 37

2.2.5友元 41

2.2.6类的继承 43

2.3重载 47

2.3.1函数重载 47

2.3.2运算符重载 50

2.4动态存储分配 53

习题 55

第3章STL简介 57

3.1泛型编程简介 57

3.1.1泛型编程的需求 57

3.1.2 C+++中模板的使用 59

3.2 STL容器简介 61

3.2.1 vector 62

3.2.2 deque 66

3.2.3 list 66

3.2.4 set和multiset 68

3.2.5 map和multimap 71

3.2 6 stack 74

3.2 7 queue 75

3.3 STL算法 77

3.3.1 STL算法简介 77

3.3.2非变动性算法 79

3.3.3变动性算法 80

3.3.4变序型算法和排序算法 81

3.3.5已排序区间算法 83

3.3.6数值算法 85

3.4 STL迭代器 85

3.4.1迭代器简介 85

3.4.2迭代器类型 87

3.4.3迭代器函数 88

3.4.4迭代器配接器 89

3.5文件流与输入输出 92

3.5.1全局性的Stream对象 92

3.5.2标准操作符﹤﹤和﹥﹥ 93

3.5.3标准IO函数 95

习题 97

第4章 程序设计实践 98

4.1程序设计风格 98

4.1.1命名 100

4.1.2语句 102

4.1.3注释 104

4.1.4程序组织原则 106

4.1.5文档 106

4.1.6实践和原则 107

4.2界面 109

4.3测试、性能和可扩展性 111

4.3.1软件测试基本概念 112

4.3.2软件测试原则 115

4.3.3软件测试策略 116

4.3.4软件测试方法 117

4.3.5测试实例 121

4.3.6性能和可扩展性 123

习题 126

第5章 问题建模 127

5.1数学模型和数学建模 127

5.1.1数学模型 127

5.1.2数学模型示例——雨中行问题 130

5.1.3生产计划问题——线性规划模型 133

5.1.4预测疾病的发展变化趋势——马尔可夫链模型 136

5.1.5 Buffon投针实验——蒙特卡罗方法 140

5.1.6公交最优路线查询系统设计问题 143

5.2设计模式 147

5.2.1设计模式的概念 147

5.2.2 MVC的设计模式 149

5.2.3设计模式举例——工厂模式 151

习题 153

第6章 经典算法设计 155

6.1状态空间 155

6.2时间复杂度计算 157

6.2.1算法时间复杂度分析 157

6.2.2递推方程求解 159

6.3穷举法 164

6.4贪心法 171

6.5递归和回溯 176

6.5.1递归法 176

6.5.2回溯法 178

6.5.3回溯法的分支限界 182

6.6搜索与剪枝 187

6.6.1盲目搜索算法 187

6.6.2剪枝 192

6.6.3搜索的效率问题 194

6.7分治法 197

6.7.1分治策略 197

6.7.2降低递归算法复杂性的途径 202

6.8动态规划 206

6.9算法思想小结 213

习题 215

第7章 问题求解实践 225

7.1问题求解 225

7.2线性结构 226

7.2.1数组元素循环右移k位——时空权衡 227

7.2.2火车调度——栈的应用 230

7.2.3 KMP模式匹配算法的应用 234

7.3树形结构 236

7.3.1二叉树遍历算法框架在问题求解中的应用 236

7.3.2树的应用 244

7.3.3选择树的应用 247

7.3.4树与二叉树的计数 252

7.4线段树 255

7.4.1线段树的定义及特征 255

7.4.2线段树的基本操作 256

7.5图的应用 260

7.5.1图的抽象 260

7.5.2图的搜索 265

7.5.3基于深度优先的拓扑排序 267

7.5.4第二最短路径 268

7.5.5唯一最小生成树 271

7.5.6有向图的强连通性问题 273

7.6排序与检索 281

7.6.1统计逆序对的归并思想 281

7.6.2求两个等长有序序列中位数的二分思想 284

7.7算法优化 287

习题 289

第8章 数据结构与算法技术应用实例 295

8.1搜索引擎中的数据结构技术 295

8.1.1概述 295

8.1.2抓取系统 296

8.1.3索引系统 298

8.1.4检索系统 303

8.2在线评测算法实习范例 305

8.3综合实习范例 314

习题 320

第9章 试题及参考答案 327

9.1期中考试 327

9.1.1 2007年期中考试试题 327

9.1.2 2007年期中考试参考答案 331

9.1.3 2008年期中考试试题 335

9.1.4 2008年期中考试参考答案 340

9.2期末考试 346

9.2.1 2007年期末考试试题 346

9.2.2 2007年期末考试参考答案 350

9.2.3 2008年期末考试试题 354

9.2.4 2008年期末考试参考答案 358

9.3高级专题考试 364

9.3.1 2007年高级专题考试试题 364

9.3.2 2007年高级专题考试参考答案 366

9.3.3 2008年高级专题考试试题 370

9.3.4 2008年高级专题考试参考答案 371

9.4实习课程考试 377

9.4.1 2007年实习课考试试题 377

9.4.2 2007年实习课考试参考答案 382

9.4.3 2008年实习课考试试题 386

9.4.4 2008年实习课考试参考答案 388

参考文献 394