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

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》迷宮問(wèn)題實(shí)驗(yàn)報(bào)告——實(shí)驗(yàn)二專(zhuān)業(yè)：物聯(lián)網(wǎng)工程班級(jí)：物聯(lián)網(wǎng) 1班學(xué)號(hào)：15180118姓名：劉沛航一、 實(shí)驗(yàn)?zāi)康谋境绦蚴抢梅沁f歸的方法求出一條走出迷宮的路徑，并將路徑輸出。 首先由用戶(hù)輸入一組二維數(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è)定的迷宮， 求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。三、程序設(shè)計(jì)1、概要設(shè)計(jì)1）設(shè)定棧的抽象數(shù)據(jù)類(lèi)型定義ADTStack

{數(shù)據(jù)對(duì)象：數(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)造一個(gè)空棧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é)果：銷(xiāo)毀棧 s}ADTStack2）設(shè)定迷宮的抽象數(shù)據(jù)類(lèi)型定義ADTyanshu

{數(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, ?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）本程序包括三個(gè)模塊a、主程序模塊voidmain (){初始化；構(gòu)造迷宮；迷宮求解；迷宮輸出；}b、棧模塊 ——實(shí)現(xiàn)棧的抽象數(shù)據(jù)類(lèi)型c、迷宮模塊 ——實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類(lèi)型2、詳細(xì)設(shè)計(jì)1）坐標(biāo)位置類(lèi)型：typedefstruct{introw; //intcol; //......

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

（SqStack&S

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

S為空棧（

S.top=NUL

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

S清空IntStackLength

（SqStack&S

）//返回棧

S的長(zhǎng)度StatusStackEmpty

（SqStack&S

）？、若

S為空棧（

S.top==NULL

），則返回

TRUE

，否則返回

FALSEStatueGetTop

（SqStack&S

，SElemTypee

）//r

若棧

S不空，則以

e待會(huì)棧頂元素并返回

TRUE

，否則返回

FALSEStatuePop(SqStack&S

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

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

s并返回

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

FALSEStatuePush(SqStack&S

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

//棧滿(mǎn)，追加存儲(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;return1;}// 若棧不空，則刪除 S的棧頂元素，用 e返回其值，并返回 1；否則返回 0。intPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)return0;*e=*--(*S).top;

//這個(gè)等式的

++*

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

0,可通過(guò)路徑為 1,不能通過(guò)路徑為點(diǎn)的序號(hào)為 1(可通過(guò)路徑 )，return1;

-1,通過(guò)路徑為足跡否則，return0

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

//使迷宮

m的

a點(diǎn)的序號(hào)變?yōu)樽阚E

(curstep)

，表示經(jīng)過(guò){m[a.x][a.y]=curstep;}根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置PosTypeNextPos(PosTypec,intdi){PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{ 行增量,列增量}移動(dòng)方向,依次為東南西北c.x+=direc[di].x;c.y+=direc[di].y;returnc;}//使迷宮 m的b點(diǎn)的序號(hào)變?yōu)?-1(不能通過(guò)的路徑 )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)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊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á)終點(diǎn)

(出口

)return1;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++;// 換下一個(gè)方向探索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請(qǐng)輸入迷宮的行數(shù),列數(shù)\n");printf("2請(qǐng)輸入迷宮內(nèi)墻單元數(shù)\n");printf("3迷宮結(jié)構(gòu)如下\n");printf("4輸入迷宮的起點(diǎn)和終點(diǎn)\n");printf("5輸出結(jié)果\n");printf("0退出\n");printf("\n\n請(qǐng)選擇");scanf("%d",&n);switch(n){case1:{printf(" 請(qǐng)輸入迷宮的行數(shù) ,列數(shù)(包括外墻 )：(空格隔開(kāi) )");scanf("%d%d",&x,&y);for(i=0;i<x;i++)//

定義周邊值為

0(同墻

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

//迷宮