隊(duì)列的應(yīng)用火車(chē)車(chē)廂重排問(wèn)題

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

2、存儲(chǔ)結(jié)構(gòu)表示n個(gè)車(chē)廂、k個(gè)緩沖軌以及入軌和出軌;設(shè)計(jì)并實(shí)現(xiàn)車(chē)廂重排算法；分析算法的時(shí)間性能 三、 試驗(yàn)分析實(shí)驗(yàn)說(shuō)明：轉(zhuǎn)軌站示意圖如下：出 軌入 軌581742963987654321H1H3H2 火車(chē)車(chē)廂重排過(guò)程如下：出 軌入 軌 581H1H3H2963742出 軌入 軌 58H1H3H29674321出 軌入 軌5H1H3H2968754321出 軌入 軌H1H3H2987654321(a) 將369、247依次入緩沖軌(b) 將1移至出軌，234移至出軌(c) 將8入緩沖軌，5移至出軌(d) 將6789移至出軌火車(chē)車(chē)廂重排算法偽代碼如下：1. 分別對(duì)k個(gè)隊(duì)列初始化；2. 初始化下一個(gè)要輸

3、出的車(chē)廂編號(hào)nowOut = 1; 3. 依次取入軌中的每一個(gè)車(chē)廂的編號(hào)；3.1 如果入軌中的車(chē)廂編號(hào)等于nowOut，則 3.1.1 輸出該車(chē)廂； 3.1.2 nowOut+；3.2 否則，考察每一個(gè)緩沖軌隊(duì)列 for (j=1; j<=k; j+) 3.2.1 取隊(duì)列 j 的隊(duì)頭元素c； 3.2.2 如果c=nowOut，則 3.2.2.1 將隊(duì)列 j 的隊(duì)頭元素出隊(duì)并輸出； 3.2.2.2 nowOut+； 3.3 如果入軌和緩沖軌的隊(duì)頭元素沒(méi)有編號(hào)為nowOut的車(chē)廂，則 3.3.1 求小于入軌中第一個(gè)車(chē)廂編號(hào)的最大隊(duì)尾元素所在隊(duì)列編號(hào)j;3.3.2 如果 j 存在，則把入軌中的

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

5、點(diǎn)的存儲(chǔ)空間void EnQueue(T x); /將元素x入隊(duì)T DeQueue( ); /將隊(duì)頭元素出隊(duì)T GetFront( ); /取鏈隊(duì)列的隊(duì)頭元素T GetRear();bool Empty( ); /判斷鏈隊(duì)列是否為空QNode<T> *front, *rear; /隊(duì)頭和隊(duì)尾指針，分別指向頭結(jié)點(diǎn)和終端結(jié)點(diǎn);template <class T>LiQueue<T>:LiQueue( )QNode <T> *s;s=new QNode<T>s->next=NULL;front=rear=s;template <

6、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; /申請(qǐng)一個(gè)數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)ss->next=NULL;rear->next=s; /將結(jié)點(diǎn)s插入到隊(duì)尾rear=s;template <clas

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

8、ear!=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,th;public :Train();void ChongPai();Train:Train(

9、)cout<<"請(qǐng)輸入火車(chē)(貨運(yùn)列車(chē)）的車(chē)廂個(gè)數(shù)為："<<endl;cin>>n;cout<<"請(qǐng)輸入轉(zhuǎn)軌站的緩沖軌個(gè)數(shù)為："<<endl;cin>>k;void Train:ChongPai()int aMS;LiQueue<int>*b;b=new LiQueue<int>k+2;cout<<"請(qǐng)輸入車(chē)廂入軌編號(hào)次序："<<endl;for(int i=0;i<n;i+)cin>>ai;for(

10、i=n-1;i>=0;i-)bk.EnQueue(ai);cout<<"則進(jìn)行車(chē)廂重排過(guò)程如下:"<<endl;th=1;while(bk.Empty()int xx=bk.DeQueue();if(xx=th)cout<<th<<"號(hào)車(chē)廂直接移至出軌"<<endl;bk+1.EnQueue(th);th+;int j=0;while(bj.Empty()int x=bj.GetFront();if(x=th)cout<<x<<"號(hào)車(chē)廂從"<

11、;<j+1<<"號(hào)緩沖軌出軌"<<endl;bj.DeQueue();bk+1.EnQueue(x);j=0;th+;elsej+;continue;else int j=0,u=5;while(bj.Empty()&&j<k)if(xx<bj.GetRear()j+;else cout<<xx<<"號(hào)車(chē)廂移至"<<j+1<<"號(hào)緩沖軌"<<endl;bj.EnQueue(xx);u=1;break;if(u=5&am

12、p;&j<k)cout<<xx<<"號(hào)車(chē)廂移至"<<j+1<<"號(hào)緩沖軌"<<endl;bj.EnQueue(xx);if(j=k-1)cout<<"n緩沖軌不夠，重排車(chē)廂失敗n"return;cout<<"車(chē)廂依次出軌的編號(hào)為："while(bk+1.Empty()cout<<bk+1.DeQueue()<<" "cout<<endl;void main()Train a;a.ChongPai();五、 測(cè)試用例1.當(dāng)有9個(gè)火車(chē)車(chē)廂，3個(gè)緩沖軌道時(shí)，運(yùn)行結(jié)果如下：2. 當(dāng)有12個(gè)火車(chē)車(chē)廂，3個(gè)緩沖軌道時(shí)，運(yùn)行結(jié)果如下：3. 當(dāng)有12個(gè)火車(chē)車(chē)廂，5個(gè)緩沖軌道，運(yùn)行結(jié)果如下：4. 當(dāng)有12個(gè)火車(chē)車(chē)廂，7個(gè)緩沖軌道時(shí)，運(yùn)行結(jié)果如下：幾次測(cè)試都表明試驗(yàn)設(shè)計(jì)的正確性。六、 試驗(yàn)總結(jié)本次試驗(yàn)中，在解決火車(chē)車(chē)廂重排問(wèn)題中，結(jié)合了最近剛學(xué)的隊(duì)列的知識(shí)，并且運(yùn)用到之前C+語(yǔ)言，很好的解決了這一類(lèi)問(wèn)題。其中，每一個(gè)軌道緩沖區(qū)就形如一個(gè)隊(duì)列一樣，車(chē)廂先進(jìn)緩沖軌道的要先出來(lái)，所以把它看成一個(gè)隊(duì)列，運(yùn)