迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-在線瀏覽
2024-08-31 13:33本頁(yè)面
【正文】 1矩陣來(lái)描述，：迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來(lái)唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組maze[M+2][N+2],然后用它的前m行n列來(lái)存放元素，即可得到一個(gè)mn的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m1,n1)表示迷宮出口位置。：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。以矩陣 0 0 1 0 1 為例，來(lái)示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，將位置(0,0)(序號(hào)0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開始搜索，其標(biāo)記變?yōu)?，由于其只有一個(gè)非障礙位置，所以接下來(lái)移動(dòng)到(0,1)(序號(hào)1)，其前節(jié)點(diǎn)序號(hào)為0，標(biāo)記變?yōu)?，然后從(0,1)移動(dòng)到(1,1)(序號(hào)2)，放入隊(duì)列中，其前節(jié)點(diǎn)序號(hào)為1，(1,1)存在(1，2)(序號(hào)3)、(2，1)(序號(hào)4)兩個(gè)可移動(dòng)位置，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)列，且它們的前節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路。為方便操作使其為全局變量迷宮中節(jié)點(diǎn)類型及隊(duì)列類型：struct point{int row,col,predecessor} que[512]2. 迷宮的操作(1)手動(dòng)生成迷宮void shoudong_maze(int m,int n){定義i,j為循環(huán)變量for(i=m)for(j=n)輸入maze[i][j]的值}(2)自動(dòng)生成迷宮void zidong_maze(int m,int n){定義i,j為循環(huán)變量for(i=m)for(j=n) maze[i][j]=rand()%2 //由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(YX+1)+X。調(diào)用enqueue(visit_point),將該節(jié)點(diǎn)入隊(duì)}⑤路徑求解void mgpath(int maze[41][41],int m,int n){先定義入口節(jié)點(diǎn)為struct point p={0,0,1},從maze[0][0]開始訪問。否則訪問入口節(jié)點(diǎn)，將入口節(jié)點(diǎn)標(biāo)記為訪問過(guò)maze[][]=2,調(diào)用函數(shù)enqueue(p)將該節(jié)點(diǎn)入隊(duì)。while(!=1){p=queue[]。} 最后將路徑圖形打印出來(lái)。i)。 print_maze(m,n)。 if(X!=0) result_maze(m,n)。 print_maze(m,n)。 if(X!=0) result_maze(m,n)。 break。 參考文獻(xiàn) 【1】 嚴(yán)蔚敏 吳偉民 《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》 清華大學(xué)出版社， 2009年9月 【2】 譚浩強(qiáng) 《C程序設(shè)計(jì)(第三版)》 清華大學(xué)出版社 2009年1月第二部分 課程設(shè)計(jì)總結(jié)通過(guò)這段時(shí)間的課程設(shè)計(jì)，本人對(duì)計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及C語(yǔ)言的使用都有了更深的了解。在理論學(xué)習(xí)和上機(jī)實(shí)踐的各個(gè)環(huán)節(jié)中，通過(guò)自主學(xué)習(xí)和請(qǐng)教老師，我收獲了不少。從當(dāng)初不喜歡上機(jī)寫程序到現(xiàn)在能主動(dòng)寫程序，從當(dāng)初拿著程序不只如何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識(shí)解決實(shí)際問題的轉(zhuǎn)變，我發(fā)現(xiàn)無(wú)論是專業(yè)知識(shí)還是動(dòng)手能力，自己都有很大程度的提高。在老師的指導(dǎo)幫助下，同學(xué)們課余時(shí)間的討論中，這些問題都一一得到了解決。例如：頭文件的使用，變量和數(shù)組的范圍問題，定義變量時(shí)出現(xiàn)的問題等等。在這次短短的課程實(shí)踐里，我們得到了侯瑞蓮老師的關(guān)心和幫助。當(dāng)我們遇到技術(shù)上難以解決的問題時(shí)，她就會(huì)指導(dǎo)我們解決問題，她把自己多年來(lái)積累的經(jīng)驗(yàn)教授給我們，使我們順利地完成了課程實(shí)踐任務(wù)。int maze[N+2][M+2]。}queue[512]。void shoudong_maze(int m,int n){ int i,j。 printf(請(qǐng)按行輸
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1