數(shù)據結構迷宮課程設計

1、<p>　　《數(shù)據結構》課程設計報告</p><p>　　課題名稱：__迷宮問題_______ _____</p><p>　　班級：_____計算機3班_____________</p><p>　　學 號：____ __________</p><p><b>　　2010年6月</b></

2、p><p>　　一、課題名稱：迷宮問題</p><p>　　二、課題設計的基本思想，原理和算法描述</p><p>　　所謂求迷宮問題，就是在一個指定的迷宮中求出從入口到出口的路徑，在求解時，我們先從入口出發(fā)，順某一方向向前試探，若能走通，則繼續(xù)往前走，否則，沿原路退回，換一個方向再繼續(xù)試探，直至所有可能的通路都試探完為止。</p><p>&l

3、t;b>　　三、源程序及注釋</b></p><p>　　#include <stdio.h></p><p>　　#define Maxsize 500</p><p>　　#define M 4</p><p>　　#define N 4</p><p><b>　　str

4、uct</b></p><p><b>　　{</b></p><p>　　int i,j,di; //當前方塊行號、列號、下一可走相鄰方位的方位號</p><p>　　}qu[Maxsize],path[Maxsize];

5、 //定義棧、最小路徑存放</p><p>　　int top=-1; //初始化棧頂指針</p><p>　　int mgpath(int xi,int yi,int xe,int ye,int mg[M

6、+2][N+2]) //求解路徑為(xi.yi)->(xe,ye)</p><p>　　{ //此處放置前面順序棧的定義</p><p>　　int num=0;</p><p>　　int i,j,k,di

7、,find,minlenth=Maxsize;</p><p>　　top++; //初始化棧</p><p>　　qu[top].i=xi;</p><p>　　qu[top].j=yi;

8、 //取棧頂方塊</p><p>　　qu[top].di=-1; //找到了出口，輸出路徑</p><p>　　mg[1][1]=-1;</p><p>　　printf("迷宮路徑如下：\n");</p

9、><p>　　while(top>-1)//棧不為空時循環(huán)</p><p><b>　　{</b></p><p>　　i=qu[top].i;j=qu[top].j;</p><p>　　di=qu[top].di;</p><p>　　if(i==xe&&j==ye)<

10、/p><p><b>　　{num++;</b></p><p>　　printf("第%d條路徑:\n",num);</p><p>　　for(k=0;k<=top;k++)</p><p><b>　　{</b></p><p>　　path[k]

11、=qu[k];</p><p>　　printf("\t(%d,%d)",qu[k].i,qu[k].j);</p><p>　　if((k+1)%5==0) //每輸出5個方塊后換一行</p><p>　　printf("\n");</p&g

12、t;<p><b>　　}</b></p><p>　　printf("\n\n");</p><p>　　mg[qu[top].i][qu[top].j]=0;</p><p>　　if(top+1<minlenth)</p><p><b>　　{</b>

13、</p><p>　　minlenth=top+1;</p><p>　　for(int c=0;c<=top;c++)</p><p>　　path[k]=qu[k];</p><p><b>　　}</b></p><p><b>　　top--;</b></

14、p><p>　　i=qu[top].i;j=qu[top].j;di=qu[top].di;</p><p><b>　　}</b></p><p><b>　　find=0;</b></p><p>　　while(di<=4&&find==0) //找(i,j)下一

15、可走方塊</p><p><b>　　{</b></p><p>　　di++; //找下一方位</p><p>　　switch(di)</p><p><b>　　{</b></p><p>　　case 0: i=qu[top].i-1

16、; j=qu[top].j;break;</p><p>　　case 1: i=qu[top].i; j=qu[top].j+1;break;</p><p>　　case 2: i=qu[top].i+1; j=qu[top].j;break;</p><p>　　case 3: i=qu[top].i; j=qu[top].j-1;break;<

17、/p><p><b>　　}</b></p><p>　　if(mg[i][j]==0) find=1; //找到下一可走相鄰方塊</p><p><b>　　}</b></p><p>　　if(find==1)

18、 //找到一可走相鄰方塊</p><p><b>　　{</b></p><p>　　qu[top].di=di; //修改原棧頂元素di</p><p>　　top++; //將可走相鄰方塊進棧</p><p&

19、gt;　　qu[top].i=i;qu[top].j=j;qu[top].di=-1;</p><p>　　mg[i][j]=-1; //值制為-1，避免重復走到該方塊</p><p><b>　　}</b></p><p>　　else

20、 //沒有相鄰方塊可走，退出棧</p><p><b>　　{</b></p><p>　　mg[qu[top].i][qu[top].j]=0; //該位置變?yōu)槠渌窂娇勺叻较?lt;/p><p>　　top--; //該方塊退棧<

21、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("路徑條數(shù)：%d\n",num);</p><p>　　printf("\n最短路徑長度為：%d\n",minlenth);</p>&

22、lt;p>　　printf("\n最短路徑為：\n");</p><p>　　for(k=0;k<=minlenth;k++)</p><p><b>　　{</b></p><p>　　printf("\t(%d,%d)",path[k].i,path[k].j);</p>&

23、lt;p>　　if((k+1)%5==0)</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　return(0);

24、 //沒有可走路徑，返回0</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　int mg[

25、M+2][N+2]={</p><p>　　{1,1,1,1,1,1},</p><p>　　{1,0,0,0,1,1},</p><p>　　{1,0,1,0,0,1},</p><p>　　{1,0,0,0,1,1},</p><p>　　{1,1,0,0,0,1}};</p><p>　　

26、printf("迷宮圖如下：\n");</p><p>　　for(i=0;i<=M+1;i++)</p><p><b>　　{</b></p><p>　　printf(" ");</p><p>　　for(j=0;j<=N+1;j++)</p>

27、<p>　　printf("%d ",mg[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　mgpath(1,1,M,N,mg);</p><p><b>　　}</b>&l

28、t;/p><p>　　四、運行示例及結果分析</p><p>　　五、調試和運行程序過程中產生的問題及采取的措施</p><p>　　在調試的過程當中，對于最短路徑和路徑長度這一問題，書上都給出了例子，且在課件和書本的第三章都有一定的解釋，這一問題我們可以依據書本的提示來解決，但若要輸出所有的路徑，我們就得另外進行考慮，全部輸出，就是將內容逐一輸出，沿著這一思路，在參考

29、C語言以及C++的相關內容，得到我們可以用FOR語句來對其進行解決。</p><p>　　六、對課題相關算法的討論、分析，改進設想</p><p>　　本課題在一些問題上可以有多種算法，比如說，在輸出所有路徑這一問題上，我們就可以采用當型循環(huán)來做，但相對于當型循環(huán)，F(xiàn)OR語句循環(huán)比較方便，同時，在迷宮數(shù)組的中，我們也采用其他格式。</p><p><b>

30、　　七、總結</b></p><p>　　本次課題需要我們對問題做進一步的分析，且需要我們參考不同書本以及課外的相關知識，需要我們對其做進一步的融合，且本次課題中的每一步都有不同的問題，這就需要我們應用不同的知識來對其進行解決，總體來說，就是我們要應用不同的知識解決不同的問題，且要對其進行融合，來時不同的問題變成一個問題，不同的知識可以相互結合，來解決一個問題。</p><p>