2023年數(shù)據(jù)結(jié)構(gòu)之迷宮求解實(shí)驗(yàn)報(bào)告武漢大學(xué)

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——迷宮求解問題實(shí)驗(yàn)上機(jī)環(huán)境：DevC++二、程序設(shè)計(jì)相關(guān)信息（1）實(shí)驗(yàn)題目：迷宮求解問題問題描述：實(shí)驗(yàn)題3.5改善節(jié)中的求解迷宮問題程序,規(guī)定輸出如圖3.14所示的迷宮的所有途徑，并求最短途徑長(zhǎng)度及最短途徑。01?.445（2）實(shí)驗(yàn)項(xiàng)目組成：本項(xiàng)目由一個(gè)原程序mg.cpp及mg.cxc文獻(xiàn)組成。（3）實(shí)驗(yàn)項(xiàng)目的程序結(jié)構(gòu)：函數(shù)調(diào)用關(guān)系圖：mainOQtrurt舛松依m(xù)onnth/X余杼兩加

(4)實(shí)驗(yàn)項(xiàng)目包含的函數(shù)的功能描述:mg[M+l][N+l]//構(gòu)造迷宮二維數(shù)組，1表達(dá)墻不可走方塊，0表達(dá)通道m(xù)g[M+l][N+l]mgpath(intxi,intyi,intxe,intye)〃求解途徑為：(xi,yi)—>(xe,ye)//采用順序棧存儲(chǔ)，進(jìn)棧，回溯,退棧等(5)算法描述:求解迷宮從入口到出口的所有途徑，從入口出發(fā)，順某一個(gè)方向向前試探，對(duì)于可走的方塊都進(jìn)棧,并將這個(gè)可走發(fā)方位保存,且t。p+1,然后試探下一個(gè)方塊,若下一個(gè)方塊能走通則繼續(xù)，否則則回溯到前一個(gè)方塊，且top-U為記錄所有的途徑調(diào)用Path[k]=Stack[k]記錄，從次方塊向不同方向去試探，已經(jīng)走過(guò)的方塊則為不可走方塊。最后比較I。P值找到一條最短途徑并輸出。試探途徑過(guò)程的算法運(yùn)用了“廣度優(yōu)先搜索遍歷”算法。流程圖:for循環(huán)mg=0(6)實(shí)驗(yàn)數(shù)據(jù):迷宮數(shù)組如下:intmg[M+l][N+l]={{1,1,1,1,1,1}J1,0,0,0,13},{1,0,1,0,0,1},實(shí)驗(yàn)結(jié)果:{1,0,0,0,1,1),{1,1,0,0,0,1),(1,1,1,1,1,1)}；路徑如下：實(shí)驗(yàn)結(jié)果:1：<1,1><1,2><1,3><2,3><3,3><4,3〉<4,4〉2：<1,1><1,2><1,3><2,3><3,3><3,2X4,2X4,3X4,4>3：<1,1><2,1><3,1><3,2><3,3><4,3><4,4>4：<1,1X2,1X3,1X3,2X4,2><4,3><4,4>最短路徑如下：路隹最妞長(zhǎng)度：7最短路徑路備<12><1,3><2,3><3,3><4,3><4,4>情按任意鍵繼續(xù)..<1三、程序代碼:#inc1ude<stdio.h>#includc#includc#includc<stdlib.h>#defineM6#define#defineMaxsize100intmg[M+l][N+l]={#includc<stdlib.h>#defineM6U/，l,1,1,1}，{1，0.0,0,1,1),{1,0,1,001},{1,0,0,0,1,1),{1,1,0,0,0,11,{1,1,1,1,1,1});struct(inti；intj;intdi;}Stack[Maxsize],Path[Maxsize];inttop=-l；intcount=1;intmin=Maxsize;intmgpath()(inti,j,di,find,k;top++;Stack[top].i=l;Stack[top].j=1；Stack[top].di=-l;mg[1][1]=-1;Prinif("迷宮所有途徑如下：'n")；whi1e(top>—1)i=Stack|top].i;j=Stack[top],j;di=Stack[top].di;if(i==M-2&&j==N-2)prinlf("%4d：",counl++);for(k=0；k<=top;k++){printf("(%d.%d)",Stack[k].i,Stack[k].j);if((k+l)%5==0)printf("\n")；)printfC'\n");if(top+1<min)(for(k=0;k<=top;k++)Path[k]=Stack[k];min=top+1;1mg[Stackftop].i][Stack[top].j]=0;topi=Stack[top].iy=Stack[top].j;di=Stack[top],di;}find=0；while(di<4&&find==0)(di++;switch(di)caseO:i=Stack[top].i-1;j=S(ackftop].j;break；case1：i=Stack[top].i;j=Stack[top].j+l:break;case2:i=Stack[top].i+1;j=Stack[lop],j;break;case3:i=Stack[top].i;j=Stack[top].j-1：break;)if(mg川[j]==0)find=1;}if(find==1)(Stack[top].di=di;top++;Suck[top].i=i;Stackftop].j=j；Stack[top].di=—1;mg[i])else(mg[Stack[topJ.iJ[Stack[(op].j]=0；top)}Printf("\n");printf("最短途徑如下:\n")；printf("途徑最短長(zhǎng)度:％d\n",min)：printf("最短途徑途徑:\n");for(k=0;k<