小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

棧的妙用-實(shí)現(xiàn)迷宮問題（轉(zhuǎn)）

 WUCANADA 2013-04-16

分類： LINUX

堆棧是計(jì)算機(jī)程序中非常重要的一部分，主要用來參數(shù)的調(diào)用，局部變量的存儲等，在C語言中的函數(shù)調(diào)用過程中通過不同函數(shù)的堆?？臻g可以非常方便的找到傳遞進(jìn)來的參數(shù)以及退出時應(yīng)該返回的地址。具體的參看“函數(shù)調(diào)用分析 ”，這篇文章中通過實(shí)例分析討論了函數(shù)調(diào)用過程中堆棧的變化過程。
 
實(shí)質(zhì)上棧的運(yùn)用并不是只能在函數(shù)調(diào)用中，棧作為一種數(shù)據(jù)結(jié)構(gòu)，自然有其特殊的意義，棧的最大特點(diǎn)是"先入后出，后入先出"，這個特點(diǎn)可以用來結(jié) 局很多的問題。C語言中的函數(shù)調(diào)用算是其中的最主要的用法之一，也就不再分析和討論。同樣遞歸，嵌套調(diào)用等都屬于函數(shù)調(diào)用的子類也不再描述。在其他方面經(jīng) 典的運(yùn)用是解決迷宮問題，不同進(jìn)制數(shù)值之間的轉(zhuǎn)換，長字符串的分解以及算術(shù)表達(dá)式的求值等。下面我主要采用棧實(shí)現(xiàn)經(jīng)典的迷宮問題。
迷宮問題
迷宮問題是經(jīng)典的一類問題，如何從給出的入口找到對應(yīng)的出口，實(shí)現(xiàn)的方法和馬踏棋盤問題相似也是通過找到周圍8個方向坐標(biāo)的關(guān)系，然后依據(jù)深度 優(yōu)先搜索方法和一定的條件找到下一步對應(yīng)的出路。由于迷宮問題需要存儲具體的完成路勁，這與前面的問題存在一定的差別。采用棧能夠很好的解決這個問題，其 中棧結(jié)構(gòu)用來存儲具體的坐標(biāo)和方向。這樣根據(jù)棧就能保證以后每一次都能快速的找到出路。
實(shí)現(xiàn)的基本步驟如下：
1、為了避免邊界檢測問題，在迷宮的外圍添加一層圍墻，比如原來的迷宮為m*n,則添加圍墻以后的矩陣為(m+2)*(n+2)。其中為1表示不能走通，0時表示可以走通。這樣maze[1][1]表示迷宮的入口，而maze[m][n]表示迷宮的出口。
2、創(chuàng)建一個堆?？臻g，可以采用靜態(tài)數(shù)組的方式，但由于不能準(zhǔn)確的估計(jì)數(shù)組空間大小，可以采用動態(tài)創(chuàng)建的方式。并將入口坐標(biāo)值壓入到棧中。定義 一個與迷宮大小相同的矩陣mark，用來統(tǒng)計(jì)當(dāng)前坐標(biāo)是否已經(jīng)到達(dá)過，當(dāng)沒有到達(dá)坐標(biāo)（i,j）時，則有mark[i][j] = 0,如果之前到達(dá)過，則有mark[i][j] = 1.這樣主要是為了避免形成內(nèi)部死循環(huán)，同時說明此路不能走通。
3、檢測?？臻g是否為空，如果為空則停止，如果不為空，則彈出棧頂?shù)脑?
4、采用循環(huán)的方式，依據(jù)元素的方向確定下一個坐標(biāo)，具體的確定方法依據(jù)之前的移動關(guān)系找到，判斷該位置是否為0（maze[nextrow] [nextcol] == 0）以及之前是否到達(dá)該位置(mark[nextrow][nextcol] == 1)。如果滿足條件，則將mark[nextrow][newcol]設(shè)置為1，并將當(dāng)前位置以及具體的方向值壓入棧中，將當(dāng)前坐標(biāo)設(shè)置為之前確定的下一 個坐標(biāo)，設(shè)置方向?yàn)?。然后重新進(jìn)行步驟4。如果8個方向全部不能找到合適的下一個坐標(biāo)，說明此路走不通。重新進(jìn)行步驟3，探索新的路勁。探索成功的條件 是(nextrow == EXIT_ROW&&nextcol == EXIT_COL)。
基本的實(shí)現(xiàn)流程圖如下所示：

代碼實(shí)現(xiàn)如下：

點(diǎn)擊(此處)折疊或打開

  1. /*maze_problem.h*/
  2. #ifndef MAZE_PROBLEM_H_H_
  3. #define MAZE_PROBLEM_H_H_

  5. typedef struct
  6. {
  7.     int vert;
  8.     int horiz;
  9. }offsets;

  11. typedef struct {
  12.     int row;
  13.     int col;
  14.     int dir;
  15. }element;

  17. typedef struct {
  18.     int row;
  19.     int col;
  20. }coordinate;
  21. #endif

點(diǎn)擊(此處)折疊或打開

  1. /*maze_problem.c*/
  2. #include "maze_problem.h"

  4. #include<stdio.h>
  5. #include<stdlib.h>

  7. offsets move[8];

  9. /*the stack save the path, and used */
  10. element * stack;
  11. int top = -1;

  13. void initial_move(void)
  14. {
  15.     /*horiz means cols*/
  16.     move[0].horiz = 0;
  17.     /*vert means rows*/
  18.     move[0].vert = -1;
  19.     
  20.     move[1].horiz = 1;
  21.     move[1].vert = -1;
  22.     
  23.     move[2].horiz = 1;
  24.     move[2].vert = 0;
  25.     
  26.     move[3].horiz = 1;
  27.     move[3].vert = 1;

  29.     move[4].horiz = 0;
  30.     move[4].vert = 1;
  31.     
  32.     move[5].horiz = -1;
  33.     move[5].vert = 1;
  34.     
  35.     move[6].horiz = -1;
  36.     move[6].vert = 0;
  37.     
  38.     move[7].horiz = -1;
  39.     move[7].vert = -1;
  40. }
  41. #define MAZE_ROWS    12
  42. #define MAZE_COLS    15

  44. #define NEW_MAZE_ROWS (MAZE_ROWS + 2)
  45. #define NEW_MAZE_COLS (MAZE_COLS + 2)
  46. #define EXIT_COL    15
  47. #define EXIT_ROW    12

  49. int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS]
  50. = {
  51.  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  52.  1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,
  53.  1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,
  54.  1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,
  55.  1,1,1,0,1,1,1,1,1,1,1,0,1,1,0,0,1,
  56.  1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,
  57.  1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,
  58.  1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,
  59.  1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
  60.  1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,
  61.  1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,
  62.  1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,
  63.  1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,
  64.  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  65. };

  67. /*used to store the used place*/
  68. int mark[NEW_MAZE_ROWS][NEW_MAZE_COLS];

  70. void mark_init()
  71. {
  72.     int i = 0,j = 0;
  73.     for(i = 0; i < NEW_MAZE_ROWS ; ++ i)
  74.         for(j = 0; j < NEW_MAZE_COLS ; ++ j)
  75.             mark[i][j] = 0;
  76. }
  77. int mark_stack_size(int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS])
  78. {
  79.     int i = 0,j = 0;

  81.     int size = 0;
  82.     for(i = 0; i < NEW_MAZE_ROWS; ++ i)
  83.         for (j = 0; j < NEW_MAZE_COLS ; ++ j)
  84.         {
  85.             if(!maze[i][j])
  86.             size ++;
  87.         }    
  88.     return size;
  89. }

  91. coordinate nextposition(element a,int dir)
  92. {
  93.     coordinate b;
  94.     b.col = a.col + move[dir].horiz;
  95.     b.row = a.row + move[dir].vert;
  96.     
  97.     return b;
  98. }

  100. int maze_out()
  101. {
  102.     element temp;
  103.     coordinate nextp;
  104.     
  105.     /*Test the stack is not empty*/
  106.     while(top >= 0)
  107.     {
  108.         /*pop a element*/
  109.         temp = *(stack+top);
  110.         top --;

  112.         /*find on eight directions*/
  113.         while(temp.dir < 8)
  114.         {
  115.             /*get the possible next positions*/
  116.             nextp = nextposition(temp,temp.dir);
  117.             /*next direction*/
  118.             temp.dir ++;

  120.             /*success conditions*/
  121.             if(nextp.row == EXIT_ROW &&
  122.              nextp.col == EXIT_COL)
  123.             {
  124.                 /*save current position*/
  125.                 stack[++top] = temp;

  127.                 /*save the exit pointion*/
  128.                 stack[++top].row = EXIT_ROW;
  129.                 stack[top].col = EXIT_COL;
  130.                 stack[top].dir = 0;

  132.                 /*exit*/
  133.                 return 1;
  134.             }

  136.             /*the new position is ok and does not wake*/
  137.             if(maze[nextp.row][nextp.col] ==0 &&
  138.              mark[nextp.row][nextp.col] == 0)
  139.             {
  140.                 /*mark means that this way has been waked*/
  141.                 mark[nextp.row][nextp.col] = 1;

  143.                 /*
  144.                  *push a element in stack
  145.                  *save current position and direction
  146.                  *if this way is failed, used to this position to start new way.
  147.                 */
  148.                 stack[++top] = temp;
  149.                 
  150.                 /*go to the new position as current position*/
  151.                 temp.row = nextp.row;
  152.                 temp.col = nextp.col;
  153.                 temp.dir = 0;
  154.             }
  155.         }
  156.     }    
  157.     /*failed*/
  158.     return 0;
  159. }

  161. int main()
  162. {
  163.     int i = 0;
  164.     /*inital the mark array*/
  165.     mark_init();
  166.     initial_move();

  168.     /*create stack*/
  169.     stack = (element*)malloc(mark_stack_size(maze)*sizeof(element));
  170.     /*if failed*/
  171.     if(stack == NULL)
  172.         return 0;
  173.     /*push a element in stack*/
  174.     top ++;
  175.     (stack+top)->col = 1;
  176.     (stack+top)->row = 1;
  177.     (stack+top)->dir = 0;

  179.     if(maze_out())
  180.     {
  181.         while(i <= top)
  182.         {
  183.             printf("(%d,%d,%d)\n",stack[i].row,stack[i].col,stack[i].dir);
  184.             i ++;
  185.         }
  186.     //    printf("(%d,%d)\n",EXIT_ROW,EXIT_COL);

  188.     }
  189.     /*free the memory*/
  190.     free(stack);
  191.     /*point to the NULL*/
  192.     stack = NULL;
  193.     return 1;
  194. }
測試結(jié)果：

在迷宮問題中，棧主要實(shí)現(xiàn)了對滿足條件坐標(biāo)以及方向值(0-7,分別表示一個具體的方向)的動態(tài)保存能夠保證路勁的一致性，也就是先入后出的特性。

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多