迷宮最短路徑-數(shù)據(jù)結(jié)構(gòu)-源碼-實驗報告

《迷宮最短路徑-數(shù)據(jù)結(jié)構(gòu)-源碼-實驗報告》由會員分享，可在線閱讀，更多相關(guān)《迷宮最短路徑-數(shù)據(jù)結(jié)構(gòu)-源碼-實驗報告（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實 驗 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實驗名稱 迷宮最短路徑 實驗類型 綜合型 實驗地點 計405機(jī)房 實驗日期 2017.5.13 指導(dǎo)教師 魏海平 專業(yè) 軟件工程 班級 軟件1601 學(xué)號 姓名 寇春雷 遼寧石油化工大學(xué)計算機(jī)與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實驗報告評分表項目要求分?jǐn)?shù)有無項目（）得分預(yù)習(xí)報告（30分）實驗?zāi)康拿鞔_5實驗內(nèi)容理解透徹5實驗方案設(shè)計完整合理程序總體框架設(shè)計完整10完成相關(guān)輔助代碼5測試方案合理5實驗過程（30分）發(fā)現(xiàn)問題5問題的分析15問題的解決方法10實驗報告（20分）內(nèi)容翔實無缺漏5如實記錄實驗過程10撰寫規(guī)整5實驗總結(jié)（10分）實驗結(jié)果的分析5

2、按照結(jié)果對原實驗方案的改進(jìn)意見5實驗體會（10分）實驗的收獲5實驗內(nèi)容的發(fā)散考慮5總分實 驗 二 迷宮最短路徑題目：迷宮最短路徑問題描述從一個迷宮的入口到出口找出一條最短路經(jīng)。用一個二維數(shù)組MAZE(1.m，1.n)模擬迷宮，數(shù)組元素為0表示該位置可以通過，數(shù)組元素為1表示該位置不可以通行。MAZE(1，1)和MAZE(m，n)分別為迷宮的入口和出口?；疽?1)輸入數(shù)據(jù)a.輸入迷宮的大小m行和n列，兩者為整數(shù)b.由隨機(jī)數(shù)產(chǎn)生0或1，建立迷宮。(2)輸出數(shù)據(jù)首先輸出模擬迷宮的二維數(shù)組，若存在最短路經(jīng)，則由出口回朔到入口打印這一條路徑，如下所示： (m，n)， ， (i，j)， ， (1，1)

3、如無通道，則打?。?THERE IS NO PATH.實現(xiàn)提示(1)數(shù)據(jù)結(jié)構(gòu)為了在程序中判斷方便，把迷宮擴(kuò)展成為MAZE(0.m+1，0.n+1)，擴(kuò)展部分的元素設(shè)置為1，相當(dāng)于在迷宮周圍布上一圈不準(zhǔn)通過的墻，這樣，在迷宮的任一位置(I，j)上都有八個可以移動的方向。用二維數(shù)組MOVE(1.8，1.2)存放八個方向上的位置量，如圖所示： (i+MOVE1，1， j+MOVE1，2) (i+MOVE8，1， j+MOVE8，2) (i+MOVE2，1， j+MOVE2，2) (i+MOVE7，1， j+MOVE7，2) (i+MOVE3，1， j+MOVE3，2) (i+MOVE6，1， j+M

4、OVE6，2) (i+MOVE4，1， j+MOVE4，2) (i+MOVE5，1， j+MOVE5，2) MOVE的設(shè)置情況 i j121-102-1130141151061-170-18-1-1為了標(biāo)志已經(jīng)通過的位置，采用一個標(biāo)志數(shù)組MARK（1.m，1.n）初值為0，在尋找路徑的過程中，若通過了位置（i，j），則將MARK（i，j）置為為1。為了記錄查找過程中到達(dá)位置及其前一位置，建立一個Q（1.m*n-1， 0.2）數(shù)組，對于某一個數(shù)組元素Q(P)，其中，Q(P，0)和Q(P，1)記下到達(dá)位置i和j，Q(P，2)記下其出發(fā)點在Q數(shù)組中的下標(biāo)。（2）算法基本思想 將入口（1，1）作為第一

5、個出發(fā)點，依次在八個反方向上搜索可通行的位置，形成第一層新的出發(fā)點，然后對第一層中各個位置分別搜索他所在八個方向上的可通行位置，形成第二層新的出發(fā)點，如此進(jìn)行下去，直至達(dá)到出口(m，n)或者迷宮所有位置都搜索完畢為止。具體實施：從(m，n)開始，將其記入Q數(shù)組，比如記入Q(1)，以它作為第一個出發(fā)點，依次對八個方向進(jìn)行搜索，若下一個位置(I，j)可通行并且尚未經(jīng)過（即MAZE(i，j)=0 且MARK(i，j)=0），則記入Q數(shù)組，如記在Q(P)，則在Q(P，2)中要記下其出發(fā)點在Q數(shù)組中的下標(biāo)1，在八個方向上都搜索過以后，根據(jù)先進(jìn)先出的原則Q從數(shù)組中重新取出一個位置作為新的出發(fā)點（這里，我們

6、實際上把Q數(shù)組作為一個順序表示的隊列），重復(fù)以上過程，若能達(dá)到位置(m ，n)，表示找到最短路徑；若Q數(shù)組中已經(jīng)沒有位置可以作為新的出發(fā)點了，則表示迷宮沒有通路。4.需求分析(1)以二維數(shù)組mazeM+2N+2表示迷宮，其中mazei0和mazeiN+1(0=i=N+1)以及maze0j和mazeM+1j(0=j=0數(shù)據(jù)關(guān)系：R1 | a(i-1),aiD,i = 2,3n基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧S。DestroyStack(&S) 初始結(jié)果：棧S已存在。 操作結(jié)果：銷毀棧S。ClearStack(&S) 初始結(jié)果：棧S已存在。 操作結(jié)果：將S清為空棧。S

7、tackLength(S) 初始結(jié)果：棧S已存在。 操作結(jié)果：返回棧S的長度StackEmpty(S) 初始條件：棧S已存在。 操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSEGetTop(S,&e) 初始條件：棧S已存在。 操作結(jié)果：若棧S不空，則以e返回棧頂元素e。Push(&S,e) 初始條件：棧S已存在。 操作結(jié)果：在棧S的棧頂插入新的棧頂元素。Pop(&S,&e) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse(S,visit() 初始條件：棧S已存在。 操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用visit()ADT Sta

8、ck(2) 設(shè)定迷宮的抽象數(shù)據(jù)類型為：ADT maze 數(shù)據(jù)對象：D = a(i,j) | a(i,j)0,1，0=i=m+1,0=j=n+1,m,n=10 數(shù)據(jù)關(guān)系：R = M，N M = |a(i-1,j)，a(i,j)D,i=1,2,m+1,j=0,1,n+1 N = | a(i,j-1),a(i,j)D,I = 0,1,m+1,j = 1,2,n+1 基本操作： InitMaze(&M,maze,m,n) 初始條件：二維數(shù)組mazem+1n+1 已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障礙。 操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組

9、，以字符0表示通路，以字符1障礙，并在迷宮四周加上一圈障礙。 MazePath(&M)初始條件：迷宮M已被賦值。 操作結(jié)果：若迷宮M中存在一條通路，則按如下規(guī)定改變迷宮M的狀態(tài)：以數(shù)字0代表可通過，數(shù)字1代表不可通過.6.模塊劃分(1) 主程序模塊： void main() int stoMN; struct mark start,end; /start,end入口和出口的坐標(biāo) int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量 initmaze(sto);/建立迷宮 printf(輸入入口的橫坐標(biāo),縱坐標(biāo)逗號隔開n); scanf(%d,%d,&start.x,&sta

10、rt.y); printf(輸入出口的橫坐標(biāo),縱坐標(biāo)逗號隔開n); scanf(%d,%d,&end.x,&end.y); MazePath(start,end,sto,add); /find path system(PAUSE); (2) 棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型；(3) 迷宮模塊實現(xiàn)迷宮抽象數(shù)據(jù)類型，建立迷宮，求解迷宮的一條路徑。7.源程序代碼:#include stdafx.h#include #include#includeint * CreateArr(int m, int n)/創(chuàng)建動態(tài)全局二維數(shù)組int i;int *p;p = (int*)malloc(sizeof(int*)

11、*m);for (i = 0; i =1;i-)j=0;printf(%d,%d),Qij,Qij+1);printf(n); void backtrack(int x,int y,int step,int m,int n)MARKxy=1;int w,v;if(x=m & y=n)flag=1;Qstep0=x;Qstep1=y;print(step);return;elsefor( w=1;w=-1;w-)for( v=1;v=-1;v-)if(w!=0 | v!=0) x+=w;y+=v;step+;/第w，v個值可選 Qstep0=x;Qstep1=y;if(MARKxy=0 & MA

12、ZExy=0) backtrack(x,y,step,m,n);step-;x-=w;y-=v;return;int main()int m,n;printf(請輸入迷宮的行數(shù):nm=);scanf_s(%d,&m);printf(請輸入迷宮的列數(shù):nn=);scanf_s(%d,&n);MAZE = CreateArr(m + 2, n + 2);MARK = CreateArr(m + 2, n + 2);Q = CreateArr(m * n, 2); srand(unsigned)time(NULL);int i,j,p;for(i=0;i=n+1;i+)/第0行用 MAZE0i=-5

13、;MAZEm+1i=-5;for(i=0;i=m+1;i+)/第0列不用 MAZEi0=-5;MAZEin+1=-5;for(i=1;im+1;i+)/其余的隨機(jī)生成0或1 for(j=1;jn+1;j+)p=rand()%10%2;/x的值為0或1 MAZEij=p;MAZE11=0;/入口為0 MAZEmn=0;/出口為0 for(i=1;im+1;i+)/0行0列不顯示 for(j=1;jn+1;j+)printf(%d ,MAZEij);printf(n);/遞歸中超界，對MARK特殊處理 for(i=1;im+1;i+)/MARK全體置為零 for(j=1;jn+1;j+) MARK

14、ij=0; for(i=0;i=m+1;i+) MARKin+1=1;MARKi0=1; for(i=0;i=n+1;i+) MARKm+1i=1; MARK0i=1; MARK11=1;Q10=1;Q11=1;backtrack(1,1,1,m,n); printf(n);if(flag=0)printf(THERE IS NO PATH.n);return 0; 8程序截圖： 9. 實驗總結(jié)1、開始沒有將Mnm.start.end設(shè)置為MAZE 型數(shù)據(jù)的下屬單元，使得各個迷宮操作的函數(shù)參數(shù)十分散雜，調(diào)試時各參數(shù)關(guān)系不易把握。2、另行設(shè)置Print函數(shù)，使得終端輸出更加友好，并巧妙地將迷宮以

15、特殊、明朗的字符輸出，效果更好。3、開始的條件沒有控制好，導(dǎo)致輸出時不是完整路徑，甚至出錯。4、選擇方向時有一定策略，開始選擇時按照順時針依次讀取方向，發(fā)現(xiàn)太耗時且效果不好，容易出現(xiàn)不必要的彎折走法，后來通過控制方向順序，即第一方向為東南方，然后再東方、南方.，選取越靠近出口的方向為優(yōu)先方向，因為這樣的話搜索路徑時自然會本著路徑最短的原則向出口處行進(jìn)，那么找到的路徑自然是最短路徑（之一）。5、由于八個方向的特殊性，根據(jù)方向的順序，搜索路徑時仍會出現(xiàn)多走的情況，比如先往東再往西南，其實是可以直接往南的，因此為了避免這種情況，在入棧時還要先進(jìn)行這種情況的判斷，如是這種情況則出棧將前一位置方向改變再

16、入棧。6、為了便于找到最短路徑，起初只使用了靠近出口處的五個方向，但是發(fā)現(xiàn)有特殊情況存在時由于不能想遠(yuǎn)離出口的方向行進(jìn)而找不到路徑，因此在搜索路徑時進(jìn)行了兩次搜索，第一次使用五個靠進(jìn)出口的方向搜索，找到路徑時則返回，若未搜索到則再進(jìn)行一次八個方向的搜索，即為了防止漏掉特殊情況，找到時則返回，由于第一搜索無結(jié)果若第二次搜索到路徑也只能是特殊情況，故也應(yīng)該是最短路徑（之一）。7、最大的問題是并沒有按照題目要求來做，因為題目中要求用隊列來存儲路徑。10. 實驗心得體會根據(jù)我在課程設(shè)計中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點：1、認(rèn)真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中要考慮

17、周到，嚴(yán)密。3、在做設(shè)計的時候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識，掌握課本中的知識點，并在此基礎(chǔ)上學(xué)會靈活運(yùn)用。5、在課余時間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯誤，以便能節(jié)省調(diào)試程序的時間。每個實驗通常都要花費(fèi)很久的時間才能理清一個程序的思路，而且要不斷的調(diào)試程序才能把程序調(diào)試正確，同時還要做到界面的輸出也是需要美化的。這次課程設(shè)計終于順利完成了，在設(shè)計中遇到了很多專業(yè)知識問題，最后在老師的辛勤指導(dǎo)下，也完成了課程設(shè)計。通過這次的課程設(shè)計，讓我更加了解到數(shù)據(jù)結(jié)構(gòu)的重要性。以及它對我們專業(yè)的發(fā)展發(fā)揮的作用。對我們而言，知識上的收獲很重要，但精神上的豐收更加可喜。讓我知道了學(xué)無止境的道理。我們每一個人永遠(yuǎn)不能滿足于現(xiàn)有的成就。這次課程設(shè)計必將成為我人生旅途上一個非常美好的回憶！同時在做課程設(shè)計時要能夠從多方面去考慮，去研究，用多種算法去實現(xiàn)要求。此次課程設(shè)計，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨立思考解決問題，出現(xiàn)差錯的隨機(jī)應(yīng)變，這些都讓我受益非淺，今后的制作應(yīng)該能夠更輕松，自己也都能夠解決并高質(zhì)量的完成項目。專心-專注-專業(yè)