瑞星卡卡安全论坛

利用数据结构中的运行栈实现（里面函数参考《数据结构第二版》清华大学出版社）数据结构定义完全参考这本书。算法也参考这本书
#include<stdio.h>
#include<stdlib.h>
#define SIS 100/*运行栈一次分配的空间*/
#define N 10/*迷宫的最大坐标，根据迷宫大小修改*/
struct sit/*数据结构定义迷宫坐标*/
{
    int seatx;
    int seaty;
};
struct finds
{
    int ord;/*路径标号*/
    struct sit *seat;
    int di;/*下一步试探的方向，上下左右用1，2，3，4来表示*/
};
struct stack/*定义运行栈*/
{
    struct finds *base;
    struct finds *top;
    int size;
};
void initstack(struct stack *s)/*构造运行栈*/
{
    struct finds *link,*end;
    s->base=s->top=link=(struct finds *)malloc(SIS*sizeof(struct finds));
    end=link+SIS-1;
    for(;link<=end;link++)
        link->seat=(struct sit *)malloc(sizeof(struct sit));
    s->size=SIS;
}
void push(struct stack *s,struct finds *find)/*把*find压入栈s，栈定指针加1*/
{
    struct finds *link,*end;
    if(s->top-s->base>=s->size)
    {
        s->base=(struct finds *)realloc(s->base,(s->size+SIS)*sizeof(struct finds));
        link=s->base+s->size;
        s->top=s->size+s->base;
        s->size+=SIS;
        end=s->base+s->size;
        for(;link<=end;link++)
            link->seat=(struct sit *)malloc(sizeof(struct sit));
       
    }
    s->top->ord=find->ord;
    s->top->seat->seatx=find->seat->seatx;
    s->top->seat->seaty=find->seat->seaty;
    s->top->di=find->di;
    s->top++;
}
void pop(struct stack *s,struct finds *find)/*栈顶元素*find出栈*/
{
    s->top--;
    find->ord=s->top->ord;
    find->seat->seatx=s->top->seat->seatx;
    find->seat->seaty=s->top->seat->seaty;
    find->di=s->top->di;
}
void footprint(int a[N][N],struct sit *seat)/*走过的路经留下足迹，也就是将坐标值为非零*/
{
    int i,j;
    i=seat->seatx;
    j=seat->seaty;
    a[j]=-1;
}
void nextpos(struct sit *find,struct sit *seat,int di)/*规定下一步试探的方向*/
{
    int i,j;
       switch(di)
                {case 1:i=seat->seatx;j=seat->seaty+1;break;
                 case 2:i=seat->seatx+1;j=seat->seaty;break;
                 case 3:i=seat->seatx;j=seat->seaty-1;break;
                case 4:i=seat->seatx-1;j=seat->seaty;break;
                }
         find->seatx=i;
         find->seaty=j;
}
int pass(struct sit *curpos,int a[N][N])/*判断改足迹是否走过，走过为1否则为0，进行下一步试探*/
{
    int i,j;
    i=curpos->seatx;
    j=curpos->seaty;
    if(a[j]==0)return 1;
    else return 0;
}

print(struct stack *s)/*输出结果，输出结果不太好看，但这不是程序的关键部分，你可以自己修改输出方法*/
{    do
    {
        printf("(%d,%d)",s->base->seat->seatx,s->base->seat->seaty);
        s->base++;
    }while(s->top!=s->base);
}
void main()
{
    struct stack *s;
    struct finds *find,*e;
    struct sit *start,*end,*curpos;
    int curstep=1,a[N][N],i,j,n,m,pa;
    char c[N][N];
     s=(struct stack *)malloc(sizeof(struct stack));
     find=(struct finds *)malloc(sizeof(struct finds));
     e=(struct finds *)malloc(sizeof(struct finds));
     start=(struct sit *)malloc(sizeof(struct sit));
     end=(struct sit *)malloc(sizeof(struct sit));
     curpos=(struct sit *)malloc(sizeof(struct sit));
     initstack(s);
     puts("在使用前请仔细阅读使用说明");
     while(1)
     {
         printf("请输入迷宫的长和宽（n，m）");
         pa=scanf("%d,%d",&n,&m);
         if(pa!=2||n>81||m>81||n<=0||m<=0)puts("输入数据错误,请重新输入");
           else break;
     }

     printf("请输入你的迷宫（0代表路径,连续输入）\n");
     for(i=0;i<n;i++)
         scanf("%s",c);
     for(i=0;i<n;i++)
              for(j=0;j<m;j++)
               a[j]=c[j]-48;
             while(1)
             {
                 printf("进入迷宫的位置（n，m）");
                 scanf("%d,%d",&curpos->seatx,&curpos->seaty);
                 if(curpos->seatx>81||curpos->seaty>81||curpos->seatx<=0||curpos->seaty<=0||curpos->seatx>=n||curpos->seatx>=m||curpos->seaty>=m||curpos->seaty>=n)puts("输入数据错误,请重新输入");
                 else break;

             }
             while(1)
                 {
                     printf("走出迷宫的位置（n，m）");
                 scanf("%d,%d",&end->seatx,&end->seaty);
                 if(end->seatx>81||end->seaty>81||end->seatx<=0||end->seaty<=0||end->seatx>=n||end->seatx>=m||end->seaty>=n||end->seaty>=m)puts("输入数据错误,请重新输入");
                 else break;
                 }

           do
        {
            if(pass(curpos,a))
                    {footprint(a,curpos);
                           e->ord=curstep;
                           e->seat=curpos;
                           e->di=1;
                           push(s,e);
                           if(curpos->seatx==end->seatx&&curpos->seaty==end->seaty)break;
                            nextpos(curpos,e->seat,1);
                             curstep++;
                    } 
            else  {
                        if(e->di<4){pop(s,e);e->di++,push(s,e);nextpos(curpos,e->seat,e->di);}
                        else  if(e->di==4)
                        {
                            pop(s,e);pop(s,e);push(s,e);e->di++;
                            if(e->di>4)pop(s,e);
                            nextpos(curpos,e->seat,e->di);
                        }
                    }
           
        }while(1);
    puts("输出路径为");
    print(s);
    puts("\n");
   
}

该被帖于【2003-1-5 0:02:08】被【黑马之王】修改

该被帖于【2003-1-5 0:13:30】被【黑马之王】修改