棧的迷宮求解(數(shù)據(jù)結構試驗)

1、精選優(yōu)質文檔-傾情為你奉上 實驗二：迷宮問題 班級： 姓名： 學號： 一、 需求分析（ 1 ） 以二維數(shù)據(jù)Mazem+2n+2 表示迷宮， 其中： Maze0j 和Mazem+1j（0=j=n+1）及Mazei0和Mazein+1(0=i=m+1)為添加一圈障礙。數(shù)組中以元素值為0 表示通路，1 表示障礙，限定迷宮的大小m,n=0數(shù)據(jù)關系：R1=|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作結果：構造一個空棧S。DestroyStack（&S）初始條件：棧S 已存在。操作結果：銷毀棧S。ClearStack(&S)初始條件：棧S 已存在。操作結果：將 S 清為空棧。St

2、ackLength(&S)初始條件：棧S 已存在。操作結果：返回棧 S 的長度。StackEmpty(&S)初始條件：棧S 已存在。操作結果：若 S 為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S 已存在。操作結果：若棧 S 不空，則以e 返回棧頂元素。Push(&S,e)初始條件：棧S 已存在。操作結果：在棧 S 的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S 已存在。操作結果：刪除 S 的棧頂元素，并以e 返回其值。StackTraverse(S,visit()初始條件：棧S 已存在。操作結果：從棧底到棧頂依次對 S 中的每個元素調用函數(shù)v

3、isit( )。ADT Stack2. 設定迷宮的抽象數(shù)據(jù)類型為：ADT maze數(shù)據(jù)對象：D=ai,j|ai,j 、#、*，0im+1,0jn+1,m,n10數(shù)據(jù)關系：R=ROW，COLROW=|ai-1,j，ai,jD,i=1,，m+1,j=0,，n+1COL=|ai,j-1,ai,jD,i=0,，m+1,j=1,，n+1基本操作：InitMaze(&M,a,row,col)初始條件：二維數(shù)組arow+2col+2已存在，其中自第1 行至第row+1行、每行中自第1 列至第col+1 列的元素已有值，并且以值0表示通路，以值1 表示障礙。操作結果：構成迷宮的字符型數(shù)組，以字符6表示通路，以

4、字符41表示障礙，并在迷宮四周加上一圈障礙。MazePath(&M)初始條件：迷宮M 已被賦值,鏈棧S已經存在。操作結果：若迷宮M 中存在一條通路，則按如下規(guī)定改變迷宮M 的狀態(tài)：以字符“6”表示路徑上的位置，字符“4”表示“死胡同”；否則迷宮的狀態(tài)不變。PrintMaze(M)初始條件：迷宮M 已存在。操作結果：以字符形式輸出迷宮。ADT maze;3. 本程序包含三個模塊1） 主程序模塊：void main( )初始化；do接受命令；處理命令；while(命令！=“退出”)；2） 棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型3） 迷宮模塊實現(xiàn)迷宮抽象數(shù)據(jù)類型各模塊之間的調用關系如下：4. 求解迷宮中一條通路的

5、偽碼算法：設定當前位置的初值為入口位置；do若當前位置可通，則將當前位置插入棧頂； /納入路徑若該位置是出口位置，則結束； /求得路徑存放在棧中否則切換當前位置的東鄰方塊為新的當前位置；否則若棧不空且棧位置尚有其他方向未被探索，則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置； /后退一步，從路徑中刪去該通道塊，主程序模塊迷宮模塊棧模塊若棧不空，則重新測試新的棧頂位置，直到找到一個可通的相鄰塊或出棧至?？眨粀hile(棧不空)；?？照f明沒有路徑存在三、 詳細設計1 坐標位置類型typedef structint r,c; /迷宮中

6、行、列的范圍PosType;2 迷宮類型typedef structint a, b;char arrMN; /各位置取值6 ,4,1或0MazeType;void initmaze(MazeType &maze,int m,int n)/按照用戶輸入的m行和n 列的二維數(shù)組（元素值為0 或1）/設置迷宮的初值，包括加上邊緣一圈的值bool mazepath(MazeType &maze,PosType start,PosType end,SNode *&S)/求解迷宮maze 中，從入口start 到出口end 的一條路徑/若存在，則返回TRUE；否則返回FALSEvoid printmaz

7、e(mazetype maze)/將迷宮以字符型方陣的形式輸出到標準輸出文件上3 棧類型typedef structint step; /當前位置在路徑上的“序號”PosType position; /當前的坐標位置int dir; /往下一坐標位置的方向ElemType; /棧的元素類型struct SNodeElemType data;SNode *next; /結點類型，指針類型棧的基本操作設置如下：void InitStack(Stack &S)/初始化，設S 為空棧（S.top=NULL）并返回TRUE,否則返回FALSEStatus Push(Stack &S,ElemType e

8、)/若分配空間成功，則在S 的棧頂插入新的棧頂元素e，并返回TRUE；/否則棧不變，并返回FALSEStatus Pop(Stack &S,ElemType &e)/若棧不空，則刪除S 的棧頂元素并以e 帶回其值，且返回TRUE/否則返回FALSEvoid print(SNode *S) /輸出棧的內容其中該程序的C+全部代碼如下：#includeusing namespace std;#define n 10#define m 10/迷宮各設置函數(shù)void print(char mazenm)for (int i=0;in;i+)for(int j=0;jm;j+)coutmazeij ;c

9、outendl;void add_maze(char mazenm) int a,b,c; for(a=1;a=(n-2)*(m-2);a+) cout障礙位置為(1=i=n-1;1=j=m-1bc; if(b=0&c=0) cout設置完成endl; break; if(b=0|c=n|c=m) cout輸入錯誤endl; break; mazebc=1; void create_maze( char mazenm)int i=0,j=0;/為迷宮加圍墻for(j=0;jm;j+)maze0j=1;mazen-1j=1;for(i=0;in;i+)mazei0=1;mazeim-1=1; /

10、設圍墻內所有點為通路for(i=1;in-1;i+) for(j=1;jm-1;j+)mazeij=0; print(maze);/輸出造好的迷宮 add_maze(maze);/增加迷宮障礙 coutendl;print(maze);/再次輸出此時造好的迷宮/迷宮棧應用struct Node int i,j;struct StackNode pos;Stack *next;void InitStack(Stack *&S)Stack *p;cout開辟一個新棧next=NULL;S-next=p;couthas created.pos.i=a; p-pos.j=b;p-next=S-next

11、;S-next=p;mazeab=Y;void pop(Stack *&S,char mazenm)/出棧及相關操作if(!S-next) coutthe stack is empty!next-pos.iS-next-pos.j=N; S-next=S-next-next; void Walking(Stack *&S,char mazenm,int i,int j)if(i=n-2 & j=m-2) return; /表示已經到達終點if(mazeij+1!=1 & mazeij+1!=Y & mazeij+1!=N)/向東走，if判斷包括下一個位置是否是墻（1），是否是已經走過的路（Y）

12、（N）j+;push(S,maze,i,j);Walking(S,maze,i,j);return;if(mazei+1j!=1 & mazei+1j!=Y & mazei+1j!=N)/向南走i+;push(S,maze,i,j);Walking(S,maze,i,j);return;if(mazeij-1!=1 & mazeij-1!=Y & mazeij-1!=N)/向西走j-;push(S,maze,i,j);Walking(S,maze,i,j);return;if(mazei-1j!=1 & mazei-1j!=Y & mazei-1j!=N)/向北走i-;push(S,maze,

13、i,j);Walking(S,maze,i,j);return; pop(S,maze);/四個方向都不通，說明該點無法到達終點，實行出棧i=S-next-pos.i;j=S-next-pos.j;Walking(S,maze,i,j);void games(Stack *&S,char mazenm)int i=1,j=1;push(S,maze,i,j);/先把第一個起始點入棧Walking(S,maze,i,j);/遞歸算法if(!S-next)cout該迷宮是死胡同endl;else cout該迷宮可走通next=NULL; InitStack(S); games(S,maze); /

14、為方便DevC+可以看到最后運行的結果，故設此輸入 coutsui; return 0;四、 調試分析1本次作業(yè)比較簡單，只有一個核心算法，即求迷宮的路徑，所以總的調試比較順利，只在調試MazePath 算法時，遇到兩個問題：其一是，起初輸出的迷宮中沒有加上4的記號，后發(fā)現(xiàn)是因為在MarkPrint 函數(shù)中的迷宮參數(shù)丟失“變參”的原因；其二是，由于回退時沒有將curpos 隨之減一，致使棧中路徑上的序號有錯。2棧的元素中的step 域沒有太多用處，可以省略。3StackTraverse 在調試過程中很有用，它可以插入在MazePath 算法中多處，以察看解迷宮過程中走的路徑是否正確，但對最后的

15、執(zhí)行版本沒有用。4本題中三個主要算法：InitMaze,MazePath 和PrintMaze 的時間復雜度均為0（a*b），本題的空間復雜度亦為0（a*b）（棧所占最大空間）5經驗體會：借助DEBUG 調試器和數(shù)據(jù)觀察窗口，可以加快找到程序中疵點。五、 用戶手冊1 本程序的運行環(huán)境為xp,w7 操作系統(tǒng)，執(zhí)行文件為：迷宮問題.exe.2 進入演示程序后，即現(xiàn)實文本方式的用戶界面：主程序Initialization ReadCommand InterpretInitMaze MazePath PrintMazeInitStack Push Pop StackEmpty StackTraverse FootPrint MarkPrint Pass NextPos 3 進入“產生迷宮（maze