數(shù)據(jù)結(jié)構(gòu) 迷宮求解問題 課程設(shè)計

PAGEPAGE16江西理工大學(xué)應(yīng)用科學(xué)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目:迷宮求解班級:姓名:學(xué)號:完成日期:目錄一、課程設(shè)計概述…………………..2二、問題描述……………………….2三、需求分析……………………….2四、概要設(shè)計……………………….2 五、存儲結(jié)構(gòu)……………………….4六、流程圖………………………...4 詳細設(shè)計……………………….4調(diào)試分析………………………..8運行結(jié)果及分析……………….8參考文獻……………………….10主程序……………………..…10一、課程設(shè)計概述本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計主要完成用棧來實現(xiàn)迷宮求解問題。使用語言：C編譯環(huán)境：VC6.0二、問題描述迷宮問題是取自心理學(xué)的一個古典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復(fù)進行上述實驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠經(jīng)過多次試驗最終學(xué)會走通迷宮的路線。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。

圖1-1.三、需求分析要求設(shè)計程序輸出如下：(1)建立一個大小為m×n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點的坐標。（3）用一種標志（如數(shù)字8）在迷宮中標出該條通路；（4）在屏幕上輸出迷宮和通路；（5）上述功能可用菜單選擇。概要設(shè)計設(shè)定棧的抽象數(shù)據(jù)類型定義為：ADTstack{數(shù)據(jù)對象：D={ai|ai∈charset,i=1,2,……,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2……,n}基本操作：InitStack(&S)//操作結(jié)果：構(gòu)造一個空棧S。DestroyStack(&S)//初始條件：棧S已存在。//操作結(jié)果：銷毀棧S。ClearStack(&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é)果：從棧底到棧頂依次對S中的每個元素調(diào)用函數(shù)visit().}ADTstack存儲結(jié)構(gòu)structpoint{ introw；//通道塊在路徑上的“行”位置intcol;//迷宮的“出口”Intpredecessor;//該通道的“前趨”}queue[512];流程圖圖1-2七、詳細設(shè)計實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法節(jié)點類型和指針類型迷宮矩陣類型：intmaze[M+2][N+2];為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型：structpoint{introw,col,predecessor}que[512]迷宮的操作(1)手動生成迷宮voidshoudong_maze(intm,intn){定義i,j為循環(huán)變量for(i<=m)for(j<=n)輸入maze[i][j]的值}(2)自動生成迷宮voidzidong_maze(intm,intn){定義i,j為循環(huán)變量for(i<=m)for(j<=n)maze[i][j]=rand()%2//由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;}(3)打印迷宮圖形voidprint_maze(intm,intn){用i,j循環(huán)變量，將maze[i][j]輸出□、■}(4)打印迷宮路徑voidresult_maze(intm,intn){用i,j循環(huán)變量，將maze[i][j]輸出□、■、☆}(5)搜索迷宮路徑①迷宮中隊列入隊操作voidenqueue(structpointp){將p放入隊尾，tail++}②迷宮中隊列出隊操作structpointdequeue(structpointp){head++,返回que[head-1]}③判斷隊列是否為空intis_empty(){返回head==tail的值，當隊列為空時，返回0}④訪問迷宮矩陣中節(jié)點voidvisit(introw,intcol,intmaze[41][41]){建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,head-1,maze[row][col]=2,表示該節(jié)點以被訪問過;調(diào)用enqueue(visit_point),將該節(jié)點入隊}⑤路徑求解voidmgpath(intmaze[41][41],intm,intn){先定義入口節(jié)點為structpointp={0,0,-1},從maze[0][0]開始訪問。如果入口處即為障礙，則此迷宮無解，返回0，程序結(jié)束。否則訪問入口節(jié)點，將入口節(jié)點標記為訪問過maze[p.row][p.col]=2,調(diào)用函數(shù)enqueue(p)將該節(jié)點入隊。判斷隊列是否為空，當隊列不為空時，則運行以下操作：{調(diào)用dequeue()函數(shù)，將隊頭元素返回給p，如果p.row==m-1且p.col==n-1,即到達出口節(jié)點，即找到了路徑，結(jié)束如果p.col+1<n且maze[p.row][p.col+1]==0,說明未到迷宮右邊界，且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點入隊標記已訪問如果p.row+1<m且maze[p.row+1][p.col]==0,說明未到迷宮下邊界，且其下方有通路,則visit(p.row+1,p.col,maze),將下方節(jié)點入隊標記已訪問如果p.col-1>0且maze[p.row][p.col-1]==0,說明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze),將左方節(jié)點入隊標記已訪問如果p.row-1>0且maze[p.row-1][p.col]==0,說明未到迷宮上邊界，且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點入隊標記已訪問}訪問到出口(找到路徑)即p.row==m-1且p.col==n-1,則逆序?qū)⒙窂綐擞洖?即maze[p.row][p.col]==3;while(p.predecessor!=-1){p=queue[p.predecessor];maze[p.row][p.col]==3;}最后將路徑圖形打印出來。3.菜單選擇while(cycle!=(-1))☆手動生成迷宮請按：1☆自動生成迷宮請按：2☆退出請按：3scanf("%d",&i);switch(i){case1：請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入)shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n);if(X!=0)result_maze(m,n);case2：請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入)zidong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);case3：cycle=(-1);break;}注：具體源代碼見附錄八、調(diào)試分析在調(diào)試過程中，首先使用的是棧進行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法。九、運行結(jié)果及分析1.程序主界面圖1-32.手動輸入迷宮圖1-4圖1-53.自動生成迷宮圖1-6圖1-7十、參考文獻[1]浩譚強.C程序設(shè)計[M]第2版.北京:清華大學(xué)出版社,2004年。[2]蔚嚴敏、吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2OO5年。十一、主程序附錄：#include"stdlib.h"#include"stdio.h"#defineN39#defineM39intX;intmaze[N+2][M+2];structpoint{ introw,col,predecessor;}queue[512];inthead=0,tail=0;voidshoudong_maze(intm,intn){ inti,j; printf("\n\n"); printf("請按行輸入迷宮，0表示通路，1表示障礙:\n\n"); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&maze[i][j]);}voidzidong_maze(intm,intn){ inti,j; printf("\n迷宮生成中……\n\n"); system("pause"); for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2;//由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX//RAND_MAX是定義在stdlib.h中的,其值至少為32767)//要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;}voidprint_maze(intm,intn){ inti,j; printf("\n迷宮生成結(jié)果如下:\n\n"); printf("迷宮入口\n"); printf("↓"); for(i=0;i<m;i++) {printf("\n"); for(j=0;j<n;j++) {if(maze[i][j]==0)printf("□"); if(maze[i][j]==1)printf("■");} } printf("→迷宮出口\n");}voidresult_maze(intm,intn){ inti,j; printf("迷宮通路(用☆表示)如下所示：\n\t"); for(i=0;i<m;i++) {printf("\n"); for(j=0;j<n;j++) {if(maze[i][j]==0||maze[i][j]==2)printf("□"); if(maze[i][j]==1)printf("■"); if(maze[i][j]==3)printf("☆"); } }}voidenqueue(structpointp){ queue[tail]=p; tail++;}structpointdequeue(){ head++; returnqueue[head-1];}intis_empty(){ returnhead==tail;}voidvisit(introw,intcol,intmaze[41][41]){ structpointvisit_point={row,col,head-1}; maze[row][col]=2; enqueue(visit_point);}intmgpath(intmaze[41][41],intm,intn){ X=1; structpointp={0,0,-1}; if(maze[p.row][p.col]==1){printf("\n===============================================\n");printf("此迷宮無解\n\n");X=0;return0;} maze[p.row][p.col]=2; enqueue(p); while(!is_empty()) {p=dequeue(); if((p.row==m-1)&&(p.col==n-1))break; if((p.col+1<n)&&(maze[p.row][p.col+1]==0))visit(p.row,p.col+1,maze); if((p.row+1<m)&&(maze[p.row+1][p.col]==0))visit(p.row+1,p.col,maze); if((p.col-1>=0)&&(maze[p.row][p.col-1]==0))visit(p.row,p.col-1,maze); if((p.row-1>=0)&&(maze[p.row-1][p.col]==0))visit(p.row-1,p.col,maze); } if(p.row==m-1&&p.col==n-1) {printf("\n==================================================================\n"); printf("迷宮路徑為：\n"); printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; while(p.predecessor!=-1) {p=queue[p.predecessor]; printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; } } else{printf("\n=============================================================\n"); printf("此迷宮無解！\n\n");X=0;} return0;}voidmain(){inti,m,n,cycle=0;while(cycle!=(-1)){printf("********************************************************************************\n");printf("歡迎進入迷宮求解系統(tǒng)\n");printf("\n");printf("********************************************************************************\n");printf("☆手動生成迷宮請按：1\n");printf("☆自動生成迷宮請按：2\n");printf("☆退出請按：3\n\n");printf("********************************************************************************\n");printf("\n");printf("請選擇你的操作：\n");scanf("%d",&i);switch(i){case1:printf("\n請輸入行數(shù)：");scanf("%d",&m); printf("\n");printf("請輸入列數(shù)：");scanf("%d",&n); while((m<=0||m>39)||(n<=0||n>39)) {printf("\n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請重新輸入：\n\n"); printf("請輸入行數(shù)：");scanf("%d",&m); printf("\n");printf("請輸入列數(shù)：");scanf("%d",&n); } shoudong_maze(m,n);