空間數(shù)據結構作業(yè)3 張弛 20133285 測繪一班

1、空間數(shù)據結構作業(yè)報告學號：20133285姓名：張弛班級：測繪一班學院：地球科學與環(huán)境工程學院教師：胡亞 2015年11月3日目錄實驗題3.53任務要求 3源程序3運行結果6心得體會6實驗題3.5任務要求 編寫一個求解迷宮問題的程序exp-5.cpp,要求輸出圖3.23所示的迷宮的所有路徑，并求最短路徑長度及最短路徑。源程序#include #define M 4/行數(shù)#define N 4/列數(shù)#define MaxSize 100/棧最多元素個數(shù)int mgM+2N+2=/一個迷宮,其四周要加上均為1的外框1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,

2、0,1,1,1,1,0,0,0,1,1,1,1,1,1,1;struct int i,j;int di; StackMaxSize,PathMaxSize;/定義棧和存放最短路徑的數(shù)組int top=-1;/棧頂指針int count=1;/路徑數(shù)計數(shù)int minlen=MaxSize;/最短路徑長度void mgpath(int xi,int yi,int xe,int ye)/求迷宮路徑int i,j,di,find,k;top+;/進棧Stacktop.i=xi;Stacktop.j=yi;Stacktop.di=-1;mgxiyi=-1;/初始方塊進棧while (top-1)/棧不

3、空時循環(huán)i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if (i=xe & j=ye)/找到了出口,輸出路徑 printf(%4d: ,count+);for (k=0;k=top;k+)printf(%d,%d) ,Stackk.i,Stackk.j);if (k+1)%5=0) printf(nt);/輸出時每5個方塊換一行printf(n);if (top+1minlen)/比較找最短路徑for (k=0;k=top;k+)Pathk=Stackk;minlen=top+1;mgStacktop.iStacktop.j=0;/讓該位置變?yōu)槠渌窂娇勺叻?/p>

4、塊top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;find=0;while (di4 & find=0)/找下一個可走方塊di+;switch(di)case 0:i=Stacktop.i-1;j=Stacktop.j;break;case 1:i=Stacktop.i;j=Stacktop.j+1;break;case 2:i=Stacktop.i+1;j=Stacktop.j;break;case 3:i=Stacktop.i,j=Stacktop.j-1;break;if (mgij=0) find=1;if (find=1)/找到了下一個可

5、走方塊Stacktop.di=di;/修改原棧頂元素的di值top+;Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;/下一個可走方塊進棧mgij=-1;/避免重復走到該方塊else/沒有路徑可走,則退棧mgStacktop.iStacktop.j=0; /讓該位置變?yōu)槠渌窂娇勺叻綁Ktop-;printf(最短路徑如下:n);printf(長度: %dn,minlen);printf(路徑: );for (k=0;kminlen;k+)printf(%d,%d) ,Pathk.i,Pathk.j);if (k+1)%5=0) printf(nt); /輸出時

6、每5個方塊換一行printf(n);void main()printf(迷宮所有路徑如下:n);mgpath(1,1,M,N);int i;scanf(%d,&i);運行結果心得體會通過完成這次編程練習，我覺得自己有很大的收獲。首先，在編程之前，我一遍又一遍地翻看了教材以及老師上課講的課件，了解了迷宮問題的一些實質內容，以及棧和隊列的本質及應用。但是在某些地方還是有些不懂，于是請教一些同學，解決了一些問題，剩下的問題，在今天的課堂上請教老師，在老師的幫助下，我將課件上運用棧來解迷宮問題的程序與老師上傳的課后習題的程序對比，發(fā)現(xiàn)兩者的不同，這是由解決問題的目的所決定的。前者注重走出迷宮，最后得到的是一條路徑，后者注重窮舉所有能走出的路徑并比較出最短路徑。這些區(qū)別決定了編寫程序語言的不同。另外可以運用隊列直接求出迷宮最短路徑，我感覺棧和隊列各有千秋，棧比較全面，但可能繁瑣；隊列注重效率，可以求出最短路徑，簡單，但內容有局限，不如棧更全面。但是我們可以根據實際要求，合理選擇他們，加以運用。這次練習讓我初步體會到棧和隊列的應用，他們在解決實際生活問題中起到巨大