數(shù)據(jù)結(jié)構(gòu)課程設(shè)計60575

1、工程技術(shù)師學院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目：車廂調(diào)度程序?qū)I(yè):軟件工程班級：R1142學生：_學號：02_指導教師： 王銳高嵐2012 年 12 月信息工程學院目錄第一章 問題描述 31. 題目 32. 需求分析 第二章 設(shè)計思路 41. 菜單顯示 42. 調(diào)度過程 3. 序列輸出過程 第三章 數(shù)據(jù)結(jié)構(gòu)定義 5第四章 系統(tǒng)功能模塊設(shè)計 9第五章 運行與調(diào)試 11總結(jié) 14附錄 15參考文獻 . 第一章 問題描述1. 題目假設(shè)停在鐵路調(diào)度站入口處的車廂序列的編號一次為1,2,3 ,n。設(shè)計一個程序，求出所有可能由此輸出的長度 為 n 的車廂序列。本設(shè)計程序用于實現(xiàn)有限個車廂調(diào)度排序，用 戶可根據(jù)

2、自身情況自行輸入車廂調(diào)度的長度，本程序會根據(jù)用戶 所輸入的長度自動進行排序。本程序增加選擇的功能，可根據(jù)不 同需要進行步驟的選擇，并顯示出所有可能的排序方法。2. 需求分析( 1 ) 提供的棧的順序存儲結(jié)構(gòu) SqStack 之上實現(xiàn)棧的基本操 作，即實現(xiàn)棧類型。( 2 ) 程序?qū)θ魏螚５娜魏未嫒?即更改、讀取和狀態(tài)判別等 操作)必須借助于基本操作執(zhí)行。( 3 ) 用戶可以自己輸入調(diào)度的大小 , 然后由程序自動生成 結(jié)果.第二章 設(shè)計思路1. 菜單顯示本系統(tǒng)主要的菜單顯示有兩個界面，一個是對本系統(tǒng)主要簡介的 界面，其中包括數(shù)據(jù)結(jié)構(gòu)課程設(shè)計、鐵路調(diào)度站模擬、 11 級軟件 工程。另一個是主要的操作

3、界面， 主要包括 1 請輸入火車長度、 2 輸出所有可能序列、 3 退出本程序。2. 調(diào)度過程本系統(tǒng)主要是利用棧進行定義和設(shè)計， 主要依賴于棧的基本操作， 首先判斷站是否為空，如果非空則進行進棧操作，否則返回。所 以每一個數(shù)根據(jù)以上出入棧的選擇， 將產(chǎn)生所有可能的車廂序列。 本設(shè)計中還用到了遞歸的思想：數(shù)據(jù)入棧后，對數(shù)據(jù)有兩種處理 方法，進?；蛘呦乱粋€數(shù)的進棧，一個數(shù)的出棧后也有兩種處理 方法，要么出棧，要么下一個數(shù)的進棧。3. 序列輸出過程根據(jù)棧的特性輸出長度為N的所有車廂序列，按ENTER各顯示所 有的序列的顯示。第三章 數(shù)據(jù)結(jié)構(gòu)定義1. 設(shè)定棧的抽象數(shù)據(jù)類型定義 :ADT Stack 數(shù)

4、據(jù)對象：D=ai|ai ADT MazeType , i = 0,1,2 n , n > 0數(shù) 據(jù) 關(guān) 系 ：R1= <ai-1,ai>| ai-1,ai D,i=2,n 基本操作 ：InitStack(SqStack &s)操作結(jié)果 ： 構(gòu)造一個空棧GetTop(SqStack s,SElemType &e)初始條件 ： 棧 s 以存在操作結(jié)果 ： 獲取棧頂元素Push(SqStack &s,SElemType &e) 初始條件 ： 棧 s 以存在 操作結(jié)果 ： 在棧頂插入新元素Pop(SqStack &s,SElemType &am

5、p;e)初始條件 ： 棧 s 以存在 操作結(jié)果 ： 刪除棧頂元素 , 并刪除 e 值StackEmpty(SqStack s) 初始條件 ： 棧 s 以存在 操作結(jié)果 ： 判斷棧是否為空ClearStack(SqStack &s) 初始條件 ： 棧 s 以存在 操作結(jié)果 ： 將棧置為空棧 ADT SqStack;2. 設(shè)定車廂調(diào)度的抽象數(shù)據(jù)類型ADT MazeType數(shù)據(jù)對象 ： D=ai,j|ai,j ', #'、*'，0<=i<=m+1, 0<=j<=n+1,m,n<=10數(shù)據(jù)關(guān)系 : R=M,NM=<ai-1,j,ai,

6、j>|ai-1,j,ai,jD,i=1, ,m+1,j=0, ,n+1N=<ai-1,j,ai,j>|ai-1,j,ai,jD,i=1, ,m+1,j=0,n+1基本操作 :void process(int pos,int path,int curp)/ 當前處理位置 pos 的元素定一兩個變量if(pos<n)/ 編號進棧遞歸push(pos+1);/ 當前元素進棧后下一個元素繼 續(xù)進棧process(pos+1,path,curp); /處理下一個元素，返回表明下一個元素進棧的情況處理完了 pop(); / 下一個元素處理完后， pop 掉， 準備處理直接出棧if(

7、!Emptys()/ 遞歸處理出棧m=pop();pathcurp=m; / 數(shù)組存放出棧元素 curp+;process(pos,path,curp);/出 棧 后 處理下一個素繼續(xù)進棧push(m);if(pos=n&&Emptys()/ 輸出一種可能的方 案for(i=0;i<curp;i+)printf("%2d",pathi);printf("n"); 本系統(tǒng)主要是考慮對棧的使用，循環(huán)隊列和雙向鏈表的運用 頭文件設(shè)計（部分） 本部分是講述棧的相關(guān)操作 ：#include"stdlib.h"#includ

8、e <windows.h>#include"stdio.h"#include <conio.h>#define MaxLen 100struct Stack_nodeint dataMaxLen;int top;s; / 定義一個棧指針int n;/ 定義輸入序列總個數(shù)/ 棧的基本操作 void Initstack()s.top=-1;void push(int q)/ 元素 n 進棧s.top+;s.datas.top=q;int pop()/ 出棧int temp;temp=s.datas.top;s.top-;return temp;int E

9、mptys()/ 判斷?？読f(s.top=-1)return 1;elsereturn 0; 實現(xiàn)文件(部分) 本部分是主控函數(shù)，函數(shù)的調(diào)用以及菜單的選擇： main.cpp 主函數(shù)void main()int pathMaxLen;int m;char ch;printf(" nnn n");printf(" | n");printf(" | 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 |n");printf(" | |n");printf(" | 鐵路調(diào)度站模擬 |n");printf(" | |n&qu

10、ot;);printf(" | 11 級軟件工程 |n"); printf(" | n");printf(" n");printf(" 按任意鍵繼續(xù) n"); if(ch=getch();停頓do / system("cls"); /printf("nnn*n");printf(" * 1:請輸入火車的長度 : *n");printf(" * *n");printf(" * 2:輸出所有可能序列 : *n");pri

11、ntf(" * *n");printf(" * 3:退出本程序 : *n");printf("I *n");printf(" 請你根據(jù)需要選擇序號n");scanf("%d",&m);if(m=1)printf(" 請輸入車廂長度 :n"); scanf("%d",&n);printf(" 車廂長度已輸入 !n"); getchar();/ 停止 getchar(); if(m=2)Initstack(); push(1

12、);printf(" 所有輸出序列 :n");process(1,path,0); /從 1 開始，遞歸處理所有元素getchar();/ 停止 getchar(); if(m=3) printf(" 歡迎退出 !n"); printf("n");if(m!=1&&m!=2&&m!=3)printf("n 輸入有誤 ! 請重新輸入 !"); getchar();/ 停止 getchar(); while(m!=3);第四章 系統(tǒng)功能模塊設(shè)計1) 主程序模塊 : int main()主

13、菜單函數(shù)，實現(xiàn)時間循環(huán).return 0;/主函數(shù)2）棧模塊-實現(xiàn)棧抽象數(shù)據(jù)類型3）遞歸模塊-實現(xiàn)調(diào)度迷宮抽象數(shù)據(jù)類型4）選擇生成模塊-用戶自定義菜單的生成5）調(diào)度模塊-實現(xiàn)車站的模擬各模塊之間的調(diào)用如下：主程序模塊第五章運行與調(diào)試1. 本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為Program min g.exe.2. 進入演示程序后，即顯示文本方式的用戶界面：進入”建立自定義調(diào)度系統(tǒng)”命令后,根據(jù)提示輸入你需要選擇的序號，回車后即可得到”調(diào)度建立完成”的提示信息。2數(shù)據(jù)不合要求則會提示:1.進入“試測模擬調(diào)度”命令后,用戶只需根據(jù)要求一步步的輸入,按Enter鍵后.完成后,輸出可能的結(jié)WW

14、WH 1X X* 證* 3;詒麗,艾茨睪苗舉転丁丁" 皿山削有町魄丐列=* 退豈主璽邑7匸山 初對艮據(jù)喬蠶 血癢廳耳pri有軸1岀 序勺»1 =-1址 1耳 4蠱 1323： SSi 理2 4 X工丁哼 1址.1fl. 4壬14 a5E 1N 41_4330 址X 32 <X 2弓 31址2 孕* “請輸入火車的長度二*玄!輸出所有可能序列=-» «*董退出本程序:*KKHiMXXXKWMilOiEHXXKMMiJfltKlltjMK j青你根據(jù)需要選擇序號 在迎退岀甲Piess 承ny key to continue根據(jù)提示輸入* 1：諳輸入火車

15、的長度二* 2：輸出所有可能序列：*K M薔其退出本程序：*屛*»<>« k mtn natJii請你根據(jù)需要選擇序號輸入第二組測試數(shù)據(jù)：3所有輸出序列:9 2丄2 3 12 1313 212 3總結(jié)1. 做本次課設(shè) , 剛開始寫的代碼中雖然用到了遞歸去求解函數(shù)， 但是不能很好的輸完整結(jié)果， 但是棧的相關(guān)操作是正確的 , 后來發(fā) 現(xiàn)是由于調(diào)度遞歸算法中元素出棧后沒有繼續(xù)讓其進棧。經(jīng)改后 恢復正常。2. 在設(shè)計調(diào)度初始化函數(shù)的時候 , 參數(shù)的傳遞出現(xiàn)錯誤 , 主要是對 指針和引用的理解出現(xiàn)混淆 , 通過查閱相關(guān)資料 , 弄清楚了兩者 之間的區(qū)別 , 指針是用于指向

16、一個變量的地址 , 而引用只是對一個 已存在變量的一個重命名 .3. 用 printf 函數(shù)輸出標志信息跟蹤函數(shù)調(diào)用 , 收到了顯著的效果 大大提高了調(diào)試效率 , 有利于以后的代碼調(diào)試 .4在實現(xiàn)調(diào)度功能時發(fā)現(xiàn) , 每次調(diào)用 system("cls") 函數(shù)時都進 行清屏操作 , 屏幕只出現(xiàn)當前的操作目標 , 一目了然。用戶進入系 統(tǒng)只需按要求進行，操作時簡潔清晰 . 代碼中的主要算法 :/ 輸出 一種可 for(i=0;i<curp;i+) 的時間復雜度為 O( n ).5. 經(jīng)驗體會 : 參考書本的代碼進行改進，使用模塊化操作易于代 碼的調(diào)試和修改 , 而且易于閱

17、讀 . 在設(shè)計實現(xiàn)過程中雖然遇到了很 多問題 , 但是在解決這些問題的過程中 , 鞏固和加深了我們對已學 知識的理解 , 對團隊合作有了一個比較基礎(chǔ)的認識 , 為以后的工作 實踐打下了基礎(chǔ)，同時也增加了我們對這門課的認識 .附錄#include"stdlib.h" #include"stdio.h" #include <conio.h> #include"windows.h" #define MaxLen 100 struct snodeint dataMaxLen;int top;s; /定義一個棧指針int n;/定義

18、輸入序列總個數(shù)void Initstack()s.top=-1;void push(int q)/ 元素 n 進棧s.top+;s.datas.top=q;int pop()/ 出棧int temp; temp=s.datas.top;s.top-;return temp;int Emptys()/ 判斷?？読f(s.top=-1)return 1;elsereturn 0;/*每次調(diào)用求值階段包含兩重遞歸，只有全部返回，才表示本 pos 處理完，可以對上一個元素求值，process 就是找出當前元素進棧后所有可能的操作，即在當前元 素進棧后各種情況下， 包括不出棧，立即出棧，出棧后繼續(xù)出棧情

19、況 (出棧遞歸 )下，繼 續(xù)處理下一個元素 (入棧遞歸 )*/void process(int pos,int path,int curp)/ 當前處理 位置 pos 的元素int m,i;if(pos<n)/ 編號進棧遞歸push(pos+1);/ 當前元素進棧后下一個元素繼續(xù)進棧 process(pos+1,path,curp); / 處理下一個元素，返回表明 下一個元素進棧的情況處理完了 , 這里用遞歸將 2,3,4n 壓入棧pop(); / 下一個元素處理完后， pop 掉，準備處理直接 出棧if(!Emptys()/ 遞歸處理出棧 m=pop();pathcurp=m; / 數(shù)

20、組存放出棧元素 curp+;process(pos,path,curp);/ 出棧后處理下一個素繼續(xù) 進棧 , 用遞歸將 n,4,3,2,1 壓入棧push(m);/ 遞歸完后又按原順序?qū)?1,2,3,4n 壓入棧if(pos=n&&Emptys()/ 輸出一種可能的方案for(i=0;i<curp;i+)printf("%2d",pathi); printf("n");void main()int pathMaxLen;int m;char ch;printf(" nnn n");printf(" |

21、 n");printf(" | 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 |n");printf(" | |n");printf(" | 鐵路調(diào)度站模擬 |n"); printf(" | |n");printf(" | 11級軟件工程 |n");printf(" | n");printf(" n");printf(" 按任意鍵繼續(xù) n"); if(ch=getch();do system("cls");/ 停頓printf("nnn *n");printf(" * 1:請輸入火車的長度: *n");printf(" * *n&quo