數(shù)據(jù)結(jié)構(gòu)實驗二 迷宮遞歸

北京郵電大學(xué)信息與通信工程學(xué)院第1頁北京郵電大學(xué)電信工程學(xué)院第1頁數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗二——棧與隊列學(xué)生姓名：大學(xué)霸班級：xxxxxxxxxx班內(nèi)序號：19學(xué)號：xxxxxxxxxx日期：2012年11月17日1．實驗要求a.實驗?zāi)康耐ㄟ^選擇下面五個題目之一進行實現(xiàn)，掌握如下內(nèi)容：進一步掌握指針、模板類、異常處理的使用掌握棧的操作的實現(xiàn)方法掌握隊列的操作的實現(xiàn)方法學(xué)習(xí)使用棧解決實際問題的能力學(xué)習(xí)使用隊列解決實際問題的能力b.實驗內(nèi)容利用棧結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。2.程序分析本程序的功能是用遞歸的方法找到所有走出迷宮的路徑，并將路徑輸出，同時在這些路徑中找出最優(yōu)解。首先，讀取后臺預(yù)定的迷宮TXT地圖（實際上是10×10的數(shù)字矩陣，0代表空地，3代表墻，可以很直觀地修改）,把數(shù)據(jù)賦給arr二維數(shù)組，內(nèi)容不發(fā)生改變。然后，將這個迷宮地圖輸出，判斷迷宮是否有完整通路，如果能走出便進行下一步，如果不能，提示錯誤迷宮有完整通路，可使用回溯的方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則此步進棧，繼續(xù)往前進；否則沿著原路返回，換另一個方向探索，直至出口位置，求得一條通路……重復(fù)上述步驟，找出所有可能的路徑，統(tǒng)計每一步在程序的最后，將每一種路徑的長度進行比較，找出最短的一個或多個路徑2.1存儲結(jié)構(gòu)定義結(jié)點的結(jié)構(gòu)體structPoint{ intX; intY;};進行前進后退等操作時即是對X、Y值的改變，同時也代表二維數(shù)組元素的行數(shù)、列數(shù)迷宮圖的數(shù)據(jù)用二維數(shù)組來存儲，用0表示空地可以前進，用3表示墻走不通arr1arr2…………arrn-1arrn當(dāng)執(zhí)行尋找路徑時，從一個節(jié)點到下一個結(jié)點系統(tǒng)會自動調(diào)用棧2.2關(guān)鍵算法分析關(guān)鍵算法1.找出迷宮走法回溯法，利用遞歸窮舉可能解每走一步：[1]如果當(dāng)前位置=出口，把完整路徑輸出，結(jié)束[2]否則：[2.1]假設(shè)當(dāng)前位置為路徑；[2.2]如果東面未走過：向東走一步[2.3]如果南面未走過：向南走一步[2.4]如果西面未走過：向西走一步[2.5]如果北面未走過：向北走一步[3]設(shè)置當(dāng)前位置走不通，回溯，并將此位置標(biāo)記2.讀取迷宮圖[1]進行循環(huán)體[1.1]輸入要讀取的迷宮圖maze[1.2]如果存在跳出循環(huán)，下一環(huán)節(jié)[1.3]如果不存在顯示錯誤輸入的迷宮圖有誤，重新上面的步驟[2]定義文件流對象fin[3]根據(jù)maze選擇打開不同的迷宮圖TXT文件，建立關(guān)聯(lián)[4]判斷文件是否能打開[4.1]如果能打開，逐行提取數(shù)字，賦給二維數(shù)組arr，關(guān)閉文件[4.2]如果不能打開，提示錯誤3.打印還未走過的迷宮圖[1]從第一行到第十行循環(huán)[2]從第一列到第十列循環(huán)[2.1]此節(jié)點如果為墻，打印“■”[2.2]其他為空地，打印空格4.判斷是否能走通[1]從最后一行倒序循環(huán)[1.1]如果找到不是墻的元素，返回能走通[2]從最后一列倒序循環(huán)[2.1]如果找到不是墻的元素，返回能走通[3]返回不能走通5.打印走通后的迷宮圖[1]將路徑計數(shù)器k置0[2]從第一行到第十行循環(huán)[2.1]從第一列到第十列循環(huán)[2.1.1]此節(jié)點如果為墻，打印“■”[2.1.2]此節(jié)點如果為路徑，打印“*”，k加1[2.1.3]此節(jié)點如果未走過，打印空格[3]將k存到向量PathLength（專門比較路徑長度）打印一共走了k步6.找出最優(yōu)解[1]定義最短路徑數(shù)組ShortestPath假設(shè)最短路徑長度ShortestLength為向量PathLength的第一個元素值[2]在向量PathLength里進行循環(huán)[2.1]如果PathLength里某個元素值小于最短路徑長度ShortestLength[2.2]將最小路徑長度ShortestLength等于這個元素值[3]在向量PathLength里進行循環(huán)[3.1]如果PathLength里某個元素值等于最短路徑長度ShortestLength[3.2]將這個元素的下標(biāo)存入最短路徑數(shù)組ShortestPath[4]打印最短路徑數(shù)組ShortestPath里的所有元素，即為最優(yōu)解[5]打印最短路徑長度ShortestLength代碼詳盡分析1.找出迷宮走法每走一步：[1]如果當(dāng)前位置=出口，把完整路徑輸出，結(jié)束[2]否則：[2.1]假設(shè)當(dāng)前位置為路徑；[2.2]如果東面未走過：向東走一步[2.3]如果南面未走過：向南走一步[2.4]如果西面未走過：向西走一步[2.5]如果北面未走過：向北走一步[3]設(shè)置當(dāng)前位置走不通，回溯，并將此位置標(biāo)記C++實現(xiàn)voidnext(intarr[][10],Pointcur){[1] if(cur.X==9||cur.Y==9)//如果走出迷宮 {cout<<"第"<<++Path<<"種路徑：\n";PrintPath(arr); arr[cur.X][cur.Y]=0;} //打印完整路徑[2] else {[2.1] arr[cur.X][cur.Y]=2;//假設(shè)當(dāng)前位置為路徑[2.2] if(arr[cur.X+1][cur.Y]==0) { Pointt=cur; t.X++; next(arr,t);//向右 }[2.3] if(arr[cur.X][cur.Y+1]==0) { Pointt=cur; t.Y++; next(arr,t);//向下 }[2.4] if(arr[cur.X-1][cur.Y]==0) { Pointt=cur; t.X--; next(arr,t);//向左 }[2.5] if(arr[cur.X][cur.Y-1]==0) { Pointt=cur; t.Y--; next(arr,t);//向上 }[3] arr[cur.X][cur.Y]=1;//標(biāo)記此處走不通 } arr[cur.X][cur.Y]=0;}2.讀取迷宮圖[1]進行循環(huán)體[1.1]輸入要讀取的迷宮圖maze[1.2]如果存在跳出循環(huán)，下一環(huán)節(jié)[1.3]如果不存在顯示錯誤輸入的迷宮圖有誤，重新上面的步驟[2]定義文件流對象fin[3]根據(jù)maze選擇打開不同的迷宮圖TXT文件，建立關(guān)聯(lián)[4]判斷文件是否能打開[4.1]如果能打開，逐行提取數(shù)字，賦給二維數(shù)組arr，關(guān)閉文件[4.2]如果不能打開，提示錯誤C++實現(xiàn)[1]do{ cout<<"請選擇迷宮(1~5):";[1.1] cin>>maze;//輸入要讀取的迷宮圖maze[1.2] if(maze>=1&&maze<=5)break;//如果存在跳出循環(huán)，下一環(huán)節(jié)[1.3] elsecout<<"無此迷宮！"<<endl<<endl;}//如果不存在顯示錯誤 while(1);[2] ifstreamfin;//定義文件流對象fin[3] switch(maze)//根據(jù)maze選擇打開不同的迷宮圖TXT文件，建立關(guān)聯(lián) { case1: fin.open("maze1.txt"); break; case2: fin.open("maze2.txt"); break; case3: fin.open("maze3.txt"); break; case4: fin.open("maze4.txt"); break; case5: fin.open("maze5.txt"); break; default: break; }//輸出迷宮[4] if(fin.is_open())//判斷文件是否能打開 { cout<<"迷宮載入中"<<endl;[4.1] for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { fin>>arr[i][j];//逐行提取數(shù)字，賦給二維數(shù)組arr } } fin.close(); PrintMaze(arr);}else[4.2]cout<<"迷宮不能打開！"<<endl;//提示錯誤3.打印還未走過的迷宮圖[1]從第一行到第十行循環(huán)[2]從第一列到第十列循環(huán)[2.1]此節(jié)點如果為墻，打印“■”[2.2]其他為空地，打印空格C++實現(xiàn)voidPrintMaze(intarr[][10]){[1] for(inti=0;i<10;i++) {[2] for(intj=0;j<10;j++) {[2.1] if(arr[i][j]==3)cout<<"■";//此節(jié)點如果為墻，打印“■”[2.2] elsecout<<"";//其他為空地，打印空格 } cout<<endl; } cout<<endl;}4.判斷是否能走通[1]從最后一行倒序循環(huán)[1.1]如果找到不是墻的元素，返回能走通[2]從最后一列倒序循環(huán)[2.1]如果找到不是墻的元素，返回能走通[3]返回不能走通C++實現(xiàn)boolIsThrough(intarr[][10]){[1] for(inti=8;i>=1;i--) {[1.1] if(arr[9][i]==0)returntrue;//如果找到不是墻的元素，返回能走通 }[2] for(inti=8;i>=1;i--) {[2.1] if(arr[i][9]==0)returntrue;//如果找到不是墻的元素，返回能走通 }[3] returnfalse;}5.打印走通后的迷宮圖[1]將路徑計數(shù)器k置0[2]從第一行到第十行循環(huán)[2.1]從第一列到第十列循環(huán)[2.1.1]此節(jié)點如果為墻，打印“■”[2.1.2]此節(jié)點如果為路徑，打印“*”，k加1[2.1.3]此節(jié)點如果未走過，打印空格[3]將k存到向量PathLength（專門比較路徑長度）[4]打印“一共走了k步”C++實現(xiàn)voidPrintPath(intarr[][10]){[1] intk=0;[2] for(inti=0;i<10;i++)//行循環(huán) {[2.1] for(intj=0;j<10;j++)//列循環(huán) {[2.1.1] if(arr[i][j]==3)cout<<"■";//此節(jié)點如果為墻，打印“■”[2.1.2] elseif(arr[i][j]==2){cout<<"*";k++;}//此節(jié)點如果為路徑，打印“*”，k加1[2.1.3] elsecout<<"";//此節(jié)點如果未走過，打印空格 } cout<<endl; }[3] PathLength.push_back(k);//插入路徑長度向量[4] cout<<"一共走了"<<k<<"步";//打印步數(shù) cout<<endl;}6.找出最優(yōu)解[1]定義最短路徑數(shù)組ShortestPath假設(shè)最短路徑長度ShortestLength為向量PathLength的第一個元素值[2]在向量PathLength里進行循環(huán)[2.1]如果PathLength里某個元素值小于最短路徑長度ShortestLength[2.1.1]將最小路徑長度ShortestLength等于這個元素值[3]在向量PathLength里進行循環(huán)[3.1]如果PathLength里某個元素值等于最短路徑長度ShortestLength[3.1.1]將這個元素的下標(biāo)存入最短路徑數(shù)組ShortestPath[4]打印最短路徑數(shù)組ShortestPath里的所有元素，即為最優(yōu)解[5]打印最短路徑長度ShortestLengthC++實現(xiàn)voidPrintShortest(){[1] intShortestPath[50]={0}; intShortestLength=PathLength[0]; ShortestPath[0]=1;[2] for(unsignedi=1;i<PathLength.size();i++) {[2.1] if(PathLength[i]<ShortestLength) {[2.1.1] ShortestLength=PathLength[i]; } } intk=0;[3] for(unsignedi=0;i<PathLength.size();i++) {[3.1] if(PathLength[i]==ShortestLength)[3.1.1]ShortestPath[k++]=i+1; }cout<<"最短路徑為：";[4] for(inti=0;i<50;i++) if(ShortestPath[i])cout<<ShortestPath[i]<<""; cout<<endl;[5] cout<<"共走了"<<ShortestLength<<"步"<<endl; }2.3其他我在調(diào)試程序時，已經(jīng)預(yù)寫了幾個迷宮地圖文件maze1.txt、maze2.txt……保存在工程文件夾下。類似的，其他開發(fā)者可以編寫新的地圖，加以改進、創(chuàng)新3.程序運行結(jié)果3.1測試主函數(shù)流程圖開始開始用戶輸入迷宮是否存在打開迷宮圖迷宮是否能打開打印迷宮圖迷宮是否能走通