1、®淵州伸吊后浦?jǐn)?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)大作業(yè)20140821班題目迷宮問題專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名姚鑫學(xué)號(hào)2014082309指導(dǎo)教師樊艷芬完成日期2016/5/19湖州師范學(xué)院信息工程學(xué)院目錄內(nèi)容摘要1,jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj設(shè)計(jì)任務(wù)與技術(shù)要求,2總體設(shè)計(jì)方案2,，數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)，2程序清單3，程序測(cè)試與調(diào)試，7結(jié)論與體會(huì)10I，Ii，/、，I迷宮問題【內(nèi)容摘要】在一個(gè)m行，n列的迷宮中求從入口到出口的一條簡(jiǎn)單路徑，即在求得路徑上不能同時(shí)重復(fù)出現(xiàn)同一通道。迷宮可用下圖所示的方塊來表示，每個(gè)方塊或者是通道（用空白方塊表示）或者是墻（用帶

2、陰影的方塊表示）。0和1分別表示迷宮中的通道和墻。輸出時(shí)簡(jiǎn)單路徑用表示，起點(diǎn)用入表示，出口用出表示，墻用表示，可走的路用表示。輸入mn,表示m行n歹U。再輸入m行n列的迷宮（用0和1組成的矩陣表示），再輸入迷宮的起點(diǎn)和終點(diǎn)，輸出迷宮（含有從起點(diǎn)到終點(diǎn)的簡(jiǎn)單路徑）。運(yùn)用了深度優(yōu)先搜索和遞歸的相關(guān)知識(shí)。【關(guān)鍵字】深度優(yōu)先搜索，遞歸AbstractLookingforasimplepathfromtheentrancetotheexitinamazeofMrowsandNcolumns,thatis,theroadcouldnotberepeatedatthesametimeinthepath.Am

3、azecanbeshownasdiamondsinthefollowingfigures.Eachdiamondiseitherroadorwall.Well,ablankdiamondshowstheroadandablackdiamondshowsthewall.Intheprogram,zerorepresentsroad,andonerepresentswall.Whenweoutput,representsroad,enterstandsforstartingpoint,outstandsforexitand''representswall.Well,'

4、9;standsforthewaythatwecanchoose.Firstweshouldtypeinmandn.Thentypeinrowsofmandcolumnsofnwhichcanberepresentedbymatrixmadeofzeroandone.Intheend,weshouldtypeinthestartingpointandexit.WehavelearnedtheinformationaboutDepthFirstSearchandrecursion.KeywordsDepthFirstSearch,recursion1、 實(shí)驗(yàn)內(nèi)容概述（設(shè)計(jì)任務(wù)與技術(shù)要求）以一個(gè)m

5、xn的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，并把這條通路顯示出來，或得出沒有通路的結(jié)論。2、 實(shí)驗(yàn)?zāi)康母攀觯傮w設(shè)計(jì)方案）a）掌握迷宮問題的DFS（深度優(yōu)先搜索）解法。b）了解和熟悉深度優(yōu)先搜索的思路。c）復(fù)習(xí)和熟悉二維數(shù)組的用法。d）使用圖形來美化輸出，使得輸出一目了然。3、 解題思路的描述（數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)）（1）總體思路：先輸入迷宮多少行多少列（從1存到n,0行0列以及n+1行n+1列設(shè)置為墻用1表示），再輸入迷宮的入口和出口，然后遞歸調(diào)用DFS函數(shù)（深度優(yōu)先搜索）來尋找從起點(diǎn)到終點(diǎn)的路線。在搜索過程中把存迷宮的

6、二維數(shù)組中每個(gè)點(diǎn)分別置為：0尚未走過的路1墻2路線然后判斷是否存在這樣一條路線，如果不存在，就輸出“不存在從入口到出口的路線”；如果存在，就輸出迷宮（包括路線）。并輸出注釋。''meanstheroute''meanstheroad''meansthewall（2）數(shù)據(jù)結(jié)構(gòu)的選擇和描述：選用了int類型數(shù)組，數(shù)組a用來存儲(chǔ)迷宮，結(jié)構(gòu)體Point用來定義入口坐標(biāo)和出口坐標(biāo)，x代表橫坐標(biāo)，y代表縱坐標(biāo)。flag用來記錄dfs時(shí)是否找到出口，即退出dfs的標(biāo)志。（flag為1時(shí)找到出口，為0時(shí)沒找到）（3）要算法的功能和描述：采用了深度優(yōu)先搜索（DFS

7、的思想。每次搜索的方向依次為右下左上，每搜索一個(gè)點(diǎn)就標(biāo)記為2,若從該點(diǎn)的四個(gè)方向進(jìn)行dfs都無(wú)法找到出口，就重新標(biāo)記為0.;（4）DFS的具體描述：1 .傳入一個(gè)點(diǎn)的橫縱坐標(biāo)，一開始就把傳入的存迷宮的這個(gè)二維數(shù)組節(jié)點(diǎn)標(biāo)記為2（路線），2 .判斷是否為終點(diǎn)，如果是終點(diǎn)flag標(biāo)記為1（防止退出DFS時(shí)走過的路線被還原0）,并跳出DFS函數(shù)；否則什么也不做，繼續(xù)往下運(yùn)行；3 .向右搜索：判斷右邊相鄰的結(jié)點(diǎn)是否違反要求（即是否是墻或者越界），如果不違反要求，就把右邊相鄰的結(jié)點(diǎn)傳入DFS進(jìn)行搜索；否則什么也不做，繼續(xù)運(yùn)行；判斷是否已經(jīng)找到終點(diǎn)，若已經(jīng)找到終點(diǎn)（flag=1）直接跳出函數(shù)；4 .向下搜索

8、：判斷下邊相鄰的結(jié)點(diǎn)是否違反要求（即是否是墻或者越界），如果不違反要求，就把下邊相鄰的結(jié)點(diǎn)傳入DFS進(jìn)行搜索；否則什么也不做，繼續(xù)運(yùn)行；判斷是否已經(jīng)找到終點(diǎn)，若已經(jīng)找到終點(diǎn)（flag=1）直接跳出函數(shù)；5 .向左搜索：判斷左邊相鄰的結(jié)點(diǎn)是否違反要求（即是否是墻或者越界），如果不違反要求，就把左邊相鄰的結(jié)點(diǎn)傳入DFS進(jìn)行搜索；否則什么也不做，繼續(xù)運(yùn)行；判斷是否已經(jīng)找到終點(diǎn)，若已經(jīng)找到終點(diǎn)（flag=1）直接跳出函數(shù)；6 .向上搜索：判斷上邊相鄰的結(jié)點(diǎn)是否違反要求（即是否是墻或者越界），如果不違反要求，就把上邊相鄰的結(jié)點(diǎn)傳入DFS進(jìn)行搜索；否則什么也不做，繼續(xù)運(yùn)行；判斷是否已經(jīng)找到終點(diǎn)，若已經(jīng)找到

9、終點(diǎn)（flag=1）直接跳出函數(shù)；7 .運(yùn)行到這里還沒找到終點(diǎn)表示此路不通，把這點(diǎn)還原為沒走過時(shí)的樣子（重新標(biāo)記為0）;4、 源程序清單（源程序中應(yīng)該附有必要的注釋）(1)源程序#include<stdio.h>typedefstructpointintx;inty;Point;Pointstart,end;inta4040;intm,n;intflag=0;voiddfs(intx,inty)axy=2;if(x=end.x)&&(y=end.y)flag=1;return;if(y+1<=n)&&(axy+1=0)dfs(x,y+1);if

10、(flag)/迷宮中每個(gè)點(diǎn)/迷宮的入口與出口/輸入時(shí)迷宮存儲(chǔ)的數(shù)組m:行n:歹U/signofexitdfs退出的標(biāo)志/深度優(yōu)先搜索/表示x行y列這個(gè)位置已被走過/找到了出口/退出dfs,防止走過的路線被還原/向右搜索return;)if(x+1<=m)&&(ax+1y=0)dfs(x+1,y);)if(flag)return;)if(y-1>=1)&&(axy-1=0)dfs(x,y-1);)if(flag)return;)if(x-1>=1)&&(ax-1y=0)dfs(x-1,y);)if(flag)return;)axy

11、=0;)/向下搜索/向左搜索/向上搜索/此路不通，把這點(diǎn)還原為沒走過時(shí)的樣子intmain()inti,j;printf("請(qǐng)輸入多少行多少列：(m,n)(注：輸入00結(jié)束)n");while(scanf("%d%d”,&m,&n)&&(m|n)/輸入00結(jié)束printf("請(qǐng)輸入迷宮：(1表示墻0表示路)n");for(i=0;i<=m+1;i+)/輸入迷宮for(j=0;j<=n+1;j+)if(i=0|j=0|i=m+1|j=n+1)/外面置為1,即墻a皿=1;elsescanf("%

12、d",&aij);printf("請(qǐng)輸入迷宮入口和出口：x1y1x2y2n");scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);dfs(start.x,start.y);if(!flag)printf("不存在從入口到出口的路線n");for(i=0;i<=m+1;i+)for(j=0;j<=n+1;j+)if(i=start.x&&j=start.y)printf("入");elsei

13、f(i=end.x&&j=end.y)printf("出)elseif(aij=1)printf("");elseif(aij=0)printf("");elseif(aij=2)printf("");printf("n");/printf("''meanstherouten");printf("''meanstheroadn");printf("''meansthewalln");

14、return0;/輸入迷宮入口及出口/深度優(yōu)先搜索搜索路徑/輸出結(jié)果/入口輸出美化出口輸出美化/墻輸出美化/路輸出美化/路線輸出美化換行/注釋(2) 算法的時(shí)間復(fù)雜度是什么？算法的空間復(fù)雜度是什么？為什么?答：空間復(fù)雜度：線性時(shí)間復(fù)雜度，具體看最長(zhǎng)的那條路徑長(zhǎng)度。棧中維持單一路徑上的節(jié)點(diǎn);時(shí)間復(fù)雜度：O(m+1)*(n+1)注：存儲(chǔ)迷宮所用的行數(shù)乘列數(shù);(3) 還可以擴(kuò)充自己的想法，題目要求所編程序都能適用哪些情況，如果做一些修改，還能適合什么情況(能解決什么問題)？答：此代碼還可以解決類似的尋找路徑問題，且輸出形象簡(jiǎn)潔。做一些修改可以解決大多數(shù)的DFS問題，如油田問題(記憶化搜索)；(4)

15、說明在這個(gè)程序中所使用的各變量、形式參數(shù)的具體含義及各子程序之間的調(diào)用關(guān)系等。答：1. 調(diào)用關(guān)系：調(diào)用DFS函數(shù)，且在搜索的過程中一直調(diào)用，直到找到終點(diǎn)。2. 結(jié)構(gòu)體Point:用來表示迷宮的每個(gè)結(jié)點(diǎn)，擁有成員變量x,y皆為整形。3. Start,End:a) Start:迷宮的起點(diǎn)；b) End:迷宮的終點(diǎn)4. a4040:存儲(chǔ)迷宮的數(shù)組；5. m,n：a) m行；b) n歹U;6. flag:dfs退出的標(biāo)志；五、程序調(diào)試及測(cè)試結(jié)果（1） 上機(jī)調(diào)試上述程序，總結(jié)在調(diào)試過程中出現(xiàn)的問題及解決方法1 .一開始沒有定義flag導(dǎo)致找到從起點(diǎn)到終點(diǎn)的路線后無(wú)法輸出路線。因?yàn)樵谕顺鰰r(shí)都被還原了（還原

16、為未走過時(shí)的樣子了）；2 .在美化輸出時(shí)沒有考慮到有些字符是普通的一個(gè)字符的兩倍，導(dǎo)致輸出完全不對(duì)；3 .沒有考慮找不到從起點(diǎn)到終點(diǎn)的路線時(shí)的情況；4 .深度優(yōu)先搜索時(shí)在搜索完四個(gè)方向都沒有找到終點(diǎn)時(shí)忘記把這個(gè)點(diǎn)還原為0了;（2） 給出幾組有代表性的數(shù)據(jù)，運(yùn)行上述程序，查看運(yùn)行結(jié)果，分析運(yùn)行結(jié)果。截圖15X5的迷宮從（1,1）到（5,5）的路線tC:U5er5Administrator,Desk±op健高巨至2exe睛輸入多少行多少列:晴輸入迷宮：（工表示墻口表示路）II1010601011aiq&&情輸入迷宮入口和出口工WX2皿1135懷存在從人口到出口的路線人ne

17、ansr1n&ansJ1nesnsthethetherouteroaduall截圖25X5的迷宮從（1,1）到（3,5）,不存在路線截圖3書上的例子（6X9的迷宮）從（1,1）到（6,9）的路線截圖4書上的例子（6X9的迷宮）從（1,1）到（1,9）路線截圖512X18的迷宮從（1,1）到（12,18）的路線六、結(jié)論與體會(huì)（1） 在解決和設(shè)計(jì)本文題目所涉及到的問題時(shí)，你所采取的方法、手段和關(guān)鍵性的技術(shù)。采用了DFS（深度優(yōu)先搜索），遞歸，輸出的轉(zhuǎn)化。（2） 在調(diào)試程序的過程中你所遇到的問題及解決方法。1 .一開始沒有定義flag導(dǎo)致找到從起點(diǎn)到終點(diǎn)的路線后無(wú)法輸出路線。因?yàn)樵谕顺鰰r(shí)都被

18、還原了。（還原為未走過時(shí)的樣子了）；2 .在美化輸出時(shí)沒有考慮到有些字符是普通的一個(gè)字符的兩倍，導(dǎo)致輸出完全不對(duì)3 .沒有考慮找不到從起點(diǎn)到終點(diǎn)的路線時(shí)的情況；4 .深度優(yōu)先搜索時(shí)在搜索完四個(gè)方向都沒有找到終點(diǎn)時(shí)忘記把這個(gè)點(diǎn)還原為0了;（3） 關(guān)于程序的特色和改進(jìn)設(shè)想。特色：1 .輸出十分形象簡(jiǎn)潔，只要輸入迷宮以及起點(diǎn)終點(diǎn)就可以輸出所求路線（路線存在的情況下）2 .采用了深度優(yōu)先搜索，代碼簡(jiǎn)潔，可讀性高；3 .深度優(yōu)先搜索時(shí)的改變方向的方式采用了最簡(jiǎn)單，易懂的方式，雖然啰嗦，但是可讀性好；改進(jìn)設(shè)想：1.可以使用BFS（廣度優(yōu)先搜索），可以找出從起點(diǎn)到終點(diǎn)的最短路徑，但是代碼會(huì)變得更長(zhǎng)，用到了隊(duì)列，可讀性降低。2.使用C+的容器隊(duì)列來使用BFS,可是代碼簡(jiǎn)潔。（4）其他需要說明的情況。任意大小的迷宮以及任意的起點(diǎn)與終點(diǎn)皆可計(jì)算出從起點(diǎn)到終點(diǎn)的路徑（雖然不是最短的）。結(jié)：迷宮問題我一開始在輸出的處理上有點(diǎn)問題，我一開始把存迷宮的int型二維數(shù)組轉(zhuǎn)存到char的字符型