數據結構課程設計報告----迷宮問題

1、<p><b>　　課程設計報告</b></p><p>　　課程名稱： 數據結構課程設計 </p><p>　　課程題目： 迷宮問題 </p><p>　　《數據結構》課程設計</p><p><b>　　迷宮問題</b></p><p><b>

2、;　　[實驗目的]</b></p><p>　　綜合運用數組、遞歸等數據結構知識，掌握、提高分析、設計、實現及測試程序的綜合能力。</p><p><b>　　[實驗內容及要求]</b></p><p>　　以一個M×N的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口

3、的通路，或得出沒有通路的結論。</p><p>　　根據二維數組，輸出迷宮的圖形。</p><p>　　探索迷宮的四個方向：RIGHT為向右，DOWN向下，LEFT向左，UP向上，輸出從入口到出口的行走路徑。</p><p><b>　　[測試數據]</b></p><p>　　左上角（1，1）為入口，右下角（8，9）為

4、出口。</p><p><b>　　[實現方法]</b></p><p>　　可使用回溯方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。</p><p><b>　　[具體思路及結果]

5、</b></p><p>　　首先，事先聲明好矩陣，矩陣長寬，棧頂元素，矩陣點左邊等。</p><p>　　然后，要求用戶盡享交互輸入迷宮(maze)各個點處的值(1或0)</p><p>　　保存并初始化棧頂元素，置所有方向數為下。</p><p>　　之后，一比較整潔大方的形式打印原迷宮供用戶查看。</p>&l

6、t;p>　　同時，開始本程序的重點，回溯算法，以1,2,3,4分別表示下上左右。</p><p>　　多次使用for循環(huán)尋找可以到達出口的路徑，期間分別先后試探下，左，上，右</p><p>　　置已經走過的點為2防止死循環(huán)，尋找完后存在TOP[]棧中。</p><p>　　最后，打印找到的當前迷宮路徑并以（坐標1）——>（坐標2）的形式輸出路徑，并且在

7、原迷宮的基礎上表示出當前找到的路徑，以#代表走過的路徑0代表沒有障礙的地方，1代表障礙，畫出迷宮路徑圖，并且立刻執(zhí)行下一次循環(huán)，尋找下一條可通過的路徑，并還原迷宮圖，繼續(xù)尋找路徑知道找到所有解后自動退出。</p><p><b>　　[具體代碼]</b></p><p>　　#include <stdio.h></p><p>　　

8、#include <stdlib.h></p><p>　　#define n1 5</p><p>　　#define n2 5</p><p>　　typedef struct node</p><p><b>　　{</b></p><p>　　int x;//存x坐標</

9、p><p>　　int y;//存y坐標</p><p>　　int c;//存該點可能的下點所在的方向，表示向1表示向下，2左，3向上，4向右</p><p>　　}linkstack;</p><p>　　linkstack top[25];</p><p>　　int rows=0;</p><p

10、>　　int cols=0;</p><p>　　int i,j,k,m,p,q=0;</p><p>　　int maze[n1][n2];</p><p>　　void main()</p><p><b>　　{</b></p><p>　　for(p=0;p<=n1-1;p++

11、){</p><p>　　for(q=0;q<=n2-1;q++){</p><p>　　printf("請輸入第%d行第%d列的數\n",p+1,q+1);</p><p>　　scanf("%d",&maze[p][q]);</p><p><b>　　}</b>

12、</p><p><b>　　}</b></p><p>　　//初始化top[]，置所有方向為下</p><p>　　for(i=0;i<n1 * n2;i++)</p><p>　　{top[i].c=1;}</p><p>　　printf("the maze is:\n&q

13、uot;);</p><p><b>　　//打印原迷宮</b></p><p>　　for(i=0;i<n1;i++)</p><p>　　{for(j=0;j<n2;j++)</p><p>　　printf(maze[i][j]?"1 ":"0 ");</p

14、><p>　　printf("\n");}</p><p>　　i=0;top[i].x=0;top[i].y=0;</p><p>　　maze[0][0]=2;</p><p><b>　　//回溯算法</b></p><p><b>　　do{</b>&

15、lt;/p><p>　　if(top[i].c<5) //還可以向前試探</p><p>　　{if(top[i].x==4&&top[i].y==4) //已找到一個組合</p><p><b>　　{ //打印路徑</b></p><p>　　printf("The way %d i

16、s:\n",m++);</p><p>　　for(j=0;j<=i;j++)</p><p>　　{printf("(%d,%d)-->",top[j].x,top[j].y);}</p><p>　　printf("\n");</p><p>　　//打印選出路徑的迷宮<

17、/p><p>　　for(j=0;j<n1;j++)</p><p>　　{for(k=0;k<n2;k++)</p><p>　　{if(maze[j][k]==0)printf("0 ");</p><p>　　else if(maze[j][k]==2) printf("# ");&l

18、t;/p><p>　　else printf("1 ");}</p><p>　　printf("\n");}</p><p>　　maze[top[i].x][top[i].y]=0;</p><p>　　top[i].c=1;</p><p><b>　　i--;<

19、;/b></p><p>　　top[i].c+=1;</p><p><b>　　continue;</b></p><p><b>　　}</b></p><p>　　switch(top[i].c) //向前試探</p><p><b>　　{<

20、/b></p><p><b>　　case 1:</b></p><p>　　{if(maze[top[i].x][top[i].y+1]==0)//下</p><p><b>　　{i++;</b></p><p>　　top[i].x=top[i-1].x;</p><

21、;p>　　top[i].y=top[i-1].y+1;</p><p>　　maze[top[i].x][top[i].y]=2;}</p><p><b>　　else</b></p><p>　　{top[i].c+=1;}</p><p><b>　　break;}</b></p&

22、gt;<p><b>　　case 2:</b></p><p>　　{if(maze[top[i-1].x-1][top[i].y]==0)//左</p><p><b>　　{i++;</b></p><p>　　top[i].x=top[i-1].x-1;</p><p>　　t

23、op[i].y=top[i-1].y;</p><p>　　maze[top[i].x][top[i].y]=2;}</p><p><b>　　else</b></p><p>　　{top[i].c+=1;}</p><p><b>　　break;}</b></p><p&

24、gt;<b>　　case 3:</b></p><p>　　{if(maze[top[i].x][top[i].y-1]==0)//上</p><p><b>　　{i++;</b></p><p>　　top[i].x=top[i-1].x;</p><p>　　top[i].y=top[i-1

25、].y-1;</p><p>　　maze[top[i].x][top[i].y]==2;}</p><p><b>　　else</b></p><p>　　{top[i].c+=1;}</p><p><b>　　break;}</b></p><p><b>

26、　　case 4:</b></p><p>　　{if(maze[top[i].x+1][top[i].y]==0)//右</p><p><b>　　{i++;</b></p><p>　　top[i].x=top[i-1].x+1;</p><p>　　top[i].y=top[i-1].y;</p

27、><p>　　maze[top[i].x][top[i].y]=2;}</p><p><b>　　else</b></p><p>　　{top[i].c+=1;}</p><p><b>　　break;}</b></p><p><b>　　}</b>

28、</p><p><b>　　}</b></p><p>　　else //回溯</p><p>　　{if(i==0) return; //已找完所有解</p><p>　　maze[top[i].x][top[i].y]=0;</p><p>　　top[i].c=1;</p>