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

數(shù)據(jù)結(jié)構(gòu)課程設計深度與廣度優(yōu)先搜索：迷宮問題專業(yè)計算機科學與技術(shù)網(wǎng)絡技術(shù)學生某某班級學號指導教師完成日期目 錄1. 課程設計的目的.32. 簡介.33. 算法說明.44. 測試結(jié)果.55. 分析與探討.66. 小結(jié).87. 參考文獻.98. 附錄,.10附錄1 源程序清單.10一課程設計的目的數(shù)據(jù)結(jié)構(gòu)課程設計是為數(shù)據(jù)結(jié)構(gòu)課程獨立開設的實踐性教學環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設計對于鞏固數(shù)據(jù)結(jié)構(gòu)知識，加強學生的實際動手能力和提高學生綜合素質(zhì)是十分必要的。課程設計的目的：1要求學生達到熟練掌握C語言的根本知識和技能。2了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，具備初步的獨立分析和設計能力。3提高程序設計和調(diào)試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用根本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。4培養(yǎng)算法分析能力。分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平。5初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等根本方法和技能。二簡介1.圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)又稱圖的表示，其最常用的方法是鄰接矩陣和鄰接表。無論采用存儲方式，其目的總是一樣的，即不僅要存儲圖中各個頂點的信息，同時還要存儲頂點之間的所有關(guān)系。2.圖的遍歷圖的遍歷就是從指定的某個頂點稱其為初始點出發(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的所有未被訪問過的鄰接點，其訪問順序可以任意，假定依次為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)先搜索如此采用隊列。從形式上，深度優(yōu)先搜索往往采用一個遞歸過程，實際上遞歸的編譯實現(xiàn)就應用了棧。本實驗的目的是設計一個程序。一般的迷宮可表示為一個二維平面圖形，將迷宮的左上角作入口，右下角作出口。迷宮問題求解的目標是尋找一條從入口點到出口點的通路。具體實驗內(nèi)容如下：選擇手動或者自動生成一個n*m的迷宮，將迷宮的左上角作為入口，右下角作為出口，設“0為通路，“1為墻，即無法穿越。假設一只老鼠從起點出發(fā)，目的地為右下角終點，可向“上，下，左，右，左上，左下，右上，右下8個方向行走。如果迷宮可以走通，如此用圖形界面標出走出迷宮的路徑。如果迷宮為死迷宮，如此只輸出迷宮原型圖。三算法說明在實例程序中使用二維數(shù)組mazeN+2N+2 的行，列數(shù)。(不用mazeNN原因是當老鼠跑到了迷宮的邊界點就有可能跳出迷宮，而使用mazeN+2N+2就可以把迷宮的外面再包一層“1，這樣就可以阻止老鼠走出格)當值為“0時表示該點是通路，當值為“1時表示該點是墻。老鼠在迷宮中的位置在任何時候都可以有行號row和列號col表示。（1） 手動生成迷宮void hand_maze(int m,int n) /手動生成迷宮int i,j;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>mazeij;(2)自動生成迷宮void automatic_maze(int m,int n) /自動生成迷宮int i,j;for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機生成0，1maze00=0; /將開始和完畢位置強制為0，保證有可能出來迷宮mazem-1n-1=0;四測試結(jié)果1.手動生成迷宮2.自動生成迷宮3.迷宮開始界面五分析與探討首先明確題目中的條件：（1） 迷宮是一個8*8大小的矩陣。（2） 從迷宮的左上角進入，右下角為迷宮的終點。（3） mazeij=0代表第i+1行第j+1列的點是通路；mazeij=1代表該點是墻，無法通行。（4） 迷宮有兩種生成方式：手工設定和自動生成。（5） 當老鼠處于迷宮中某一點的位置上，它可以向8個方向前進，分別是：“上、下、左、右、左上、左下、右上、右下8個方向。（6） 在實例程序中使用二維數(shù)組mazeN+2N+2 的行，列數(shù)。(不用mazeNN原因是當老鼠跑到了迷宮的邊界點就有可能跳出迷宮，而使用mazeN+2N+2就可以把迷宮的外面再包一層“1，這樣就可以阻止老鼠走出格)當值為“0時表示該點是通路，當值為“1時表示該點是墻。老鼠在迷宮中的位置在任何時候都可以有行號row和列號col表示（7） 老鼠在每一點都有8種方向可以走，分別是：North，NorthEast，East，SouthEast,South,SouthWest,West，NorthWest?？梢杂脭?shù)組move8來表示每一個方向上的橫縱坐標的偏移量，見表3.1。根據(jù)這個數(shù)組，就很容易計算出沿某個方向行走后的下一個點的坐標。 表3.1 8種方向move的偏移量Name dirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW60-1迷宮問題可以用深度優(yōu)先搜索方法實現(xiàn)。當老鼠在迷宮中移動的時候，可能會有許多種移動選擇方向。程序需要記錄并用棧來保存當前點的坐標，然后任意選擇一個方向進展移動。由于應用棧保存了當前通道上各點的坐標，所以當在當前各方向上都走不通時可以返回上一個點，然后選擇另一個方向前進。 可定義element結(jié)構(gòu)用于存儲每一步的橫縱坐標和方向。 typedef struct short int row; short int col; short int dir;element;element stackMAX _STACK_SIZE;根據(jù)表3.1可推算出每次移動后的坐標。設當前的坐標是row,col,移動的方向是dir，移動后的點是next,如此有next_row=row+movedir.vert;next_col=col+movedir.horiz; 可用另一個二維數(shù)組markN+2來記錄哪些點已經(jīng)被訪問過。當經(jīng)過點mazerowcol時，相應地將markrowcol的值從0置為1。 本程序支持自動生成迷宮。利用random2函數(shù)可隨機產(chǎn)生0或1，來支持迷宮的自動生成。注意mazeNN和maze11一定要等于0，因為他們分別是起點和終點。六小結(jié)一周的課程設計完畢了，在這次課程設計中不僅檢驗我所學習的知識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在設計的過程中，和同學們相互探討，相互學習，相互監(jiān)視。我學會了運籌帷幄，學會了寬容，學會了理解，也學會了做人和處世，這次的課程設計對我來說受益良多。通過這次課程設計，更是讓我深刻認識到自己在學習中的不足，同時也找到了克制不足的方法，這也是一筆很大的資源。在以后的時間中，我們應該利用更多的時間去上機實驗，加強自學的能力，多編寫程序，相信不久后我們的編程能力都會有很大的提高。參考文獻1 X振安,X燕君.C程序設計課程設計M.機械工業(yè),2004年9月2 譚浩強.C程序設計第三版.清華大學,2005年7月3 嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版.清華大學,1997年4月4 李志球?qū)嵱肅語言程序設計教程 ：電子工業(yè)，19995 王立柱：C/C+與數(shù)據(jù)結(jié)構(gòu) ：清華大學，20026 吳文虎 程序設計根底 ：清華大學，20037 郭福順，王曉芬，李蓮治 數(shù)據(jù)結(jié)構(gòu)修訂本，某某理工大學，19978 潘道才，陳一華 數(shù)據(jù)結(jié)構(gòu)，電子科技大學，1994附 錄附錄1 源程序清單#include<stdlib.h> /庫中包含system("pause")和rand()函數(shù)#include<stdio.h> /c語言里的庫#include<iostream>using namespace std;#define N 49 /定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改#define M 49int X; int mazeN+2M+2;int head=0,tail=0; /隊列的頭尾指針，初始值設為0struct point /存放迷宮訪問到點的隊列結(jié)構(gòu)體，包含列，行，序號 int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手動生成迷宮int i,j;cout<<endl; cout<<"請按行輸入迷宮，0表示通路，1表示障礙:"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; void automatic_maze(int m,int n) /自動生成迷宮int i,j;cout<<"n迷宮生成中nn"system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機生成0、1maze00=0; /將開始和完畢位置強制為0，保證有可能出來迷宮mazem-1n-1=0;void data(int m,int n) /當用戶輸入的不是規(guī)整的m行n列的迷宮，用來生成規(guī)如此的數(shù)字迷宮int i,j; cout<<endl;cout<<"根據(jù)您先前設定的迷宮X圍"<<endl;cout<<endl;cout<<" 我們將取所輸入的前"<<m*n<<"個數(shù)生成迷宮"<<endl;cout<<"n數(shù)字迷宮生成結(jié)果如下:nn"cout<<"迷宮入口n" cout<<""for(i=0;i<m;i+) cout<<"n"for(j=0;j<n;j+) if(mazeij=0) cout<<" 0"if(mazeij=1) cout<<" 1" cout<<"迷宮出口n"void print_maze(int m,int n) /打印迷宮外殼int i,j,k;cout<<"n字符迷宮生成結(jié)果如下:nn"cout<<"迷宮入口n"cout<<" "cout<<endl;cout<<" " /生成上外殼for(k=0;k<n;k+)cout<<"" /這兩個黑三角用來生成頂部外殼for(i=0;i<m;i+)cout<<"n" /生成左外殼cout<<""for(j=0;j<n;j+) if(mazeij=0) printf("");if(mazeij=1) printf("");cout<<"" /生成右外殼cout<<endl;for(k=0;k<n;k+)cout<<""cout<<" n" /生成底部外殼 for(i=0;i<n;i+)cout<<" " cout<<"n"for(i=0;i<n;i+)cout<<" "cout<<"迷宮出口n"void result_maze(int m,int n) /這個是打印輸出迷宮的星號路徑 int i,j;cout<<"迷宮通路(用表示)如下所示：nt"for(i=0;i<m;i+)cout<<"n"for(j=0;j<n;j+)if(mazeij=0|mazeij=2) /2是隊列中訪問過的點 cout<<""if(mazeij=1) cout<<""if(mazeij=3) /3是標記的可以走通的路徑cout<<""void enqueue(struct point p) /迷宮中隊列入隊操作queuetail=p;tail+; /先用再加，隊列尾部加1struct point dequeue() /迷宮中隊列出隊操作，不需要形參，因此用結(jié)構(gòu)體定義head+;return queuehead-1;int is_empty() /判斷隊列是否為空return head=tail;void visit(int row,int col,int maze5151) /訪問迷宮矩陣中的節(jié)點struct point visit_point=row,col,head-1; /head-1的作用是正在訪問的這個點的序號為之前的點序號maze /將訪問過的點位標記為2enqueue(visit_point);/入隊int path(int maze5151,int m,int n) /路徑求解X=1; /初始值定為1struct point p=0,0,-1; /定義入口節(jié)點if(mazep.rowp.col=1) /入口為1時，迷宮不可解 cout<<"n=n" cout<<"此迷宮無解nn" X=0; return 0; mazep.rowp.col=2; /標記為已訪問 enqueue(p); /將p入隊列while(!is_empty() p=dequeue(); if(p.row=m-1)&&(p.col=n-1) /當行和列為出口時跳出 break; /定義8個走位方向 if(p.row-1)>=0)&&(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)>=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.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)<n)&&(p.col-1)>=0)&&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0)<m)&&(p.col-1)<n)&&(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)<n)&&(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) /如果當前矩陣點是出口點，輸出路徑cout<<"n=n" cout<<"迷宮路徑為：n" cout<<"出口"<<endl; cout<<" "<<""<<endl; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; /逆序?qū)⒙窂綐擞洖? 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 cout<<"n=n" cout<<"此迷宮無解！nn" X=0;return 0;void main() int i,m,n,cycle=0; while(cycle!=(-1) cout<<"*n" cout<<" 歡迎進入迷宮求解系統(tǒng)n" cout<<endl; cout<<" 設計者:姜雯B計算機131班n" cout<<"*n" cout<<" 手動生成迷宮 請按：1n" cout<<" 自動生成迷宮 請按：2n" cout<<" 退出 請按：3nn" cout<<"*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抱歉，你輸入的行列數(shù)超出預設X圍(0-49,0-49),請重新輸入：nn" 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ù) cout<<"nnPress 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抱歉，你輸入的行列數(shù)超出預設X圍(0-49,0-49),請重新輸入：nn" 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<<"nnPress 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;