迷宮問題求解_第1頁
迷宮問題求解_第2頁
迷宮問題求解_第3頁
迷宮問題求解_第4頁
迷宮問題求解_第5頁
已閱讀5頁,還剩12頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、課程設計報告課題名稱: 迷宮問題的求解及演示 姓 名: 學 號: 專 業(yè): 計算機與信息學院 班 級: 指導教師: 數據結構課程設計任務書針對本課程設計,完成以下課程設計任務書:1. 熟悉系統(tǒng)實現(xiàn)工具和上機環(huán)境。2. 根據課程設計任務,查閱相關資料。3. 針對所選課題完成以下工作: (1)需求分析(2)概要設計(3)詳細設計(4)編寫源程序(5)靜態(tài)走查程序和上機調試程序 4.書寫上述文檔和撰寫課程設計報告目 錄第一部分 課程設計任務書 1 第二部分 課程設計報告 2第一章 課程設計內容和要求42.1 問題描述42.2 需求分析4第二章 課程設計總體方案及分析43.1 概要設計73.2 詳細設

2、計73.3 調試分析103.4 測試結果10第三章 設計總結134.1課程設計總結134.2參考文獻 4.3 附錄(源代碼)14 第二部分 課程設計報告 第一章  課程設計內容和要求  2.1問題描述: 迷宮以16*16的矩陣存儲在數據文件中(迷宮中的障礙物要占到一定比例),編寫非遞歸的程序,求出一條從入口到出口的路徑并顯示之(結果若能用C的繪圖函數顯示更好)2.2需求分析:1要求設計程序輸出如下:(1) 建立一個大小為m×n的任意迷宮(迷宮數據可由用戶輸入或由程序自動生成),并在屏幕上顯示出來;(2)找出一條通路的二元組(i,j)數據序列,(i,j)表示通路上某

3、一點的坐標。(3)用一種標志(如數字8)在迷宮中標出該條通路;(4)在屏幕上輸出迷宮和通路;(5)上述功能可用菜單選擇。2.迷宮的建立:迷宮中存在通路和障礙,為了方便迷宮的創(chuàng)建,可用0表示通路,用1表示障礙,這樣迷宮就可以用0、1矩陣來描述,3.迷宮的存儲:迷宮是一個矩形區(qū)域,可以使用二維數組表示迷宮,這樣迷宮的每一個位置都可以用其行列號來唯一指定,但是二維數組不能動態(tài)定義其大小,我們可以考慮先定義一個較大的二維數組mazeM+2N+2,然后用它的前m行n列來存放元素,即可得到一個m×n的二維數組,這樣(0,0)表示迷宮入口位置,(m-1,n-1)表示迷宮出口位置。注:其中M,N分別

4、表示迷宮最大行、列數,本程序M、N的缺省值為39、39,當然,用戶也可根據需要,調整其大小。4.迷宮路徑的搜索:首先從迷宮的入口開始,如果該位置就是迷宮出口,則已經找到了一條路徑,搜索工作結束。否則搜索其上、下、左、右位置是否是障礙,若不是障礙,就移動到該位置,然后再從該位置開始搜索通往出口的路徑;若是障礙就選擇另一個相鄰的位置,并從它開始搜索路徑。為防止搜索重復出現(xiàn),則將已搜索過的位置標記為2,同時保留搜索痕跡,在考慮進入下一個位置搜索之前,將當前位置保存在一個隊列中,如果所有相鄰的非障礙位置均被搜索過,且未找到通往出口的路徑,則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法,如

5、果找到路徑,則為最短路徑。以矩陣 0 0 1 0 1 為例,來示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先,將位置(0,0)(序號0)放入隊列中,其前節(jié)點為空,從它開始搜索,其標記變?yōu)?,由于其只有一個非障礙位置,所以接下來移動到(0,1)(序號1),其前節(jié)點序號為0,標記變?yōu)?,然后從(0,1)移動到(1,1)(序號2),放入隊列中,其前節(jié)點序號為1,(1,1)存在(1,2)(序號3)、(2,1)(序號4)兩個可移動位置,其前節(jié)點序號均為2.對于每一個非障礙位置,它的相鄰非障礙節(jié)點均入隊列,且它們的前節(jié)點序號均為該位置的序號,所以如果存在路徑,則從出口處節(jié)點的位

6、置,逆序就可以找到其從出口到入口的通路。如下表所示: 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) 搜索算法流程圖如下所示: 第二章      課程設計總體方案及分析3.1概要設計1.構建一個二維數組mazeM+2N+2用于存儲迷宮矩陣自動或手動生成迷宮,即為二維數組mazeM+2N+2賦值構建一個隊列用

7、于存儲迷宮路徑建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況實現(xiàn)搜索算法屏幕上顯示操作菜單 2.本程序包含10個函數: (1)主函數 main()(2)手動生成迷宮函數 shoudong_maze()(3)自動生成迷宮函數 zidong_maze()(4)將迷宮打印成圖形 print_maze()(5)打印迷宮路徑 (若存在路徑) result_maze()(6)入隊 enqueue()(7)出隊 dequeue()(8)判斷隊列是否為空 is_empty()(9)訪問節(jié)點 visit()(10)搜索迷宮路徑 mgpath()3.2 詳細設計實現(xiàn)概要設計中定義的所有數據

8、類型及操作的偽代碼算法1. 節(jié)點類型和指針類型迷宮矩陣類型:int mazeM+2N+2;為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型:struct pointint row,col,predecessor que5122. 迷宮的操作(1)手動生成迷宮void shoudong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n)輸入mazeij的值(2)自動生成迷宮void zidong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n) mazeij=rand()%2 /由于rand

9、()產生的隨機數是從0到RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產生從X到Y的數,只需要這樣寫:k=rand()%(Y-X+1)+X;(3)打印迷宮圖形void print_maze(int m,int n)用i,j循環(huán)變量,將mazeij輸出 、(4)打印迷宮路徑void result_maze(int m,int n)用i,j循環(huán)變量,將mazeij輸出 、(5)搜索迷宮路徑 迷宮中隊列入隊操作void enqueue(struct point p)將p放入隊尾,tail+迷宮中隊列出隊操作struct point dequeue(stru

10、ct point p)head+,返回quehead-1判斷隊列是否為空int is_empty()返回head=tail的值,當隊列為空時,返回0訪問迷宮矩陣中節(jié)點void visit(int row,int col,int maze4141)建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,head-1,mazerowcol=2,表示該節(jié)點以被訪問過;調用enqueue(visit_point),將該節(jié)點入隊路徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點為struct point p=0,0,-1,從maze00開始訪問

11、。如果入口處即為障礙,則此迷宮無解,返回0 ,程序結束。否則訪問入口節(jié)點,將入口節(jié)點標記為訪問過mazep.rowp.col=2,調用函數enqueue(p)將該節(jié)點入隊。判斷隊列是否為空,當隊列不為空時,則運行以下操作: 調用dequeue()函數,將隊頭元素返回給p,如果p.row=m-1且p.col=n-1,即到達出口節(jié)點,即找到了路徑,結束如果p.col+1<n且mazep.rowp.col+1=0,說明未到迷宮右邊界,且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點入隊標記已訪問如果p.row+1<m且mazep.row+1p.col=0,

12、說明未到迷宮下邊界,且其下方有通路,則visit(p.row+1,p.col,maze),將下方節(jié)點入隊標記已訪問如果p.col-1>0且mazep.rowp.col-1=0,說明未到迷宮左邊界,且其左方有通路,則visit(p.row,p.col-1,maze),將左方節(jié)點入隊標記已訪問如果p.row-1>0且mazep.row-1p.col=0,說明未到迷宮上邊界,且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點入隊標記已訪問訪問到出口(找到路徑)即p.row=m-1且p.col=n-1,則逆序將路徑標記為3即mazep.rowp.col=3;w

13、hile(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3; 最后將路徑圖形打印出來。3.菜單選擇 while(cycle!=(-1) 手動生成迷宮 請按:1 自動生成迷宮 請按:2 退出 請按:3 scanf("%d",&i); switch(i) case 1:請輸入行列數(如果超出預設范圍則提示重新輸入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 2 :請輸入行列數(如

14、果超出預設范圍則提示重新輸入) zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 3:cycle=(-1); break;注:具體源代碼見附錄3.3 調試分析(1)在調試過程中,首先使用的是棧進行存儲,但是產生的路徑是多條或不是最短路徑,所以通過算法比較,改用此算法。(2)在編寫 while 語句時,另一種情況(即當前位置不能通過時)也同樣出現(xiàn)在墻節(jié)點就直接往南走的情況,綜合上面的情況,同樣的,也是退位沒有賦值。這種錯誤比較難發(fā)現(xiàn),往往只有在復雜的迷宮求解過程中才能發(fā)現(xiàn)。這類錯

15、誤屬于邏輯錯誤,調試不會顯示,需要自己拙句地查看和分析,并能充分的理解程序每一步的認識,才能發(fā)現(xiàn)并解決這樣的問題。 (3)在編寫MazePath函數時,當遇到墻(即遇到下一位置為1)時,直接從現(xiàn)在墻位置進行往南跳轉。以至有許多應該走的通路位置沒有走,而且使總共走的步數變短。在測試前期怎么也想不明白,出棧操作也有,退位也有,但就是不進行退到上一位置的操作。最后發(fā)現(xiàn),少了一步把出棧的數進行賦值的操作。(4)在進行對迷宮的輸出時,變成按行輸出,得不到預期的迷宮結果,更不用說驗證其正確性。這就是粗心造成的 。 3.4 測試結果 1.手動輸入迷宮  2.自動生成迷宮 第二部分 設計總結4.1

16、課程設計總結通過這次的數據結構課程設計讓我對計算機的應用,數據結構的作用以及c語言的使用都有了更深的理解。尤其是C語言的進步讓我深刻的感受到任何所學的知識都需要實踐,沒有實踐就無法真正理解這些知識以及掌握它們,使其成為自己的財富。在理論學習和上機實踐的各個環(huán)節(jié)中,通過自主學習和請教老師,我收獲了不少。當然也遇到不少的問題,也正是因為這些問題引發(fā)的思考給我?guī)Я耸斋@。從當初不喜歡上機寫程序到現(xiàn)在能主動寫程序,從當初拿著程序不只如何下手到現(xiàn)在知道如何分析問題,如何用專業(yè)知識解決實際問題的轉變,我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力,自己都有很大程度的提高。在這段時間里,我對for、while等的循環(huán)函數用

17、法更加熟悉,逐漸形成了較好的編程習慣。在老師的指導幫助下,同學們課余時間的討論中,這些問題都一一得到了解決。在程序的調試能力上,無形中得到了許多的提高。 在實際的上機操作過程中,不僅是讓我們了解數據結構的理論知識,更重要的是培養(yǎng)解決實際問題的能力,譬如迷宮的實現(xiàn),面對問題時我學會了應該如何解決。同時,也讓我對棧這一章節(jié)有更深的體會,以及用不同的方法解決問題相比較得出較好的解決方案。數據結構課程設計的主要目的是介紹一些常用的數據結構,闡明數據結構內在的邏輯關系,討論它們在計算機中的存儲表示,并結合各種數據結構,討論對他們實行的各種運算的實現(xiàn)算法。 此次迷宮問題的求解及演示課程設計你在實際操作中也

18、犯了很多錯誤,這些錯誤同時也讓我意外的收獲了很多。對我所學的數據結構知識理論也得到鞏固。通過實際的設計和分析,讓我學會了編程的基本步驟和方法,同時也開發(fā)了自己的邏輯思維能力,提高了解決問題的能力。在不斷的遇到問題,不斷的解決問題的過程中,培養(yǎng)的專業(yè)的思維是最重要的,也是這次課程設計所要達到的目的,我很慶幸我做到了。4.2 參考文獻【1】數據結構(C語言版)嚴蔚敏 吳偉民 編著 清華大學出版社【2】數據結構 (C語言版) 秦鋒 編著 清華大學出版社【3】C+程序設計杜茂康 編著 清華大學出版社43 附錄(程序清單):#include"stdlib.h"#includ

19、e"stdio.h"#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf("nn");printf("請按行輸入迷宮,0表示通路,1表示障礙:nn");for(i=0;i<m;i+)for(j=0;j<n;j+) scanf("%d",&maze

20、ij);void zidong_maze(int m,int n)int i,j;printf("n迷宮生成中nn");system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2;/由于rand()產生的隨機數是從0到RAND_MAX/RAND_MAX是定義在stdlib.h中的,其值至少為32767)/要產生從X到Y的數,只需要這樣寫:k=rand()%(Y-X+1)+X; void print_maze(int m,int n)int i,j;printf("n迷宮

21、生成結果如下:nn");printf("迷宮入口n");printf("");for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+) if(mazeij=0) printf(""); if(mazeij=1) printf("");printf("迷宮出口n");void result_maze(int m,int n)int i,j;printf("迷宮通路(用表示)如下所示:nt");for(i=0;

22、i<m;i+)printf("n"); for(j=0;j<n;j+) if(mazeij=0|mazeij=2) printf(""); if(mazeij=1) printf(""); if(mazeij=3) printf(""); void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit

23、(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)printf("n=n");printf("此迷宮無解nn");X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=de

24、queue();if(p.row=m-1)&&(p.col=n-1) break;if(p.col+1<n)&&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze);if(p.row+1<m)&&(mazep.row+1p.col=0) visit(p.row+1,p.col,maze);if(p.col-1>=0)&&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);if(p.row-1>=0)&&(maz

25、ep.row-1p.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);mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor;printf("(%d,%d)n",p.row,p.col);mazep.rowp.col=3;else printf(

26、"n=n"); printf("此迷宮無解!nn");X=0;return 0;void main()int i,m,n,cycle=0;while(cycle!=(-1) printf("*n"); printf("t*歡迎使用迷宮模擬程序*n"); printf(" 設計者: 安徽工程大學 n"); printf("*n"); printf(" 手動生成迷宮 請按:1n"); printf(" 自動生成迷宮 請按:2n"); pri

27、ntf(" 退出 請按:3nn"); printf("*n"); printf("n"); printf("請選擇你的操作:n"); scanf("%d",&i); switch(i) case 1:printf("n請輸入行數:");scanf("%d",&m); printf("n"); printf("請輸入列數:");scanf("%d",&n); while(m<=0|m>39)|(n<=0|n>39) printf("n抱歉,你輸入的行列數超出預設范圍(0-39,0-39),請重新輸入:nn"); printf("請輸入行數:");scanf("%d",&m); printf("n"); printf("請輸入列數:");scanf("%d"

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論