1、實(shí)驗(yàn)報(bào)告：迷宮問題題目：編寫一個(gè)求解迷宮通路的程序一、 需求分析：1) 采用二維數(shù)組mazeMN來表示迷宮，其中：maze0j和mazeM-1j(0jN-1)及mazei0和mazeiN-1(0iM-1)為添加在迷宮外圍的一圈障礙。數(shù)據(jù)元素值0表示通路，1表示障礙。限定迷宮的大小M8，N10.2) 本次實(shí)驗(yàn)直接在主程序中輸入表示迷宮的二維數(shù)組。另外，迷宮的入口和出口位置都將在主程序中直接設(shè)置。3) 實(shí)驗(yàn)中求出的迷宮通路用“-”表示，迷宮的障礙用“#”表示，已走過但未能求出通路的路徑用“”表示。4) 本程序只求出一條成功的通路。5) 本次實(shí)驗(yàn)將直接輸出構(gòu)建迷宮的二維數(shù)組、初始化的二維數(shù)組和求解后

2、的迷宮數(shù)組。二、 概要設(shè)計(jì)：數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義。（1）棧的抽象數(shù)據(jù)類型ADT Stack數(shù)據(jù)對(duì)象：D=ai| aiCharSet,i=1,2n,n=0數(shù)據(jù)關(guān)系：R1=| ai-1, aiD,i=2,n基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長(zhǎng)度。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALS

3、E。GetTop(S，&e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。Push(&S， e)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S，&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse（S，visit（）初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit（）。 ADT Stack （2）迷宮的抽象數(shù)據(jù)類型ADT maze數(shù)據(jù)對(duì)象：D=ai,j| ai,j ,#,*,0=i=m+1,0=j=n+1,m,n=10數(shù)據(jù)關(guān)系：R=ROW,COL基本操作：InitMa

4、ze(&M,a,row,col)初始條件：二維數(shù)組arow+2col+2已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白字符表示通路，以字符#表示障礙，并在迷宮四周加上一圈障礙。MazePath(&M)初始條件：迷宮M已被賦值。操作結(jié)果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài)：以字符*表示路徑上的位置，字符表示“死胡同”，否則迷宮的狀態(tài)不變。PrintMaze（M）初始條件：迷宮M已存在。操作結(jié)果：以字符形式輸出迷宮。 ADT maze三、 詳細(xì)設(shè)計(jì)：1、 程序具體代碼為：

5、/ MazePath.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#include #include #include #include typedef int Status;#define RANGE 20/RANGE為實(shí)際分配的空間行列數(shù)#define M 8/maze數(shù)組的行數(shù) #define N 11/ maze數(shù)組的列數(shù) typedef struct/表達(dá)迷宮元素

6、位置信息的坐標(biāo)int r,c;PosType;typedef struct/m，n為待處理的迷宮的行列數(shù)，RANGE為實(shí)際分配的空間行列數(shù)int m,n;char arrRANGERANGE;MazeType;typedef int directiveType;/東西南北方向用1，2，3，4整數(shù)對(duì)應(yīng)typedef struct/路徑擬用棧來存儲(chǔ)，此處定義棧元素中數(shù)據(jù)域的信息int step;/存儲(chǔ)到達(dá)該點(diǎn)時(shí)經(jīng)歷的步數(shù)PosType seat;/該點(diǎn)位置directiveType di;/從該點(diǎn)位置走向下一位置的方向ElemType;typedef struct NodeType/路徑擬用鏈棧來

7、存儲(chǔ)ElemType data;struct NodeType *next;NodeType,*LinkType;typedef struct/對(duì)鏈棧的頭指針和元素個(gè)數(shù)進(jìn)行封裝LinkType top;int size;Stack;/以上是對(duì)存儲(chǔ)結(jié)構(gòu)逐層進(jìn)行定義void InitStack(Stack &S) /構(gòu)建空鏈棧，不帶頭結(jié)點(diǎn)S.top=NULL; S.size=0; Status MakeNode(LinkType &p,ElemType e) /創(chuàng)建一個(gè)新結(jié)點(diǎn)，以便插入，本函數(shù)可作為鏈?zhǔn)酱鎯?chǔ)創(chuàng)建結(jié)點(diǎn)的通用函數(shù)，可用于鏈表、鏈棧、鏈隊(duì)的插入操作p=(NodeType *)malloc

8、(sizeof(NodeType); if(!p)return FALSE; p-data=e;p-next=NULL; return TRUE; Status Push(Stack &S,ElemType e) /入棧操作，在這里本質(zhì)上是棧頭（鏈表頭）進(jìn)行插入LinkType p; if(MakeNode(p,e) p-next=S.top; S.top=p; S.size+; return TRUE; return FALSE; Status StackEmpty(Stack S) /判斷是否為空棧，這里是通過top指針為NULL來判斷的，本質(zhì)上也可以通過size是否為0來判斷if(S.t

9、op=NULL)return TRUE; return FALSE; Status Pop(Stack &S,ElemType &e) /出棧操作，本質(zhì)上是刪除表頭元素LinkType p;if(StackEmpty(S) return FALSE; else p=S.top;S.top=S.top-next; e=p-data; S.size-; free(p);return TRUE; Status pass(MazeType maze,PosType curpos) /判斷迷宮Maze中，當(dāng)前位置curpos是否是一個(gè)可達(dá)位置int m,n; /注意這里的m，n只是表達(dá)下標(biāo)的臨時(shí)變量，與

10、前面出現(xiàn)的m，n是不一樣的m=curpos.r; n=curpos.c; if(maze.arrmn= )return TRUE; return FALSE; Status Same(PosType curpos,PosType end) /判斷當(dāng)前位置curpos是否已達(dá)出口if(curpos.r=end.r & curpos.c=end.c)return TRUE; return FALSE; void FootPrint(MazeType &maze,PosType curpos) /在迷宮中標(biāo)識(shí)走過的位置，避免在有路可走時(shí)還走回頭路出現(xiàn)死循環(huán)int m,n; m=curpos.r; n

11、=curpos.c; maze.arrmn=-; PosType NextPos(PosType curpos,int di) /通過di的值，確定下一步的位置，下一步位置實(shí)際是當(dāng)前位置的四個(gè)鄰居中的一個(gè)switch(di)case 1:curpos.c+; /向東走break;case 2:curpos.r+; /向南走break;case 3:curpos.c-; /向西走break;case 4:curpos.r-; /向北走 break;return curpos; void MarkPrint(MazeType &maze,PosType p) /對(duì)試探無路可走后回退的位置做特殊標(biāo)識(shí)

12、maze.arrp.rp.c=; void PrintMaze(MazeType ma) /對(duì)迷宮輸出，實(shí)際是對(duì)一個(gè)二維數(shù)組的輸出int i,j;printf(n); for(i=0;ima.m;i+) printf(t);for(j=0;jma.n;j+) printf(%c ,ma.arrij); printf(n); printf(n); void InitMaze(MazeType &maze,int aN,int row,int col) /根據(jù)二維數(shù)組來初始化迷宮，這個(gè)二維數(shù)組可以設(shè)計(jì)為由用戶從鍵盤輸入，解決不同迷宮的問題，但這里用戶接口不是我們考慮的重點(diǎn)/數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)時(shí)往往將輸入

13、的數(shù)據(jù)直接嵌入到程序中，以簡(jiǎn)化輸入節(jié)約時(shí)間/二維數(shù)組名a做參數(shù)時(shí)，需要知道待讀的二維數(shù)組的列數(shù)，因?yàn)镃語言中二維數(shù)組是按行優(yōu)先順序存儲(chǔ)的/控制每行長(zhǎng)度的實(shí)際就是定義列的數(shù)值，所以要明確參數(shù)Nint i,j;maze.m=row;maze.n=col;for(i=0;irow;i+) for(j=0;jcol;j+) if(aij=0)maze.arrij= ; elsemaze.arrij=#; /*int MazePath(MazeType &maze,PosType start,PosType end) /求解迷宮的關(guān)鍵函數(shù)，maze作為引用型變量是因?yàn)橐獙?duì)相關(guān)路徑做一些標(biāo)識(shí)/返回值為路徑

14、的長(zhǎng)度,返回0表示無通路Stack s; int curstep=1; /統(tǒng)計(jì)路徑長(zhǎng)度實(shí)際可不用curstep，棧s中的size分量已有相關(guān)信息，修改一下程序curstep可以用于統(tǒng)計(jì)走過的總步數(shù)int found=0; ElemType e; /以棧元素的形式暫存當(dāng)前位置的相關(guān)信息，以便入棧構(gòu)成路徑PosType curpos=start; /置開始位置為當(dāng)前位置InitStack(s);do /棧不空且未到出口則繼續(xù)循環(huán)if(pass(maze,curpos) /如果curpos位置可達(dá)則先入棧 FootPrint(maze,curpos); /如果可通則標(biāo)記為-，當(dāng)然后邊如發(fā)現(xiàn)是死胡同，

15、則會(huì)重新標(biāo)記為另外的符號(hào)e.step=curstep; e.seat=curpos; e.di=1; Push(s,e); if(Same(curpos,end)found=s.size;else curpos=NextPos(curpos,1); /到新位置時(shí)默認(rèn)先向東走 curstep+; else if(!StackEmpty(s) Pop(s,e); /如果curpos位置不可達(dá)，且棧不空，則把剛?cè)霔５脑貜棾鲎鱿嚓P(guān)判斷while(e.di=4) & !StackEmpty(s) MarkPrint(maze,e.seat); /標(biāo)識(shí)此路不通 Pop(s,e); /回到上一個(gè)位置cur

16、step-; /不減一的話可以用于統(tǒng)計(jì)走過的總步數(shù) if(e.di0)/判斷下一位置是否可走return steps+;/返回抵達(dá)出口時(shí)的步數(shù)elseMarkPrint(maze,start);/輸出迷宮以及路徑return FALSE;elsereturn FALSE;void Print(int mazeN)int i,j;printf(表示迷宮的數(shù)組n);for(i=0;iM;i+)printf(t);for(j=0;jN;j+)printf(%d ,mazeij);printf(n);printf(n);void main()int step=0;int mazeMN=1,1,1,1,

17、1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1;/在程序中直接輸入一個(gè)建立迷宮的數(shù)組MazeType L;PosType start,end;Print(maze);/調(diào)用Print函數(shù)輸出直接輸出已建立的迷宮數(shù)組InitMaze(L,maze,M,N);/調(diào)用InitMaze函數(shù)將二維數(shù)組初始化為迷宮star

18、t.r=1;start.c=1;/設(shè)置迷宮的入口end.r=6;end.c=9;/設(shè)置迷宮的出口printf(由數(shù)組轉(zhuǎn)化出的迷宮);PrintMaze(L);/輸出已轉(zhuǎn)化的迷宮if(step=MazePath(L,start,end)printf(迷宮的路徑，用-表示,路徑長(zhǎng)度為:%d,step);elseprintf(此迷宮沒有通路！);PrintMaze(L);2、 程序調(diào)用關(guān)系為： mainPrint InitMaze PrintMaze MazePathSame FootPrint pass NextPos MarkPrint MazePath四、 調(diào)試分析：1) 本次實(shí)驗(yàn)采用兩種求解迷宮路徑的