火車(chē)車(chē)廂重排問(wèn)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)二：火車(chē)車(chē)廂重排問(wèn)題 班級(jí)：2010級(jí)數(shù)學(xué)班 學(xué)號(hào):7 姓名：裴志威 一.問(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ē)廂編號(hào)與他們的目的地一樣。為了便于從列車(chē)上卸掉相應(yīng)的車(chē)廂，必須重排車(chē)廂順序，使得各車(chē)廂從前往后按編號(hào)1到n的次序排列。當(dāng)所有車(chē)廂按照這種次序排列時(shí)，在每個(gè)車(chē)站只需卸掉最后一個(gè)車(chē)廂即可。我們?cè)谝粋€(gè)轉(zhuǎn)軌站里完成重拍的工作，在轉(zhuǎn)軌站有一個(gè)入軌，一個(gè)出軌和k個(gè)緩沖軌（位于入軌和出軌之間）。二.基本要求：（1）：設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示n個(gè)車(chē)廂，k個(gè)緩沖軌以及入軌和出軌

2、，（2）設(shè)計(jì)并實(shí)現(xiàn)車(chē)廂重排算法，（3）分析算法的時(shí)間性能。三.算法描述：為了重排車(chē)廂，需從前往后依次檢查入軌上的所有車(chē)廂。如果正在檢查的車(chē)廂就是下一個(gè)滿足要求的車(chē)廂，可以直接把它放到出軌上。否則，則把它移動(dòng)到緩沖軌上，直到按輸出順序要求輪到它的時(shí)候才可以將他放到出軌上。緩沖軌是按照FILO的方式使用的，因?yàn)檐?chē)廂的進(jìn)出都是在緩沖軌的頂端進(jìn)行的。在重排車(chē)廂過(guò)程中，僅允許以下活動(dòng)：1、車(chē)廂可以從入軌的前部移動(dòng)到一個(gè)緩沖軌的頂部或者是出軌的左端2、車(chē)廂可以從一個(gè)緩沖軌的頂部移動(dòng)到出軌的左端在將車(chē)廂放入緩沖軌的過(guò)程中，應(yīng)該注意：有空的可以優(yōu)先放，沒(méi)空的緩沖軌時(shí)，要將新的車(chē)廂放在滿足以下條件的緩沖軌中：在

3、緩沖軌的頂部車(chē)廂編號(hào)比新車(chē)廂的編號(hào)大的所有緩沖軌中選擇頂部車(chē)廂編號(hào)最小的那個(gè)。四.偽代碼：1. 分別對(duì)k個(gè)隊(duì)列初始化；2. 初始化下一個(gè)要輸出的車(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)

4、有編號(hào)為nowOut的車(chē)廂，則 3.3.1 求小于入軌中第一個(gè)車(chē)廂編號(hào)的最大隊(duì)尾元素所在隊(duì)列編號(hào)j;3.3.2 如果 j 存在，則把入軌中的第一個(gè)車(chē)廂移至緩沖軌 j；3.3.2 如果 j 不存在，但有多于一個(gè)空緩沖軌，則把入軌中的第一個(gè)車(chē)廂移至一個(gè)空緩沖軌；否則車(chē)廂無(wú)法重排，算法結(jié)束；五.源程序代碼：#include<stdio.h>#include<stdlib.h>#define Max 20typedef structint dataMax;int front,rear;squeue;void initqueue(squeue *&q)q=(squeue

5、*)malloc(sizeof(squeue);q->front=q->rear=0;void enqueue(squeue *&q,int e)q->rear=(q->rear+1)%Max;q->dataq->rear=e;void dequeue(squeue *&q)q->front=(q->front+1)%Max;int gettop(squeue *&q)return q->dataq->front+1;int getrear(squeue *&q)return q->dataq-&

6、gt;rear;void reset(squeue *&q,squeue *&w1,squeue *&w2,int k)int nowout=1;int n1=0,n2=0;for(int i=0;i<50;i+)if(q->dataq->front+1=nowout)printf("%d號(hào)車(chē)廂出軌！t",q->dataq->front+1);nowout+;dequeue(q);else if(gettop(w1)=nowout)printf("%d號(hào)車(chē)廂出軌！t",gettop(w1);nowou

7、t+;dequeue(w1);else if(gettop(w2)=nowout)printf("%d號(hào)車(chē)廂出軌！t",gettop(w2);nowout+;dequeue(w2);elseint c=gettop(q);n1=getrear(w1);n2=getrear(w2);if(n1>n2)if(c>n1)enqueue(w1,c);dequeue(q);elseenqueue(w2,c);dequeue(q);elseif(c>n2)enqueue(w2,c);dequeue(q);elseenqueue(w1,c);dequeue(q);int

8、 examenter(int a,int k)for(int i=1;i<=k;i+)if(ai!=i)return 0;break;void main()squeue *q,*w1,*w2;initqueue(q);initqueue(w1);initqueue(w2);int a10,k;label:printf("要輸入幾個(gè)車(chē)廂？n");scanf("%d",&k);if(k<=0)printf("請(qǐng)輸入正確的車(chē)廂號(hào)!n");printf("*");printf("n"

9、);goto label;label2:printf("輸入重排前的序列n");for(int i=1;i<=k;i+)scanf("%d",&ai);enqueue(q,ai);int r=examenter(a,k);if(r=0)printf("您的輸入車(chē)廂號(hào)有誤! 請(qǐng)輸入連續(xù)自然數(shù):n");goto label2;else if(r!=0)printf("重排前的序列為n");for(i=1;i<=k;i+)printf("%dt",ai);printf("

10、n");printf("排列后的車(chē)廂號(hào)為：n");reset(q,w1,w2,k);elseprintf("我也不知道錯(cuò)哪了？'");六.測(cè)試結(jié)果1.輸入正確的序列后得到結(jié)果如圖：2.如果輸入的車(chē)廂數(shù)有誤的時(shí)候（為負(fù)數(shù)或零）六、總結(jié)       本次數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)主要是練習(xí)使用隊(duì)列的思想，我做的是火車(chē)重排問(wèn)題的實(shí)驗(yàn)，此實(shí)驗(yàn)在課本上有一些講解，也給出來(lái)主要函數(shù)TrainPermute()的主要編寫(xiě)思路，減輕了自己的工作量，不過(guò)由于此程序的代碼比較復(fù)雜，在編譯調(diào)試過(guò)程中也很耗費(fèi)時(shí)間，通過(guò)設(shè)置斷點(diǎn)，分步調(diào)試，才使得程序沒(méi)有了bug。例如，由于程序用了較多的循環(huán)，包括多重循環(huán)，在剛剛寫(xiě)出代碼的時(shí)候常常陷入死循環(huán)，而因?yàn)榇a冗長(zhǎng)，僅僅通過(guò)看代碼很難找出邏輯上的錯(cuò)誤。功夫不負(fù)有