數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問題專業(yè)軟件工程班級(jí)B軟件121學(xué)號(hào)1210701128學(xué)生姓名設(shè)計(jì)題H設(shè)計(jì)分析設(shè)計(jì)實(shí)現(xiàn)4測(cè)試方法4.1測(cè)試目的4.2測(cè)試輸入4.3正確輸出4.4實(shí)際輸出 14.5錯(cuò)誤原因（若無錯(cuò)誤此節(jié)可以省略）115分析與探討115.1測(cè)試結(jié)果分析115.2探討與改進(jìn)116設(shè)訃小結(jié)111設(shè)計(jì)題目a）迷宮問題求解的目標(biāo)：尋找一條從入口點(diǎn)到出口點(diǎn)的通路。（迷宮可表示為一 個(gè)二維平面圖形，將迷宮的左上角作入口，右下角作出口。）例如，可以設(shè)計(jì)一個(gè)8*8 矩陣maze88來表示迷宮，如下所示：0 10000 1 1000 1001010101011101011010111111

2、01 00 1 10001 0 1 0001 11 0 1 10 100左下角maze00為起點(diǎn),右下角maze77為終點(diǎn);設(shè)“0”為通路，T 為 墻，既無法穿越。假設(shè)一只老鼠從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上、下、 左、右、左上、左下、右上、右下” 8個(gè)方向行走。b）設(shè)計(jì)程序要求：能自動(dòng)生成或者手動(dòng)生成這樣一個(gè)8*8矩陣；針對(duì)這個(gè)矩陣， 程序判斷是否能從起點(diǎn)經(jīng)過迷宮走到終點(diǎn)。如果不能，請(qǐng)指出；如果能，請(qǐng)用圖形 界面標(biāo)出走出迷宮的路徑。2設(shè)計(jì)分析a）首先明確題中的已知條件：迷宮是一個(gè)8*8大小的矩陣。從迷宮的左上角進(jìn)入，右下角為迷宮的終點(diǎn)。mazeij=0代表第i+1行第j+1列的點(diǎn)是通路

3、：mazeij=l代表該點(diǎn)是墻，無 法通行。迷宮有兩種生成方式：手工設(shè)定和自動(dòng)生成。當(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表示。b) 為什么指定mazeN+2N+2表示迷宮，而不是使用mazeNN來表示迷宮？ 原因是當(dāng)老鼠跑到迷宮的邊界點(diǎn)時(shí)就有可能跳出迷宮；而使用ma

4、zeN+2N+2就可以把迷宮的外面再包一層“1”，這樣就能阻止老鼠走出格。c) 老鼠再每一點(diǎn)都有8種方向可以走，分別是：North , NorthEast,East,SouthEast,East,South,SouthWest,West,NorthWest.可以用數(shù)組m ove8 來表示在每一個(gè)方向上的橫縱坐標(biāo)的偏移量，見表21。根據(jù)這個(gè)數(shù)組，就很容易 計(jì)算出沿某個(gè)方向行走后的下一點(diǎn)的坐標(biāo)。NamedirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW511W601NW6)1表21 8種方向move的偏移量d) 迷宮問題可以用深度優(yōu)先搜索方

5、法實(shí)現(xiàn)。當(dāng)老鼠當(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)前各方 向上都走不通時(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;(element;Element stackMAX _STACK_SIZE;根據(jù)表21可推算出每次移動(dòng)后的坐標(biāo)。設(shè)當(dāng)前的坐標(biāo)是(row,col),移動(dòng)的方向是 dir,移動(dòng)后的點(diǎn)是

6、next,則有 next_row=row+movedir .vert;next_col=col+movedir.horiz;可用另一個(gè)二維數(shù)組markN+2來記錄哪些點(diǎn)已經(jīng)被訪問過。當(dāng)經(jīng)過點(diǎn)mazerowcol時(shí),相應(yīng)地將markrowcol的值從0置為 1。e) 本程序支持自動(dòng)生成迷宮。利用random(2)函數(shù)可隨機(jī)產(chǎn)生0或1,來支持迷宮 的自動(dòng)生成。注意mazeNN和mazell定要等于0,因?yàn)樗麄兎謩e是起點(diǎn)和終 點(diǎn)。f) 如果找到了一條走出迷宮的路徑，則需要在屏幕中打印出走出迷宮的信息。 這里要用到graphics.ho為畫出效果圖，可使用circle()函數(shù)畫圓，outtexttxy

7、O函數(shù)標(biāo) 記文字，并用line()函數(shù)來劃線。g) 程序的主要函數(shù)如下：函數(shù)void add(int*top,element item),將當(dāng)前步的信息item壓入到作為全局變量 的棧stack(棧頂為top)中。函數(shù)element delete(int * top),返回stack中棧頂?shù)脑?。函?shù)void path(void),采用深度優(yōu)先搜索算法，首先取岀棧頂元素作為當(dāng)前點(diǎn) 選擇一個(gè)方向前進(jìn)到下一個(gè)點(diǎn)(如果能走得話)；然后，將下一個(gè)點(diǎn)壓入棧，并將 二維數(shù)組mark中對(duì)應(yīng)的值改為1,表示該點(diǎn)已經(jīng)走到了。反復(fù)執(zhí)行上面兩步，當(dāng)走 到一個(gè)點(diǎn)不能再走下去了(已經(jīng)嘗試了各個(gè)方向并失敗)，并且這個(gè)點(diǎn)不

8、是終點(diǎn)， 則這個(gè)點(diǎn)的上一個(gè)點(diǎn)會(huì)從棧中被跑拋出，從而''回朔”到上一點(diǎn)；當(dāng)遇到終點(diǎn)時(shí)， 程序結(jié)束，找到一條路徑；當(dāng)在程序循環(huán)過程中遇到棧為空，則說明該迷宮根本無 法走到終點(diǎn)。3設(shè)計(jì)實(shí)現(xiàn)/*This program can be compiled under VC6.0*/ #include <stdio.h>#include <stdlib.h>#include <graphics.h># include<time.h>#include<conio.h>8N*N/*最大棧容量*/10#define N#define MA

9、X_STACK_SIZE#define TRUE#define FALSE#define 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)體記錄水半和垂直的偏移量*/* 8個(gè)方向的move */*二維數(shù)組記錄迷宮勺/*記錄迷宮中每點(diǎn)是否可到達(dá)*/typedef struct short int vert; short int horiz; (offsets;offsets niov

10、e8;int mazeN+2N+2; int markN+2N+2;int EXIT_ROW = N, EXIT.COL = N;/*衫*在棧中力口入一個(gè)元素*；$:林/void add(int *top, element item) if (*top >= MAX_STACK_SIZE - 1) printf(HThe stack is full!nH);return;) stack+*top = item;/*返回棧中頂部的元素*/element delete_top(int *top) if (*top = -1)printf(nThe stack is empty ! nH);

11、exit(l);return stack(水top); /*輸出走出迷宮的路徑*/void path(void)int i, j, k，row, col, next_row, nextcol, dir, found = FALSE; int gd=VGA;int gm二VGAHI;/*用來循環(huán)計(jì)數(shù)Irow , col-當(dāng)前位置的坐標(biāo)next_row一 移動(dòng)后的位置的橫坐標(biāo)Inext_col移動(dòng)后的位置的縱坐標(biāo)II dir移動(dòng)的方向Ifound標(biāo)志路徑是否發(fā)現(xiàn)*/element position;int top = 0;markl l = 1;/* maze 1 1已經(jīng)被走過了*/stack0.

12、row = 1;stack0.col = 1;stackO.dir= 1;/* 第一步的狀態(tài) */move0.vert = -1; move0.horiz = 0 ;move 1 .vert = -1; move 1 .horiz = 1 ;niove2.vert = 0 ; move2.horiz = 1 ;move3.vert = 1 ; move3.horiz = 1 ;move4.vert = 1 ; move4.horiz = 0 ;niove5.vert = 1 ; move5.horiz = -1;niove6.vert = 0 ; move6.horiz = -1;move7.

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

14、ck 中的元素*/row = position.row;col = position.col;dir = position.dir;while (dir < 8 && !found) nextrow = row + niovedir.vert;next_col = col + movedir.horiz;if (next.row = EXIT_ROW && next_col = EXIT_COL)found = TRUE;/* 發(fā)現(xiàn)路徑 */else if ( !mazenext_rownexCcol &&!mjrknext_rownext

15、_col)/*如果這點(diǎn)沒有被走過并且可以走*/marknext_row next_col = 1;/* 設(shè)成 1*/position.row = row;position.col = col;position.dir = +dir;ndd(&top. position);/*加入到 stack*/row = nextrow;col = nexCcol;dir = 0;/*移動(dòng)到下一個(gè)點(diǎn)*/else +dir;/*嘗試其他方向*/for(j=l;j<=N;j+)for(k= 1 ;k<=N ;k+)setcolor(WHITE);circle(j*LEN,k*LEN,10);

16、setcolor(MAGENTA); outtextxy(j*LEN-2,k*LEN-2,mazekj?，r,:"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+l.col*LEN,stacki+l.row*LEN);line(stacki.col*LEN, stacki.row*LEN,col*LEN,row*LEN); line(

17、col*LEN, row*LEN,EXIT_COL*LEN,EXIT_ROW*LEN);else outtextxy(20,10/The maze does not have a path”)；/*否則打印不存在信息*/void main()int i, j, c;srand(time(O); system(HclsH);for (i=0;ivN+2;i+)maze0i=l;mazei0=l;mazeN+li=l; mazeiN+l=l;/*將迷宮的四周設(shè)為1 (墻壁)*/printf(HWould you like to input the maze by youself?nYes or N

18、o?”); c = getchar();if(c二二'Y'll c= 'y')printf(HEnter the %d * %d maze:n",N,N);/*手動(dòng)輸入*/for (i=l; ivN+1; i+)for(j=l; jvN+l; j+)scanf(” d",&mazeij);)elseprintf(nThe maze is created by the computer:nn);for (i=l; i<N+l; i+)for(j=l; j<N+l; j+)inazeij=rand()%2;mazeNN=O;m

19、azel 1 = 0;for(i= 1 ;i<N+l ;i+) for(j=1 ;j<N+1 ;j+)printf(”3d”,mazeij);printf("n“)；path();/* 調(diào)用函數(shù) path() */getch();4測(cè)試方法4.1測(cè)試目的針對(duì)迷宮生成方式不同，本程序的測(cè)試分為兩類：手動(dòng)輸入迷宮測(cè)試和計(jì)算機(jī) 自動(dòng)生成迷宮測(cè)試。另外，根據(jù)測(cè)試用例不同也可以分為兩類：有解迷宮測(cè)試無解 迷宮測(cè)試。即檢查是否可以自動(dòng)生成或手動(dòng)生成一個(gè)齢n的迷宮，并判斷生成的迷 宮圖是否可從入口不經(jīng)過重復(fù)點(diǎn)通過路“0”走向出口。4.2測(cè)試輸入a)按Y或y手動(dòng)生成迷宮矩陣(有解迷宮):

20、先輸入8*8的矩陣b）按任意鍵自動(dòng)生成迷宮矩陣（有解迷宮）：C）按任意鍵自動(dòng)生成迷宮矩陣（無解迷宮）:4.3正確輸出不管是手動(dòng)生成還是自動(dòng)生成迷宮，走數(shù)字為零的點(diǎn)且不經(jīng)過重復(fù)點(diǎn)走向出 口。如果沒有通路則失敗。4.4實(shí)際輸出a）給出的迷宮路線如圖：b）對(duì)于自動(dòng)生成電腦路線（有解迷宮），給出的迷宮路線:c）對(duì)于有些自動(dòng)生成的迷宮（無解迷宮），可能不可以完成走迷宮:4.5錯(cuò)誤原因走迷宮失敗原因是從入口通向出口的路上被墻“1”給堵住了，則無法走向出口。 即沒有一條從入口到出口的通路。5分析與探討5.1測(cè)試結(jié)果分析比手動(dòng)生成的迷宮圖是由一個(gè)8*8的矩陣構(gòu)成的，這是由最大棧容量 MAX_STACK_SIZ

21、E決定的，0為路，1為墻，并且可以上、下、左、右、左上、左下、 右上、右下行走，且不會(huì)走已經(jīng)走過的點(diǎn)。最終從左上入口點(diǎn)開始到右下出口點(diǎn)結(jié) 束。b.自動(dòng)生成的迷宮圖同樣遵循迷宮行走法則。5.2探討與改進(jìn)上述的實(shí)驗(yàn)代碼及實(shí)驗(yàn)結(jié)果都是在vc中進(jìn)行的。因?yàn)閠urbo c現(xiàn)在有很多人不用 且我習(xí)慣用的是vc,所以我用vc寫。教學(xué)中給的代碼適合在turbo C中進(jìn)行，從源代 碼到現(xiàn)在代碼的改進(jìn)以及為完成實(shí)驗(yàn)要求。需先在VC中安裝graphics.h和graphics.lib 文件。并修 改一些方法如 random(2)改成 rand()%2 , clrscr()改成 system("cls"), randomize()改成srand