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

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

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 深度與廣度優(yōu)先搜索：迷宮問(wèn)題 專(zhuān)業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)〔網(wǎng)絡(luò)技術(shù)〕 學(xué)生某某 班級(jí) 學(xué)號(hào) 指導(dǎo)教師 完成日期 目 錄 1. 課程設(shè)計(jì)的目的…………………………………………………….3 2. 簡(jiǎn)介………………………………………………………………….3 3. 算法說(shuō)明…………………………………………………………….4 4. 測(cè)試結(jié)果……………………………………………………………..5 5. 分析與探討…………………………

2、………………………………..6 6. 小結(jié)…………………………………………………………………..8 7. 參考文獻(xiàn)……………………………………………………………..9 8. 附錄………………………………………………………………,,,..10 附錄1 源程序清單…………………………………………………….10 一．課程設(shè)計(jì)的目的 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是為數(shù)據(jù)結(jié)構(gòu)課程獨(dú)立開(kāi)設(shè)的實(shí)踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)對(duì)于鞏固數(shù)據(jù)結(jié)構(gòu)知識(shí)，加強(qiáng)學(xué)生的實(shí)際動(dòng)手能力和提高學(xué)生綜合素質(zhì)是十分必要的。課程設(shè)計(jì)的目的： 1．要求學(xué)生達(dá)到熟練掌握C語(yǔ)言的根本知識(shí)和技能。 2．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)

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

4、始點(diǎn)〕出發(fā)，按照一定的搜索方法對(duì)圖中所有頂點(diǎn)各做一次訪問(wèn)的過(guò)程。根據(jù)搜索的方法不同，遍歷有如下兩種。 〔1〕深度優(yōu)先搜索遍歷：深度優(yōu)先搜索〔DFS〕是一個(gè)遞歸過(guò)程。首先訪問(wèn)一個(gè)頂點(diǎn)Vi并將其標(biāo)記為已訪問(wèn)過(guò)，然后從Vi的任意一個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)展深度優(yōu)先搜索遍歷。如此執(zhí)行，當(dāng)Vi的所有鄰接點(diǎn)均被訪問(wèn)過(guò)時(shí)，如此退回到上一個(gè)頂點(diǎn)Vk，從Vk的另一未被訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)進(jìn)展深度優(yōu)先搜索遍歷。如此執(zhí)行，直到退回到初始點(diǎn)并且沒(méi)有違背訪問(wèn)過(guò)的鄰接點(diǎn)為止。 〔2〕廣度優(yōu)先搜索遍歷：廣度優(yōu)先搜索過(guò)程〔BFS〕為：首先訪問(wèn)初始點(diǎn)Vi，并將其標(biāo)記為已訪問(wèn)過(guò)，接著訪問(wèn)Vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，其訪問(wèn)順序

5、可以任意，假定依次為Vi1，Vi2，…..Vin，并均被標(biāo)記為已訪問(wèn)過(guò)，然后按照Vi1，Vi2，…..Vin，的次序，訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，并均標(biāo)記為已訪問(wèn)過(guò)，以此類(lèi)推，直到圖中所有和初始點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。 無(wú)論是深度優(yōu)先搜索還是廣度優(yōu)先搜索，其本質(zhì)都是將圖的二維頂點(diǎn)結(jié)構(gòu)線性化的過(guò)程，并將當(dāng)前頂點(diǎn)相鄰的未被訪問(wèn)的頂點(diǎn)作為下一個(gè)頂點(diǎn)，由于與當(dāng)前頂點(diǎn)相鄰的頂點(diǎn)可能多于一個(gè)，而每次只能選擇其中一個(gè)作為下一個(gè)頂點(diǎn)，這樣勢(shì)必要保存其他相鄰頂點(diǎn)。深度優(yōu)先搜索和廣度優(yōu)先搜索在數(shù)據(jù)結(jié)構(gòu)上的區(qū)別就在于用于保存其他相鄰頂點(diǎn)的方式不一樣，深度優(yōu)先搜索采用棧，而廣度優(yōu)先搜索如此

6、采用隊(duì)列。從形式上，深度優(yōu)先搜索往往采用一個(gè)遞歸過(guò)程，實(shí)際上遞歸的編譯實(shí)現(xiàn)就應(yīng)用了棧。 本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序。一般的迷宮可表示為一個(gè)二維平面圖形，將迷宮的左上角作入口，右下角作出口。迷宮問(wèn)題求解的目標(biāo)是尋找一條從入口點(diǎn)到出口點(diǎn)的通路。具體實(shí)驗(yàn)內(nèi)容如下： 選擇手動(dòng)或者自動(dòng)生成一個(gè)n*m的迷宮，將迷宮的左上角作為入口，右下角作為出口，設(shè)“0〞為通路，“1〞為墻，即無(wú)法穿越。假設(shè)一只老鼠從起點(diǎn)出發(fā)，目的地為右下角終點(diǎn)，可向“上，下，左，右，左上，左下，右上，右下〞8個(gè)方向行走。如果迷宮可以走通，如此用圖形界面標(biāo)出走出迷宮的路徑。如果迷宮為死迷宮，如此只輸出迷宮原型圖。 三．算法說(shuō)明 在

7、實(shí)例程序中使用二維數(shù)組maze[N+2][N+2] 的行，列數(shù)。(不用maze[N][N]原因是當(dāng)老鼠跑到了迷宮的邊界點(diǎn)就有可能跳出迷宮，而使用maze[N+2][N+2]就可以把迷宮的外面再包一層“1〞，這樣就可以阻止老鼠走出格)當(dāng)值為“0〞時(shí)表示該點(diǎn)是通路，當(dāng)值為“1〞時(shí)表示該點(diǎn)是墻。老鼠在迷宮中的位置在任何時(shí)候都可以有行號(hào)row和列號(hào)col表示。 （1） 手動(dòng)生成迷宮 void hand_maze(int m,int n) //手動(dòng)生成迷宮 { int i,j; for(i=0;i

8、>>maze[i][j]; } } (2)自動(dòng)生成迷宮 void automatic_maze(int m,int n) //自動(dòng)生成迷宮 { int i,j; for(i=0;i

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

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

11、 表3.1 8種方向move的偏移量 Name dir Move[dir].vert Move[dir].horiz N 0 -1 0 NE 1 -1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1 -1 W 6 0 -1 NW 6 0 -1 迷宮問(wèn)題可以用深度優(yōu)先搜索方法實(shí)現(xiàn)。當(dāng)老鼠在迷宮中移動(dòng)的時(shí)候，可能會(huì)有許多種移動(dòng)選擇方向。程序需要記錄并用棧來(lái)保存當(dāng)前點(diǎn)的坐標(biāo)，然后任意選擇一個(gè)方向進(jìn)展移動(dòng)。由于應(yīng)用棧保存了當(dāng)前通道上各點(diǎn)的坐標(biāo)，所以當(dāng)在當(dāng)前各方向上都走不通時(shí)可以返回上

12、一個(gè)點(diǎn)，然后選擇另一個(gè)方向前進(jìn)。 可定義element結(jié)構(gòu)用于存儲(chǔ)每一步的橫縱坐標(biāo)和方向。 typedef struct{ short int row; short int col; short int dir; }element; element stack[MAX _STACK_SIZE]; 根據(jù)表3.1可推算出每次移動(dòng)后的坐標(biāo)。設(shè)當(dāng)前的坐標(biāo)是〔row,col〕,移動(dòng)的方向是dir，移動(dòng)后的點(diǎn)是next,如此有 next_row=row+move[dir].vert; next_col=col+move[dir].horiz; 可

13、用另一個(gè)二維數(shù)組mark[N+2]來(lái)記錄哪些點(diǎn)已經(jīng)被訪問(wèn)過(guò)。當(dāng)經(jīng)過(guò)點(diǎn)maze[row][col]時(shí)，相應(yīng)地將mark[row][col]的值從0置為1。 本程序支持自動(dòng)生成迷宮。利用random〔2〕函數(shù)可隨機(jī)產(chǎn)生0或1，來(lái)支持迷宮的自動(dòng)生成。注意maze[N][N]和maze[1][1]一定要等于0，因?yàn)樗麄兎謩e是起點(diǎn)和終點(diǎn)。 六．小結(jié) 一周的課程設(shè)計(jì)完畢了，在這次課程設(shè)計(jì)中不僅檢驗(yàn)我所學(xué)習(xí)的知識(shí)，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在設(shè)計(jì)的過(guò)程中，和同學(xué)們相互探討，相互學(xué)習(xí)，相互監(jiān)視。我學(xué)會(huì)了運(yùn)籌帷幄，學(xué)會(huì)了寬容，學(xué)會(huì)了理解，也學(xué)會(huì)了做

14、人和處世，這次的課程設(shè)計(jì)對(duì)我來(lái)說(shuō)受益良多。 通過(guò)這次課程設(shè)計(jì)，更是讓我深刻認(rèn)識(shí)到自己在學(xué)習(xí)中的不足，同時(shí)也找到了克制不足的方法，這也是一筆很大的資源。在以后的時(shí)間中，我們應(yīng)該利用更多的時(shí)間去上機(jī)實(shí)驗(yàn)，加強(qiáng)自學(xué)的能力，多編寫(xiě)程序，相信不久后我們的編程能力都會(huì)有很大的提高。 參考文獻(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)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)〔C語(yǔ)言版〕.清華大學(xué),1997年4月 [4] 李志球《實(shí)用C語(yǔ)言程序設(shè)計(jì)教程》 ：電子工業(yè)，1999

15、[5] 王立柱：C/C++與數(shù)據(jù)結(jié)構(gòu) ：清華大學(xué)，2002 [6] 吳文虎 《程序設(shè)計(jì)根底》 ：清華大學(xué)，2003 [7] 郭福順，王曉芬，李蓮治 《數(shù)據(jù)結(jié)構(gòu)》〔修訂本〕，某某理工大學(xué)，1997 [8] 潘道才，陳一華 《數(shù)據(jù)結(jié)構(gòu)》，電子科技大學(xué)，1994 附 錄 附錄1 源程序清單 #include //庫(kù)中包含system("pause")和rand()函數(shù) #include //c語(yǔ)言里的庫(kù) #incl

16、ude using namespace std; #define N 49 //定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改 #define M 49 int X; int maze[N+2][M+2]; int head=0,tail=0; //隊(duì)列的頭尾指針，初始值設(shè)為0 struct point

17、 //存放迷宮訪問(wèn)到點(diǎn)的隊(duì)列結(jié)構(gòu)體，包含列，行，序號(hào) { int row,col,predecessor; }queue[1200]; void hand_maze(int m,int n) //手動(dòng)生成迷宮 { int i,j; cout<>maze[i][j]; } } v

18、oid automatic_maze(int m,int n) //自動(dòng)生成迷宮 { int i,j; cout<<"\n迷宮生成中……\n\n"; system("pause"); for(i=0;i

19、]=0; } void data(int m,int n) { //當(dāng)用戶輸入的不是規(guī)整的m行n列的迷宮，用來(lái)生成規(guī)如此的數(shù)字迷宮 int i,j; cout<

20、<"↓"; for(i=0;i

21、生成結(jié)果如下:\n\n"; cout<<"迷宮入口\n"; cout<<" ↓"; cout<

22、▲"; for(j=0;j

23、 { cout<<" ";} cout<<"↓\n"; for(i=0;i

24、j=0;j

25、中隊(duì)列入隊(duì)操作 { queue[tail]=p; tail++; //先用再加，隊(duì)列尾部加1 } struct point dequeue() //迷宮中隊(duì)列出隊(duì)操作，不需要形參，因此用結(jié)構(gòu)體定義 { head++; return queue[head-1]; } int is_empty() //判斷隊(duì)列是否為空 { retur

26、n head==tail; } void visit(int row,int col,int maze[51][51]) //訪問(wèn)迷宮矩陣中的節(jié)點(diǎn) { struct point visit_point={row,col,head-1}; //head-1的作用是正在訪問(wèn)的這個(gè)點(diǎn)的序號(hào)為之前的點(diǎn)序號(hào) maze

27、

28、 //將訪問(wèn)過(guò)的點(diǎn)位標(biāo)記為2 enqueue(visit_point);//入隊(duì) } int path(int maze[51][51],int m,int n) //路徑求解 { X=1; //初始值定為1 struct point p={0,0,

29、-1}; //定義入口節(jié)點(diǎn) if(maze[p.row][p.col]==1) //入口為1時(shí)，迷宮不可解 { cout<<"\n===============================================\n"; cout<<"此迷宮無(wú)解\n\n"; X=0; return 0; } maze[p.row][p.col]=2;

30、 //標(biāo)記為已訪問(wèn) enqueue(p); //將p入隊(duì)列 while(!is_empty()) { p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) //當(dāng)行和列為出口時(shí)跳出 break; //定義8個(gè)走位方向 if((((p.row-1)>=

31、0)&&((p.row-1)=0)&&((p.row-1)

32、e[p.row+0][p.col+1]==0)) visit(p.row+0,p.col+1,maze); //東 if((((p.row+1)

33、aze); //南 if((((p.row+1)=0))&&(maze[p.row+1][p.col-1]==0)) visit(p.row+1,p.col-1,maze); //西南 if((((p.row+0)=0))&&(maze[p.row+0][p.col-1]==0)) visit(p.row+0,p.col-1,maze); //西

34、 if((((p.row-1)>=0)&&((p.row-1)=0))&&(maze[p.row-1][p.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)，輸出路徑 { cout<<"\n=========================================================

35、=========\n"; cout<<"迷宮路徑為：\n"; cout<<"出口"<

36、]; printf("(%d,%d)\n",p.row+1,p.col+1); cout<<" "<<"↑"<

37、 { int i,m,n,cycle=0; while(cycle!=(-1)) { cout<<"********************************************************************************\n"; cout<<" 歡迎進(jìn)入迷宮求解系統(tǒng)\n"; cout<

38、************************************************************************\n"; cout<<" ☆ 手動(dòng)生成迷宮 請(qǐng)按：1\n"; cout<<" ☆ 自動(dòng)生成迷宮 請(qǐng)按：2\n"; cout<<" ☆ 退出 請(qǐng)按：3\n\n"; cout<<"************************

39、********************************************************\n"; cout<<"\n"; cout<<"請(qǐng)選擇你的操作：\n"; cin>>i; switch(i) { case 1: cout<<"\n請(qǐng)輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請(qǐng)輸入列數(shù)："; cin>>n; while((m<0||m>49)||(n<0||n>49)) { cout<<"\n

40、抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請(qǐng)重新輸入：\n\n"; cout<<"\n請(qǐng)輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請(qǐng)輸入列數(shù)："; cin>>n; } hand_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); //當(dāng)X不為0時(shí)，有解，調(diào)用輸出路徑函數(shù) c

41、out<<"\n\nPress Enter Contiue!\n"; getchar(); while(getchar()!='\n'); //承受一個(gè)輸入，當(dāng)為回車(chē)時(shí)執(zhí)行break跳出，否如此一直執(zhí)行承受數(shù)據(jù) break; case 2: cout<<"\n請(qǐng)輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請(qǐng)輸入列數(shù)："; cin>>n; while((m<0||m>49)||(n<0||n>49)) { cout<<"\n

42、抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請(qǐng)重新輸入：\n\n"; cout<<"\n請(qǐng)輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請(qǐng)輸入列數(shù)："; cin>>n; } automatic_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); cout<<"\n\nPress Enter Contiue!\n"; getchar(); while(getchar()!='\n'); break; case 3: cycle=(-1);break; default: cout<<"\n";cout<<"你的輸入有誤!\n"; cout<<"\nPress Enter Contiue!\n"; getchar(); while(getchar()!='\n'); break; } } }