C 數(shù)據(jù)結(jié)構(gòu)之迷宮求解

2009級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：用棧和隊列實現(xiàn)迷宮問題求解學(xué)生姓名：桂柯易班級：2009211120班內(nèi)序號：07學(xué)號：09210580日期：2010年11月19日1.實驗要求【實驗?zāi)康摹窟M一步掌握指針、模板類、異常處理的使用；掌握棧的操作的實現(xiàn)方法；掌握隊列的操作的實現(xiàn)方法；培養(yǎng)使用棧解決實際問題的能力；培養(yǎng)使用隊列解決實際問題的能力。【實驗內(nèi)容】利用棧結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設(shè)置很多障礙物，對前進方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。2.程序分析2.1存儲結(jié)構(gòu)存儲結(jié)構(gòu)：隊列2.2關(guān)鍵算法分析【設(shè)計思想】可以采用回溯法實現(xiàn)該問題的求解。回溯法是一種不斷試探及時糾正錯誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達，則到達新點，否則試探下一方向；若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探，直到所有可能的通路都搜索到，或找到一條通路，或無路可走又返回到入口點。在求解過程中，為了保證在任何位置上都能沿原路返回，需要一個后進先出的棧來保存從入口到當(dāng)前位置的路徑?？紤]到使用棧的實現(xiàn)復(fù)雜度，本次實驗采用標(biāo)記法標(biāo)記已經(jīng)走過的地方，所以就在求解迷宮通路方面可能不夠全面，有時不能得到正確的解法。可以將迷宮定義成一個二維數(shù)組，則每個點有8個試探方向，如當(dāng)前點的坐標(biāo)是（x,y），與其相鄰的8個點的坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，規(guī)定試探順序為順時針方向，將這8個方向的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move[8]中，在move數(shù)組中，每個元素由兩個域組成：x表示橫坐標(biāo)增量，y表示縱坐標(biāo)增量。這樣會很方便地求出從某點（x,y）按某一方向v（0≤v≤7）到達新點（i,j）的坐標(biāo)：i=x+move[v].x；j=y+move[v].y?！緜未a】棧初始化；將入口點坐標(biāo)（x,y）及該點的方向d（設(shè)為-1）入棧；當(dāng)棧不空時循環(huán)執(zhí)行下述操作：3.1（x,y,d）<==棧頂元素出棧；3.2求出下一個要試探的方向d++;3.3沿順時針試探每一個方向，執(zhí)行下述操作：3.3.1如果方向d可走，則3.3.1.1將（x,y,d）入棧；3.3.1.2求新點坐標(biāo)（i,j）；3.3.1.3將新點（i,j）切換為當(dāng)前點（x,y）；3.3.1.4若（x,y）是終點，則算法結(jié)束；否則，重置d=0；3.3.2否則，試探下一個方向d++；【復(fù)雜度】（1）手動生成迷宮算法：voidhand_maze(intm,intn){ inti,j; cout<<endl;cout<<"請按行輸入迷宮，0表示通路，1表示障礙:"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++) { cin>>maze[i][j]; }}該算法的時間復(fù)雜度為T(N)=O(N2)（2）自動生成迷宮算法：voidautomatic_maze(intm,intn)//自動生成迷宮{ inti,j; cout<<"\n迷宮生成中……\n\n"; system("pause"); for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2;//隨機生成0、1maze[0][0]=0;maze[i-1][j-1]=0;//首尾置為0，保證迷宮基本功能的實現(xiàn)}時間復(fù)雜性、度上，該算法同于手動生成迷宮算法，為T（N）=O（N2）2.3其他程序源代碼：#include<stdlib.h>//rand()函數(shù)#include<stdio.h>#include<iostream>usingnamespacestd;#defineN100//定義迷宮數(shù)組的上線,為全局變量#defineM100intX;//標(biāo)記迷宮是否有解的變量intmaze[N+2][M+2];inthead=NULL,tail=NULL;//隊列的頭尾指針，初始值設(shè)為NULLstructpoint//定義迷宮的隊列結(jié)構(gòu)體，包含列，行，序號{introw,col,predecessor;}queue[1000];voidstudent_maze()//函數(shù)生成書本后面的迷宮{ cout<<"下面將要為您生成書本課后的迷宮，請稍候"<<endl; system("pause");maze[0][0]=0;maze[0][1]=1;maze[0][2]=1;maze[0][3]=1;maze[0][4]=1;maze[0][5]=1;maze[0][6]=1;maze[0][7]=1;maze[0][8]=1;maze[0][9]=1;maze[1][0]=1;maze[1][1]=0;maze[1][2]=0;maze[1][3]=1;maze[1][4]=0;maze[1][5]=0;maze[1][6]=0;maze[1][7]=1;maze[1][8]=0;maze[1][9]=1;maze[2][0]=1;maze[2][1]=0;maze[2][2]=0;maze[2][3]=1;maze[2][4]=0;maze[2][5]=0;maze[2][6]=0;maze[2][7]=1;maze[2][8]=0;maze[2][9]=1;maze[3][0]=1;maze[3][1]=0;maze[3][2]=0;maze[3][3]=0;maze[3][4]=0;maze[3][5]=1;maze[3][6]=1;maze[3][7]=0;maze[3][8]=0;maze[3][9]=1; maze[4][0]=1;maze[4][1]=0;maze[4][2]=1;maze[4][3]=1;maze[4][4]=1;maze[4][5]=0;maze[4][6]=0;maze[4][7]=0;maze[4][8]=0;maze[4][9]=1; maze[5][0]=1;maze[5][1]=0;maze[5][2]=0;maze[5][3]=0;maze[5][4]=1;maze[5][5]=0;maze[5][6]=0;maze[5][7]=0;maze[5][8]=0;maze[5][9]=1; maze[6][0]=1;maze[6][1]=0;maze[6][2]=1;maze[6][3]=0;maze[6][4]=0;maze[6][5]=0;maze[6][6]=1;maze[6][7]=0;maze[6][8]=0;maze[6][9]=1;maze[7][0]=1;maze[7][1]=0;maze[7][2]=1;maze[7][3]=1;maze[7][4]=1;maze[7][5]=0;maze[7][6]=1;maze[7][7]=1;maze[7][8]=0;maze[7][9]=1; maze[8][0]=1;maze[8][1]=0;maze[8][2]=0;maze[8][3]=0;maze[8][4]=0;maze[8][5]=0;maze[8][6]=0;maze[8][7]=0;maze[8][8]=0;maze[8][9]=0; maze[9][0]=1;maze[9][1]=1;maze[9][2]=1;maze[9][3]=1;maze[9][4]=1;maze[9][5]=1;maze[9][6]=1;maze[9][7]=1;maze[9][8]=1;maze[9][9]=0;}voidautomatic_maze(intm,intn)//定義函數(shù)可自動生成一個迷宮{ inti,j; cout<<"自動生成迷宮中，請稍候......"<<endl; system("pause"); for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2;//隨機生成0、1作為迷宮中一點的標(biāo)志（通路或障礙） maze[0][0]=0;//將入口和出口強制為0，保證有可能出來迷宮 maze[m-1][n-1]=0;}voidhand_maze(intm,intn)//定義函數(shù)手動生成一個迷宮{ inti,j;cout<<"請按行輸入迷宮，0表示此處為通路，1表示此處為障礙:"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++) { cin>>maze[i][j];//需手動輸入每一個點的相關(guān)信息，比較繁瑣，僅供求解已知迷宮形狀用 if(maze[i][j]!=0&&maze[i][j]!=1)//當(dāng)輸入的數(shù)字不是0或1的時候，需要及時糾錯 cout<<"您輸入的數(shù)字有誤，請輸入0或1!"<<endl; cin>>maze[i][j]; }}voiddata(intm,intn)//考慮到用戶輸入數(shù)字的隨機性，加入異常處理函數(shù)，保證能生成一個規(guī)則的迷宮{ inti,j; cout<<"根據(jù)您先前輸入的迷宮范圍"<<endl; cout<<"系統(tǒng)將取所輸入的前"<<m*n<<"個數(shù)生成一個迷宮"<<endl; cout<<"\n數(shù)字迷宮生成結(jié)果:\n\n"; cout<<"迷宮入口\n";cout<<"↓"; for(i=0;i<m;i++)//組成一個方陣，顯示每一點的情況（障礙還是通路） { cout<<"\n"; for(j=0;j<n;j++) { if(maze[i][j]==0)cout<<"0"; if(maze[i][j]==1)cout<<"1"; } } cout<<"→迷宮出口\n";}voidprint_maze(intm,intn)//函數(shù)將迷宮輸出為可視化界面，加強程序交互性{ inti,j,k; cout<<"\n迷宮圖生成結(jié)果如下，空心圓代表此處為通路，實心圓代表此處為障礙:\n"; cout<<"迷宮入口\n"<<"↓";//入口指示 cout<<endl; cout<<"★";//生成入口邊上的五角星 for(k=0;k<n;k++)//通過一個橫排的實心五角星來生成迷宮的上邊界 { cout<<"★"; } for(i=0;i<m;i++) { cout<<"\n";//生成左邊界 cout<<"★"; for(j=0;j<n;j++) { if(maze[i][j]==0)printf("○");//空心圓代表此處為通路，實心圓代表此處為障礙 if(maze[i][j]==1)printf("●"); } cout<<"★";//生成右邊界 } cout<<endl; for(k=0;k<n;k++) { cout<<"★"; } cout<<"★\n";//最后是底部的邊界for(i=0;i<n;i++) { cout<<"";}cout<<"↓\n"; for(i=0;i<n-1;i++) { cout<<"";} cout<<"迷宮出口\n";//出口指示}voidresult_maze(intm,intn)//這個函數(shù)用來輸出迷宮的求解結(jié)果{ inti,j; cout<<"以上生成的迷宮通路(用□表示)為：\n\t"; for(i=0;i<m;i++) { cout<<"\n"; for(j=0;j<n;j++) { if(maze[i][j]==0||maze[i][j]==2)//2標(biāo)記的是隊列中已訪問過的點 cout<<"○"; if(maze[i][j]==1) cout<<"●"; if(maze[i][j]==3)//3標(biāo)記的是走出迷宮路徑 cout<<"□"; } }}voidenqueue(structpointp)//迷宮中隊列入隊操作{ queue[tail]=p; tail++;}structpointdequeue()//迷宮中隊列出隊操作，返回的是結(jié)構(gòu)體變量{ head++; returnqueue[head-1];}boolis_empty()//判斷隊列是否為空{(diào) returnhead==tail;}voidvisit(introw,intcol,intmaze[102][102])//訪問迷宮中的各個位置{ structpointvisit_point={row,col,head-1};//head-1的作用是訪問這個點序號之前的點序號 maze[row][col]=2;//將已訪問過的點位標(biāo)記為2，便于以后輸出 enqueue(visit_point);//將訪問過的位置入隊}intpath(intmaze[102][102],intm,intn)//主要函數(shù)，用于求解迷宮路徑{ X=1;//剛開始聲明的變量，初始值定為1 structpointp={0,0,-1};//定義入口節(jié)點 if(maze[p.row][p.col]==1)//異常處理，如果入口為1時，迷宮無解{cout<<"很遺憾......此迷宮無解\n\n"; X=0; return0; }maze[p.row][p.col]=2;//入口標(biāo)記為已訪問 enqueue(p);//將p入隊列 while(!is_empty())//只在隊列不為空的情況下執(zhí)行此函數(shù)，向著迷宮通的位置移動，尋找路線 {p=dequeue();//將p標(biāo)記為此時訪問的位置，如果這個位置已到出口，則表示迷宮有解 if((p.row==m-1)&&(p.col==n-1))//當(dāng)行和列為出口時結(jié)束 break; //以下定義8個走位方向 if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col+0)<n))&&(maze[p.row-1][p.col+0]==0)) visit(p.row-1,p.col+0,maze);//北 if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col+1)<n))&&(maze[p.row-1][p.col+1]==0)) visit(p.row-1,p.col+1,maze);//東北 if((((p.row+0)<m)&&((p.col+1)<n))&&(maze[p.row+0][p.col+1]==0)) visit(p.row+0,p.col+1,maze);//東 if((((p.row+1)<m)&&((p.col+1)<n))&&(maze[p.row+1][p.col+1]==0)) visit(p.row+1,p.col+1,maze);//東南 if((((p.row+1)<m)&&((p.col+0)<n))&&(maze[p.row+1][p.col+0]==0)) visit(p.row+1,p.col+0,maze);//南 if((((p.row+1)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row+1][p.col-1]==0)) visit(p.row+1,p.col-1,maze);//西南 if((((p.row+0)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row+0][p.col-1]==0)) visit(p.row+0,p.col-1,maze);//西 if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row-1][p.col-1]==0)) visit(p.row-1,p.col-1,maze);//西北 } if(p.row==m-1&&p.col==n-1)//如果p到達出口點，輸出路徑 { cout<<"\n恭喜您，此迷宮有解!\n"; cout<<"迷宮路徑為：\n";cout<<"出口"<<endl; cout<<""<<"↑"<<endl; printf("(%d,%d)\n",p.row+1,p.col+1); cout<<""<<"↑"<<endl; maze[p.row][p.col]=3;//逆序?qū)⒙窂綐?biāo)記為3，便于以后輸出 while(p.predecessor!=-1)//輸出迷宮的坐標(biāo)求解圖 { p=queue[p.predecessor]; printf("(%d,%d)\n",p.row+1,p.col+1); cout<<""<<"↑"<<endl; maze[p.row][p.col]=3; } cout<<"入口"<<endl; } else { cout<<endl<<"很遺憾，此迷宮無解！\n\n"; X=0; } return0;}voidmain(){inti,m,n,cycle=0;//初始化各函數(shù)變量while(cycle!=(-1))//用cycle標(biāo)記當(dāng)前是否繼續(xù)調(diào)試{cout<<"================================================================================\n";cout<<"歡迎進入迷宮求解系統(tǒng)\n"; cout<<endl;cout<<"設(shè)計者:桂柯易（09210580，2009211120班）\n";cout<<"================================================================================\n";cout<<"如需手動生成迷宮請按：1\n";cout<<"如需自動生成迷宮請按：2\n"; cout<<"如需求解書后給的迷宮請按：3\n";cout<<"如需退出請按：4\n\n";cout<<"================================================================================\n";cout<<endl;cout<<"請選擇你的操作：\n";cin>>i; switch(i)//用switch函數(shù)確定對應(yīng)的操作 { case1: cout<<"\n請輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請輸入列數(shù)："; cin>>n; while((m<0||m>100)||(n<0||n>100))//異常處理，當(dāng)輸入的行列數(shù)不滿足要求時，需要重新輸入 { cout<<"\n抱歉，你輸入的行列數(shù)不屬于預(yù)設(shè)范圍(0-100,0-100),請重新輸入：\n\n"; cout<<"\n請輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請輸入列數(shù)："; cin>>n; } hand_maze(m,n);//手動輸入迷宮 data(m,n);//根據(jù)實際情況生成數(shù)字迷宮 print_maze(m,n);//畫出迷宮圖 path(maze,m,n);//迷宮求解 if(X!=0)result_maze(m,n);//當(dāng)X不為0時，有解，調(diào)用輸出路徑函數(shù) cout<<"\n\n需要繼續(xù)調(diào)試，請按回車鍵!\n"; getchar(); while(getchar()!='\n');//輸入一個操作，當(dāng)為回車時執(zhí)行break跳出 break; case2: cout<<"\n請輸入行數(shù)：";cin>>m; cout<<"\n";cout<<"請輸入列數(shù)："; cin>>n; while((m<0||m>49)||(n<0||n>49))//異常處理，行列不滿足要求時需要重新輸入 { cout<<"\n抱歉，你輸入的行列數(shù)不屬于預(yù)設(shè)范圍(0-100,0-100),請重新輸入：\n\n"; cout<<"\n請輸入行數(shù)："; cin>>m; cout<<"\n"; cout<<"請輸入列數(shù)："; cin>>n; } automatic_maze(m,n);//自動生成迷宮 data(m,n);//生成數(shù)字迷宮 print_maze(m,n);//畫出迷宮圖 path(maze,m,n);//迷宮求解 if(X!=0)result_maze(m,n);//當(dāng)X不為0時，有解，調(diào)用輸出路徑函數(shù) cout<<"\n\n需要繼續(xù)調(diào)試，請按回車鍵!\n"; getchar(); while(getchar()!='\n'); break; case3: student_maze();//生成書后迷宮 print_maze(10,10);//畫出迷宮圖（暫不生成數(shù)字迷宮） path(maze,10,10);//迷宮求解 if(X!=0)result_maze(10,10);