1、實用標準文案©*#?建大*世仁埠茂CwnflyvyCdAgifl, MjiUqrrml>!Df FMi arMf tolinrmviwQftcm數據結構與算法設計迷宮問題實驗報告實驗二專業：物聯網工程班級：物聯網1班學號：15180118姓名：劉沛航實驗目的本程序是利用非遞歸的方法求出一條走出迷宮的路徑，弁將路徑輸出。首先由用戶輸入一組二維數組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以 0和1所組成 的迷宮形式輸出，標記所走過的路徑結束程序；當迷宮無路徑時， 提示輸入錯誤結束程序。二、實驗內容用一個m*m長方陣表示迷宮，0和1分別表示迷宮中的通路和 障礙。設

2、計一個程序對于任意設定的迷宮， 求出一條從入口到出口的 通路，或得出沒有通路的結論。三、程序設計1、概要設計(1)設定棧的抽象數據類型定義ADT Stack 數據對象：D=ai|ai 屬于 CharSet, i=1、2n, n>=0數據關系：R=<ai-1,ai>|ai-1,ai 屬于 D , i=2,3，n 基本操作：InitStack(&S)操作結果：構造一個空棧Push (&S , e)初始條件：棧已經存在操作結果：將e所指向的數據加入到棧 s中Pop (&S,&e )初始條件：棧已經存在操作結果：若棧不為空，用 e返回棧頂元素，并刪除棧

3、頂元素Getpop ( &S , &e)初始條件：棧已經存在操作結果：若棧不為空，用 e返回棧頂元StackEmpty(&S)初始條件：棧已經存在操作結果：判斷棧是否為空。若棧為空，返回 1,否則返回0Destroy(&S)初始條件：棧已經存在操作結果：銷毀棧s ADT Stack(2)設定迷宮的抽象數據類型定義ADT yanshu 數據對象：D=ai,j|ai,j 屬于 '、 '*'、 '、 ' #' ,0<=i<=M,0<=j<=N數據關系：R=ROW,COLROW=<ai-1,j

4、 ,ai,j>|ai-1,j ,ai,j 屬于 D, i=1,2,M,j=0,1，NCOL=<ai,j-1 ,ai,j>|ai,j-1 ,ai,j 屬于 D,i=0,1，M, j=1,2,N基本操作：InitMaze(MazeType &maze, int aCOL, int row, int col)初始條件：二維數組int a口COL,已經存在，其中第1至第 m-1行，每行自第1到第n-1列的元素已經值，并以值0表示障 礙，值1表示通路。操作結果：構造迷宮的整形數組，以空白表示通路，字符0'表示障礙在迷宮四周加上一圈障礙MazePath (&maz

5、e) 初始條件：迷宮maze已被賦值操作結果：若迷宮maze中存在一條通路，則按如下規定改 變maze的狀態；以字符*'表示路徑上的位置。字符''表示 死胡同；否則迷宮的狀態不變)PrintMaze (M ) 初始條件：迷宮M已存在操作結果：以字符形式輸出迷宮)ADTmaze(3)本程序包括三個模塊a、主程序模塊 void main () 初始化； 構造迷宮； 迷宮求解； 迷宮輸出；b、棧模塊一一實現棧的抽象數據類型c、迷宮模塊一一實現迷宮的抽象數據類型2、詳細設計(1)坐標位置類型：typedef structintrow; /迷宮中的行 int col; /的列Po

6、sType;坐標(2)迷宮類型：typedef structint m,n;int arrRANGERANGE;MazeType;/迷宮類型void/設置迷宮的初值，包括邊緣一圈的值Bool MazePath(MazeType &maze,PosType start, PosType end)求解迷宮 maze中，從入口 start到出口 end的一條路徑/若存在，則返回true ,否則返回falseVoid PrintMaze ( MazeType maze )/將迷宮打印出來(3)棧類型：typedef structint step; /當前位置在路徑上的"序號"

7、;PosType seat; 當前的坐標位置DirectiveType di; /往下一個坐標位置的方向SElemType;棧的元素類型typedef structSElemType *base;SElemType *top;int stacksize;SqStack;棧的基本操作設置如下：Void InitStack (SqStack & S)初始化，設 S為空棧(S.top=NUL )Void DestroyStack(Stack &S)銷毀棧S,并釋放空間Void ClearStack (SqStack & S)/將棧S清空Int StackLength (SqS

8、tack &S)/返回棧S的長度Status StackEmpty (SqStack &S )?、若S為空棧(S.top=NULL ),則返回TRUE,否則返回 FALSEStatue GetTop (SqStack &S , SElemType e)/r若棧S不空，則以e待會棧頂元素并返回TRUE,否則返回FALSEStatue Pop(SqStack&S, SElemType e)/若分配空間成功，則在 S的棧頂插入新的棧頂元素s并返回TRUE否則棧不變，并返回FALSEStatue Push(SqStack&S, SElemType &e)

9、/若分配空間程控，則刪除棧頂并以e帶回其值，則返回 TRUE否則返回FALSEVoid StackTraverse (SqStack &S , Status) ( *Visit) (SElemType e)/從棧頂依次對S中的每個節點調用函數Visit4求迷宮路徑的偽碼算法：Status MazePath(MazeType &maze,PosType start, PosType end)/球解迷宮 maze 中，從入 口 start 到出口 end的一條路徑InitStack(s);PosType curpos = start;int curstep = 1;/ 探索第一部d

10、oif( Pass(maze,curpos) ) /如果當前位置可以通過，即是未曾走到的通道塊FootPrint(maze,curpos); / 留下足跡e = CreateSElem(curstep,curpos,1); 創建元素Push(s,e);if( PosEquare(curpos,end) ) return TRUE;curpos =NextPos(curpos,1); /獲得下一節點：當前位置的東鄰curstep+;/ 探索下一步else/當前位置不能通過if(!StackEmpty(s)Pop(s,e);while(e.di=4 && !StackEmpty(s

11、) )MarkPrint(maze,e.seat); Pop(s,e); /留下不能通過的標記，并退回步if(e.di<4)e.di+; Push(s,e);/ 換一個方向探索curpos = NextPos(e.seat,e.di); 設定當前位置是該方向上的相塊/if/ifelsewhile(!StackEmpty(s);return FALSE;/MazePath四、程序調試分析1 .首先呢，想自己讀入數據的，回來發現那樣，很麻煩，所以還 是事先定義一個迷宮。2 .棧的元素類型一開始有點迷惑，后來就解決了3 .本題中三個主要算法；InitMaze, MazePath和PrintMa

12、ze的時 間復雜度均為O (m*n)本題的空間復雜度也是 O (m*n) 五、用戶使用說明1.本程序運行在windows系列的操作系統下，執行文件為:Maze_Test.exe)六、程序運行結果文檔大全1.建立迷宮:2.通過1功能建立8*8的迷宮后，通過2功能繼續建立迷宮內部： WUSERKPEKAHV 口- X2g*3=t；m；MeR*JaM*何雇用閉 口 51W01口潸ji*i£*iXiC*也口*Qot*1請輸入迷宮的行黜列數 百音箱人逆育口堵中礴 於官結溝如二 礴人迷宮的起點和終點 播史轉果 送出情選悻2適輔入讓日內堵堂無救；10話儕找希人達5四地旺里元的行魏,列蠹；三棺展開;

13、2 34 55 26 47 68 6M 79 510 311 5建拓拼音場人法全：通過建立自己設定單元數目建立迷宮內墻。3 .通過3功能觀察已建立的迷宮結構：4 .通過4功能確立迷宮起點和終點：（此處像我們隨機選擇4,4和2,7分別為起點終點）1C:U5tR5FEKAHBESKTCi 叫新建交件夫XPebuflWazr j«oe”*力士* *XCJ1;* 物 R 壬網 L珈-15 1 gg 11 沛航率 3CXA4* KX*XC* jQC*i二宦新區在百的行就列效 2請輸入正有內向年廠扣 我酹懶嚇 碗A迷宮的底點和終點 礴出結果 噬出清出至4；H略漏開：，4 4:空格隔開）Z，趙心起

14、占:j招刊現 請輔人終點的行瓢到敷澧我拼吉穎底等:5 .執行5功能，判斷是否有路徑走出迷宮:t:USER5FEKAHPESKTCiF1.薪珅克沖左但匕小川也上就”- X卜c±*T«t4*a«t *Hc*+* *dg；*物科網 場匕 15式 1 虛卞|沛布；M44* 其Hc*i*"*I*At4;情新3泮百的行就到前 2請輸入正有內埼單元款 碓舌楸嚇 儲A 住目的起點和終點 就出結果噬出I南町圣s此之目，殳才從人口到出口的埼徑，謝謝使用劉葉帆tUir 陸人口近出注國拼音鐲入法全：這種情況無法走出迷宮。我們再次觀察圖像設4,4和1,6分別為起點終點，再運行 5

15、功能 XJ "Q'.UserspekahDeEicLCDea uqIVaze 后111薄人迷宮的比，列數 工請輸人迷宮內清單元數 ；迷官結構加下4輸入迷宮的越點植終點 司葉片中Q退出卜青:*j莘 5此迷宮從入口到出口的一聚珞座如下,00000Q.10013U15167L8031311C1100910-10110n80010nn謝亦使司利沛骯的程序:觀察到可以成功解開迷宮步數從1依次開始七、程序清單#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h

16、>/迷宮坐標位置類型typedef structint x;/ 行值int y;/ 列值PosType;#define MAXLENGTH 25 /設迷宮的最大行列為25typedef int MazeTypeMAXLENGTHMAXLENGTH; /迷宮數組行歹U typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的"序號"PosType seat;/通道塊在迷宮中的"坐標位置"int di; /從此通道塊走向下一通道塊的"方向" (03表示東北) SElemType;/全局變量MazeTyp

17、e m; / 迷宮數組int curstep=1;/ 當前足跡，初值為1#define STACK_INIT_SIZE 10/存儲空間初始分配量#define STACKINCREMENT 2/存儲空間分配增量/棧的順序存儲表示typedef struct SqStackSElemType *base; /在棧構造之前和銷毀之后，base的值為NULLSElemType *top;/ 棧頂指針int stacksize; /當前已分配的存儲空間，以元素為單位SqStack; / 順序棧/構造一個空棧S int InitStack(SqStack *S)/為棧底分配一個指定大小的存儲空間(*S)

18、.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base; /棧底與棧頂相同表示一個空棧(*S).stacksize = STACK_INIT_SIZE;return 1;/若棧S為空棧(棧頂與棧底相同的)，則返回1,否則返回0。int StackEmpty(SqStack S) if(S.top = S.base)return 1;elsereturn 0;/插入元素e為新的棧頂元素。int Push(SqStack *S, SElem

19、Type e)if(*S).top - (*S).base >= (*S).stacksize) / 棧滿，追加存儲空間(*S).base = (SElemType *)realloc(*S).base ,(*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;/若棧不空，則刪除S的棧頂元素，用e返回其值，并返

20、回 1;否則返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base) return 0;*e = *-(*S).top;/這個等式的+ *優先級相同，但是它們的運算方式，是自右向左return 1;/定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡/當迷宮 m的b點的序號為1(可通過路徑),return 1;否則，return 0。int Pass(PosType b)if(mb.xb.y=1)return 1;elsereturn 0;void FootPrint(PosType a) /使迷宮 m的a點的序號

21、變為足跡(curstep),表示經過ma.xa.y=curstep;/根據當前位置及移動方向，返回下一位置PosType NextPos(PosType c,int di) PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量，列增量/移動方向，依次為東南西北c.x+=direcdi.x;c.y+=direcdi.y; return c;/使迷宮m的b點的序號變為-1(不能通過的路徑)void MarkPrint(PosType b)mb.xb.y=-1;/若迷宮maze中存在從入口 start到出口 end的通道，則求得一條/存放在棧中(從棧底到棧頂)，并返回1;否

22、則返回0int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start; do if(Pass(curpos) /當前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos);/ 留下足跡 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); /入棧當前位置及狀態curstep+; / 足跡加 1if(curpos.x=end.x&

23、;&curpos.y=end.y) /至1J達終點(出 口 )return 1;curpos=NextPos(curpos,e.di); else /當前位置不能通過 if(!StackEmpty(S) Pop(&S,&e); /退棧到前一位置curstep-;(北)while(e.di=3&&!StackEmpty(S) /前一位置處于最后一個方向 MarkPrint(e.seat);/留下不能通過的標記(-1)Pop(&S,&e); /退回一步curstep-;if(e.di<3)/沒到最后一個方向(北) e.di+; /換下一

24、個方向探索 Push(&S,e); curstep+;/ 設定當前位置是該新方向上的相鄰塊 curpos=NextPos(e.seat,e.di); while(!StackEmpty(S); return 0;/輸出迷宮的結構 void Print(int x,int y) int i,j;for(i=0;i<x;i+) for(j=0;j<y;j+) printf("%3d",mij); printf("n"); void main() PosType begin,end; int i,j,x,y,x1,y1,n,k; dosys

25、tem("cls");printf("*坨坨坨")；printf("printf("printf("printf("printf("printf("printf("nn請選擇");scanf("%d",&n);switch(n)case 1:printf("請輸入迷宮的行數 scanf("%d%d", &x, &y);清屏函數物聯網 1 班 -15180118- 劉沛航1請輸入迷宮的行數，列數n");2請輸入迷宮內墻單元數n");3迷宮結卞如下n");4輸入迷宮的起點和終點n");5輸出結果n");0退出n");，列數(包括外墻)：(空格隔開)");for(i=0;i<x;i+)/定義周邊值為0(同墻)m0i=0；mx-1i=0；/迷宮上面行的周邊即上邊墻迷宮下面