- 相關(guān)推薦
火車車廂重排問(wèn)題
實(shí)驗(yàn)二：火車車廂重排問(wèn)題
班級(jí)：2010級(jí)數(shù)學(xué)班 學(xué)號(hào):201008101127 姓名：裴志威
一.問(wèn)題描述：
一列貨運(yùn)列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個(gè)車站的編號(hào)分別為1~n,貨運(yùn)列車按照第n站至第1站
的順序經(jīng)過(guò)這些車站。車廂編號(hào)與他們的目的地一樣。為了便于從列車上卸掉相應(yīng)的車廂，必須重排車廂順序，使得各車廂
從前往后按編號(hào)1到n的次序排列。當(dāng)所有車廂按照這種次序排列時(shí)，在每個(gè)車站只需卸掉最后一個(gè)車廂即可。我們?cè)谝粋�(gè)
轉(zhuǎn)軌站里完成重拍的工作，在轉(zhuǎn)軌站有一個(gè)入軌，一個(gè)出軌和k個(gè)緩沖軌（位于入軌和出軌之間）。
二.基本要求：
（1）：設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示n個(gè)車廂，k個(gè)緩沖軌以及入軌和出軌，
（2）設(shè)計(jì)并實(shí)現(xiàn)車廂重排算法，
（3）分析算法的時(shí)間性能。
三.算法描述：
為了重排車廂，需從前往后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足要求的車廂，可以直接把它放
到出軌上。否則，則把它移動(dòng)到緩沖軌上，直到按輸出順序要求輪到它的時(shí)候才可以將他放到出軌上。緩沖軌是按照FILO
的方式使用的，因?yàn)檐噹倪M(jìn)出都是在緩沖軌的頂端進(jìn)行的。
在重排車廂過(guò)程中，僅允許以下活動(dòng)：
1、車廂可以從入軌的前部移動(dòng)到一個(gè)緩沖軌的頂部或者是出軌的左端
2、車廂可以從一個(gè)緩沖軌的頂部移動(dòng)到出軌的左端
在將車廂放入緩沖軌的過(guò)程中，應(yīng)該注意：有空的可以優(yōu)先放，沒(méi)空的緩沖軌時(shí)，要將新的車廂放在滿足以下條件的緩沖軌
中：在緩沖軌的頂部車廂編號(hào)比新車廂的編號(hào)大的所有緩沖軌中選擇頂部車廂編號(hào)最小的那個(gè)。
四.偽代碼：
1. 分別對(duì)k個(gè)隊(duì)列初始化；
2. 初始化下一個(gè)要輸出的車廂編號(hào)nowOut = 1;
3. 依次取入軌中的每一個(gè)車廂的編號(hào)；
3.1 如果入軌中的車廂編號(hào)等于nowOut，則
3.1.1 輸出該車廂；
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的車廂，則
3.3.1 求小于入軌中第一個(gè)車廂編號(hào)的最大隊(duì)尾元素所在隊(duì)列編號(hào)j;
3.3.2 如果 j 存在，則把入軌中的第一個(gè)車廂移至緩沖軌 j；
3.3.2 如果 j 不存在，但有多于一個(gè)空緩沖軌，則把入軌中的第一個(gè)車廂移至一個(gè)空緩沖軌；否則車廂無(wú)法重排，算法結(jié)束；
五.源程序代碼：
#include
#include
#define Max 20
typedef struct
int data[Max]; int front,rear;
}squeue;
void initqueue(squeue *&q)
{
}
void enqueue(squeue *&q,int e)
{
}
void dequeue(squeue *&q)
{
}
int gettop(squeue *&q)
{
}
int getrear(squeue *&q)
{
}
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->data[q->front+1]==nowout) { { } return q->data[q->rear]; return q->data[q->front+1]; q->front=(q->front+1)%Max; q->rear=(q->rear+1)%Max; q->data[q->rear]=e; q=(squeue *)malloc(sizeof(sq第一文庫(kù)網(wǎng)ueue)); q->front=q->rear=0;
} nowout++; dequeue(q); else if(gettop(w1)==nowout) { printf("%d號(hào)車廂出軌！\t",gettop(w1)); nowout++; dequeue(w1); } else if(gettop(w2)==nowout) { } else { int c=gettop(q); n1=getrear(w1); n2=getrear(w2); if(n1>n2) { if(c>n1) { } else { enqueue(w2,c); dequeue(q); enqueue(w1,c); dequeue(q); printf("%d號(hào)車廂出軌！\t",gettop(w2)); nowout++; dequeue(w2); } else { } if(c>n2) { enqueue(w2,c); dequeue(q);
}
else { enqueue(w1,c); dequeue(q); } } } }
int examenter(int a[],int k)
{
}
void main()
{
squeue *q,*w1,*w2; initqueue(q); initqueue(w1); initqueue(w2); int a[10],k; label: printf("要輸入幾個(gè)車廂？\n"); for(int i=1;i<=k;i++) { } if(a[i]!=i) { } return 0; break; scanf("%d",&k); if(k<=0) { } printf("請(qǐng)輸入正確的車廂號(hào)!\n"); printf("****************************************************"); printf("\n"); goto label;
} for(int i=1;i<=k;i++) { } int r=examenter(a,k); if(r==0) { } else if(r!=0) { } else { } printf("我也不知道錯(cuò)哪了？'"); printf("重排前的序列為\n"); for(i=1;i<=k;i++) { } printf("\n"); printf("排列后的車廂號(hào)為：\n"); reset(q,w1,w2,k); printf("%d\t",a[i]); printf("您的輸入車廂號(hào)有誤! 請(qǐng)輸入連續(xù)自然數(shù):\n"); goto label2; scanf("%d",&a[i]); enqueue(q,a[i]);
六.測(cè)試結(jié)果
1.輸入正確的序列后得到結(jié)果如圖：
2.如果輸入的車廂數(shù)有誤的時(shí)候（為負(fù)數(shù)或零）
六、總結(jié)
本次數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)主要是練習(xí)使用隊(duì)列的思想，我做的是火車重排問(wèn)題的實(shí)驗(yàn)，此實(shí)驗(yàn)在課本上有一些講解，也給出來(lái)主要函數(shù)TrainPermute()的主要編寫思路，減輕了自己的工作量，不過(guò)由于此程序的代碼比較復(fù)雜，在編譯調(diào)試過(guò)程中也很耗費(fèi)時(shí)間，通過(guò)設(shè)置斷點(diǎn)，分步調(diào)試，才使得程序沒(méi)有了bug。例如，由于程序用了較多的循環(huán)，包括多重循環(huán)，在剛剛寫出代碼的時(shí)候常常陷入死循環(huán)，而因?yàn)榇a冗長(zhǎng)，僅僅通過(guò)看代碼很難找出邏輯上的錯(cuò)誤。功夫不負(fù)有心人，最后終于用與非門的思想解決了這個(gè)死循環(huán)問(wèn)題，并簡(jiǎn)單優(yōu)化程序。
總的來(lái)說(shuō)，本程序由于使用了模板類結(jié)構(gòu)，擴(kuò)展性還算比較好。但是代碼部分有些冗長(zhǎng)，可讀性不算太好。如果要做下
一步工作的話，應(yīng)該是盡量精簡(jiǎn)代碼，使得程序更加具有實(shí)用性和可讀性
【火車車廂重排問(wèn)題】相關(guān)文章：
通過(guò)粒子重排序?qū)崿F(xiàn)量子安全直接通訊04-30
分子CH3NH=B:的結(jié)構(gòu)及重排反應(yīng)的理論研究05-01
紅霉素肟貝克曼重排反應(yīng)中的構(gòu)型異構(gòu)化04-29
應(yīng)用端粒區(qū)帶涂染探針檢測(cè)染色體微小結(jié)構(gòu)重排05-02
心身問(wèn)題的問(wèn)題式04-29
鈦硅分子篩催化氣相環(huán)己酮肟貝克曼重排反應(yīng)04-30