迷宮與棧問題課程設(shè)計(jì)報(bào)告.doc

二、課程設(shè)計(jì)內(nèi)容（含技術(shù)指標(biāo)）【問題描述】以一個(gè)mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?！救蝿?wù)要求】首先實(shí)現(xiàn)一個(gè)以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。編寫遞歸形式的算法，求得迷宮中所有可能的通路。以方陣形式輸出迷宮及其通路?！緶y試數(shù)據(jù)】迷宮的測試數(shù)據(jù)如下：左上角（0，1）為入口，右下角（8，9）為出口。四、基本要求1在設(shè)計(jì)時(shí)，要嚴(yán)格按照題意要求獨(dú)立進(jìn)行設(shè)計(jì)，不能隨意更改。若確因條件所限，必須要改變課題要求時(shí)，應(yīng)在征得指導(dǎo)教師同意的前提下進(jìn)行。 2在設(shè)計(jì)完成后，應(yīng)當(dāng)場運(yùn)行和答辯，由指導(dǎo)教師驗(yàn)收，只有在驗(yàn)收合格后才能算設(shè)計(jì)部分的結(jié)束。 3設(shè)計(jì)結(jié)束后要寫出課程設(shè)計(jì)報(bào)告，以作為整個(gè)課程設(shè)計(jì)評分的書面依據(jù)和存檔材料。設(shè)計(jì)報(bào)告以規(guī)定格式的電子文檔書寫、打印并裝訂，報(bào)告格式嚴(yán)格按照模板要求撰寫，排版及圖、表要清楚、工整。從總體來說，所設(shè)計(jì)的程序應(yīng)該全部符合要求，問題模型、求解算法以及存儲結(jié)構(gòu)清晰；具有友好、清晰的界面；設(shè)計(jì)要包括所需要的輔助程序，如必要的數(shù)據(jù)輸入、輸出、顯示和錯(cuò)誤檢測功能；操作使用要簡便；程序的整體結(jié)構(gòu)及局部結(jié)構(gòu)要合理；設(shè)計(jì)報(bào)告要符合規(guī)范。 課程負(fù)責(zé)人簽名： 2011年7月1日迷宮與棧問題摘 要數(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)在計(jì)算機(jī)的表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)。本次課程設(shè)計(jì)是迷宮求解問題，主要是模擬從入口到出口的通路。程序中的數(shù)據(jù)采取的是“?！弊鳛閿?shù)據(jù)的邏輯結(jié)構(gòu)，并且使用鏈?zhǔn)酱鎯Y(jié)構(gòu)，即是實(shí)現(xiàn)一個(gè)以鏈表作存儲結(jié)構(gòu)的棧類型。本課程設(shè)計(jì)實(shí)現(xiàn)了鏈棧的建立，入棧，出棧，判斷棧是否為空的方法，關(guān)鍵的是迷宮通路路徑的“窮舉求解”和遞歸求解的方法。本課程設(shè)計(jì)重要說明了系統(tǒng)的設(shè)計(jì)思路、概要設(shè)計(jì)以及各個(gè)功能模塊的詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)方法。本次程序的開發(fā)工具是microsoft visual studio 2008，編程語言是C語言。關(guān)鍵詞：迷宮求解 鏈棧 窮舉求解 遞歸求解目 錄摘要IIII1需求分析 11.1基本原理分析11.2功能要求12 概要設(shè)計(jì)22.1數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義22.1.1棧的抽象數(shù)據(jù)類型22.1.2迷宮的抽象數(shù)據(jù)類型22.1.3功能模塊分解33 詳細(xì)設(shè)計(jì)43.1主函數(shù)與各功能模塊43.2迷宮路徑模塊43.2.1算法分析43.2.2流程圖54軟件測試64.1調(diào)試過程中遇到的問題的解決，以及程序設(shè)計(jì)思想的實(shí)現(xiàn)64.2測試數(shù)據(jù)64.3測試結(jié)果84.4結(jié)果分析10參考文獻(xiàn)11心得體會12教師評語13答辯記錄表14 附錄15211 需求分析1.1基本原理分析迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。棧是一個(gè)后進(jìn)先出的結(jié)構(gòu)，可以用來保存從入口到當(dāng)前位置的路徑。定義迷宮類型來存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何一個(gè)位置，均約定東、南、西、北四個(gè)方向可通。1.2功能要求（1）以一個(gè)mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮的四周有一圈障礙。（2）程序輸出的結(jié)果以三元組（i,j,di）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，di表示走到下一坐標(biāo)的方向，di的取值為1、2、3、4分別表示東、南、西、北（3）程序能夠輸出一個(gè)任意的迷宮從指定入口到出口的所有通路，以及以方陣形式輸出迷宮（4）若設(shè)定的迷宮存在通路，則以方陣形式將迷宮及其通路輸出到標(biāo)準(zhǔn)輸出文件上，其中字符“1”表示障礙，“2”表示路徑，“3”表示曾途經(jīng)該位置但不能到達(dá)出口，其余位置用0表示。若設(shè)定迷宮不存在通路則報(bào)告相應(yīng)信息2 概要設(shè)計(jì)2.1數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義2.1.1棧的抽象數(shù)據(jù)類型ADT 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)造一個(gè)空棧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 Maze數(shù)據(jù)對象：D=ai,j| ai,j0,1,2,3,0=i=m-1,0=j=n-1,m,n迷宮模塊-棧模塊3 詳細(xì)設(shè)計(jì)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留下標(biāo)記MarkPrint判斷方向NextPos留下足跡FootPrint判斷能否通過Pass圖3-13.2 迷宮路徑模塊3.2.1算法分析 解決迷宮問題最重要的程序段是找到通路，并存儲在棧里，現(xiàn)只分析實(shí)現(xiàn)這一過程的函數(shù)do 若當(dāng)前位置可通， 則 將當(dāng)前位置插入棧頂； 若該位置是出口位置，則結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則， 若棧不空且棧頂位置尚有其他方向未經(jīng)探索， 則設(shè)定的新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置； 若棧不空，則重新測試新的棧頂位置， 直到找到一個(gè)可通的相鄰塊或出棧至棧空； while（棧不空）；3.2.2 流程圖將入口、出口位置傳入方法里判斷當(dāng)前位置是否可通將元素入棧是否到達(dá)迷宮出口右邊是否存在通路上邊是否存在通路左邊是否存在通路下邊是否存在通路存儲結(jié)點(diǎn)入棧循環(huán)結(jié)束，無解迷宮有解迷宮圖3-24軟件測試4.1調(diào)試過程中遇到的問題的解決，以及程序設(shè)計(jì)思想的實(shí)現(xiàn)（1）調(diào)試過程中出現(xiàn)的錯(cuò)誤有編譯連接時(shí)的一些語法錯(cuò)誤，也有由于算法存在問題而導(dǎo)致程序運(yùn)行沒有結(jié)果或者不是預(yù)期的結(jié)果。這里主要說一下自己由于算法而導(dǎo)致的錯(cuò)誤：因?yàn)闆]有注意結(jié)點(diǎn)不能重復(fù)走，所以造成了死循環(huán)，程序沒有結(jié)果。通過分析后把走過的結(jié)點(diǎn)變?yōu)椴豢勺叩慕Y(jié)點(diǎn)，這樣就避免了重復(fù)走到該結(jié)點(diǎn)。還有就是判斷迷宮是否有通路的這個(gè)結(jié)果不能如預(yù)期的結(jié)果那樣：有通路就輸出所有的通路，沒有就輸出“沒有路徑可走!”。因?yàn)闆]有通路可走的時(shí)候棧是空的，但是輸出所有的路徑以后棧也是空的。當(dāng)迷宮有通路的時(shí)候，在輸出所有路徑以后還是會輸出“沒有路徑可走!”這句話。當(dāng)迷宮沒有通路的時(shí)候，輸出“沒有路徑可走!”這句話。因?yàn)樗惴ǖ乃枷胧沁@樣的，所以達(dá)不到預(yù)期的結(jié)果。解決的方法是如果迷宮有通路則輸出所有的通路，如果迷宮沒有通路，則沒有結(jié)果輸出。（2）迷宮的求解一般采用的是“窮舉求解”，利用棧的思想，先將入口位置進(jìn)棧，判斷方向，若其方向可通，則進(jìn)棧，若不通，則出棧，如此循環(huán)下去。4.2測試數(shù)據(jù)迷宮輸入遞歸求路 非遞歸求路徑：以方陣形式輸出迷宮及其通路： 測試無通路的迷宮： 4.3測試結(jié)果迷宮輸入： 求通路:以方陣形式輸出迷宮及其通路：4.4結(jié)果分析本題中三個(gè)主要算法：InitMaze,MazePath和PrintMaze時(shí)間復(fù)雜度均為O（row*line），空間復(fù)雜度也為O（row*line）參考文獻(xiàn)1 嚴(yán)蔚敏、吳偉民：數(shù)據(jù)結(jié)構(gòu)（C語言版）M，清華大學(xué)出版社 2007年版2 譚浩強(qiáng)：C語言設(shè)計(jì)（第三版）M，清華大學(xué)出版社 2005年版3 曹衍龍、林瑞仲、徐慧：C語言實(shí)例解析精粹（第二版）M，人民郵電出版社心得 體會通過這段時(shí)間的課程設(shè)計(jì)，本人對計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。尤其是C語言的進(jìn)步讓我深刻的感受到任何所學(xué)的知識都需要實(shí)踐，沒有實(shí)踐就無法真正理解這些知識以及掌握它們，使其成為自己的財(cái)富。在設(shè)計(jì)此程序時(shí)，剛開始感到比較迷茫，然后一步步分析，試著寫出基本的算法，思路漸漸清晰，最后完成程序。當(dāng)然也遇到不少的問題，也正是因?yàn)檫@些問題引發(fā)的思考給我?guī)Я耸斋@。在遇到描寫迷宮路徑的算法時(shí)，我感到有些困難，后來經(jīng)過一步步分析和借鑒書本上的窮舉求解的算法，最后把算法寫出來。但其要求是要輸出迷宮路徑的一步步位置，我通過利用兩個(gè)棧的互相出入棧，達(dá)到棧的逆序輸出。在利用遞歸方法求路徑時(shí)花費(fèi)了我很長時(shí)間，由于本人對遞歸方面的知識運(yùn)用較少，導(dǎo)致我不熟悉它的用法，但最終還是通過詢問同學(xué)、查找書本和上網(wǎng)了解關(guān)于遞歸方面的知識寫出來了。這次課程設(shè)計(jì)讓我更加深入了解很多方面的知識，如鏈結(jié)構(gòu)的棧類型及其基本操作，數(shù)組的運(yùn)用等等。在程序的編寫中不要一味的模仿，要自己去摸索，只有帶著問題反復(fù)實(shí)踐，才能熟練地掌握和運(yùn)用。在實(shí)際的上機(jī)操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識，更重要的是培養(yǎng)解決實(shí)際問題的能力，所以相信通過此次實(shí)習(xí)可以提高我們分析設(shè)計(jì)能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。附 錄程序源代碼：#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_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; / 當(dāng)前位置在路徑上的“序號” PosType seat; /當(dāng)前的坐標(biāo)位置 int di; /往下一坐標(biāo)位置的方向SElemType;typedef struct StacknodeSElemType data;struct Stacknode *next;*LinkStack;/構(gòu)建一個(gè)空棧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 PushLinkStack(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 (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; / 如果當(dāng)前位置是可以通過，返回else return FALSE; / 其它情況返回void FootPrint(MazeType &MyMaze,PosType CurPos) 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;ReturnPos.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；否則返回FALSELinkStack S,S1;PosType curpos;int curstep;SElemType e;InitLinkStack(S);InitLinkStack(S1);curpos = start; / 設(shè)定當(dāng)前位置為入口位置curstep = 1; / 探索第一步doif(Pass(maze,curpos) / 當(dāng)前位置可通過，即是未曾走到過的通道塊FootPrint(maze,curpos); / 留下足跡e.di =1;e.ord = curstep;e.seat= curpos;PushLinkStack(S,e); / 加入路徑if(curpos.row = end.row & 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); / 到達(dá)終點(diǎn)（出口）curpos = NextPos(curpos, 1); / 下一位置是當(dāng)前位置的東鄰curstep+; / 探索下一步else / 當(dāng)前位置不能通過if (!LinkStackEmpty(S) PopLinkStack(S,e);while (e.di=4 & !LinkStackEmpty(S) MarkPrint(maze,e.seat); PopLinkStack(S,e); / 留下不能通過的標(biāo)記，并退回一步curstep-; / whileif (e.di4) e.di+;PushLinkStack(S,e); / 換下一個(gè)方向探索curpos = NextPos(e.seat,e.di); / 當(dāng)前位置設(shè)為新方向的相鄰塊 / if / if / else while (!LinkStackEmpty(S) );printf(此迷宮無通路！n);return 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;i=maze.row;i+)/迷宮列外墻maze.arri0=1;maze.arrimaze.line+1=1;return OK;/以方陣形式輸出迷宮及其通路void PrintMaze(MazeType &maze)/將標(biāo)記路徑信息的迷宮輸出到終端(包括外墻)int i,j;for(i=0;i=maze.row+1;i+) for(j=0;j=maze.line+1;j+)printf(%2d,maze.arrij);/輸出迷宮/當(dāng)前位置的標(biāo)記 printf(nn); /PrintMaze/遞歸算法LinkStack L,L1;void MazePath_Recursion(MazeType &maze,PosType cur,PosType end,int curstep)int i;SElemType e;PosType next; / 下一個(gè)位置/ 行增量,列增量PosType direc4=0,1,1,0,0,-1,-1,0;/ 移動(dòng)方向,依次為東南西北for(i=0;i=3;i+) / 依次試探東南西北四個(gè)方向next.row=cur.row+direci.row;next.line=cur.line+direci.line;if(maze.arrnext.rownext.line=0) / 是通路e.seat=next;PushLinkStack(L,e);maze.arrnext.rownext.line=+curstep;if(next.row != end.row | next.line != end.line) / 沒到終點(diǎn)MazePath_Recursion(maze,next,end,1); / 試探下一點(diǎn)(遞歸調(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; / 恢復(fù)為通路