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