隊列的應(yīng)用火車車廂重排問題

1、一、試驗課題隊列的應(yīng)用實驗?zāi)康模?1) 掌握隊列的特點及其存儲方法；(2) 掌握隊列的常見算法和程序?qū)崿F(xiàn)。二、試驗內(nèi)容(1) 問題描述：一列貨運列車共有 n節(jié)車廂，每節(jié)車廂將停放在不同的車 站。假定n個車站的編號分別為1n，即貨運列車按照第n站至第1站的次序經(jīng) 過這些車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號應(yīng)與車站的編號相 同，這樣，在每個車站只要卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必 須重新排列它們。車廂的重排工作可以通過國轉(zhuǎn)軌站完成。 在轉(zhuǎn)軌站中有一個入 軌、一個出軌和k個緩沖軌，緩沖軌位于入軌和出軌之間。假定緩沖軌按先進先 出飛方式運作，設(shè)計算法解決火車車廂重排問題。(2

2、) 基本要求：設(shè)計存儲結(jié)構(gòu)表示n個車廂、k個緩沖軌以及入軌和出軌; 設(shè)計并實現(xiàn)車廂重排算法；分析算法的時間性能、試驗分析實驗說明：轉(zhuǎn)軌站示意圖如下：Hi581742963 t1H311ii987654321i壬iFiii-產(chǎn)入軌iiH2ii岀軌19635811Fi1H1-*iii入軌11H3742i岀1軌H2(a)將 369、247依次入緩沖軌965 1H1ii! 543211入軌J1H387;岀I-軌H2(c)將8入緩沖軌，5移至岀軌H96H115811 4321入軌1H3-岀軌071:H2(b如將1移至出軌，234移至! 987654321> ! 入軌H3丨岀軌1 ;H2(d)將67

3、89移至出軌火車車廂重排算法偽代碼如下:1. 分別對k個隊列初始化；2. 初始化下一個要輸出的車廂編號nowOut = 1;3. 依次取入軌中的每一個車廂的編號；3.1如果入軌中的車廂編號等于 nowOut，貝U3.1.1輸岀該車廂；3.1.2 nowOut+;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.2 nowOut+ ；3.3如果入軌和緩沖軌的隊頭元素沒有編號為nowOut的車廂，貝U3.3.1求小于入軌中第一個車廂編號的最大隊尾元素

4、所在隊列編號j;3.3.2如果j存在，則把入軌中的第一個車廂移至緩沖軌j ；3.3.2如果j不存在，但有多于一個空緩沖軌，則把入軌中的第一個車廂移至一個 空緩沖軌；否則車廂無法重排，算法結(jié)束；四、源程序代碼#include<iostream>using namespace std;const MS=100;template <class T>struct QNodeT data;QNode<T> *next; template <class T> class LiQueue public:LiQueue( ); / 構(gòu)造函數(shù)，初始化一個空的鏈隊列

5、LiQueue( ); / 析構(gòu)函數(shù)，釋放鏈隊列中各結(jié)點的存儲空間void EnQueue(T x); / 將元素 x 入隊T DeQueue( ); / 將隊頭元素出隊T GetFront( ); /取鏈隊列的隊頭元素T GetRear();bool Empty( ); / 判斷鏈隊列是否為空QNode<T> *front, *rear; / 隊頭和隊尾指針，分別指向頭結(jié)點和終端結(jié)點 ;template <class T>LiQueue<T>:LiQueue( )QNode <T> *s;s=new QNode<T>s->ne

6、xt=NULL;front=rear=s; template <class T> LiQueue<T>:LiQueue( )QNode <T> *p;while(front) p=front;front=front->next;delete p; template <class T>void LiQueue<T>:EnQueue(T x)QNode<T> *s;s=new QNode<T>s->data=x; / 申請一個數(shù)據(jù)域為 x 的結(jié)點 ss->next=NULL;rear->ne

7、xt=s; / 將結(jié)點 s 插入到隊尾 rear=s; template <class T> T LiQueue<T>:DeQueue()QNode <T> *p; int x;if (rear=front) throw "下溢 "p=front->next;x=p->data; / 暫存隊頭元素front->next=p->next; / 將隊頭元素所在結(jié)點摘鏈if (p->next=NULL) rear=front; / 判斷出隊前隊列長度是否為 1 delete p; return x;template

8、 <class T>T LiQueue<T>:GetFront()if (rear!=front)return front->next->data;template <class T>T LiQueue<T>:GetRear()if(rear!=front)return rear->data;template <class T>bool LiQueue<T>:Empty( )if(front=rear) return 0;else return 1;class Trainprivate :int n,k,

9、th;public :Train();void ChongPai();Train:Train()cout<<" 請輸入火車 ( 貨運列車)的車廂個數(shù)為： "<<endl;cin>>n;cout<<" 請輸入轉(zhuǎn)軌站的緩沖軌個數(shù)為： "<<endl;cin>>k;void Train:ChongPai()int aMS;LiQueue<int>*b;b=new LiQueue<int>k+2; cout<<" 請輸入車廂入軌編號次序： &qu

10、ot;<<endl;for(int i=0;i<n;i+)cin>>ai;for(i=n-1;i>=0;i-) bk.EnQueue(ai);cout<<" 則進行車廂重排過程如下 :"<<endl;th=1;while(bk.Empty()int xx=bk.DeQueue(); if(xx=th) cout<<th<<" 號車廂直接移至出軌 "<<endl; bk+1.EnQueue(th);th+;int j=0;while(bj.Empty()int

11、x=bj.GetFront(); if(x=th) cout<<x<<" 號車廂從 "<<j+1<<" 號緩沖軌出軌 "<<endl; bj.DeQueue();bk+1.EnQueue(x);j=0;th+;elsej+; continue;elseint j=0,u=5; while(bj.Empty()&&j<k)if(xx<bj.GetRear() j+;else cout<<xx<<" 號車廂移至 "<<

12、;j+1<<" 號緩沖軌 "<<endl; bj.EnQueue(xx);u=1;break; if(u=5&&j<k)cout<<xx<<" 號車廂移至 "<<j+1<<" 號緩沖軌 "<<endl; bj.EnQueue(xx); if(j=k-1)cout<<"n 緩沖軌不夠，重排車廂失敗 n"return;cout<<" 車廂依次出軌的編號為： "while(

13、bk+1.Empty() cout<<bk+1.DeQueue()<<" " cout<<endl;void main()Train a;a.ChongPai();五、測試用例1當(dāng)有9個火車車廂，3個緩沖軌道時，運行結(jié)果如下:2 3456789請輸入火車（貸運列車）的車廂個數(shù)為: 魯輸入轉(zhuǎn)軌站的緩沖軌個數(shù)為：g *C:Progra* FilesVlicrosoft Vi sual Studi oHyProj ects54adsaEd£Debug54adsasd£. exe*|n| x田22 12呂u 1 n:ti艸 c

14、 -I I I I I至IPQIPalp頁ke 丄2諾小出y 次an.依s下 如九出出出軌丸出出出岀為on1112 2 2龍至至至至至至T.- D-T.-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃-冃.'.!. 1iw83 P'IFLnE<3-6-9-2-4-7-1-2-3-4-8-5-6-7斷車車車車車車車車車車車車車車開 臨口¥-¥-¥-¥-¥-¥-¥-¥-¥-¥-¥-¥-¥-3-2.當(dāng)有12個火車車廂，3個緩沖軌道時，運行

15、結(jié)果如下:3.當(dāng)有12個火車車廂，5個緩沖軌道，運行結(jié)果如下:4.當(dāng)有12個火車車廂，7個緩沖軌道時，運行結(jié)果如下:c : XFrogr« FilesVlicrosaft Vi&tlo1 StudiolyFr«jetsVSt&dsftEdfD«的車廂個數(shù)為;- JLrJ11軌21誇gtJlrolrolnllnl>lpo>lpn¥IFn萬 0 1 2洼輸入轉(zhuǎn)軌站的緩沖軌個數(shù)為;岀岀出軌九出出出岀 2過強緩釁緩巽鏡蠱10重至託至3.4 4廂移聲t； M車廂就廂FP i行車硏車勺 7UK -ti 應(yīng)卅卅為onc 劉窮編to 3423AAAiy 翥護M 赴號車劭車車車簾車車車車車車車車車車車車SS IJS2Elht-iDllho0mi.-m-n1n-Dfl-Dn-nn-nn-Dn-Dn-Dn-i-nmww 拆七''5 ' 3 LE4 £Lul耳色巨l£互& &怪多333多至互： :':'-B耳 冒-專 看 莽-曰-曰-唱-弔-用=書-B一陽申-弔-陽-陽 -h4u耳14|.耳耳耳耳耳耳耳 ：；fjr L ;；：； ：幾次測試都表明試驗設(shè)計的正確性。六、試驗總結(jié)本次試驗中，在解決火車車廂重排問題中， 結(jié)合了最近剛學(xué)的隊列的知識， 并且運用到之