迷宮程序設(shè)計

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

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

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

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

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

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

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

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

9、ef struct (int r;int c;PosType;typedef struct(int step;當前位置在路徑上的序號PosType seat; /當前位置的坐標int di;彳主下一坐標的方向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)走過，3表示已經(jīng)知道其不能通過 MazeType;void InitMaze(MazeType &M,int col,int row)/按照用戶的輸入的行數(shù)row和列數(shù)col列的二維數(shù)組(元素值為1或0)設(shè)置迷宮的錯初值，加上邊緣的一圈的值M.Col=col;M.Row=row;int i;/根據(jù)隨機產(chǎn)生

12、數(shù)進行初始化這個二維數(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，即恰好是路或是通道圍墻的標記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)進行二維數(shù)組的標記值來輸出迷宮(或者其通路)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中，當前位置pos不是障礙物0,不是圍墻-1,以前沒有經(jīng)過2且不是不可通 過3 則可以通過，并返回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)過這個位置M.arrpos.rpos.c=2;void MarkPrint(MazeType &M,PosType pos)/在迷宮的pos位置，留下不能通過的標記M.arrpos.rpos.c=3;PosType NextPos(PosType CurPos, int Dir) /根據(jù)不同的方向來進行移動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è)置當前坐標為入口位置；int curstep=1;當前的步數(shù)bool Find=false;是否找到出口ElemType e;doif(Pass(M,curpos)/如果當前位置可以通過(不是障礙物且未曾留下足跡)FootPrint(M,curpos);/在 當前位置標記為 2 e.step=1;e.seat=curpos;e.di=1;/初始化為向東臨位置移動（即向右）Push(S,e)

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

18、step-;/whileif(e.di4)/不能通過則改變方向e.di+;/方向順時針改變一下Push(S,e);curpos = NextPos(e.seat,e.di);/求下一個節(jié)點/if/if/elsewhile(!StackEmpty(S)&!Find);/(!StackEmpty(S)&!Find);/當棧不為空且沒有找到出口return false;/沒有找到出口則返回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