数据结构栈的应用(迷宫求解)

迷宫求解

任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；

源代码：

#include

#include

/*数据定义*/

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 x,int y);            //初始化迷宫

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

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 x,int y,PosType start,PosType end); //显示通路

/*主函数*/

void main (void)

{

    PosType start,end;

    int t=0;

    SqStack S;

    int maze[12][12];     

    do{

        if(t!=0)

        printf("\\n");

        for(int i=0;i<20;i++)

        {

            printf("* ");

        }

        if(t==0)

        {    

            printf("\\n*\欢迎来到迷宫世界\      * \\n");

            printf("*\ 1.设置迷宫\\      * \\n");

        }

        else

        {

            printf("\\n* 请继续选择：\\\      * \\n");

            printf("*\ 1.设置迷宫\\      * \\n");

        }

        printf("*\ 2.设置迷宫路径\\      * \\n");

        printf("*\ 3.输出迷宫通路路径\      * \\n");

        printf("*\ 4.结束\\\      *\\n");

        t++;

        for(int j=0;j<20;j++)

        {

            printf("* ");

        }

        printf("\\n");

        int s;

        printf("请选择：");

        scanf("%d",&s);

        int aa;    int x,y;

        switch(s) 

        {

        case 1://1.初始化迷宫

            aa=1;

            printf("迷宫设置：请输入\\n"); //设置迷宫大小

            do

            {

                printf("行X(x<10)=");

                scanf("%d",&x);

                printf("列Y(y<10)=");

                scanf("%d",&y);

                if(x<1 || x>10||y<1 || y>10)

                {

                    printf("输入错误!\\n");

                }

            }while(x<1 || x>10||y<1 || y>10);        

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

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

            break;

        case 2://寻找迷宫路径

            if(aa==1)

            {

                aa=2;                //设置入口和出口

                do{

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

                    if(start.row>x)

                        printf("输入错误!\\n");

                }while(start.row>x);

                do{

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

                    if(start.line>y)

                        printf("输入错误!\\n");

                }while(start.line>y);

                do{

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

                    if(end.row>x)

                        printf("输入错误!\\n");

                }while(end.row>x);

                do{

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

                    if(end.line>y)

                        printf("输入错误!\\n");

                }while(end.line>y);    

            }

            else

                printf("请先初始化迷宫！\\n");    

            printf("\\n所设置入口坐标为(%d,%d),出口坐标为(%d,%d).\\nstart.row,start.line,end.row,end.line);    

            break;

        case 3://输出此迷宫通路路径

            if(aa==2)

            {

                aa=3;

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

                    printpath(maze,S,x,y,start,end);

                else

                    printf("\\n抱歉，找不到通路!\\n\\n");

            }

            else

                printf("请先初始化迷宫并寻找路径！\\n");

            break;

        case 4:exit(0); 

            break;

        default:

            exit(0);

    }       

    }while(1);

}

/*若迷宫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;

} 

/*初始化迷宫     时间复杂度：n^2*/

void Initmaze(int maze[12][12],int x,int y)

{

    char select; 

    do{

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

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

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

          {                

              for(int i=1;i              {

                  for(int j=1;j                      maze[i][j]=rand()%2;                

              }            

              break;             

          }

          else if(select=='b'||select=='B') //手动设置

          {

              printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\\nx,y);

              for(int i=1;i              {

                  for(int j=1;j                      scanf("%d",&maze[i][j]);

                  maze[i][y+1]=1;

              }

              for(i=0;i              break; 

          }

          else if(select=='\\n')goto label;      //排除Enter键的影响

          else 

              if(select!='b'||select!='B'||select!='a'||select!='A')

                  printf("输入错误!\\n");

    }while(select!='b'||select!='B'||select!='a'||select!='A');

}

/*显示迷宫     时间复杂度：n^2*/

void printmaze(int maze[12][12],int x,int y)

{

    printf("\\n\\n");

    printf("显示所建的迷宫(#表示墙):\\n");

    printf("%c ",'#');

    printf("%c ",'y');

    for(int j=1;j        printf("%d ",j);

        printf("%c ",'#');

     printf("\nx ");

    for(int i=1;i        printf("%c ",'#');

     printf("\\n");        

    for(i=1;i    { 

        if(i            printf("%d ",i);        

        else

            printf("%c ",'#');

        printf("%c ",'#');

        for(int j=1;j        {

            printf("%d ",maze[i][j]);

        }

        printf("%c",'#');

        printf("\\n");

    }

    for(i=0;i}

/*输出路径      时间复杂度：n^2*/

void printpath(int maze[12][12],SqStack S,int x,int y,PosType start,PosType end)

{ 

    printf("\\n\\n\\001通路路径:\\n");

    SElemType * p=S.base;

    while(p!=S.top)

    {

     maze[p->seat.row][p->seat.line]=2;      //标记为路径中的点

        p++;

    }

    printf("\\001路径图为：\\n");

    printf("%c ",'#');

    printf("%c ",'y');

    for(int j=1;j        printf("%d ",j);

        printf("%c ",'#');

        printf("\nx ");   

    for(int m=1;m        printf("%c ",'#');

    printf("\\n");

    for(int i=1;i    { 

            if(i            printf("%d ",i);        

        else

            printf("%c ",'#');

        printf("%c ",'#');

        for(int j=1;j        {

            if(maze[i][j]==2)

            {if(i==start.row&&j==start.line||i==end.row&&j==end.line){

                if(i==start.row&&j==start.line)

                    printf("i ");

                if(i==end.row&&j==end.line)

                    printf("o ");}

                else

                printf("%c ",' ');}

            else 

                printf("%c ",'#');

        }

        printf("%c ",'#');

        printf("\\n");

    }

        for(i=0;i                printf("%c ",'#');

            printf("\\n\\n");

        printf("\\001路径线路为：\\n");

        SqStack M;    

        InitStack(M);

        SElemType a;

        while (!StackEmpty(S))

        {     

            Pop(S,a);

            Push(M,a);

        }

        while (!StackEmpty(M))

        {     

            Pop(M,a);

            printf("(%d,%d)a.seat.row,a.seat.line);

        }

        printf("\\n");    

        printf("路径输出成功！\\n");

}

/* 判断当前位置是否可通*/

Status Pass(int maze[12][12],PosType CurPos)

{

    if(maze[CurPos.row][CurPos.line]==0)

        return OK;                              // 如果当前位置是可以通过，返回1

    else

        return ERROR;                        // 其它情况返回0

}

/* 标记当前位置不可通*/

void Markfoot(int maze[12][12],PosType CurPos)

{

    maze[CurPos.row][CurPos.line]=1;

}

/*进入下一位置*/

PosType NextPos(PosType CurPos, int Dir) 

{

    PosType ReturnPos; 

    switch (Dir) 

    {

    case 1:

        ReturnPos.row=CurPos.row;

        ReturnPos.line=CurPos.line+1;

        break;

    case 2:

        ReturnPos.row=CurPos.row+1;

        ReturnPos.line=CurPos.line;

        break;

    case 3:

        ReturnPos.row=CurPos.row;

        ReturnPos.line=CurPos.line-1;

        break;

    case 4:

        ReturnPos.row=CurPos.row-1;

        ReturnPos.line=CurPos.line;

        break;

    }

    return ReturnPos;

}

/*创建一个空栈S*/

Status InitStack(SqStack &S)

{

    S.base=(SElemType *)malloc(100*sizeof(SElemType));

    if(!S.base)return ERROR;

    S.top=S.base;

    S.stacksize=100;

    return OK;

}

/*插入新元素a*/

Status Push(SqStack &S,SElemType &a)

{

    *S.top++=a;

    return OK;

}

/* 删除栈顶元素，a返回其值*/

Status Pop(SqStack &S,SElemType &a)

{

    if(S.top==S.base)return ERROR;

    a=*--S.top;

    return OK;

}

/*检查是否空栈*/

Status StackEmpty(SqStack S)

{

    if(S.top==S.base)return OK;

    return ERROR;

}