深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)

1、數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)課課程程設(shè)設(shè)計(jì)計(jì)報(bào)報(bào)告告深度與廣度優(yōu)先搜索：迷宮問深度與廣度優(yōu)先搜索：迷宮問題題的設(shè)計(jì)的設(shè)計(jì)目目 錄錄1 設(shè)計(jì)內(nèi)容.12 設(shè)計(jì)分析.13 設(shè)計(jì)實(shí)踐.34 測試方法.45 程序運(yùn)行效果.66 設(shè)計(jì)心得.87 附錄.9數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2017）1深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)1 設(shè)計(jì)內(nèi)容 一般的迷宮可表示為一個(gè)二維平面圖形，將迷宮的左上角作入口，右下角作出口。迷宮問題求解的目標(biāo)是尋找一條從入口點(diǎn)到出口點(diǎn)的通路。例如，可以設(shè)計(jì)一個(gè)8*8矩陣maze88來表示迷宮，如下所示：0 1 0 0 0 0 1 10 0 0 1 0 0 1 01 0

2、1 0 1 0 1 11 0 1 0 1 1 0 10 1 1 1 1 1 1 01 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 左上角maze00為起點(diǎn)，右下角maze77為終點(diǎn)；設(shè)“0”為通路， “1”為墻，即無法穿越。假設(shè)一只老鼠從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上，下，左，右，左上，左下，右上，右下”8個(gè)方向行走。 設(shè)計(jì)一個(gè)程序，能自動(dòng)生存或者手動(dòng)生成這樣一個(gè)8*8矩陣，針對(duì)這個(gè)矩陣，程序判斷是否能從起點(diǎn)經(jīng)過迷宮走到終點(diǎn)。如果不能，指出；如果能，用圖形界面標(biāo)出走出迷宮的路徑。2 設(shè)計(jì)分析首先明確題目中的已知條件：（1） 迷宮是一個(gè) 8*

3、8 大小的矩陣。（2） 從迷宮的左上角進(jìn)入，右下角為迷宮的終點(diǎn)。mazeij=0 代表第 i+1 行第 j+1 列的點(diǎn)是通路；mazeij=1 代表該點(diǎn)是墻，無法通行。（3） 迷宮有兩種生成方式：手工設(shè)定和自動(dòng)生成。（4） 當(dāng)老鼠處于迷宮中某一點(diǎn)的位置上，它可以向 8 個(gè)方向前進(jìn)，分別是：“上、下、左、右、左上、左下、右上、右下”8 個(gè)方向。 要實(shí)現(xiàn)這個(gè)程序，首先要考慮如何表示這個(gè)迷宮。在實(shí)例程序中使用二維數(shù)組mazeN+2N+2來表示這個(gè)迷宮，其中 N 為迷宮的行，列數(shù)。當(dāng)值為“0”時(shí)表示該點(diǎn)是通路，當(dāng)值為“1”時(shí)表示該點(diǎn)是墻。老鼠在迷宮中的位置在任何時(shí)候都可以由行號(hào) row 和列號(hào) col

4、 表示。 為什么指定 mazeN+2N+2來表示迷宮，而不是使用 mazeNN來表示迷宮？原因是當(dāng)老鼠跑到迷宮的邊界點(diǎn)時(shí)就有可能跳出迷宮，而使用 mazeN+2N+2就可以把迷宮的外面再包一層“1” ，這樣就能阻止老鼠走出格。 老鼠在每一點(diǎn)都有 8 種方向可以走，分別是：North，NorthEast，East，SouthEast，South，SouthWest，West，NorthWest?？梢杂脭?shù)組 move8來表示在每一個(gè)方向上的橫縱坐標(biāo)的偏移量，見表 3.1。根據(jù)這個(gè)數(shù)組，就很容易計(jì)算出沿某個(gè)方向行走的下一點(diǎn)的坐標(biāo)。深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)2表 3.1 8 種方向 move

5、的偏移量NameDirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW7-1-1迷宮問題可以用深度優(yōu)先搜索方法實(shí)現(xiàn)。當(dāng)老鼠在迷宮中移動(dòng)的時(shí)候，可能會(huì)有多種移動(dòng)方向。程序需要記錄并用棧來保存當(dāng)前點(diǎn)的坐標(biāo)，然后任意任取一個(gè)方向進(jìn)行移動(dòng)。由于應(yīng)用棧保存了當(dāng)前通道上各點(diǎn)的坐標(biāo)，所以當(dāng)在當(dāng)前各方向上走不通時(shí)可以返回上一個(gè)點(diǎn)，然后選擇另一個(gè)方向前進(jìn)?？啥xelement結(jié)構(gòu)用于存儲(chǔ)每一步的橫縱坐標(biāo)和方向。Typedef struct short int row; short int col; short int dir;eleme

6、nt;element stackMAX_STACK_SIZE；根據(jù)表3.1 可推算出每次移動(dòng)后的坐標(biāo)。設(shè)當(dāng)前點(diǎn)的坐標(biāo)是（row,col） ，移動(dòng)方向是dir,移動(dòng)后的點(diǎn)是next,則有next_row=-row+movedir.vert;next_col=col+movedir.horiz;可用另一個(gè)二維數(shù)組markN+2N+2來記錄哪些點(diǎn)已經(jīng)被訪問過。當(dāng)經(jīng)過點(diǎn)mazerowcol時(shí)，相應(yīng)地將markrowcol的值從0置1。本程序支持自動(dòng)生存迷宮。利用random（2）函數(shù)可隨機(jī)產(chǎn)生0或1，來支持迷宮的自動(dòng)生存。注意mazeNN和maze11一定要等于0，因?yàn)樗鼈兎謩e是起點(diǎn)和終點(diǎn)。如果找到了

7、一條走出迷宮的路徑，則需要在屏幕中打印出如圖3.5所示格式的信息。這里要用到graphices.h，即TC中的圖形庫。程序的主要函數(shù)如下：函數(shù)void add(int *top,element item)，將當(dāng)前步的信息item壓入到作為全局變量的棧stack(棧頂為top)中。函數(shù)elemrnt delete(int *top)，返回stack中棧頂?shù)脑?。?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2017）3函數(shù)void path(void)，采用深度優(yōu)先搜索算法，首先取出棧頂元素作為當(dāng)前點(diǎn)，并從當(dāng)前點(diǎn)選擇一個(gè)方向前進(jìn)到下一個(gè)點(diǎn)（如果能走得話） ；然后，將下一個(gè)點(diǎn)壓入棧，并將二維數(shù)組mark中對(duì)應(yīng)的值改為1，

8、表示該點(diǎn)已經(jīng)走到了。反復(fù)執(zhí)行上面兩步，當(dāng)走到一個(gè)點(diǎn)不能再走下去了，并且這個(gè)點(diǎn)不是終點(diǎn)，則這個(gè)點(diǎn)的上一個(gè)點(diǎn)會(huì)從棧中被拋出，從而“回溯”到上一個(gè)點(diǎn)；當(dāng)遇到終點(diǎn)時(shí)，程序結(jié)束，找到一條路徑；當(dāng)在程序循環(huán)過程中遇到棧為空，則說明該迷宮根本無法走到終點(diǎn)。3 設(shè)計(jì)實(shí)踐3.1 結(jié)構(gòu)體記錄水平和垂直的偏移量typedef struct short int vert;short int horiz;offsets;offsets move8; /* 8 個(gè)方向的 move*/int mazeN+2N+2;/*二維數(shù)組記錄迷宮*/int markN+2N+2;/*記錄迷宮中每點(diǎn)是否可到達(dá)*/int EXIT_ROW

9、 = N, EXIT_COL = N;3.2 輸出走出迷宮的路徑void path(void) int i, j, k, row, col, next_row, next_col, dir, found = FALSE; int gd=VGA; int gm=VGAHI;/*-*|i - 用來循環(huán)計(jì)數(shù) |row , col - 當(dāng)前位置的坐標(biāo) |next_row - 移動(dòng)后的位置的橫坐標(biāo) |next_col - 移動(dòng)后的位置的縱坐標(biāo)|dir - 移動(dòng)的方向 |found - 標(biāo)志路徑是否發(fā)現(xiàn) |*-*/ element position; int top = 0; mark11 = 1; /*

10、 maze11已經(jīng)被走過了*/ stack0.row = 1; stack0.col = 1; stack0.dir = 1; /*第一步的狀態(tài)*/ move0.vert = -1; move0.horiz = 0 ; move1.vert = -1; move1.horiz = 1 ;深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)4 move2.vert = 0 ; move2.horiz = 1 ; move3.vert = 1 ; move3.horiz = 1 ; move4.vert = 1 ; move4.horiz = 0 ; move5.vert = 1 ; move5.horiz = -

11、1; move6.vert = 0 ; move6.horiz = -1; move7.vert = -1; move7.horiz = -1; initgraph(&gd,&gm,); /* 指定了八個(gè)方向*/ /*-* | 主要算法描述: | | 當(dāng) stack 不為空,移動(dòng)到 stack 頂部的位置 | | 試著向各個(gè)方向移動(dòng)，如果可以移動(dòng)就移動(dòng)到 | 下一個(gè)位置并把它標(biāo)志成 1。 | | 然后保存狀態(tài)并加入到 stack 中 | | 如果路徑被破壞，或者不存在，就將其刪除 | | 并返回到上一點(diǎn)繼續(xù)遍歷其他方向的點(diǎn) | | 直到一條路徑被發(fā)現(xiàn)。 | *-*/4 測試方法

12、 針對(duì)迷宮生成方式不同，本程序的測試分為兩類：手動(dòng)輸入迷宮測試和計(jì)算機(jī)自動(dòng)生成迷宮測試。另外，根據(jù)測試用例類型不同也可分為兩類：有解迷宮測試和無解迷宮測試。 下面給出兩個(gè)測試用例。測試用例 1（有解迷宮）：0 1 1 1 1 0 1 00 0 0 1 0 1 0 11 0 1 0 0 1 1 01 0 1 1 0 1 0 01 0 0 1 0 1 1 00 1 1 0 1 1 1 10 1 0 1 0 1 1 11 1 1 1 0 0 0 0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2017）5其期望輸出結(jié)果如圖所示。測試用例 2;（無解迷宮）0 1 0 0 0 1 1 11 0 0 1 1 0 1 00 0 1

13、 0 1 1 0 11 0 1 0 0 1 0 00 0 0 1 0 1 1 10 0 1 0 1 1 0 00 0 0 0 0 1 0 00 1 0 1 1 1 1 0深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)6其期望輸出結(jié)果如圖所示。5 程序運(yùn)行效果測試用例 1（有解迷宮）：0 1 1 1 1 0 1 00 0 0 1 1 1 0 11 0 1 0 0 1 1 01 0 1 1 0 1 0 01 0 0 1 0 1 1 00 1 1 0 1 1 1 10 1 0 1 0 1 1 11 1 1 1 0 0 0 0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2017）7其期望輸出結(jié)果如圖所示。測試用例 2;（無解迷宮）0

14、1 0 0 0 1 1 11 0 1 1 0 0 1 00 1 1 0 0 1 1 11 0 1 1 0 0 0 00 1 0 1 0 1 1 00 1 1 0 1 0 0 00 0 1 1 0 0 1 11 1 0 1 0 1 1 0深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)8其期望輸出結(jié)果如圖所示。6 設(shè)計(jì)心得通過這五天的課程設(shè)計(jì)里，也讓我從中有所獲，此次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)使我對(duì)深度和廣度優(yōu)先搜索有了更加深刻的了解，迷宮問題的課程設(shè)計(jì)就是充分的利用深度和廣度優(yōu)先搜索的有關(guān)知識(shí)。剛開始用 C 語言編寫，碰到了一個(gè)很大的問題，調(diào)試了很多次，在 VC 里執(zhí)行不出來。 “#include” ，這其實(shí)是 TC

15、 里的一個(gè)圖形庫，在 VC 里編譯時(shí)不行的，會(huì)顯示有一個(gè)錯(cuò)誤。但在 TC 里也碰到問題了，代碼不能完全輸入到編輯器中，導(dǎo)致最后還是無法運(yùn)行。最后找了相關(guān)的代碼，安裝了相關(guān)圖形文件進(jìn)去，試了試，終于運(yùn)行成功。這次課程設(shè)計(jì)讓我受益匪淺，對(duì)數(shù)據(jù)結(jié)構(gòu)也有進(jìn)一步的理解和認(rèn)識(shí)。但也讓我認(rèn)識(shí)到我還有很多的不足，今后需要多實(shí)踐和學(xué)習(xí)，提高能力和熟練應(yīng)用。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2017）97 附錄附錄#include #include #include #define N8#define MAX_STACK_SIZEN*N/*最大棧容量 */#define TRUE1#define FALSE0#define

16、LEN(300/N)/*結(jié)構(gòu)體記錄每一步的橫坐標(biāo)，縱坐標(biāo)和方向*/typedef struct short int row;short int col;short int dir;element;element stackMAX_STACK_SIZE;/*結(jié)構(gòu)體記錄水平和垂直的偏移量*/typedef struct short int vert;short int horiz;offsets;offsets move8; /* 8 個(gè)方向的 move*/int mazeN+2N+2;/*二維數(shù)組記錄迷宮*/int markN+2N+2;/*記錄迷宮中每點(diǎn)是否可到達(dá)*/int EXIT_ROW

17、= N, EXIT_COL = N;/*在棧中加入一個(gè)元素*/void add(int *top, element item)if (*top = MAX_STACK_SIZE - 1)printf(The stack is full!n);return; stack+*top = item;/*返回棧中頂部的元素*/element delete(int *top)if (*top = -1)printf(The stack is empty ! n);exit(1); return stack(*top)-;深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計(jì)10/*輸出走出迷宮的路徑*/void path(

18、void) int i, j, k, row, col, next_row, next_col, dir, found = FALSE; int gd=VGA; int gm=VGAHI;/*-*|i - 用來循環(huán)計(jì)數(shù) |row , col - 當(dāng)前位置的坐標(biāo) |next_row - 移動(dòng)后的位置的橫坐標(biāo) |next_col - 移動(dòng)后的位置的縱坐標(biāo)|dir - 移動(dòng)的方向 |found - 標(biāo)志路徑是否發(fā)現(xiàn) |*-*/ element position; int top = 0; mark11 = 1; /* maze11已經(jīng)被走過了*/ stack0.row = 1; stack0.col

19、 = 1; stack0.dir = 1; /*第一步的狀態(tài)*/ move0.vert = -1; move0.horiz = 0 ; move1.vert = -1; move1.horiz = 1 ; move2.vert = 0 ; move2.horiz = 1 ; move3.vert = 1 ; move3.horiz = 1 ; move4.vert = 1 ; move4.horiz = 0 ; move5.vert = 1 ; move5.horiz = -1; move6.vert = 0 ; move6.horiz = -1; move7.vert = -1; move7

20、.horiz = -1; initgraph(&gd,&gm,); /* 指定了八個(gè)方向*/ /*-* | 主要算法描述: | | 當(dāng) stack 不為空,移動(dòng)到 stack 頂部的位置 | | 試著向各個(gè)方向移動(dòng)，如果可以移動(dòng)就移動(dòng)到 | 下一個(gè)位置并把它標(biāo)志成 1。 | | 然后保存狀態(tài)并加入到 stack 中 | | 如果路徑被破壞，或者不存在，就將其刪除 | | 并返回到上一點(diǎn)繼續(xù)遍歷其他方向的點(diǎn) | | 直到一條路徑被發(fā)現(xiàn)。 | *-*/ while ( top -1 & !found) /*stack 不為空*/ position = delete(&

21、;top); /*刪除 stack 中的元素*/ row = position.row; col = position.col; dir = position.dir;數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2017）11 while (dir 8 & !found) next_row = row + movedir.vert; next_col = col + movedir.horiz; if (next_row = EXIT_ROW & next_col = EXIT_COL) found = TRUE; /*發(fā)現(xiàn)路徑*/ else if ( !mazenext_rownext_col &

22、amp; !marknext_rownext_col) /*如果這點(diǎn)沒有被走過并且可以走*/ marknext_rownext_col = 1; /*設(shè)成 1*/ position.row = row; position.col = col; position.dir = +dir; add(&top, position); /*加入到 stack*/ row = next_row; col = next_col; dir = 0; /* 移動(dòng)到下一個(gè)點(diǎn) */ else +dir; /*嘗試其他方向*/ for(j=1;j=N;j+) for(k=1;k=N;k+) setcolor(WHITE); circle(j*LEN,k*LEN,10); setcolor(MAGENTA); outtextxy(j*LEN-2,k*LEN-2,mazekj?1:0); if (found) /* 如果發(fā)現(xiàn)路徑，則打印出來*/ outtextxy(20,10,The path is:); setcolor(YELLOW); for (i=0; i top;i+) line(stacki.col*LEN, stacki.row*LEN,stacki+1.col*LEN,sta