數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題

1、<p><b>　　《數(shù)據(jù)結(jié)構(gòu)》</b></p><p><b>　　---課程設(shè)計(jì)報(bào)告</b></p><p>　　題目： </p><p>　　班級(jí)： </p><p>　　學(xué)號(hào)： </p><p>　　姓名：

2、 </p><p>　　同組成員： </p><p>　　指導(dǎo)教師： </p><p><b>　　目錄</b></p><p>　　設(shè)計(jì)題目…………………………………………2</p><p>　　需求分析…………………………………………2<

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

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

5、得到它學(xué)習(xí)走通迷宮的路線(xiàn)。設(shè)計(jì)一個(gè)計(jì)算機(jī)程序?qū)θ我庠O(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。</p><p><b>　　要求程序輸出：</b></p><p>　　（1）一條通路的二元組（i，j）數(shù)據(jù)序列，（i，j）表示通路上某一點(diǎn)的坐標(biāo)。</p><p>　?。?）用一種標(biāo)志（如數(shù)字8）在二維數(shù)組中標(biāo)出該條通路，并在屏幕

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

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

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

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

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

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

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

13、t;<p>　　{//按照用戶(hù)輸入的row行和col列的二維數(shù)組（元素為0或1）</p><p><b>　　int m,n;</b></p><p>　　printf("\n請(qǐng)輸入迷宮數(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ù)輸入結(jié)束.\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)//自動(dòng)生成迷宮</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、迷宮求解模塊設(shè)計(jì)</p><p>　　從迷宮的入口位置按東、東南、南、西南、西、西北、北、東北方向的順序依次進(jìn)行探索，其移動(dòng)的操作為：</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>　　在搜索的過(guò)程中調(diào)用FootPrint(maze,curpos)，MarkPrint(maze,e.seat)判斷所初位置的正確與否，調(diào)用NextPos(e.seat,e.di)搜索當(dāng)前的下一位置。其具體代碼如下所示：&

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;//設(shè)定"當(dāng)前位置"為"入口

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>　　{//當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊留下足跡</p><p>　　FootPrint(maze,curpos);//做可以通過(guò)的標(biāo)記</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;//如果到達(dá)終點(diǎn)返回true</p><p><b>　　else</b></p><p><

30、b>　　{</b></p><p>　　curpos=NextPos(curpos,1);//下一位置是當(dāng)前位置的東鄰</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);//換下個(gè)方向探索</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、;//沒(méi)有找到路徑</p><p><b>　　}</b></p><p><b>　　五、運(yùn)行數(shù)據(jù)及結(jié)果</b></p><p><b>　　主菜單界面：</b></p><p><b>　　圖3 主菜單界面</b></p><p

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

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

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