《数据结构实验》指导书Data Structures and Algorithms Laboratory Projects王金荣2014-09-11目录1《数据结构实验》课程实验教学大纲--------------------------------------12 实验准备: 如何使用VC 6.0? ----------------------------------------------33 Projects---------------------------------------------------------------------------8 3.1 Project 1: 算法性能测量-------------------------------------------------8 3.2 Project 2: 有序表归并实验---------------------------------------------10 3.3 Project 3: 数据转换------------------------------------------------------11 3.4 Project 4: 二叉树遍历实验---------------------------------------------12 3.5 Project 5-1: 堆排序算法实现------------------------------------------13 3.6 Project 5-2: 归并排序算法实现---------------------------------------14 3.7 Project 5-3: 快速排序算法实现---------------------------------------15 3.8 Project 6-1: 图的深度优先搜索---------------------------------------16 3.9 Project 6-2: 图的广度优先搜索---------------------------------------173.10 Project 7: 散列实验---------------------------------------------------184.1 ACM题目-------------------------------------------------------------------19 4.1 ACM 1: ACboy needs your help again!-------------------------------19 4.2 ACM 2: Jumping the Queue--------------------------------------------21 4.3 ACM 3: Median ----------------------------------------------------------234.4 ACM 4: Ignatius and the Princess I------------------------------------255 实验报告格式-----------------------------------------------------------------28 6实验报告上交说明-----------------------------------------------------------291《数据结构实验》课程实验教学大纲课程中文名称：数据结构实验课程英文名称：Data Structure Practices实验课程性质：独立设课课程编码：044209101一、学时、学分课程总学时：34 实验学时：34课程总学分：1 实验学分：1二、适用专业及年级计算机科学与技术专业，软件工程专业，第二学期三、实验教学目的与基本要求“数据结构实验”的总体目标是：通过实验使学生对课堂讲授的内容有实际的体验，加深对概念、算法、技术的理解、掌握、应用，并激发学生进一步的思考和发挥，注重培养学生的学习兴趣和创新思维。
通过实验，使学生进一步掌握VC编程环境；理解和掌握数据结构的基本问题和基本算法；具备大型程序的编程能力，特别是多文件大型工程的编程；了解ACM竞赛的赛题，掌握参加ACM竞赛的基本技能。
四、主要仪器设备通过局域网互联、安装Windows XP / windows 7操作系统和Visual C++环境的微机。
注：1．实验项目名称，表达要简洁准确；2．实验属性，分“基础”、“专业基础”、“专业”。
按课程代码的第3位进行识别，第3位≤3的为“基础”，第3位＝4的为“专业基础”，第3位＝5的为“专业”。
3．项目类型，分“演示”、“验证”、“综合”、“设计研究”、“其他”。
4．项目要求，分“必做”、“选做”。
六、成绩考核（1）实验成绩的构成：平时成绩占50 %，实验考核占50 %，其它占0 %。
（2）评分标准（按构成分类说明）：平时成绩: 自编讲义《数据结构实验指导书》中已经明确规定每个实验的目的、任务、主要步骤和评分标准。
教师以此为依据，根据学生通过上交的实验报告和实验源代码确定其完成数量和质量、进行评分。
实验考核：期末考试安排闭卷上机考试，考试题目从平时课堂试验中随机抽取。
七、实验教科书、参考书（一）教科书《数据结构实验指导书》袁贞明，王金荣编，自编讲义（二）参考书1.《数据结构与算法分析》Mark Allen Weiss，陈越改编，人民邮电出版社,2005.082.《数据结构(C语言)》 Ellis Horowitz，李建中等译, 机械工业出版社,2006.07.2 实验准备: 如何使用visual studio 2010编写一个c++程序?/article/466506580cc227f549e5f80b.html3 Projects3.1 Project 1: 算法性能测量（1）问题描述随机生成为N个随机整数，请分别用“选择排序法”和“希尔排序法”对其进行从小到大的排序，并测试不同规模N下两算法的运行时间。
（2）任务①实现选择排序法，算法见教材P11-Program 1.4；②实现希尔排序法，算法附后；③分折选择排序法的时间和空间复杂度；④当规模N分别取1000、2000、4000、8000、16000、32000、64000时，测试四个函数的运行时间，将所测结果填入表1中。
⑤* 画出函数运行时间T随着规模N的变化趋势图（可以用PPT、Matlab画）。
（3）生成随机整数的方法生成方法如下图所示，程序开头需要加上“stdlib.h”头文件。
（4）函数运行时间测试方法为测试一个C函数的运行时间，需要使用头文件“time.h”，具体测试方法参见第1.6.1节，如下所示：注: 当一个函数的运行时间小于一个tick（毫秒），则其所测时间为0.0，为了测试这种情况下函数的运行时间，我们可以将该函数重复运行K次，再测试其总运行时间（“Total Time”），然后将该时间除以K即得该函数的一次运行时间（“Duration”）。
此处的K要求足够大，使得总运行时间不能少于100毫秒。
表1 四个函数的运行时间统计（秒）（5）希尔排序算法3.2 Project 2: 有序表归并实验（1）问题描述对任意输入的两个按值非递减有序的整数序列，写一程序将它们归并成一个按值非递减有序序列。
（2）输入描述文本文件“input.txt”中保存了n个测试用例，文件以-1结束。
每个用例的第一行m1表示第一个待归并有序序列的元素个数，第二行为该序列的m1个元素，第三行m2表示第二个待归并有序序列的元素个数，第四行为该序列的m2个元素。
（3）输出描述输出结果保存在文本文件“output.txt”中。
对于每个测试用例均有二行输出，第一行输出“Case #:##”，#表示用例的编号（1…n），##表示归并后有序序列的元素个数；第二行输出##个按值非递减有序元素。
（4）输入示例51 4 8 10 3072 4 20 35 50 60 86338 45 100438 50 100 120-1（5）输出示例Case 1:121 2 4 4 8 10 20 30 35 50 60 86Case 2:738 38 45 50 100 100 1203.3 Project 3: 数据转换（1）问题描述对任意输入的十进制正整数，写一程序将其转换成二进制表示。
要求首先实现Stack ADT，然后用栈的基本操作完成该程序。
（2）输入描述文本文件“input.txt”中保存了n个小于32768的正整数，文件以-1结束。
（3）输出描述输出结果保存在文本文件“output.txt”中，文件每一行输出“#--->##”，#表示十进制表示的正整数，##为其二进制表示结果。
（4）输入示例20163445100-1（5）输出示例20--->1010016--->1000034--->10001045--->101101100--->11001003.4 Project 4: 二叉树遍历实验（1）Problem descriptionCreate binary tree as follow (Figure-1) in computer, write out the functions of inOrder , preOrder , postOrder and levelOrder, and use them to traversal the binary tree. And compute the leaf number and height of the binary tree.Hint: You may choose suitable representation, such as linked representation is often used.Figure-1 a binary tree（2）Steps and restrict conditionsStep 1. Write the function of create to create a tree by input data. The input format of the binary tree in Figure-1 is as : ABD#G##CE##FH###.Step 2. Write recursive version functions of inOrder, preOrder and postOrder to traversal the tree.Step 3. Select a suitable representation to implement stack ADT, which must at least has five basic operations: IsFull, IsEmpty, Push and Pop. The element type in the stack ispointer of node.Step 4. Implement Queue ADT represented by circular queue, which has seven basic operations: IsEmpty, IsFull, AddQ, DeleteQ. The element type in the queue is pointer of node.Step 5. Write an iterative version of inorder, the name is iterInorder() to inorder traversal tree. Step 6. Write a function for level order traversal of binary tree, the name is levelOrder.Step 7. Write a function to compute the leaf number of the binary tree, the name is leaf.Step 8. Write a function to compute the height of the binary tree, the name is height.（1）问题描述对于任一无序正整数序列，写一程序用堆排序算法将其排序成按值非递减有序序列。