數(shù)據(jù)結(jié)構(gòu)-迷宮-實驗報告及代碼

1、-. z.一需求分析 本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標記所走過的路徑完畢程序；當迷宮無路徑時，提示輸入錯誤完畢程序。程序執(zhí)行的命令：1創(chuàng)立迷宮 ；2求解迷宮；3輸出迷宮求解；二算法設計本程序中采用的數(shù)據(jù)模型，用到的抽象數(shù)據(jù)類型的定義，程序的主要算法流程及各模塊之間的層次調(diào)用關(guān)系程序根本構(gòu)造：設定棧的抽象數(shù)據(jù)類型定義：ADTStack 數(shù)據(jù)對象：D=|CharSet，i=1,2,3,.,n,n=0;數(shù)據(jù)關(guān)系：R=|，D,i=2,n設置迷宮的抽象類型A

2、DT maze數(shù)據(jù)對象：D=ai|ai，#，1,i=1,2,n,n=0數(shù)據(jù)關(guān)系：R=r,cr=|ai-1,aiD, i=1,2,n,c=|ai-1,aiD, i=1,2,n,構(gòu)造體定義：typedef struct /迷宮中*行y列的位置int *; int y;PosType;typedef struct /棧類型 int ord; /通道塊在路徑上的序號 PosType seat; /通道塊在迷宮中的坐標位置 int di; /從此通道塊走向下一通道塊的方向MazeType;typedef struct MazeType *base; MazeType *top; int stacksiz

3、e;MazeStack;根本函數(shù)：Status InitStack(MazeStack &S)/新建一個棧Status Push(MazeStack &S, MazeType &e)/入棧Status Pop(MazeStack &S, MazeType &e)/出棧Status StackEmpty(MazeStack &S)/判斷是否為空Status MazePath(PosType start, PosType end)/迷宮路徑求解void FootPrint(PosType pos)PosType Ne*tPos(PosType curPos, int &i)void MakePri

4、nt(PosType pos)三程序設計根據(jù)算法設計中給出的有關(guān)數(shù)據(jù)和算法，選定物理構(gòu)造，詳細設計需求分析中所要求的程序。包括：人機界面設計、主要功能的函數(shù)設計、函數(shù)之間調(diào)用關(guān)系描述等。1界面設計1迷宮界面 2迷宮路徑顯示2主要功能入棧操作Status Push(MazeStack &S, MazeType &e) /入棧操作if(S.top - S.base = S.stacksize)S.base = (MazeType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(MazeType);if(!S.base)e*it(O

5、VERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;出棧操作Status Pop(MazeStack &S, MazeType &e)/出棧if(S.top = S.base)return ERROR;e = *-S.top;return OK;判斷棧是否為空Status StackEmpty(MazeStack &S)/判斷是否為空if(S.base = S.top)return OK;return ERROR; 4迷宮路徑求解Status MazePath(Pos

6、Type start, PosType end)/迷宮路徑求解PosType curpos;MazeStack S;MazeType e;int curstep;InitStack(S);curpos = start; /設定當前位置為入口位置curstep = 1; /探索第一步cout 起點: ( start.y , start.* ) endl;doif(Pass(curpos) /當前位置可以通過，即是未曾走到的通道塊FootPrint(curpos); /留下足跡e.ord = curstep;e.seat = curpos;e.di = 1;Push(S, e); /參加路徑if(

7、curpos.* = end.* & curpos.y = end.y)cout n終點 ( e.seat.y , e.seat.* );return TRUE; /到達終點出口curpos = Ne*tPos(curpos, e.di); /下一位置是當前位置的東鄰+curstep; /探索下一步else /當前位置不能通過if(!StackEmpty(S)Pop(S, e);while(e.di = 4 & !StackEmpty(S)MakePrint(e.seat); /留下不能通過的標記Pop(S, e);cout 倒退到( e.seat.y , e.seat.* );if(e.di

8、 4)+e.di; /換下一個方向探索Push(S, e);curpos = Ne*tPos(e.seat, e.di); /設定當前位置是該新方向上的相鄰塊while(!StackEmpty(S);return FALSE;5探索下一個位置PosType Ne*tPos(PosType curPos, int &i)switch(i) /順時針方向case 1:+curPos.*; /東if(mazeMapcurPos.ycurPos.* != 2)break;-curPos.*;case 2:i = 2;+curPos.y; /南if(mazeMapcurPos.ycurPos.* !=

9、2)break;-curPos.y;case 3:i = 3;-curPos.*; /西if(mazeMapcurPos.ycurPos.* != 2)break;+curPos.*;case 4:i = 4;-curPos.y; /北if(mazeMapcurPos.ycurPos.* = 2)+curPos.y;mazeMapcurPos.ycurPos.* = 0;break;return curPos;標記走過的路徑void FootPrint(PosType pos)mazeMappos.ypos.* = 2; /將走過的路徑設為2標記作廢路徑void MakePrint(PosTy

10、pe pos)cout n( pos.y , pos.* )走不通，作廢;mazeMappos.ypos.* = 0; /將走不通的塊替換為墻壁3函數(shù)調(diào)用int main()PosType mazeStart, mazeEnd;mazeStart.* = 1;/開場與完畢點mazeStart.y = 1;mazeEnd.* = 8;mazeEnd.y = 8;cout 迷宮: endl;for(int i = 0; i 10; +i)for(int j = 0; j 10; +j)cout mazeMapij;cout endl;cout endl endl;if(MazePath(mazeS

11、tart, mazeEnd)cout n走通迷宮 endl;elsecout n走不通迷宮 。源程序：#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef struct/迷宮中*行y列的位置int *;int y;PosType;typedef struct/棧類型int ord; /通道塊在路徑上的序號PosType seat; /通道塊在迷

12、宮中的坐標位置int di; /從此通道塊走向下一通道塊的方向, /1:東 2:北 3:西 順時針)MazeType;typedef structMazeType *base;MazeType *top;int stacksize;MazeStack;#include using namespace std;Status InitStack(MazeStack &S);Status Push(MazeStack &S, MazeType &e);Status Pop(MazeStack &S, MazeType &e);Status StackEmpty(MazeStack &S);Statu

13、s MazePath(PosType start, PosType end);Status Pass(PosType &pos);void FootPrint(PosType pos);PosType Ne*tPos(PosType curPos, int &i);void MakePrint(PosType pos);/迷宮地圖，0表示墻壁，1表示通路,入口:mazeMap11,出口mazeMap88int mazeMap1010 = /0,1,2,3,4,5,6,7,8,90,0,0,0,0,0,0,0,0,0, /00,1,1,0,1,1,1,0,1,0, /10,1,1,0,1,1,1

14、,0,1,0, /20,1,1,1,1,0,0,1,1,0, /30,1,0,0,0,1,1,1,1,0, /40,1,1,1,0,1,1,1,1,0, /50,1,0,1,1,1,0,1,1,0, /60,1,0,0,0,1,0,0,1,0, /70,0,1,1,1,1,1,1,1,0, /80,0,0,0,0,0,0,0,0,0 /9;int main()PosType mazeStart, mazeEnd;mazeStart.* = 1;/開場與完畢點mazeStart.y = 1;mazeEnd.* = 8;mazeEnd.y = 8;cout 迷宮: endl;for(int i =

15、 0; i 10; +i)for(int j = 0; j 10; +j)cout mazeMapij;cout endl;cout endl endl;if(MazePath(mazeStart, mazeEnd)cout n走通迷宮 endl;elsecout n走不通迷宮 = S.stacksize)S.base = (MazeType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(MazeType);if(!S.base)e*it(OVERFLOW);S.top = S.base + S.stacksize;S.st

16、acksize += STACKINCREMENT;*S.top+ = e;return OK;Status Pop(MazeStack &S, MazeType &e)/出棧if(S.top = S.base)return ERROR;e = *-S.top;return OK;Status StackEmpty(MazeStack &S)/判斷是否為空if(S.base = S.top)return OK;return ERROR;Status MazePath(PosType start, PosType end)/迷宮路徑求解PosType curpos;MazeStack S;Maz

17、eType e;int curstep;InitStack(S);curpos = start; /設定當前位置為入口位置curstep = 1; /探索第一步cout 起點: ( start.y , start.* ) endl;doif(Pass(curpos) /當前位置可以通過，即是未曾走到的通道塊FootPrint(curpos); /留下足跡e.ord = curstep;e.seat = curpos;e.di = 1;Push(S, e); /參加路徑if(curpos.* = end.* & curpos.y = end.y)cout n終點 ( e.seat.y , e.s

18、eat.* );return TRUE; /到達終點出口curpos = Ne*tPos(curpos, e.di); /下一位置是當前位置的東鄰+curstep; /探索下一步else /當前位置不能通過if(!StackEmpty(S)Pop(S, e);while(e.di = 4 & !StackEmpty(S)MakePrint(e.seat); /留下不能通過的標記Pop(S, e);cout 倒退到( e.seat.y , e.seat.* );if(e.di 4)+e.di; /換下一個方向探索Push(S, e);curpos = Ne*tPos(e.seat, e.di); /設定當前位置是該新方向上的相鄰塊while(!StackEmpty(S);return FALSE;Status Pass(PosType &pos)if(