数据结构中栈的应用--迷宫问题

    迷宫问题可以说是很经典的问题,也算是栈的一个应用吧,在谈到这道题目时,我首先想到的是迷宫存储问题,我将他初始化成一个数组,为了模拟迷,我将1代表不可走,0代表可走.然后定义迷宫类型,当让包括方向dir,行row,列col.而dir则包括了4个方向:即东南西北,当然也可以设置成8个方向!
    写好了这些,就开始写迷宫算法吧!代码我都加上了注释,以下程序均通过gcc4.1版本测试,运行结果及代码如下:


#include<stdio.h>
#include<stdbool.h>
#define MAX_STACK_SIZE 100
#define EXIT_ROW 9
#define EXIT_COL 9
 
 
int maze[10][10] = {
        {1,0,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,1,1,1,0,1},
        {1,1,0,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,0,1}};/*初始化迷宫*/
int mark[10][10] = {0};/*初始化标志位,0代表没走过,1代表走过*/
 
/*方向*/
typedef struct{
    short int vert;
    short int horiz;
}offsets;
 
offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};/*北,东,南,西*/
 
 
/*迷宫类型*/
typedef struct {
    short int row;
    short int col;
    short int dir;
}element;
 
element stack[MAX_STACK_SIZE];
 
 
void path(void);
element delete(int* top);
void add(int* top,element item);
 
 
element delete(int* top)/*出栈,top指向栈顶元素*/
{
    if(*top == -1)
    {
        printf("stack is empty!\n");
    }
    return stack[(*top)--];
}
 
 
void add(int* top,element item)/*入栈*/
{
    if(*top >= MAX_STACK_SIZE - 1)
    {
        printf("stack is full!\n");
        return;
    }
    stack[++*top] = item;
}
 
 
void path(void)/*迷宫函数*/
{
    element position;
    int i,row,col,next_row,next_col,dir,top;
    _Bool found = 0;
    mark[1][1] = 1,top = 0;/*初始化标志数组元素以及栈*/
    stack[0].row = 1,stack[0].col = 1,stack[0].dir = 0;
    while(top > -1 && !found)
    {
        position = delete(&top);    /*将栈顶元素取出,*/
        row = position.row;            /*利用中间变量row,col,dir等候判断*/
        col = position.col;
        dir = position.dir;
        while(dir < 4 && !found)
        {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;
            if(next_row == EXIT_ROW && next_col == EXIT_COL)
                found = 1;
            else if(!maze[next_row][next_col] && !mark[next_row][next_col])/*判断下一步可走并且没走过,则入栈*/
                    {
                        mark[next_row][next_col] = 1;
                        position.row = row;
                        position.col = col;
                        position.dir = ++dir;
                        add(&top,position);/*合理则入栈*/
                        row = next_row;/*继续向下走*/
                        col = next_col;dir = 0;
                    }
                    else
                        dir++;/*dir<4时,改变方向*/
        }
        if(found)/*判断是否有出口*/
        {
            printf("the path is:\n");
            printf("row col\n");
            for(i = 0;i <= top;++i)
                printf("%2d%5d",stack[i].row,stack[i].col);
            printf("%2d%5d\n",row,col);
            printf("%2d%5d\n",EXIT_ROW,EXIT_COL);
        } 
    }
}
 
 
int main(void)
{  
    path();
    return 0;
}

注释:参见Fundamentals of Data STRUCTURES In C 中文版数据结构(C语言版)

posted on 2007-04-28 23:22 honker 阅读(5573) 评论(2)  编辑 收藏 引用 所属分类: c/c++

评论

# re: 数据结构中栈的应用--迷宫问题[未登录] 2008-03-28 13:26 1

垃圾  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2024年12月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

常用链接

留言簿(3)

随笔分类(10)

随笔档案(14)

相册

搜索

最新评论

阅读排行榜

评论排行榜