级算法与数据结构实验指导书18.docx
《级算法与数据结构实验指导书18.docx》由会员分享，可在线阅读，更多相关《级算法与数据结构实验指导书18.docx（18页珍藏版）》请在冰点文库上搜索。
级算法与数据结构实验指导书18
实验课程类别：
课程内实验
实验课程性质：
必修
适用专业、年级：
2012级计算机大类
开课院、系：
计算机科学与工程学院
学时：
18
编写依据：
《算法与数据结构》实验教学大纲
修订时间：
2014年2月
《算法与数据结构》课程实验指导书（以下简称：
指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。
上机的工作环境要求：
Windows2000或以上操作系统、VC++6.0或者其它高级程序设计语言。
学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。
每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。
报告内容至少包含如下内容：
1、学生基本情况：
专业班级、学号、姓名
2、实验题目、实验内容
3、设计分析
4、源程序代码
5、测试用例（尽量覆盖所有分支）
6、实验总结
一．实验内容与学时分配
序次
实验
题目
实验
类型
基本技能训练
学时
一
线性结构综合应用
基础性
（1）掌握线性结构的常用操作；
（2）能够应用线性结构解决比较简单的问题。
10
二
非线性结构综合应用
设计性
（1）掌握树形、图形结构的插入、删除、查找等算法；
（2）能够应用二叉树解决比较简单的问题。
4
三
查找技术综合应用
设计性
（1）熟练掌握查找的常用算法；
（2）设计和应用查找算法解决简单的实际问题。
2
四
排序技术综合应用
基础性
（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；
（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
2
二．实验说明
实验一、线性结构综合应用
（一）顺序表的应用
1、实验目的：
（1）掌握用VC++上机调试线性表的基本方法；
（2）掌握顺序表的存储结构以及基本运算的实现。
2、实验内容
约瑟夫环问题：
设编号为1，2，3，……，n的n（n>0）个人按顺时针方向围坐一圈，m为任意一个正整数。
从第一个人开始顺时针方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下一个人开始重新从1报数，报到m时停止并且报m的人出列。
如此下去，直到所有人全部出列为止。
要求设计一个程序模拟此过程，对任意给定的m和n，求出出列编号序列。
3、实验要求：
用顺序表实现。
（二）链表的应用
1、实验目的：
（1）熟练掌握链表结构及有关算法的设计；
（3）掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。
2、实验内容：
一元多项式求和。
把任意给定的两个一元多项式P（x） ,Q（x） 输入计算机，计算它们的和并输出计算结果。
3、实验说明：
一元多项式可以用单链表表示，结点结构图示如下：
一元多项式链表的结点结构
coefexpnext
一元多项式算法伪代码如下：
1.工作指针p、q初始化；
2.while（p存在且q存在）执行下列三种情形之一
2.1如果p->expexp，则指针p后移;
2.2如果p->exp>q->exp，则
2.2.1将结点q插入到结点p之前；
2.2.2指针q指向原指结点的下一个结点；
2.3如果p->exp=q->exp，则
2.3.1p->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.如果q不为空，将结点q链接在第一个单链表的后面；
（三）栈的应用
1、实验目的：
（1）掌握栈的特点及其存储方法；
（2）掌握栈的常见算法以及程序实现；
（3）了解递归的工作过程。
2、实验内容：
表达式求值问题。
这里限定的表达式求值问题是：
用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。
算术表达式求值过程是：
STEP1：
先将算术表达式转换成后缀表达式。
STEP2：
然后对该后缀表达式求值。
3、实验说明：
在设计相关算法中用到栈，这里采用顺序栈存储结构。
初始化运算符栈op;
将'='进栈;
从exp读取字符ch;
while（ch!
='\0'）
{if（ch不为运算符）
将后续的所有数字均依次存放到postexp中,并以字符'#'标志数值串结束;
else
switch（Precede（op栈顶运算符,ch））
{
case'<':
//栈顶运算符优先级低
将ch进栈;从exp读取下字符ch;break;
case'=':
//只有栈顶运算符为'（',ch为'）'的情况
退栈;从exp读取下字符ch;break;
case'>':
//栈顶运算符应先执行,所以出栈并存放到postexp中
退栈运算符并将其存放到postexp中;break;
}
}
若字符串exp扫描完毕,则将运算符栈op中'='之前的所有运算符依次出栈并存放到postexp中。
最后得到后缀表达式postexp;
中缀表达式exp⇒⇒后缀表达式postexp伪代码如下：
while（从postexp读取字符ch,ch!
='\0'）
{若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。
若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。
若ch为“－”,则从数值栈st中退栈两个运算数,相减后进栈st中。
若ch为“*”,则从数值栈st中退栈两个运算数,相乘后进栈st中。
若ch为“/”,则从数值栈st中退栈两个运算数,相除后进栈st中（若除数为零,则提示相应的错误信息）。
}
若字符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。
对后缀表达式postexp求值伪代码如下：
（四）队列的应用
1、实验目的：
（1）掌握队列的特点及其存储方法；
（2）掌握队列的常见算法和程序实现。
2、实验内容：
火车车厢重排问题。
3、实验说明：
出轨
入轨
581742963
987654321
H1
H3
H2
转轨站示意图如下：
出轨
入轨
581
H1
H3
H2
963
742
出轨
入轨
58
H1
H3
H2
96
7
4321
出轨
入轨
5
H1
H3
H2
96
87
54321
出轨
入轨
H1
H3
H2
987654321
（a）将369、247依次入缓冲轨
（b）将1移至出轨，234移至出轨
（c）将8入缓冲轨，5移至出轨
（d）将6789移至出轨
火车车厢重排过程如下：
火车车厢重排算法伪代码如下：
1.分别对k个队列初始化；
2.初始化下一个要输出的车厢编号nowOut=1;
3.依次取入轨中的每一个车厢的编号；
3.1如果入轨中的车厢编号等于nowOut，则
3.1.1输出该车厢；
3.1.2nowOut++；
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.2nowOut++；
3.3如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则
3.3.1求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;
3.3.2如果j存在，则把入轨中的第一个车厢移至缓冲轨j；
3.3.2如果j不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；
（五）稀疏矩阵的应用
1、实验目的：
（1）掌握掌握稀疏矩阵的表示方法及其运算的实现；
（2）实现稀疏矩阵在三元组、十字链表等表示下的各运算并分析其效率。
2、实验内容
在m×n的矩阵中，有t个非零元。
令δ=t/（m*n）,称δ矩阵的稀疏因子，常认为δ≤0.05时称为稀疏矩阵。
稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。
用三元组表实现稀疏矩阵的转置，用（顺序取，直接存）方法。
3、实验说明：
引入两个数组作为辅助数据结构：
num[nu]：
表示矩阵A中某列的非零元素的个数；
cpot[nu]：
初始值表示矩阵A中某列的第一个非零元素在B中的位置。
num与cpot递推关系：
cpot[0]=0;
cpot[col]=cpot[col-1]+num[col-1];1≤col
三元组表实现稀疏矩阵的转置（顺序取，直接存）算法伪代码如下：
1.设置转置后矩阵B的行数、列数和非零元素的个数；
2.计算A中每一列的非零元素个数；
3.计算A中每一列的第一个非零元素在B中的下标；
4.依次取A中的每一个非零元素对应的三元组；
4.1确定该元素在B中的下标pb；
4.2将该元素的行号列号交换后存入B中pb的位置；
4.3预置该元素所在列的下一个元素的存放位置；
实验二、非线性结构综合应用
（六）树的应用
1、实验目的：
（1）针对问题的实际要求，正确应用树形结构组织和存储数据；
（2）掌握二叉树的存储方法。
（3）掌握二叉树的各种遍历方法。
2、实验内容:
二叉树后序遍历的非递归算法。
3、实验说明：
二叉树后序遍历的非递归算法：
结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。
1第一次出栈，只遍历完左子树，该结点不能访问
2第二次出栈，遍历完右子树，该结点可以访问
flag＝
设根指针为root，则可能有以下两种情况：
⑴若root!
=NULL，则root及标志flag（置为1）入栈，遍历其左子树；
⑵若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。
若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。
二叉树后序遍历的非递归算法伪代码如下：
1.栈s初始化；
2.循环直到root为空且栈s为空
2.1当root非空时循环
2.1.1将root连同标志flag=1入栈；
2.1.2继续遍历root的左子树；
2.2当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;
2.3若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；
（七）图的应用
1、实验目的：
（1）熟练掌握图的基本存储方法；
（2）熟练掌握图的深度优先和广度优先搜索方法；
（3）掌握AOV网和拓扑排序算法；
（4）掌握AOE网和关键路径。
2、实验内容：
拓扑排序。
任意给定一个有向图，设计一个算法，对它进行拓扑排序。
拓扑排序算法思想：
a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。
3、实验说明：
拓扑排序算法伪代码如下：
1.栈S初始化；累加器count初始化；
2.扫描顶点表，将没有前驱（即入度为0）的顶点压栈；
3.当栈S非空时循环
3.1vj=退出栈顶元素；输出vj；累加器加1；
3.2将顶点vj的各个邻接点的入度减1；
3.3将新的入度为0的顶点入栈；
4.if（count
实验三、查找技术综合应用
（八）查找技术综合应用
1、实验目的：
（1）熟练掌握查找的常用算法；
（2）熟练设计和应用查找算法解决比较简单的实际问题。
2、实验内容：
二叉排序树。
任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。
3、实验说明：
二叉排序树存储结构如下：
typedefstructBiTNode{//结点结构
structBiTNode*lchild,*rchild;
//左右孩子指针
}BiTNode,*BiTree;
二叉排序树插入算法伪代码如下：
1.若root是空树，则将结点s作为根结点插入；否则
2.若s->data＜root->data，则把结点s插入到root的左子树中；否则
3.把结点s插入到root的右子树中。
二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：
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；
实验四、排序技术综合应用
（九）排序技术综合应用
1、实验目的：
（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；
（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；
（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
2、实验内容：
对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。
任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组数据：
单增、单减、乱码等，对它们进行比较分析。
3、实验说明：
希尔排序算法如下：
voidShellSort（intr[],intn）
{
for（d=n/2;d>=1;d=d/2）//以增量为d进行直接插入排序
{
for（i=d+1;i<=n;i++）
{
r[0]=r[i];//暂存被插入记录
for（j=i-d;j>0&&r[0]r[j+d]=r[j];//记录后移d个位置
r[j+d]=r[0];
}
}
}
快速排序算法伪码如下：
voidQuickSort（intr[],intfirst,intend）
{
if（firstpivot=Partition（r,first,end）;//一次划分
QuickSort（r,first,pivot-1）;//递归地对左侧子序列进行快速排序
QuickSort（r,pivot+1,end）;//递归地对右侧子序列进行快速排序
}
}
intPartition（intr[],intfirst,intend）
{
i=first;j=end;//初始化
while（i{
while（iif（ir[i]←→r[j];//将较小记录交换到前面
i++;
}
while（iif（ir[j]←→r[i];//将较大记录交换到后面
j--;
}
}
retutni;//i为轴值记录的最终位置
}
修订者：
蔡琼
2014-2
Whenyouareoldandgreyandfullofsleep,
Andnoddingbythefire,takedownthisbook,
Andslowlyread,anddreamofthesoftlook
Youreyeshadonce,andoftheirshadowsdeep;
Howmanylovedyourmomentsofgladgrace,
Andlovedyourbeautywithlovefalseortrue,
Butonemanlovedthepilgrimsoulinyou,
Andlovedthesorrowsofyourchangingface;
Andbendingdownbesidetheglowingbars,
Murmur,alittlesadly,howlovefled
Andpaceduponthemountainsoverhead
Andhidhisfaceamidacrowdofstars.
Thefurthestdistanceintheworld
Isnotbetweenlifeanddeath
ButwhenIstandinfrontofyou
Yetyoudon'tknowthat
Iloveyou.
Thefurthestdistanceintheworld
IsnotwhenIstandinfrontofyou
Yetyoucan'tseemylove
Butwhenundoubtedlyknowingthelovefromboth
Yetcannotbetogether.
Thefurthestdistanceintheworld
Isnotbeingapartwhilebeinginlove
ButwhenIplainlycannotresisttheyearning
Yetpretendingyouhaveneverbeeninmyheart.
Thefurthestdistanceintheworld
Isnotstrugglingagainstthetides
Butusingone'sindifferentheart
Todiganuncrossableriver
Fortheonewholovesyou.
升级会员 