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

《队列的应用火车车厢重排问题》由会员分享，可在线阅读，更多相关《队列的应用火车车厢重排问题（13页珍藏版）》请在装配图网上搜索。

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

2、问题。(2)基本要求：设计存储结构表示 n 个车厢、k 个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能、试验分析实验说明：转轨站示意图如下：Hi581742963H3:987654321-L-火车车厢重排过程如下:H2581_-963H1I II入轨H3岀轨742jH2(a)将 369、247 依次入缓冲轨196iH15!54321入轨H3i 岀轨871H2(c)将 8 入缓冲轨，5 移至岀轨11961H158114321入轨H3:岀轨171H2出)轨将1移至出轨，234移至:H1；1987654321F-1-J入轨H3丨岀轨IIIH2(d)将 6789 移至出轨火车车厢重

3、排过程如下:火车车厢重排算法伪代码如下:1.分别对 k 个队列初始化；2.初始化下一个要输出的车厢编号nowOut=1;3.依次取入轨中的每一个车厢的编号；3.1 如果入轨中的车厢编号等于 nowOut，贝 U3.1.1 输岀该车厢；3.1.2nowOut+;3.2 否则，考察每一个缓冲轨队列for(j=1;jv=k;j+)3.2.1 取队列 j 的队头元素 c；3.2.2 如果 c=nowOut，贝 U3.2.2.1 将队列 j 的队头元素出队并输出；3.2.2.2nowOut+；3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut 的车厢，贝 U3.3.1 求小于入轨中第一个车厢编号的

4、最大队尾元素所在队列编号j;3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨j；3.3.2 如果 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个 空缓冲轨；否则车厢无法重排，算法结束；四、源程序代码#in cludeusing n amespace std;const MS=100;template struct QNodeT data;QNode*n ext;template class LiQueuepublic:LiQueue();/构造函数，初始化一个空的链队列LiQueue();/析构函数，释放链队列中各结点的存储空间void EnQueue(T x);

5、/将元素 x 入队T DeQueue();/将队头元素出队T GetFro nt();/取链队列的队头元素T GetRear();bool Empty();/判断链队列是否为空QNode*fron t,*rear;/队头和队尾指针，分别指向头结点和终端结点;template LiQueue:LiQueue()QNode *s;s=new QNode;s-n ext=NULL;fr on t=rear=s;template LiQueue:LiQueue()QNode *p;while(fro nt)p=fron t;fr ont=front-n ext;delete p;template vo

6、id LiQueue:E nQueue(T x)QNode*s;s=new QNode;s-data=x;/申请一个数据域为 x 的结点 ss-n ext=NULL;rear-next=s;/将结点 s 插入至 U 队尾 rear=s;template T LiQueue:DeQueue()QNode *p;int x;if(rear=fro nt)throw 下溢;p=front-n ext;x=p-data;/暂存队头元素fron t-next=p-next;/将队头元素所在结点摘链if(p-next=NULL)rear=fro nt;/判断出队前队列长度是否为 1delete p;ret

7、urn x;template T LiQueue:GetFro nt()if(rear!=fro nt)retur n fron t-n ext-data;template T LiQueue:GetRear()if(rear!=fr on t)retur n rear-data;template bool LiQueue:Empty()if(fron t=rear)return 0;else return 1;class Trainprivate:int n,k,th;public:Train();void Chon gPai();Trai n:Trai n()coutvv请输入火车(货运列

8、车)的车厢个数为：endl;cinn;coutvv请输入转轨站的缓冲轨个数为：k;void Trai n:Ch on gPai()int aMS;LiQueue*b;b=new LiQueuev in tk+2;coutvv请输入车厢入轨编号次序：vvendl;for(int i=0;ivn;i+)cin ai;for(i=n-1;i=0;i-)bk.E nQueue(ai);coutvv则进行车厢重排过程如下:vvendl;th=1;while(bk.Empty()int xx=bk.DeQueue();if(xx=th)coutvvthvv号车厢直接移至出轨vvendl;bk+1.E nQ

9、ueue(th);th+;int j=0;while(bj.Empty()int x=bj.GetFro nt();if(x=th)coutvvxvv号车厢从vvj+1vv号缓冲轨出轨vvendl;bj.DeQueue();bk+1.E nQueue(x);j=O;th+;elsej+;con ti nue;elseint j=0,u=5;while(bj.Empty()&jvk)if(xxb|j.GetRear()j+；elsecoutvvxxvv号车厢移至j+1号缓冲轨endl;bj.E nQueue(xx);u=1;break;if(u=5&jk)coutvvxxvv号车厢移至j+1号缓

10、冲轨endl;bj.EnQueue(xx);if(j=k-1)coutn 缓冲轨不够，重排车厢失败n;return;coutvv车厢依次出轨的编号为：;while(bk+1.Empty()coutvbk+1.DeQueue()vv;coutvve ndl;void mai n()Train a;a.Ch on gPai();五、测试用例1 1当有 9 9 个火车车厢，3 3 个缓冲轨道时，运行结果如下:亡*C:kPr QgTrui Filicx-osoEt Vi su-kl S-tudio j ecl.s54ndsA；ad.Debug：G4&ds asd.cz e-Jnl v v序下次如机岀岀

11、歳丸出出出出酋DI1DI1编ftcocoY YX X1 1t:t:_l_l1-_l_l1-2 2-2 2-.a.al-m-Dn-nr-D-l-m-Dn-nr-D-劭2 2福至至至至至至iF 7 Er HP rn npn ru.T-nH-r-MHr Fnr.mH.rrp.nTrHT.-DH-DZL-mT w亍JrJTJTff/JrJTJTff/r r阳/F/F用井幷用庫库印花小544IS$r544IS$r薛R R;IJlIJlLllral?al?alpo.pqp4poLllral?al?alpo.pqp4po苕瓦占吾ITOX-言S SJ J臨Kt至zhgzhg畑MhhlMhhl出y y次anan

12、厢“2.2.当有 1212 个火车车厢，3 3 个缓冲轨道时，运行结果如下:3.3.当有 1212 个火车车厢，5 5 个缓冲轨道，运行结果如下:11ill址中轨旦请输人火车（贺运列车）的车頤个数为I誇输人转轨站的緩冲軌个数为1z.匚：IPLFi 1 Hcir-oZOf t Vi u-aJ.Stn.di.oHyPro j ae iLs54nd!=-a.cd.f De&-4a.ds as.ex c请输人车用入轨編号次序*57134 10 92 11 8 12则进押至朋重肖1淨车瞬至卜缓冲轨不够，董排车厢失败Picss anky to cant ious4.4.当有 1212 个火车车厢，7 7

13、个缓冲轨道时，运行结果如下:*C:XFrogr输入火车货运列弃）的弃厢个数为u F i_es Viicrosoft iSUSLIS tudi olyFrOjecf.s54&dsas:dfDebufV5.,.6 61 12 2口言！F-n-n-ili iliHHH;ti;ti-勢肌出出出轨衣出出出岀ntAinintAini为onon的-h hcece专出出出花梓店3 37 74 4厨厢两厢厢厢甫厢厢厢厢厢厢ffl厢厢厢厢厢原昴康汐2 2 7 7丿/牛再Fm4JJLJF1T4L4LUJFF4IJ-4-JJ-41J4UHJF-输输？_“号2 2-S S号苕卫y y直1 10 0重至f f2 2全也创

14、百至舀l la am ml l韦号已詡恫多耳多吕w wa a多互丑吉4 4 5 5 4 4 r ra a总3 3 4 4 2 2 3 3.曹车討车车鑫车车车车车车车车车车车咅总卡号一口莒包有口百言包岂旨IPQIFQInJIPalFUlp45S 789101112几次测试都表明试验设计的正确性。六、试验总结本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识,并且运用到之前 C+语言，很好的解决了这一类问题。其中，每一个轨道缓冲 区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队 列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题。通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是 一种先进队列的后出队列的储存结构。本次试验让我更好的把书本上的知识运 用到具体的例子中来，学会了通过 VC6.0 来建立队列，以及初始化队列、进队 列、出队列等等。同时也了解到了火车车厢重排问题可以通过队列的相关知识 来解决，也体会其中算法的奥妙。