實訓報告-迷宮問題

C語言課程設計迷宮問題215-實訓報告實訓報告題目：迷宮問題院系：信息科技學院專業(yè)：計算機科學與技術姓名：黃經(jīng)偉學號：1151210213指導教師：梁海日期：2013年1月6日桂林電子科技大學信息科技學院目錄TOC\o"1-7"\h\z\u迷宮問題 -3-一、 設計需求 -3-二、 概要設計 -3-1、系統(tǒng)設計 -3-1．1總體設計 -3-1．2詳細設計 -4-1.2.1執(zhí)行流程 -4-3、系統(tǒng)實現(xiàn) -5-3．1編碼 -5-3.1.1類和結(jié)構(gòu)體的代碼 -5-3.1.2初始界面及行列數(shù)輸入的代碼 -5-3.1.3手動設計迷宮的代碼 -5-3.1.4自動設置迷宮的代碼 -6-3.1.5顯示迷宮的代碼 -7-3.1.6搜索通路的代碼 -7-3．2測試與調(diào)試 -9-3.2.1概述 -9-3.2.2程序測試 -10-4、系統(tǒng)維護 -14-5、歸納總結(jié) -14-5．1開發(fā)經(jīng)驗 -14-5．2實訓中遇到的問題及解決方法 -14-5．3感想和心得體會 -14-迷宮問題【摘要】隨著信息科技的發(fā)展，我們可以在計算機上設計一些系統(tǒng)來計算一些比較復雜的問題，例如：迷宮問題。迷宮問題指的是在一個迷宮內(nèi)尋找一條可以走出迷宮的路徑，我們可以通過計算機來的高速運算來快速求出路徑，這就是本次實訓的目的。【關鍵字】迷宮尋找路徑快速設計需求本次實訓我選擇了迷宮問題，迷宮問題是數(shù)據(jù)結(jié)構(gòu)課程的一個經(jīng)典問題。迷宮問題要求尋找一條從入口到出口的路徑。為了保證在任何位置上都能原路退回，顯然需要用一個后進先出的結(jié)構(gòu)來保存從入口到當前位置的路徑。因此，在求解迷宮的通路的算法中要應用“棧”的思想。對于棧的內(nèi)容在整個學期學習中我也有了一定的了解，所以選擇迷宮這一經(jīng)典的問題來作為實訓。概要設計1、系統(tǒng)設計1．1總體設計采用模塊化的程序設計方法，即將較大的任務按照一定的原則分為一個個較小的任務，然后分別設計各個小任務。需要注意的是劃分出來的模塊應該相對獨立但又相關，且容易理解?？梢杂媚K化層次結(jié)構(gòu)圖（即模塊圖）來分析其任務的劃分，一般從上到下進行，最上面一層是主模塊，下面各層是其上一層模塊的逐步細化描述。結(jié)束結(jié)束迷宮問題迷宮生成隨機生成手動生成輸出迷宮和迷宮路徑手動編輯迷宮輸出迷宮和迷宮路徑圖2.1功能結(jié)構(gòu)圖本迷宮問題設計如圖2.1所示，它由兩個部分組成：隨機生成：電腦隨機生成迷宮，可以快速畫出迷宮，并求出迷宮是否有通路。手動生成：通過自己手動來設計出迷宮，設計好后，系統(tǒng)通過計算，畫出迷宮并求出迷宮是否有通路。1．2詳細設計圖2.2執(zhí)行流程圖開始進到初始界面選擇迷宮的行數(shù)和列數(shù)選擇手動繪制或者電腦繪制圖2.2執(zhí)行流程圖開始進到初始界面選擇迷宮的行數(shù)和列數(shù)選擇手動繪制或者電腦繪制電腦繪制手動繪制編輯迷宮顯示迷宮，并輸出路徑結(jié)束本迷宮系統(tǒng)執(zhí)行主流程如圖2.2所示。它首先進入初始界面，然后用戶可以對功能進行選擇進行相應的操作，可以查看手動和自動生成迷宮，并求出路徑。3、系統(tǒng)實現(xiàn)3．1編碼3.1.1類和結(jié)構(gòu)體的代碼classCLabyrinth{ intX,Y;//迷宮的大小 intMap[MaxX][MaxY];//迷宮結(jié)構(gòu) PointResult[255];//存放正確的路徑(棧) inttop;//棧頂（指針） public: CLabyrinth();//得到迷宮尺寸 voidSetMap();//手工設置迷宮結(jié)構(gòu) voidAutoSetMap();//自動設置迷宮結(jié)構(gòu) voidShowMap();//顯示迷宮 voidSearchWay();//搜索通路 voidShowResult();//顯示通路 };3.1.2初始界面及行列數(shù)輸入的代碼CLabyrinth::CLabyrinth()//主界面 { cout<<"\t\t★歡迎進入迷宮★\t\t\n" <<"輸入迷宮的大小X*Y(最大為50*50):\n" <<"【不建議超過8列，因為繪出的地圖將不會顯示】\n"; intx,y; cout<<"請輸入行數(shù):"<<endl; cin>>x; cout<<"請輸入列數(shù):"<<endl; cin>>y; X=(x>48)?50:x+2;//多兩個單位是存放迷宮外壁 Y=(y>48)?50:y+2; top=-1; }3.1.3手動設計迷宮的代碼voidCLabyrinth::SetMap()//手工設置迷宮結(jié)構(gòu) { cout<<"\n依次輸入迷宮的結(jié)構(gòu)(1為有障礙，0為無障礙):\n" <<"前進方向有4個,分別是上、下、左、右\n"; for(inti=0,j,t;i<X;i++) for(j=0;j<Y;j++) { if(i==0||j==0||i==X-1||j==Y-1)//在迷宮周圍包上一圈1，防止搜索通路時越界 { Map[i][j]=1; continue; } cin>>t; Map[i][j]=(t!=0)?1:0; } }3.1.4自動設置迷宮的代碼voidCLabyrinth::AutoSetMap()//自動設置迷宮結(jié)構(gòu) { cout<<"\n前進方向有4個,分別是上、下、左、右、\n"; inta(39),b(72); for(inti=0,j;i<X;i++) { srand((unsigned)time(NULL)); for(j=0;j<Y;j++) { if(i==0||j==0||i==X-1||j==Y-1) { Map[i][j]=1; continue; } srand((rand()*(a++)+(b++))%65536);//隨機生成點 Map[i][j]=rand()%2; } } }3.1.5顯示迷宮的代碼voidCLabyrinth::ShowMap()//顯示迷宮 { if(Y>10)return; cout<<"\n迷宮示意圖為:\n"; for(inti=1,j;i<X-1;i++) { for(j=1;j<Y-1;j++) { if(i==1&&j==1)//cout<<"\n\t入口->"; cout<<"入口->"; elsecout<<"\t"; cout<<Map[i][j]; } if(i==X-2&&j==Y-1)cout<<"->出口"; cout<<endl; } }3.1.6搜索通路的代碼voidCLabyrinth::SearchWay()//搜索通路 { if(Map[X-2][Y-2])return;//如果出口不通直接返回 inti(X-2),j(Y-2);//出口的坐標從出口向入口找路 intpow;//檢查方向的計數(shù)器 do { if(!Map[i][j]) { Result[++top].x=i;//將要可通行的坐標入棧 Result[top].y=j; if(Result[top].x==1&&Result[top].y==1)break;//如果找到了入口退出循環(huán) i=i-1;//下一個要檢查的坐標左斜上方 j=j-1; pow=0;//計數(shù)器清零 } else { pow++; i=Result[top].x;//取出棧頂元素上一次的可通行坐標 j=Result[top].y; switch(pow) { case1:i--;break;//上 case2:j--;break;//左 case3:i--;j++; if(i==Result[top-1].x&&j==Result[top-1].y)//若是來路 pow++; elsebreak; case4:i++;j--; if(i==Result[top-1].x&&j==Result[top-1].y) pow++; elsebreak; default:Map[i][j]=1;i=Result[--top].x;j=Result[top].y;//將該坐標設為不可通行再回到上一次可通行坐標 } } }while(top!=-1);//棧不為空繼續(xù)循環(huán) } voidCLabyrinth::ShowResult()//顯示通路 { if(top==-1) { cout<<"\n此迷宮沒有通路!!!\n"; return; } cout<<"\n此迷宮的其中一條通路為:\n入口"; for(;top!=-1;top--) cout<<"->("<<Result[top].x<<','<<Result[top].y<<')'; cout<<"->出口\n"; }將各類的代碼相應的加到程序中，然后進行測試與調(diào)試。3．2測試與調(diào)試3.2.1概述一般情況下，為解決一個問題所編寫的程序代碼較長，可能包括幾百條甚至成千上萬條語句。在檢查并排除所有語法錯誤后，還會有不易發(fā)現(xiàn)的邏輯錯誤，因此要對程序進行認真仔細的測試與調(diào)試。測試是通過運行程序發(fā)現(xiàn)錯誤的過程，常見的錯誤有數(shù)據(jù)溢出、數(shù)組越界、進入死循環(huán)、語句順序顛倒、多加“；”或少加“{}”等等。調(diào)試則是確定測試中找到的錯誤性質(zhì)并改正錯誤的過程。測試與調(diào)試通常交替進行，即測試——調(diào)試——再測試——再調(diào)試。能檢查出尚未發(fā)現(xiàn)的、各種不同類型錯誤的測試才是成功的測試。測試程序需要測試用例，測試用例可用如下公式表示：測試用例＝測試數(shù)據(jù)＋預期結(jié)果。好的測試用例應該是用盡可能少的測試數(shù)據(jù)發(fā)現(xiàn)盡可能多的錯誤，即發(fā)現(xiàn)錯誤的概率要大。要選擇合適的測試數(shù)據(jù)，使系統(tǒng)在運行時盡量能執(zhí)行到每條語句，以測試各指令是否正確。還應分別測試輸入合法數(shù)據(jù)與非法數(shù)據(jù)時，程序的運行情況，。對于合法數(shù)據(jù)，還要考慮數(shù)據(jù)的一般性與特殊性，如求最大值的問題，應測試最大值在最前面、最后面、中間某一位置的情況。測試可按模塊測試、組裝測試和確認測試的步驟進行。（1）模塊測試就是分別對各模塊進行測試的過程。在編寫一個模塊后應立即對其進行測試，因為這時對模塊記憶深刻，而且單個模塊相對較小，所以容易構(gòu)造測試數(shù)據(jù)，能方便地檢查和改正錯誤。（2）組裝測試就是把所有模塊（應該是通過模塊測試的模塊）按預先制定的計劃逐步組裝和測試的過程。一般情況下，各模塊之間要相互傳遞數(shù)據(jù)和控制信息，因此組裝測試的主要任務是發(fā)現(xiàn)模塊接口中的錯誤。（3）確認測試是最后一個步驟，一般在將軟件交付用戶之前，應確認軟件是否確實滿足用戶的要求，通常使用接近實際的用例進行測試。測試程序時，用監(jiān)視窗口可以隨時查看變量或表達式的值，有時還可以將部分程序代碼用注釋符暫時括起來，縮短程序，以便壓縮出錯代碼的范圍。3.2.2程序測試運行程序進入界面后就說明程序沒有錯誤現(xiàn)在開始進行各種功能的測試！圖3.1進入迷宮系統(tǒng)輸入迷宮大小依次輸入迷宮的行數(shù)和列數(shù)圖3.2輸入迷宮大小選擇手工繪制迷宮圖3.3選擇手工繪制迷宮編輯迷宮編輯好迷宮按回車鍵后，系統(tǒng)就生成迷宮，并將迷宮路徑求出，打印出來。圖3.4手動編輯迷宮后再次編輯剛剛設計好大小的迷宮選擇y后，回到選擇手工或者電腦繪制迷宮的界面。圖3.5返回迷宮選擇繪制界面選擇電腦繪制迷宮因為迷宮沒用通路所以會輸出“此迷宮沒用通路的字樣”圖3.6選擇電腦繪制迷宮選擇任意值返回初始界面選擇一個任意的值，