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

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

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

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

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

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

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

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

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

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

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

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 迷宮問題可以用深度優(yōu)先搜索方法實現(xiàn)。當老鼠在迷宮中移動的時候，可能會有許多種移動選擇方向。程序需要記錄并用棧來保存當前點的坐標，然后任意選擇一個方向進展移動。由于應(yīng)用棧保存了當前通道上各點的坐標，所以當在當前各方向上都走不通時可以返回上

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

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

14、人和處世，這次的課程設(shè)計對我來說受益良多。 通過這次課程設(shè)計，更是讓我深刻認識到自己在學(xué)習(xí)中的不足，同時也找到了克制不足的方法，這也是一筆很大的資源。在以后的時間中，我們應(yīng)該利用更多的時間去上機實驗，加強自學(xué)的能力，多編寫程序，相信不久后我們的編程能力都會有很大的提高。 參考文獻 [1] X振安,X燕君.C程序設(shè)計課程設(shè)計[M].[]機械工業(yè),2004年9月 [2] 譚浩強.C程序設(shè)計〔第三版〕.清華大學(xué),2005年7月 [3] 嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)〔C語言版〕.清華大學(xué),1997年4月 [4] 李志球《實用C語言程序設(shè)計教程》 ：電子工業(yè)，1999

15、[5] 王立柱：C/C++與數(shù)據(jù)結(jié)構(gòu) ：清華大學(xué)，2002 [6] 吳文虎 《程序設(shè)計根底》 ：清華大學(xué)，2003 [7] 郭福順，王曉芬，李蓮治 《數(shù)據(jù)結(jié)構(gòu)》〔修訂本〕，某某理工大學(xué)，1997 [8] 潘道才，陳一華 《數(shù)據(jù)結(jié)構(gòu)》，電子科技大學(xué)，1994 附 錄 附錄1 源程序清單 #include //庫中包含system("pause")和rand()函數(shù) #include //c語言里的庫 #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; //隊列的頭尾指針，初始值設(shè)為0 struct point

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

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

19、]=0; } void data(int m,int n) { //當用戶輸入的不是規(guī)整的m行n列的迷宮，用來生成規(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、中隊列入隊操作 { queue[tail]=p; tail++; //先用再加，隊列尾部加1 } struct point dequeue() //迷宮中隊列出隊操作，不需要形參，因此用結(jié)構(gòu)體定義 { head++; return queue[head-1]; } int is_empty() //判斷隊列是否為空 { retur

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

27、

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

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

30、 //標記為已訪問 enqueue(p); //將p入隊列 while(!is_empty()) { p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) //當行和列為出口時跳出 break; //定義8個走位方向 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) //如果當前矩陣點是出口點，輸出路徑 { 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<<" 歡迎進入迷宮求解系統(tǒng)\n"; cout<

38、************************************************************************\n"; cout<<" ☆ 手動生成迷宮 請按：1\n"; cout<<" ☆ 自動生成迷宮 請按：2\n"; cout<<" ☆ 退出 請按：3\n\n"; cout<<"************************

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

40、抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請重新輸入：\n\n"; cout<<"\n請輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請輸入列數(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); //當X不為0時，有解，調(diào)用輸出路徑函數(shù) c

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

42、抱歉，你輸入的行列數(shù)超出預(yù)設(shè)X圍(0-49,0-49),請重新輸入：\n\n"; cout<<"\n請輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請輸入列數(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; } } }