原创 迷宫求解堆栈实现

        else              printf("  ");

    如图所示效果：

    程序见第三部分。

4.进入下一位置

         PosType NextPos(PosType CurPos, int Dir);  //进入下一位置时按顺时针方向

                                                    //向下一位置探索

    程序见第三部分。 

5.堆栈操作，包括创建，入栈，出栈，判空。

  Status InitStack(SqStack &S);         //创建一个空栈S

  Status Push(SqStack &S,SElemType &a); //插入新元素a

  Status Pop(SqStack &S,SElemType &a);  //删除栈顶元素，a返回其值

  Status StackEmpty(SqStack S);         //检查是否空栈

    程序见第三部分。

三、源程序及注释：

#include<stdio.h>

#include<stdlib.h>

/**************************************************************

                        数据定义

**************************************************************/

typedef enum { ERROR, OK } Status;

typedef struct         

{

       int row;  //row表示“行”号

       int line;   //line表示“列”号

}PosType;     //位置的元素类型

typedef struct    

{

       int          ord;       //该通道在路径上的“序号”              

       PosType seat;      //通道块在迷宫中的“坐标位置”

       int          di;         //从此通道走向下以通道块的“方向”

}SElemType;              //栈的元素类型

typedef struct

{

       SElemType * base;

       SElemType * top;

       int        stacksize;

}SqStack;

/**************************************************************

                        函数原型说明

**************************************************************/

Status InitStack(SqStack &S);                         //创建一个空栈S

Status Push(SqStack &S,SElemType &a);        //插入新元素a

Status Pop(SqStack &S,SElemType &a);          //删除栈顶元素，a返回其值

Status StackEmpty(SqStack S);                       //检查是否空栈

Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end); //找通路

void Initmaze(int maze[12][12],int size);             //初始化迷宫

void printmaze(int maze[12][12],int size);            //显示迷宫

Status Pass(int maze[12][12],PosType CurPos);       //判断当前位置是否可通

void Markfoot(int maze[12][12], PosType CurPos);  //标记当前位置不可通

PosType NextPos(PosType CurPos, int Dir);           //进入下一位置

void printpath(int maze[12][12],SqStack S,int size);  //显示通路

/**************************************************************

                           主函数

**************************************************************/

void main (void)

{   

       SqStack S;

       int         size;                //正方形迷宫尺寸

       int         maze[12][12];  //存储迷宫内路径可通情况

       for(int n=0;n<10;n++)

      {

             printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):\n"); //设置迷宫大小

             scanf("%d",&size);if(size<1 || size>10){printf("输入错误!");return;}

             Initmaze(maze,size);           //初始化迷宫 

             printmaze(maze,size);         //显示所创建的迷宫

             PosType start,end;             //设置入口和出口

             printf("输入入口行坐标和列坐标:");scanf("%d",&start.row);scanf("%d",&start.line);

             printf("输入出口行坐标和列坐标:");scanf("%d",&end.row);scanf("%d",&end.line);

             if(MazePath(maze,S,start,end))   //若有通路，显示通路

                   printpath(maze,S,size);

             else printf("找不到通路!\n\n");

      }

}

/**************************************************************

 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中           

**************************************************************/

Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end) 

{  

       PosType curpos;

       int curstep;

       SElemType e;

       InitStack(S);

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

       curstep = 1;                    // 探索第一步

       do 

      {

              if (Pass(maze,curpos))     // 当前位置可通过，即是未曾走到过的通道块

             { 

                    Markfoot(maze,curpos);   // 留下足迹

                    e.di =1;

                    e.ord = curstep;

                    e.seat= curpos;

                    Push(S,e);            // 加入路径

                    if (curpos.row==end.row && curpos.line==end.line)  

                          return OK;     // 到达终点（出口）

                    curpos = NextPos(curpos, 1);   // 下一位置是当前位置的东邻

                    curstep++;           // 探索下一步

             } 

             else                           // 当前位置不能通过

            {

                     if (!StackEmpty(S)) 

                    {

                            Pop(S,e);

                            while (e.di==4 && !StackEmpty(S))  

                           {

                                  Markfoot(maze,e.seat); // 留下不能通过的标记，并退回一步

                                  Pop(S,e);    

                           } 

                           if (e.di<4) 

                          {

                                  e.di++;          // 换下一个方向探索

                                  Push(S, e);  

                                  curpos = NextPos(e.seat, e.di); // 当前位置设为新方向的相邻块    

                          } 

                   } 

            } 

      } while (!StackEmpty(S));

      return ERROR;

} 

/**************************************************************

                           初始化迷宫

**************************************************************/

void Initmaze(int maze[12][12],int size)

{

       char select;                                                   

       printf("选择创建方式  A:自动生成  B:手动创建\n");       

       label:scanf("%c",&select);

       if(select=='a'||select=='A')  //自动生成

      {

            for(int i=0;i<size+2;i++)maze[0]=1;