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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(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 改進(jìn)3.1.4節(jié)中的求解迷宮問題程序，要求輸出如圖3.14所示的迷宮的所有路徑，并求最短路徑長(zhǎng)度及最短路徑。0 1 2 3 4 5 0 1 2 3 4 5出口入口（2）實(shí)驗(yàn)項(xiàng)目組成：本項(xiàng)目由一個(gè)原程序mg.cpp及mg.exe文件組成。（3）實(shí)驗(yàn)項(xiàng)目的程序結(jié)構(gòu)：main()struct結(jié)構(gòu)體mgpath()路徑函數(shù)函數(shù)調(diào)用關(guān)系圖：main()（4）實(shí)驗(yàn)項(xiàng)目包含的函數(shù)的功能描述：mgM+1N+1 /構(gòu)造迷宮二維數(shù)組，1表示墻不可走方塊，0表示通道

2、mgpath(int xi,int yi,int xe,int ye) /求解路徑為：（xi,yi）->（xe,ye）/采用順序棧存儲(chǔ)，進(jìn)棧，回溯，退棧等（5）算法描述：求解迷宮從入口到出口的所有路徑，從入口出發(fā)，順某一個(gè)方向向前試探，對(duì)于可走的方塊都進(jìn)棧，并將這個(gè)可走發(fā)方位保存，且top+1，然后試探下一個(gè)方塊，若下一個(gè)方塊能走通則繼續(xù)，否則則回溯到前一個(gè)方塊，且top-1。為記錄所有的路徑調(diào)用Pathk=Stackk記錄，從次方塊向不同方向去試探，已經(jīng)走過的方塊則為不可走方塊。最后比較top值找到一條最短路徑并輸出。試探路徑過程的算法利用了“廣度優(yōu)先搜索遍歷”算法。流程圖：mg=0回

3、溯mg=1進(jìn)棧循環(huán)for下一個(gè)方塊變成前一個(gè)方塊下一個(gè)方塊值mgij前一個(gè)方塊值mg=0下一個(gè)方塊值mg=0輸出方位坐標(biāo)( , )入口結(jié)束（6）實(shí)驗(yàn)數(shù)據(jù)：迷宮數(shù)組如下：int mgM+1N+1= 1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1;實(shí)驗(yàn)結(jié)果：三、程序代碼：#include <stdio.h>#include <stdlib.h>#define M 6#define N 6#define Maxsize 100int mgM+1N+1= 1,1,1,1,1,1,

4、1,0,0,0,1,1, 1,0,1,0,0,1, 1,0,0,0,1,1, 1,1,0,0,0,1, 1,1,1,1,1,1;struct int i; int j; int di; StackMaxsize,PathMaxsize;int top=-1;int count=1;int min=Maxsize;int mgpath() int i,j,di,find,k; top+; Stacktop.i=1; Stacktop.j=1; Stacktop.di=-1; mg11=-1; printf("迷宮所有路徑如下:n"); while(top>-1) i=S

5、tacktop.i;j=Stacktop.j;di=Stacktop.di; if(i=M-2&&j=N-2) printf("%4d:",count+); for(k=0;k<=top;k+) printf("(%d,%d)",Stackk.i,Stackk.j); if(k+1)%5=0) printf("n "); printf("n"); if(top+1<min) for(k=0;k<=top;k+) Pathk=Stackk; min=top+1; mgStacktop

6、.iStacktop.j=0; top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; find=0; while(di<4&&find=0) di+; switch(di) case 0:i=Stacktop.i-1;j=Stacktop.j;break; case 1:i=Stacktop.i;j=Stacktop.j+1;break; case 2:i=Stacktop.i+1;j=Stacktop.j;break; case 3:i=Stacktop.i;j=Stacktop.j-1;break; if(mgij=0)find=1; if(find=1) Stacktop.di=di; top+; Stacktop.i=i; Stacktop.j=j; Stacktop.di=-1; mgij=-1; else mgStacktop.iStacktop.j=0; top-; printf("n"); printf("最短路徑如下：n"); printf("路徑最短長(zhǎng)度：%dn",min); printf("最短路徑路徑：n"); for(k=0;k<min;k+) printf("(%d,%d)&quo