數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二專業(yè)：物聯(lián)網(wǎng)工程班級(jí)：物聯(lián)網(wǎng)1班學(xué)號(hào)：15180118姓名：劉沛航一、 實(shí)驗(yàn)?zāi)康?         本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來(lái)組成迷宮，確認(rèn)后程序自動(dòng)運(yùn)行，當(dāng)迷宮有完整路徑可以通過(guò)時(shí)，以0和1所組成的迷宮形式輸出，標(biāo)記所走過(guò)的路徑結(jié)束程序；當(dāng)迷宮無(wú)路徑時(shí)，提示輸入錯(cuò)誤結(jié)束程序。二、實(shí)驗(yàn)內(nèi)容 用一個(gè)m*m長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序?qū)τ谌我庠O(shè)定的迷宮，求出一條從入口到出口

2、的通路，或得出沒(méi)有通路的結(jié)論。三、程序設(shè)計(jì) 1、概要設(shè)計(jì)（1） 設(shè)定棧的抽象數(shù)據(jù)類型定義 ADT Stack數(shù)據(jù)對(duì)象：D=ai|ai屬于CharSet，i=1、2n，n>=0數(shù)據(jù)關(guān)系：R=<ai-1,ai>|ai-1,ai屬于D，i=2,3,n基本操作：          InitStack(&S)             

3、0;   操作結(jié)果：構(gòu)造一個(gè)空棧          Push（&S，e）                 初始條件：棧已經(jīng)存在              

4、;   操作結(jié)果：將e所指向的數(shù)據(jù)加入到棧s中          Pop（&S,&e）                 初始條件：棧已經(jīng)存在            

5、     操作結(jié)果：若棧不為空，用e返回棧頂元素，并刪除棧頂元素          Getpop（&S，&e）                 初始條件：棧已經(jīng)存在        &#

6、160;        操作結(jié)果：若棧不為空，用e返回棧頂元          StackEmpty(&S)                 初始條件：棧已經(jīng)存在      

7、0;          操作結(jié)果：判斷棧是否為空。若棧為空，返回1，否則返回0          Destroy(&S)                 初始條件：棧已經(jīng)存在    

8、             操作結(jié)果：銷毀棧sADT Stack（2）設(shè)定迷宮的抽象數(shù)據(jù)類型定義ADT yanshu數(shù)據(jù)對(duì)象：D=ai,j|ai,j屬于 、*、#,0<=i<=M,0<=j<=N數(shù)據(jù)關(guān)系：R=ROW,COL          ROW=<ai-1,j,ai,j>|ai-1,j,ai,j屬于D，i=1,2,M,j=0,1,

9、N          COL=<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)初始條件：二維數(shù)組int aCOL,已經(jīng)存在，其中第1至第m-1行，每行自第1到第n-1列的元素已經(jīng)值，并以值0表示障礙，值1表示通路。操作結(jié)果：構(gòu)造迷宮的整形數(shù)組，以空白表示通路，字符0表示障礙    &#

10、160;           在迷宮四周加上一圈障礙              MazePath（&maze）                初始條件：迷宮maze已被賦值 

11、;               操作結(jié)果：若迷宮maze中存在一條通路，則按如下規(guī)定改變maze的狀態(tài)；以字符*表示路徑上的位置。字符表示死胡同；否則迷宮的狀態(tài)不變PrintMaze（M）初始條件：迷宮M已存在操作結(jié)果：以字符形式輸出迷宮           ADTmaze（3）本程序包括三個(gè)模塊a、 主程序模塊void mai

12、n()初始化；構(gòu)造迷宮；迷宮求解；迷宮輸出；b、 棧模塊實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型c、 迷宮模塊實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型2、詳細(xì)設(shè)計(jì) （1）坐標(biāo)位置類型： typedef struct         int row;    /迷宮中的行    int col;      /.的列PosType;/坐標(biāo)    

13、60;                                            （2） 迷宮類型：typedef struct 

14、;   int m,n;    int arrRANGERANGE;MazeType;            /迷宮類型void InitMaze(MazeType &maze, int aCOL, int row, int col)/設(shè)置迷宮的初值，包括邊緣一圈的值Bool MazePath(MazeType &maze,PosType start, PosType end)/求

15、解迷宮maze中，從入口start到出口end的一條路徑/若存在，則返回true，否則返回falseVoid PrintMaze（MazeType maze）/將迷宮打印出來(lái)（3）  棧類型：typedef struct    int          step;    /當(dāng)前位置在路徑上的"序號(hào)"    PosType 

16、60;    seat;    /當(dāng)前的坐標(biāo)位置    DirectiveType   di;        /往下一個(gè)坐標(biāo)位置的方向SElemType;/棧的元素類型 typedef struct    SElemType *base;    SElemType *top;&#

17、160;   int stacksize;SqStack;棧的基本操作設(shè)置如下：Void InitStack（SqStack & S）/初始化，設(shè)S為空棧（S.top=NUL）Void DestroyStack(Stack &S)/銷毀棧S，并釋放空間Void ClearStack（SqStack & S）/將棧S清空Int StackLength（SqStack &S）/返回棧S的長(zhǎng)度Status StackEmpty（SqStack &S）？、若S為空棧（S.top=NULL），則返回TRUE，否則返回FALSEStat

18、ue GetTop（SqStack &S，SElemType e）/r若棧S不空，則以e待會(huì)棧頂元素并返回TRUE，否則返回FALSEStatue Pop(SqStack&S，SElemType e)/若分配空間成功，則在S的棧頂插入新的棧頂元素s并返回TRUE/否則棧不變，并返回FALSEStatue Push(SqStack&S，SElemType &e)/若分配空間程控，則刪除棧頂并以e帶回其值，則返回TRUE/否則返回FALSEVoid StackTraverse（SqStack &S，Status）（*Visit）（SElemType e）/從

19、棧頂依次對(duì)S中的每個(gè)節(jié)點(diǎn)調(diào)用函數(shù)Visit4求迷宮路徑的偽碼算法：Status MazePath(MazeType &maze,PosType start, PosType end) /求解迷宮maze中,從入口start到出口end的一條路徑    InitStack(s);    PosType curpos = start;    int curstep = 1;        &#

20、160;       /探索第一部    do        if( Pass(maze,curpos) )    /如果當(dāng)前位置可以通過(guò),即是未曾走到的通道塊            FootPrint(maze,curpos); 

21、0;          /留下足跡            e = CreateSElem(curstep,curpos,1);    /創(chuàng)建元素            Push(s,e);  

22、0;         if( PosEquare(curpos,end) )    return TRUE;            curpos =NextPos(curpos,1);            /獲得下一節(jié)點(diǎn):當(dāng)前位

23、置的東鄰            curstep+;                            /探索下一步       

24、; else                        /當(dāng)前位置不能通過(guò)            if(!StackEmpty(s)        

25、;        Pop(s,e);                while(e.di=4 && !StackEmpty(s) )                 

26、0;  MarkPrint(maze,e.seat); Pop(s,e);   /留下不能通過(guò)的標(biāo)記,并退回步                                if(e.di<4)  

27、60;                 e.di+; Push(s,e);            /換一個(gè)方向探索                &#

28、160;   curpos = NextPos(e.seat,e.di);    /設(shè)定當(dāng)前位置是該方向上的相塊                /if            /if      

29、;  /else    while(!StackEmpty(s);    return FALSE;/MazePath四、程序調(diào)試分析 1.首先呢，想自己讀入數(shù)據(jù)的，回來(lái)發(fā)現(xiàn)那樣，很麻煩，所以還是事先定義一個(gè)迷宮。2.棧的元素類型 一開(kāi)始有點(diǎn)迷惑，后來(lái)就解決了3.本題中三個(gè)主要算法；InitMaze，MazePath和PrintMaze的時(shí)間復(fù)雜度均為O（m*n）本題的空間復(fù)雜度也是O（m*n）五、用戶使用說(shuō)明 1本程序運(yùn)行在windows系列的操作系統(tǒng)下，執(zhí)行文件為：Maze_Test.exe

30、。六、程序運(yùn)行結(jié)果1.建立迷宮：2通過(guò)1功能建立8*8的迷宮后，通過(guò)2功能繼續(xù)建立迷宮內(nèi)部：通過(guò)建立自己設(shè)定單元數(shù)目建立迷宮內(nèi)墻。3通過(guò)3功能觀察已建立的迷宮結(jié)構(gòu)：4通過(guò)4功能確立迷宮起點(diǎn)和終點(diǎn)：（此處像我們隨機(jī)選擇4,4和2,7分別為起點(diǎn)終點(diǎn)）5執(zhí)行5功能，判斷是否有路徑走出迷宮：這種情況無(wú)法走出迷宮。我們?cè)俅斡^察圖像設(shè)4,4和1,6分別為起點(diǎn)終點(diǎn)，再運(yùn)行5功能。觀察到可以成功解開(kāi)迷宮步數(shù)從1依次開(kāi)始。七、程序清單#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.

31、h>/ 迷宮坐標(biāo)位置類型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 設(shè)迷宮的最大行列為25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組行列 typedef struct / 棧的元素類型 int ord; / 通道塊在路徑上的序號(hào) PosType seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03表示東北) SElemType;/ 全局變量 MazeType m; / 迷宮數(shù)組 int curstep

32、=1; / 當(dāng)前足跡,初值為1 #define STACK_INIT_SIZE 10/ 存儲(chǔ)空間初始分配量 #define STACKINCREMENT 2/ 存儲(chǔ)空間分配增量 / 棧的順序存儲(chǔ)表示 typedef struct SqStackSElemType *base;/ 在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType *top;/ 棧頂指針 int stacksize;/ 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 SqStack;/ 順序棧/構(gòu)造一個(gè)空棧Sint InitStack(SqStack *S)/ 為棧底分配一個(gè)指定大小的存儲(chǔ)空間(*S).base = (SEl

33、emType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base;/ 棧底與棧頂相同表示一個(gè)空棧(*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)

34、.top - (*S).base >= (*S).stacksize)/ 棧滿，追加存儲(chǔ)空間(*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返回其值，并返回1；否則返回0。int

35、Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top; / 這個(gè)等式的+ * 優(yōu)先級(jí)相同，但是它們的運(yùn)算方式，是自右向左return 1;/ 定義墻元素值為0,可通過(guò)路徑為1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡/ 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，return 1; 否則，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;void FootPrint(PosType a) / 使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curs

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

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

38、&curpos.y=end.y) / 到達(dá)終點(diǎn)(出口) return 1;curpos=NextPos(curpos,e.di);else/ 當(dāng)前位置不能通過(guò) if(!StackEmpty(S)Pop(&S,&e); / 退棧到前一位置 curstep-;while(e.di=3&&!StackEmpty(S) / 前一位置處于最后一個(gè)方向(北)MarkPrint(e.seat); / 留下不能通過(guò)的標(biāo)記(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di<3) / 沒(méi)到最后一個(gè)方向(北) e.di+;

39、/ 換下一個(gè)方向探索Push(&S,e); curstep+;/ 設(shè)定當(dāng)前位置是該新方向上的相鄰塊curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/ 輸出迷宮的結(jié)構(gòu) 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;dosystem("cls"); /清屏函數(shù)printf("*物聯(lián)網(wǎng)1班-15