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

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

1、精選優(yōu)質(zhì)文檔-----傾情為你奉上 實(shí) 驗(yàn) 報(bào) 告 課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)名稱(chēng) 迷宮最短路徑 實(shí)驗(yàn)類(lèi)型 綜合型 實(shí)驗(yàn)地點(diǎn) 計(jì)405機(jī)房 實(shí)驗(yàn)日期 2017.5.13 指導(dǎo)教師 魏海平 專(zhuān)業(yè) 軟件工程 班級(jí) 軟件1601 學(xué)號(hào) 姓名 寇春雷

2、 遼寧石油化工大學(xué)計(jì)算機(jī)與通信工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告評(píng)分表 項(xiàng)目 要求 分?jǐn)?shù) 有無(wú)項(xiàng)目（√） 得分 預(yù)習(xí)報(bào)告 （30分） 實(shí)驗(yàn)?zāi)康拿鞔_ 5 實(shí)驗(yàn)內(nèi)容理解透徹 5 實(shí)驗(yàn)方案設(shè)計(jì)完整合理 程序總體框架設(shè)計(jì)完整 10 完成相關(guān)輔助代碼 5 測(cè)試方案合理 5 實(shí)驗(yàn)過(guò)程 （30分） 發(fā)現(xiàn)問(wèn)題 5 問(wèn)題的分析 15 問(wèn)題的解決方法 10 實(shí)驗(yàn)報(bào)告 （20分） 內(nèi)容翔實(shí)無(wú)缺漏 5 如實(shí)記錄實(shí)驗(yàn)過(guò)程 10 撰寫(xiě)規(guī)整 5

3、 實(shí)驗(yàn)總結(jié) （10分） 實(shí)驗(yàn)結(jié)果的分析 5 按照結(jié)果對(duì)原實(shí)驗(yàn)方案的改進(jìn)意見(jiàn) 5 實(shí)驗(yàn)體會(huì) （10分） 實(shí)驗(yàn)的收獲 5 實(shí)驗(yàn)內(nèi)容的發(fā)散考慮 5 總分 實(shí) 驗(yàn) 二 迷宮最短路徑 題目：迷宮最短路徑 ⒈問(wèn)題描述 從一個(gè)迷宮的入口到出口找出一條最短路經(jīng)。用一個(gè)二維數(shù)組MAZE(1..m，1..n)模擬迷宮，數(shù)組元素為0表示該位置可以通過(guò)，數(shù)組元素為1表示該位置不可以通行。MAZE(1，1)和MAZE(m，n)分別為迷宮的入口和出口。 ⒉基本要求 (1)輸入數(shù)據(jù) a.輸入迷宮的大小m行和n列，兩者為整數(shù) b.由隨機(jī)

4、數(shù)產(chǎn)生0或1，建立迷宮。 (2)輸出數(shù)據(jù) 首先輸出模擬迷宮的二維數(shù)組，若存在最短路經(jīng)，則由出口回朔到入口打印這一條路徑，如下所示： (m，n)， ……， (i，j)， ……， (1，1) 如無(wú)通道，則打?。? THERE IS NO PATH. ⒊實(shí)現(xiàn)提示 (1)數(shù)據(jù)結(jié)構(gòu) ①為了在程序中判斷方便，把迷宮擴(kuò)展成為MAZE(0..m+1，0..n+1)，擴(kuò)展部分的元素設(shè)置為1，相當(dāng)于在迷宮周?chē)忌弦蝗Σ粶?zhǔn)通過(guò)的墻，這樣，在迷宮的任一位置(I，j)上都有八個(gè)可以移動(dòng)的方向。 ②用二維數(shù)組MOVE(1..8，1..2)存放八個(gè)方向上的位置量，如圖所示： (i+MO

5、VE[1，1]， j+MOVE[1，2]) (i+MOVE[8，1]， j+MOVE[8，2]) (i+MOVE[2，1]， j+MOVE[2，2]) (i+MOVE[7，1]， j+MOVE[7，2]) (i+MOVE[3，1]， j+MOVE[3，2]) (i+MOVE[6，1]， j+MOVE[6

6、，2]) (i+MOVE[4，1]， j+MOVE[4，2]) (i+MOVE[5，1]， j+MOVE[5，2]) MOVE的設(shè)置情況 i j 1 2 1 -1 0 2 -1 1 3 0 1 4 1 1 5 1 0 6 1 -1 7 0 -1 8 -1 -1 ③為了標(biāo)志已經(jīng)通過(guò)的位置，采用一個(gè)標(biāo)志數(shù)組MARK（1..m，1..n）初值為0，

7、在尋找路徑的過(guò)程中，若通過(guò)了位置（i，j），則將MARK（i，j）置為為1。 ④為了記錄查找過(guò)程中到達(dá)位置及其前一位置，建立一個(gè)Q（1..m*n-1， 0..2）數(shù)組，對(duì)于某一個(gè)數(shù)組元素Q(P)，其中，Q(P，0)和Q(P，1)記下到達(dá)位置i和j，Q(P，2)記下其出發(fā)點(diǎn)在Q數(shù)組中的下標(biāo)。 （2）算法基本思想 將入口（1，1）作為第一個(gè)出發(fā)點(diǎn)，依次在八個(gè)反方向上搜索可通行的位置，形成第一層新的出發(fā)點(diǎn)，然后對(duì)第一層中各個(gè)位置分別搜索他所在八個(gè)方向上的可通行位置，形成第二層新的出發(fā)點(diǎn)，…，如此進(jìn)行下去，直至達(dá)到出口(m，n)或者迷宮所有位置都搜索完畢為止。 具體實(shí)施：從(m，n)開(kāi)始，

8、將其記入Q數(shù)組，比如記入Q(1)，以它作為第一個(gè)出發(fā)點(diǎn)，依次對(duì)八個(gè)方向進(jìn)行搜索，若下一個(gè)位置(I，j)可通行并且尚未經(jīng)過(guò)（即MAZE(i，j)=0 且MARK(i，j)=0），則記入Q數(shù)組，如記在Q(P)，則在Q(P，2)中要記下其出發(fā)點(diǎn)在Q數(shù)組中的下標(biāo)1，在八個(gè)方向上都搜索過(guò)以后，根據(jù)先進(jìn)先出的原則Q從數(shù)組中重新取出一個(gè)位置作為新的出發(fā)點(diǎn)（這里，我們實(shí)際上把Q數(shù)組作為一個(gè)順序表示的隊(duì)列），重復(fù)以上過(guò)程，若能達(dá)到位置(m ，n)，表示找到最短路徑；若Q數(shù)組中已經(jīng)沒(méi)有位置可以作為新的出發(fā)點(diǎn)了，則表示迷宮沒(méi)有通路。 4.需求分析 (1)以二維數(shù)組maze[M+2][N+2]表示迷宮，其中maz

9、e[i][0]和maze[i][N+1](0=

10、= 1,2，…,n，n>=0} 數(shù)據(jù)關(guān)系：R1{ | a(i-1),ai∈D,i = 2,3…n} 基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧S。 DestroyStack(&S) 初始結(jié)果：棧S已存在。 操作結(jié)果：銷(xiāo)毀棧S。 ClearStack(&S) 初始結(jié)果：棧S已存在。 操作結(jié)果：將S清為空棧。 StackLength(S) 初始結(jié)果：棧S已存在。 操作結(jié)果：返回棧S的長(zhǎng)度 StackEmpty(S) 初始條件：棧S已存

11、在。 操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE GetTop(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é)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用vis

12、it() }ADT Stack (2) 設(shè)定迷宮的抽象數(shù)據(jù)類(lèi)型為： ADT maze{ 數(shù)據(jù)對(duì)象：D = {a(i,j) | a(i,j)∈{0,1}，0=|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

13、,maze,m,n) 初始條件：二維數(shù)組maze[m+1][n+1] 已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障礙。 操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以字符0表示通路，以字符1障礙，并在迷宮四周加上一圈障礙。 MazePath(&M) 初始條件：迷宮M已被賦值。 操作結(jié)果：若迷宮M中存在一條通路，則按如下規(guī)定改變迷宮M的狀態(tài)：以數(shù)字0代表可通過(guò)，數(shù)字1代表不可通過(guò). 6.模塊劃分 (1) 主程序模塊： void main() { int sto

14、[M][N]; struct mark start,end; //start,end入口和出口的坐標(biāo) int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 initmaze(sto);//建立迷宮 printf("輸入入口的橫坐標(biāo),縱坐標(biāo)[逗號(hào)隔開(kāi)]\n"); scanf("%d,%d",&start.x,&start.y); printf("輸入出口的橫坐標(biāo),縱坐標(biāo)[逗號(hào)隔開(kāi)]\n"); scanf("%d,%d",&end.x,&end.y); MazePath(start,end,sto,add); //f

15、ind path system("PAUSE"); } (2) 棧模塊——實(shí)現(xiàn)棧抽象數(shù)據(jù)類(lèi)型； (3) 迷宮模塊——實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類(lèi)型，建立迷宮，求解迷宮的一條路徑。 7.源程序代碼: #include "stdafx.h" #include #include #include int ** CreateArr(int m, int n){//創(chuàng)建動(dòng)態(tài)全局二維數(shù)組 int i; int **p; p = (int**)malloc(sizeof(int*)*m); for (i = 0; i < m;

16、 i++){ p[i] = (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),",Q[i][j],Q[i][j+1]); } printf("\n"); } void backtrack(int x,int y,int step,int m,int n){

17、MARK[x][y]=1; int w,v; if(x==m && y==n){ flag=1; Q[step][0]=x; Q[step][1]=y; print(step); return; }else{ for( w=1;w>=-1;w--){ for( v=1;v>=-1;v--){ if(w!=0 || v!=0){ x+=w;y+=v;step++;//第w，v個(gè)值可選 Q[step][0]=x;Q[step][1]=y; if(MARK[x][y]==0 && MAZE

18、[x][y]==0) backtrack(x,y,step,m,n); step--;x-=w;y-=v; } } } } return; } int main(){ int m,n; printf("請(qǐng)輸入迷宮的行數(shù):\nm="); scanf_s("%d",&m); printf("請(qǐng)輸入迷宮的列數(shù):\nn="); scanf_s("%d",&n); MAZE = CreateArr(m + 2, n + 2); MARK = CreateArr(m + 2, n + 2); Q = CreateArr(m

19、* n, 2); srand((unsigned)time(NULL)); int i,j,p; for(i=0;i<=n+1;i++){//第0行用 MAZE[0][i]=-5; MAZE[m+1][i]=-5; } for(i=0;i<=m+1;i++){//第0列不用 MAZE[i][0]=-5; MAZE[i][n+1]=-5; } for(i=1;i

20、=p; } } MAZE[1][1]=0;//入口為0 MAZE[m][n]=0;//出口為0 for(i=1;i

21、m+1;i++){ MARK[i][n+1]=1; MARK[i][0]=1; } for(i=0;i<=n+1;i++){ MARK[m+1][i]=1; MARK[0][i]=1; } MARK[1][1]=1; Q[1][0]=1; Q[1][1]=1; backtrack(1,1,1,m,n); printf("\n"); if(flag==0) printf("THERE IS NO PATH.\n"); return 0; } 8．程序截圖： 9. 實(shí)驗(yàn)總結(jié)

22、 1、開(kāi)始沒(méi)有將M[n][m].start.end設(shè)置為MAZE 型數(shù)據(jù)的下屬單元，使得各個(gè)迷宮操作的函數(shù)參數(shù)十分散雜，調(diào)試時(shí)各參數(shù)關(guān)系不易把握。 2、另行設(shè)置Print函數(shù)，使得終端輸出更加友好，并巧妙地將迷宮以特殊、明朗的字符輸出，效果更好。 3、開(kāi)始的條件沒(méi)有控制好，導(dǎo)致輸出時(shí)不是完整路徑，甚至出錯(cuò)。 4、選擇方向時(shí)有一定策略，開(kāi)始選擇時(shí)按照順時(shí)針依次讀取方向，發(fā)現(xiàn)太耗時(shí)且效果不好，容易出現(xiàn)不必要的彎折走法，后來(lái)通過(guò)控制方向順序，即第一方向?yàn)闁|南方，然后再東方、南方...，選取越靠近出口的方向?yàn)閮?yōu)先方向，因?yàn)檫@樣的話(huà)搜索路徑時(shí)自然會(huì)本著路徑最短的原則向出口處行進(jìn)，那么找到的路徑自然

23、是最短路徑（之一）。 5、由于八個(gè)方向的特殊性，根據(jù)方向的順序，搜索路徑時(shí)仍會(huì)出現(xiàn)多走的情況，比如先往東再往西南，其實(shí)是可以直接往南的，因此為了避免這種情況，在入棧時(shí)還要先進(jìn)行這種情況的判斷，如是這種情況則出棧將前一位置方向改變?cè)偃霔！? 6、為了便于找到最短路徑，起初只使用了靠近出口處的五個(gè)方向，但是發(fā)現(xiàn)有特殊情況存在時(shí)由于不能想遠(yuǎn)離出口的方向行進(jìn)而找不到路徑，因此在搜索路徑時(shí)進(jìn)行了兩次搜索，第一次使用五個(gè)靠進(jìn)出口的方向搜索，找到路徑時(shí)則返回，若未搜索到則再進(jìn)行一次八個(gè)方向的搜索，即為了防止漏掉特殊情況，找到時(shí)則返回，由于第一搜索無(wú)結(jié)果若第二次搜索到路徑也只能是特殊情況，故也應(yīng)該是最短路徑

24、（之一）。 7、最大的問(wèn)題是并沒(méi)有按照題目要求來(lái)做，因?yàn)轭}目中要求用隊(duì)列來(lái)存儲(chǔ)路徑。 10. 實(shí)驗(yàn)心得體會(huì) 根據(jù)我在課程設(shè)計(jì)中遇到得問(wèn)題，我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn)： 1、認(rèn)真上好專(zhuān)業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。 2、寫(xiě)程序的過(guò)程中要考慮周到，嚴(yán)密。 3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。 4、認(rèn)真的學(xué)習(xí)課本知識(shí)，掌握課本中的知識(shí)點(diǎn)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。 5、在課余時(shí)間里多寫(xiě)程序，熟練掌握在調(diào)試程序的過(guò)程中所遇到的常見(jiàn)錯(cuò)誤，以便能節(jié)省調(diào)試程序的時(shí)間。 每個(gè)實(shí)驗(yàn)通常都要花費(fèi)很久的時(shí)間才能理清一個(gè)程序的思路，而且要不斷的調(diào)試程序才能把程序調(diào)試正確，同時(shí)還要做

25、到界面的輸出也是需要美化的。這次課程設(shè)計(jì)終于順利完成了，在設(shè)計(jì)中遇到了很多專(zhuān)業(yè)知識(shí)問(wèn)題，最后在老師的辛勤指導(dǎo)下，也完成了課程設(shè)計(jì)。 通過(guò)這次的課程設(shè)計(jì)，讓我更加了解到數(shù)據(jù)結(jié)構(gòu)的重要性。以及它對(duì)我們專(zhuān)業(yè)的發(fā)展發(fā)揮的作用。對(duì)我們而言，知識(shí)上的收獲很重要，但精神上的豐收更加可喜。讓我知道了學(xué)無(wú)止境的道理。我們每一個(gè)人永遠(yuǎn)不能滿(mǎn)足于現(xiàn)有的成就。這次課程設(shè)計(jì)必將成為我人生旅途上一個(gè)非常美好的回憶！同時(shí)在做課程設(shè)計(jì)時(shí)要能夠從多方面去考慮，去研究，用多種算法去實(shí)現(xiàn)要求。此次課程設(shè)計(jì)，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨(dú)立思考解決問(wèn)題，出現(xiàn)差錯(cuò)的隨機(jī)應(yīng)變，這些都讓我受益非淺，今后的制作應(yīng)該能夠更輕松，自己也都能夠解決并高質(zhì)量的完成項(xiàng)目。 專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)