版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p><b> 課程設(shè)計(jì)報(bào)告</b></p><p> 課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p> 課程題目: 迷宮問(wèn)題 </p><p> 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p><b> 迷宮問(wèn)題</b></p><p><b>
2、; [實(shí)驗(yàn)?zāi)康腯</b></p><p> 綜合運(yùn)用數(shù)組、遞歸等數(shù)據(jù)結(jié)構(gòu)知識(shí),掌握、提高分析、設(shè)計(jì)、實(shí)現(xiàn)及測(cè)試程序的綜合能力。</p><p><b> [實(shí)驗(yàn)內(nèi)容及要求]</b></p><p> 以一個(gè)M×N的長(zhǎng)方陣表示迷宮,0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序,對(duì)任意設(shè)定的迷宮,求出一條從入口到出口
3、的通路,或得出沒(méi)有通路的結(jié)論。</p><p> 根據(jù)二維數(shù)組,輸出迷宮的圖形。</p><p> 探索迷宮的四個(gè)方向:RIGHT為向右,DOWN向下,LEFT向左,UP向上,輸出從入口到出口的行走路徑。</p><p><b> [測(cè)試數(shù)據(jù)]</b></p><p> 左上角(1,1)為入口,右下角(8,9)為
4、出口。</p><p><b> [實(shí)現(xiàn)方法]</b></p><p> 可使用回溯方法,即從入口出發(fā),順著某一個(gè)方向進(jìn)行探索,若能走通,則繼續(xù)往前進(jìn);否則沿著原路退回,換一個(gè)方向繼續(xù)探索,直至出口位置,求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口,則所設(shè)定的迷宮沒(méi)有通路。</p><p><b> [具體思路及結(jié)果]
5、</b></p><p> 首先,事先聲明好矩陣,矩陣長(zhǎng)寬,棧頂元素,矩陣點(diǎn)左邊等。</p><p> 然后,要求用戶盡享交互輸入迷宮(maze)各個(gè)點(diǎn)處的值(1或0)</p><p> 保存并初始化棧頂元素,置所有方向數(shù)為下。</p><p> 之后,一比較整潔大方的形式打印原迷宮供用戶查看。</p>&l
6、t;p> 同時(shí),開(kāi)始本程序的重點(diǎn),回溯算法,以1,2,3,4分別表示下上左右。</p><p> 多次使用for循環(huán)尋找可以到達(dá)出口的路徑,期間分別先后試探下,左,上,右</p><p> 置已經(jīng)走過(guò)的點(diǎn)為2防止死循環(huán),尋找完后存在TOP[]棧中。</p><p> 最后,打印找到的當(dāng)前迷宮路徑并以(坐標(biāo)1)——>(坐標(biāo)2)的形式輸出路徑,并且在
7、原迷宮的基礎(chǔ)上表示出當(dāng)前找到的路徑,以#代表走過(guò)的路徑0代表沒(méi)有障礙的地方,1代表障礙,畫(huà)出迷宮路徑圖,并且立刻執(zhí)行下一次循環(huán),尋找下一條可通過(guò)的路徑,并還原迷宮圖,繼續(xù)尋找路徑知道找到所有解后自動(dòng)退出。</p><p><b> [具體代碼]</b></p><p> #include <stdio.h></p><p>
8、#include <stdlib.h></p><p> #define n1 5</p><p> #define n2 5</p><p> typedef struct node</p><p><b> {</b></p><p> int x;//存x坐標(biāo)</
9、p><p> int y;//存y坐標(biāo)</p><p> int c;//存該點(diǎn)可能的下點(diǎn)所在的方向,表示向1表示向下,2左,3向上,4向右</p><p> }linkstack;</p><p> linkstack top[25];</p><p> int rows=0;</p><p
10、> int cols=0;</p><p> int i,j,k,m,p,q=0;</p><p> int maze[n1][n2];</p><p> void main()</p><p><b> {</b></p><p> for(p=0;p<=n1-1;p++
11、){</p><p> for(q=0;q<=n2-1;q++){</p><p> printf("請(qǐng)輸入第%d行第%d列的數(shù)\n",p+1,q+1);</p><p> scanf("%d",&maze[p][q]);</p><p><b> }</b>
12、</p><p><b> }</b></p><p> //初始化top[],置所有方向?yàn)橄?lt;/p><p> for(i=0;i<n1 * n2;i++)</p><p> {top[i].c=1;}</p><p> printf("the maze is:\n&q
13、uot;);</p><p><b> //打印原迷宮</b></p><p> for(i=0;i<n1;i++)</p><p> {for(j=0;j<n2;j++)</p><p> printf(maze[i][j]?"1 ":"0 ");</p
14、><p> printf("\n");}</p><p> i=0;top[i].x=0;top[i].y=0;</p><p> maze[0][0]=2;</p><p><b> //回溯算法</b></p><p><b> do{</b>&
15、lt;/p><p> if(top[i].c<5) //還可以向前試探</p><p> {if(top[i].x==4&&top[i].y==4) //已找到一個(gè)組合</p><p><b> { //打印路徑</b></p><p> printf("The way %d i
16、s:\n",m++);</p><p> for(j=0;j<=i;j++)</p><p> {printf("(%d,%d)-->",top[j].x,top[j].y);}</p><p> printf("\n");</p><p> //打印選出路徑的迷宮<
17、/p><p> for(j=0;j<n1;j++)</p><p> {for(k=0;k<n2;k++)</p><p> {if(maze[j][k]==0)printf("0 ");</p><p> else if(maze[j][k]==2) printf("# ");&l
18、t;/p><p> else printf("1 ");}</p><p> printf("\n");}</p><p> maze[top[i].x][top[i].y]=0;</p><p> top[i].c=1;</p><p><b> i--;<
19、;/b></p><p> top[i].c+=1;</p><p><b> continue;</b></p><p><b> }</b></p><p> switch(top[i].c) //向前試探</p><p><b> {<
20、/b></p><p><b> case 1:</b></p><p> {if(maze[top[i].x][top[i].y+1]==0)//下</p><p><b> {i++;</b></p><p> top[i].x=top[i-1].x;</p><
21、;p> top[i].y=top[i-1].y+1;</p><p> maze[top[i].x][top[i].y]=2;}</p><p><b> else</b></p><p> {top[i].c+=1;}</p><p><b> break;}</b></p&
22、gt;<p><b> case 2:</b></p><p> {if(maze[top[i-1].x-1][top[i].y]==0)//左</p><p><b> {i++;</b></p><p> top[i].x=top[i-1].x-1;</p><p> t
23、op[i].y=top[i-1].y;</p><p> maze[top[i].x][top[i].y]=2;}</p><p><b> else</b></p><p> {top[i].c+=1;}</p><p><b> break;}</b></p><p&
24、gt;<b> case 3:</b></p><p> {if(maze[top[i].x][top[i].y-1]==0)//上</p><p><b> {i++;</b></p><p> top[i].x=top[i-1].x;</p><p> top[i].y=top[i-1
25、].y-1;</p><p> maze[top[i].x][top[i].y]==2;}</p><p><b> else</b></p><p> {top[i].c+=1;}</p><p><b> break;}</b></p><p><b>
26、 case 4:</b></p><p> {if(maze[top[i].x+1][top[i].y]==0)//右</p><p><b> {i++;</b></p><p> top[i].x=top[i-1].x+1;</p><p> top[i].y=top[i-1].y;</p
27、><p> maze[top[i].x][top[i].y]=2;}</p><p><b> else</b></p><p> {top[i].c+=1;}</p><p><b> break;}</b></p><p><b> }</b>
28、</p><p><b> }</b></p><p> else //回溯</p><p> {if(i==0) return; //已找完所有解</p><p> maze[top[i].x][top[i].y]=0;</p><p> top[i].c=1;</p>
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 迷宮問(wèn)題——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(迷宮問(wèn)題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--迷宮
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---迷宮求解
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--求解迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題求解
- c數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題課程設(shè)計(jì)
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告迷宮求解
- 數(shù)據(jù)結(jié)構(gòu)迷宮求解課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)迷宮課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)迷宮課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論