




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、課程設(shè)計任務(wù)書專業(yè) 計算機科學與技術(shù)班級姓名設(shè)計起止日期設(shè)計題目:迷宮問題的操作設(shè)計任務(wù)(主要技術(shù)參數(shù)):學會運用數(shù)據(jù)結(jié)構(gòu)建立迷宮問題,編造出迷宮并設(shè)計出走出迷宮的方法硬件環(huán)境:處理器:英特爾 第三代酷睿i3-3110M 2.40GHz雙核內(nèi)存:4GB(三星 DDR3 1333MHz)主硬盤:希捷 ST500LM012 HN-M500MBB (500GB/5400 轉(zhuǎn)/分)顯示器:三星 SEC3649(14英寸)軟件環(huán)境:操作系統(tǒng): Windows 8 64位(DirectX 11)開發(fā)環(huán)境:VC+6.0指導(dǎo)教師評語:成績: 簽字:1、課程設(shè)計目的為了配合數(shù)據(jù)結(jié)構(gòu)課程的開設(shè),通過設(shè)計一完整的程
2、序,掌握數(shù)據(jù) 結(jié)構(gòu)的應(yīng)用、算法的編寫、類C語言的算法轉(zhuǎn)換成C程序并用TC上機調(diào)試的基本 方法特進行題目為兩個鏈表合并的課程設(shè)計。 通過此次課程設(shè)計充分鍛煉有關(guān)數(shù) 據(jù)結(jié)構(gòu)中鏈表的創(chuàng)建、合并等方法以及怎樣通過轉(zhuǎn)化成 C語言在微機上運行實現(xiàn) 等其他方面的能力。2.課程設(shè)計的內(nèi)容與要求2.1 問題描述:迷宮問題是取自心理學的一個古典實驗。 在該實驗中,把一只老鼠從一個無頂大 盒子的門放入,在盒子中設(shè)置了許多墻,對行進方向形成了多處阻擋。盒子僅有 一個出口,在出口處放置一塊奶酪,吸引老鼠在迷宮中尋找道路以到達出口。 對 同一只老鼠重復(fù)進行上述實驗,一直到老鼠從入口走到出口,而不走錯一步。老 鼠經(jīng)過多次試
3、驗最終學會走通迷宮的路線。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的矩 形迷宮如下圖A所示,求出一條從入口到出口的通路,或得出沒有通路的結(jié)論。圖A2.2 設(shè)計要求:要求設(shè)計程序輸出如下:(1)建立一個大小為mxn的任意迷宮(迷宮數(shù)據(jù)可由用戶輸入或由程序自動生 成),并在屏幕上顯示出來;(2)找出一條通路的二元組(i,j)數(shù)據(jù)序列,(i,j)表示通路上某一點的坐標:(3)用一種標志(如數(shù)字8)在迷宮中標出該條通路;(4)在屏幕上輸出迷宮和通路;(5)上述功能可用菜單選擇。3.課程設(shè)計總體方案及分析3.1 問題分析:1 .迷宮的建立:迷宮中存在通路和障礙,為了方便迷宮的創(chuàng)建,可用0表示通路,用1表示障礙, 這
4、樣迷宮就可以用0、1矩陣來描述,2 .迷宮的存儲:迷宮是一個矩形區(qū)域,可以使用二維數(shù)組表示迷宮,這樣迷宮的每一個位置都可 以用其行列號來唯一指定,但是二維數(shù)組不能動態(tài)定義其大小,我們可以考慮先 定義一個較大的二維數(shù)組 mazeM+2N+2,然后用它的前m行n列來存放元素, 即可得到一個mxn的二維數(shù)組,這樣(0,0)表示迷宮入口位置,(m-1,n-1)表示迷 宮出口位置。注:其中M, N分別表示迷宮最大行、列數(shù),本程序 M、N的缺省值為39、39, 當然,用戶也可根據(jù)需要,調(diào)整其大小。3 .迷宮路徑的搜索:首先從迷宮的入口開始,如果該位置就是迷宮出口,則已經(jīng)找到了一條路徑,搜 索工作結(jié)束。否則
5、搜索其上、下、左、右位置是否是障礙,若不是障礙,就移動 到該位置,然后再從該位置開始搜索通往出口的路徑; 若是障礙就選擇另一個相 鄰的位置,并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn),則將已搜索過的位置標 記為2,同時保留搜索痕跡,在考慮進入下一個位置搜索之前,將當前位置保存 在一個隊列中,如果所有相鄰的非障礙位置均被搜索過,且未找到通往出口的路徑,則表明不存在從入口到出口的路徑。 這實現(xiàn)的是廣度優(yōu)先遍歷的算法, 如果 找到路徑,則為最短路徑。以矩陣0 010 1為例,來示范一下首先,將位置(0,0)(序號0)放入隊列中,其前節(jié)點為空,從它開始搜索,其 標記變?yōu)?,由于其只有一個非障礙位置,所以接
6、下來移動到(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é)點的位置,逆 序就可以找到其從出口到入口的通路。如下表所示:0910(0,0)(0,1)(3,4)-101212345678(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)2 3 4 56 7 9由此可以看出,
7、得到最短路徑:(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)搜索算法流程圖如下所示1.構(gòu)建一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣自動或手動生成迷宮,即為二維數(shù)組 mazeM+2N+2賦值構(gòu)建一個隊列用于存儲迷宮路徑建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況實現(xiàn)搜索算法屏幕上顯示操作菜單2.本程序包含10個函數(shù):(1)主函數(shù)main()(2)手動生成迷宮函數(shù) shoudong_maze()(3)自動生成迷宮函數(shù)zidong_maze()將迷宮打印成圖形print_maze()(5)打印迷宮路徑(若存在路徑)result_ma
8、ze()(6)入隊 enqueue。出隊dequeue。(8)判斷隊列是否為空is_empty()(9)訪問節(jié)點visit()(10)搜索迷宮路徑 mgpath()3.3詳細設(shè)計實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法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)輸入m
9、azeij的值(2)自動生成迷宮void zidong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n)mazeij=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)打印迷宮圖形void print_maze(int m,int n)用i,j循環(huán)變量,將mazeij輸出 口、打印迷宮路徑void result_maze(int m,int n)用i,j循環(huán)變量
10、,將mazeij輸出 口、(5)搜索迷宮路徑迷宮中隊列入隊操作void enqueue(struct point p)將p放入隊尾,tail+迷宮中隊列出隊操作struct point dequeue(struct 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é)點以被訪問過;調(diào)
11、用enqueue(visit_point)將該節(jié)點入隊路徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點為struct point p=0,0,-1,從maze00開始訪問。如果入口處即 為障礙,則此迷宮無解,返回 0 ,程序結(jié)束。否則訪問入口節(jié)點,將入口節(jié)點 標記為訪問過mazep.rowp.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
12、H mazep.rowp.col+1=0,說明未到迷宮右邊界,且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點入隊標記已訪問如果p.row+1<m且mazep.row+1p.col=0,說明未到迷宮下邊界,且其下方有通路,則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,說明未到迷宮
13、上邊界,且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點入隊標記已訪問訪問到出口(找到路徑)即p.row=m-1且p.col=n-1,則逆序?qū)⒙窂綐擞洖?3即mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3;最后將路徑圖形打印出來。3 .菜單選擇while(cycle!=(-1)手動生成迷宮請按:1 自動生成迷宮 請按:2退出請按:3scanf("%d",&i);switch(i) case 1:請輸入行列數(shù)(如果超出預(yù)設(shè)范圍
14、則提示重新輸入)shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0) result_maze(m,n);case 2 :請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入)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.4 調(diào)試分析在調(diào)試過程中,首先使用的是棧進行存儲,但是產(chǎn)生的路徑是多條或 不是最短路徑,所以通過算法比較,改用此算法3.5 測試結(jié)果1 .手
15、動輸入迷宮“ 一 _ ,請輸入行數(shù):44請輸入列數(shù):4抱歉,你輸入的行列數(shù)超出預(yù)設(shè)范圍(。-39.539),清里新輸入:請輸入行數(shù):4請輸入列數(shù):4 請按行輸入迷宮,。表示通路, 1表示障礙:0 Q G 1e 1 e 1 e e i 1e e e oB宮生成結(jié)果如下:b宮入口I一迷宮出口 迷宮路徑為:(3.3)(3.2)(3,1)(2.1)(2.G)(1.0)(0.0)法宮通路(用表示)如下所示:Press Enter Contiue!搜狗拼音輸入法全:口2自動生成迷宮:手動生成迷宮 自動生成迷宮 退出 L: 6 口分迷宮出口歡迎進入迷宮求解系統(tǒng)設(shè)計者:付吉龍Entsr ContiuefD:V
16、CMicrosoft Visual StudioIS/DebugNUM2.exe'!* » 按按按 請清清4 .設(shè)計體會通過本次的課程設(shè)計,使我學會了如何去組織代碼量較大大程序。 與此同時, 也使我學會了一些對代碼量較大的的程序進行編寫、 連接、編譯運行、以及調(diào)試 和修改的技巧這次的課程設(shè)計涉及到編程語言和數(shù)據(jù)結(jié)構(gòu)的知識,要求和平時的實比相對 較高。從本次的課程設(shè)計可以檢驗我們對 C語言和數(shù)據(jù)結(jié)構(gòu)的掌握情況,同時也 檢驗了我們對所學習過的知識的靈活運用情況。 在創(chuàng)新性方面,這次的課程設(shè)計 雖然完成了課程設(shè)計的任務(wù),但是缺乏創(chuàng)造性的設(shè)計思想,在以后的學習過程中 還得繼續(xù)努力。5
17、 .參考文獻1 .嚴蔚敏編著.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學出版社,20022 .朱戰(zhàn)立.編著.數(shù)據(jù)結(jié)構(gòu)一一使用C語言.西安交通大學出版社,20043 .朱戰(zhàn)立,張選平編著.數(shù)據(jù)機構(gòu)學習指導(dǎo)和典型題解.西安交通大學出版社,20024 .蘇小紅,孫志崗等編著.C語言大學實用教程(第2版).電子工業(yè)出版社,20085 .梁肇新編著.編程高手箴言.電子工業(yè)出版社,2003附件:#include"stdlib.h"#include"stdio.h"#define N 39#define M 39int X;int mazeN+2M+2;struct pointi
18、nt 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”,&mazeij);void zidong_maze(int m,int n)int i,j;printf("n 迷宮生成中nn");system("
19、pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=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;void print_maze(int m,int n)int i,j;printf("n迷宮生成結(jié)果如下:nn");printf("迷宮入口 n");printf(" J ");for(i=0;i<m;
20、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;i<m;i+)printf("n");for(j=0;j<n;j+)if(mazeij=0|mazeij=2) printf
21、(" ”);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(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enque
22、ue(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=dequeue();if(p.row=m-1)&&(p.col=n-1) break;if(p.col+1<n)&&(mazep.rowp.
23、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)&&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&&p.col=n-1)printf("
24、;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;elseprintf("n=n");printf(“此迷宮無解!nn");X=0;return 0;void main()int i,m,n,cycle=0;while(cycle
25、!=(-1)printf(*n");printf(歡迎進入迷宮求解系統(tǒng)printf(”*n");printf(printf(printf( 手動生成迷宮 請按: 自動生成迷宮 請按: 退出請按:n");1n");2'n");3nn");printf(”*”*n");printf("n");printf("請選擇你的操作:n");scanf("%d",&i);switch(i)case 1:printf("n 請輸入行數(shù):");sc
26、anf("%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),請重新輸入:nn");printf(“請輸入行數(shù):");scanf("%d",&m);printf("n");printf(“請輸入列數(shù):");scanf("%d",&n);shoudong_m
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年軟件開發(fā)技術(shù)趨勢試題及答案
- 加油站電路火災(zāi)應(yīng)急預(yù)案(3篇)
- 行政法學的實踐案例分析方法試題及答案
- 2025年軟考設(shè)計師備考試題及答案全解
- 2025年軟考設(shè)計師考試命題動態(tài)觀察試題及答案
- 行政法學考試沖刺試題及答案
- 2025年VB編程實戰(zhàn)試題及答案解析
- 跨平臺開發(fā)考試試題及答案分享
- 2025年軟考考試技巧與試題及答案分享
- 2025年軟考考生成功經(jīng)驗與試題及答案
- 機場運營效率提升策略與創(chuàng)新模式-洞察闡釋
- 安徽省1號卷A10聯(lián)盟2025屆高三5月最后一卷生物試題及答案
- 網(wǎng)絡(luò)安全等級保護備案表(2025版)
- 共情研究的歷史發(fā)展及其當前狀況分析
- 《綠色建筑評價》課件 - 邁向可持續(xù)建筑的未來
- 2025年湖南九年級物理(BEST湘西州聯(lián)考)(含答案)
- 山東省臨沂市2025年普通高等學校招生全國統(tǒng)一考試(模擬)語文及答案(臨沂二模)
- 濟南幼兒師范高等??茖W校招聘真題2024
- 以患者為中心的醫(yī)教融合模式在提升醫(yī)療服務(wù)質(zhì)量中的應(yīng)用研究
- 制氫技術(shù)與工藝課件:液氫
- (2025)全國小學生“學憲法、講憲法”活動知識競賽題庫及答案
評論
0/150
提交評論