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

xx大学 xx学院算法与数据结构试验报告设计名称： 算法与数据结构 设计题目： 队列的应用 学生学号： xx 专业班级： xx 学生姓名： xx 学生成绩： 指导教师（职称）： xx 课题工作时间： 2012年4月26日 说明：实验课程类别：课程内实验实验课程性质：必修适用专业、年级：2010级计算机工程、计算机网络开课院、系：计算机科学与工程学院计算机工程教研室学时：18编写依据：算法与数据结构实验教学大纲修订时间：2012年2月算法与数据结构课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。上机的工作环境要求：Windows 2000或以上操作系统、VC+ 6.0或者其它高级程序设计语言。学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容：1、 学生基本情况：专业班级、学号、姓名2、 实验题目、实验内容3、 设计分析4、 源程序代码5、 测试用例（尽量覆盖所有分支）6、 实验总结一实验内容与学时分配序次实验题目实验类型基本技能训练学时一线性结构综合应用综合性（1）掌握线性结构的常用操作；（2）能够应用线性结构解决比较简单的问题。10二非线性结构综合应用综合性（1）掌握树形、图形结构的插入、删除、查找等算法；（2）能够应用二叉树解决比较简单的问题。4三查找技术综合应用综合性（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决简单的实际问题。2四排序技术综合应用综合性（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2一、 试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。二、 试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能 三、 试验分析实验说明：转轨站示意图如下：出 轨入 轨581742963987654321H1H3H2 火车车厢重排过程如下：出 轨入 轨 581H1H3H2963742出 轨入 轨 58H1H3H29674321出 轨入 轨5H1H3H2968754321出 轨入 轨H1H3H2987654321(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.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 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；四、 源程序代码#includeusing namespace std;const MS=100;template struct QNodeT data;QNode *next;template class LiQueuepublic:LiQueue( ); /构造函数，初始化一个空的链队列LiQueue( ); /析构函数，释放链队列中各结点的存储空间void EnQueue(T x); /将元素x入队T DeQueue( ); /将队头元素出队T GetFront( ); /取链队列的队头元素T GetRear();bool Empty( ); /判断链队列是否为空QNode *front, *rear; /队头和队尾指针，分别指向头结点和终端结点;template LiQueue:LiQueue( )QNode *s;s=new QNode;s-next=NULL;front=rear=s;template LiQueue:LiQueue( )QNode *p;while(front)p=front;front=front-next;delete p;template void LiQueue:EnQueue(T x)QNode *s;s=new QNode; s-data=x; /申请一个数据域为x的结点ss-next=NULL;rear-next=s; /将结点s插入到队尾rear=s;template T LiQueue:DeQueue() QNode *p; int x;if (rear=front) throw 下溢;p=front-next; x=p-data; /暂存队头元素front-next=p-next; /将队头元素所在结点摘链if (p-next=NULL) rear=front; /判断出队前队列长度是否为1delete p;return x;template T LiQueue:GetFront()if (rear!=front) return front-next-data;template T LiQueue:GetRear()if(rear!=front)return rear-data;template bool LiQueue:Empty( )if(front=rear) return 0;else return 1;class Trainprivate :int n,k,th;public :Train();void ChongPai();Train:Train()cout请输入火车(货运列车）的车厢个数为：n;cout请输入转轨站的缓冲轨个数为：k;void Train:ChongPai()int aMS;LiQueue*b;b=new LiQueuek+2;cout请输入车厢入轨编号次序：endl;for(int i=0;iai;for(i=n-1;i=0;i-)bk.EnQueue(ai);cout则进行车厢重排过程如下:endl;th=1;while(bk.Empty()int xx=bk.DeQueue();if(xx=th)coutth号车厢直接移至出轨endl;bk+1.EnQueue(th);th+;int j=0;while(bj.Empty()int x=bj.GetFront();if(x=th)coutx号车厢从j+1号缓冲轨出轨endl;bj.DeQueue();bk+1.EnQueue(x);j=0;th+;elsej+;continue;else int j=0,u=5;while(bj.Empty()&jk)if(xxbj.GetRear()j+;else coutxx号车厢移至j+1号缓冲轨endl;bj.EnQueue(xx);u=1;break;if(u=5&jk)coutxx号车厢移至j+1号缓冲轨endl;bj.EnQueue(xx);if(j=k-1)coutn缓冲轨不够，重排车厢失败n;return;cout车厢依次出轨的编号为：;while(bk+1.Empty()coutbk+1.DeQueue() ;coutendl;void main()Train a;a.ChongPai();五、 测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。六、 试验总结本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前C+语言，很好的解决了这一类问题。其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨