數(shù)據(jù)結構迷宮問題實驗報告

1、.數(shù)據(jù)結構與算法設計迷宮問題實驗報告實驗二專業(yè)：物聯(lián)網(wǎng)工程班級：物聯(lián)網(wǎng)1班學號：姓名：劉沛航一、 實驗目的 本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標記所走過的路徑結束程序；當迷宮無路徑時，提示輸入錯誤結束程序。二、實驗內容 用一個m*m長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序對于任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。三、程序設計 1、概要設計（1）設定棧的抽象數(shù)據(jù)類型定義 ADT Stack數(shù)據(jù)對象：D=a

2、i|ai屬于CharSet，i=1、2n，n=0數(shù)據(jù)關系：R=|ai-1,ai屬于D，i=2,3,n基本操作：InitStack(&S)操作結果：構造一個空棧Push（&S，e）初始條件：棧已經(jīng)存在操作結果：將e所指向的數(shù)據(jù)加入到棧s中Pop（&S,&e）初始條件：棧已經(jīng)存在操作結果：若棧不為空，用e返回棧頂元素，并刪除棧頂元素Getpop（&S，&e）初始條件：棧已經(jīng)存在操作結果：若棧不為空，用e返回棧頂元StackEmpty(&S)初始條件：棧已經(jīng)存在操作結果：判斷棧是否為空。若棧為空，返回1，否則返回0Destroy(&S)初始條件：棧已經(jīng)存在操作結果：銷毀棧sADT Stack（2）設

3、定迷宮的抽象數(shù)據(jù)類型定義ADT yanshu數(shù)據(jù)對象：D=ai,j|ai,j屬于 、*、#,0=i=M,0=j=N數(shù)據(jù)關系：R=ROW,COLROW=|ai-1,j,ai,j屬于D，i=1,2,M,j=0,1,NCOL=|ai,j-1,ai,j屬于D,i=0,1,M，j=1,2,N基本操作：InitMaze(MazeType &maze, int aCOL, int row, int col)初始條件：二維數(shù)組int aCOL,已經(jīng)存在，其中第1至第m-1行，每行自第1到第n-1列的元素已經(jīng)值，并以值0表示障礙，值1表示通路。操作結果：構造迷宮的整形數(shù)組，以空白表示通路，字符0表示障礙在迷宮四

4、周加上一圈障礙MazePath（&maze）初始條件：迷宮maze已被賦值操作結果：若迷宮maze中存在一條通路，則按如下規(guī)定改變maze的狀態(tài)；以字符*表示路徑上的位置。字符表示死胡同；否則迷宮的狀態(tài)不變PrintMaze（M）初始條件：迷宮M已存在操作結果：以字符形式輸出迷宮ADTmaze（3）本程序包括三個模塊a、主程序模塊void main()初始化；構造迷宮；迷宮求解；迷宮輸出；b、棧模塊實現(xiàn)棧的抽象數(shù)據(jù)類型c、迷宮模塊實現(xiàn)迷宮的抽象數(shù)據(jù)類型2、詳細設計 （1）坐標位置類型： typedef structint row;/迷宮中的行int col;/.的列PosType;/坐標（2）

5、迷宮類型：typedef structint m,n;int arrRANGERANGE;MazeType;/迷宮類型voidInitMaze(MazeType &maze, int aCOL, int row, int col)/設置迷宮的初值，包括邊緣一圈的值Bool MazePath(MazeType &maze,PosType start, PosType end)/求解迷宮maze中，從入口start到出口end的一條路徑/若存在，則返回true，否則返回falseVoid PrintMaze（MazeType maze）/將迷宮打印出來（3）棧類型：typedef structin

6、tstep;/當前位置在路徑上的序號PosTypeseat;/當前的坐標位置DirectiveTypedi;/往下一個坐標位置的方向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

7、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)/若分配空間程控，則刪除棧頂并以e帶回其值，則返回TRUE/否則返

8、回FALSEVoid StackTraverse（SqStack &S，Status）（*Visit）（SElemType e）/從棧頂依次對S中的每個節(jié)點調用函數(shù)Visit4求迷宮路徑的偽碼算法：Status MazePath(MazeType &maze,PosType start, PosType end) /求解迷宮maze中,從入口start到出口end的一條路徑InitStack(s);PosType curpos = start;int curstep = 1;/探索第一部doif( Pass(maze,curpos) )/如果當前位置可以通過,即是未曾走到的通道塊FootPri

9、nt(maze,curpos);/留下足跡e = CreateSElem(curstep,curpos,1);/創(chuàng)建元素Push(s,e);if( PosEquare(curpos,end) )return TRUE;curpos =NextPos(curpos,1);/獲得下一節(jié)點:當前位置的東鄰curstep+;/探索下一步else/當前位置不能通過if(!StackEmpty(s)Pop(s,e);while(e.di=4 & !StackEmpty(s) )MarkPrint(maze,e.seat); Pop(s,e);/留下不能通過的標記,并退回步if(e.di4)e.di+; P

10、ush(s,e);/換一個方向探索curpos = NextPos(e.seat,e.di);/設定當前位置是該方向上的相塊/if/if/elsewhile(!StackEmpty(s);return FALSE;/MazePath四、程序調試分析 1.首先呢，想自己讀入數(shù)據(jù)的，回來發(fā)現(xiàn)那樣，很麻煩，所以還是事先定義一個迷宮。2.棧的元素類型 一開始有點迷惑，后來就解決了3.本題中三個主要算法；InitMaze，MazePath和PrintMaze的時間復雜度均為O（m*n）本題的空間復雜度也是O（m*n）五、用戶使用說明 1本程序運行在windows系列的操作系統(tǒng)下，執(zhí)行文件為：Maze_T

11、est.exe。六、程序運行結果1.建立迷宮：2通過1功能建立8*8的迷宮后，通過2功能繼續(xù)建立迷宮內部：通過建立自己設定單元數(shù)目建立迷宮內墻。3通過3功能觀察已建立的迷宮結構：4通過4功能確立迷宮起點和終點：（此處像我們隨機選擇4,4和2,7分別為起點終點）5執(zhí)行5功能，判斷是否有路徑走出迷宮：這種情況無法走出迷宮。我們再次觀察圖像設4,4和1,6分別為起點終點，再運行5功能。觀察到可以成功解開迷宮步數(shù)從1依次開始。七、程序清單#include#include#include#include/ 迷宮坐標位置類型typedef struct int x;/ 行值 int y;/ 列值 PosT

12、ype;#define MAXLENGTH 25 / 設迷宮的最大行列為25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組行列 typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的序號 PosType seat; / 通道塊在迷宮中的坐標位置 int di; / 從此通道塊走向下一通道塊的方向(03表示東北) SElemType;/ 全局變量 MazeType m; / 迷宮數(shù)組 int curstep=1; / 當前足跡,初值為1 #define STACK_INIT_SIZE 10/ 存儲空間初始分配量 #d

13、efine STACKINCREMENT 2/ 存儲空間分配增量 / 棧的順序存儲表示 typedef struct SqStackSElemType *base;/ 在棧構造之前和銷毀之后，base的值為NULL SElemType *top;/ 棧頂指針 int stacksize;/ 當前已分配的存儲空間，以元素為單位 SqStack;/ 順序棧/構造一個空棧Sint InitStack(SqStack *S)/ 為棧底分配一個指定大小的存儲空間(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(

14、*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, SElemType e)if(*S).top - (*S).base = (*S).stacksize)/ 棧滿，追加存儲空間(*S).base =

15、 (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返回其值，并返回1；否則返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;

16、*e = *-(*S).top; / 這個等式的+ * 優(yōu)先級相同，但是它們的運算方式，是自右向左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點的序號變?yōu)樽阚E(curstep)，表示經(jīng)過ma.xa.y=curstep;/ 根據(jù)當前位置及移動方向，返回下一位置 PosType NextPo

17、s(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點的序號變?yōu)?1(不能通過的路徑)void MarkPrint(PosType b) mb.xb.y=-1;/ 若迷宮maze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 int MazePath(PosType start,PosType end) SqStack S;PosType

18、curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 當前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos); / 留下足跡 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入棧當前位置及狀態(tài) curstep+; / 足跡加1 if(curpos.x=end.x&curpos.y=end.y) / 到達終點(出口) return 1;curpos=NextPos(curpos,e.di);else/ 當前

19、位置不能通過 if(!StackEmpty(S)Pop(&S,&e); / 退棧到前一位置 curstep-;while(e.di=3&!StackEmpty(S) / 前一位置處于最后一個方向(北)MarkPrint(e.seat); / 留下不能通過的標記(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di3) / 沒到最后一個方向(北) e.di+; / 換下一個方向探索Push(&S,e); curstep+;/ 設定當前位置是該新方向上的相鄰塊curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0

20、;/ 輸出迷宮的結構 void Print(int x,int y) int i,j;for(i=0;ix;i+)for(j=0;jy;j+)printf(%3d,mij);printf(n); void main()PosType begin,end;int i,j,x,y,x1,y1,n,k;dosystem(cls); /清屏函數(shù)printf(*物聯(lián)網(wǎng)1班-15180118-劉沛航*nnn);printf( 1請輸入迷宮的行數(shù),列數(shù)n);printf( 2請輸入迷宮內墻單元數(shù)n);printf( 3迷宮結構如下n);printf( 4輸入迷宮的起點和終點n);printf( 5輸出結果n);printf( 0退出n);printf(nn請選擇 ); scanf(%d,&n);switch(n)case 1: printf(請輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開); scanf(%d%d, &x, &y); for(i=0;ix;i+) / 定義周邊值為0(同墻) m