




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告迷宮求解問題實(shí)驗(yàn)上機(jī)環(huán)境: DevC+二、程序設(shè)計(jì)相關(guān)信息(1)實(shí)驗(yàn)題目:迷宮求解問題問題描述:實(shí)驗(yàn)題3.5 改進(jìn)3.1.4節(jié)中的求解迷宮問題程序,要求輸出如圖3.14所示的迷宮的所有路徑,并求最短路徑長(zhǎng)度及最短路徑。0 1 2 3 4 5 0 1 2 3 4 5出口入口(2)實(shí)驗(yàn)項(xiàng)目組成:本項(xiàng)目由一個(gè)原程序mg.cpp及mg.exe文件組成。(3)實(shí)驗(yàn)項(xiàng)目的程序結(jié)構(gòu):main()struct結(jié)構(gòu)體mgpath()路徑函數(shù)函數(shù)調(diào)用關(guān)系圖:main()(4)實(shí)驗(yàn)項(xiàng)目包含的函數(shù)的功能描述:mgM+1N+1 /構(gòu)造迷宮二維數(shù)組,1表示墻不可走方塊,0表示通道
2、mgpath(int xi,int yi,int xe,int ye) /求解路徑為:(xi,yi)->(xe,ye)/采用順序棧存儲(chǔ),進(jìn)棧,回溯,退棧等(5)算法描述:求解迷宮從入口到出口的所有路徑,從入口出發(fā),順某一個(gè)方向向前試探,對(duì)于可走的方塊都進(jìn)棧,并將這個(gè)可走發(fā)方位保存,且top+1,然后試探下一個(gè)方塊,若下一個(gè)方塊能走通則繼續(xù),否則則回溯到前一個(gè)方塊,且top-1。為記錄所有的路徑調(diào)用Pathk=Stackk記錄,從次方塊向不同方向去試探,已經(jīng)走過的方塊則為不可走方塊。最后比較top值找到一條最短路徑并輸出。試探路徑過程的算法利用了“廣度優(yōu)先搜索遍歷”算法。流程圖:mg=0回
3、溯mg=1進(jìn)棧循環(huán)for下一個(gè)方塊變成前一個(gè)方塊下一個(gè)方塊值mgij前一個(gè)方塊值mg=0下一個(gè)方塊值mg=0輸出方位坐標(biāo)( , )入口結(jié)束(6)實(shí)驗(yàn)數(shù)據(jù):迷宮數(shù)組如下:int mgM+1N+1= 1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,0,0,1, 1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,1;實(shí)驗(yàn)結(jié)果:三、程序代碼:#include <stdio.h>#include <stdlib.h>#define M 6#define N 6#define Maxsize 100int mgM+1N+1= 1,1,1,1,1,1,
4、1,0,0,0,1,1, 1,0,1,0,0,1, 1,0,0,0,1,1, 1,1,0,0,0,1, 1,1,1,1,1,1;struct int i; int j; int di; StackMaxsize,PathMaxsize;int top=-1;int count=1;int min=Maxsize;int mgpath() int i,j,di,find,k; top+; Stacktop.i=1; Stacktop.j=1; Stacktop.di=-1; mg11=-1; printf("迷宮所有路徑如下:n"); while(top>-1) i=S
5、tacktop.i;j=Stacktop.j;di=Stacktop.di; if(i=M-2&&j=N-2) printf("%4d:",count+); for(k=0;k<=top;k+) printf("(%d,%d)",Stackk.i,Stackk.j); if(k+1)%5=0) printf("n "); printf("n"); if(top+1<min) for(k=0;k<=top;k+) Pathk=Stackk; min=top+1; mgStacktop
6、.iStacktop.j=0; top-; i=Stacktop.i;j=Stacktop.j;di=Stacktop.di; find=0; while(di<4&&find=0) di+; switch(di) case 0:i=Stacktop.i-1;j=Stacktop.j;break; case 1:i=Stacktop.i;j=Stacktop.j+1;break; case 2:i=Stacktop.i+1;j=Stacktop.j;break; case 3:i=Stacktop.i;j=Stacktop.j-1;break; if(mgij=0)find=1; if(find=1) Stacktop.di=di; top+; Stacktop.i=i; Stacktop.j=j; Stacktop.di=-1; mgij=-1; else mgStacktop.iStacktop.j=0; top-; printf("n"); printf("最短路徑如下:n"); printf("路徑最短長(zhǎng)度:%dn",min); printf("最短路徑路徑:n"); for(k=0;k<min;k+) printf("(%d,%d)&quo
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 邏輯協(xié)議書模板
- 合伙開公司協(xié)議書
- 人事代理與招聘服務(wù)協(xié)議
- 烽火通信協(xié)議書
- 進(jìn)出口涉外合同協(xié)議
- 專業(yè)藝術(shù)品采購(gòu)與存儲(chǔ)服務(wù)協(xié)議
- 灣區(qū)投資協(xié)議書
- 透明膜質(zhì)保合同協(xié)議
- 送水工勞務(wù)合同協(xié)議
- 車輛轉(zhuǎn)入?yún)f(xié)議書范本
- 土地合同轉(zhuǎn)讓三方協(xié)議書
- 聚焦財(cái)稅場(chǎng)景的AIBM生態(tài)服務(wù)行業(yè)白皮書
- 2024年綿陽(yáng)市商業(yè)銀行招聘考試真題
- 入隊(duì)前教育測(cè)試題及答案
- 2025年上半年廣東東莞市委辦公室招聘勞務(wù)派遣人員重點(diǎn)基礎(chǔ)提升(共500題)附帶答案詳解
- GB/T 35267.4-2025清洗消毒器第4部分:內(nèi)鏡清洗消毒器
- 規(guī)范佩戴紅領(lǐng)巾
- TCAWAORG 032-2024 家庭醫(yī)生遠(yuǎn)程與互聯(lián)網(wǎng)健康服務(wù)規(guī)范
- 電磁懸浮手術(shù)床技術(shù)-深度研究
- 2025年春季學(xué)期 形勢(shì)與政策講稿第五講-從教育大國(guó)邁向教育強(qiáng)國(guó)
- 大型活動(dòng)安保人員配置措施
評(píng)論
0/150
提交評(píng)論