#define ERROR 0

#define NULL 0

#define true 1

#define TRUE 1

#define false 0

#define FALSE 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

#include

#include

/*

初始化迷宫,1表示通道,0表示墙

*/

int maze[8][8] = {

    1,1,0,1,1,1,0,1,

    1,1,0,1,1,1,0,1,

    1,1,1,1,0,0,1,1,

    1,0,0,0,1,1,1,1,

    1,1,1,0,1,1,1,1,

    1,0,1,1,1,0,1,1,

    1,0,0,0,1,0,0,1,

    0,1,1,1,1,1,1,1

};

//定义栈元素类型 

typedef struct MStackElem

{

    int x;//x坐标

    int y;//y坐标

    int val;//maze[x][y]的值

}MStackElem;

//定义栈

typedef struct {

    MStackElem * base;

    MStackElem * top;

    int stackSize;

}MStack;

//=============Stack的实现========================

//初始化栈-------构造一个空栈

void initStack(MStack *s) {

s->base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem));

if (!s->base) {

       printf("in initStack()...Failed to initalize the MStack ,no enough space! exit now. ");

       exit(OVERFLOW);//存储分配失败

    }

s->top = s->base;

s->stackSize = STACK_INIT_SIZE;

}

//向栈中添加元素

void push(MStack *s,MStackElem e) {

     //向栈中添加元素前先判断栈是否还有空间容纳新元素

if (s->top - s->base >= s->stackSize) { //栈满,追加元素

s->base = (MStackElem *)realloc(s->base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem));

if (!s->base) {

        printf("in push()...Failed to realloc the MStack ,no enough space! exit now. ");

        exit(OVERFLOW);//存储分配失败

       }

s->top = s->base + s->stackSize; //因为是重新分配了空间,所以base的值其实已经改变,所以top的值也就相应的改变,才能指向新的迷宫栈 

s->stackSize += STACKINCREMENT;

    }

    //将新元素加到栈顶 

*(s->top++) = e;

}

//获得栈顶元素

MStackElem getTop(MStack *s) {

if (s->top == s->base) {

   printf("in getTop(),empty stack! exit now. ");

   exit(ERROR);

}

else {

return *(s->top - 1);

}

}

//删除栈顶元素

void pop(MStack *s) {

//若栈不为空,则删除s的栈顶元素

if (s->top == s->base) {

       printf("in pop(),empty stack! exit now. ");

       exit(ERROR);

    }

    else {

--(s->top);

    }

}

//================求解迷宫的相关操作=====================//

//构造两个栈,一个用来保存探索中的全部路径,一个用来保存有效路径

MStack realPath,path;

//判断当前位置是否走过

int unPass(MStack path,MStackElem cur) {//这里不能传path的地址,否则在遍历过程中它的top值就真的被改了 !! 

    int flag = 1;

    while(path.top != path.base)

    {

       MStackElem e = *(path.top - 1);

       if (e.x == cur.x&& e.y == cur.y)

       {

        flag = 0;

       }

       //每循环一次令头指针下移一个位置 

       (path.top)--;

    }

    return flag;

}

//获得东面相邻的位置

MStackElem getEast(MStackElem cur) {

           if(cur.y != 7) {//当y==7时已到了迷宫右边界,不能再向东(右)行了 

                cur.y += 1;

                cur.val = maze[cur.x][cur.y];

           } 

           return cur;// 当y==7时返回的是它本身 

} 

//获得南面相邻的位置

MStackElem getSouth(MStackElem cur) {

           if(cur.x != 7) {//当x==7时已到了迷宫下边界,不能再向南(下)行了 

                cur.x += 1;

                cur.val = maze[cur.x][cur.y];

           }

           return cur;// 当x==7时返回的是它本身 

}

//获得西面相邻的位置

MStackElem getWest(MStackElem cur) {

           if(cur.y != 0) {//当y==0时已到了迷宫左边界,不能再向西(左)行了 

                cur.y -= 1;

                cur.val = maze[cur.x][cur.y];

           }

           return cur;// 当y==0时返回的是它本身 

}

//获得北面相邻的位置

MStackElem getNorth(MStackElem cur) {

     if(cur.x != 0) {//当cur.x==0时表示在迷宫的上边界,不能再向北(上)行了 

        cur.x -= 1;

        cur.val = maze[cur.x][cur.y];

     }

     return cur;// 当cur.x==0时返回的还是它本身 

}

//获得下一个可通行的位置,按东南西北的方向试探

MStackElem getNext(MStackElem cur) {

MStackElem next;

next.x = next.y=next.val = -1;

if(getEast(cur).val != 0 && unPass(path,getEast(cur))) {

   next = getEast(cur);

}

else if(getSouth(cur).val != 0 && unPass(path,getSouth(cur))) {

   next = getSouth(cur);

}

else if(getWest(cur).val != 0 && unPass(path,getWest(cur))) {

   next = getWest(cur);

}

else if(getNorth(cur).val != 0 && unPass(path,getNorth(cur))) {

   next = getNorth(cur);

}

//如果当前位置的四面或为墙或已走过,则返回的next的val值为-1 

return next;

}

int getMazePath(){//获得迷宫路径的函数

    MStackElem start,end,cur; 

    start.x = 0;

    start.y = 0;

    start.val = maze[start.x][start.y];

    end.x = 7;

    end.y = 7; 

    end.val = maze[end.x][end.y];

    cur = start; //设定当前为位置为"入口位置"

    //没有重载=运算符,可以这样用吗,结果对吗?试试吧:

    /*                                               

    printf("%d",cur.x);

    printf("%d",cur.y); 

    printf("%d",cur.val);                                                 

    */

    do 

    {                                                  

        if (unPass(path,cur)) {//如果当前位置未曾走到过

            push(&realPath,cur);

            push(&path,cur);

            cur = getNext(cur);

            if (cur.x == end.x && cur.y == end.y) { //到达出口了,则跳出循环,并返回true 

               //把出口结点放入路径中 

                push(&realPath,cur);

                push(&path,cur);

                //直接跳出函数(而不只是跳出这个循环 ) 

                return true;

            }

            else if(cur.val == -1) {//当前位置的四面或为墙或已走过

                 //删除真实路径的栈顶元素

                 pop(&realPath);

                 cur = getTop(&realPath);//令cur指向栈顶元素

             }

        }

       else {//如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向

            cur = getNext(cur);

            if (cur.val == -1) {//仍不通,删除真实路径的栈顶元素

               pop(&realPath);

               cur = getTop(&realPath);//令cur指向栈顶元素

            }

       }

    } while (cur.x != end.x || cur.y != end.y);

}

//打印迷宫路径

void printMazePath(MStack *s) {//为了安全,这里不传MStack的地址,以防在遍历的过程中把它们的top或base的值也修改了 

 /*注:这种方法实际是倒序打印出路径,让人看着别扭,所以我用下面的方法"倒序遍历这个栈 ' 

while (s->top != s->base) {

MStackElem e = *(s->top-1);

printf("maze[%d][%d]----->",e.x,e.y);

(s->top)--;

    }

    */

     MStackElem e;

while (s->base < (s->top-1)) {

e = *(s->base);//先指向栈底元素,以后依次向上增1 

printf("maze[%d][%d]----->",e.x,e.y);

(s->base)++;

     }

     //最后一个结点没有后继,所以不再输出"------>"

e = *(s->base);

     printf("maze[%d][%d]",e.x,e.y);

}

main(){

      //初始化栈

    initStack(&realPath);

    initStack(&path); 

    getMazePath();

    printf("The path of through the maze is:\\n\\n");

    printMazePath(&realPath);

    getchar();

}下载本文