南京信息工程大學(xué)本科課程設(shè)計報告

1、 成績： _ 課程設(shè)計（數(shù)據(jù)結(jié)構(gòu)）院、系 計算機(jī)與軟件學(xué)院 專業(yè) 軟件工程 姓 名 學(xué)號 指導(dǎo)教師 二零一五 年 十二 月 二十五 日南京信息工程大學(xué)課程設(shè)計車廂調(diào)度問題摘要：車廂調(diào)度問題要求通過對車廂序列的調(diào)整，輸出所有可能的車廂順序。本問題需要設(shè)計一個棧來模擬調(diào)度站，利用遞歸的方法輸出所有可能，利用數(shù)組儲存信息，入棧和出棧模擬了車廂進(jìn)站和出站的過程。主要問題就是設(shè)計函數(shù)來模擬進(jìn)站出站的過程。關(guān)鍵詞：模擬，遞歸，棧，車廂 1、 題目分析1.1、問題描述：假設(shè)停在鐵路調(diào)度站入口處的車廂序列的編號依次為1，2，3，4。設(shè)計程序求所有可能由此輸出的長度為4的車廂序列1.2、解決思路：車廂只能實(shí)現(xiàn)進(jìn)

2、站和出站，所以需要用到棧的方法來模擬車廂進(jìn)站出站，通過遞歸求出所有可能。2、 程序結(jié)構(gòu)整個程序包括定義棧和，初始化棧，入棧，出棧，判斷棧是否為空，以及遞歸模擬車站五個函數(shù)2.1棧的基礎(chǔ)知識 定義棧； void Initstack() /初始化棧；s.top = -1; void push(int e) /進(jìn)棧；將e入棧； int pop() /出棧； 返回棧頂元素并刪除； int Emptys() /判斷棧是否為空； if s.top=-1 return yes;else return no; 2.2、核心算法內(nèi)容void simulation（int begin,int path,int e

3、nd)begin初始值為0，利用begin判斷是否所有元素都已經(jīng)入棧入棧遞歸：if(beginn) push(begin+1); simulation(begin+1,path,end); pop(); 此處采用遞歸，所有數(shù)據(jù)都經(jīng)歷入棧；判斷棧是否為空，若不為空則準(zhǔn)備出棧處理；if(!Emptys() m=pop(); pathend=m; end+; simulation(begin,path,end);/出棧后處理下一個元素 push(m); 輸出一種可能；2.3、主函數(shù)中調(diào)用simulation函數(shù)；3、算法分析模仿車廂進(jìn)出站的規(guī)則，當(dāng)一個數(shù)進(jìn)棧之后會有兩種結(jié)果，要么立刻出棧，要么下一個

4、數(shù)進(jìn)棧，所以利用一個遞歸實(shí)現(xiàn)這個效果，當(dāng)這個數(shù)出棧之后也有兩種結(jié)果，要么棧中下一個數(shù)繼續(xù)出棧，要么另外一個數(shù)入棧，所以出棧段也有遞歸，實(shí)現(xiàn)這個效果。直到?？詹⑶宜性囟冀?jīng)歷入棧，輸出一種可能性，兩重遞歸可以把所有可能性都輸出，程序運(yùn)行結(jié)束。 4、運(yùn)行界面5、設(shè)計體會剛開始面對題目的時候我簡單的以為只是對4進(jìn)行全排列，所以我設(shè)計程序?qū)崿F(xiàn)4的全排列。后來發(fā)現(xiàn)了其中的主要問題和難點(diǎn)?；疖嚨能噹豢梢噪S意調(diào)動，只能通過進(jìn)出車站來調(diào)整順序，這就和棧是同樣的思路，所以我又重新設(shè)計程序，利用棧來模擬車站，因?yàn)橐敵鏊锌赡?，所以我想到用遞歸來實(shí)現(xiàn)，經(jīng)過設(shè)計，調(diào)試，修改，最終成功運(yùn)行并且得到結(jié)果。6、編譯環(huán)境 Microsoft Visual C+ 6.0；參考文獻(xiàn)： 1 嚴(yán)