2012级算法与数据结构实验指导书18.pdf

《2012级算法与数据结构实验指导书18.pdf》由会员分享，可在线阅读，更多相关《2012级算法与数据结构实验指导书18.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 算法与数据结构实验指导书实验课程类别：课程内实验 实验课程性质：必修 适用专业、年级：2012 级计算机大类 开课院、系：计算机科学与工程学院 学时：18 编写依据：算法与数据结构实验教学大纲 修订时间：2014 年 2 月 算法与数据结构课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。上机的工作环境要求：Windows 2000 或以上操作系统、VC+6.0 或者其它高级程序设计语言。学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内

2、容至少包含如下内容：1、学生基本情况：专业班级、学号、姓名 2、实验题目、实验内容 3、设计分析 4、源程序代码 5、测试用例（尽量覆盖所有分支）6、实验总结 一实验内容与学时分配 序次 实验 题目 实验 类型 基本技能训练 学时 一 线性结构综合应用 基础性（1）掌握线性结构的常用操作；（2）能够应用线性结构解决比较简单的问题。10 二 非线性结构综合应用 设计性（1）掌握树形、图形结构的插入、删除、查找等算法；（2）能够应用二叉树解决比较简单的问题。4 三 查找技术综合应用 设计性（1）熟练掌握查找的常用算法；（2）设计和应用查找算法解决简单的实际问题。2 四 排序技术综合应用 基础性（1

3、）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2 二实验说明 实验一、线性结构综合应用（一）顺序表的应用 1、实验目的：（1）掌握用 VC+上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。2、实验内容 约瑟夫环问题：设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，m 为任意一个正整数。从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止并且报 m 的人出列，再从他的下一个人开始重新

4、从 1 报数，报到 m 时停止并且报 m 的人出列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的 m 和 n，求出出列编号序列。3、实验要求：用顺序表实现。（二）链表的应用 1、实验目的：（1）熟练掌握链表结构及有关算法的设计；（3）掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。2、实验内容：一元多项式求和。把任意给定的两个一元多项式 P(x),Q(x)输入计算机，计算它们的和并输出计算结果。3、实验说明：一元多项式可以用单链表表示，结点结构图示如下：一元多项式算法伪代码如下：一元多项式链表的结点结构 coef exp next 1.工作指针 p、

5、q 初始化；2.while（p 存在且 q 存在）执行下列三种情形之一 2.1 如果 p-expexp，则指针 p 后移;2.2 如果 p-expq-exp，则 2.2.1 将结点 q 插入到结点 p 之前；2.2.2 指针 q 指向原指结点的下一个结点；2.3 如果 p-exp=q-exp，则 2.3.1 p-coef=p-coef+q-coef；2.3.2 如果 p-coef=0，则执行下列操作，否则，指针 p 后移;2.3.2.1 删除结点 p；2.3.2.2 使指针 p 指向它原指结点的下一个结点；2.3.3 删除结点 q；2.3.4 使指针 q 指向它原指结点的下一个结点；3.如果

6、q 不为空，将结点 q 链接在第一个单链表的后面；（三）栈的应用 1、实验目的：（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。2、实验内容：表达式求值问题。这里限定的表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。算术表达式求值过程是：STEP 1：先将算术表达式转换成后缀表达式。STEP 2：然后对该后缀表达式求值。3、实验说明：在设计相关算法中用到栈，这里采用顺序栈存储结构。中缀表达式 exp 后缀表达式 postexp 伪代码如下：对后缀表达式 postexp 求值伪

7、代码如下：初始化运算符栈op;将=进栈;从exp读取字符ch;while(ch!=0)if(ch不为运算符)将后续的所有数字均依次存放到postexp中,并以字符#标志数值串结束;else switch(Precede(op栈顶运算符,ch)case:/栈顶运算符应先执行,所以出栈并存放到postexp中 退栈运算符并将其存放到postexp中;break;若字符串exp扫描完毕,则将运算符栈op中=之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp;while(从 postexp 读取字符 ch,ch!=0)若 ch 为数字,将后续的所有数字构成一个整数存放到

8、数值栈 st 中。若 ch 为“+”,则从数值栈 st 中退栈两个运算数,相加后进栈 st 中。若 ch 为“”,则从数值栈 st 中退栈两个运算数,相减后进栈 st 中。若 ch 为“*”,则从数值栈 st 中退栈两个运算数,相乘后进栈 st 中。若 ch 为“/”,则从数值栈 st 中退栈两个运算数,相除后进栈 st 中(若除数为零,则提示相应的错误信息)。若字符串 postexp 扫描完毕,则数值栈 op 中的栈顶元素就是表达式的值。出 轨 入 轨 581 H1 H3 H2 963 742 出 轨 入 轨 58 H1 H3 H2 96 7 4321 出 轨 入 轨 5 H1 H3 H2

9、96 87 54321 出 轨 入 轨 H1 H3 H2 987654321(a)将 369、247 依次入缓冲轨(b)将 1 移至出轨，234 移至出轨(c)将 8 入缓冲轨，5 移至出轨(d)将 6789 移至出轨（四）队列的应用 1、实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。2、实验内容：火车车厢重排问题。3、实验说明：转轨站示意图如下：火车车厢重排过程如下：火车车厢重排算法伪代码如下：出 轨 入 轨 581742963 987654321 H1 H3 H2 1.分别对k个队列初始化；2.初始化下一个要输出的车厢编号nowOut=1;3.依次取入轨中

10、的每一个车厢的编号；3.1 如果入轨中的车厢编号等于nowOut，则 3.1.1 输出该车厢；3.1.2 nowOut+；3.2 否则，考察每一个缓冲轨队列 for(j=1;j=k;j+)3.2.1 取队列 j 的队头元素c；3.2.2 如果c=nowOut，则 3.2.2.1 将队列 j 的队头元素出队并输出；3.2.2.2 nowOut+；3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则 3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；3.3.2 如果 j 不存在，但有多于一个空缓冲轨，

11、则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；（五）稀疏矩阵的应用 1、实验目的：（1）掌握掌握稀疏矩阵的表示方法及其运算的实现；（2）实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。2、实验内容 在 mn 的矩阵中，有 t 个非零元。令=t/(m*n),称 矩阵的稀疏因子，常认为 0.05 时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。用三元组表实现稀疏矩阵的转置，用（顺序取，直接存）方法。3、实验说明：引入两个数组作为辅助数据结构：numnu：表示矩阵 A 中某列的非零元素的个数；cpotnu：初始值表示矩阵

12、 A 中某列的第一个非零元素在 B 中的位置。num 与 cpot 递推关系：三元组表实现稀疏矩阵的转置（顺序取，直接存）算法伪代码如下：cpot0=0;cpotcol=cpotcol-1+numcol-1;1colnu 1.设置转置后矩阵 B 的行数、列数和非零元素的个数；2.计算 A 中每一列的非零元素个数；3.计算 A 中每一列的第一个非零元素在 B 中的下标；4.依次取 A 中的每一个非零元素对应的三元组；4.1 确定该元素在 B 中的下标 pb；4.2 将该元素的行号列号交换后存入 B 中 pb 的位置；4.3 预置该元素所在列的下一个元素的存放位置；实验二、非线性结构综合应用 （六

13、）树的应用 1、实验目的：（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法。（3）掌握二叉树的各种遍历方法。2、实验内容:二叉树后序遍历的非递归算法。3、实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志 flag，当结点进、出栈时，其标志 flag 也同时进、出栈。设根指针为 root，则可能有以下两种情况：若 root!=NULL，则 root 及标志 flag（置为 1）入栈，遍历其左子树；若 root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结

14、点的标志 flag=1，则表明栈顶结点的左子树已遍历完毕，将 flag 修改为 2，并遍历栈顶结点的右子树；若栈顶结点的标志 flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。二叉树后序遍历的非递归算法伪代码如下：（七）图的应用 1、实验目的：（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握 AOV 网和拓扑排序算法；（4）掌握 AOE 网和关键路径。2、实验内容：拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法1 第一次出栈，只遍历完左子树，该结点不能访问 2 第二次出栈，遍历完右子树，该结点可以访问 flag 1

15、.栈 s 初始化；2.循环直到 root 为空且栈 s 为空 2.1 当 root 非空时循环 2.1.1 将 root 连同标志 flag=1 入栈；2.1.2 继续遍历 root 的左子树；2.2 当栈 s 非空且栈顶元素的标志为 2 时，出栈并输出栈顶结点;2.3 若栈非空，将栈顶元素的标志改为 2，准备遍历栈顶结点的右子树；思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述 a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。3、实验说明：拓扑排序算法伪代码如

16、下：实验三、查找技术综合应用（八）查找技术综合应用 1、实验目的：（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决比较简单的实际问题。2、实验内容：二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。3、实验说明：二叉排序树存储结构如下：二叉排序树插入算法伪代码如下：二叉排序树中删除一个结点 f 的左孩子结点 p 算法伪代码如下：1.栈 S 初始化；累加器 count 初始化；2.扫描顶点表，将没有前驱（即入度为 0）的顶点压栈；3.当栈 S 非空时循环 3.1 vj=退出栈顶元素；输出 vj；累加器加 1；3.2 将顶点 vj的各个邻

17、接点的入度减 1；3.3 将新的入度为 0 的顶点入栈；4.if(countdataroot-data，则把结点 s 插入到 root 的左子树中；否则 3.把结点 s 插入到 root 的右子树中。实验四、排序技术综合应用（九）排序技术综合应用 1、实验目的：（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2、实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。任意选择希尔排序、快速排序、归并排序中两种排序方

18、法，对任意给定一组数据：单增、单减、乱码等，对它们进行比较分析。3、实验说明：希尔排序算法如下：1.若结点 p 是叶子，则直接删除结点 p；2.若结点 p 只有左子树，则只需重接 p 的左子树；若结点 p 只有右子树，则只需重接 p 的右子树；3.若结点 p 的左右子树均不空，则 3.1 查找结点 p 的右子树上的最左下结点 s 以及结点 s 的双亲结点 par；3.2 将结点 s 数据域替换到被删结点 p 的数据域；3.3 若结点 p 的右孩子无左子树，则将 s 的右子树接到 par 的右子树上；否则，将 s 的右子树接到结点 par 的左子树上；3.4 删除结点 s；void ShellS

19、ort(int r,int n)for(d=n/2;d=1;d=d/2)/以增量为 d 进行直接插入排序 for(i=d+1;i0&r0rj;j=j-d)rj+d=rj;/记录后移 d 个位置 rj+d=r0;快速排序算法伪码如下：修订者：蔡琼 When you are old and grey and full of sleep,And nodding by the fire,take down this book,And slowly read,and dream of the soft look Your eyes had once,and of their shadows deep;H

20、ow many loved your moments of glad grace,void QuickSort(int r,int first,int end)if(firstend)/递归结束 pivot=Partition(r,first,end);/一次划分 QuickSort(r,first,pivot-1);/递归地对左侧子序列进行快速排序 QuickSort(r,pivot+1,end);/递归地对右侧子序列进行快速排序 int Partition(int r,int first,int end)i=first;j=end;/初始化 while(ij)while(ij&ri=rj)

21、j-;/右侧扫描 if(ij)rirj;/将较小记录交换到前面 i+;while(ij&ri=rj)i+;/左侧扫描 if(ij)rjri;/将较大记录交换到后面 j-;retutn i;/i 为轴值记录的最终位置 And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows of your changing face;And bending down beside the glowing bars,Murmur,a little sad

22、ly,how love fled And paced upon the mountains overhead And hid his face amid a crowd of stars.The furthest distance in the world Is not between life and death But when I stand in front of you Yet you dont know that I love you.The furthest distance in the world Is not when I stand in front of you Yet

23、 you cant see my love But when undoubtedly knowing the love from both Yet cannot be together.The furthest distance in the world Is not being apart while being in love But when I plainly cannot resist the yearning Yet pretending you have never been in my heart.The furthest distance in the world Is no

24、t struggling against the tides But using ones indifferent heart To dig an uncrossable river For the one who loves you.倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。周遭流岚升腾，没露出那真实的面孔。面对那流转的薄雾，我会幻想，那里有一个世外桃源。在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临 许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流 秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。偶尔，一片飞舞的落叶，会飘到我的窗前。斑驳的印迹里，携刻着深秋的颜色。在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。窗外，是未被污染的银白色世界。我会去迎接，这人间的圣洁。在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。