1、精選優質文檔-傾情為你奉上一、需求分析本課程設計是解決迷宮求解的問題，從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路退回，換一個方向再繼續探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進先出的結構來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法中要應用“棧”的思想假設“當前位置”指的是“在搜索過程中的某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當前位置“可通”，則納入“當前路徑”，并繼續朝“下一位置”探索，即切換“下一位置”為“當前位置”，如此重復直至到達出口；若當前位置“不可通”，則應順著“來向

2、”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續探索；若該通道塊的四周4個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。所謂“下一位置”指的是當前位置四周4個方向（東、南、西、北）上相鄰的方塊。假設以棧S記錄“當前路徑”，則棧頂中存放的是“當前路徑上最后一個通道塊”。由此，“納入路徑”的操作即為“當前位置入棧”；“從當前路徑上刪除前一通道塊”的操作即為“出棧”。二、數據結構1. 數據結構設計考慮1) 建立一個二維數組表示迷宮的路徑（0表示通道，1表示墻壁）；2) 創建一個棧，用來存儲“當前路徑”，即“在搜索過程中某一時刻所在圖中某個方塊位置”。2. 邏輯結構存儲結構1) 創建

3、一個Int類型的二維數組int mazen1n2,用來存放0和1 ；2) 創建一個結構體用來儲存數組信息(數組的橫坐標X，數組的縱坐標Y，方向C) typedef struct node int x; int y; int c; linkstack;3) 創造一個棧包括(top表示棧頂元素) linkstack topn1*n2;三、算法設計首先，創建數組的大小，此數組大小要求用戶自己輸入。具體算法： printf("輸入迷宮大小(提示:行列數不能超過50!):"); scanf("%d",&g); printf("大小創建完畢,請輸入

4、迷宮:n");其次，用戶自己定義迷宮的內容，算法： void shuzu(int g,int h) int a,b; for(a=0;a<g;a+) for(b=0;b<h;b+) scanf("%d",&mazeab); 第三，產生迷宮，算法： void scsu(int g,int h) int a,b; printf("生成的迷宮是:n"); for(a=0;a<g;a+) for(b=0;b<h;b+) printf(mazeab?"#":" "); printf(

5、"n"); 最后，迷宮尋路找到出口，其算法見源代碼。根據這些算法設計，我們設計出了迷宮求解的應用。四、源代碼#include<stdio.h>#include<stdlib.h>#define n1 50/定義行范圍#define n2 50/定義列范圍typedef struct node/創建一個結構體存儲數組信息int x;int y;int c;linkstack;int mazen1n2; /創建一個二維數組linkstack topn1*n2; /創建一個N*N的棧int i,j,k,m=1,run; void shuzu(int g,i

6、nt h) /以二維數組形式定義迷宮內容 int a,b; for(a=0;a<g;a+) for(b=0;b<h;b+) scanf("%d",&mazeab);/輸入迷宮對應的數組數據 void scsu(int g,int h)/生成迷宮 int a,b; printf("生成的迷宮是:n"); for(a=0;a<g;a+) for(b=0;b<h;b+) printf(mazeab?"#":" ");/輸出迷宮圖形 printf("n"); void m

7、ain() int g,h,v; int w; printf("*n"); printf("*n"); printf("* 歡迎使用迷宮求解 *n"); printf("*n"); printf("*n"); printf("n"); printf("*n"); printf("*n"); printf("*迷宮求解請按:1 *n"); printf("* 退出請按:2 *n"); printf(

8、"*n"); printf("*n"); printf("輸入您的選擇:"); scanf("%d",&w); switch(w)/若輸入的W為1或2,則繼續程序 case 1:printf("輸入迷宮大小(提示:行列數不能超過50!):");/W為1時 scanf("%d",&g); printf("大小創建完畢,請輸入迷宮:n"); h=g;/確定數組大小為g維 shuzu(g,h); for(i=0;i<=g*h;i+) top

9、i.c=1; scsu(g,h);/生成迷宮 i=0; topi.x=1;/i=0時X方向對應值得和為1 topi.y=0; /i=0時Y方向對應值得和為0 maze10=2;/入口迷宮值變為2 run=1; v=1; do /定義行走規則和出口判斷 if(topi.c<5)/若i點可到方向值小于5則向下進行 if(topi.x=(g-2)&&topi.y=(h-1)/ 當i點為出口時所滿足的條件 printf("第%d條通路是:n",m+);/輸出不同的路程 for(j=0;j<=i;j+) printf("(%d,%d)"

10、,topj.x,topj.y); /輸出通路坐標 printf("n"); for(j=0;j<g;j+)/求出迷宮路線圖形 for(k=0;k<h;k+) if(mazejk=0) printf(" "); else if(mazejk=2) printf("O"); else printf("#"); printf("n"); mazetopi.xtopi.y=0; topi.c=1; i-; topi.c+=1; continue; switch(topi.c) case 0:

11、 run=0; if(v=1) printf("此迷宮無通路!"); break; case 1: if(mazetopi.xtopi.y+1=0) i+; topi.x=topi-1.x; topi.y=topi-1.y+1; mazetopi.xtopi.y=2; if(mazeg-2h-1=2) v=0; else topi.c+=1; break; case 2: if(mazetopi.x-1topi.y=0) i+; topi.x=topi-1.x-1; topi.y=topi-1.y; mazetopi.xtopi.y=2; else topi.c+=1; b

12、reak; case 3: if(mazetopi.xtopi.y-1=0) i+; topi.x=topi-1.x; topi.y=topi-1.y-1; mazetopi.xtopi.y=2; else topi.c+=1; break; case 4: if(mazetopi.x+1topi.y=0) i+; topi.x=topi-1.x+1; topi.y=topi-1.y; mazetopi.xtopi.y=2; else topi.c+=1; break; else if(i=0) return; mazetopi.xtopi.y=0; topi.c=1; i-; topi.c+=1; while(run=1); break; case 2: printf("歡迎下次使用!") ; break; default: break; 六、體會及不足之處