課程設(shè)計(jì)迷宮問題

1、西安郵電學(xué)院數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告題 目： 迷宮問題院系名稱： 計(jì)算機(jī)學(xué)院 專業(yè)名稱： 軟件工程班 級(jí)： 1002班 學(xué)生姓名： 吳云漢學(xué)號(hào)（8位）： 04103071指導(dǎo)教師： 王 燕設(shè)計(jì)起止時(shí)間：2011年11月28日2011年12月11日一：設(shè)計(jì)目的僅僅認(rèn)識(shí)到隊(duì)列是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使學(xué)生深入了解隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它，同時(shí)還將鞏固這種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法二. 設(shè)計(jì)內(nèi)容1.迷宮的建立：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述，2.迷宮的存儲(chǔ)：迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷

2、宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組Mazemaxsizemaxsize,然后用它的前m行n列來存放元素，即可得到一個(gè)mn的二維數(shù)組。 3.迷宮路徑的搜索：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列

3、中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑三概要設(shè)計(jì)1功能模塊圖maze creat()int found(int x,int y,Point *head)Point *secret(maze a) int print(Point *p) printmazepath(Point *p,maze road)void main()2. 各個(gè)模塊詳細(xì)的功能描述maze creat()/創(chuàng)建迷宮數(shù)組int found(int x,int y,Point *head)Point *secret(

4、maze a)/尋找迷宮出路函數(shù)int print(Point *p)/輸出迷宮路徑printmazepath(Point *p,maze road)/路徑圖void main()/主函數(shù)部分四詳細(xì)設(shè)計(jì)1功能函數(shù)的調(diào)用關(guān)系圖2重點(diǎn)設(shè)計(jì)及編碼尋找迷宮出路函數(shù)Point *secret(maze a)/ Point *top,*p;/定義top入口、p為出口 int j,m,x,y;/j表示四個(gè)方向;m用來輔助j的循環(huán)判斷條件 p=(Point *)malloc(sizeof(Point);/申請(qǐng)空間存放p p-vex_x=1; p-vex_y=1;/初始化行列數(shù)值 p-next=NULL;/置空

5、top=p;/將p的值賦給top j=1;/方向 do while(jvex_x; y=top-vex_y; switch(j) case 1:if(y+1vex_x=x;p-vex_y=y+1;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整下一步方向 top=p;m=1; break; case 2:if(x+1vex_x=x+1;p-vex_y=y;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整方向 top=p;m=1; break; case 3:if(y-1vex_x=x;p-vex_y=y-1;/控制行列

6、 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整方向 top=p;m=1; break; case 4:if(x-1vex_x=x-1;p-vex_y=y;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整方向 top=p;m=1; break; if(m!=0) j=1;break; else j+; /whileif(j4)/控制j的值和控制跳出條件 if(top!=NULL) top=top-next; if(top=NULL)return NULL; j=top-direction+1;top-direction=j; w

7、hile(top-vex_x!=a.maze_x|top-vex_y!=a.maze_y);/dowhile探索條件 if(top-vex_x=a.maze_x&top-vex_y=a.maze_y)top-direction=0;/判斷是否到達(dá)頂點(diǎn) return top;五測試數(shù)據(jù)及運(yùn)行結(jié)果1 正常測試數(shù)據(jù)和運(yùn)行結(jié)果2異常測試數(shù)據(jù)及運(yùn)行結(jié)果六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)1改進(jìn)方案在調(diào)試過程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多條或不是最短路徑，所以改用其他算法。2體會(huì)1. 對(duì)棧的理解還不夠透徹，有些地方的改進(jìn)是請(qǐng)教同學(xué)幫忙實(shí)現(xiàn)的.2. 了解數(shù)據(jù)結(jié)構(gòu)在編寫比較復(fù)雜的程序的重要作用.七參考文

8、獻(xiàn)數(shù)據(jù)結(jié)構(gòu)-C語言描述 耿國華 數(shù)據(jù)結(jié)構(gòu)案例精編-清華大學(xué)出版社C語言程序設(shè)計(jì)-科學(xué)出版社 王曙燕八附錄：源代碼（電子版）#include#include#define maxsize 100/迷宮的最大行列數(shù)typedef struct int Mazemaxsizemaxsize;/迷宮數(shù)組 int maze_x,maze_y;/迷宮的行和列maze;typedef struct point int vex_x,vex_y; int direction;/方向 struct point *next;/遞歸定義point指向下一個(gè)結(jié)點(diǎn) Point;maze creat()/創(chuàng)建迷宮數(shù)組 in

9、t i,j; maze a;/用a表示迷宮數(shù)組maze printf(迷宮的行數(shù)和列數(shù):);/迷宮的行數(shù)和列數(shù) scanf(%d%d,&a.maze_x,&a.maze_y);printf(|用0表示迷宮中的通路、1表示迷宮中的障礙!|n); for(i=1;i=a.maze_x;i+)/創(chuàng)建迷宮、給迷宮賦值 printf(輸入第%d行:,i); for(j=1;jvex_x&y=p-vex_y) return 1; p=p-next; return 0;Point *secret(maze a)/尋找迷宮出路函數(shù) Point *top,*p;/定義top入口、p為出口 int j,m,x,y

10、;/j表示四個(gè)方向;m用來輔助j的循環(huán)判斷條件 p=(Point *)malloc(sizeof(Point);/申請(qǐng)空間存放p p-vex_x=1; p-vex_y=1;/初始化行列數(shù)值 p-next=NULL;/置空top=p;/將p的值賦給top j=1;/方向 do while(jvex_x; y=top-vex_y; switch(j) case 1:if(y+1vex_x=x;p-vex_y=y+1;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整下一步方向 top=p;m=1; break; case 2:if(x+1vex_x=x+1;p-

11、vex_y=y;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整方向 top=p;m=1; break; case 3:if(y-1vex_x=x;p-vex_y=y-1;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整方向 top=p;m=1; break; case 4:if(x-1vex_x=x-1;p-vex_y=y;/控制行列 p-next=top;/調(diào)整新出口 top-direction=j;/調(diào)整方向 top=p;m=1; break; if(m!=0) j=1;break; else j+; /whil

12、eif(j4)/控制j的值和控制跳出條件 if(top!=NULL) top=top-next; if(top=NULL)return NULL; j=top-direction+1;top-direction=j; while(top-vex_x!=a.maze_x|top-vex_y!=a.maze_y);/dowhile探索條件 if(top-vex_x=a.maze_x&top-vex_y=a.maze_y)top-direction=0;/判斷是否到達(dá)頂點(diǎn) return top;int print(Point *p)/輸出迷宮路徑 int i=0,top=0; Point *stac

13、kmaxsize;/輸出的數(shù)組 if(p=NULL) printf(您輸入的迷宮不能到達(dá)出口!n); return 0; else printf(輸出路徑:n); while(p!=NULL)/入棧 stacktop+=p; p=p-next; while(top0)/出棧 top-; printf(%d,%d,%d),stacktop-vex_x,stacktop-vex_y,stacktop-direction); i+; if(i%8=0)printf(n); printf(n); return 1;void printmazepath(Point *p,maze road)/路徑圖 i

14、nt i,j; char mmaxsizemaxsize;/路徑圖數(shù)組 printf(路徑圖是:n); for(i=1;i=road.maze_x;i+) for(j=1;jdirection)/方向箭頭case 0:mp-vex_xp-vex_y=15;break;/到達(dá)case 1:mp-vex_xp-vex_y=26;break;/case 2:mp-vex_xp-vex_y=25;break;/case 3:mp-vex_xp-vex_y=27;break;/case 4:mp-vex_xp-vex_y=24;break;/p=p-next;for(i=1;i=road.maze_x;i+)for(j=1;j=road.maze_y