[畢業(yè)設(shè)計精品]迷宮問題

1、課 程 設(shè) 計題 目迷宮問題學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)計算機科學(xué)與技術(shù)班 級計算機科學(xué)與技術(shù)0909班姓 名指導(dǎo)教師2011年7月2日課程設(shè)計任務(wù)書題 目: 迷宮問題 初始條件： 以一個mn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1），（1,2,2），（2,2,2）

2、，（3,2,3），（3,1,2），。 測試用例見題集p105。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）課程設(shè)計報告按學(xué)校規(guī)定格式用a4紙打?。〞鴮懀?，并應(yīng)包含如下內(nèi)容： 1、 問題描述簡述題目要解決的問題是什么。2、 設(shè)計存儲結(jié)構(gòu)設(shè)計、主要算法設(shè)計（用類c語言或用框圖描述）、測試用例設(shè)計；3、 調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設(shè)計和編碼的討論和分析。4、 經(jīng)驗和體會（包括對算法改進的設(shè)想）5、 附源程序清單和運行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運行結(jié)果要包含這些測試數(shù)據(jù)和運行輸出，6、 設(shè)計報告、程序不得相互抄襲和拷貝；若有

3、雷同，則所有雷同者成績均為0分。時間安排：1、第19周完成。2、7月1 日14：00到計算中心檢查程序、交課程設(shè)計報告、源程序（cd盤）。指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日目錄1、問題描述與需求分析31.1 問題描述312 需求分析32、設(shè)計32.1 設(shè)計原理32.2 儲存結(jié)構(gòu)設(shè)計42.2.1 設(shè)定棧的抽象數(shù)據(jù)類型定義：42.2.2 設(shè)定迷宮的抽象數(shù)據(jù)類型為：62.3 詳細設(shè)計72.3.2、棧模塊：82.3.3 主程序模塊：122.3.4 函數(shù)調(diào)用關(guān)系的層次結(jié)構(gòu)框圖：142.4 測試用例設(shè)計143、調(diào)試報告153.1 遇到的問題及解決辦法153.2 對設(shè)計和編碼的

4、討論與分析154、經(jīng)驗和體會165、源程序和運行結(jié)果165.1 源程序165.2 運行結(jié)果216、參考文獻23題目：迷宮問題1、問題描述與需求分析1.1 問題描述 以一個mn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3

5、,1,2），12 需求分析 （1）以二維數(shù)組mazem+2n+2表示迷宮，其中：maze0j和mazem+1j(0=j=n+1)及mazei0和mazein+1 (0=i=n+1)為添加的一圈障礙。數(shù)組中一元素值為0表示通路，1表示障礙。（2）其中迷宮的入口位置和出口位置可由用戶隨時設(shè)定。（3）迷宮內(nèi)墻的編寫，用1表示內(nèi)墻，0表示通路。（4）以鏈表作存儲結(jié)構(gòu)的棧類型，實現(xiàn)求解迷宮的非遞歸程序。（5）本程序只求出一條成功的通路，然而，只需要對迷宮求解的函數(shù)作小量修改，便可求得全部路徑。2、設(shè)計2.1 設(shè)計原理主要采取三大模塊：主程序模塊、棧模塊和迷宮模塊棧模塊：實現(xiàn)迷宮數(shù)據(jù)的抽象化和對迷宮數(shù)據(jù)的

6、處理； 迷宮模塊：實現(xiàn)迷宮數(shù)據(jù)抽象類型；主程序模塊：初始化迷宮模塊。棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型迷宮模塊實現(xiàn)迷宮抽象數(shù)據(jù)類型主程序模塊：void main() 初始化； do 接受命令； 處理命令； while(命令！=“退出”)；各模塊之間的調(diào)用關(guān)系如下：主程序模塊迷宮模塊棧模塊2.2 儲存結(jié)構(gòu)設(shè)計2.2.1 設(shè)定棧的抽象數(shù)據(jù)類型定義：adt stack 數(shù)據(jù)對象：d= ai|ai charset,i=1,2,n,n0 數(shù)據(jù)關(guān)系：r1=| ai-1 , ai d,i=2,n 基本操作： initstack(&s) 操作結(jié)果：構(gòu)造一個空棧s。 destroystack(&s) 初始條件：棧s已存在

7、。 操作結(jié)果：銷毀棧s。 clearstack(&s) 初始條件：棧s已存在。 操作結(jié)果：將s清為空棧。 stacklength(s)初始條件：棧s已存在。 操作結(jié)果：返回棧s的長度。 stackempty(s) 初始條件：棧s已存在。 操作結(jié)果：若s為空棧，則返回true,否則返回false。 gettop(s,&e) 初始條件：棧s已存在。 操作結(jié)果：若棧s不空，則以e返回棧頂元素。 push(&s,e) 初始條件：棧s已存在。 操作結(jié)果：在棧s的棧頂插入信的棧頂元素e。 pop(&s,&e) 初始條件：棧s已存在。 操作結(jié)果：刪除s的棧頂元素，并以e返回其值。 stacktraverse

8、(s,visit() 初始條件：棧s已存在。 操作結(jié)果：從棧底到棧頂一次對s中的每個元素調(diào)用函數(shù)visit（）。adt stack2.2.2 設(shè)定迷宮的抽象數(shù)據(jù)類型為：adt maze 數(shù)據(jù)對象：d=ai,j | ai,j 0,1,0im+1,0jn+1,m,n10 數(shù)據(jù)關(guān)系：r=row,col row= | ai-1,j , ai-1d,i=1,m+1,j=0,n+1 col= | ai,j-1 , ai-1d,i=1,m+1,j=0,n+1 initmaze (&m ,a ,row , col )初始條件：二維數(shù)組arow+2col+2已經(jīng)存在，其中自第一行至第row+1行、每行中自第1列

9、至第col+1列的元素已經(jīng)有值，并且以值0表示通路，以值1表示障礙。操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，并在迷宮四周加上一圈障礙。 mazepath (&m)初始條件：迷宮m已被賦值。操作結(jié)果：若迷宮m中存在一條通路，則按照所走的步驟，從小到大依次排列。 printmaze (m)初始條件：迷宮m已存在。操作結(jié)果：已字符形式輸出迷宮。adt maze;2.2.3 尋找公共路徑的思想圖如下：設(shè)定當(dāng)前為出始值的入口：do 若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂； 若該位置是出口位置，則結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則 若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置

10、為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一鄰塊； 若棧不為空且棧頂位置的四周均不可通， 則刪除棧頂位置； 若棧不為空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至棧空； 2.3 詳細設(shè)計2.3.1迷宮模塊：以二維數(shù)組mazem+2n+2表示迷宮，其中：maze0j和mazem+1j(0=j=n+1)及mazei0和mazein+1 (0=i=n+1)為添加的一圈障礙。數(shù)組中一元素值為0表示通路，1表示障礙，限定迷宮的大小m,n=(*s).stacksize) /* 棧滿，追加存儲空間 */ (*s).base=(selemtype *)realloc(*s).base,(*s).st

11、acksize+stackincrement)*sizeof(selemtype); if(!(*s).base) exit(1); /* 存儲分配失敗 */ (*s).top=(*s).base+(*s).stacksize; (*s).stacksize+=stackincrement; *(*s).top)+=e; return true;判斷棧是否為空：bool stackempty(sqstack s) /* 若棧s為空棧，則返回true，否則返回false*/ if(s.top=s.base) return true; else return false;刪除棧頂元素使之為空：bo

12、ol pop(sqstack *s,selemtype *e) /* 若棧不空，則刪除s的棧頂元素，用e返回其值，并返回true；否則返回false */ if(*s).top=(*s).base) return false; *e=*-(*s).top; return true;bool mazepath(postype start,postype end) /* 算法3.3 */ /* 若迷宮maze中存在從入口start到出口end的通道，則求得一條 */ /* 存放在棧中(從棧底到棧頂)，并返回true；否則返回false */ sqstack s; postype curpos; s

13、elemtype e; initstack(&s); curpos=start; do if(pass(curpos) /* 當(dāng)前位置可以通過，即是未曾走到過的通道塊 */ footprint(curpos); /* 留下足跡 */ e.ord=curstep; acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di=0; push(&s,e); /* 入棧當(dāng)前位置及狀態(tài) */ curstep+; /* 足跡加1 */ if(curpos.x=end.x&curpos.y=end.y) /* 到達終點(出口)

14、*/ return true; curpos=nextpos(curpos,e.di); else /* 當(dāng)前位置不能通過 */ if(!stackempty(s) pop(&s,&e); /* 退棧到前一位置 */curpos=e.seat;-curstep; while(e.di=3) & (!stackempty(s) / 前一位置處于最后一個方向(北) markprint(e.seat); /* 留下不能通過的標(biāo)記(-1) */ pop(&s,&e); /* 退回一步 */ curstep-; if(e.di3) /* 沒到最后一個方向(北) */ e.di+; /* 換下一個方向探索

15、 */ push(&s,e); acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di; curstep+; curpos=nextpos(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 while(!stackempty(s); return false;2.3.3 主程序模塊：void main()do 接受命令；處理命令；while(命令!=“退出”)程序如下：void main() postype begin,end; int i,j,x,y,x1,y1; coutxy; for(i=

16、0;ix;i+) /* 定義周邊值為1(同墻) */ m0i=1; /* 行周邊 */ mx-1i=1; for(j=0;jy;j+) mj0=1; /* 列周邊 */ mjy-1=1; for(i=1;ix-1;i+) for(j=1;jy-1;j+) mij=0; /* 定義通道初值為0 */ coutj; cout請依次輸入迷宮內(nèi)墻每個單元的行數(shù),列數(shù)：endl; for(i=1;ix1y1; mx1y1=1; /* 定義墻的值為1 */ cout迷宮結(jié)構(gòu)如下:endl; print(x,y); coutbegin.xbegin.y; coutend.xend.y; if(mazepat

17、h(begin,end) /* 求得一條通路 */ cout此迷宮從入口到出口的一條路徑如下:endl; print(x,y); /* 輸出此通路 */ cout迷宮所走過路徑的坐標(biāo)及方向(0代表右,1代表下,2代表左,3代表上):endl; for(i=1;icurstep;i+) cout(ai,bi,ci)endl; else cout此迷宮沒有從入口到出口的路徑endl;2.3.4 函數(shù)調(diào)用關(guān)系的層次結(jié)構(gòu)框圖：主程序samenextposmarkprintpassfootprintpushinitstackinitmazeinitializationreadcommandinterpr

18、etmazepathprintmazepopstackemptystacktraverse 2.4 測試用例設(shè)計 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000上面的測試數(shù)據(jù)是沒有加邊墻的，在本程序中要加上四周的邊墻。另外，本程序是運用內(nèi)墻的數(shù)量來定位的，本測試設(shè)計內(nèi)墻總共有26（有26個1）。3、調(diào)試報告3.1 遇到的問題及解決辦法（1）這次的課程設(shè)計程序大多來自于教科書和練習(xí)冊，相對比較容易。但也會出現(xiàn)很多錯誤，在定義外墻時，粗心地將循環(huán)初始值j定為1，在剛開始調(diào)

19、試時用了一個簡單的例子，沒發(fā)現(xiàn)這個錯誤，以至于到后面查看要求的示例時，出現(xiàn)了最后一行外墻為0的狀況。解決這種狀況只需將其初始值變?yōu)?，并把控制條件改為jy即可。（2）在編寫mazepath函數(shù)時，當(dāng)遇到墻（即遇到下一位置為1）時，直接從現(xiàn)在墻位置進行往南跳轉(zhuǎn)。以至有許多應(yīng)該走的通路位置沒有走，而且使總共走的步數(shù)變短。在測試前期怎么也想不明白，出棧操作也有，curstep退位也有，但就是不進行退到上一位置的操作。最后發(fā)現(xiàn)，少了一步把出棧的數(shù)進行賦值的操作。只要進行curpos=e.seat的操作，上面的問題就迎刃而解了。（3）在進行對迷宮的輸出時，變成按行輸出，得不到預(yù)期的迷宮結(jié)果，更不用說驗證

20、其正確性。這就是粗心造成的，本來為簡潔，就不用在下行再寫cout了，直接就在coutmij后加了endl，這使得每出一個數(shù)就會換行，而導(dǎo)致輸出的迷宮出錯。（4）在編寫do while 語句時，另一種情況（即當(dāng)前位置不能通過時）也同樣出現(xiàn)在墻節(jié)點就直接往南走的情況，綜合上面的情況，同樣的，也是退位沒有賦值。這種錯誤比較難發(fā)現(xiàn)，往往只有在復(fù)雜的迷宮求解過程中才能發(fā)現(xiàn)。這類錯誤屬于邏輯錯誤，調(diào)試不會顯示，需要自己拙句地查看和分析，并能充分的理解程序每一步的認識，才能發(fā)現(xiàn)并解決這樣的問題。3.2 對設(shè)計和編碼的討論與分析（1）剛著手這個迷宮問題，首先要解決的就有兩大問題，如何儲存這樣的迷宮，如何實現(xiàn)求

21、解迷宮？由于我們用的計算機的高計算特點，我們可以用窮舉法來尋找迷宮的解。于是，又有問題了，如何窮舉？該怎么窮舉就不會出錯？根據(jù)習(xí)題冊上的實例，可以分為四個方向挨個探索。至于，如何儲存并實現(xiàn)這個迷宮，就得依賴于棧和二維數(shù)組。（2）在具體編碼時，也會遇到很多問題，譬如根據(jù)書上的一些代碼的運用會出現(xiàn)錯誤，需要自己動手，動腦親自編寫。這樣有助于對數(shù)據(jù)結(jié)構(gòu)的理解，同時也達到了這門課程設(shè)計的實驗?zāi)康摹?、經(jīng)驗和體會通過這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，讓我學(xué)會了很多，譬如迷宮的實現(xiàn)，面對問題時應(yīng)該怎樣解決。同時，也讓我對棧這一章節(jié)有更深的體會，以及用不同的方法解決同意問題。相比較得出較好的解決方案。拿實現(xiàn)迷宮解的通

22、路來說，按照題目的要求要實現(xiàn)三位數(shù)代表通路的路徑和方向。通過對題目的研究，我們可以得出三位數(shù)的前兩位是這個節(jié)點的坐標(biāo)，另一個數(shù)則是表示方向的，同時我們也可以讓第一個數(shù)據(jù)表示方向，后兩位表示節(jié)點坐標(biāo)。這樣，為實現(xiàn)這個要求，我們可以定義三個一維數(shù)組。分別表示不同的數(shù)，在解決路徑上標(biāo)識每一步的序號，通過這個序號來實現(xiàn)不同數(shù)組的賦值。同時也是對棧的應(yīng)用。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的主要目的是介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們在計算機中的存儲表示，并結(jié)合各種數(shù)據(jù)結(jié)構(gòu)，討論對他們實行的各種運算的實現(xiàn)算法。通過本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，讓我學(xué)到了很多有用的知識，在實際操作中也犯了很多錯誤，這些錯

23、誤同時也讓我意外的收獲了很多。對我所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識理論也得到鞏固。通過實際的設(shè)計和分析，讓我學(xué)會了編程的基本步驟和方法，同時也開發(fā)了自己的邏輯思維能力，培養(yǎng)了份額系問題、解決問題的能力。在不斷的遇到問題，不斷的解決問題的過程中，培養(yǎng)的專業(yè)的思維是最重要的，也是這次課程設(shè)計所要達到的目的，我很慶幸我做到了。5、源程序和運行結(jié)果5.1 源程序#includeusing namespace std;struct postype /迷宮坐標(biāo)位 int x; /行值 int y; / 列值 ;#define maxlength 25 typedef int mazetypemaxlengthmaxle

24、ngth; /* 迷宮數(shù)組行列 */ mazetype m; / 迷宮數(shù)組 int curstep=1; /當(dāng)前足跡,初值為1 int amaxlength; int bmaxlength; int cmaxlength; struct selemtype/* 棧的元素類型 */ int ord; /* 通道塊在路徑上的序號 */ postype seat; /* 通道塊在迷宮中的坐標(biāo)位置 */ int di; /* 從此通道塊走向下一通道塊的方向(03表示東北) */ ;#define stack_init_size 10 #define stackincrement 2 struct sq

25、stack selemtype *base; selemtype *top; int stacksize; ; /* 順序棧 */ bool pass(postype b) /* 當(dāng)迷宮m的b點的序號為0(可通過路徑)，return true, 否則，return false。 */ if(mb.xb.y=0) return true; else return false; void footprint(postype a) /使迷宮m的a點的序號變?yōu)樽阚E(curstep) ma.xa.y=curstep; postype nextpos(postype c,int di) /* 根據(jù)當(dāng)前位置

26、及移動方向，返回下一位置 */ postype direc4=0,1,1,0,0,-1,-1,0; /* 行增量,列增量 */ /* 移動方向,依次為東南西北 */ c.x+=direcdi.x; c.y+=direcdi.y; return c; void markprint(postype b) /* 使迷宮m的b點的序號變?yōu)?1(不能通過的路徑) */ mb.xb.y=-1; bool initstack(sqstack *s) /* 構(gòu)造一個空棧s */ (*s).base=(selemtype *)malloc(stack_init_size*sizeof(selemtype); i

27、f(!(*s).base) exit(1); /* 存儲分配失敗 */ (*s).top=(*s).base; (*s).stacksize=stack_init_size; return true; bool push(sqstack *s,selemtype e) /* 插入元素e為新的棧頂元素 */ if(*s).top-(*s).base=(*s).stacksize) /* 棧滿，追加存儲空間 */ (*s).base=(selemtype *)realloc(*s).base,(*s).stacksize+stackincrement)*sizeof(selemtype); if(

28、!(*s).base) exit(1); /* 存儲分配失敗 */ (*s).top=(*s).base+(*s).stacksize; (*s).stacksize+=stackincrement; *(*s).top)+=e; return true; bool stackempty(sqstack s) /* 若棧s為空棧，則返回true，否則返回false */ if(s.top=s.base) return true; else return false; bool pop(sqstack *s,selemtype *e) /* 若棧不空，則刪除s的棧頂元素，用e返回其值，并返回ok

29、；否則返回error */ if(*s).top=(*s).base) return false; *e=*-(*s).top; return true; bool mazepath(postype start,postype end) /* 若迷宮maze中存在從入口start到出口end的通道，則求得一條 存放在棧中(從棧底到棧頂)，并返回true；否則返回false */ /int curstep=1;sqstack s; postype curpos; selemtype e; initstack(&s); curpos=start; do if(pass(curpos) /* 當(dāng)前位

30、置可以通過，即是未曾走到過的通道塊 */ footprint(curpos); /* 留下足跡 */ e.ord=curstep; /coutcurstep; acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di=0; /coutacurstep bcurstep ccurstependl; push(&s,e); /* 入棧當(dāng)前位置及狀態(tài) */ curstep+; /* 足跡加1 */ if(curpos.x=end.x&curpos.y=end.y) /* 到達終點(出口) */ return true;

31、 curpos=nextpos(curpos,e.di); else /* 當(dāng)前位置不能通過 */ if(!stackempty(s) pop(&s,&e); /* 退棧到前一位置 */ curpos=e.seat; curstep-; while(e.di=3) & (!stackempty(s) /* 前一位置處于最后一個方向(北) */ markprint(e.seat); /* 留下不能通過的標(biāo)記(-1) */ pop(&s,&e); /* 退回一步 */ curpos=e.seat; curstep-; if(e.di3) /* 沒到最后一個方向(北) */ e.di+; /* 換下一個方向探索 */ push(&s,e); acurstep=e.seat.x=curpos.x; bcurstep=e.seat.y=curpos.y; ccurstep=e.di; curstep+; curpos=nextpos(e.seat,e.di); /* 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 */ while(!stacke