迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-文庫吧
2025-07-06 13:33 本頁面
【正文】 一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，將位置(0,0)(序號0)放入隊列中，其前節(jié)點為空，從它開始搜索，其標(biāo)記變?yōu)?，由于其只有一個非障礙位置，所以接下來移動到(0,1)(序號1)，其前節(jié)點序號為0，標(biāo)記變?yōu)?，然后從(0,1)移動到(1,1)(序號2)，放入隊列中，其前節(jié)點序號為1，(1,1)存在(1，2)(序號3)、(2，1)(序號4)兩個可移動位置，它的相鄰非障礙節(jié)點均入隊列，且它們的前節(jié)點序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點的位置，逆序就可以找到其從出口到入口的通路。如下表所示： 0 1 2 3 4 5 6 7 8 9 10(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)(3,4)10122345679 由此可以看出，得到最短路徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 搜索算法流程圖如下所示： 概要設(shè)計1.①構(gòu)建一個二維數(shù)組maze[M+2][N+2]用于存儲迷宮矩陣②自動或手動生成迷宮，即為二維數(shù)組maze[M+2][N+2]賦值③構(gòu)建一個隊列用于存儲迷宮路徑④建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況⑤實現(xiàn)搜索算法⑥屏幕上顯示操作菜單 ： (1)主函數(shù) main()(2)手動生成迷宮函數(shù) shoudong_maze()(3)自動生成迷宮函數(shù) zidong_maze()(4)將迷宮打印成圖形 print_maze()(5)打印迷宮路徑 (若存在路徑) result_maze()(6)入隊 enqueue()(7)出隊 dequeue()(8)判斷隊列是否為空 is_empty()(9)訪問節(jié)點 visit()(10)搜索迷宮路徑 mgpath() 詳細設(shè)計實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法1. 節(jié)點類型和指針類型迷宮矩陣類型：int maze[M+2][N+2]。為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型：struct point{int row,col,predecessor} que[512]2. 迷宮的操作(1)手動生成迷宮void shoudong_maze(int m,int n){定義i,j為循環(huán)變量for(i=m)for(j=n)輸入maze[i][j]的值}(2)自動生成迷宮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)生的隨機數(shù)是從0到RAND_MAX,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(YX+1)+X。}(3)打印迷宮圖形void print_maze(int m,int n){用i,j循環(huán)變量，將maze[i][j]輸出 □、■}(4)打印迷宮路徑void result_maze(int m,int n){用i,j循環(huán)變量，將maze[i][j]輸出 □、■、☆}(5)搜索迷宮路徑 ①迷宮中隊列入隊操作void enqueue(struct point p){將p放入隊尾，tail++}②迷宮中隊列出隊操作struct point dequeue(struct point p){head++,返回que[head1]}③判斷隊列是否為空int is_empty(){返回head==tail的值，當(dāng)隊列為空時，返回0}④訪問迷宮矩陣中節(jié)點void visit(int row,int col,int maze[41][41]){建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,head1,maze[row][col]=2,表示該節(jié)點以被訪問過。調(diào)用enqueue(visit_point),將該節(jié)點入隊}⑤路徑求解void mgpath(int maze[41][41],int m,int n){先定義入口節(jié)點為struct point p={0,0,
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1