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

精選優(yōu)質文檔-傾情為你奉上實 驗 報 告課程名稱 數(shù)據(jù)結構 實驗名稱 迷宮最短路徑 實驗類型 綜合型 實驗地點 計405機房 實驗日期 2017.5.13 指導教師 魏海平 專業(yè) 軟件工程 班級 軟件1601 學號 姓名 寇春雷 遼寧石油化工大學計算機與通信工程學院數(shù)據(jù)結構實驗報告評分表項目要求分數(shù)有無項目（）得分預習報告（30分）實驗目的明確5實驗內容理解透徹5實驗方案設計完整合理程序總體框架設計完整10完成相關輔助代碼5測試方案合理5實驗過程（30分）發(fā)現(xiàn)問題5問題的分析15問題的解決方法10實驗報告（20分）內容翔實無缺漏5如實記錄實驗過程10撰寫規(guī)整5實驗總結（10分）實驗結果的分析5按照結果對原實驗方案的改進意見5實驗體會（10分）實驗的收獲5實驗內容的發(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.由隨機數(shù)產(chǎn)生0或1，建立迷宮。(2)輸出數(shù)據(jù)首先輸出模擬迷宮的二維數(shù)組，若存在最短路經(jīng)，則由出口回朔到入口打印這一條路徑，如下所示： (m，n)， ， (i，j)， ， (1，1)如無通道，則打?。?THERE IS NO PATH.實現(xiàn)提示(1)數(shù)據(jù)結構為了在程序中判斷方便，把迷宮擴展成為MAZE(0.m+1，0.n+1)，擴展部分的元素設置為1，相當于在迷宮周圍布上一圈不準通過的墻，這樣，在迷宮的任一位置(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+MOVE6，2) (i+MOVE4，1， j+MOVE4，2) (i+MOVE5，1， j+MOVE5，2) MOVE的設置情況 i j121-102-1130141151061-170-18-1-1為了標志已經(jīng)通過的位置，采用一個標志數(shù)組MARK（1.m，1.n）初值為0，在尋找路徑的過程中，若通過了位置（i，j），則將MARK（i，j）置為為1。為了記錄查找過程中到達位置及其前一位置，建立一個Q（1.m*n-1， 0.2）數(shù)組，對于某一個數(shù)組元素Q(P)，其中，Q(P，0)和Q(P，1)記下到達位置i和j，Q(P，2)記下其出發(fā)點在Q數(shù)組中的下標。（2）算法基本思想 將入口（1，1）作為第一個出發(fā)點，依次在八個反方向上搜索可通行的位置，形成第一層新的出發(fā)點，然后對第一層中各個位置分別搜索他所在八個方向上的可通行位置，形成第二層新的出發(fā)點，如此進行下去，直至達到出口(m，n)或者迷宮所有位置都搜索完畢為止。具體實施：從(m，n)開始，將其記入Q數(shù)組，比如記入Q(1)，以它作為第一個出發(fā)點，依次對八個方向進行搜索，若下一個位置(I，j)可通行并且尚未經(jīng)過（即MAZE(i，j)=0 且MARK(i，j)=0），則記入Q數(shù)組，如記在Q(P)，則在Q(P，2)中要記下其出發(fā)點在Q數(shù)組中的下標1，在八個方向上都搜索過以后，根據(jù)先進先出的原則Q從數(shù)組中重新取出一個位置作為新的出發(fā)點（這里，我們實際上把Q數(shù)組作為一個順序表示的隊列），重復以上過程，若能達到位置(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<=M+1)為外加的一圈圍墻。數(shù)組中元素0表示障礙1表示可通過，迷宮的大小可不限；(2) 迷宮中的數(shù)據(jù)均由用戶自由輸入；(3) 迷宮的出口和入口可由用戶自由設定；(4) 本程序只求出一條成功的通路；(5) 程序執(zhí)行的命令為： 創(chuàng)建迷宮 求解迷宮 輸出迷宮的解5. 概要設計 5.1 抽象數(shù)據(jù)類型定義(1)設定棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象：D=ai | aiCharSet，i = 1,2，,n，n>=0數(shù)據(jù)關系：R1<a(i-1)> | a(i-1),aiD,i = 2,3n基本操作： InitStack(&S) 操作結果：構造一個空棧S。DestroyStack(&S) 初始結果：棧S已存在。 操作結果：銷毀棧S。ClearStack(&S) 初始結果：棧S已存在。 操作結果：將S清為空棧。StackLength(S) 初始結果：棧S已存在。 操作結果：返回棧S的長度StackEmpty(S) 初始條件：棧S已存在。 操作結果：若S為空棧，則返回TRUE，否則返回FALSEGetTop(S,&e) 初始條件：棧S已存在。 操作結果：若棧S不空，則以e返回棧頂元素e。Push(&S,e) 初始條件：棧S已存在。 操作結果：在棧S的棧頂插入新的棧頂元素。Pop(&S,&e) 初始條件：棧S已存在。 操作結果：刪除S的棧頂元素，并以e返回其值。StackTraverse(S,visit() 初始條件：棧S已存在。 操作結果：從棧底到棧頂依次對S中的每個元素調用visit()ADT Stack(2) 設定迷宮的抽象數(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ù)關系：R = M，N M = <a(i-1,j)，a(i,j)>|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)> | 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表示障礙。 操作結果：構成迷宮的字符型數(shù)組，以字符0表示通路，以字符1障礙，并在迷宮四周加上一圈障礙。 MazePath(&M)初始條件：迷宮M已被賦值。 操作結果：若迷宮M中存在一條通路，則按如下規(guī)定改變迷宮M的狀態(tài)：以數(shù)字0代表可通過，數(shù)字1代表不可通過.6.模塊劃分(1) 主程序模塊： void main() int stoMN; struct mark start,end; /start,end入口和出口的坐標 int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量 initmaze(sto);/建立迷宮 printf("輸入入口的橫坐標,縱坐標逗號隔開n"); scanf("%d,%d",&start.x,&start.y); printf("輸入出口的橫坐標,縱坐標逗號隔開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 <stdio.h>#include<cstdlib>#include<ctime>int * CreateArr(int m, int n)/創(chuàng)建動態(tài)全局二維數(shù)組int i;int *p;p = (int*)malloc(sizeof(int*)*m);for (i = 0; i < m; i+)pi = (int*)malloc(sizeof(int)*n);return (p);int *MAZE;int *MARK;int *Q;int flag=0;void print(int step)int i,j;for(i=step;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 && MAZExy=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;MAZEm+1i=-5;for(i=0;i<=m+1;i+)/第0列不用 MAZEi0=-5;MAZEin+1=-5;for(i=1;i<m+1;i+)/其余的隨機生成0或1 for(j=1;j<n+1;j+)p=rand()%10%2;/x的值為0或1 MAZEij=p;MAZE11=0;/入口為0 MAZEmn=0;/出口為0 for(i=1;i<m+1;i+)/0行0列不顯示 for(j=1;j<n+1;j+)printf("%d ",MAZEij);printf("n");/遞歸中超界，對MARK特殊處理 for(i=1;i<m+1;i+)/MARK全體置為零 for(j=1;j<n+1;j+) MARKij=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. 實驗總結1、開始沒有將Mnm.start.end設置為MAZE 型數(shù)據(jù)的下屬單元，使得各個迷宮操作的函數(shù)參數(shù)十分散雜，調試時各參數(shù)關系不易把握。2、另行設置Print函數(shù)，使得終端輸出更加友好，并巧妙地將迷宮以特殊、明朗的字符輸出，效果更好。3、開始的條件沒有控制好，導致輸出時不是完整路徑，甚至出錯。4、選擇方向時有一定策略，開始選擇時按照順時針依次讀取方向，發(fā)現(xiàn)太耗時且效果不好，容易出現(xiàn)不必要的彎折走法，后來通過控制方向順序，即第一方向為東南方，然后再東方、南方.，選取越靠近出口的方向為優(yōu)先方向，因為這樣的話搜索路徑時自然會本著路徑最短的原則向出口處行進，那么找到的路徑自然是最短路徑（之一）。5、由于八個方向的特殊性，根據(jù)方向的順序，搜索路徑時仍會出現(xiàn)多走的情況，比如先往東再往西南，其實是可以直接往南的，因此為了避免這種情況，在入棧時還要先進行這種情況的判斷，如是這種情況則出棧將前一位置方向改變再入棧。6、為了便于找到最短路徑，起初只使用了靠近出口處的五個方向，但是發(fā)現(xiàn)有特殊情況存在時由于不能想遠離出口的方向行進而找不到路徑，因此在搜索路徑時進行了兩次搜索，第一次使用五個靠進出口的方向搜索，找到路徑時則返回，若未搜索到則再進行一次八個方向的搜索，即為了防止漏掉特殊情況，找到時則返回，由于第一搜索無結果若第二次搜索到路徑也只能是特殊情況，故也應該是最短路徑（之一）。7、最大的問題是并沒有按照題目要求來做，因為題目中要求用隊列來存儲路徑。10. 實驗心得體會根據(jù)我在課程設計中遇到得問題，我將在以后的學習過程中注意以下幾點：1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴密。3、在做設計的時候要有信心，有耐心，切勿浮躁。4、認真的學習課本知識，掌握課本中的知識點，并在此基礎上學會靈活運用。5、在課余時間里多寫程序，熟練掌握在調試程序的過程中所遇到的常見錯誤，以便能節(jié)省調試程序的時間。每個實驗通常都要花費很久的時間才能理清一個程序的思路，而且要不斷的調試程序才能把程序調試正確，同時還要做到界面的輸出也是需要美化的。這次課程設計終于順利完成了，在設計中遇到了很多專業(yè)知識問題，最后在老師的辛勤指導下，也完成了課程設計。通過這次的課程設計，讓我更加了解到數(shù)據(jù)結構的重要性。以及它對我們專業(yè)的發(fā)展發(fā)揮的作用。對我們而言，知識上的收獲很重要，但精神上的豐收更加可喜。讓我知道了學無止境的道理。我們每一個人永遠不能滿足于現(xiàn)有的成就。這次課程設計必將成為我人生旅途上一個非常美好的回憶！同時在做課程設計時要能夠從多方面去考慮，去研究，用多種算法去實現(xiàn)要求。此次課程設計，學到了很多課內學不到的東西，比如獨立思考解決問題，出現(xiàn)差錯的隨機應變，這些都讓我受益非淺，今后的制作應該能夠更輕松，自己也都能夠解決并高質量的完成項目。專心-專注-專業(yè)