《C++ 數(shù)據(jù)結(jié)構(gòu) 迷宮問題》由會員分享，可在線閱讀，更多相關(guān)《C++ 數(shù)據(jù)結(jié)構(gòu) 迷宮問題（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、課程設(shè)計（論文）任務(wù)書 軟件 學(xué) 院 軟件工程+電子商務(wù)2009 專 業(yè) 2 班 一、課程設(shè)計(論文)題目 迷宮問題 二、課程設(shè)計(論文)工作自 2010 年 12月 27 日起至 2011 年 1月 2 日止 三、課程設(shè)計(論文) 地點: 創(chuàng)新大樓實訓(xùn)中心 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的（1）鞏固和加深對數(shù)據(jù)結(jié)構(gòu)基本知識的理解，提高綜合運用課程知識的能力。（2）使學(xué)生掌握軟件設(shè)計的基本內(nèi)容和設(shè)計方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計的能力。（3）使學(xué)生掌握使用各種計算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計的基本能力。2課程設(shè)計的任務(wù)及要求1）基本要求：（1）對系統(tǒng)進(jìn)行功能模

2、塊分析、控制模塊分析；（2）系統(tǒng)設(shè)計要能完成題目所要求的功能；（3）編程簡練，可用，盡可能的使系統(tǒng)的功能更加完善和全面；（4）說明書、流程圖要清楚；（5）提高學(xué)生的論文寫作能力； （6）特別要求自己獨立完成； 2）創(chuàng)新要求： 在基本要求達(dá)到后，可進(jìn)行創(chuàng)新設(shè)計，如改善算法性能、友好的人機(jī)界面。3）課程設(shè)計論文編寫要求（1）要按照書稿的規(guī)格打印與寫課程設(shè)計論文（2）論文包括目錄、正文、小結(jié)、參考文獻(xiàn)、附錄等（3）課程設(shè)計論文裝訂按學(xué)校的統(tǒng)一要求完成4）課程設(shè)計進(jìn)度安排內(nèi)容 天數(shù) 地點構(gòu)思及收集資料 1 圖書館編碼與調(diào)試 3 實驗室撰寫論文 1 圖書館、實驗室學(xué)生簽名： 20011 年 1 月 3日

3、課程設(shè)計(論文)評審意見（1）基本算法 （20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）設(shè)計分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （3）調(diào)試分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）論文內(nèi)容（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）答辯分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性及考勤是否降等級：是（ ）、否（）評閱人： 職稱： 講師 2011 年 1月4日目錄一、需求分析1二、概要設(shè)計2三、詳細(xì)設(shè)計5四、調(diào)試分析及測試15五、個人工作及創(chuàng)新18六、小結(jié)19參考文獻(xiàn)20數(shù)據(jù)結(jié)構(gòu)課程設(shè)計一、

4、 需求分析1.選題理由本次課設(shè)我選擇了迷宮問題，迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個經(jīng)典問題，迷宮問題要求尋找一條從入口到出口的路徑。通常用的是“窮舉求解”的方法。為了保證在任何位置上都能原路退回，顯然需要用一個后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求解迷宮通路的算法中要應(yīng)用“?！钡乃枷搿τ跅５膬?nèi)容在整個學(xué)期的學(xué)習(xí)中我也有了一定的了解，所以選擇了迷宮這一經(jīng)典問題作為本次課設(shè)的內(nèi)容。 2.基本原理分析 迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探

5、索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。棧是一個后進(jìn)先出的結(jié)構(gòu)，可以用來保存從入口到當(dāng)前位置的路徑。以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何一個位置，均約定東、南、西、北四個方向可通。 3.功能要求 （1）以一個二維數(shù)組Mazem+2n+2表示迷宮，其中：Maze0j和Mazem+1j(0=j=n+1)及Mazei0和Mazein+1 (0=i=m+1)為做外層的一圈障礙。數(shù)組中以0表示通路，1表示障礙，限定迷宮的大小為：m,n=0數(shù)據(jù)關(guān)系：R1=| ai-1, aiD,i=2,n基本操作：In

6、itStack(&S)操作結(jié)果：構(gòu)造一個空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(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é)

7、果：刪除S的棧頂元素，并以e返回其值。StackTraverse（S，visit（）初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit（）。 ADT Stack（2）迷宮的抽象數(shù)據(jù)類型ADT maze數(shù)據(jù)對象：D=ai,j| ai,j ,#,*,0=i=m+1,0=j=n+1,m,n=10數(shù)據(jù)關(guān)系：R=ROW,COL基本操作：InitMaze(&M,a,row,col)初始條件：二維數(shù)組arow+2col+2已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白

8、字符表示通路，以字符#表示障礙，并在迷宮四周加上一圈障礙。MazePath(&M)初始條件：迷宮M已被賦值。操作結(jié)果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài)：以字符*表示路徑上的位置，字符表示“死胡同”，否則迷宮的狀態(tài)不變。PrintMaze（M）初始條件：迷宮M已存在。操作結(jié)果：以字符形式輸出迷宮。 ADT maze2、整體框架 本程序包含三個模塊（1）棧模塊實現(xiàn)棧抽象數(shù)據(jù)類型（2）迷宮模塊實現(xiàn)迷宮抽象數(shù)據(jù)類型（3）主程序模塊：void mian() 初始化； Do接受命令；處理命令；while(命令!=“退出”)；各模塊之間的調(diào)用關(guān)系如圖一： 圖一：調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖

9、反映了程序的層次結(jié)構(gòu)如圖二： 圖二 ：函數(shù)的調(diào)用關(guān)系圖三、 詳細(xì)設(shè)計源程序:#include #include #include #define MAXLEN 10/迷宮包括外墻最大行列數(shù)目#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Status;/ 坐標(biāo)位置類型typedef struct int r,c; PosType;/迷宮中r行c列的位置/迷宮類型typedef struct int r; int c; char arrMAXLENMAXLEN;/可取 ,*,#MazeType; typede

10、f struct/int step; / 當(dāng)前位置在路徑上的“序號” PosType seat; /當(dāng)前的坐標(biāo)位置 int di; /往下一坐標(biāo)位置的方向SElemType;/結(jié)點類型typedef struct NodeType SElemType data; NodeType *next;NodeType,*LinkType;/棧類型typedef struct LinkType top; int stacksize;SqStack; PosType start;PosType end;MazeType maze;bool found;/創(chuàng)建棧Status InitStack(SqStac

11、k &S) S.top=(LinkType)malloc(sizeof(NodeType); S.top-next=NULL; S.stacksize=0; return OK;/進(jìn)棧Status Push(SqStack &S,SElemType &e) LinkType p; p=(NodeType*)malloc(sizeof(NodeType); p-data=e; p-next=S.top; S.top=p; S.stacksize+; return OK;/判斷是否為?？誗tatus StackEmpty(SqStack S) if(S.top-next=NULL) return

12、OK; return ERROR; /出棧Status Pop(SqStack &S,SElemType &e) LinkType p; if(StackEmpty(S) return ERROR; p=S.top; e=p-data; S.top=S.top-next; S.stacksize-; free(p); return OK;/銷毀棧Status DestroyStack(SqStack &S) LinkType p; while(S.top!=NULL) p=S.top; S.top=S.top-next; free(p); /一個一個刪除 if(S.top=NULL) retu

13、rn OK; else return ERROR;/曾走過但不是通路標(biāo)記并返回OKStatus MarkPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rcurpos.c=;/表示曾走過但不通return OK;/曾走過而且是通路標(biāo)記并返回OKStatus FootPrint(MazeType &maze,PosType curpos) maze.arrcurpos.rcurpos.c=*;/*表示可通 return OK;/選擇下一步的方向PosType NextPos(PosType &curpos,int i) PosType cpo

14、s; cpos=curpos; switch(i) /1.2.3.4分別表示東,南,西,北方向 case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break;return cpos;/判斷當(dāng)前位置是否可通 Status Pass(MazeType &maze, PosType curpos) if(maze.arrcurpos.rcurpos.c= ) return TRUE; else return FALSE;/創(chuàng)建迷宮/按照用戶輸入的二維

15、數(shù)組（0或1），設(shè)置迷宮maze的初值，包括加上邊緣一圈的值void InitMaze(MazeType &maze, char aMAXLENMAXLEN, int row, int col) maze.r=row; maze.c=col; for(int i=0;i=col+1;i+) a0i=1; arow+1i=1; for(i=0;i=row+1;i+) ai0=1; aicol+1=1; for(i=0;i=maze.r+2;i+) for(int j=0;jmaze.c+2;j+) if(aij=1) maze.arrij=#; else maze.arrij= ; /求迷宮路徑

16、的偽碼算法：Status MazePath(MazeType &maze,PosType start,PosType end)/求解迷宮maze中，從入口start到出口end的一條路徑，若存在，返回TRUE,否則返回FALSE PosType curpos; SqStack S; SElemType e; InitStack(S); curpos=start;/設(shè)定“當(dāng)前位置”為“入口位置” /curstep=1; /探索第一步 found=false;do if(Pass(maze,curpos) /當(dāng)前位置可以通過，即是未曾走到過的通道塊留下足跡 FootPrint(maze,curpo

17、s);/做可以通過的標(biāo)識/e.step=curstep; e.seat=curpos; e.di=1; /為棧頂元素賦值 Push(S,e); /加入路徑 if(curpos.r=end.r & curpos.c=end.c) found=true;/如果到達(dá)終點返回true else curpos=NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰 else /當(dāng)前位置不能通過 if(!StackEmpty(S) Pop(S,e); while(e.di=4 & !StackEmpty(S) MarkPrint(maze,e.seat); /留下不能通過的標(biāo)記 Pop(S,e);

18、 if(e.di4) e.di+; /換下個方向 Push(S,e); / curpos=NextPos(e.seat,e.di); /進(jìn)行探索 while(!StackEmpty(S)&!found);DestroyStack(S);return found;/將標(biāo)記路徑信息的迷宮（字符型方陣）輸出到終端(包括外墻)void PrintMaze(MazeType &maze) for(int i=0;i=maze.r+2;i+) for(int j=0;j=2) if(ncnum)m+;n=1; a2mn=datai; n+; i+; fclose(fp);InitMaze(maze, a2

19、, rnum, cnum); printf(n迷宮建立完成！n); break; case m: printf(n請輸入迷宮入口的坐標(biāo)，以空格為間隔:-); scanf(%d %d,&start.r,&start.c); printf(n請輸入迷宮出口的坐標(biāo)，以空格為間隔:-); scanf(%d %d,&end.r,&end.c); MazePath(maze, start, end); break; case p: if(found) printf(n求解迷宮的結(jié)果如下-n); PrintMaze(maze); else printf(n找不到路徑！n); void main()char

20、cmd;Initialization();do ReadCommand(cmd); /讀入一個操作符命令 Interpre(cmd); /解釋執(zhí)行命令操作符while(cmd!=q);四、 調(diào)試分析及測試1、調(diào)試分析：（1）本程序有一個核心算法，即求迷宮的路徑，在調(diào)試的時候，出現(xiàn)了兩個問題：沒有想到要用記號，導(dǎo)致迷宮走不出來；沒有設(shè)置found，不知何時跳出。（2）原本棧的元素e中除了di往下一坐標(biāo)位置的方向和seat當(dāng)前的坐標(biāo)位置，還有一個step當(dāng)前位置在路徑上的序號，后來發(fā)現(xiàn)step沒什么用，就刪掉了。（3）函數(shù)ReadCommand中，cmd=getchar();的位置找不準(zhǔn)，最后是試

21、出來的。（4）調(diào)試的時候多次出現(xiàn)，沒有錯誤，但是dos環(huán)境下就是執(zhí)行不起來，所以采用了一些輸出變量，判斷到底是哪里出了問題。 （5）本程序中三個主要的算法：InitMaze，MazePath和MarkPrint的時間復(fù)雜度均為O（m*n）, 本程序的空間復(fù)雜度也為O（m*n）（棧所占最大空間）2、 使用說明和運行結(jié)果：（1）首先以文件形式輸入迷宮數(shù)據(jù)，如圖三： 圖三（2）進(jìn)入演示程序后，會出現(xiàn)以下界面如圖四： 圖四（3） 進(jìn)入“創(chuàng)建迷宮”的命令后，即提示輸入迷宮數(shù)據(jù)的文件名，結(jié)束符為“回車符”，該命令執(zhí)行之后輸出“迷宮建立完成”，且輸出下面可執(zhí)行的操作。如圖五：圖五（4） 進(jìn)入“執(zhí)行迷宮”的命

22、令后，即提示輸入迷宮入口，出口的坐標(biāo)，結(jié)束符為“回車符”，該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路徑。請注意：若迷宮中存在路徑，執(zhí)行此命令后，迷宮狀態(tài)已經(jīng)改變，若要重復(fù)執(zhí)行此命令，需重新輸入迷宮數(shù)據(jù)。如圖六：圖六（5） 進(jìn)入“輸出迷宮”的命令后，即輸出迷宮求出路徑之后的狀態(tài)。#表示障礙， 表示曾走過但不通，*表示路徑。如圖七： 圖七（6） 進(jìn)入“退出”的命令后，按任意鍵結(jié)束。如圖八： 圖八3、 缺點與改進(jìn)：（1） 在定義函數(shù)Mazepath的時候，開始的循環(huán)語句的結(jié)束條件不對，沒有出路時，導(dǎo)致一直出現(xiàn)了不正確的結(jié)果，最后沒有新位置入棧，則返回上一個位置，否則沒有路徑。（2） 只是以文件形

23、式輸入迷宮 ，如果迷宮數(shù)據(jù)量大時，要先建好文件還是很浪費時間，如果以隨機(jī)產(chǎn)生函數(shù)自動產(chǎn)生迷宮會更好 。五、 個人工作及創(chuàng)新為了準(zhǔn)備這次課程設(shè)計我查找了很多的資料，對于迷宮問題的求解中迷宮的產(chǎn)生方式有很多的不同，有的是直接輸入迷宮，有的是用文件輸入，有的是隨機(jī)函數(shù)產(chǎn)生，我的課設(shè)是參考了用文件輸入的方法，這樣做相比直接輸入迷宮操作要更簡單。當(dāng)然用隨機(jī)函數(shù)產(chǎn)生迷宮 比如用： for (i = 0; i MAX_ROW; i+) for(j = 0; j MAX_COL; j+) mazeij = (int) (rand() % 2); maze10 = 1; /* start point */ ma

24、zeMAX_ROW - 1MAX_COL - 2 = 1; /* end point */這樣產(chǎn)生迷宮要更加的方便。結(jié)果也有不確定性，可能可以有通路也可能沒有。對于迷宮的求解都是采用的“窮舉求解”的方法，用到了一些棧的知識。把以前學(xué)過的棧的基本操作實際應(yīng)用了一番也使有了更加清楚的認(rèn)識。 在求解迷宮的算法中，先設(shè)定當(dāng)前位置的初值為入口位置，然后Do若當(dāng)前位置可通，則將當(dāng)前位置插入棧頂； 若該位置是出口位置，則結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則 若棧不為空且棧頂位置尚有其它方向未被探索， 則設(shè)定新的當(dāng)前位置為延順時針方向旋轉(zhuǎn)找到的棧頂位置的下 一相鄰塊； 若棧不空但棧頂位置四

25、周均不通， 則刪去棧頂位置； 若棧不為空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至棧空； 求解迷宮的算法大概就是這么個思路。六、 小結(jié)要能很好的掌握編程，僅僅通過幾個簡單的程序的編寫是無法達(dá)成的，更需要的是大量的積累和深入研究才可能。在程序的編寫中也不能一味的向已有的程序進(jìn)行模仿，而要自己去探索，去尋找最好的解決方法，只有帶著問題去反復(fù)實踐，才能更熟練的掌握和運用，當(dāng)然，對現(xiàn)有的程序也要多去接觸，因為有些程序是我們在短時間內(nèi)無法想出來的，我們也應(yīng)該去參考別人的作品，這樣可以節(jié)約時間獲得更多的知識。最重要的是持之以恒，要經(jīng)常性的復(fù)習(xí)原來接觸到的程序，這樣才能保證我們有足夠的經(jīng)驗去面對程序問題。參考文獻(xiàn)1. 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社.20072. 嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.清華大學(xué)出版社.20073. 譚浩強(qiáng) ，C程序設(shè)計（第四版）.清華大學(xué)出版社.200719