迷宮程序設(shè)計(jì)

1、（一）設(shè)計(jì)題目：迷宮（二）需求分析：任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷 宮的路徑，并將路徑輸出；要求：在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、 源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；（三）概要設(shè)計(jì)：在迷宮設(shè)計(jì)中，由于不能使用遞歸則可以借助棧來(lái)實(shí)現(xiàn)在迷宮中的前進(jìn)和 后退。同時(shí)在還需要設(shè)計(jì)迷宮的大小、迷宮的出入口、根據(jù)輸入的入口來(lái)尋找迷 宮的出口，并把路徑輸出來(lái)。在這個(gè)編程中由于不知道所走路勁步數(shù)，所以采用了鏈?zhǔn)綏?shí)現(xiàn)每一步的 移動(dòng)，若找到出路則前進(jìn)否則返回下一步改變方向來(lái)實(shí)現(xiàn)相關(guān)的移動(dòng)，所以棧在 其間起到了工具

2、作用。在設(shè)計(jì)迷宮大小和出入口時(shí)，采用的是根據(jù)操作者實(shí)現(xiàn)的，但迷宮的具體 路障和通道是隨機(jī)實(shí)現(xiàn)的。當(dāng)然，重點(diǎn)是如何從出口來(lái)找出口。求迷宮的一條通路的偽碼如下：設(shè)當(dāng)前初始位置為出口：do（若當(dāng)前位置可通，則將該位置插入到棧頂；/納入路徑若該位置為出口位置。則結(jié)束當(dāng)前程序；/求得的路徑放在棧中 否則切換當(dāng)前位置的東臨位置（即向右）為新的當(dāng)前的位置；否則若棧不為空且棧頂元素尚有其他位置未被探索，則設(shè)定新的當(dāng)前位置為 沿著順時(shí)針旋轉(zhuǎn)得到的棧頂位置的下一個(gè)臨快；若棧不為空且棧頂位置的四周均不通（則刪去棧頂元素；后退一步，從路徑中刪去該通塊若棧不空，則重新測(cè)試新的棧頂位置，直到找到一個(gè)可通的相 鄰塊或出棧至

3、?？眨?否則while（棧不為空）本程序的模塊主程序從main （）函數(shù)中進(jìn)行，包括輸入迷宮的大小等信息，然后調(diào)用迷 宮模塊，在迷宮模塊中也調(diào)用了棧的模塊。棧模塊一一實(shí)現(xiàn)棧抽象數(shù)據(jù)類型迷宮模塊一一實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型各模塊之間的關(guān)系如下：主程序模塊迷宮模塊棧模塊（四）詳細(xì)設(shè)計(jì)1.坐標(biāo)的位置類型：typedef struct （int r;int c;PosType;2.迷宮類型：typedef structint Col,Row;/迷宮的大小int arrRangleRangle; /0表示障礙，1表示是可走的通道，-1表示外界的圍墻/2表示已經(jīng)走過(guò)，3表示已經(jīng)知道其不能通過(guò)MazeType;

4、void InitMaze（MazeType &M,int col,int row）按照用戶的輸入的行數(shù)row和列數(shù)col列的二維數(shù)組（元素值為1或0）設(shè)置迷宮的錯(cuò)初值，加上邊緣的一圈的值void PrintMaze(MazeType M)根據(jù)已經(jīng)進(jìn)行二維數(shù)組的標(biāo)記值來(lái)輸出迷宮（或者其通路）bool Pass(MazeType M,PosType pos)/求解迷宮M中，從Start到end的一條路徑/若存在則返回true,否則返回falseStack S;InitStack(S);PosType curpos=start;/設(shè)置當(dāng)前坐標(biāo)為入口位置；int curstep=1;當(dāng)前的步數(shù)boo

5、l Find=false;是否找到出口ElemType e;doif(Pass(M,curpos)/如果當(dāng)前位置可以通過(guò)(不是障礙物且未曾留下足跡)FootPrint(M,curpos);/在 當(dāng)前位置標(biāo)記為 2e.step=1;e.seat=curpos;e.di=1;/初始化為向東臨位置移動(dòng)(即向右)Push(S,e);/將已經(jīng)周的的放入棧中if(curpos.c=end.c&curpos.r=end.r)/如果找到了 出口則終止，并返回 trueFind=true;return Find;else/在其東臨位置上移動(dòng)，當(dāng)前步數(shù)加一curpos=NextPos(curpos,1);curs

6、tep+;else/當(dāng)前位置不能通過(guò)if(!StackEmpty(S)Pop(S,e);/將已經(jīng)走過(guò)的最近位置彈出，數(shù)據(jù)保存在e中while(e.di=4&!(StackEmpty(S)/當(dāng)方向改變一周后仍不能找到可通過(guò)的 路徑MarkPrint(M,e.seat);/留下不能通過(guò)的標(biāo)記Pop(S,e);/刪除站定元素curstep-;/whileif(e.di4)/不能通過(guò)則改變方向e.di+;/方向順時(shí)針改變一下Push(S,e);curpos = NextPos(e.seat,e.di);/求下一個(gè)節(jié)點(diǎn)/if/if/elsewhile(!StackEmpty(S)&!Find);/(!S

7、tackEmpty(S)&!Find);/當(dāng)棧不為空且沒(méi)有找到出口return false;/沒(méi)有找到出口則返回false從入口口到出口的查找的流程圖（五）調(diào)試分析、測(cè)試結(jié)果（1）由于是不確定的步驟，采用的是易于操作的鏈?zhǔn)綏＃@ 樣就不免了時(shí)間和空間的浪費(fèi)。（2）對(duì)于設(shè)計(jì)迷宮，可能會(huì)覺(jué)得會(huì)很繁瑣，剛開(kāi)始也是自己 設(shè)計(jì)迷宮圖，但由于是隨機(jī)設(shè)定迷宮的大小這就需要利用隨機(jī)數(shù) 來(lái)設(shè)計(jì)一個(gè)迷宮圖。而利用運(yùn)算則可以解決這個(gè)問(wèn)題，因?yàn)樵?設(shè)置迷宮數(shù)組時(shí)，1就代表通道，而0就是障礙，隨意一個(gè)隨機(jī) 數(shù)%2得到的就是0或者1就可以自由設(shè)計(jì)迷宮了。（3）來(lái)利用到進(jìn)出棧時(shí)為計(jì)算進(jìn)出棧的情況，特設(shè)定了 curstep來(lái)

8、調(diào)試程序的執(zhí)行。那下面就介紹一下設(shè)計(jì)的迷宮界面情況:C:Users李星運(yùn)阮*叩瞬把結(jié)構(gòu)設(shè)3趴基礎(chǔ)類.|叵1云 音 云云 音 云 迷迷入入圖輸輸莒工繼 否 請(qǐng)請(qǐng)迷米演迷必請(qǐng)請(qǐng)淤演共是!=L 一一歹歹第第口口柴澳米渙第第米吏口 口入出的的宮宮迷迷去續(xù)云入入.泌。0-輸輸 ogI CS CS 是rrr設(shè)計(jì)心得體會(huì)在知識(shí)方面,在設(shè)計(jì)迷宮時(shí)需要用到一些基本的如棧的相關(guān)信 息，來(lái)解決不能使用遞歸的問(wèn)題，遞歸在使用過(guò)程中雖然簡(jiǎn)介但 不易理解通過(guò)棧的使用來(lái)加強(qiáng)我們對(duì)遞歸的使用。在對(duì)問(wèn)題的理解上我們通過(guò)對(duì)相關(guān)知識(shí)的理解和認(rèn)識(shí)，來(lái)解決 一些實(shí)際問(wèn)題。附錄Stack.h#include #include typed

9、ef struct (int r;int c;PosType;typedef struct(int step;當(dāng)前位置在路徑上的序號(hào)PosType seat; /當(dāng)前位置的坐標(biāo)int di;彳主下一坐標(biāo)的方向ElemType;typedef struct NodeType(ElemType data;NodeType *next;*NodeLink;typedef struct(NodeLink top;/指 向棧頂int size;Stack;/棧的基本操作void InitStack(Stack &S)(/初始化棧，設(shè)S為空棧S.size=0;/cout棧初始化成功data=e;p-nex

10、t=S.top;S.top=p;S.size+;return true;bool Pop(Stack &S,ElemType &e)/若棧不空，將棧S的棧頂元素刪除并由e帶回其值，且返回trueNodeType *p=S.top;if(p=NULL)coutdata;S.size-;S.top=p-next;free(p);return true;bool StackTraveser(Stack S)NodeType *p;p=S.top;if(p=NULL)return false;while(!p)coutdata.dinext;return true;主程序#include#includ

11、e #include #include stack.h#include/* 迷宮的相關(guān)信息*/ #define Rangle 100typedef struct(int Col,Row;/int arrRangleRangle; /0表示障礙，1表示是可走的通道，-1表示外界的圍墻/2表示已經(jīng)走過(guò)，3表示已經(jīng)知道其不能通過(guò) MazeType;void InitMaze(MazeType &M,int col,int row)/按照用戶的輸入的行數(shù)row和列數(shù)col列的二維數(shù)組(元素值為1或0)設(shè)置迷宮的錯(cuò)初值，加上邊緣的一圈的值M.Col=col;M.Row=row;int i;/根據(jù)隨機(jī)產(chǎn)生

12、數(shù)進(jìn)行初始化這個(gè)二維數(shù)組for(i=1;iM.Row+2;i+)for(int j=1;jM.Col+2;j+)/srand(time(0);int n=rand()%101+100;M.arrij=n%2;/得到的值是1或者0，即恰好是路或是通道圍墻的標(biāo)記for(i=0;iM.Col+2;i+)M.arr0i=-1;M.arrM.Row+1i=-1;for(i=0;iM.Row+2;i+)M.arri0=-1;M.arriM.Col+1=-1;void PrintMaze(MazeType M)/根據(jù)已經(jīng)進(jìn)行二維數(shù)組的標(biāo)記值來(lái)輸出迷宮(或者其通路)int i,j;for(i = 0; i M

13、.Row+2; i+) for(j = 0; j M.Col+2; j+)if(M.arrij = 0)coutB;礙，在Dos界面上是白色的else if(M.arrij =-1)cout濃”;圍墻else if(M.arrij =2)cout。；elsecout;coutn;bool Pass(MazeType M,PosType pos)/若在迷宮M中，當(dāng)前位置pos不是障礙物0,不是圍墻-1,以前沒(méi)有經(jīng)過(guò)2且不是不可通 過(guò)3 則可以通過(guò)，并返回trueif(M.arrpos.rpos.c!=0&M.arrpos.rpos.c!=-1&M.arrpos.rpos.c!=2&M.arrpo

14、s.rpos.c!=2&M.arrpos.rpos.c!=3)return true;else return false;void FootPrint(MazeType &M,PosType pos)/在迷宮中的pos的位置留下足跡，證明已經(jīng)經(jīng)過(guò)這個(gè)位置M.arrpos.rpos.c=2;void MarkPrint(MazeType &M,PosType pos)/在迷宮的pos位置，留下不能通過(guò)的標(biāo)記M.arrpos.rpos.c=3;PosType NextPos(PosType CurPos, int Dir) /根據(jù)不同的方向來(lái)進(jìn)行移動(dòng)PosType ReturnPos;switch

15、 (Dir) (case 1:/向右ReturnPos.r=CurPos.r;ReturnPos.c=CurPos.c+1;break;case 2:/向下ReturnPos.r=CurPos.r+1;ReturnPos.c=CurPos.c;break;case 3:/向左ReturnPos.r=CurPos.r;ReturnPos.c=CurPos.c-1;break;case 4:/向上ReturnPos.r=CurPos.r-1;ReturnPos.c=CurPos.c;break;return ReturnPos;bool MazePath(MazeType &M,PosType s

16、tart,PosType end)求解迷宮M中，從Start到end的一條路徑/若存在則返回true，否則返回falseStack S;InitStack(S);PosType curpos=start;/設(shè)置當(dāng)前坐標(biāo)為入口位置；int curstep=1;當(dāng)前的步數(shù)bool Find=false;是否找到出口ElemType e;doif(Pass(M,curpos)/如果當(dāng)前位置可以通過(guò)(不是障礙物且未曾留下足跡)FootPrint(M,curpos);/在 當(dāng)前位置標(biāo)記為 2 e.step=1;e.seat=curpos;e.di=1;/初始化為向東臨位置移動(dòng)（即向右）Push(S,e)

17、;/將已經(jīng)周的的放入棧中if(curpos.c=end.c&curpos.r=end.r)/如果找到了 出口則終止，并返回 trueFind=true;return Find;else/在其東臨位置上移動(dòng)，當(dāng)前步數(shù)加一curpos=NextPos(curpos,1);curstep+;else/當(dāng)前位置不能通過(guò)if(!StackEmpty(S)Pop(S,e);/將已經(jīng)走過(guò)的最近位置彈出，數(shù)據(jù)保存在e中while(e.di=4&!(StackEmpty(S)/當(dāng)方向改變一周后仍不能找到可通過(guò)的路徑MarkPrint(M,e.seat);/留下不能通過(guò)的標(biāo)記Pop(S,e);/刪除站定元素cur

18、step-;/whileif(e.di4)/不能通過(guò)則改變方向e.di+;/方向順時(shí)針改變一下Push(S,e);curpos = NextPos(e.seat,e.di);/求下一個(gè)節(jié)點(diǎn)/if/if/elsewhile(!StackEmpty(S)&!Find);/(!StackEmpty(S)&!Find);/當(dāng)棧不為空且沒(méi)有找到出口return false;/沒(méi)有找到出口則返回falsevoid main()MazeType M;int col,row;PosType start,end;loop:coutrow;coutcol;InitMaze(M,col,row);cout”迷宮圖：n;PrintMaze(M);coutstart.rstart.c;coutend.rend.c;if