1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：走迷宮游戲?qū)I(yè)：計(jì)算機(jī)科技院系:計(jì)算機(jī)學(xué)院姓名:XXXXXXXX學(xué)號(hào)XXXXXXXXX時(shí)間：2013年10月10日目錄一、 課程設(shè)計(jì)的目的2二、需求分析三、課程設(shè)計(jì)報(bào)告內(nèi)容 2222222222222222221. 概要設(shè)計(jì) 222222222222222222222222232. 詳細(xì)設(shè)計(jì)2222222222222222. 22222243. 調(diào)試分析 2222222222222222222. 2294. 用戶手冊(cè) 22222222222222222222222225. 測(cè)試結(jié)果 2222222222222222222222221206. 程序清單 222222

2、222222222222222222121四、小結(jié) 2222222222222221262222五、參考文獻(xiàn) 2222222222222222 16、課程設(shè)計(jì)的目的(1) 熟練使用 C 語言編寫程序，解決實(shí)際問題 ;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法， 具備初步的獨(dú)立分析和 設(shè)計(jì)能力 ;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試 等基本方法和技能 ;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能 力;二、需求分析 程序開始運(yùn)行時(shí)顯示一個(gè)迷宮地圖， 迷宮中央有一只老鼠， 迷宮的右 下方有一個(gè)糧倉。 游戲的任務(wù)是使用鍵盤上的方向鍵操縱老鼠在規(guī)定 的時(shí)間

3、內(nèi)走到糧倉處。要求： 老鼠形象可辨認(rèn)，可用鍵盤操縱老鼠上下左右移動(dòng)； 迷宮的墻足夠結(jié)實(shí)，老鼠不能穿墻而過； 正確檢測(cè)結(jié)果，若老鼠在規(guī)定時(shí)間內(nèi)走到糧倉處，提示成功，否則 提示失敗； 添加編輯迷宮功能， 可修改當(dāng)前迷宮， 修改內(nèi)容：墻變路、路變墻； 找出走出迷宮的所有路徑，以及最短路徑。利用序列化功能實(shí)現(xiàn)迷宮地圖文件的存盤和讀出等功能三、實(shí)驗(yàn)報(bào)告內(nèi)容1 概要設(shè)計(jì)( 1)具體要求 構(gòu)建一個(gè)二維數(shù)組 mazeM+2N+2 用于存儲(chǔ)迷宮矩陣 自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組mazeM+2N+2賦值 構(gòu)建一個(gè)隊(duì)列用于存儲(chǔ)迷宮路徑 建立迷宮節(jié)點(diǎn) struct point, 用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問 情況

4、 實(shí)現(xiàn)搜索算法 屏幕上顯示操作菜單(2) 本程序包含 10 個(gè)函數(shù)： 主函數(shù) main() 手動(dòng)生成迷宮函數(shù) shoudong_maze() 自動(dòng)生成迷宮函數(shù) zidong_maze() 將迷宮打印成圖形 print_maze() 打印迷宮路徑 ( 若存在路徑 ) result_maze() 入隊(duì) enqueue() 出隊(duì) dequeue() 判斷隊(duì)列是否為空 is_empty() 訪問節(jié)點(diǎn) visit() 搜索迷宮路徑 mgpath()2 詳細(xì)設(shè)計(jì) 實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型及操作的偽代碼算法節(jié)點(diǎn)類型和指針類型迷宮矩陣類型： int mazeM+2N+2; 為方便操作使其為全局變量 迷

5、宮中節(jié)點(diǎn)類型及隊(duì)列類型： struct pointint row,col,predecessor que512迷宮的操作(1) 手動(dòng)生成迷宮void shoudong_maze(int m,int n) 定義 i,j 為循環(huán)變量for(i=m)for(j=n)輸入 mazeij 的值(2) 自動(dòng)生成迷宮void zidong_maze(int m,int n) 定義 i,j 為循環(huán)變量for(i=m)for(j=n)mazeij=rand()%2 / 由于 rand() 產(chǎn)生的隨機(jī)數(shù)是從 0 到RAND_MAX,RAND_I是定義在stdlib.h中的，其值至少為32767),要產(chǎn)生從X到丫的

6、數(shù)，只需要這樣寫：k=rand()%(Y-X+1)+X;(3) 打印迷宮圖形void print_maze(int m,int n) 用 i,j 循環(huán)變量，將 mazeij 輸出 、 (4) 打印迷宮路徑void result_maze(int m,int n) 用 i,j 循環(huán)變量，將 mazeij 輸出 、 搜索迷宮路徑 迷宮中隊(duì)列入隊(duì)操作void enqueue(struct point p)將p放入隊(duì)尾，tail+ 迷宮中隊(duì)列出隊(duì)操作struct point dequeue(struct point p)head+, 返回 quehead-1 判斷隊(duì)列是否為空int is_empty(

7、) 返回 head=tail 的值，當(dāng)隊(duì)列為空時(shí)，返回 0 訪問迷宮矩陣中節(jié)點(diǎn)void visit(int row,int col,int maze4141) 建立新的隊(duì)列節(jié)點(diǎn) visit_point, 將其值分別賦為 row,col,head-1,mazerowcol=2, 表示該節(jié)點(diǎn)以被訪問過 ; 調(diào)用 enqueue(visit_point), 將該節(jié)點(diǎn)入隊(duì) 路徑求解void mgpath(int maze4141,int m,int n) 先定義入口節(jié)點(diǎn)為 struct point p=0,0,-1, 從 maze00 開始訪 問。如果入口處即為障礙，則此迷宮無解，返回 0 ，程序結(jié)束

8、。否 則訪問入口節(jié)點(diǎn)，將入口節(jié)點(diǎn)標(biāo)記為訪問過 mazep.rowp.col=2, 調(diào)用函數(shù) enqueue(p) 將該節(jié)點(diǎn)入隊(duì)。判斷隊(duì)列是否為空，當(dāng)隊(duì)列不為空時(shí)，則運(yùn)行以下操作： 調(diào)用 dequeue() 函數(shù)，將隊(duì)頭元素返回給 p，如果 p.row=m-1 且 p.col=n-1, 即到達(dá)出口節(jié)點(diǎn)，即找到了路徑， 結(jié)束 如果 p.col+1n 且 mazep.rowp.col+1=0, 說明未到迷宮右邊界， 且其右方有通路 , 則 visit(p.row,p.col+1,maze), 將右邊節(jié)點(diǎn)入隊(duì)標(biāo) 記已訪問如果 p.row+10 且 mazep.rowp.col-1=0, 說明未到迷宮左

9、邊界， 且其左方有通路 , 則 visit(p.row,p.col-1,maze), 將左方節(jié)點(diǎn)入隊(duì)標(biāo) 記已訪問如果 p.row-10 且 mazep.row-1p.col=0, 說明未到迷宮上邊界， 且其上方有通路 , 則 visit(p.row,p.col+1,maze), 將上方節(jié)點(diǎn)入隊(duì)標(biāo) 記已訪問訪問到出口(找到路徑)即p.row=m-1且p.col=n-1,則逆序?qū)⒙窂綐?biāo)記為 3 即 mazep.rowp.col=3;while(p.predecessor!=-1) p=queuep.predecessor; mazep.rowp.col=3;最后將路徑圖形打印出來。printf(“

10、|1n);printf( I歡迎進(jìn)入走迷宮游戲演示系統(tǒng)n);printf( II n);printf( I-1.手動(dòng)生成迷宮n);printf( I-2.系統(tǒng)自動(dòng)生成迷宮n);printf( I-3.退出系統(tǒng)n);printf(11菜單選擇while(cycle!=(-1) n);IIIIprintf(n);printf( 請(qǐng)選擇你的操作 bb);scanf(%d,&i);switch(i)case 1:printf(n 請(qǐng)輸入行數(shù) bb);scanf(%d,&m); printf(n);printf( 請(qǐng)輸入列數(shù) bb);scanf(%d,&n); while(m39)|(n39)print

11、f(n 抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍 請(qǐng)重新輸入： nn);printf( 請(qǐng)輸入行數(shù) bb);scanf(%d,&m);printf(n);printf( 請(qǐng)輸入列數(shù) bb);scanf(%d,&n);shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n);if(X!=0)result_maze(m,n);printf(nnPress Enter Contiue!n);getchar();while(getchar()!=n);break;case 2:printf(n 請(qǐng)輸入行數(shù) bb);scanf(%d,&m); printf(n)

12、;printf( 請(qǐng)輸入列數(shù) bb);scanf(%d,&n); while(m39)|(n39) printf(n 抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍 請(qǐng)重新輸入 !nn);printf( 請(qǐng)輸入行數(shù) bb);scanf(%d,&m);printf(n);printf( 請(qǐng)輸入列數(shù) bb);scanf(%d,&n);zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n);(0-39,0-39),(0-39,0-39),if(X!=0) result_maze(m,n); printf(nnPress Enter Contiue!n); getch

13、ar();while(getchar()!=n);break;case 3: cycle=(-1);break;default:printf(n);printf(你的輸入有誤!n);prin tf(nPress En terCon tiue!n);getchar();while(getchar()!=n);break;注：具體源代碼見附錄3. 調(diào)試分析在調(diào)試過程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法4. 用戶手冊(cè) 本程序的運(yùn)行環(huán)境為windows7 64位操作系統(tǒng) 進(jìn)入演示程序后即顯示文本方式的用戶界面歡迎進(jìn)入定迷宮游戲演示系統(tǒng)宮迷宮成迷生

14、動(dòng)統(tǒng)出 12祕(mì)華你的操作(15. 測(cè)試結(jié)果型奧奔孚員謁巻還示彗囂條統(tǒng)目動(dòng)生晟迷宮陰選擇你的操作【口 ”青輸入行數(shù)【4】 L鏘入列數(shù)【切贋按行輸入迷宮，/表示誦路，i表示障礙:” D DB 1 Q 00 0 0 11 0 e a迷宮生成結(jié)果如下:謹(jǐn)宮入口-迷宮出口迷宮路徑為：(2,2)Cl,2C0.2)(0,1)迷宮通路誦“評(píng)表示如下所示:鼠鼠鼠Jie&s Ent&y Contijuef圖1手動(dòng)生成迷宮歡迎進(jìn)入走迷宮游戲演示系統(tǒng)囉癒迷宮請(qǐng)選擇你的操作【彰請(qǐng)輸入行數(shù)【5】 請(qǐng)輸入列數(shù)畀 迷宮生成中 請(qǐng)按任意鍵繼續(xù) 迷宮生成結(jié)果如下， 草宮入口 1111 I J 1: h I *迷宮出口 此迷宮無解

15、圖2系統(tǒng)自動(dòng)生成迷宮6. 程序清單#in clude#in clude#defi ne N 39#defi ne M 39int X;int mazeN+2M+2;struct poi ntint row,col,predecessor;queue512;int head=0,tail=0;void shoudo ng_maze(i nt m,i nt n)int i,j;prin tf(nn);printf(”請(qǐng)按行輸入迷宮，0表示通路，1表示障礙：nn); for(i=0;im;i+) for(j=0;jn;j+) scanf(%d,&mazeij);void zidong_maze(in

16、t m,int n)int i,j;printf(n迷宮生成中nn);system(pause);for(i=0;im;i+)for(j=0;jn;j+) mazeij=rand()%2;/ 由于 rand() 產(chǎn)生的隨機(jī)數(shù)是從 0 到 RAND_MAXRAND_MAX是定義在 stdlib.h 中的,其值至少為 32767)/要產(chǎn)生從X到Y(jié)的數(shù)，只需要這樣寫：k=rand()%(Y-X+1)+X;void print_maze(int m,int n)int i,j;printf(n 迷宮生成結(jié)果如下 :nn);printf( 迷宮入口 n);printf(J );for(i=0;im;i+

17、)printf(n);for(j=0;jn;j+)if(maz eij=0) printf( );if(mazeij=1) printf();printf(”t迷宮出口 n);void result_maze(int m,int n)int i,j;printf( 迷宮通路 ( 用“鼠”表示 ) 如下所示： nt); for(i=0;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0|mazeij=2) printf( );if(mazeij=1) printf( );if(mazeij=3) printf(鼠 );void enqueue(struct poi

18、nt p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)pri

19、ntf(nn);printf( 此迷宮無解 nn);X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze); if(p.row+1=0)&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze); if(p.row-1=0)&(mazep.row-1p.col=0) visit(p.row-1,

20、p.col,maze);if(p.row=m-1&p.col=n-1)printf(nn);printf( 迷宮路徑為： n);printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;while(p.predecessor!=-1) p=queuep.predecessor; printf(%d,%d)n,p.row,p.col); mazep.rowp.col=3;else printf(nn);printf( 此迷宮無解！ nn);X=0;return 0;void main()int i,m,n,cycle=0;system(cls);system(co

21、lor 1f);prin tf(”|1n);printf(”丨必做題：走迷宮游戲I n);printf(I姓名：xxxxI n);printf(I學(xué)號(hào)： xxxxxxxxxI n);printf(11n);while(cycle!=(-1)prin tf(i1n);printf(|歡迎進(jìn)入走迷宮游戲演示系統(tǒng)| n);printf(| n);printf(|1.手動(dòng)生成迷宮| n);printf(|2.系統(tǒng)自動(dòng)生成迷宮| n);printf(|printf(1一3.退出系統(tǒng)| n);1n);printf(n);printf( 請(qǐng)選擇你的操作 bb);scanf(%d,&i);switch(i)c

22、ase 1:printf(n 請(qǐng)輸入行數(shù) bb);scanf(%d,&m); printf(n);printf( 請(qǐng)輸入列數(shù) bb);scanf(%d,&n);while(m39)|(n39)printf(n 抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍 (0-39,0-39), 入： nn);printf(請(qǐng)輸入行數(shù) bb);scanf(%d,&m);printf(n);printf(請(qǐng)輸入列數(shù) bb);scanf(%d,&n); shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n);if(X!=0) result_maze(m,n); printf(nnPress Enter Contiue!n); getchar();while(getchar()!=n);break;case 2: printf(n 請(qǐng)輸入行數(shù) bb);scanf(%d,&m); printf(n);printf( 請(qǐng)輸入列數(shù) bb);scanf(%d,&n); while(m39)|(n39)printf(n 抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍 (0-39,0-39), 入!nn);printf(請(qǐng)輸入行數(shù) bb);scanf(%d,&m);printf(n);printf(請(qǐng)輸入列數(shù) bb);scanf(%d,&n); zidong_maze(m,n)