大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問的題目

《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問的題目》由會員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問的題目（14頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問題專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)網(wǎng)絡(luò)技術(shù)學(xué)生某某班級學(xué)號指導(dǎo)教師完成日期目 錄1. 課程設(shè)計(jì)的目的.32. 簡介.33. 算法說明.44. 測試結(jié)果.55. 分析與探討.66. 小結(jié).87. 參考文獻(xiàn).98. 附錄,.10附錄1 源程序清單.10一課程設(shè)計(jì)的目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是為數(shù)據(jù)結(jié)構(gòu)課程獨(dú)立開設(shè)的實(shí)踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)對于鞏固數(shù)據(jù)結(jié)構(gòu)知識，加強(qiáng)學(xué)生的實(shí)際動手能力和提高學(xué)生綜合素質(zhì)是十分必要的。課程設(shè)計(jì)的目的：1要求學(xué)生達(dá)到熟練掌握C語言的根本知識和技能。2了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力。3提高程序設(shè)計(jì)和調(diào)試能力。

2、學(xué)生通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會有效利用根本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。4培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平。5初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等根本方法和技能。二簡介1.圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)又稱圖的表示，其最常用的方法是鄰接矩陣和鄰接表。無論采用存儲方式，其目的總是一樣的，即不僅要存儲圖中各個頂點(diǎn)的信息，同時還要存儲頂點(diǎn)之間的所有關(guān)系。2.圖的遍歷圖的遍歷就是從指定的某個頂點(diǎn)稱其為初始點(diǎn)出發(fā)，按照一定的搜索方法對圖中所有頂點(diǎn)各做一次訪問的過程。根據(jù)搜索的方法不同，遍歷有如下兩種。1深度

3、優(yōu)先搜索遍歷：深度優(yōu)先搜索DFS是一個遞歸過程。首先訪問一個頂點(diǎn)Vi并將其標(biāo)記為已訪問過，然后從Vi的任意一個未被訪問的鄰接點(diǎn)出發(fā)進(jìn)展深度優(yōu)先搜索遍歷。如此執(zhí)行，當(dāng)Vi的所有鄰接點(diǎn)均被訪問過時，如此退回到上一個頂點(diǎn)Vk，從Vk的另一未被訪問過的鄰接點(diǎn)出發(fā)進(jìn)展深度優(yōu)先搜索遍歷。如此執(zhí)行，直到退回到初始點(diǎn)并且沒有違背訪問過的鄰接點(diǎn)為止。2廣度優(yōu)先搜索遍歷：廣度優(yōu)先搜索過程BFS為：首先訪問初始點(diǎn)Vi，并將其標(biāo)記為已訪問過，接著訪問Vi的所有未被訪問過的鄰接點(diǎn)，其訪問順序可以任意，假定依次為Vi1，Vi2，.Vin，并均被標(biāo)記為已訪問過，然后按照Vi1，Vi2，.Vin，的次序，訪問每一個頂點(diǎn)的所有

4、未被訪問過的鄰接點(diǎn)，并均標(biāo)記為已訪問過，以此類推，直到圖中所有和初始點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問過為止。無論是深度優(yōu)先搜索還是廣度優(yōu)先搜索，其本質(zhì)都是將圖的二維頂點(diǎn)結(jié)構(gòu)線性化的過程，并將當(dāng)前頂點(diǎn)相鄰的未被訪問的頂點(diǎn)作為下一個頂點(diǎn)，由于與當(dāng)前頂點(diǎn)相鄰的頂點(diǎn)可能多于一個，而每次只能選擇其中一個作為下一個頂點(diǎn)，這樣勢必要保存其他相鄰頂點(diǎn)。深度優(yōu)先搜索和廣度優(yōu)先搜索在數(shù)據(jù)結(jié)構(gòu)上的區(qū)別就在于用于保存其他相鄰頂點(diǎn)的方式不一樣，深度優(yōu)先搜索采用棧，而廣度優(yōu)先搜索如此采用隊(duì)列。從形式上，深度優(yōu)先搜索往往采用一個遞歸過程，實(shí)際上遞歸的編譯實(shí)現(xiàn)就應(yīng)用了棧。本實(shí)驗(yàn)的目的是設(shè)計(jì)一個程序。一般的迷宮可表示為一個二維平

5、面圖形，將迷宮的左上角作入口，右下角作出口。迷宮問題求解的目標(biāo)是尋找一條從入口點(diǎn)到出口點(diǎn)的通路。具體實(shí)驗(yàn)內(nèi)容如下：選擇手動或者自動生成一個n*m的迷宮，將迷宮的左上角作為入口，右下角作為出口，設(shè)“0為通路，“1為墻，即無法穿越。假設(shè)一只老鼠從起點(diǎn)出發(fā)，目的地為右下角終點(diǎn)，可向“上，下，左，右，左上，左下，右上，右下8個方向行走。如果迷宮可以走通，如此用圖形界面標(biāo)出走出迷宮的路徑。如果迷宮為死迷宮，如此只輸出迷宮原型圖。三算法說明在實(shí)例程序中使用二維數(shù)組mazeN+2N+2 的行，列數(shù)。(不用mazeNN原因是當(dāng)老鼠跑到了迷宮的邊界點(diǎn)就有可能跳出迷宮，而使用mazeN+2N+2就可以把迷宮的外面

6、再包一層“1，這樣就可以阻止老鼠走出格)當(dāng)值為“0時表示該點(diǎn)是通路，當(dāng)值為“1時表示該點(diǎn)是墻。老鼠在迷宮中的位置在任何時候都可以有行號row和列號col表示。（1） 手動生成迷宮void hand_maze(int m,int n) /手動生成迷宮int i,j;for(i=0;im;i+)for(j=0;jmazeij;(2)自動生成迷宮void automatic_maze(int m,int n) /自動生成迷宮int i,j;for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2; /隨機(jī)生成0，1maze00=0; /將開始和完畢位置強(qiáng)制為0，保證有可

7、能出來迷宮mazem-1n-1=0;四測試結(jié)果1.手動生成迷宮2.自動生成迷宮3.迷宮開始界面五分析與探討首先明確題目中的條件：（1） 迷宮是一個8*8大小的矩陣。（2） 從迷宮的左上角進(jìn)入，右下角為迷宮的終點(diǎn)。（3） mazeij=0代表第i+1行第j+1列的點(diǎn)是通路；mazeij=1代表該點(diǎn)是墻，無法通行。（4） 迷宮有兩種生成方式：手工設(shè)定和自動生成。（5） 當(dāng)老鼠處于迷宮中某一點(diǎn)的位置上，它可以向8個方向前進(jìn)，分別是：“上、下、左、右、左上、左下、右上、右下8個方向。（6） 在實(shí)例程序中使用二維數(shù)組mazeN+2N+2 的行，列數(shù)。(不用mazeNN原因是當(dāng)老鼠跑到了迷宮的邊界點(diǎn)就有可

8、能跳出迷宮，而使用mazeN+2N+2就可以把迷宮的外面再包一層“1，這樣就可以阻止老鼠走出格)當(dāng)值為“0時表示該點(diǎn)是通路，當(dāng)值為“1時表示該點(diǎn)是墻。老鼠在迷宮中的位置在任何時候都可以有行號row和列號col表示（7） 老鼠在每一點(diǎn)都有8種方向可以走，分別是：North，NorthEast，East，SouthEast,South,SouthWest,West，NorthWest?？梢杂脭?shù)組move8來表示每一個方向上的橫縱坐標(biāo)的偏移量，見表3.1。根據(jù)這個數(shù)組，就很容易計(jì)算出沿某個方向行走后的下一個點(diǎn)的坐標(biāo)。 表3.1 8種方向move的偏移量Name dirMovedir.vertMove

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

10、TACK_SIZE;根據(jù)表3.1可推算出每次移動后的坐標(biāo)。設(shè)當(dāng)前的坐標(biāo)是row,col,移動的方向是dir，移動后的點(diǎn)是next,如此有next_row=row+movedir.vert;next_col=col+movedir.horiz; 可用另一個二維數(shù)組markN+2來記錄哪些點(diǎn)已經(jīng)被訪問過。當(dāng)經(jīng)過點(diǎn)mazerowcol時，相應(yīng)地將markrowcol的值從0置為1。 本程序支持自動生成迷宮。利用random2函數(shù)可隨機(jī)產(chǎn)生0或1，來支持迷宮的自動生成。注意mazeNN和maze11一定要等于0，因?yàn)樗麄兎謩e是起點(diǎn)和終點(diǎn)。六小結(jié)一周的課程設(shè)計(jì)完畢了，在這次課程設(shè)計(jì)中不僅檢驗(yàn)我所學(xué)習(xí)的知

11、識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在設(shè)計(jì)的過程中，和同學(xué)們相互探討，相互學(xué)習(xí)，相互監(jiān)視。我學(xué)會了運(yùn)籌帷幄，學(xué)會了寬容，學(xué)會了理解，也學(xué)會了做人和處世，這次的課程設(shè)計(jì)對我來說受益良多。通過這次課程設(shè)計(jì)，更是讓我深刻認(rèn)識到自己在學(xué)習(xí)中的不足，同時也找到了克制不足的方法，這也是一筆很大的資源。在以后的時間中，我們應(yīng)該利用更多的時間去上機(jī)實(shí)驗(yàn)，加強(qiáng)自學(xué)的能力，多編寫程序，相信不久后我們的編程能力都會有很大的提高。參考文獻(xiàn)1 X振安,X燕君.C程序設(shè)計(jì)課程設(shè)計(jì)M.機(jī)械工業(yè),2004年9月2 譚浩強(qiáng).C程序設(shè)計(jì)第三版.清華大學(xué),2005年7月3 嚴(yán)蔚敏,吳

12、偉民.數(shù)據(jù)結(jié)構(gòu)C語言版.清華大學(xué),1997年4月4 李志球?qū)嵱肅語言程序設(shè)計(jì)教程 ：電子工業(yè)，19995 王立柱：C/C+與數(shù)據(jù)結(jié)構(gòu) ：清華大學(xué)，20026 吳文虎 程序設(shè)計(jì)根底 ：清華大學(xué)，20037 郭福順，王曉芬，李蓮治 數(shù)據(jù)結(jié)構(gòu)修訂本，某某理工大學(xué)，19978 潘道才，陳一華 數(shù)據(jù)結(jié)構(gòu)，電子科技大學(xué)，1994附 錄附錄1 源程序清單#include /庫中包含system(pause)和rand()函數(shù)#include /c語言里的庫#includeusing namespace std;#define N 49 /定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改#define M 4

13、9int X; int mazeN+2M+2;int head=0,tail=0; /隊(duì)列的頭尾指針，初始值設(shè)為0struct point /存放迷宮訪問到點(diǎn)的隊(duì)列結(jié)構(gòu)體，包含列，行，序號 int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手動生成迷宮int i,j;coutendl; cout請按行輸入迷宮，0表示通路，1表示障礙:endl; for(i=0;im;i+) for(j=0;jmazeij; void automatic_maze(int m,int n) /自動生成迷宮int i,j;coutn迷宮

14、生成中nn;system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2; /隨機(jī)生成0、1maze00=0; /將開始和完畢位置強(qiáng)制為0，保證有可能出來迷宮mazem-1n-1=0;void data(int m,int n) /當(dāng)用戶輸入的不是規(guī)整的m行n列的迷宮，用來生成規(guī)如此的數(shù)字迷宮int i,j; coutendl;cout根據(jù)您先前設(shè)定的迷宮X圍endl;coutendl;cout 我們將取所輸入的前m*n個數(shù)生成迷宮endl;coutn數(shù)字迷宮生成結(jié)果如下:nn;cout迷宮入口n; cout;for(i=0;im;i+)

15、coutn;for(j=0;jn;j+) if(mazeij=0) cout 0;if(mazeij=1) cout 1; cout迷宮出口n;void print_maze(int m,int n) /打印迷宮外殼int i,j,k;coutn字符迷宮生成結(jié)果如下:nn;cout迷宮入口n;cout ;coutendl;cout ; /生成上外殼for(k=0;kn;k+)cout; /這兩個黑三角用來生成頂部外殼for(i=0;im;i+)coutn; /生成左外殼cout;for(j=0;jn;j+) if(mazeij=0) printf();if(mazeij=1) printf()

16、;cout; /生成右外殼coutendl;for(k=0;kn;k+)cout;cout n; /生成底部外殼 for(i=0;in;i+)cout ; coutn;for(i=0;in;i+)cout ;cout迷宮出口n;void result_maze(int m,int n) /這個是打印輸出迷宮的星號路徑 int i,j;cout迷宮通路(用表示)如下所示：nt;for(i=0;im;i+)coutn;for(j=0;jn;j+)if(mazeij=0|mazeij=2) /2是隊(duì)列中訪問過的點(diǎn) cout;if(mazeij=1) cout;if(mazeij=3) /3是標(biāo)記的可

17、以走通的路徑cout;void enqueue(struct point p) /迷宮中隊(duì)列入隊(duì)操作queuetail=p;tail+; /先用再加，隊(duì)列尾部加1struct point dequeue() /迷宮中隊(duì)列出隊(duì)操作，不需要形參，因此用結(jié)構(gòu)體定義head+;return queuehead-1;int is_empty() /判斷隊(duì)列是否為空return head=tail;void visit(int row,int col,int maze5151) /訪問迷宮矩陣中的節(jié)點(diǎn)struct point visit_point=row,col,head-1; /head-1的作用是正

18、在訪問的這個點(diǎn)的序號為之前的點(diǎn)序號maze /將訪問過的點(diǎn)位標(biāo)記為2enqueue(visit_point);/入隊(duì)int path(int maze5151,int m,int n) /路徑求解X=1; /初始值定為1struct point p=0,0,-1; /定義入口節(jié)點(diǎn)if(mazep.rowp.col=1) /入口為1時，迷宮不可解 coutn=n; cout=0)&(p.row-1)m)&(p.col+0)=0)&(p.row-1)m)&(p.col+1)n)&(mazep.row-1p.col+1=0) visit(p.row-1,p.col+1,maze); /東北 if(p

19、.row+0)m)&(p.col+1)n)&(mazep.row+0p.col+1=0) visit(p.row+0,p.col+1,maze); /東 if(p.row+1)m)&(p.col+1)n)&(mazep.row+1p.col+1=0) visit(p.row+1,p.col+1,maze); /東南 if(p.row+1)m)&(p.col+0)n)&(mazep.row+1p.col+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)m)&(p.col-1)=0)&(mazep.row+1p.col-1=0) visit(p.ro

20、w+1,p.col-1,maze); /西南 if(p.row+0)m)&(p.col-1)=0)&(mazep.row+0p.col-1=0) visit(p.row+0,p.col-1,maze); /西 if(p.row-1)=0)&(p.row-1)m)&(p.col-1)=0)&(mazep.row-1p.col-1=0) visit(p.row-1,p.col-1,maze); /西北if(p.row=m-1&p.col=n-1) /如果當(dāng)前矩陣點(diǎn)是出口點(diǎn)，輸出路徑coutn=n; cout迷宮路徑為：n; cout出口endl; cout endl; printf(%d,%d)n

21、,p.row+1,p.col+1); cout endl; mazep.rowp.col=3; /逆序?qū)⒙窂綐?biāo)記為3 while(p.predecessor!=-1) p=queuep.predecessor; printf(%d,%d)n,p.row+1,p.col+1); cout endl; mazep.rowp.col=3; cout入口endl;else coutn=n; cout此迷宮無解！nn; X=0;return 0;void main() int i,m,n,cycle=0; while(cycle!=(-1) cout*n; cout 歡迎進(jìn)入迷宮求解系統(tǒng)n; coute

22、ndl; cout 設(shè)計(jì)者:姜雯B計(jì)算機(jī)131班n; cout*n; cout 手動生成迷宮 請按：1n; cout 自動生成迷宮 請按：2n; cout 退出 請按：3nn; cout*n; coutn; couti; switch(i) case 1: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請重新輸入：nn; coutm; coutn; coutn; hand_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0)

23、result_maze(m,n); /當(dāng)X不為0時，有解，調(diào)用輸出路徑函數(shù) coutnnPress Enter Contiue!n; getchar(); while(getchar()!=n); /承受一個輸入，當(dāng)為回車時執(zhí)行break跳出，否如此一直執(zhí)行承受數(shù)據(jù) break; case 2: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請重新輸入：nn; coutm; coutn; coutn; automatic_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); coutnnPress Enter Contiue!n; getchar(); while(getchar()!=n); break; case 3: cycle=(-1);break; default: coutn;cout你的輸入有誤!n; coutnPress Enter Contiue!n; getchar(); while(getchar()!=n); break;