C++數(shù)據(jù)結(jié)構(gòu) 迷宮問題

上傳人:wan****g1 文檔編號(hào):139087021 上傳時(shí)間:2022-08-22 格式:DOCX 頁數(shù):23 大?。?83.27KB
收藏 版權(quán)申訴 舉報(bào) 下載
C++數(shù)據(jù)結(jié)構(gòu) 迷宮問題_第1頁
第1頁 / 共23頁
C++數(shù)據(jù)結(jié)構(gòu) 迷宮問題_第2頁
第2頁 / 共23頁
C++數(shù)據(jù)結(jié)構(gòu) 迷宮問題_第3頁
第3頁 / 共23頁

本資源只提供3頁預(yù)覽,全部文檔請(qǐng)下載后查看!喜歡就下載吧,查找使用更方便

15 積分

下載資源

資源描述:

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

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

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

3、一般(、差();(2)設(shè)計(jì)分析(20分):優(yōu)()、良()、中()、一般(、差();(3)調(diào)試分析(20分):優(yōu)()、良()、中()、一般(、差();(4)論文內(nèi)容(20分):優(yōu)()、良()、中()、一般(、差();(5)答辯分析(20分):優(yōu)()、良()、中()、一般(、差();(6)格式規(guī)范性及考勤是否降等級(jí):是()、否()目錄一、需求分析1二、概要設(shè)計(jì)2三、詳細(xì)設(shè)計(jì)5四、調(diào)試分析及測試15五、個(gè)人工作及創(chuàng)新18六、小結(jié)19參考文獻(xiàn)20數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、需求分析1. 選題理由本次課設(shè)我選擇了迷宮問題,迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個(gè)經(jīng)典問題,迷宮問題要求尋找一條從入口到出口的路徑。通常用的是“

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

5、點(diǎn)的下標(biāo)為(1,1),出口點(diǎn)的下標(biāo)為(n,n)。為處理方便起見,在迷宮的四周加一圈障礙。對(duì)于迷宮任何一個(gè)位置,均約定東、南、西、北四個(gè)方向可通。3. 功能要求(1)以一個(gè)二維數(shù)組Mazem+2n+2表示迷宮,其中:MazeOj和Mazem+1j(0=j=n+1)及MazeiO和Mazein+1(0=i=m+1)為做外層的一圈障礙。數(shù)組中以0表示通路,1表示障礙,限定迷宮的大小為:m,n=0數(shù)據(jù)關(guān)系:R1=|ai-1,ai$D,i=2,口基本操作:InitStack(&S)操作結(jié)果:構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件:棧S已存在。操作結(jié)果:銷毀棧S。ClearStack(&

6、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(S,visit()初始條件:棧S已存在。操作結(jié)果:從棧底到棧頂依次對(duì)S中的每個(gè)元素

7、調(diào)用函數(shù)visit()。ADTStack2)迷宮的抽象數(shù)據(jù)類型ADTmaze數(shù)據(jù)對(duì)象:D=ai,j|ai,je,#,*,0=i=m+1,0=j=n+1,m,n;Same圖二:函數(shù)的調(diào)用關(guān)系圖三、詳細(xì)設(shè)計(jì)源程序:#include#include#include#defineMAXLEN10/迷宮包括外墻最大行列數(shù)目#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;/坐標(biāo)位置類型typedefstructintr,c;PosType;/迷宮中r行c列的位置/迷宮類型typedefstructintr;intc;char

8、arrMAXLENMAXLEN;/可取,MazeType;typedefstruct/intstep;/當(dāng)前位置在路徑上的“序號(hào)”PosTypeseat;/當(dāng)前的坐標(biāo)位置intdi;/往下一坐標(biāo)位置的方向SElemType;/結(jié)點(diǎn)類型typedefstructNodeTypeSElemTypedata;NodeType*next;NodeType,*LinkType;/棧類型typedefstructLinkTypetop;intstacksize;SqStack;PosTypestart;PosTypeend;MazeTypemaze;boolfound;/創(chuàng)建棧StatusInitStac

9、k(SqStack&S)S.top=(LinkType)malloc(sizeof(NodeType);S.top-next=NULL;S.stacksize=0;returnOK;/進(jìn)棧StatusPush(SqStack&S,SElemType&e)LinkTypep;p=(NodeType*)malloc(sizeof(NodeType);p-data=e;p-next=S.top;S.top=p;S.stacksize+;returnOK;/判斷是否為??誗tatusStackEmpty(SqStackS)if(S.top-next=NULL)returnOK;returnERROR;

10、/出棧StatusPop(SqStack&S,SElemType&e)LinkTypep;if(StackEmpty(S)returnERROR;p=S.top;e=p-data;S.top=S.top-next;S.stacksize-;free(p);returnOK;/銷毀棧StatusDestroyStack(SqStack&S)LinkTypep;while(S.top!=NULL)p=S.top;S.top=S.top-next;free(p);/一個(gè)一個(gè)刪除if(S.top=NULL)returnOK;elsereturnERROR;/曾走過但不是通路標(biāo)記并返回OKStatusM

11、arkPrint(MazeType&maze,PosTypecurpos)maze.arrcurpos.rcurpos.c=;/表示曾走過但不通returnOK;/曾走過而且是通路標(biāo)記并返回OKStatusFootPrint(MazeType&maze,PosTypecurpos)maze.arrcurpos.rcurpos.c二*;/*表示可通returnOK;/選擇下一步的方向PosTypeNextPos(PosType&curpos,inti)PosTypecpos;cpos=curpos;switch(i)/1.2.3.4分別表示東,南,西,北方向case1:cpos.c+=1;bre

12、ak;case2:cpos.r+=1;break;case3:cpos.c-=1;break;case4:cpos.r-=1;break;returncpos;/判斷當(dāng)前位置是否可通StatusPass(MazeType&maze,PosTypecurpos)if(maze.arrcurpos.rcurpos.c=)returnTRUE;elsereturnFALSE;/創(chuàng)建迷宮/按照用戶輸入的二維數(shù)組(0或1),設(shè)置迷宮maze的初值,包括加上邊緣一圈的值voidInitMaze(MazeType&maze,charaMAXLENMAXLEN,introw,intcol)maze.r=row

13、;maze.c=col;for(inti=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(intj=0;jmaze.c+2;j+)if(aij=1)maze.arrij=#;elsemaze.arrij=;/求迷宮路徑的偽碼算法:StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)/求解迷宮maze中,從入口start到出口end的一條路徑,若存在,返回TRUE,否則返回FALSEPosTypecurpos;S

14、qStackS;SElemTypee;InitStack(S);curpos二start;/設(shè)定“當(dāng)前位置為“入口位置/curstep=1;/探索第一步found=false;doif(Pass(maze,curpos)/當(dāng)前位置可以通過,即是未曾走到過的通道塊留下足跡FootPrint(maze,curpos);/做可以通過的標(biāo)識(shí)/e.step=curstep;e.seat=curpos;e.di=1;/為棧頂元素賦值Push(S,e);/加入路徑if(curpos.r二二end.r&curpos.c二二end.c)found二true;/如口果到達(dá)終點(diǎn)返回trueelsecurpos二Ne

15、xtPos(curpos,l);/下一位置是當(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);if(e.di4)e.di+;/換下個(gè)方向Push(S,e);/curpos=NextPos(e.seat,e.di);/進(jìn)行探索while(!StackEmpty(S)&!found);DestroyStack(S);returnfound;/將標(biāo)記路徑信息的迷宮(字符型方陣)輸出到終端(包括外墻)voidPrintMaz

16、e(MazeType&maze)for(inti=0;i=maze.r+2;i+)for(intj=0;j=2)if(ncnum)m+;n=1;a2mn=datai;n+;i+;fclose(fp);InitMaze(maze,a2,rnum,cnum);printf(n迷宮建立完成!n);break;,fcasem:printf(n請(qǐng)輸入迷宮入口的坐標(biāo),以空格為間隔:-);scanf(%d%d,&start.r,&start.c);printf(n請(qǐng)輸入迷宮出口的坐標(biāo),以空格為間隔:-);scanf(%d%d,&end.r,&end.c);MazePath(maze,start,end);b

17、reak;,fcasep:if(found)printf(n求解迷宮的結(jié)果如下-n);PrintMaze(maze);elseprintf(n找不到路徑!n);voidmain()charcmd;Initialization();do/讀入一個(gè)操作符命令/解釋執(zhí)行命令操作符ReadCommand(cmd);Interpre(cmd);while(cmd!=q);調(diào)試分析及測試1、調(diào)試分析:(1) 本程序有一個(gè)核心算法,即求迷宮的路徑,在調(diào)試的時(shí)候,出現(xiàn)了兩個(gè)問題:沒有想到要用記號(hào),導(dǎo)致迷宮走不出來;沒有設(shè)置found,不知何時(shí)跳出。(2) 原本棧的元素e中除了di往下一坐標(biāo)位置的方向和seat

18、當(dāng)前的坐標(biāo)位置,還有一個(gè)step當(dāng)前位置在路徑上的序號(hào),后來發(fā)現(xiàn)step沒什么用,就刪掉了。(3) 函數(shù)ReadCommand中,cmd=getchar();的位置找不準(zhǔn),最后是試出來的。(4) 調(diào)試的時(shí)候多次出現(xiàn),沒有錯(cuò)誤,但是dos環(huán)境下就是執(zhí)行不起來,所以采用了一些輸出變量,判斷到底是哪里出了問題。(5) 本程序中三個(gè)主要的算法:InitMaze,MazePath和MarkPrint的時(shí)間復(fù)雜度均為O(m*n),本程序的空間復(fù)雜度也為O(m*n)(棧所占最大空間)2、使用說明和運(yùn)行結(jié)果:(1)首先以文件形式輸入迷宮數(shù)據(jù),如圖三:12-記事本丨回文1中E探輯E13式衛(wèi))樂也耳和(HJEFU

19、LU1U0C110-LUL-1)11C0:1n1n劃FJ圖三(2)進(jìn)入演示程序后,會(huì)出現(xiàn)以下界面如圖四:圖四(3) 進(jìn)入“創(chuàng)建迷宮”的命令后,即提示輸入迷宮數(shù)據(jù)的文件名,結(jié)束符為“回車符”,該命令執(zhí)行之后輸出“迷宮建立完成”,且輸出下面可執(zhí)行的操作。如圖五:圖五(4) 進(jìn)入“執(zhí)行迷宮”的命令后,即提示輸入迷宮入口,出口的坐標(biāo),結(jié)束符為“回車符”,該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路徑。請(qǐng)注意:若迷宮中存在路徑,執(zhí)行此命令后,迷宮狀態(tài)已經(jīng)改變,若要重復(fù)執(zhí)行此命令,需重新輸入迷宮數(shù)據(jù)。如圖六:圖六(5) 進(jìn)入“輸出迷宮”的命令后,即輸出迷宮求出路徑之后的狀態(tài)。#表示障礙,表示曾走過但不通

20、,*表示路徑。如圖七:圖七(6) 進(jìn)入“退出”的命令后,按任意鍵結(jié)束。如圖八:圖八3、缺點(diǎn)與改進(jìn):(1) 在定義函數(shù)Mazepath的時(shí)候,開始的循環(huán)語句的結(jié)束條件不對(duì),沒有出路時(shí),導(dǎo)致一直出現(xiàn)了不正確的結(jié)果,最后沒有新位置入棧,則返回上一個(gè)位置,否則沒有路徑。(2) 只是以文件形式輸入迷宮,如果迷宮數(shù)據(jù)量大時(shí),要先建好文件還是很浪費(fèi)時(shí)間,如果以隨機(jī)產(chǎn)生函數(shù)自動(dòng)產(chǎn)生迷宮會(huì)更好。五、個(gè)人工作及創(chuàng)新為了準(zhǔn)備這次課程設(shè)計(jì)我查找了很多的資料,對(duì)于迷宮問題的求解中迷宮的產(chǎn)生方式有很多的不同,有的是直接輸入迷宮,有的是用文件輸入,有的是隨機(jī)函數(shù)產(chǎn)生,我的課設(shè)是參考了用文件輸入的方法,這樣做相比直接輸入迷宮

21、操作要更簡單。當(dāng)然用隨機(jī)函數(shù)產(chǎn)生迷宮比如用:for(i=0;iMAX_ROW;i+)for(j=0;jMAX_COL;j+)mazeij=(int)(rand()%2);maze10=1;/*startpoint*/mazeMAX_ROW-1MAX_COL-2=1;/*endpoint*/這樣產(chǎn)生迷宮要更加的方便。結(jié)果也有不確定性,可能可以有通路也可能沒有。對(duì)于迷宮的求解都是采用的“窮舉求解”的方法,用到了一些棧的知識(shí)。把以前學(xué)過的棧的基本操作實(shí)際應(yīng)用了一番也使有了更加清楚的認(rèn)識(shí)。在求解迷宮的算法中,先設(shè)定當(dāng)前位置的初值為入口位置,然后Do若當(dāng)前位置可通,則將當(dāng)前位置插入棧頂;若該位置是出口位

22、置,則結(jié)束;否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置;否則若棧不為空且棧頂位置尚有其它方向未被探索,則設(shè)定新的當(dāng)前位置為延順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊;若棧不空但棧頂位置四周均不通,則刪去棧頂位置;若棧不為空,則重新測試新的棧頂位置,直至找到一個(gè)可通的相鄰塊或出棧至???;求解迷宮的算法大概就是這么個(gè)思路。六、小結(jié)要能很好的掌握編程,僅僅通過幾個(gè)簡單的程序的編寫是無法達(dá)成的,更需要的是大量的積累和深入研究才可能。在程序的編寫中也不能一味的向已有的程序進(jìn)行模仿,而要自己去探索,去尋找最好的解決方法,只有帶著問題去反復(fù)實(shí)踐,才能更熟練的掌握和運(yùn)用,當(dāng)然,對(duì)現(xiàn)有的程序也要多去接觸,因?yàn)橛行┏绦蚴俏覀冊(cè)诙虝r(shí)間內(nèi)無法想出來的,我們也應(yīng)該去參考別人的作品,這樣可以節(jié)約時(shí)間獲得更多的知識(shí)。最重要的是持之以恒,要經(jīng)常性的復(fù)習(xí)原來接觸到的程序,這樣才能保證我們有足夠的經(jīng)驗(yàn)去面對(duì)程序問題。參考文獻(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è)計(jì)(第四版)清華大學(xué)出版社.2007

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!