數(shù)據(jù)結構車廂調度課件

1、數(shù)據(jù)結構數(shù)據(jù)結構.車廂車廂 調度調度 假設停在鐵路調度口的車廂序列的編號依次 1,2,3,n， 設計一個程序，求出所有可能由此輸出的長度為 n的車 廂序列。 問題 描述： 為使車廂能夠調度，常把站臺設計成棧式結構。 利用先進后出的性質，改變車廂的順序。 從而，問題可以轉化為： 1,2,3,n依次全部 進棧且全部出棧，求所有的出棧序列。 問題 分析： 從具體問題入手： 第一步：假如有1,2,3準備進棧，此時具體的過程如下 第二步：對上述過程的進一步分析，一個數(shù)進棧以后，有 兩種處理方式：要么下一個元素進棧（如果有的話），要 么立刻出棧；一個數(shù)出棧以后，要么繼續(xù)出棧（如果棧不 為空），要么下一個元

2、素進棧（如果有的話） 第三步：繼續(xù)分析，由此得出一個結論，在操作過程中的 任何狀態(tài)下都有兩種可能的操作：“入”和“出”。每個 狀態(tài)下處理問題的方法都是相同的，這說明問題本身具有 天然的遞歸特性，可以考慮用遞歸算法實現(xiàn)。 本程序的主要算法分析： 調度函數(shù)的偽碼算法如下： void Scheduling(int pos, int path,int i) if(posn) 一個數(shù)進棧后,有兩種處理方式：要么下一個數(shù)的進棧， 要么立刻出棧 if(!IsEmpty()=true) 一個數(shù)出棧后,有兩種處理方式：要么繼續(xù)出棧 ,要么下一 個數(shù)的進棧 if(pos=n if (posmaxSize) Pus

3、h(pos+1); Scheduling(pos+1,path,i); Pop(); if (IsEmpty()=false) temp=Pop(); pathi+=temp; Scheduling(pos,path,i); Push(temp); if (pos=maxSize for (int j=0;ji;j+) coutpathj ; coutt; S(1,path,0) push(2) S(2,path,0) pop() t=path0=p op() S(1,path,1) push(t) S(2,path,0) 停止 t=path0=p op() S(1,path,1) push(

4、t) S(1,path,1) 停止 t=path0=p op() S(1,path,2) push(t) S(1,path,1) push(2) S(2,path,1) pop() 停止 S(1,path,2) 停止 停止 輸出 pathi:2,1 S(2,path,1) 停止 停止 輸出 pathi:1,2 主函數(shù)調用Scheduling函數(shù)后后究竟怎么執(zhí)行的呢 現(xiàn)考慮只有兩個車廂 1,2 ？ 1 2 2 1 1 2 1 1 1 初始狀態(tài)： ： ： ： ： ： ： ： ： 進出棧情況： 謝謝 謝謝 ！看收 ！ 3進 3進 無 3出 1出 無 2出 無 2出 3進 空 3出 無 3進 無 3出 無 3出 1出 3進 無 1出 2出 無 空 空 無 3出 無 空 無 無 空 空 無 2進 2進 1出 1進 空 2出 輸