回 帖 发 新 帖 刷新版面

主题:算法3.3 P51页结合P46,47页算法(迷宫)

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

struct complex{
    int i;
    int j;
}

struct SqStack{
    complex *base;
    complex *top;
    int stacksize;
};

bool InitStack(SqStack &S){
    S.base=(complex*)malloc(STACK_INIT_SIZE*sizeof(complex));
    if(!S.base)return false;
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return true;
}
bool GetTop(SqStack &S,complex &e)
{
    if(S.top==S.base) return false;
    e=*(S.top-1);
    return true;
}
bool Push(SqStack &S,complex e)
{
    if((S.top-S.base)>=S.stacksize)
    {
    S.base=(complex*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(complex));
    if(!S.base)return false;
    S.stacksize+=STACKINCREMENT;
    }
    *S.top++=e;
    return true;
}
bool Pop(SqStack &S,complex &e,int &a[10][10])
{
    if(S.top==S.base)return false;
    a[(S.top-1)->i][(S.top-1)->j]=1;
    e=*S.top--;
    return true;
}
void DestoryStack(SqStack &S)
{
    if(S.base!=NULL)
    free(S.base);
}
void ClearStack(SqStack &S)
{
    S.top=S.base;
}
bool StackEmpty(SqStack S)
{
    if(S.base==S.top)
        return true;
    else
        return false;
}
bool MazePath(int &a[10][10],complex start,complex end)
{
    int col=1,row=1;
    SqStack S,S1;
    InitStack(SqStack &S);
    InitStack(SqStack &S1);
    if(start.i-end.i)
        col=-1;
    if(start.j-end.j)
        row=-1;
    complex p=start,e;
    bool flag=true;
    while(p!=end&&flag)
    {
        flag=false;
        if(!a[p.i+col][p.j])
        {
            p.i=p.i+col;
            Push(S,p);
            flag=true;
        }
        else
            if(!a[p.i][p.j+1])
            {
                p.j=p.j+row;
                Push(S,p);
                flag=true;
            }
            else
            {
                flag=Pop(S,e,a);
            }
    }
    while(!StackEmpty(SqStack S))
    {
        GetTop(S,e);
        Push(S1,e);
        Pop(S,e,a);
    }
    while(!StackEmpty(SqStack S1))
    {
        GetTop(S1,e);
        printf("\n %d %d",e.i,e.j);
        Pop(S1,e,a);
    }
    DestoryStack(S1);
    DestoryStack(S);

}

//////////////
void main()
{
    int a[10][10],i,j;
    for(i=0; i<10; i++)
    {
        for(j=0; j<10; j++)
        {
            a[i][j]=0;
        }
    }
    for(i=0; i<10; i++)
    {
        a[1][i]=1;
        a[9][i]=1;
    }
    for(i=1; i<10; i++)
    {
        a[i][0]=1;
        a[i][9]=1;
    }
    a[1][3]=a[2][3]=a[1][7]=a[2][7]=a[3][5]=a[3][6]=a[4][2]=a[4][3]=a[4][4]=a[5][4]=a[6][2]=a[6][6]=a[7][2]=a[7][3]=a[7][4]=a[7][6]=a[7][7]=a[8][1]=1;


    complex start,end;
    bool flag=false;
    do
    {
        printf("输入开始位置:(%d %d)");
        scanf("%d %d",&start.i,&start.j);
        if(a[start.i][start.j])
        {
            printf("开始位置不能为1(那是墙)\n");
        }
        else
            flag=true;
    }while(!flag);
    flag=false;
    do
    {
        printf("输入开始位置:(%d %d)");
        scanf("%d %d",&end.i,&end.j);
        if(a[end.i][end.j])
        {
            printf("开始位置不能为1(那是墙)\n");
        }
        else
            flag=true;
    }while(!flag);
    MazePath(a,start,end);
}

回复列表 (共3个回复)

沙发

这是严蔚敏老师写的数据结构中的算法3.3 P51页结合P46,47页算法(迷宫)

板凳

不错

3 楼

不过这只会往右和下方找,不能往上找.:)

我来回复

您尚未登录,请登录后再回复。点此登录或注册