數(shù)據(jù)結(jié)構(gòu)迷宮問題實驗報告

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》迷宮問題實驗報告——實驗二專業(yè)：物聯(lián)網(wǎng)工程班級：物聯(lián)網(wǎng) 1班學(xué)號：15180118姓名：劉沛航一、 實驗?zāi)康谋境绦蚴抢梅沁f歸的方法求出一條走出迷宮的路徑，并將路徑輸出。 首先由用戶輸入一組二維數(shù)組來組成迷宮， 確認(rèn)后程序自動運行， 當(dāng)迷宮有完整路徑可以通過時， 以0和1所組成的迷宮形式輸出， 標(biāo)記所走過的路徑結(jié)束程序； 當(dāng)迷宮無路徑時，提示輸入錯誤結(jié)束程序。二、實驗內(nèi)容用一個 m*m長方陣表示迷宮， 0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序?qū)τ谌我庠O(shè)定的迷宮， 求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。三、程序設(shè)計1、概要設(shè)計1）設(shè)定棧的抽象數(shù)據(jù)類型定義ADTStack

{數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：

D={ai|ai 屬于 CharSet ，i=1、2?ｎ，n>=0}R={<ai-1,ai>|ai-1,ai 屬于 D，i=2,3, ?n}基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧Push

（&S

，e）初始條件：棧已經(jīng)存在操作結(jié)果：將

e所指向的數(shù)據(jù)加入到棧

s中Pop

（

&S,&e

）初始條件：棧已經(jīng)存在操作結(jié)果：若棧不為空，用 e返回棧頂元素，并刪除棧頂元素Getpop （&S，&e）初始條件：棧已經(jīng)存在操作結(jié)果：若棧不為空，用 e返回棧頂元StackEmpty(&S)初始條件：棧已經(jīng)存在操作結(jié)果：判斷棧是否為空。若棧為空，返回 1，否則返回 0Destroy(&S)初始條件：棧已經(jīng)存在操作結(jié)果：銷毀棧 s}ADTStack2）設(shè)定迷宮的抽象數(shù)據(jù)類型定義ADTyanshu

{數(shù)據(jù)對象：

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, ?N}COL={<ai,j-1

,ai,j>|ai,j-1

,ai,j

屬于

D,i=0,1,

?Ｍ，j=1,2,

?N}基本操作：InitMaze(MazeType&maze,inta[][COL],introw,intcol){初始條件：二維數(shù)組 inta[][COL], 已經(jīng)存在，其中第m-1 1 n-1礙，值1表示通路。

1至第0操作結(jié)果： 構(gòu)造迷宮的整形數(shù)組，

以空白表示通路，

字符‘0表’示障礙在迷宮四周加上一圈障礙MazePath（&maze）{初始條件：迷宮 maze已被賦值操作結(jié)果：若迷宮 maze中存在一條通路，則按如下規(guī)定改變maze的狀態(tài)；以字符‘*’表示路徑上的位置。字符‘@’表示‘死胡同’；否則迷宮的狀態(tài)不變}PrintMaze（M）{初始條件：迷宮 M已存在操作結(jié)果：以字符形式輸出迷宮}}ADTmaze3）本程序包括三個模塊a、主程序模塊voidmain (){初始化；構(gòu)造迷宮；迷宮求解；迷宮輸出；}b、棧模塊 ——實現(xiàn)棧的抽象數(shù)據(jù)類型c、迷宮模塊 ——實現(xiàn)迷宮的抽象數(shù)據(jù)類型2、詳細(xì)設(shè)計1）坐標(biāo)位置類型：typedefstruct{introw; //intcol; //......

迷宮中的行的列}PosType;//坐標(biāo)2）迷宮類型：typedefstruct{intm,n;intarr[RANGE][RANGE];}MazeType; // 迷宮類型void//設(shè)置迷宮的初值，包括邊緣一圈的值BoolMazePath(MazeType&maze,PosTypestart,PosTypeend)//求解迷宮 maze中，從入口 start 到出口 end的一條路徑//若存在，則返回 true，否則返回 falseVoidPrintMaze （MazeTypemaze ）//將迷宮打印出來3）棧類型：typedefstruct{int step; // 當(dāng)前位置在路徑上的 "序號"PosType seat; // 當(dāng)前的坐標(biāo)位置DirectiveType di; // 往下一個坐標(biāo)位置的方向}SElemType;// 棧的元素類型typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;棧的基本操作設(shè)置如下：VoidInitStack

（SqStack&S

）//初始化，設(shè)

S為空棧（

S.top=NUL

）VoidDestroyStack(Stack&S)//銷毀棧 S，并釋放空間VoidClearStack （SqStack&S）//將棧

S清空IntStackLength

（SqStack&S

）//返回棧

S的長度StatusStackEmpty

（SqStack&S

）？、若

S為空棧（

S.top==NULL

），則返回

TRUE

，否則返回

FALSEStatueGetTop

（SqStack&S

，SElemTypee

）//r

若棧

S不空，則以

e待會棧頂元素并返回

TRUE

，否則返回

FALSEStatuePop(SqStack&S

，SElemTypee)//若分配空間成功，則在

S的棧頂插入新的棧頂元素

s并返回

TRUE//否則棧不變，并返回

FALSEStatuePush(SqStack&S

，SElemType&e)//若分配空間程控，則刪除棧頂并以 e帶回其值，則返回 TRUE//否則返回 FALSEVoidStackTraverse （SqStack&S，Status）（*Visit）（SElemTypee））//從棧頂依次對 S中的每個節(jié)點調(diào)用函數(shù) Visit求迷宮路徑的偽碼算法：StatusMazePath(MazeType &maze,PosType start, PosType end){ //求解迷宮 maze中,從入口start到出口 end的一條路徑InitStack(s);PosTypecurpos=start;intcurstep=1; // 探索第一部do{if(Pass(maze,curpos)){ // 如果當(dāng)前位置可以通過 ,即是未曾走到的通道塊FootPrint(maze,curpos); // 留下足跡e=CreateSElem(curstep,curpos,1); // 創(chuàng)建元素Push(s,e);if(PosEquare(curpos,end)) returnTRUE;curpos=NextPos(curpos,1); // 獲得下一節(jié)點 :當(dāng)前位置的東鄰curstep++; // 探索下一步}else{ // 當(dāng)前位置不能通過if(!StackEmpty(s)){Pop(s,e);while(e.di==4&&!StackEmpty(s)){MarkPrint(maze,e.seat);Pop(s,e); // 留下不能通過的標(biāo)記 ,并退回步}if(e.di<4){e.di++;Push(s,e); // 換一個方向探索curpos=NextPos(e.seat,e.di); // 設(shè)定當(dāng)前位置是該方向上的相塊}//if}//if}//else}while(!StackEmpty(s));returnFALSE;}//MazePath四、程序調(diào)試分析首先呢，想自己讀入數(shù)據(jù)的，回來發(fā)現(xiàn)那樣，很麻煩，所以還是事先定義一個迷宮。2.棧的元素類型 一開始有點迷惑，后來就解決了3.本題中三個主要算法； InitMaze ，MazePath和PrintMaze 的時間復(fù)雜度均為 O（m*n）本題的空間復(fù)雜度也是 O（m*n）五、用戶使用說明1．本程序運行在 windows系列的操作系統(tǒng)下， 執(zhí)行文件為：Maze_Test.exe。六、程序運行結(jié)果建立迷宮：2．通過1功能建立 8*8的迷宮后，通過 2功能繼續(xù)建立迷宮內(nèi)部：通過建立自己設(shè)定單元數(shù)目建立迷宮內(nèi)墻。3．通過 3功能觀察已建立的迷宮結(jié)構(gòu)：4．通過 4功能確立迷宮起點和終點：（此處像我們隨機選擇 4,4和2,7分別為起點終點）5．執(zhí)行 5功能，判斷是否有路徑走出迷宮：這種情況無法走出迷宮。我們再次觀察圖像設(shè) 4,4和1,6分別為起點終點，再運行 5功能。觀察到可以成功解開迷宮步數(shù)從 1依次開始。七、程序清單#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>迷宮坐標(biāo)位置類型typedefstruct{intx; // 行值inty; // 列值}PosType;#defineMAXLENGTH25// 設(shè)迷宮的最大行列為 25typedefintMazeType[MAXLENGTH][MAXLENGTH];// 迷宮數(shù)組 [行][列]typedefstruct// 棧的元素類型{intord;// 通道塊在路徑上的＂序號＂PosTypeseat;// 通道塊在迷宮中的＂坐標(biāo)位置＂intdi;// 從此通道塊走向下一通道塊的＂方向＂ (0～3表示東～北 )}SElemType;全局變量MazeTypem;// 迷宮數(shù)組intcurstep=1;// 當(dāng)前足跡 ,初值為 1#defineSTACK_INIT_SIZE10 //存儲空間初始分配量#defineSTACKINCREMENT2 //存儲空間分配增量//棧的順序存儲表示typedefstructSqStack{SElemType*base; //在棧構(gòu)造之前和銷毀之后， base的值為 NULLSElemType*top; // 棧頂指針intstacksize; //當(dāng)前已分配的存儲空間，以元素為單位}SqStack; //順序棧// 構(gòu)造一個空棧 SintInitStack(SqStack*S){為棧底分配一個指定大小的存儲空間(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(0);(*S).top=(*S).base; // 棧底與棧頂相同表示一個空棧(*S).stacksize=STACK_INIT_SIZE;return1;}//若棧 S為空棧（棧頂與棧底相同的）

，則返回

1，否則返回

0。intStackEmpty(SqStackS){if(S.top==S.base)return1;elsereturn0;}// 插入元素 e為新的棧頂元素。intPush(SqStack*S,SElemTypee){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;return1;}// 若棧不空，則刪除 S的棧頂元素，用 e返回其值，并返回 1；否則返回 0。intPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)return0;*e=*--(*S).top;

//這個等式的

++*

優(yōu)先級相同，但是它們的運算方式，是自右向左return1;}//定義墻元素值為//當(dāng)迷宮 m的b

0,可通過路徑為 1,不能通過路徑為點的序號為 1(可通過路徑 )，return1;

-1,通過路徑為足跡否則，return0

。intPass(PosTypeb){if(m[b.x][b.y]==1)return1;elsereturn0;}voidFootPrint(PosTypea)

//使迷宮

m的

a點的序號變?yōu)樽阚E

(curstep)

，表示經(jīng)過{m[a.x][a.y]=curstep;}根據(jù)當(dāng)前位置及移動方向，返回下一位置PosTypeNextPos(PosTypec,intdi){PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{ 行增量,列增量}移動方向,依次為東南西北c.x+=direc[di].x;c.y+=direc[di].y;returnc;}//使迷宮 m的b點的序號變?yōu)?-1(不能通過的路徑 )voidMarkPrint(PosTypeb){m[b.x][b.y]=-1;}//若迷宮 maze中存在從入口 start 到出口 end的通道，則求得一條存放在棧中(從棧底到棧頂)，并返回1；否則返回0intMazePath(PosTypestart,PosTypeend){SqStackS;PosTypecurpos;SElemTypee;InitStack(&S);curpos=start;do{if(Pass(curpos)){// 當(dāng)前位置可以通過，即是未曾走到過的通道塊FootPrint(curpos);// 留下足跡e.ord=curstep;e.di=0;Push(&S,e);//

入棧當(dāng)前位置及狀態(tài)curstep++;//

足跡加

1if(curpos.x==end.x&&curpos.y==end.y)//

到達(dá)終點

(出口

)return1;curpos=NextPos(curpos,e.di);}else{// 當(dāng)前位置不能通過if(!StackEmpty(S)){Pop(&S,&e);// 退棧到前一位置curstep--;while(e.di==3&&!StackEmpty(S))//{

前一位置處于最后一個方向

(北)MarkPrint(e.seat);// 留下不能通過的標(biāo)記 (-1)Pop(&S,&e);// 退回一步curstep--;}if(e.di<3)// 沒到最后一個方向 (北){e.di++;// 換下一個方向探索Push(&S,e);curstep++;// 設(shè)定當(dāng)前位置是該新方向上的相鄰塊curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));return0;}輸出迷宮的結(jié)構(gòu)voidPrint(intx,inty){inti,j;for(i=0;i<x;i++){for(j=0;j<y;j++)printf("%3d",m[i][j]);printf("\n");}}voidmain(){PosTypebegin,end;inti,j,x,y,x1,y1,n,k;do{system("cls");//清屏函數(shù)printf("**************************物聯(lián)網(wǎng)1班-15180118-劉沛航*************************\n\n\n");printf("1請輸入迷宮的行數(shù),列數(shù)\n");printf("2請輸入迷宮內(nèi)墻單元數(shù)\n");printf("3迷宮結(jié)構(gòu)如下\n");printf("4輸入迷宮的起點和終點\n");printf("5輸出結(jié)果\n");printf("0退出\n");printf("\n\n請選擇");scanf("%d",&n);switch(n){case1:{printf(" 請輸入迷宮的行數(shù) ,列數(shù)(包括外墻 )：(空格隔開 )");scanf("%d%d",&x,&y);for(i=0;i<x;i++)//

定義周邊值為

0(同墻

){m[0][i]=0;

//迷宮