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