【精品】算法与数据结构实验指导书

《【精品】算法与数据结构实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、名上传。报告内容至少包含如下内容：1、学生基木情况：专业班级、学号、姓名2、丈验题1=1、实验内容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(n>0)个人按顺时针方向围处一圈，m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数,报到m时停止并且报m的人出列，再从他的下一个人开始重新从1报数，报到m时停止并II报m的人出列

4、。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的ni和n,求出出列编号序列。3、实验要求：用顺序表实现。(-)链表的应用1、实验目的:(1)熟练掌握链表结构及有关算法的设计；(3)掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。2、实验内容：一元多项式求和。把任意给定的两个一元多项式P(x),Q(x)输入计算机，计算它们的和并输出计算结果。3、实验说明：-•元多项式可以用单链表表示，结点结构图示如coefexpnext一•元多项式链表的结点结构一元多项式算法伪代码如下:1.工作指针p、q初始化：2.while(p存在且q存在)执行下列三种情形Z—2」如

5、果p->expexp,则指针p后移;2.2如果p->exp>q->exp,贝92.2.1将结点q插入到结点pZ前；2.2.2指针q指向原指结点的下一个结点；2.3如果p->exp=q->exp,则2.3.1p->cocf=p->cocf+q->cocf；2.3.2如果p->coef==(),则执行下列操作，否则，指针p后移;2.3.2」删除结点p：2.322使指针p指向它原指结点的下一个结点；2.3.3删除结点q；2.3.4使指针q指向它原指结点的下一个结点；1.如果q不为空，将结点q链接在第一个单链表的后面；(三)栈的应用1、实验目的:(1)掌握栈的特点及其存储方法；(2)掌握栈的常

6、见算法以及程序实现;(3)了解递归的工作过程。2、实验内容:Hanoi塔问题。(要求4个盘子移动，输出中间结果)3、实验说明：三个盘子Hanoi求解示意图如下:ABCA(aABC(b)BC三个盘子汉诺塔算法的超行轨迹:(d)Hanio算法如卜'：1voidHcinoi(intn,charA,charB,charC)〃第一列为语句行号2{3讦(n==l)Move(A,C)；//Move是一个抽彖操竹•:，表示将碟了从A移到€：上4else{5Hanoi(n~l,A,C,B);6Move(A,C);7Hanoi(nT,B,A,C);8}9}(四)队列的应用1、实验目的：(1)学握队列的特点及其存储

7、方法；(1)掌:握队列的常见算法和程序实现。2、实验内容：火车车厢重排问题。3、实验说明：转轨站示意图如下：J581742963!¥分别对k个队列初始化；初始化下一个要输出的车用I编号nowOut=1;依次取入轨中的毎一个车厢的编号；3.1如果入轨小的车厢编号等于nowOut，则3.1.1输出该车厢；3.1.2nowOut++；3.2否则，考察每一个缓冲轨队列for(j=l；jv=k;j++)3.