2011年6月17日 星期五

EX15.使用堆疊的回溯控制- 走迷宮

修改程式範例: Ch5-4-1.c 為 Ch5-4-1e.c
1. 請使用堆疊方式找出走出迷宮的路，如下所示：
2. 可走的路自行設定。





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/* 程式範例: Stack.c */
#include "Ch5-2-2.h"
/* 函數: 檢查堆疊是否是空的 */
int isStackEmpty() {
   if ( top == NULL ) return 1;
   else               return 0;
}
/* 函數: 將資料存入堆疊 */
void push(int d) {
   LStack new_node;            /* 新節點指標 */
   /* 配置節點記憶體 */
   new_node = (LStack)malloc(sizeof(SNode));
   new_node->data = d;         /* 建立節點內容 */
   new_node->next = top;       /* 新節點指向原開始 */
   top = new_node;             /* 新節點成為堆疊開始 */   
}
/* 函數: 從堆疊取出資料 */
int pop() {
   LStack ptr;                 /* 指向堆疊頂端 */
   int temp;
   if ( !isStackEmpty()  ) {   /* 堆疊是否是空的 */
      ptr = top;               /* 指向堆疊頂端 */
      top = top->next;         /* 堆疊指標指向下節點 */
      temp = ptr->data;        /* 取出資料 */
      free(ptr);               /* 釋回節點記憶體 */
      return temp;             /* 堆疊取出 */
   }
   else return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12

/* 程式範例: Ch5-2-2.h */
struct Node {                  /* 堆疊節點的宣告 */
   int data;                   /* 儲存堆疊資料 */
   struct Node *next;          /* 指向下一節點 */
};
typedef struct Node SNode;     /* 堆疊節點的新型態 */ 
typedef SNode *LStack;         /* 串列堆疊的新型態 */
LStack top = NULL;             /* 堆疊頂端的指標 */
/* 抽象資料型態的操作函數宣告 */ 
extern int isStackEmpty();
extern void push(int d);
extern int pop();



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/* 程式範例: Ch5-4-1e.c */
#include <stdio.h>
#include <stdlib.h>
#include "stack.c"
/* 主程式: 使用回溯方法在陣列走迷宮 */
int main() {
   int maze[8][11] = { /* 迷宮陣列,數字0可走, 1不可走 */
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1,
            1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1,
            1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1,
            1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1,
            1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
            1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
   int i,j;
   int x = 6;                     /* 迷宮入口座標 */
   int y = 9;
   while ( x != 1 || y != 1 ) {   /* 主迴圈 */
      maze[x][y] = 2;             /* 標示為已走過的路 */
      if ( maze[x-1][y] <= 0 ) {  /* 往上方走 */
         x = x - 1;               /* 座標x減1 */
         push(x);                 /* 存入路徑 */
         push(y);
      }
      else if ( maze[x+1][y] <= 0 ) { /* 往下方走 */
           x = x + 1;            /* 座標x加1 */
           push(x);              /* 存入路徑 */
           push(y);
         }
         else if ( maze[x][y-1] <= 0 ) { /* 往左方走 */
              y = y - 1;            /* 座標y減1 */
              push(x);              /* 存入路徑 */
              push(y);
           }
           else if ( maze[x][y+1] <= 0 ) {/* 往右方走 */
                y = y + 1;             /* 座標y加1 */
                push(x);               /* 存入路徑 */
                push(y);
             }
             else {  /* 沒有路可走:迴溯 */
                  maze[x][y] = 3;   /* 表示是迴溯的路 */
                  y = pop();        /* 退回一步 */
                  x = pop();
               }
   }
   maze[x][y] = 2;                /* 標示最後位置 */
   printf("迷宮路徑圖(從右下角到左上角): \n");
   for ( i = 0; i <= 7; i++) {    /* 顯示迷宮圖形 */
      for ( j = 0; j <= 10; j++)
         printf("%d ", maze[i][j]); /* 顯示座標值 */
      printf("\n");
   }
   printf("\n數字 1: 牆壁\n數字 2: 走過的路徑\n");
   printf("數字 3: 回溯路徑\n");
   system("PAUSE");
   return 0; 
}
執行結果：
迷宮路徑圖(從右下角到左上角):
1 1 1 1 1 1 1 1 1 1 1
1 2 1 2 2 2 1 1 1 1 1
1 2 2 2 1 2 2 1 1 1 1
1 1 3 1 1 1 2 2 1 1 1
1 1 3 1 1 1 1 2 2 1 1
1 3 2 3 3 3 3 1 2 2 1
1 3 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 1 1 1 1
數字 1: 牆壁
數字 2: 走過的路徑
數字 3: 回溯路徑
請按任意鍵繼續 . . .
張貼者： 於

1 則留言:

  1. JCCL2011年6月24日 清晨5:08

    評分: ★★★★▲

    pls include "Ch5-2-2.h" source code.

    回覆刪除

訂閱： 張貼留言 (Atom)