《大數(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é)生通過上機實習，驗證自己設(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é)習的知識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在設(shè)計的過程中，和同學(xué)們相互探討，相互學(xué)習，相互監(jiān)視。我學(xué)會了運籌帷幄，學(xué)會了寬容，學(xué)會了理解，也學(xué)會了做
14、人和處世，這次的課程設(shè)計對我來說受益良多。
通過這次課程設(shè)計，更是讓我深刻認識到自己在學(xué)習中的不足，同時也找到了克制不足的方法，這也是一筆很大的資源。在以后的時間中，我們應(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;
}
}
}
大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計深度與廣度優(yōu)先搜索：迷宮問的題目
