數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-走迷宮

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 走迷宮游戲 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 設(shè)計題目：走迷宮游戲?qū)?業(yè)：計算機科技院 系：計算機學(xué)院姓 名： xxxxxxxx學(xué) 號： xxxxxxxxx時間：2013年10月10日目 錄一、課程設(shè)計的目的.2二、需求分析.2三、課程設(shè)計報告內(nèi)容.31.概要設(shè)計.32.詳細設(shè)計.43.調(diào)試分析.94.用戶手冊.95.測試結(jié)果.106.程序清單.11四、小結(jié)16 五、參考文獻16一、課程設(shè)計的目的(1) 熟練使用 C 語言編寫程序，解決實際問題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本

2、方法和技能;(4) 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力;二、需求分析程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務(wù)是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處。要求：老鼠形象可辨認(rèn)，可用鍵盤操縱老鼠上下左右移動；迷宮的墻足夠結(jié)實，老鼠不能穿墻而過；正確檢測結(jié)果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，否則提示失??；添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻；找出走出迷宮的所有路徑，以及最短路徑。利用序列化功能實現(xiàn)迷宮地圖文件的存盤和讀出等功能三、實驗報告內(nèi)容1 概要設(shè)計（1） 具體要求構(gòu)建一個二維數(shù)組maze

3、M+2N+2用于存儲迷宮矩陣自動或手動生成迷宮，即為二維數(shù)組mazeM+2N+2賦值構(gòu)建一個隊列用于存儲迷宮路徑建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況實現(xiàn)搜索算法屏幕上顯示操作菜單 （2）本程序包含10個函數(shù)： 主函數(shù) main()手動生成迷宮函數(shù) shoudong_maze()自動生成迷宮函數(shù) zidong_maze()將迷宮打印成圖形 print_maze()打印迷宮路徑 (若存在路徑) result_maze()入隊 enqueue()出隊 dequeue()判斷隊列是否為空 is_empty()訪問節(jié)點 visit()搜索迷宮路徑 mgpath()2 詳

4、細設(shè)計實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法節(jié)點類型和指針類型迷宮矩陣類型：int mazeM+2N+2;為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型：struct pointint row,col,predecessor que512迷宮的操作(1)手動生成迷宮void shoudong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n)輸入mazeij的值(2)自動生成迷宮void zidong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n) mazeij=rand(

5、)%2 /由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(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輸出 、搜索迷宮路徑迷宮中隊列入隊操作void enqueue(struct point p)將p放入隊尾，tail+迷宮中隊列出隊操作struct point deque

6、ue(struct point p)head+,返回quehead-1判斷隊列是否為空int is_empty()返回head=tail的值，當(dāng)隊列為空時，返回0訪問迷宮矩陣中節(jié)點void visit(int row,int col,int maze4141)建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,head-1,mazerowcol=2,表示該節(jié)點以被訪問過;調(diào)用enqueue(visit_point),將該節(jié)點入隊路徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點為struct point p=0,0,-1,從maz

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

8、.col=0,說明未到迷宮下邊界，且其下方有通路,則visit(p.row+1,p.col,maze),將下方節(jié)點入隊標(biāo)記已訪問如果p.col-1>0且mazep.rowp.col-1=0,說明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze),將左方節(jié)點入隊標(biāo)記已訪問如果p.row-1>0且mazep.row-1p.col=0,說明未到迷宮上邊界，且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點入隊標(biāo)記已訪問訪問到出口(找到路徑)即p.row=m-1且p.col=n-1,則逆序?qū)⒙窂綐?biāo)記為3即mazep.rowp.

9、col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3; 最后將路徑圖形打印出來。菜單選擇while(cycle!=(-1)printf("n");printf(" 歡迎進入走迷宮游戲演示系統(tǒng) n");printf(" - n");printf(" -1. 手動生成迷宮 n");printf(" -2.系統(tǒng)自動生成迷宮 n");printf(" -3.退出系統(tǒng) n");printf("

10、n");printf(">>>>>>>n");printf("請選擇你的操作 bb");scanf("%d",&i);switch(i)case 1:printf("n請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(shù) bb");scanf("%d",&n);while(m<=0|m>39)|(n&

11、lt;=0|n>39)printf("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請重新輸入：nn");printf("請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(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("

12、nnPress Enter Contiue!n");getchar();while(getchar()!='n');break;case 2:printf("n請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(shù) bb");scanf("%d",&n);while(m<=0|m>39)|(n<=0|n>39)printf("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0

13、-39),請重新輸入!nn");printf("請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(shù) bb");scanf("%d",&n);zidong_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(getch

14、ar()!='n');break;case 3: cycle=(-1);break;default:printf("n");printf("你的輸入有誤!n");printf("nPress Enter Contiue!n");getchar();while(getchar()!='n');break;注：具體源代碼見附錄3調(diào)試分析 在調(diào)試過程中，首先使用的是棧進行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法4.用戶手冊本程序的運行環(huán)境為windows7 64位操作系統(tǒng)進入演示

15、程序后即顯示文本方式的用戶界面5.測試結(jié)果圖1 手動生成迷宮圖2 系統(tǒng)自動生成迷宮6程序清單#include<stdlib.h>#include<stdio.h>#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf("nn");printf("請按行輸入迷宮，0表示通路，1表示障礙:nn&q

16、uot;);for(i=0;i<m;i+)for(j=0;j<n;j+)scanf("%d",&mazeij);void zidong_maze(int m,int n)int i,j;printf("n迷宮生成中nn");system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2;/由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX/RAND_MAX是定義在stdlib.h中的,其值至少為32767)/要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：

17、k=rand()%(Y-X+1)+X; void print_maze(int m,int n)int i,j;printf("n迷宮生成結(jié)果如下:nn");printf("迷宮入口n");printf("");for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+) if(mazeij=0) printf("");if(mazeij=1) printf("");printf("迷宮出口n");void result

18、_maze(int m,int n)int i,j;printf("迷宮通路(用'鼠'表示)如下所示：nt");for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+)if(mazeij=0|mazeij=2) printf("");if(mazeij=1) printf("");if(mazeij=3) printf("鼠");void enqueue(struct point p)queuetail=p;tail+;struct poi

19、nt 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)printf("n-n");printf("

20、;此迷宮無解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+1<n)&&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze);if(p.row+1<m)&&(mazep.row+1p.col=0) visit(p.row+1,p.col,maze);if(p.col-1>=0)&&

21、(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,p.col,maze);if(p.row=m-1&&p.col=n-1)printf("n-n");printf("迷宮路徑為：n");printf("(%d,%d)n",p.row,p.col);mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.pred

22、ecessor;printf("(%d,%d)n",p.row,p.col);mazep.rowp.col=3;else printf("n-n");printf("此迷宮無解！nn");X=0;return 0;int main()int i,m,n,cycle=0;system("cls");system("color 1f");printf(" n");printf(" 必做題：走迷宮游戲 n");printf(" 姓名：xxxx n&qu

23、ot;);printf(" 學(xué)號：xxxxxxxxx n");printf(" n");while(cycle!=(-1) printf("n"); printf(" 歡迎進入走迷宮游戲演示系統(tǒng) n"); printf(" - n"); printf(" 1.手動生成迷宮 n"); printf(" 2.系統(tǒng)自動生成迷宮 n"); printf(" 3.退出系統(tǒng) n"); printf("n");printf(&qu

24、ot;>>>>>>>n");printf("請選擇你的操作 bb");scanf("%d",&i);switch(i)case 1:printf("n請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(shù) bb");scanf("%d",&n);while(m<=0|m>39)|(n<=0|n>39)print

25、f("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請重新輸入：nn");printf("請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(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 Conti

26、ue!n");getchar();while(getchar()!='n');break;case 2:printf("n請輸入行數(shù) bb");scanf("%d",&m);printf("n");printf("請輸入列數(shù) bb");scanf("%d",&n);while(m<=0|m>39)|(n<=0|n>39)printf("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請重新輸入!nn");printf("請輸入行數(shù) bb");scanf("%d",&m);printf("