迷宮問(wèn)題課程設(shè)計(jì)報(bào)告

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

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

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

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

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

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

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

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

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

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

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

12、ntf(%d,z); 此語(yǔ)句用來(lái)標(biāo)明列號(hào)用 for 控制循環(huán) 在第一重循環(huán)里，使用語(yǔ)句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;下一

13、位置在上else 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是輸出“”另外在輸出語(yǔ)句上，與矩陣輸出相同，標(biāo)明了行號(hào)與列號(hào)（該功能為王教授所要求而后加的） 3.主函數(shù)void menu()定義迷宮數(shù)組矩陣mazeM+2N+2定義輔助數(shù)組abcM+2N+2 以用來(lái)在可以在第一次產(chǎn)生迷宮中重復(fù)選擇入口與出口定義變量k以用來(lái)控制循環(huán) 定義整型變量 x1，y1 ，用于

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

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

16、 打印出的迷宮路徑6，輸入一個(gè)非“0”繼續(xù) 圖8 輸入非“0”繼續(xù)走該迷宮7，輸入入口與出口，無(wú)通路 圖9 無(wú)通路附錄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;/定義一個(gè)棧int backupM+2N+2; /備份數(shù)組/*建立迷宮矩陣*/void create(int mazeN+2)/建立迷宮int i,j,flag;srand( (u

17、nsigned)time( NULL ) ); /以時(shí)間產(chǎn)生隨機(jī)種子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,手動(dòng)建立n2,自動(dòng)建立n請(qǐng)輸入您的選擇：n);scanf(%d,&flag);if(flag=1)/手動(dòng)建立迷宮printf(手動(dòng)建立迷宮矩陣(0表示可通1表示障礙):n);for(i=1;i=M;i+)for(j=1;j=N;j+)scanf(%d,&

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

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

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

21、Mlink *)malloc(sizeof(Mlink);p-row=stack-row;p-col=stack-col+1;p-next=stack; /入棧stack=p;mazestack-rowstack-col=1;/標(biāo)記已訪問(wèn)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;/標(biāo)記已訪問(wèn) else if(mazestack-

22、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;/標(biāo)記已訪問(wèn)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、/標(biāo)記已訪問(wèn)else /不可通 返回上一點(diǎn)if (stack-next!=NULL)/堆棧里布置一個(gè)頂點(diǎn)則出棧并返回循環(huán)p=stack;stack=stack-next; /出棧free(p); /釋放空間else /堆棧里只有一個(gè)頂點(diǎn)即入口，此時(shí)若釋放空間出棧會(huì)使循環(huán) /控制語(yǔ)句無(wú)法比較（因?yàn)閟tack-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);/*輸出坐標(biāo)通

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

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

26、intf(%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; whi