隊列的應用火車車廂重排問題

./試驗課題隊列的應用實驗目的：〔1掌握隊列的特點及其存儲方法；〔2掌握隊列的常見算法和程序實現(xiàn)。試驗容<1>問題描述：一列貨運列車共有n節(jié)車廂,每節(jié)車廂將停放在不同的車站。假定n個車站的編號分別為1~n,即貨運列車按照第n站至第1站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應的車廂,車廂的編號應與車站的編號相同,這樣,在每個車站只要卸掉最后一節(jié)車廂。所以,給定任意次序的車廂,必須重新排列它們。車廂的重排工作可以通過國轉軌站完成。在轉軌站中有一個入軌、一個出軌和k個緩沖軌,緩沖軌位于入軌和出軌之間。假定緩沖軌按先進先出飛方式運作,設計算法解決火車車廂重排問題。<2>基本要求：設計存儲結構表示n個車廂、k個緩沖軌以及入軌和出軌;設計并實現(xiàn)車廂重排算法；分析算法的時間性能試驗分析實驗說明：轉軌站示意圖如下：出軌出軌入軌581742963987654321H1H3H2火車車廂重排過程如下：出軌出軌入軌581H1H3H2963742出軌入軌58H1H3H29674321出軌入軌5H1H3H2968754321出軌入軌H1H3H2987654321<a>將369、247依次入緩沖軌<b>將1移至出軌,234移至出軌<c>將8入緩沖軌,5移至出軌<d>將6789移至出軌火車車廂重排算法偽代碼如下：1.分別對k個隊列初始化；1.分別對k個隊列初始化；2.初始化下一個要輸出的車廂編號nowOut=1;3.依次取入軌中的每一個車廂的編號；3.1如果入軌中的車廂編號等于nowOut,則輸出該車廂；nowOut++；3.2否則,考察每一個緩沖軌隊列for<j=1;j<=k;j++>取隊列j的隊頭元素c；如果c=nowOut,則.1將隊列j的隊頭元素出隊并輸出；.2nowOut++；3.3如果入軌和緩沖軌的隊頭元素沒有編號為nowOut的車廂,則求小于入軌中第一個車廂編號的最大隊尾元素所在隊列編號j;如果j存在,則把入軌中的第一個車廂移至緩沖軌j；如果j不存在,但有多于一個空緩沖軌,則把入軌中的第一個車廂移至一個空緩沖軌；否則車廂無法重排,算法結束；源程序代碼#include<iostream>usingnamespacestd;constMS=100;template<classT>structQNode{ Tdata; QNode<T>*next;};template<classT>classLiQueue{ public: LiQueue<>;//構造函數(shù),初始化一個空的鏈隊列 ~LiQueue<>;//析構函數(shù),釋放鏈隊列中各結點的存儲空間 voidEnQueue<Tx>;//將元素x入隊 TDeQueue<>;//將隊頭元素出隊 TGetFront<>;//取鏈隊列的隊頭元素 TGetRear<>; boolEmpty<>;//判斷鏈隊列是否為空 QNode<T>*front,*rear;//隊頭和隊尾指針,分別指向頭結點和終端結點};template<classT>LiQueue<T>::LiQueue<>{ QNode<T>*s;s=newQNode<T>;s->next=NULL;front=rear=s;}template<classT>LiQueue<T>::~LiQueue<>{ QNode<T>*p; while<front> { p=front;front=front->next;deletep; }}template<classT>voidLiQueue<T>::EnQueue<Tx>{ QNode<T>*s;s=newQNode<T>; s->data=x;//申請一個數(shù)據(jù)域為x的結點s s->next=NULL; rear->next=s;//將結點s插入到隊尾 rear=s;}template<classT>TLiQueue<T>::DeQueue<>{ QNode<T>*p;intx; if<rear==front>throw"下溢"; p=front->next; x=p->data;//暫存隊頭元素 front->next=p->next;//將隊頭元素所在結點摘鏈 if<p->next==NULL>rear=front;//判斷出隊前隊列長度是否為1 deletep; returnx;}template<classT>TLiQueue<T>::GetFront<>{ if<rear!=front> returnfront->next->data;}template<classT>TLiQueue<T>::GetRear<>{ if<rear!=front>returnrear->data;}template<classT>boolLiQueue<T>::Empty<> { if<front==rear>return0;elsereturn1;}classTrain{ private: intn,k,th; public: Train<>;voidChongPai<>;};Train::Train<>{ cout<<"請輸入火車<貨運列車的車廂個數(shù)為："<<endl; cin>>n; cout<<"請輸入轉軌站的緩沖軌個數(shù)為："<<endl; cin>>k;}voidTrain::ChongPai<>{ inta[MS];LiQueue<int>*b; b=newLiQueue<int>[k+2]; cout<<"請輸入車廂入軌編號次序："<<endl; for<inti=0;i<n;i++> cin>>a[i]; for<i=n-1;i>=0;i--> b[k].EnQueue<a[i]>; cout<<"則進行車廂重排過程如下:"<<endl; th=1; while<b[k].Empty<>> { intxx=b[k].DeQueue<>; if<xx==th> { cout<<th<<"號車廂直接移至出軌"<<endl; b[k+1].EnQueue<th>; th++; intj=0; while<b[j].Empty<>> { intx=b[j].GetFront<>; if<x==th> { cout<<x<<"號車廂從"<<j+1<<"號緩沖軌出軌"<<endl; b[j].DeQueue<>;b[k+1].EnQueue<x>; j=0;th++; } else j++; } continue; } else { intj=0,u=5; while<b[j].Empty<>&&j<k> { if<xx<b[j].GetRear<>> j++; else { cout<<xx<<"號車廂移至"<<j+1<<"號緩沖軌"<<endl; b[j].EnQueue<xx>; u=1;break; } } if<u==5&&j<k> { cout<<xx<<"號車廂移至"<<j+1<<"號緩沖軌"<<endl; b[j].EnQueue<xx>; } if<j==k-1> { cout<<"\n緩沖軌不夠,重排車廂失敗\n";return; } } } cout<<"車廂依次出軌的編號為："; while<b[k+1].Empty<>> cout<<b[k+1].DeQueue<><<""; cout<<endl;}voidmain<>{ Traina;a.ChongPai<>;}測試用例1.當有9個火車車廂,3個緩沖軌道時,運行結果如下：2.當有12個火車車廂,3個緩沖軌道時,運行結果如下：3.當有12個火車車廂,5個緩沖軌道,運行結果如下：4.當有12個火車車廂,7個緩沖軌道時,運行結果如下：幾次測試都表明試驗設計的正確性。試驗總結本次試驗中,在解決火車車廂重排問題中,結合了最近剛學的隊列的知識,并且運用到之前C++語言,很好的解決了這一類問題。其中,每一個軌道緩沖區(qū)就形如一個隊列一樣,車廂先進緩沖軌道的要先出來,所