数据结构与算法实验教程

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

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

1.1.1 课程的基本定位

1.1.2 知识体系

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

1.2.1 概论

1.2.2 线性表

1.2.3 栈与队列

1.2.4 字符串

1.2.5 二叉树

1.2.6 树

1.2.7 图

1.2.8 内排序

1.2.9 文件与外排序

1.2.10 检索

1.2.11 索引

1.2.12 高级数据结构

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

2.1 面向对象程序设计概述

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

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

2.2 C++编程概述

2.2.1 C++中的类和对象

2.2.2 对象的定义

2.2.3 类的成员函数

2.2.4 构造函数和结构函数

2.2.5 友元

2.2.6 类的继承

2.3 重载

2.3.1 函数重载

2.3.2 运算符重载

2.4 动态存储分配

习题

第3章 STL简介

3.1 泛型编程简介

3.1.1 泛型编程的需求

3.1.2 C++中模板的使用

3.2 STL容器简介

3.2.1 vector

3.2.2 deque

3.2.3 list

3.2.4 set和multiset

3.2.5 map和multimap

3.2.6 stack

3.2.7 queue

3.3 STL算法

3.3.1 STL算法简介

3.3.2 非变动性算法

3.3.3 变动性算法

3.3.4 变序型算法和排序算法

3.3.5 已排序区间算法

3.3.6 数值算法

3.4 STL迭代器

3.4.1 迭代器简介

3.4.2 迭代器类型

3.4.3 迭代器函数

3.4.4 迭代器配接器

3.5 文件流与输入输出

3.5.1 全局性的Stream对象

3.5.2 标准操作符

3.5.3 标准10函数

习题

第4章 程序设计实践

4.1 程序设计风格

4.1.1 命名

4.1.2 语句

4.1.3 注释

4.1.4 程序组织原则

4.1.5 文档

4.1.6 实践和原则

4.2 界面

4.3 测试、性能和可扩展性

4.3.1 软件测试基本概念

4.3.2 软件测试原则

4.3.3 软件测试策略

4.3.4 软件测试方法

4.3.5 测试实例

4.3.6 性能和可扩展性

习题

第5章 问题建模

5.1 数学模型和数学建模

5.1.1 数学模型

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

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

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

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

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

5.2 设计模式

5.2.1 设计模式的概念

5.2.2 MVC的设计模式

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

习题

第6章 经典算法设计

6.1 状态空间

6.2 时间复杂度计算

6.2.1 算法时间复杂度分析

6.2.2 递推方程求解

6.3 穷举法

6.4 贪心法

6.5 递归和回溯

6.5.1 递归法

6.5.2 回溯法

6.5.3 回溯法的分支限界

6.6 搜索与剪枝

6.6.1 盲目搜索算法

6.6.2 剪枝

6.6.3 搜索的效率问题

6.7 分治法

6.7.1 分治策略

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

6.8 动态规划

6.9 算法思想小结

习题

第7章 问题求解实践

7.1 问题求解

7.2 线性结构

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

7.2.2 火车调度——栈的应用

7.2.3 KMP模式匹配算法的应用

7.3 树形结构

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

7.3.2 树的应用

7.3.3 选择树的应用

7.3.4 树与二叉树的计数

7.4 线段树

7.4.1 线段树的定义及特征

7.4.2 线段树的基本操作

7.5 图的应用

7.5.1 图的抽象

7.5.2 图的搜索

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

7.5.4 第二最短路径

7.5.5 唯一最小生成树

7.5.6 有向图的强连通性问题

7.6 排序与检索

7.6.1 统计逆序对的归并思想

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

7.7 算法优化

习题

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

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

8.1.1 概述

8.1.2 抓取系统

8.1.3 索引系统

8.1.4 检索系统

8.2 在线评测算法实习范例

8.3 综合实习范例

习题

第9章 试题及参考答案

9.1 期中考试

9.1.1 2007年期中考试试题

9.1.2 2007年期中考试参考答案

9.1.3 2008年期中考试试题

9.1.4 2008年期中考试参考答案

9.2 期末考试

9.2.1 2007年期末考试试题

9.2.2 2007年期末考试参考答案

9.2.3 2008年期末考试试题

9.2.4 2008年期末考试参考答案

9.3 高级专题考试

9.3.1 2007年高级专题考试试题

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

9.3.3 2008年高级专题考试试题

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

9.4 实习课程考试

9.4.1 2007年实习课考试试题

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

9.4.3 2008年实习课考试试题

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

参考文献

“数据结构与算法”课程是一门理论和实践紧密结合的课程，上机实习题的设计、实习训练的数量和质量都非常重要。与作者编著的《数据结构与算法》主教材相呼应，张铭等编著的《数据结构与算法实验教程》主要介绍程序设计实践和技巧，常用的问题建模方法、基本算法，以及数据结构与算法应用，目的在于指导学生灵活地运用数据结构和算法解决具体问题，以便更好地巩固“数据结构与算法”课程所学的内容。《数据结构与算法实验教程》给出了大量的数据结构与算法实习题，可用作相关知识点的实验设计题目。尤其是第8章给出了10道综合性较强的中小型应用题，适合于布置期末综合实习，或者作为综合的课程设计作业项目。

　　《数据结构与算法实验教程》概念清楚，逻辑性强，内容新颖，可作为普通高校计算机科学技术专业与计算机应用专业学生的教材和参考书，还可供相关的信息技术领域工程技术人员参考。

数据结构与算法实习课程注重实践能力和工程能力的培养，提高学生的实际动手能力，为后续专业基础课和专业课程学习打下坚实的基础。张铭等编著的《数据结构与算法实验教程》旨在指导学生灵活运用数据结构和算法解决具体问题。以更好地巩固理论课程所学的内容。

　　《数据结构与算法实验教程》主要内容包括数据结构与算法教学实施方案、C++概述及基础知识、泛型化程序设计思想和标准模板库、STL基本概念、程序设计实践和技巧、问题建模专题讨论、问题求解实践和数据结构与算法应用实例。

　　《数据结构与算法实验教程》附有北京大学数据结构与算法课程期中、期末、高级专题以及期末试题与参考答案。同时提供配套的教学讲义、课程网站等教学资源。便于教师教学。