迷宮與棧問題課程設計報告

1、一、課程設計題目迷宮與棧問題二、課程設計內(nèi)容（含技術(shù)指標）【問題描述】以一個mxn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?！救蝿找蟆渴紫葘崿F(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標，d表示走到下一坐標的方向。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。編寫遞歸形式的算法，求得迷宮中所有可能的通路。以方陣形式輸出迷宮及其通

2、路?！緶y試數(shù)據(jù)】迷宮的測試數(shù)據(jù)如下：左上角（0，1）為入口，右下角（8，9）為出口。迷宮與棧問題摘 要數(shù)據(jù)結(jié)構(gòu)是研究與數(shù)據(jù)之間的關(guān)系，是互相之間一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機的表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)。本次課程設計是迷宮求解問題，主要是模擬從入口到出口的通路。程序中的數(shù)據(jù)采取的是“?！弊鳛閿?shù)據(jù)的邏輯結(jié)構(gòu)，并且使用鏈式存儲結(jié)構(gòu)，即是實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型。本課程設計實現(xiàn)了鏈棧的建立，入棧，出棧，判斷棧是否為空的方法，關(guān)鍵的是迷宮通路路徑的“窮舉求解”和遞歸求解的方法。本課程設計重要說明了系統(tǒng)的設計思路、概要設

3、計以及各個功能模塊的詳細設計和實現(xiàn)方法。本次程序的開發(fā)工具是microsoft visual studio 2008，編程語言是c語言。關(guān)鍵詞：迷宮求解 鏈棧 窮舉求解 遞歸求解目 錄摘要31需求分析 11.1基本原理分析11.2功能要求12 概要設計22.1數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義22.1.1棧的抽象數(shù)據(jù)類型22.1.2迷宮的抽象數(shù)據(jù)類型22.1.3功能模塊分解33 詳細設計43.1主函數(shù)與各功能模塊43.2迷宮路徑模塊43.2.1算法分析43.2.2流程圖54軟件測試64.1調(diào)試過程中遇到的問題的解決，以及程序設計思想的實現(xiàn)64.2測試數(shù)據(jù)64.3測試結(jié)果84.4結(jié)果分析10參考文獻

4、11心得體會12教師評語13答辯記錄表14 附錄151 需求分析1.1基本原理分析迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。棧是一個后進先出的結(jié)構(gòu)，可以用來保存從入口到當前位置的路徑。定義迷宮類型來存儲迷宮數(shù)據(jù)，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何一個位置，均約定東、南、西、北四個方向可通。1.2功能要求（1）以一個mxn的長方陣表

5、示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮的四周有一圈障礙。（2）程序輸出的結(jié)果以三元組（i,j,di）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，di表示走到下一坐標的方向，di的取值為1、2、3、4分別表示東、南、西、北（3）程序能夠輸出一個任意的迷宮從指定入口到出口的所有通路，以及以方陣形式輸出迷宮（4）若設定的迷宮存在通路，則以方陣形式將迷宮及其通路輸出到標準輸出文件上，其中字符“1”表示障礙，“2”表示路徑，“3”表示曾途經(jīng)該位置但不能到達出口，其余位置用0表示。若設定迷宮不存在通路則報告相應信息2 概要設計2.1數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義2.1.1棧的抽象數(shù)據(jù)類型ad

6、t linkstack數(shù)據(jù)對象：d=ai| aicharset,i=1,2n,n=0數(shù)據(jù)關(guān)系：r1=| ai-1, aid,i=2,n基本操作：initlinkstack(&s)操作結(jié)果：構(gòu)造一個空棧s。linkstackempty(&s)初始條件：棧s已存在。操作結(jié)果：若s為空棧，則返回true，否則返回false。pushlinkstack (&s，e)初始條件：棧s已存在。操作結(jié)果：在棧s的棧頂插入新的棧頂元素e。poplinkstack (&s，&e)初始條件：棧s已存在。操作結(jié)果：刪除s的棧頂元素，并以e返回其值。 adt linkstack2.1.2迷宮的抽象數(shù)據(jù)類型adt maz

7、e數(shù)據(jù)對象：d=ai,j| ai,j0,1,2,3,0=i=m-1,0=j=n-1,m,n迷宮模塊-棧模塊3 詳細設計3.1主函數(shù)與各功能模塊主函數(shù)的各函數(shù)調(diào)用關(guān)系如圖3-1所示，主函數(shù)調(diào)用創(chuàng)建迷宮函數(shù)和求解所有路徑的函數(shù)，其中創(chuàng)建迷宮信息的函數(shù)調(diào)用初始化迷宮和輸出迷宮。主函數(shù)求解所有路徑mazepath初始化迷宮initmaze初始化棧initlinkstackack輸出迷宮printmaze入棧pushlinkstack出棧poplinkstack判斷棧是否為空linkstackempty留下標記markprint判斷方向nextpos留下足跡footprint判斷能否通過pass圖3-1

8、3.2 迷宮路徑模塊3.2.1算法分析 解決迷宮問題最重要的程序段是找到通路，并存儲在棧里，現(xiàn)只分析實現(xiàn)這一過程的函數(shù)do 若當前位置可通， 則 將當前位置插入棧頂； 若該位置是出口位置，則結(jié)束； 否則切換當前位置的東鄰方塊為新的當前位置； 否則， 若棧不空且棧頂位置尚有其他方向未經(jīng)探索， 則設定的新的當前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置； 若棧不空，則重新測試新的棧頂位置， 直到找到一個可通的相鄰塊或出棧至?？?； while（棧不空）；3.2.2 流程圖將入口、出口位置傳入方法里判斷當前位置是否可通將元素入棧是否到達迷宮

9、出口右邊是否存在通路上邊是否存在通路左邊是否存在通路下邊是否存在通路存儲結(jié)點入棧循環(huán)結(jié)束，無解迷宮有解迷宮圖3-24軟件測試4.1調(diào)試過程中遇到的問題的解決，以及程序設計思想的實現(xiàn)（1）調(diào)試過程中出現(xiàn)的錯誤有編譯連接時的一些語法錯誤，也有由于算法存在問題而導致程序運行沒有結(jié)果或者不是預期的結(jié)果。這里主要說一下自己由于算法而導致的錯誤：因為沒有注意結(jié)點不能重復走，所以造成了死循環(huán)，程序沒有結(jié)果。通過分析后把走過的結(jié)點變?yōu)椴豢勺叩慕Y(jié)點，這樣就避免了重復走到該結(jié)點。還有就是判斷迷宮是否有通路的這個結(jié)果不能如預期的結(jié)果那樣：有通路就輸出所有的通路，沒有就輸出“沒有路徑可走!”。因為沒有通路可走的時候棧

10、是空的，但是輸出所有的路徑以后棧也是空的。當迷宮有通路的時候，在輸出所有路徑以后還是會輸出“沒有路徑可走!”這句話。當迷宮沒有通路的時候，輸出“沒有路徑可走!”這句話。因為算法的思想是這樣的，所以達不到預期的結(jié)果。解決的方法是如果迷宮有通路則輸出所有的通路，如果迷宮沒有通路，則沒有結(jié)果輸出。（2）迷宮的求解一般采用的是“窮舉求解”，利用棧的思想，先將入口位置進棧，判斷方向，若其方向可通，則進棧，若不通，則出棧，如此循環(huán)下去。4.2測試數(shù)據(jù)迷宮輸入遞歸求路 非遞歸求路徑：以方陣形式輸出迷宮及其通路： 測試無通路的迷宮： 4.3測試結(jié)果迷宮輸入： 求通路:以方陣形式輸出迷宮及其通路：4.4結(jié)果分析

11、本題中三個主要算法：initmaze,mazepath和printmaze時間復雜度均為o（row*line），空間復雜度也為o（row*line）參考文獻1 嚴蔚敏、吳偉民：數(shù)據(jù)結(jié)構(gòu)（c語言版）m，清華大學出版社 2007年版2 譚浩強：c語言設計（第三版）m，清華大學出版社 2005年版3 曹衍龍、林瑞仲、徐慧：c語言實例解析精粹（第二版）m，人民郵電出版社心得 體會通過這段時間的課程設計，本人對計算機的應用，數(shù)據(jù)結(jié)構(gòu)的作用以及c語言的使用都有了更深的了解。尤其是c語言的進步讓我深刻的感受到任何所學的知識都需要實踐，沒有實踐就無法真正理解這些知識以及掌握它們，使其成為自己的財富。在設計此程

12、序時，剛開始感到比較迷茫，然后一步步分析，試著寫出基本的算法，思路漸漸清晰，最后完成程序。當然也遇到不少的問題，也正是因為這些問題引發(fā)的思考給我?guī)Я耸斋@。在遇到描寫迷宮路徑的算法時，我感到有些困難，后來經(jīng)過一步步分析和借鑒書本上的窮舉求解的算法，最后把算法寫出來。但其要求是要輸出迷宮路徑的一步步位置，我通過利用兩個棧的互相出入棧，達到棧的逆序輸出。在利用遞歸方法求路徑時花費了我很長時間，由于本人對遞歸方面的知識運用較少，導致我不熟悉它的用法，但最終還是通過詢問同學、查找書本和上網(wǎng)了解關(guān)于遞歸方面的知識寫出來了。這次課程設計讓我更加深入了解很多方面的知識，如鏈結(jié)構(gòu)的棧類型及其基本操作，數(shù)組的運用

13、等等。在程序的編寫中不要一味的模仿，要自己去摸索，只有帶著問題反復實踐，才能熟練地掌握和運用。在實際的上機操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識，更重要的是培養(yǎng)解決實際問題的能力，所以相信通過此次實習可以提高我們分析設計能力和編程能力，為后續(xù)課程的學習及實踐打下良好的基礎。附 錄程序源代碼：#include #include #include #define maxlen 10/迷宮包括外墻最大行列數(shù)目#define true 1#define false 0#define ok 1#define error 0#define overflow -2#define stack_init

14、_size 100 /存儲空間初始分配量typedef int status;typedef struct int row;intline;postype;/迷宮中row行l(wèi)ine列的位置typedef struct mazetypeint row; int line; int arrmaxlenmaxlen;mazetype; /迷宮類型typedef struct int ord; / 當前位置在路徑上的“序號” postype seat; /當前的坐標位置 int di; /往下一坐標位置的方向selemtype;typedef struct stacknodeselemtype dat

15、a;struct stacknode *next;*linkstack;/構(gòu)建一個空棧sint initlinkstack(linkstack &s)s=(linkstack)malloc(sizeof(linkstack); /通過malloc函數(shù)分配空間if (!s)return error; /如果分配失敗，則返回s-next=null;return ok;/判斷棧是否為空status linkstackempty(linkstack &s)if (s!=null) if (s-next=null)return ok;return error;/插入元素e為新的棧頂元素status pu

16、shlinkstack(linkstack &s,selemtype e)linkstack q=s;linkstack m=(linkstack)malloc(sizeof(linkstack); /通過malloc函數(shù)分配空間if (s!=null)while (q-next!=null)q=q-next;m-data=e;m-next=null;q-next=m;return error;/若棧不空，則刪除s的棧頂元素，用e返回其值，并返回ok；否則返回errorstatus poplinkstack(linkstack &s,selemtype &e)linkstack q=s;if

17、(s!=null)if (q-next!=null) /若棧不是空的while (q-next-next!=null)q=q-next;e=q-next-data;q-next=null;return ok;return error;status pass(mazetype mymaze,postype curpos) if(mymaze.arrcurpos.rowcurpos.line=0)return true; / 如果當前位置是可以通過，返回else return false; / 其它情況返回void footprint(mazetype &mymaze,postype curpos

18、) mymaze.arrcurpos.rowcurpos.line=2;void markprint(mazetype &mymaze,postype curpos) mymaze.arrcurpos.rowcurpos.line=3;postype nextpos(postype curpos, int dir) postype returnpos; switch (dir) case 1:returnpos.row=curpos.row;returnpos.line=curpos.line+1;break;case 2:returnpos.row=curpos.row+1;returnpo

19、s.line=curpos.line;break;case 3:returnpos.row=curpos.row;returnpos.line=curpos.line-1;break;case 4:returnpos.row=curpos.row-1;returnpos.line=curpos.line;break;return returnpos;status mazepath(mazetype &maze, postype start, postype end) / 若迷宮maze中從入口start到出口end的通道，則求得一條存放在棧中/ （從棧底到棧頂），并返回true；否則返回fal

20、selinkstack s,s1;postype curpos;int curstep;selemtype e;initlinkstack(s);initlinkstack(s1);curpos = start; / 設定當前位置為入口位置curstep = 1; / 探索第一步doif(pass(maze,curpos) / 當前位置可通過，即是未曾走到過的通道塊footprint(maze,curpos); / 留下足跡e.di =1;e.ord = curstep;e.seat= curpos;pushlinkstack(s,e); / 加入路徑if(curpos.row = end.r

21、ow & curpos.line=end.line)while(!linkstackempty(s)poplinkstack(s,e);pushlinkstack(s1,e);printf(迷宮的路徑：);while(!linkstackempty(s1)poplinkstack(s1,e);printf(第%d步：(%d,%d,%d) ,e.ord,e.seat,e.di);return (true); / 到達終點（出口）curpos = nextpos(curpos, 1); / 下一位置是當前位置的東鄰curstep+; / 探索下一步else / 當前位置不能通過if (!links

22、tackempty(s) poplinkstack(s,e);while (e.di=4 & !linkstackempty(s) markprint(maze,e.seat); poplinkstack(s,e); / 留下不能通過的標記，并退回一步curstep-; / whileif (e.di4) e.di+;pushlinkstack(s,e); / 換下一個方向探索curpos = nextpos(e.seat,e.di); / 當前位置設為新方向的相鄰塊 / if / if / else while (!linkstackempty(s) );printf(此迷宮無通路！n);r

23、eturn false; / mazepath/初始化迷宮status initmaze(mazetype &maze)int i,j;printf(請輸入迷宮的行和列數(shù): ); scanf(%d,%d,&maze.row,&maze.line);printf(請輸入迷宮(以表示可走,1表示有障礙)：n);for(i=1;i=maze.row;i+)for(j=1;j=maze.line;j+)scanf(%d,&maze.arrij);for(i=0;i=maze.line+1;i+)/迷宮行外墻maze.arr0i=1; maze.arrmaze.row+1i=1;/for for(i=1

24、;i=maze.row;i+)/迷宮列外墻maze.arri0=1;maze.arrimaze.line+1=1;return ok;/以方陣形式輸出迷宮及其通路void printmaze(mazetype &maze)/將標記路徑信息的迷宮輸出到終端(包括外墻)int i,j;for(i=0;i=maze.row+1;i+) for(j=0;j=maze.line+1;j+)printf(%2d,maze.arrij);/輸出迷宮/當前位置的標記 printf(nn); /printmaze/遞歸算法linkstack l,l1;void mazepath_recursion(mazety

25、pe &maze,postype cur,postype end,int curstep)int i;selemtype e;postype next; / 下一個位置/ 行增量,列增量postype direc4=0,1,1,0,0,-1,-1,0;/ 移動方向,依次為東南西北for(i=0;i=3;i+) / 依次試探東南西北四個方向next.row=cur.row+direci.row;next.line=cur.line+direci.line;if(maze.arrnext.rownext.line=0) / 是通路e.seat=next;pushlinkstack(l,e);maz

26、e.arrnext.rownext.line=+curstep;if(next.row != end.row | next.line != end.line) / 沒到終點mazepath_recursion(maze,next,end,1); / 試探下一點(遞歸調(diào)用) elseprintf(n); printf(迷宮的路徑：);while(!linkstackempty(l)poplinkstack(l,e);pushlinkstack(l1,e);while(!linkstackempty(l1)poplinkstack(l1,e);printf(%d,%d ) ,e.seat);maze.arrnext.rownext.line=0; / 恢復為通路，試探下一條路curstep-;void main()mazety