車廂調(diào)度實習(xí)報告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計車廂調(diào)度胡海洪1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計車廂調(diào)度胡海洪310400642904計算機科學(xué)與技術(shù)（1）班2006年7月

2．3題車廂調(diào)度實習(xí)報告題目：編制一個將長度為n的車廂進行調(diào)度后的所有序列輸出的程序班級：04計算機科學(xué)與技術(shù)1班姓名：胡海洪學(xué)號：3104006429完成日期：06年7月一、需求分析1、用編號依次為1，2，3，……，n表示停在鐵路調(diào)度站入口處的車廂序列。2、用一個棧形象地表示為火車的調(diào)度站。3、利用棧先進后出的性質(zhì)，結(jié)合遞歸和回溯算法，實現(xiàn)編號1…n的車廂的所有可能的序列和每種序列的出入棧變化過程。本程序用C語言實現(xiàn)，已經(jīng)在TURBOC2.0環(huán)境下通過。二、概要設(shè)計1、設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對象：D={ai|ai∈CharSet，i=1，2，……，n，n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2，……，n}基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。Push(&S,e);初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S,e);初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。}ADTStack本程序包括三個模塊：初始化數(shù)據(jù)——輸入總數(shù)——初始化棧和序列顯示所有的序列——遞歸調(diào)用——輸出所有結(jié)果演示一種序列——輸入要演示的序列——每一步演示三、詳細設(shè)計1、為了使車廂能夠調(diào)度，需要定義一個棧，利用棧先進后出的性質(zhì)，改變車廂的順序；因為輸出的序列有很多種，而且序列的產(chǎn)生是用遞歸產(chǎn)生的，所以定義一個二維數(shù)組，用它保存所有的輸出序列，供演示時調(diào)用。structpathss{intpaths[MAXSIZE][MAXSIZE];intnumber;}AllPath;2、棧類型structSNode{intdata[MAXSIZE];inttop;}S;棧的基本操作：voidInitStack()/*棧的初始化*/{S.top=-1;}voidPush(intq)/*進棧*/{S.data[++S.top]=q;}intPop()/*出棧*/{inttemp;temp=S.data[S.top--];returntemp;}intStackEmpty()/*判斷棧是否為空*/{if(S.top==-1)return1;elsereturn0;}3、求所有序列的偽碼算法：voidAttemper(intpos,intpath[],intcur){if(pos<n){一個數(shù)進棧后,有兩種處理方式：要么立刻出棧,要么進行下一個數(shù)的進棧}if(棧不空){一個數(shù)出棧后,有兩種處理方式：要么繼續(xù)出棧,要么繼續(xù)下一個數(shù)的進棧}if(pos==n&&?？?{一種可能輸出序列產(chǎn)生，輸出；并將每種序列保存在二維數(shù)組里；}}4、演示一種序列的偽碼算法：演示時，采用的是向逆推的方法，因為我們已經(jīng)知道了一種輸出序列的結(jié)果和它的最初狀態(tài)，就可以利用棧將中間過程顯示出來；voidChooseDisplay(){intk,Output,Input=1;for(Output=0;Output<n;Output++){if(輸出序列中當(dāng)前的數(shù)據(jù)大于等于入口處的數(shù)據(jù)時){while(輸出序列中當(dāng)前的數(shù)據(jù)大于等于入口處的數(shù)據(jù)時){入口處的數(shù)據(jù)要一直壓棧}顯示每一步結(jié)果}else（序列中當(dāng)前的數(shù)據(jù)小于入口處的數(shù)據(jù)）{彈出棧頂,重新顯示結(jié)果}}}5、主函數(shù)和其他函數(shù)voidmain()/*主函數(shù)*/{功能選擇分別調(diào)用：1:InputNumber()2:DisplayAll()3:ChooseDisplay()}voidDisplayAll()/*顯示所有輸出序列*/{調(diào)用函數(shù)Attemper}voidPrint()/*一個棧打印操作*/{inti;for(i=S.top;i>=0;i--)printf("\t\t\t|%d|\n",S.data[i]);}voidDisplayOnly(intk,intOutput,intInput)/*顯示操作序列的狀態(tài)的變化過程*/{第一步：顯示輸出序列的狀態(tài)變化第二步：顯示棧的狀態(tài)變化第三步：顯示輸入序列的狀態(tài)變化}6、函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：InputNumber()DisplayAll()Attemper()ChooseDisplay()InputNumber()ExitInitStack()InputNumber()DisplayAll()Attemper()ChooseDisplay()InputNumber()ExitInitStack()DisplayOnly()InitStack()四、調(diào)試分析本程序的棧其實也是一個一維數(shù)組,然后用一個top作為指針,控制數(shù)組的長度。棧的基本操作較簡單明了。本程序有兩個核心算法，即求所有序列和演示每一序列的變化過程。整個程序運行期間實行靜態(tài)存儲管理。本程序在TURBOC2.0同VC++環(huán)境下均可通過。五、用戶手冊本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：Attemper.exe。2、運行程序后,顯示如下界面:六、測試結(jié)果（1）測試數(shù)據(jù)n=3；（也可以測試其他數(shù)據(jù)）（2）選擇功能“1”,回車，顯示如下：*******************1:輸入火車的長度N**2:輸出所有可能序列**3:演示一個序列變化**4:退出本程序*******************1請輸入火車車廂的長度N:（3）輸入車廂總數(shù)“3”,選擇功能“2”，按回車顯示如下：2所有可能的輸出序列如下:1:3212:2313:2134:1325:123*******************1:輸入火車的長度N**2:輸出所有可能序列**3:演示一個序列變化**4:退出本程序*******************（4）選擇功能“3”,回車顯示如下:3請輸入你想要查看序列狀態(tài)變化過程的序號:7．輸入要演示的序列號,如輸入“3”,再一直按回車，顯示如下:3請輸入你想要查看序列狀態(tài)變化過程的序號:3輸出序列棧輸入序列<----1<----2<----3|1|<----2<----3|2||1|<----3<----2|1|<----3<----2<----1<----3<----2<----1|3|<----2<----1<----3（5）輸入”4”,回車則退出程序七、附錄源程序文件名清單：Attemper.c//主程序Attemper.exe//可執(zhí)行文件Attemper.OBJ//目標源文件八、心得體會1、通過這次作業(yè)，我感到學(xué)到不少知識，首先對C語言有了一個比較完整的認識，以前學(xué)習(xí)C語言的知識很零碎、不系統(tǒng)，通過寫源程序使我對C語言的數(shù)據(jù)類型（特別構(gòu)造類型的數(shù)據(jù)）有了一個完整的認識，為今后進一步學(xué)習(xí)C++奠定了良好的基礎(chǔ)。2、加深了對《數(shù)據(jù)結(jié)構(gòu)》這門課程的學(xué)習(xí)和領(lǐng)會。以往只是知道這門課程對計算機專業(yè)很重要，但具體起來又不明白到底怎樣重要？通過設(shè)計，我才體會到?jīng)]有《數(shù)據(jù)結(jié)構(gòu)》的知識是無法寫程序的！由于本人掌握知識深度欠缺，只好采用一個二維數(shù)組和一個一維數(shù)組，這樣明顯增加了時間復(fù)雜性。3、實踐是檢驗真理的唯一手段！《數(shù)據(jù)結(jié)構(gòu)》中的許多