(完整word版)迷宮(C語(yǔ)言版)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、一迷宮問(wèn)題求解1. 問(wèn)題描述迷宮問(wèn)題是實(shí)驗(yàn)心理學(xué)的一個(gè)經(jīng)典問(wèn)題，心理學(xué)家把一只老鼠從一個(gè)無(wú)頂蓋的大盒子的入口出趕迷宮。 迷宮中設(shè)置了很多隔壁， 對(duì)前進(jìn)方向形成了多出障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪， 吸引老鼠在迷宮中尋找路徑以到達(dá)出口。然而，用計(jì)機(jī)模擬迷宮問(wèn)題，即劃好迷宮的隔壁的設(shè)置，讓計(jì)算機(jī)從入口處進(jìn)入迷宮探究出一條通路。2. 設(shè)計(jì)思路回溯法是一種不斷試探且及時(shí)糾正錯(cuò)誤的探索方法。下面的求解過(guò)程既是使用回溯法。從入口出發(fā)，按某一個(gè)方向向前探索，若能走通并且未走過(guò)，即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一個(gè)方向；若所有的方向均沒(méi)有通路，則沿原路返回前一個(gè)點(diǎn)， 換下一個(gè)方向繼續(xù)探索

2、， 直到找到一條通路， 或無(wú)路可走又返回到入口點(diǎn)。在求解過(guò)程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無(wú)路）時(shí)，能正確返回前一個(gè)點(diǎn)以便繼續(xù)從下一個(gè)方向向前試探， 則需要用一個(gè)棧保存所有到達(dá)點(diǎn)的下標(biāo)。另外，求解該問(wèn)題的一個(gè)重要問(wèn)題是如何防止回溯時(shí)走重復(fù)節(jié)點(diǎn)，以避免發(fā)生死循環(huán)。這里，我們采用對(duì)走過(guò)的結(jié)點(diǎn)，修改其結(jié)點(diǎn)信息。如在設(shè)計(jì)之初，我們?cè)O(shè)置保存迷宮結(jié)構(gòu)的二維數(shù)組中0 值代表該節(jié)點(diǎn)可走， 1 值代表其不可走，那么我們可以把走過(guò)的結(jié)點(diǎn)值改為非0，已使其不能被再次探索。3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)由上面的設(shè)計(jì)思路知，若想正確的使用回溯法求解迷宮問(wèn)題，必須要借助一個(gè)棧以保存走過(guò)的結(jié)點(diǎn)信息。 而這里我活用了棧， 只把

3、其數(shù)據(jù)結(jié)構(gòu)抽象為了一個(gè)結(jié)構(gòu)體數(shù)組，具體設(shè)計(jì)如下：typedef structint x,y;/*記錄迷宮結(jié)點(diǎn)的位置信息*/pos;pos Pos100; /*結(jié)構(gòu)體數(shù)組以保存走過(guò)的結(jié)點(diǎn)信息*/4功能函數(shù)介紹（ 1）判斷是否找到出口函數(shù)Isover （）；該函數(shù)的參數(shù)是當(dāng)前結(jié)點(diǎn)的 x、y 坐標(biāo)與出口結(jié)點(diǎn)的 x、y 坐標(biāo)，通過(guò)比較其值來(lái)判斷是否找到出口結(jié)點(diǎn)，從而控制程序結(jié)束。（ 2）對(duì)程序相關(guān)信息的簡(jiǎn)單介紹函數(shù) introduce() ；該函數(shù)主要是在進(jìn)行繪制迷宮的圖形化界面之前開發(fā)者搞的一點(diǎn)小插曲，以介紹跟該程序的相關(guān)的部分信息。（ 3）用回溯法探究迷宮出口函數(shù) mazepath（）；該函數(shù)即是

4、利用回溯法探究迷宮問(wèn)題。函數(shù)從接受的起點(diǎn)出發(fā)，逐個(gè)向其可走方向進(jìn)行探究，并同時(shí)把其所走過(guò)的結(jié)點(diǎn)的結(jié)點(diǎn)信息值改為迷宮現(xiàn)有探索結(jié)點(diǎn)中為有效的個(gè)數(shù)，以避免走重復(fù)結(jié)點(diǎn)。同時(shí)該函數(shù)在探索一條有入口到出口的路徑的同時(shí)，加入了一些圖像處理函數(shù)，把迷宮的探索的過(guò)程動(dòng)態(tài)的顯示出來(lái)，個(gè)人對(duì)迷宮探索的思路已較為直觀的感覺。(4)主函數(shù) main()該函數(shù)中處理了圖形設(shè)備的初始化及迷宮結(jié)構(gòu)的初始化工作， 同時(shí)在調(diào)用上述功能函數(shù)完成迷宮探索路徑問(wèn)題的同時(shí)， 加入了探索完成后的一些圖形界面的顯示內(nèi)容。5. 編碼實(shí)現(xiàn)#include#include#include#include#include#include#defin

5、e MaxSize 8#define StartPx 170#define StartPy 150typedef structint x,y;pos;pos Pos100;int Isover(int s_x,int s_y,int e_x,int e_y) /* 判斷是否找到出口 */if(s_x=e_x&s_y=e_y)return 1;else return 0;void mazepath(int m_mazeArrayMaxSize,int s_x,int s_y,int e_x,int e_y)int count=0,sum=0;int str80;m_mazeArrays_ys_x

6、=-1;Poscount.x=s_x;Poscount.y=s_y;while(!Isover(s_x,s_y,e_x,e_y)if(m_mazeArrays_ys_x+1=0)sum+;m_mazeArrays_y+s_x=+count;setcolor(GREEN);circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10);setfillstyle(1,YELLOW);floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN);sleep(1);Poscount.x=s_x;Poscount.y=s_y;el

7、se if(m_mazeArrays_y-1s_x=0)sum+;m_mazeArray-s_ys_x=+count;setcolor(GREEN);circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10);setfillstyle(1,YELLOW);floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN);sleep(1);Poscount.x=s_x;Poscount.y=s_y;else if(m_mazeArrays_ys_x-1=0)sum+;m_mazeArrays_y-s_x=+count;se

8、tcolor(GREEN);circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10);setfillstyle(1,YELLOW);floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN);sleep(1);Poscount.x=s_x;Poscount.y=s_y;else if(m_mazeArrays_y+1s_x=0)sum+;m_mazeArray+s_ys_x=+count;setcolor(GREEN);circle(s_x*30+StartPx+15,s_y*30+StartPy+15,10);

9、setfillstyle(1,YELLOW);floodfill(s_x*30+StartPx+15,s_y*30+StartPy+15,GREEN);sleep(1);Poscount.x=s_x;Poscount.y=s_y;elsem_mazeArrays_ys_x=-1;sum+;count-;setcolor(BLUE);rectangle(s_x*30+StartPx,s_y*30+StartPy,s_x*30+StartPx+30,s_y*30+Star tPy+30);setfillstyle(1,GREEN);floodfill(s_x*30+StartPx+10,s_y*3

10、0+StartPy+10,BLUE); sleep(1);if(count=-1)sum-;break;s_x=Poscount.x;s_y=Poscount.y;if(count!=-1)settextstyle(1,0,1);outtextxy(170,400,you win!n);sprintf(str,It walk %d steps totally!n,count);outtextxy(180,430,str);elsesettextstyle(1,0,1);outtextxy(170,400,Thereisnowayforittoreachtheend!nn);int main()

11、int gdriver, gmode;int x,y;int m_mazeMaxSizeMaxSize;int triangle8;char str2;detectgraph(&gdriver, &gmode);/*自動(dòng)測(cè)試硬件 */initgraph(&gdriver, &gmode, c:Win-Tcprojects);setbkcolor(BLACK);setcolor(RED);settextstyle(0,0,3);outtextxy(160,50,Problem:Maze);srand( time( NULL ) );setcolor(WHITE);for( x = 0; x Ma

12、xSize; x+ )m_maze0x = 1;m_mazeMaxSize-1x = 1;for( x = 0; x MaxSize; x+ )m_mazex0 = 1;m_mazexMaxSize-1 = 1;for ( y = 1; y MaxSize-1; y+ )for ( x = 1; x 1 ? 1 : 0 );/*為數(shù)組隨機(jī)附值 */m_maze11=0;m_mazeMaxSize-2MaxSize-2=0; /*指定迷宮出口 */for ( y = 0; y MaxSize; y+ )for ( x = 0; x MaxSize; x+ )if(m_mazeyx=1)recta

13、ngle(x*30+StartPx,y*30+StartPy,x*30+StartPx+30,y*30+StartPy+30);line(x*30+StartPx,y*30+StartPy,x*30+StartPx+30,y*30+StartPy+30);line(x*30+StartPx+30,y*30+StartPy,x*30+StartPx,y*30+StartPy+30);sleep(1);x=y=1;setcolor(GREEN);circle(x*30+StartPx+15,y*30+StartPy+15,10);setfillstyle(1,YELLOW);floodfill(x

14、*30+StartPx+15,y*30+StartPy+15,GREEN); sleep(1);line(x*30+StartPx+15,y*30+StartPy,x*30+StartPx+15,y*30+StartPy-50);line(x*30+StartPx+15,y*30+StartPy-50,x*30+StartPx+5,y*30+StartPy-40);line(x*30+StartPx+15,y*30+StartPy-50,x*30+StartPx+25,y*30+StartPy-40);settextstyle(1,0,0);outtextxy(x*30+StartPx,y*3

15、0+StartPy-50,StartPoint);x=y=MaxSize-2;setcolor(RED);triangle0=x*30+StartPx+10;triangle1=y*30+StartPy;triangle2=x*30+StartPx+20;triangle3=y*30+StartPy+10;triangle4=x*30+StartPx+10;triangle5=y*30+StartPy+20;triangle6=x*30+StartPx+10;triangle7=y*30+StartPy;drawpoly(4,triangle);setfillstyle(1,RED);floo

16、dfill(x*30+StartPx+15,y*30+StartPy+6,RED);/*line(x*30+StartPx+10,y*30+StartPy,x*30+StartPx+20,y*30+StartPy+10);line(x*30+StartPx+20,y*30+StartPy+10,x*30+StartPx+10,y*30+StartPy+20);*/line(x*30+StartPx+10,y*30+StartPy+20,x*30+StartPx+10,y*30+StartPy+30);sleep(1);line(x*30+StartPx+30,y*30+StartPy+15,x

17、*30+StartPx+30+50,y*30+StartPy+ 15);line(x*30+StartPx+30+50,y*30+StartPy+15,x*30+StartPx+30+50-10,y*30+St artPy+15-10);line(x*30+StartPx+30+50,y*30+StartPy+15,x*30+StartPx+30+50-10,y*30+St artPy+15+10);settextstyle(1,1,0);outtextxy(x*30+StartPx+30+50,y*30+StartPy,EndPoint);mazepath(m_maze,1,1,MaxSize-2,MaxSize-2);getch();closegraph();return 0;6. 測(cè)試與運(yùn)行截圖程序中對(duì)迷宮的結(jié)構(gòu)以及其起點(diǎn)、終點(diǎn)都已經(jīng)指定，故程序運(yùn)行開始后，不需要用戶進(jìn)行相關(guān)操作， 只需要觀看迷宮的探索過(guò)程即可。 探索過(guò)程會(huì)有圖像顯示，給人關(guān)于探索問(wèn)題的直觀反映。程序運(yùn)行的部分截圖如下：7. 問(wèn)題分析與總結(jié)迷宮問(wèn)題相對(duì)圖的遍歷的其他問(wèn)