C語(yǔ)言版數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)48020

1、 . . . 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)資 料 袋計(jì)算機(jī)與通信 學(xué)院（系、部）20092010學(xué)年第二學(xué)期 課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)指導(dǎo)教師職稱(chēng) 博士學(xué)生專(zhuān)業(yè)班級(jí)通信工程學(xué)號(hào)題 目編制車(chē)廂調(diào)度的程序成 績(jī)起止日期2010年6月28日2010年7月10日目 錄 清 單序號(hào)材 料 名 稱(chēng)資料數(shù)量備 注1課程設(shè)計(jì)任務(wù)書(shū)12課程設(shè)計(jì)說(shuō)明書(shū)13課程設(shè)計(jì)圖紙1456課程設(shè)計(jì)任務(wù)書(shū)2009 2010 學(xué)年第 二 學(xué)期計(jì)算機(jī)與通信學(xué)院（系、部）通信工程專(zhuān)業(yè)092班級(jí)課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)題目：編制一個(gè)車(chē)廂調(diào)度的程序完成期限：自2010年6月28日至2010年7 月10 日共 一周容與任務(wù)一、設(shè)計(jì)的主要技術(shù)參數(shù)使用棧機(jī)制模擬迷

2、宮的尋路過(guò)程, 圖的DFS 自動(dòng)生成隨機(jī)迷宮地圖。二、設(shè)計(jì)任務(wù)使用C語(yǔ)言實(shí)現(xiàn)各個(gè)模塊的功能。三、設(shè)計(jì)工作量王燦陽(yáng)負(fù)責(zé)對(duì)棧的基本操作，我實(shí)現(xiàn)車(chē)廂的調(diào)度的進(jìn)和出，以與狀態(tài)的變化。進(jìn)度安排起止日期工作容2010-6-28設(shè)計(jì)本程序思路2010-6-30實(shí)現(xiàn)子程序模塊函數(shù)2010-7-6將子程序和主程序構(gòu)建成完整的C源程序，并且進(jìn)行相關(guān)編譯調(diào)試2010-7-7數(shù)據(jù)測(cè)試、形成文檔指導(dǎo)教師（簽字）：年 月 日系（教研室）主任（簽字）：年 月 日XVIII / 18數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說(shuō)明書(shū)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)編制一個(gè)車(chē)廂調(diào)度的程序起止日期： 2010年6月28日 至 2010年7月10日學(xué)生班級(jí)通信092班學(xué)號(hào)成績(jī)指

3、導(dǎo)教師(簽字)計(jì)算機(jī)與通信學(xué)院（部）年 月 日工業(yè)大學(xué)課程設(shè)計(jì)情況分析表課程設(shè)計(jì)名稱(chēng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)周數(shù)17周學(xué)院（部）計(jì)算機(jī)與通信學(xué)院系（教研室）通信工程系指導(dǎo)教師文志誠(chéng)學(xué)生專(zhuān)業(yè)、班級(jí)通信工程0901選題車(chē)廂調(diào)度成績(jī)分布優(yōu)良中與格不與格學(xué)生數(shù)百分比學(xué)生課程設(shè)計(jì)存在的主要問(wèn)題改進(jìn)措施與建議指導(dǎo)教師（簽字）：年 月 日系（教研室）主任（簽字）：年 月 日備注：本表在課程設(shè)計(jì)完成后由指導(dǎo)教師填寫(xiě)，與課程設(shè)計(jì)資料一起存檔。目錄1. 題目 VI2.概要設(shè)計(jì) VII3. 功能函數(shù)設(shè)計(jì) XI4. 調(diào)試分析XIX5. 用戶(hù)手冊(cè) XXI6. 測(cè)試結(jié)果XIV7. 附錄 完整的程序清單 XV一、題目:編制一個(gè)車(chē)廂調(diào)度

4、的程序.擴(kuò)展:增加清屏函數(shù)；;增選擇的功能;可顯示所有的運(yùn)行結(jié)果.需求分析( 1 )在教材書(shū)3.1.2節(jié)中提供的棧的順序存儲(chǔ)結(jié)構(gòu)SqStack之上實(shí)現(xiàn)棧的基本操作，即實(shí)現(xiàn)棧類(lèi)型。( 2 )程序?qū)θ魏螚５娜魏未嫒。锤?、讀取和狀態(tài)判別等操作）必須借助于基本操作執(zhí)行。( 3 ) 用戶(hù)可以自己輸入調(diào)度的大小 , 然后由程序自動(dòng)生成結(jié)果.二、概要設(shè)計(jì)1. 設(shè)定棧的抽象數(shù)據(jù)類(lèi)型定義 :ADT Stack 數(shù)據(jù)對(duì)象 : D=ai|aiADT MazeType , i = 0,1,2n , n0數(shù)據(jù)關(guān)系 : R1= <ai-1,ai> | ai-1,ai D,i=2,n 基本操作 :InitS

5、tack(SqStack &s)操作結(jié)果 : 構(gòu)造一個(gè)空棧GetTop(SqStack s,SElemType &e)初始條件 : 棧 s 以存在操作結(jié)果 : 獲取棧頂元素Push(SqStack &s,SElemType &e)初始條件 : 棧 s 以存在操作結(jié)果 : 在棧頂插入新元素Pop(SqStack &s,SElemType &e)初始條件 : 棧 s 以存在操作結(jié)果 : 刪除棧頂元素,并刪除e值StackEmpty(SqStack s)初始條件 : 棧 s 以存在操作結(jié)果 : 判斷棧是否為空ClearStack(SqStack &am

6、p;s)初始條件 : 棧 s 以存在操作結(jié)果 : 將棧置為空棧 ADT SqStack;2. 設(shè)定車(chē)廂調(diào)度的抽象數(shù)據(jù)類(lèi)型ADT MazeType數(shù)據(jù)對(duì)象 : D=ai,j|ai,j,#、*，0<=i<=m+1, 0<=j<=n+1,m,n<=10數(shù)據(jù)關(guān)系 : R=M,NM=<a i-1,j,ai,j>|ai-1,j,ai,jD,i=1,m+1,j=0,n+1N=<a i-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)/當(dāng)前

7、處理位置pos的元素 定一兩個(gè)變量 if(pos<n)/編號(hào)進(jìn)棧遞歸 push(pos+1);/當(dāng)前元素進(jìn)棧后下一個(gè)元素繼續(xù)進(jìn)棧 process(pos+1,path,curp); /處理下一個(gè)元素，返回表明下一個(gè)元素進(jìn)棧的情況處理完了 pop(); /下一個(gè)元素處理完后，pop 掉，準(zhǔn)備處理直接出棧 if(!Emptys()/遞歸處理出棧 m=pop(); pathcurp=m; /數(shù)組存放出棧元素 curp+; process(pos,path,curp);/出棧后處理下一個(gè)素繼續(xù)進(jìn)棧 push(m); if(pos=n&&Emptys()/輸出一種可能的方案 for

8、(i=0;i<curp;i+) printf("%2d",pathi); printf("n"); 3.本程序包含6個(gè)模塊1) 主程序模塊:int main()主菜單函數(shù), 實(shí)現(xiàn)時(shí)間循環(huán).return 0;/主函數(shù)2) 棧模塊-實(shí)現(xiàn)棧抽象數(shù)據(jù)類(lèi)型3) 遞歸模塊-實(shí)現(xiàn)調(diào)度迷宮抽象數(shù)據(jù)類(lèi)型4) 選擇生成模塊-用戶(hù)自定義菜單的生成5) 調(diào)度模塊-實(shí)現(xiàn)車(chē)站的模擬各模塊之間的調(diào)用如下:主程序模塊選擇模塊棧模塊遞歸模塊調(diào)度模塊4.求解調(diào)度通路的偽碼算法:設(shè)定當(dāng)前位置的初值為入口位置;Do若當(dāng)前位置可通,按任意鍵進(jìn)行，同時(shí)選擇你需要的功能if(m=1)輸入你的你

9、的車(chē)廂長(zhǎng)度if(m=2)調(diào)用遞歸函數(shù)，輸出所有可能的序列if(m=3)歡迎你使用，系統(tǒng)while ( 棧不空 ); ?？照f(shuō)明沒(méi)有路徑存在 三、功能函數(shù)設(shè)計(jì)本系統(tǒng)主要是考慮對(duì)棧的使用，循環(huán)隊(duì)列和雙向鏈表的運(yùn)用。-頭文件設(shè)計(jì)(部分)-本部分是講述棧的相關(guān)操作：#include"stdlib.h"#include"stdafx.h"#include <windows.h>#include"stdio.h"#include <conio.h> #define MaxLen 100 struct Stack_node i

10、nt dataMaxLen; int top; s; /定義一個(gè)棧指針 int n;/定義輸入序列總個(gè)數(shù) /-棧的基本操作-void Initstack() s.top=-1; void push(int q)/元素n進(jìn)棧 s.top+; s.datas.top=q; int pop()/出棧 int temp; temp=s.datas.top; s.top-; return temp; int Emptys()/判斷棧空 if(s.top=-1) return 1; else return 0; -實(shí)現(xiàn)文件(部分)-本部分是主控函數(shù)，函數(shù)的調(diào)用以與菜單的選擇：main.cpp 主函數(shù)voi

11、d main() int pathMaxLen; int m; char ch; printf(" nnn - n"); printf(" | n"); printf(" |數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)|n"); printf(" | |n"); printf(" | 鐵路調(diào)度站模擬 |n"); printf(" | |n"); printf(" | 11級(jí)軟件工程|n"); printf(" | n"); printf(" -n&quo

12、t;); printf(" 按任意鍵繼續(xù) n"); if(ch=getch(); do / system("cls"); /停頓 printf("nnn * n"); printf(" * 1:請(qǐng)輸入火車(chē)的長(zhǎng)度: *n"); printf(" * *n"); printf(" * 2:輸出所有可能序列: *n"); printf(" * *n"); printf(" * 3:退出本程序: *n"); printf(" * n&

13、quot;); printf(" 請(qǐng)你根據(jù)需要選擇序號(hào)n"); scanf("%d",&m); if(m=1) printf("請(qǐng)輸入車(chē)廂長(zhǎng)度:n"); scanf("%d",&n); printf("車(chē)廂長(zhǎng)度已輸入!n"); getchar();/停止 getchar(); if(m=2) Initstack(); push(1); printf("所有輸出序列:n"); process(1,path,0); /從1 開(kāi)始，遞歸處理所有元素 getchar(

14、);/停止 getchar(); if(m=3) printf("歡迎退出!n"); printf("n"); if(m!=1&&m!=2&&m!=3) printf("n輸入有誤!請(qǐng)重新輸入!"); getchar();/停止 getchar(); while(m!=3);四:調(diào)試分析1. 做本次課設(shè), 剛開(kāi)始寫(xiě)的代碼中雖然用到了遞歸去求解函數(shù)，但是不能很好的輸完整結(jié)果，但是棧的相關(guān)操作是正確的,后來(lái)發(fā)現(xiàn)是由于調(diào)度遞歸算法中元素出棧后沒(méi)有繼續(xù)讓其進(jìn)棧。經(jīng)改后恢復(fù)正常。2. 在設(shè)計(jì)調(diào)度初始化函數(shù)的時(shí)候,

15、參數(shù)的傳遞出現(xiàn)錯(cuò)誤,主要是對(duì)指針和引用的理解出現(xiàn)混淆,通過(guò)查閱相關(guān)資料, 弄清楚了兩者之間的區(qū)別,指針是用于指向一個(gè)變量的地址,而引用只是對(duì)一個(gè)已存在變量的一個(gè)重命名. 3.用printf函數(shù)輸出標(biāo)志信息跟蹤函數(shù)調(diào)用,收到了顯著的效果,大大提高了調(diào) 試效率, 有利于以后的代碼調(diào)試.4. 在實(shí)現(xiàn)調(diào)度功能時(shí)發(fā)現(xiàn),每次調(diào)用system("cls")函數(shù)時(shí)都進(jìn)行清屏操作,屏幕只出現(xiàn)當(dāng)前的操作目標(biāo),一目了然。用戶(hù)進(jìn)入系統(tǒng)只需按要求進(jìn)行，操作時(shí)簡(jiǎn)潔清晰.代碼中的主要算法:/輸出一種可能的for(i=0;i<curp;i+)的時(shí)間復(fù)雜度為 O( n ). 5. 經(jīng)驗(yàn)體會(huì): 參考書(shū)本

16、的代碼進(jìn)行改進(jìn)，使用模塊化操作易于代碼的調(diào)試和修改,而且易于閱讀.在設(shè)計(jì)實(shí)現(xiàn)過(guò)程中雖然遇到了很多問(wèn)題,但是在解決這些問(wèn)題的過(guò)程中,鞏固和加深了我們對(duì)已學(xué)知識(shí)的理解,對(duì)團(tuán)隊(duì)合作有了一個(gè)比較基礎(chǔ)的認(rèn)識(shí),為以后的工作實(shí)踐打下了基礎(chǔ)，同時(shí)也增加了我們對(duì)這門(mén)課的認(rèn)識(shí).五.用戶(hù)手冊(cè)1.本程序的運(yùn)行環(huán)境為 DOS 操作系統(tǒng), 執(zhí)行文件為Programming.exe.2.進(jìn)入演示程序后 , 即顯示文本方式的用戶(hù)界面:操作提示信息鍵入選擇3. 進(jìn)入”建立自定義調(diào)度系統(tǒng)” 命令后, 根據(jù)提示輸入你需要選擇的序號(hào),回車(chē)后即可得到”調(diào)度建立完成”的提示信息.操作命令清單4. 數(shù)據(jù)不合要求則會(huì)提示:5. 進(jìn)入 “試測(cè)

17、模擬調(diào)度” 命令后, 用戶(hù)只需根據(jù)要求一步步的輸入,按Enter鍵后.完成后,輸出可能的結(jié)果。6. 輸入 “3” 即可退出此演示程序.六. 測(cè)試結(jié)果1. 根據(jù)提示輸入2. 輸入第二組測(cè)試數(shù)據(jù) ：3七、附錄 完整的程序清單:#include"stdlib.h"#include"stdafx.h"#include"stdio.h"#include <conio.h>#include"windows.h" #define MaxLen 100 struct snode int dataMaxLen; int

18、top; s; /定義一個(gè)棧指針 int n;/定義輸入序列總個(gè)數(shù) void Initstack() s.top=-1; void push(int q)/元素n進(jìn)棧 s.top+; s.datas.top=q; int pop()/出棧 int temp; temp=s.datas.top; s.top-; return temp; int Emptys()/判斷?？?if(s.top=-1) return 1; else return 0; /* 每次調(diào)用求值階段包含兩重遞歸，只有全部返回，才表示本pos 處理完，可以對(duì)上一個(gè)元素求值，process 就是找出當(dāng)前元素進(jìn)棧后所有可能的操作，

19、即在當(dāng)前元素進(jìn)棧后各種情況下， 包括不出棧，立即出棧，出棧后繼續(xù)出棧情況(出棧遞歸)下，繼續(xù)處理下一個(gè)元素(入棧遞歸) */ void process(int pos,int path,int curp)/當(dāng)前處理位置pos的元素 int m,i; if(pos<n)/編號(hào)進(jìn)棧遞歸 push(pos+1);/當(dāng)前元素進(jìn)棧后下一個(gè)元素繼續(xù)進(jìn)棧 process(pos+1,path,curp); /處理下一個(gè)元素，返回表明下一個(gè)元素進(jìn)棧的情況處理完了,這里用遞歸將2,3,4.n壓入棧 pop(); /下一個(gè)元素處理完后，pop 掉，準(zhǔn)備處理直接出棧 if(!Emptys()/遞歸處理出棧 m

20、=pop(); pathcurp=m; /數(shù)組存放出棧元素 curp+; process(pos,path,curp);/出棧后處理下一個(gè)素繼續(xù)進(jìn)棧,用遞歸將n,.4,3,2,1壓入棧 push(m);/遞歸完后又按原順序?qū)?,2,3,4.n壓入棧 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

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