迷宮問題課程設(shè)計報告#參考資料

1、目 錄第一章: 設(shè)計問題描述與分析.11.1. 課程設(shè)計內(nèi)容.1 1.2. 問題分析.11.3功能實現(xiàn).21.4運行環(huán)境.3第二章: 算法設(shè)計與流程圖.42.1.主函數(shù)的流程圖.42.2.概要設(shè)計.52.4 詳細設(shè)計.6 2.4.1. 節(jié)點類型和指針類型.6 2.4.2. 迷宮的操作.6 （1）生成迷宮.6 （2）打印迷宮矩陣與字符圖形.7 （3）迷宮求解路由求解操作.7 （4）打印迷宮通路坐標.8 (5)輸出迷宮通路的字符圖形.8 2.4.3. 主函數(shù).9第三章：調(diào)試分析.10第四章：使用說明.11第五章：測試結(jié)果.12附錄1.19附錄2.19 嚴選內(nèi)容#第一章：設(shè)計問題描述與分析1.1.課

2、程設(shè)計內(nèi)容： 該系統(tǒng)是由C 語言編寫的生成一個NM(N行M列)的迷宮，完成迷宮的組織和存儲，并實現(xiàn)迷宮路由算法?；疽?、 N和M是用戶可配置的，缺省值為50和50。2、迷宮的入口和出口分別在左上角和右下角。提示：（1）可以使用二維數(shù)組mazeM+2N+2表示迷宮，其中M,N為迷宮的行、列數(shù)，當元素值為0時表示該點是通路，當元素值為1時表示該點是墻。老鼠在每一點都有4種方向可以走，可以用數(shù)組move4來表示每一個方向上的橫縱坐標的偏移量，可用另一個二維數(shù)組markM+2N+2記錄節(jié)點的訪問情況。（2）可以選用深度優(yōu)先算法或廣度優(yōu)先算法實行，迷宮可由自動或手動生成。測試用例應(yīng)該包含有解迷宮和無

3、解迷宮。1.2. 問題分析本程序要求實現(xiàn)迷宮問題的相關(guān)操作，包括迷宮的組織和存儲，并實現(xiàn)迷宮路由算法（即查找迷宮路徑）。程序所能達到的：具體包括迷宮的建立，迷宮的存儲（迷宮由自動生成或手動生成），迷宮中路徑的查找迷宮是一個矩形區(qū)域，迷宮存在一個入口和一個出口，其內(nèi)部包含了不能穿越的墻或者障礙。迷宮的建立即是建立這樣一個迷宮矩陣，用于存儲迷宮信息，包括可穿越的路和不可穿越的墻或者障礙，分別用0表示通路，1表示障礙。對于迷宮矩陣，用mn的矩陣來描述，m和n分別代表迷宮的行數(shù)和列數(shù)。這樣，則迷宮中的每個位置都可以用其行號和列號來指定。從入口到出口的路徑是由一組位置構(gòu)成的。每個位置上都沒有障礙，且每個

4、位置（第一個除外）都是前一個位置的上、下、左、右的鄰居。為了描述迷宮中位置（i ，j）處有無障礙，規(guī)定，當位置（i ，j）處有一個障礙時，其值為1，否則為0.這樣迷宮就可以用0、1矩陣來描述，在構(gòu)造矩陣時，為了操作方便會將矩陣四周置為1（不通）。對于查找迷宮路由問題首先，考察，迷宮的入口位置，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則，考察其上、下、左、右位置上的鄰居是否是障礙，若不是就移動到這個相鄰位置上，然后對于這個位置開始搜索通往出口的路徑。如果不成功，就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索出現(xiàn)重復(fù)，則將已搜索過的位置標記為1。同時為保留過搜索的痕跡

5、，在考察相鄰位置之前，將當前位置保存在一個堆棧中，如果所有相鄰的非障礙位置均被搜索過，且未能找到通往出口的路徑，則表明不存在從入口到出口的路徑。且對于此，實現(xiàn)的是深度優(yōu)先遍歷算法，如果查找到路徑，則為從入口到出口的路徑。下面實現(xiàn)如何利用堆棧實行深度優(yōu)先遍歷算法進行迷宮最短路徑的查找。以矩陣 1 1 1 1 1 1 11 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1首先，將位置（1，1）放入堆棧中，從它開始搜索，標記。由于其只有一個非障礙位置，所以接下來移動到（1，2），防止稍后的搜索再經(jīng)過這個位置。從（1

6、，2）移動到（2，2），放入堆棧中，（2，2）存在（2，3）、（3，2）兩個可移動位置。標記已被搜索過，對于每一個非障礙位置，它的相鄰非障礙節(jié)點均入隊列，實現(xiàn)了深度優(yōu)先遍歷算法。所以如果存在路徑，則從出口處節(jié)點的位置，逆序則可以找到其從出口到入口的通路。實現(xiàn)了查找路徑。1.3功能實現(xiàn)： 1、數(shù)據(jù)輸入形式和輸入值的范圍：生成迷宮時可選擇手動或者自動生成；手動輸入迷宮矩陣時以0 表示無障礙為通路，1 表示該點有障礙為墻。所有輸入中，元素的值均為整數(shù)。2、結(jié)果的輸出形式：當完成迷宮生成后，會提示輸入入口與出口，進入迷宮路由查找算法，如找到出口，則打印出路徑矩陣坐標，并顯示顯示迷宮生成圖形3、測試數(shù)據(jù)

7、：a、進入界面，選擇2，自動生成b、輸入入口與出口c、查看結(jié)果1.4運行環(huán)境： 運行環(huán)境為DOS第二章：算法設(shè)計與流程圖2.1.主函數(shù)的流程圖： 循環(huán)結(jié)束，無通路判斷入口是否為通路NY 將該位置入棧，并標記為1N棧不為空且棧頂非出口 棧頂為出口？NYYY棧頂位置下面可通？ 找出通路，鏈棧內(nèi)即為通路Y棧頂位置上面可通？NY 循環(huán)結(jié)束N棧頂位置右面可通？Y棧頂位置左面可通？N 棧頂出棧N 圖1迷宮算法流程圖 2.2概要設(shè)計 1、為了實現(xiàn)上述功能，需要：構(gòu)造一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣,構(gòu)造一個二維數(shù)組backupM+2N+2用于備份迷宮矩陣；自動或手動生成迷宮，即為二維數(shù)組ma

8、zeM+2N+2賦值并備份；將構(gòu)造一個堆棧用于存儲迷宮路由；建立迷宮節(jié)點struct Mlink，用于存儲迷宮中每個訪問過的節(jié)點。實現(xiàn)迷宮路由算法，用深度優(yōu)先遍歷實現(xiàn)查找迷宮路徑。如找到路徑則顯示路徑，否則提示無通路。同時顯示生成迷宮。在屏幕上顯示操作菜單。2、本程序包含6 個函數(shù)：( 1 )主函數(shù) main( )( 2 )生成迷宮函數(shù) create( )( 3 )打印迷宮矩陣與圖形函數(shù)prin( ) ( 4 )尋找迷宮路由Mazepath( ) ( 5 )輸出迷宮通路坐標printonglu1( ) ( 6 )輸出迷宮生成圖形printonglu2( ) 各函數(shù)之間的關(guān)系如下圖（圖2）所示：

9、 函數(shù)關(guān)系圖：create( ) prin( )main() Mazepath( )printonglu1( )printonglu2( )圖 2各函數(shù)間關(guān)系圖2.3詳細設(shè)計 實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型，對各個操作給出偽代碼算法。對于主程序和各個模塊也給出相應(yīng)的偽代碼算法。1.節(jié)點類型和指針類型迷宮矩陣類型：Mlink *stack; 全局變量堆棧，存儲迷宮通路int abcM+2N+2 輔助數(shù)組int mazeM+2N+2; 迷宮矩陣int backupM+2N+2; 備份矩陣，便于操作，定義為全局變量 迷宮中節(jié)點類型及隊列類型：struct Mlink int row ,col ;

10、struct node * next; Mlink;2.迷宮的操作(1)生成迷宮void create(int mazeN+2)定義變量i,j,flag;srand( (unsigned)time( NULL ) ) 以時間產(chǎn)生隨機種子利用for初始化迷宮矩陣與備份矩陣，包括邊界全置為1利用for將迷宮置為0選擇迷宮生成方式1為手動生成，2為自動生成，輸入值并賦給flagflag=1以i , j 控制迷宮中行列數(shù)的循環(huán)輸入以0 表示通路，以1 表示障礙,給mazeij賦值，不包括邊界。循環(huán)結(jié)束，完成迷宮生成flag=2定義變量i1，j1用以接收隨機值以i , j 控制迷宮中行列數(shù)的循環(huán)賦值操作

11、以0 表示通路，以1 表示障礙用for(c=1;c=M*N;c+) i1=(int)(rand()%M)+1;j1=(int)(rand()%N)+1; mazei1j1=int(rand()%2);隨機定位矩陣一點，給mazei1j1賦一個隨機值，這樣可以增加迷宮通路的概率，循環(huán)結(jié)束，完成迷宮生成以i , j 控制迷宮中行列數(shù)的循環(huán)賦值操作，將maze備份到backup;(2)打印迷宮矩陣與字符圖形void prin(int mazeN+2)此函數(shù)主要用于將迷宮矩陣顯示出來定義變量i，j，z；for(z=1;z=N;z+)if(z10)printf(%d ,z); else printf(%

12、d,z); 此語句用來標明列號用 for 控制循環(huán) 在第一重循環(huán)里，使用語句printf(n);if(inext(5)輸出迷宮通路的字符圖形void printonglu2()此函數(shù)根據(jù)堆棧內(nèi)棧頂與“次棧頂”的位置關(guān)系決定輸出字符，或，其中2=，3=，4=，5=所有的操作都是在備份矩陣backup上。出口位置輸出int i，z，j；Mlink *p=stack；p不空if(p-rowp-next-row) backupp-next-rowp-next-col=5; 下一位置在下else if(p-rownext-row) backupp-next-rowp-next-col=2;下一位置在上e

13、lse if(p-colp-next-col) backupp-next-rowp-next-col=4;下一位置在右else ;下一位置在左利用for循環(huán)，i，j為循環(huán)控制變量輸出備份矩陣backup為0是輸出“”為1是輸出“”為2是輸出“”為3是輸出“”為4是輸出“”為5是輸出“”為6是輸出“”另外在輸出語句上，與矩陣輸出相同，標明了行號與列號（該功能為王教授所要求而后加的） 3.主函數(shù)void menu()定義迷宮數(shù)組矩陣mazeM+2N+2定義輔助數(shù)組abcM+2N+2 以用來在可以在第一次產(chǎn)生迷宮中重復(fù)選擇入口與出口定義變量k以用來控制循環(huán) 定義整型變量 x1，y1 ，用于存儲入口。

14、定義整型變量 x2，y2 ，用于存儲出口。定義整型變量x用于接收mazepash的返回值。輸入入口與出口。如果x=1則條用函數(shù)printonglu1();printonglu2();否則提示無通路。界面開始會顯示：1,手動建立2,自動建立按提示操作，輸入入口與出口，回車即會看到結(jié)果 第三章：調(diào)試分析在調(diào)試過程中，開始用堆棧實現(xiàn)了路徑的查找并調(diào)試成功，但輸出的結(jié)果僅僅只是路徑坐標，看起來不形象，于是想到了用字符來表示圖形并標出通路，雖然不是太完美，但比之之前好好多了在實現(xiàn)這一算法過程，注意將訪問過的節(jié)點進行標記，并且在遍歷過程中對矩陣數(shù)組是“破壞性”遍歷，在算法完成后，矩陣已被破壞，堆棧中會存用

15、路徑，為了再原矩陣中用字符圖形表示出通路，在建立矩陣后會迷宮矩陣備份一下，當然或許會有更好的處理方法。 第四章：使用說明程序名為迷宮.exe，運行環(huán)境為DOS，程序執(zhí)行后顯示：建立迷宮矩陣(選擇1或者2)：1,手動建立2,自動建立進請輸入您的選擇：在輸入選擇后輸入數(shù)字選擇執(zhí)行不同的迷宮建立。按要求輸入入口與出口 第五章：測試結(jié)果1.主頁面 圖3 主頁面2.選擇自動建立 圖4 迷宮自動生成中3，自動生成迷宮，上面為數(shù)組矩陣，其中0可通，1障礙。下面為字符圖形，其中白色可通，黑色障礙 圖5 打印出的迷宮矩陣與迷宮圖形4，根據(jù)提示輸入入口與出口 圖6 輸入入口與出口5，回車后輸出路徑 圖7 打印出的

16、迷宮路徑6，輸入一個非“0”繼續(xù) 圖8 輸入非“0”繼續(xù)走該迷宮7，輸入入口與出口，無通路 圖9 無通路附錄1： 附錄2：源代碼：#include#include#include#include#define M 20#define N 20typedef struct node/堆棧結(jié)構(gòu)int row; /行int col; /列struct node * next;Mlink;Mlink *stack;/定義一個棧int backupM+2N+2; /備份數(shù)組/*建立迷宮矩陣*/void create(int mazeN+2)/建立迷宮int i,j,flag;srand( (unsign

17、ed)time( NULL ) ); /以時間產(chǎn)生隨機種子for(i=0;i=M+1;i+)for(j=0;j=N+1;j+)mazeij=1;/將四周置為1for(i=1;i=M;i+)for(j=1;j=N;j+)mazeij=0;/初始化矩陣backupij=0;/初始化備份矩陣printf(建立迷宮矩陣(選擇1或者2)：n1,手動建立n2,自動建立n請輸入您的選擇：n);scanf(%d,&flag);if(flag=1)/手動建立迷宮printf(手動建立迷宮矩陣(0表示可通1表示障礙):n);for(i=1;i=M;i+)for(j=1;j=N;j+)scanf(%d,&mazei

18、j); if(flag=2) /自動建立迷宮int c,i1,j1;for(c=1;c=M*N;c+) /矩陣初始為“0”，隨機選擇位置賦予一個隨機的0或1， i1=(int)(rand()%M)+1;j1=(int)(rand()%N)+1; mazei1j1=int(rand()%2); /隨機矩陣 按照王教授的要求這樣可以產(chǎn)生更多的“0”即通路printf(自動生成中n);system (pause);for(i=1;i=M;i+)for(j=1;j=N;j+)backupij=mazeij;/備份數(shù)組矩陣/*華麗的分割線*/*打印迷宮矩陣*/void prin(int mazeN+2)

19、int i,j;printf(迷宮矩陣如下(0可通)：n );int z;for(z=1;z=N;z+) /在矩陣上方標明列號if(z10)printf(%d ,z); else printf(%d,z);for(i=1;i=M;i+)printf(n); if(i10) printf(%d ,i); /矩陣左方標明行號else printf(%d,i);for(j=1;j=N;j+)printf(%d ,mazeij);printf(n迷宮圖形如下(白色可通)：n);printf( );for(z=1;z=N;z+) /在圖形上方標明列號if(z10)printf(%d ,z); else

20、printf(%d,z);for(i=1;i=M;i+)printf(n);if(i10) printf(%d ,i); /矩陣左方標明行號else printf(%d,i);for(j=1;jrow=x1;p-col=y1;p-next=NULL;stack=p; /將入口放入堆棧mazestack-rowstack-col=1;/標志入口已訪問while(!(stack-row=NULL&stack-col=NULL)&(!(stack-row=x2&stack-col=y2)/未找到出口并且堆棧不空if(mazestack-rowstack-col+1=0)/下面位置可通p=(Mlink

21、 *)malloc(sizeof(Mlink);p-row=stack-row;p-col=stack-col+1;p-next=stack; /入棧stack=p;mazestack-rowstack-col=1;/標記已訪問else if(mazestack-rowstack-col-1=0)/上面可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row;p-col=stack-col-1;p-next=stack; /入棧stack=p;mazestack-rowstack-col=1;/標記已訪問 else if(mazestack-row+1

22、stack-col=0)/右面可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row+1;p-col=stack-col;p-next=stack; /入棧stack=p;mazestack-rowstack-col=1;/標記已訪問else if(mazestack-row-1stack-col=0)/左面可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row-1;p-col=stack-col;p-next=stack; /入棧stack=p;mazestack-rowstack-col=1;/標記已訪

23、問else /不可通 返回上一點if (stack-next!=NULL)/堆棧里布置一個頂點則出棧并返回循環(huán)p=stack;stack=stack-next; /出棧free(p); /釋放空間else /堆棧里只有一個頂點即入口，此時若釋放空間出棧會使循環(huán) /控制語句無法比較（因為stack-col,stack-row都已不存在，)stack-row=NULL;stack-col=NULL;stack-next=NULL;if (stack-row=x2&stack-col=y2) return (1);else return (0);else return(0);/*輸出坐標通路*/vo

24、id printonglu1() Mlink *q;printf(其中的一條通道為：n); q=stack; printf(出口-); while (q!=NULL) printf(%d%3d)row,q-col);q=q-next; printf(入口n);/*分割線*/*輸出圖形通路*/2時輸出，3時輸出，4時輸出，5時輸出void printonglu2()printf(圖形通路如下：n);int z;printf( );for(z=1;z=N;z+) /圖形上方標明列號if(zrowp-col=6;while (p-next!=NULL)if(p-next-col!=NULL)if(

25、p-row p-next-row ) backupp-next-rowp-next-col=5;/下一節(jié)點在下else if(p-rownext-row) backupp-next-rowp-next-col=2;/下一節(jié)點在上else if(p-colp-next-col) backupp-next-rowp-next-col=4;/下一節(jié)點在右else backupp-next-rowp-next-col=3;/下一節(jié)點在左else ;p=p-next;for(i=1;i=M;i+)printf(n);if(i10) printf(%d ,i); /圖形左方標明行號else printf(

26、%d,i);for(j=1;j=N;j+)if(backupij=0) printf();if(backupij=1) printf();if(backupij=2) printf();if(backupij=3) printf();if(backupij=4) printf();if(backupij=5) printf();if(backupij=6) printf();void main() system(color f0); /背景該為白色 int k=1; int mazeM+2N+2;/迷宮矩陣 create(maze); /建立迷宮 int abcM+2N+2,p,q; /備份數(shù)組以重復(fù)使用迷宮 for(p=0;p=M+2;p+) for(q=0;q=N+2;q+) abcpq=mazepq; while(k!=0) int x,x1,