數(shù)據(jù)結構課程設計---迷宮問題

1、<p><b>　　《數(shù)據(jù)結構》</b></p><p><b>　　---課程設計報告</b></p><p>　　題目： </p><p>　　班級： </p><p>　　學號： </p><p>　　姓名：

2、 </p><p>　　同組成員： </p><p>　　指導教師： </p><p><b>　　目錄</b></p><p>　　設計題目…………………………………………2</p><p>　　需求分析…………………………………………2<

3、/p><p>　　概要設計…………………………………………2</p><p>　　詳細設計…………………………………………2</p><p>　　運行數(shù)據(jù)及結果…………………………………5</p><p><b>　　一、設計題目</b></p><p><b>　　迷宮問題</b&g

4、t;</p><p><b>　　二、需求分析</b></p><p>　　迷宮實驗是取自心理學的一個古典的實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒中設置了許多墻，對行進方向形成了多處阻攔。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗，一直到老鼠從入口到出口，而不走錯一步。老鼠經(jīng)多次試驗終于

5、得到它學習走通迷宮的路線。設計一個計算機程序對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。</p><p><b>　　要求程序輸出：</b></p><p>　?。?）一條通路的二元組（i，j）數(shù)據(jù)序列，（i，j）表示通路上某一點的坐標。</p><p>　　（2）用一種標志（如數(shù)字8）在二維數(shù)組中標出該條通路，并在屏幕

6、上輸出二維數(shù)組。</p><p><b>　　三、概要設計</b></p><p><b>　　1.功能模塊設計</b></p><p>　　該程序的主要模塊有：初始化棧模塊、迷宮建立模塊、迷宮求解模塊</p><p>　　初始化棧模塊，由InitStack(Stack &S)，Push(S

7、tack &S,ElemType e)，Pop(Stack &S,ElemType &e)，StackEmpty(Stack &S)函數(shù)構成</p><p>　　迷宮建立模塊;由InitMaze1(maze,a,row,col)，InitMaze2(maze,a,row,col)函數(shù)構成，此模塊用于產(chǎn)生迷宮</p><p>　　迷宮求解模塊，由MazePat

8、h(maze,start,end)，NextPos(e.seat,e.di)函數(shù)構成，此模塊是基于棧的特點與迷宮實際結合來實現(xiàn)的。</p><p><b>　　2.算法設計</b></p><p>　　走迷宮的過程可以模擬為一個搜索的過程：每到一處總讓它按東、東南、南、西南、西、西北、北、東北8個方向順序試探下一個位置；如果可以通過并不曾到達，則前進一步，在新的位置上

9、繼續(xù)進行搜索；如果8個方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置繼續(xù)試探下一個位置。每前進或后退一步，都要進行判斷：若前進到出口處，則說明找到一條通路，并打印路徑；若退回到路口處，則說明不存在通路。</p><p>　　用一個字符型的二維數(shù)組表示迷宮，數(shù)組中的每個元素取值“0”（表示通路）或“1”（表示墻壁），并且將0記錄為“ ”，1記錄為“#”； 迷宮的產(chǎn)生可由用戶決定：1.自動生成2.手動輸入。迷宮生

10、產(chǎn)后，入口與出口由用戶自己輸入。設計一個模擬走迷宮的算法，為其尋找一條從入口到出口的通入。</p><p>　　從迷宮的入口位置開始沿圖示方向順序依次進行搜索。搜索過程中，每前進一步，在當前位置處做標記“*”（表示這個位置在通路上），并將該位置的壓入棧中。每后退的時候，將該位置標記為“@”，表示該路不通， 并將元素從棧中彈出。</p><p>　　搜索到出口位置時，數(shù)組中那些

11、值為“*”的元素形成一條通路。 圖1 位置方向圖</p><p><b>　　四、詳細設計</b></p><p>　　1、迷宮建立模塊設計</p><p>　　此模塊主要由InitMaze1(maze,a,row,col)，InitMaze2(maze,a,row,col)函數(shù)構成，其中InitMaze1(maze,a,row,c

12、ol)用于用戶自己建立迷宮，InitMaze2(maze,a,row,col)是利用庫函數(shù)中的隨機函數(shù)來建立迷宮，迷宮是通過矩陣形式表現(xiàn)的，用1、0分別表示墻和通路，并用二維數(shù)組存儲，從而將實際問題轉化為數(shù)學模型，方便程序的設計。</p><p>　　void InitMaze1(MazeType &maze,int a[100][100],int row,int col)//手動生成迷宮</p&g

13、t;<p>　　{//按照用戶輸入的row行和col列的二維數(shù)組（元素為0或1）</p><p><b>　　int m,n;</b></p><p>　　printf("\n請輸入迷宮數(shù)據(jù)，1為障礙，0為通路\n");</p><p>　　for(m=1;m<=row;m++)</p>&

14、lt;p>　　for(n=1;n<=col;n++)</p><p>　　scanf("%d",&a[m][n]);</p><p>　　printf("數(shù)據(jù)輸入結束.\n");</p><p>　　for(m=1;m<=row;m++)</p><p>　　for(n=1;n

15、<=col;n++)</p><p><b>　　{</b></p><p>　　if(a[m][n]==1)</p><p>　　maze.arr[m][n]='#';</p><p><b>　　else </b></p><p>　　maze.ar

16、r[m][n]=' ';</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void InitMaze2(MazeType &maze,int a[100][100],int row,int col)//自動生成迷宮</p><p

17、><b>　　{</b></p><p><b>　　int m,n;</b></p><p>　　printf("\n迷宮生成中……\n\n");</p><p>　　system("pause");</p><p>　　printf("\n

18、");</p><p>　　for(m=1;m<=row;m++)</p><p><b>　　{</b></p><p>　　for(n=1;n<=col;n++)</p><p><b>　　{</b></p><p>　　a[m][n]=rand

19、()%2;</p><p>　　printf("%d ",a[m][n]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　for(m

20、=1;m<=row;m++)</p><p>　　for(n=1;n<=col;n++)</p><p><b>　　{</b></p><p>　　if(a[m][n]==1)</p><p>　　maze.arr[m][n]='#';</p><p><b&g

21、t;　　else </b></p><p>　　maze.arr[m][n]=' ';</p><p><b>　　}</b></p><p>　　} 圖2迷宮建立功能模塊圖</p><p

22、>　　2、迷宮求解模塊設計</p><p>　　從迷宮的入口位置按東、東南、南、西南、西、西北、北、東北方向的順序依次進行探索，其移動的操作為：</p><p>　　東移：curpos.c=curpos.c+1; curpos.r=curpos.r; 東南：curpos.c=curpos.c+1; curpos.r=curpos.r+1; </p><p>　

23、　南移：curpos.r=curpos.r+1; curpos.c=curpos.c; 西南：curpos.c=curpos.c-1; curpos.r=curpos.r+1;</p><p>　　西移：curpos.c=curpos.c-1;curpos.r=curpos.r; 西北：curpos.c=curpos.c-1; curpos.r=curpos.r-1;</p><p>　

24、　北移：curpos.r=curpos.r-1; curpos.c=curpos.c; 東北：curpos.c=curpos.c+1;curpos.r=curpos.r-1;</p><p>　　在搜索的過程中調(diào)用FootPrint(maze,curpos)，MarkPrint(maze,e.seat)判斷所初位置的正確與否，調(diào)用NextPos(e.seat,e.di)搜索當前的下一位置。其具體代碼如下所示：&

25、lt;/p><p>　　bool MazePath(MazeType &maze,PosType start,PosType end)</p><p>　　{//求解迷宮maze中，從入口start到出口end的一條路徑，</p><p>　　//若存在則返回TRUE,否則返回FALSE</p><p>　　PosType curpos;

26、</p><p>　　int curstep;</p><p><b>　　Stack S;</b></p><p>　　ElemType e;</p><p>　　InitStack(S);</p><p>　　curpos=start;//設定"當前位置"為"入口

27、位置"</p><p>　　curstep=1; //探索第一步</p><p>　　bool found=false;</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　if(Pass(maze,curpos))

28、</p><p>　　{//當前位置可以通過，即是未曾走到過的通道塊留下足跡</p><p>　　FootPrint(maze,curpos);//做可以通過的標記</p><p>　　e.step=curstep;</p><p>　　e.seat=curpos;</p><p>　　e.di=1;//為棧頂元素賦值

29、</p><p>　　if(Push(S,e)!=1) return ERROR; </p><p>　　if(curpos.r==end.r && curpos.c==end.c) found=true;//如果到達終點返回true</p><p><b>　　else</b></p><p><

30、b>　　{</b></p><p>　　curpos=NextPos(curpos,1);//下一位置是當前位置的東鄰</p><p>　　curstep++;//探索下一步</p><p><b>　　}//else</b></p><p><b>　　}//if</b><

31、/p><p>　　else if(StackEmpty(S)!=true)</p><p><b>　　{</b></p><p><b>　　Pop(S,e);</b></p><p>　　while(e.di==8 && !StackEmpty(S))</p><

32、p><b>　　{</b></p><p>　　MarkPrint(maze,e.seat);</p><p><b>　　Pop(S,e);</b></p><p>　　curstep--;</p><p><b>　　}//while</b></p>&

33、lt;p>　　if(e.di<8)</p><p><b>　　{</b></p><p><b>　　e.di++;</b></p><p>　　Push(S,e);//換下個方向探索</p><p>　　curpos=NextPos(e.seat,e.di);</p>

34、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　}while(!StackEmpty(S)&& !found );</p><p>　　if(!StackEmpty(S)){</p><p>　　printf("\n迷宮

35、路徑：(迷宮出口)<==");</p><p>　　while(!StackEmpty(S))</p><p><b>　　{</b></p><p>　　LinkType p;</p><p><b>　　p=S.top;</b></p><p>　　S.t

36、op=S.top->next;;</p><p>　　e=p->data;</p><p>　　printf("(%d,%d)<==",e.seat.r,e.seat.c);</p><p><b>　　S.size--;</b></p><p><b>　　}</b

37、></p><p>　　printf("迷宮入口");}</p><p><b>　　if(found)</b></p><p>　　return true;</p><p><b>　　else</b></p><p>　　return false

38、;//沒有找到路徑</p><p><b>　　}</b></p><p><b>　　五、運行數(shù)據(jù)及結果</b></p><p><b>　　主菜單界面：</b></p><p><b>　　圖3 主菜單界面</b></p><p

39、>　　進入主菜單界面，根據(jù)提示按任意鍵開始進入迷宮路徑求解系統(tǒng)，或者選擇退出系統(tǒng)</p><p><b>　　生成迷宮界面：</b></p><p>　　圖4（a）迷宮生成界面</p><p>　　該圖為用戶按“1”選擇手動生成迷宮界面，根據(jù)系統(tǒng)所給提示輸入迷宮的行列數(shù)，后輸入迷宮數(shù)據(jù)，系統(tǒng)根據(jù)用戶輸入數(shù)據(jù)顯示迷宮。</p>

40、<p>　　圖4（b）迷宮生成界面</p><p>　　該圖為用戶按鈕“2”選擇系統(tǒng)自動生成迷宮界面，根據(jù)系統(tǒng)所給提示輸入迷宮的行列數(shù)，系統(tǒng)自動顯示迷宮的矩陣形式，及圖畫形式。</p><p><b>　　求解路徑界面：</b></p><p>　　圖5（a）路徑求解界面</p><p>　　圖5（b）路徑求

41、解界面</p><p>　　根據(jù)系統(tǒng)所給提示輸入迷宮的入口及出口位置，輸入完畢，若有通路，顯示迷宮通路路徑;若不存在通路，則提示沒有通路。</p><p><b>　　顯示迷宮界面：</b></p><p><b>　　圖6迷宮顯示界面</b></p><p>　　選擇“3”功能鍵，系統(tǒng)將路徑求解中