課件數(shù)據(jù)結(jié)構(gòu).車(chē)廂調(diào)度PPT

數(shù)據(jù)結(jié)構(gòu).車(chē)廂調(diào)度[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第1頁(yè)。假設(shè)停在鐵路調(diào)度口的車(chē)廂序列的編號(hào)依次1,2,3,…,n，設(shè)計(jì)一個(gè)程序，求出所有可能由此輸出的長(zhǎng)度為n的車(chē)廂序列。

問(wèn)題描述：[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第2頁(yè)。為使車(chē)廂能夠調(diào)度，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)。利用先進(jìn)后出的性質(zhì)，改變車(chē)廂的順序。

從而，問(wèn)題可以轉(zhuǎn)化為：1,2,3,…,n依次全部進(jìn)棧且全部出棧，求所有的出棧序列。…[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第3頁(yè)。問(wèn)題分析：從具體問(wèn)題入手：第一步：假如有1,2,3準(zhǔn)備進(jìn)棧，此時(shí)具體的過(guò)程如下第二步：對(duì)上述過(guò)程的進(jìn)一步分析，一個(gè)數(shù)進(jìn)棧以后，有兩種處理方式：要么下一個(gè)元素進(jìn)棧（如果有的話），要么立刻出棧；一個(gè)數(shù)出棧以后，要么繼續(xù)出棧（如果棧不為空），要么下一個(gè)元素進(jìn)棧（如果有的話）第三步：繼續(xù)分析，由此得出一個(gè)結(jié)論，在操作過(guò)程中的任何狀態(tài)下都有兩種可能的操作：“入”和“出”。每個(gè)狀態(tài)下處理問(wèn)題的方法都是相同的，這說(shuō)明問(wèn)題本身具有天然的遞歸特性，可以考慮用遞歸算法實(shí)現(xiàn)。[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第4頁(yè)。本程序的主要算法分析：調(diào)度函數(shù)的偽碼算法如下：voidScheduling(intpos,intpath[],inti){if(pos<n){一個(gè)數(shù)進(jìn)棧后,有兩種處理方式：要么下一個(gè)數(shù)的進(jìn)棧，要么立刻出棧}if(!IsEmpty()==true){一個(gè)數(shù)出棧后,有兩種處理方式：要么繼續(xù)出棧,要么下一個(gè)數(shù)的進(jìn)棧}if(pos==n&&IsEmpty()){一種可能輸出序列產(chǎn)生，輸出}}[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第5頁(yè)。具體的調(diào)度函數(shù)的程序代碼：voidSeqStack::Scheduling(intpos,intpath[],inti){ inttemp; if(pos<maxSize){ Push(pos+1); Scheduling(pos+1,path,i); Pop(); } if(IsEmpty()==false){ temp=Pop(); path[i++]=temp; Scheduling(pos,path,i); Push(temp); } if(pos==maxSize&&IsEmpty()==true){ count++; for(intj=0;j<i;j++) cout<<path[j]<<''; cout<<'\t'; }}[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第6頁(yè)。S(1,path,0)push(2)S(2,path,0)pop()t=path[0]=pop()S(1,path,1)push(t)S(2,path,0)停止t=path[0]=pop()S(1,path,1)push(t)S(1,path,1)停止t=path[0]=pop()S(1,path,2)push(t)S(1,path,1)push(2)S(2,path,1)pop()停止S(1,path,2)停止停止輸出path[i]:2,1S(2,path,1)停止停止輸出path[i]:1,2主函數(shù)調(diào)用Scheduling函數(shù)后后究竟怎么執(zhí)行的呢現(xiàn)考慮只有兩個(gè)車(chē)廂1,2？[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第7頁(yè)。122112111初始狀態(tài)：①：②：③：④：⑤：⑥：⑦：④：⑤：④：①：⑤：④：⑨：①：⑤：④：⑧：進(jìn)出棧情況：[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第8頁(yè)。謝謝！看收！[課件]數(shù)據(jù)結(jié)構(gòu)全文共10頁(yè)，當(dāng)前為第9頁(yè)。3進(jìn)3進(jìn)無(wú)3出1出無(wú)2出無(wú)2出3進(jìn)空3出無(wú)3進(jìn)無(wú)3出無(wú)3出1出3進(jìn)無(wú)1出2出無(wú)空空無(wú)3出無(wú)空無(wú)無(wú)空空無(wú)2進(jìn)2進(jìn)