欢迎来到天天文库
浏览记录
ID:55849927
大小:182.50 KB
页数:12页
时间:2020-03-14
《队列的应用火车车厢重排问题.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、xx大学xx学院算法与数据结构试验报告设计名称:算法与数据结构设计题目:队列的应用学生学号:xx专业班级:xx学生姓名:xx学生成绩:指导教师(职称):xx课题工作时间:2012年4月26日说明:实验课程类别:课程内实验实验课程性质:必修适用专业、年级:2010级计算机工程、计算机网络开课院、系:计算机科学与工程学院计算机工程教研室学时:18编写依据:《算法与数据结构》实验教学大纲修订时间:2012年2月《算法与数据结构》课程实验指导书(以下简称:指导书)是针对计算机学院所开设的对应课程的上机实验而编写的教学文件,供学生上机实验时使用。上机的工作环
2、境要求:Windows2000或以上操作系统、VC++6.0或者其它高级程序设计语言。学生应按指导教师的要求独立完成实验,并按要求撰写实验报告。每一个实验,编程上机调试并且提交电子文档实验报告,以学号姓名作为文件名上传。报告内容至少包含如下内容:1、学生基本情况:专业班级、学号、姓名2、实验题目、实验内容3、设计分析4、源程序代码5、测试用例(尽量覆盖所有分支)6、实验总结一.实验内容与学时分配序次实验题目实验类型基本技能训练学时一线性结构综合应用综合性(1)掌握线性结构的常用操作;(2)能够应用线性结构解决比较简单的问题。10二非线性结构综合应用
3、综合性(1)掌握树形、图形结构的插入、删除、查找等算法;(2)能够应用二叉树解决比较简单的问题。4三查找技术综合应用综合性(1)熟练掌握查找的常用算法;(2)熟练设计和应用查找算法解决简单的实际问题。2四排序技术综合应用综合性(1)熟练掌握常用的排序方法,并掌握用高级语言实现排序算法的方法;(2)深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;(3)了解各种方法的排序过程及其依据的原则,并掌握各种排序方法的时间复杂度的分析方法。2一、试验课题队列的应用实验目的:(1)掌握队列的特点及其存储方法;(2)掌握队列的常见算法和程序实现。二、试验
4、内容(1)问题描述:一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n,即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢,车厢的编号应与车站的编号相同,这样,在每个车站只要卸掉最后一节车厢。所以,给定任意次序的车厢,必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨,缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作,设计算法解决火车车厢重排问题。(2)基本要求:设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算
5、法;分析算法的时间性能三、试验分析实验说明:转轨站示意图如下:出轨入轨581742963987654321H1H3H2火车车厢重排过程如下:出轨入轨581H1H3H2963742出轨入轨58H1H3H29674321出轨入轨5H1H3H2968754321出轨入轨H1H3H2987654321(a)将369、247依次入缓冲轨(b)将1移至出轨,234移至出轨(c)将8入缓冲轨,5移至出轨(d)将6789移至出轨火车车厢重排算法伪代码如下:1.分别对k个队列初始化;2.初始化下一个要输出的车厢编号nowOut=1;3.依次取入轨中的每一个车厢的编号
6、;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不存在,但有多于一个空缓冲轨,则把入轨中的第
7、一个车厢移至一个空缓冲轨;否则车厢无法重排,算法结束;一、源程序代码#includeusingnamespacestd;constMS=100;templatestructQNode{Tdata;QNode*next;};templateclassLiQueue{public:LiQueue();//构造函数,初始化一个空的链队列~LiQueue();//析构函数,释放链队列中各结点的存储空间voidEnQueue(Tx);//将元素x入队TDeQueue();//将队头元素出队TGetFr
8、ont();//取链队列的队头元素TGetRear();boolEmpty();//判断链队列是否为空QNode*f
此文档下载收益归作者所有