北 京 邮 电 大 学
计 算 机 科 学 与 技 术 学 院
算 法 与 数 据 结 构
实 验 指 导 书
杨俊、徐塞虹、漆涛 编著
2006年9月
1 算法与数据结构 实验指导书
目录
实验要求....................................................................................................................................3 试验
一、约瑟夫环..............................................................................…………………..……4 试验
二、长整数四则运算运算………………………………………………………………4 实验
三、八皇后.....................................……..........................................................................5 实验
四、骑士遍历......................................……………………..............................................5 实验
五、桌面计算器...............................……………..............................................................6 实验
六、平衡排序二叉树....................…...…….....................................................................6 试验
七、多重集合的实现……......................................………………………………………7 试验
八、图论………………………………………………………………………….……..8 实验
八、内部排序性能的比较..........………………….............................................................8 教材及主要参考文献………………………………………………………………………………..9 2 北京邮电大学 计算机科学与技术学院 算法与数据结构 实验指导书
实验要求
一、本课程在讲课期间需要做上机实验，目的之一是检查学生对所学算法的掌握和理解程度；其次是锻炼学生的团队合作精神。
二、成绩：
1、编码：占整个实验成绩的50%；
2、测试：占整个实验成绩的20%；
3、文档：占整个实验成绩的30%。
三、按时提交上机文档，实验文档包含以下各项：
1、问题描述：实验题目、内容和要求；
2、算法思路：实验小组对问题的解决方法的文字描述；
3、算法描述：用类算法语言等对算法进行描述；
4、源程序及驱动程序：上机实验编制的代码源程序及程序运行环境；
5、测试数据：对算法的测试用例；
6、结果分析和结论：对算法及测试结果的分析及结论；
7、心得体会：通过实验获得的心得体会；
8、分工及签名：最后是小组成员的分工及签名。
3 北京邮电大学 计算机科学与技术学院 - 1 -算法与数据结构 实验指导书
实验
一、约瑟夫环
一、实验类别：设计型实验。
二、问题描述：约瑟夫环问题是：n个人p0,p1,…pn 围坐成一个圆环。每个人pk持有一个秘密的数字ck。0
三、实验目的：检查学生对各种线性表的实现的掌握程度。
四、实验学时：2小时
五、实验组人数：1人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：各种队列的实现。
八、实验内容和要求：至少用3种以上的线性表来完成此试验。可以在带头节点的和不带头节点的线性表、循环的和非循环线性表、动态链表和静态链表以及向量（数组）之间选择三种。从空表开始，为每个人生成一个随机数。然后将此人加入到线性表之中。
九、可研究与探索的问题：给出各种实现的优缺点比较。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出各种线性表实现的优缺点分析。
实验
二、长整数四则运算
一、实验类别：验证实验。
二、问题描述：计算机CPU本身可以做32位或者64位的整数四则运算。本试验要求对任意大小的整数实现其四则运算。将一个整数N表示为
N = ±(d0 + d1*B + d2*B2 + ….+ bk*Bk)
其中 1
三、实验目的：对具体的问题选择适当的线性表实现。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：各种队列的实现。
八、实验内容和要求：至少用2种以上的线性表来完成此试验。比较不同线性表实现的速度。
九、可研究与探索的问题：1）对具体问题选择合适的线性表实现。2）B 的选取问题。可
4 否选择更大的基B。B的选择所应考虑的因素。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。能够得出用向量（数组）实现的线性表速度最快。
实验
三、八皇后问题
一、实验类别：设计型实验。
二、问题描述：在n*n 的国际象棋棋盘上放置n个皇后，使每个皇后不受其他皇后的攻击。
三、实验目的：检查学生对堆栈和递归程序掌握程度。
四、实验学时：2小时
五、实验组人数：1人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：递归程序与堆栈
八、实验内容和要求： 分别用递归和堆栈完成此试验。统计程序运行时间与问题规模n 的关系。
九、可研究与探索的问题：问题的复杂度。当n 比较大时，讨论提高程序运行的方法。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。找出程序运行速度的瓶颈。
实验
四、骑士遍历
一、实验类别：设计型实验。
二、问题描述：在国际象棋n*n的棋盘中，一匹马从棋盘中任意一格出发，要求用n2-1步走完所有的n2个格子。每个格子走且只走过一次。应如何走？ 试给出算法实现。
三、实验目的：检查学生对堆栈与回溯算法的掌握。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：堆栈与回溯
八、实验内容和要求：用堆栈完成此试验。统计程序运行时间与问题规模n 的关系。
九、可研究与探索的问题：怎样枚举所有马下一步可走的位置。选择下一步所走位置的策略。注意由于这个程序非常耗时，在初期程序调试时应取较小的n。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。找出程序运行速度的瓶颈。给出不同选择策略的程序运行
5 速度的比较结果。
实验
五、桌面计算器（表达式求值）
一、实验类别：设计型实验。
二、问题描述：模仿Unix系统下的dc命令。输入表达式字符串，按回车键后给出表达式的值。操作数为实数。
1） 操作符有 “+”、“-”、“*”、“/”、“^”（乘方）
2） 还可以有临时变量。用法如 pi = 3.1415926，r = 3, r*pi^2 3） 还可以有事先定义的函数如：“sin( )”（正弦）、“cos( )”（余弦）、“log( )”（对数）、“ln( )”（自然对数）等函数。
三、实验目的：检查学生用堆栈解决实际问题。为本课程后续的内容提供伏笔。也为后继的课程如编译原理预习。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：堆栈，线性表，命令行参数的处理。
八、实验内容和要求：学生应至少应实现处理五个运算符：“+”、“-”、“*”、“/”、“^”（乘方）。可以用一个线性表来存储临时变量。另一个线性表来存储预定义的函数名。
九、可研究与探索的问题：查找临时变量名的不同方法。如哈希表，二叉树。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。
实验
六、平衡排序二叉树
一、实验类别：设计型实验。
二、问题描述：随机生成一组整数p0,p1,…pn－１。将这组整数按生成的次序插入到一个平衡排序二叉树中。然后将p0,p1,…pn－１随机重新排列为q0,q1,…qn－１。再按照次次序将这些整数从生成的平衡排序二叉树删除。
三、实验目的：平衡排序二叉树的插入和删除。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：平衡排序二叉树的插入和删除中的旋转。
八、实验内容和要求：统计在平衡排序二叉树的插入和删除过程中各种旋转的出现次数。
九、可研究与探索的问题：研究平衡排序二叉树与一般的排序二叉树在插入和删除方面的性能比较。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出在均匀的随机分布下，平衡排序二叉树与一般排序二叉树的性能比较。
实验
七、多重集合的实现
一、实验类别：设计型实验。
二、问题描述：实现数学上多重集合。所谓的多重集合类似于集合，但是一件东西可以放置多个副本。就如一个菜篮子里面可以放两个苹果。
三、实验目的：查找结构的各种实现。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：平衡排序二叉树的插入和删除、遍历，查找。哈希查找结构。
八、实验内容和要求： 假设集合中包含的元素是可以排序的。将多重集合封装成一个类。具体的实现可以是中序线索化的平衡排序二叉树，或者带父节点指针的平衡排序二叉树。多重集合的界面如下：
template //假设类型 T 是可以排序的
cla Multi_set
{
Multi_set(void); //构造函数，初始化为空集合
~Multi_set(void); //析构函数
Multi_set& operator=(Multi_set const a); //重载运算符=
bool contains(T const& v)const; //如果集合包含v 则返回true，否则返回false
Multi_set& operator+=(Multi_set const&a); //将集合a 并到自身中。
Multi_set& operator-=(Multi_set const& a); //自身减去集合a
Multi_set& operator-=(T const& a); //自身减去一个元素a
};//~cla Multi_set
//返回集合a,b的并
template Multi_set Mult_set:: operator+(Multi_set const& a,
Multi_set const& b);
//返回集合a,b的差
template Multi_set Mult_set:: operator-(Multi_set const& a,
Multi_set const& b);
//返回 a –{v}
template
Multi_set Multi_set::operator-(Multi_set const& a,T const& v);
7
九、可研究与探索的问题：哈希函数的选取。比较哈希与平衡排序二叉树的优缺点、性能和速度。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出平衡排序二叉树实现的多重集合和用哈希实现的多重集合的性能比较。
实验
八、图论
一、实验类别：设计型实验。
二、问题描述：实现图论中的各种算法。
1） 最小代价生成树的Krscal 算法和Prim算法。 2） 单源点的最短路径的Dijstra 算法。 3） 深度优先遍历与广度优先遍历。 4） 拓扑排序
5） 求所有节点之间的最短路径Floyd算法
（在这五个小题中只要选作一个即可。）
三、实验目的：学习根据不同的运算来选取不同的存储结构。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：图论中的各种算法及其复杂度。根据不同的操作来决定图的存储结构。
八、实验内容和要求：至少实现上面五个小题目中的一个。从文件中读入一个图的信息。
九、可研究与探索的问题：高级数据结构如堆、并查集在图论算法中的应用。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出在均匀的随机分布下，平衡排序二叉树与一般排序二叉树的性能比较。
实验
九、内部排序性能的比较
一、实验类别：设计型实验。
二、问题描述：随机生成一组整数p0,p1,…pn－１。对这组数据进行排序。
三、实验目的：比较不同排序算法的性能。
四、实验学时：2小时
五、实验组人数：3人。
六、实验设备环境：计算机。
七、实验原理及要点（知识点）：各种内部排序算法。
八、实验内容和要求：
8 1） 实现插入排序，选择排序，希尔排序，堆排序以及快速排序。 2） 快速排序的多种版本。 3） 对单链表实现归并排序。 4） 基数排序。
5） 对小型问题（n = 10）、中型问题（n = 1000）以及大型问题（n = 1百万）分别统计不同排序算法的键值比较次数、键值移动次数以及程序运行时间。
26） 排序算法的时间复杂度可以有O(n) 和 O(n log n)。对相同复杂度的算法，给出他们运行时间与时间复杂度的比值。
九、可研究与探索的问题：研究快速排序算法的不同改进方法。自省排序算法。只需要移动而不需要交换的快速排序方法。
十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出在均匀的随机分布下，对大中小问题的最快的排序算法。
教材及主要参考文献
[1] 严蔚敏、吴伟民，数据结构习题集，清华大学出版社，1999年
[2] John R.Hubbard, Data Structures with C++, China Machine Pre, 2002.
[3] Mark Allen Wei, Data Structures and Problem Solving Using C++, 2ed, 清华大学出版社。2004年。 [4] Robert Sedgewick， Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中国电力出版社，2003年。
[5] 严蔚敏、吴伟民，数据结构(C语言版)，清华大学出版社，2006年
