C語言數(shù)據(jù)結構中求解迷宮問題的示例分析-創(chuàng)新互聯(lián)

這篇文章給大家分享的是有關C語言數(shù)據(jù)結構中求解迷宮問題的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

創(chuàng)新互聯(lián)是一家集網站制作、網站建設、網站頁面設計、網站優(yōu)化SEO優(yōu)化為一體的專業(yè)的建站公司，已為成都等多地近百家企業(yè)提供網站建設服務。追求良好的瀏覽體驗,以探求精品塑造與理念升華,設計最適合用戶的網站頁面。 合作只是第一步，服務才是根本,我們始終堅持講誠信，負責任的原則，為您進行細心、貼心、認真的服務,與眾多客戶在蓬勃發(fā)展的市場環(huán)境中,互促共生。

C語言 數(shù)據(jù)結構中求解迷宮問題實現(xiàn)方法

   首先求迷宮問題通常用的是“窮舉求解” 即從入口出發(fā)，順某一方向試探，若能走通，則繼續(xù)往前走，否則原路返回，換另一個方向繼續(xù)試探，直至走出去。

我們可以先建立一個8*8的迷宮其中最外側為1的是墻

int mg[M+2][N+2]={
 {1,1,1,1,1,1,1,1,1,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,0,0,1,1,0,0,1},
 {1,0,1,1,1,0,0,0,0,1},
 {1,0,0,0,1,0,0,0,0,1},
 {1,0,1,0,0,0,1,0,0,1},
 {1,0,1,1,1,0,1,1,0,1},
 {1,1,0,0,0,0,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1},
}

   如上所示，0對應通道方塊，1代表墻。對于迷宮中的每個方塊，有上下左右4個方塊相鄰，我們規(guī)定第i行第j列方塊的位置為（i,j） 規(guī)定上方方塊方位為0，順時針方向遞增編號。(i,j)上方的即為(i-1,j),下方(i+1,j)，左方(i,j-1)，右方(i,j+1).    為了方面回溯，我們需要有進棧出棧操作，所以我們來定義：

struct {
  int i;//當前方位行
  int j;//當前方位列
  int di;//下一個可走方位號
}St[MaxSize];//棧
int top=-1;//初始化棧頂指針

我們來看看文字過程~~

   首先將入口進棧（初始方位為-1），在棧不空的情況下循環(huán)：取棧頂方塊（不退棧），若該方塊是出口，則退棧。若存在這樣的方塊，則將其方位保存到棧頂元素中，并將這個可走的相鄰方塊進棧。

對應的算法：

void mgpath(int x1,int y1,int x2,int y2){
  int i.j,di,find,k;
  top++;
  St[top].i=x1; St[top].j=y1; St[top].di=-1; mg[x1][y1]=-1;

 while (top>-1){
  i=St[top].i; j=St[top].j; di=St[top].di;
  if (i==x2 && j==y2){
     printf("迷宮路徑如下：\n");
    for (k=0;k<=top;k++){
      printf("\t(%d,%d)",St[k].i,S[k].j);
       if ((k+1)%5==0) printf("\n"); //輸出5個換一行
       }
  printf("\n");  //找到一條路徑后結束
  return ;
  }
  find=0;
  while (di<4 && find==0){
  di++;
  switch(di){
   case 0: i=St[top].i-1; j=S[top].j;break;
   case 1: i=St[top].i;  j=St[top].j+1;break;
   case 2: i=St[top].i+1;j=St[top].j;break;
   case 3: i=St[top].i;  j=St[top].j-1;break;
   }
    if(mg[i] [j]==0) find=1;
  }
  if (find==1){  //找到了下一個可走方塊
   St[top].di=di;//修改原棧頂?shù)闹?   top++;  //下一個可走方塊進棧
  St [top].i=i; St[top].j=j;St[top].di=-1;
  mg[i] [j]=-1;//避免重復走到該方塊
 }
  else{  //沒有路徑可走,進行退棧操作
    mg[St[top].i] [St[top].j]=0;//讓該位置變?yōu)槠渌窂降目勺叻綁K
    top--;
    }

}
  printf("沒有路徑可走!\n");
}

當然我們也可以用隊列去求該迷宮的最優(yōu)算法，這只是一個用來理解棧的例子~~~

感謝各位的閱讀！關于“C語言數(shù)據(jù)結構中求解迷宮問題的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)建站bm7419.com，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網頁題目：C語言數(shù)據(jù)結構中求解迷宮問題的示例分析-創(chuàng)新互聯(lián)
網站路徑：http://bm7419.com/article42/dpoehc.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、網站內鏈、全網營銷推廣、域名注冊、云服務器、電子商務

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)

手機網站建設