數(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ù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第1頁(yè)。實(shí)驗(yàn)?zāi)康?/p>

本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶(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ì)象：D={ai|ai屬于CharSet，i=1、2…n，n>=0}數(shù)據(jù)關(guān)系：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)存在數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第2頁(yè)。

操作結(jié)果：若棧不為空，用e返回棧頂元數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第2頁(yè)。

StackEmpty(&S)

初始條件：棧已經(jīng)存在

操作結(jié)果：判斷棧是否為空。若棧為空，返回1，否則返回0

Destroy(&S)

初始條件：棧已經(jīng)存在

操作結(jié)果：銷(xiāo)毀棧s}ADTStack（2）設(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,…M，j=1,2,…N}基本操作：InitMaze(MazeType&maze,inta[][COL],introw,intcol){初始條件：二維數(shù)組inta[][COL],已經(jīng)存在，其中第1至第m-1行，每行自第1到第n-1列的元素已經(jīng)值，并以值0表示障礙，值1表示通路。操作結(jié)果：構(gòu)造迷宮的整形數(shù)組，以空白表示通路，字符‘0’表示障礙

在迷宮四周加上一圈障礙

MazePath（&maze）{

初始條件：迷宮maze已被賦值

操作結(jié)果：若迷宮maze中存在一條通路，則按如下規(guī)定改變maze的狀態(tài)；以字符‘*’表示路徑上的位置。字符‘’表示‘死胡同’；否則迷宮的狀態(tài)不變}PrintMaze（M）{初始條件：迷宮M已存在操作結(jié)果：以字符形式輸出迷宮}

}ADTmaze數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第3頁(yè)。（3）本程序包括三個(gè)模塊數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第3頁(yè)。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

InitMaze(MazeType&maze,inta[][COL],introw,intcol)\//設(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{數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第4頁(yè)。

SElemType*base;數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第4頁(yè)。

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ù)Visit4求迷宮路徑的偽碼算法：StatusMazePath(MazeType&maze,PosTypestart,PosTypeend){//求解迷宮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)記,并退回步數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第5頁(yè)。

}數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第5頁(yè)。

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)試分析1.首先呢，想自己讀入數(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。數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第6頁(yè)。六、程序運(yùn)行結(jié)果數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第6頁(yè)。1.建立迷宮：2．通過(guò)1功能建立8*8的迷宮后，通過(guò)2功能繼續(xù)建立迷宮內(nèi)部：通過(guò)建立自己設(shè)定單元數(shù)目建立迷宮內(nèi)墻。數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第7頁(yè)。3．通過(guò)3功能觀察已建立的迷宮結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第7頁(yè)。4．通過(guò)4功能確立迷宮起點(diǎn)和終點(diǎn)：（此處像我們隨機(jī)選擇4,4和2,7分別為起點(diǎn)終點(diǎn)）數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第8頁(yè)。5．執(zhí)行5功能，判斷是否有路徑走出迷宮：數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第8頁(yè)。這種情況無(wú)法走出迷宮。我們?cè)俅斡^察圖像設(shè)4,4和1,6分別為起點(diǎn)終點(diǎn)，再運(yùn)行5功能。數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第9頁(yè)。數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第9頁(yè)。觀察到可以成功解開(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;數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第10頁(yè)。//全局變量數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第10頁(yè)。MazeTypem;//迷宮數(shù)組intcurstep=1;//當(dāng)前足跡,初值為1#defineSTACK_INIT_SIZE10 //存儲(chǔ)空間初始分配量#defineSTACKINCREMENT2 //存儲(chǔ)空間分配增量//棧的順序存儲(chǔ)表示typedefstructSqStack{ SElemType*base; //在棧構(gòu)造之前和銷(xiāo)毀之后，base的值為NULL SElemType*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; else return0;}// 插入元素e為新的棧頂元素。intPush(SqStack*S,SElemTypee){ if((*S).top-(*S).base>=(*S).stacksize) //棧滿，追加存儲(chǔ)空間 {數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第11頁(yè)。 (*S).base=(SElemType*)realloc((*S).base,數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第11頁(yè)。 ((*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;}//定義墻元素值為0,可通過(guò)路徑為1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡//當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，return1;否則，return0。intPass(PosTypeb){ if(m[b.x][b.y]==1) return1; else return0;}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;數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第12頁(yè)。}數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第12頁(yè)。//使迷宮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.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&&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--; }數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第13頁(yè)。 if(e.di<3)//沒(méi)到最后一個(gè)方向(北)數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第13頁(yè)。 { 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){數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第14頁(yè)。case1:{ 數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題實(shí)驗(yàn)報(bào)告全文共16頁(yè)，當(dāng)前為第14頁(yè)。 printf("請(qǐng)輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開(kāi))"); scanf("%d%d",&x,&y); for(i=0;i<x;i++)//定義