队列的应用火车车厢重排问题

《队列的应用火车车厢重排问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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）能够应用线

3、性结构解决比较简单的问题。10二非线性结构综合应用综合性（1）学握树形、图形结构的插入、删除、查找等算法；（2）能够应用二叉树解决比较简单的问题。4三查找技术综合应用综合性（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决简单的实际问题。2四排序技术综合应用综合性（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2一、试验课题队列的应用实验目的：(1

4、)常握队列的特点及其存储方法；(2)常握队列的常见算法和程序实现。二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为广n,即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重

5、排问题。(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：亠581742963iH丨987654321>>]>——入轨：[出轨火车车厢重排过程如下963ri581!1Hiiiii入轨丨i比742［出轨ii(a)将369、h2247依次入缓冲轨96ii5iH1i

6、54321入轨］i日3871出轨1»-►1兄(c)将8入缓冲轨.5移至出轨9658,尽一4321入轨比7出轨H2(b)…将1移至出轨，234移至厂.--iiiiAH、

7、987654321入轨Iii・•・■►出轨(d)将6789移至出轨火车车厢重排算法伪代码如下:1.分别对k个队列初始化；2.初始化卜•一个要输出的车厢编号nowOut=1;3.依次取入轨中的每一个车厢的编号；3」如果入轨中的车厢编号等于nowOut,则3」」输出该车厢；3.1.2nowOut卄；3.2否则，考察每一个缓冲轨队列for(j=l;jv=k;j++)3.2.1取队列j的队头元素c；3.2.2如果c二nowOut,则3.2.2.1将队列j的队头元素出队并输出；3.2.2.2nowOut++；3.3如果入轨和缓冲轨的队

8、头元素没有编号为nowOut的车厢，则3.3」求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;3.3.2如果j存在，则把入轨中的第一个车厢移至缓冲轨j；3.3.2如果j不存在，但有多于一个空缓冲轨，则把入轨屮的第一个车厢移至一个空缓冲轨；否则车厢无法巫排，算法结束；四、源程序代码#includeusingnamcspaccstd;constMS=100;templatestructQNode{Tdata;QNode*next;}；templateclassLi

9、Queue{public:LiQueue();〃构造函数，初始化一个空的链队列LiQueue();〃析构函数,—释放链队列中各结点的存储空间voidEnQueue(Tx);//将元素x入队TDcQucuc();//将队头元素岀队TGetFront();//取链队列的队头元素TGetRear