數據結構課程設計車廂調度胡海洪1數據結構課程設計車廂調度胡海洪310400642904計算機科學與技術（1）班2006年7月

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