用C语言来写迷宫问题(深搜,链栈)

这学期老师非得让用C语言写一个栈来解决迷宫可解性的问题,让我们这些学过一些stl的比较难以接受,明明两行就能解决的函数定义非要搞得那么麻烦....

用C语言来写顺栈的话,就是用数组模拟,链栈可以用链表,以链头当栈顶.

话不多说,直接上代码;

顺栈:

#include 
#include
#define MAXN 20000
int migong[101][100];
int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
typedef struct{
int x;
int y;
int d;
}date;
struct seq
{
    int t;
    date s[MAXN];
};
typedef struct seq * pseq;
pseq creat_seq()
{
    pseq pseqa;
    pseqa=(pseq)malloc(sizeof(seq));
    if(pseqa==NULL)
        printf("malloc error!\n");
    else
        pseqa->t=-1;
    return pseqa;
}
void push_seq(pseq pseqa,date x)
{
    if(pseqa->t>MAXN)
        printf("error 2!\n");
    else
    {
        pseqa->t++;
        pseqa->s[pseqa->t]=x;
    }
}
int empty_seq(pseq pseqa)
{
    if(pseqa->t==-1)
        return 1;
    else
        return 0;
}
void pop_seq(pseq pseqa)
{
    if(!empty_seq(pseqa))
        pseqa->t--;
}
date top_seq(pseq pseq)
{
    return pseq->s[pseq->t];
}
int output_seq(pseq pseqa)
{
    date n;
    if(empty_seq(pseqa))
        return  0;
    n.x=pseqa->s[pseqa->t].x;
    n.y=pseqa->s[pseqa->t].y;
    pop_seq(pseqa);
    output_seq(pseqa);
    printf("(%d %d)",n.x,n.y);
}
int path(int migong[][100],int dirction[][2],int x1,int y1,int x2,int y2,int m,int n,pseq st)   //x1,为起点纵坐标，x2为终点的，m行，n列
{
    int i,j,k,g,h,b,x0,y0;
    date a;
    if(st==NULL)
        return 0;
    migong[x1][y1]=2;
    a.x=x1;
    a.y=y1;
    a.d=-1;
    push_seq(st,a);
    if(x1==x2&&y1==y2)
        return 1;

    while(st->t!=-1)
    {
        a=top_seq(st);
        x0=a.x;
        y0=a.y;
        k=a.d+1;
        while(k<=3)
        {
            g=x0+direction[k][0];
            h=y0+direction[k][1];
            if(g>=0&&g<=n-1&&h>=0&&h<=m-1&&migong[g][h]==0)
                if(path(migong,direction,g,h,x2,y2,m,n,st)==1)
                    return 1;

            k=k+1;
        }
        pop_seq(st);
    }
    return 2;
}
int main()
{
    int x1,x2,y1,y2,m,n,i,j;
    pseq st;
    scanf("%d %d",&m,&n);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    for(i=0;i<=m-1;i++)
        for(j=0;j<=n-1;j++)
        {
            scanf("%d",&migong[i][j]);
        }
    st=creat_seq();
    if(path(migong,direction,x1,y1,x2,y2,m,n,st)==1)
        output_seq(st);
    else
        printf("No Path!");
    return 0;
}

链栈:

#include 
#include
#define MAXN 20000
int migong[101][100];
int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
typedef struct{
int x;
int y;
int d;
}date;
struct Node
{
    date data;
    struct Node *next;
};
typedef struct{
    struct Node *top;
}stk;
stk *creat_seq()
{
    stk *p=NULL;
    p=(stk*)malloc(sizeof(stk));
    if(p!=NULL)
        p->top=NULL;
    else
        printf("out of space!\n");
    return p;
}
int push_seq(stk *pseqa,date x)
{
    struct Node *pnew=NULL;
    pnew=(struct Node*)malloc(sizeof(struct Node));
    if(pnew!=NULL)
    {
        pnew->data=x;
        pnew->next=pseqa->top;
        pseqa->top=pnew;
        return 1;
    }
    printf("out of space!\n");
    return 0;
}
int empty_seq(stk *pseqa)
{
    if(pseqa->top==NULL)
        return 1;
    else
        return 0;
}
date pop_seq(stk *pseqa)
{
    date n;
    struct Node *ptemp=NULL;
    n=pseqa->top->data;
    ptemp=pseqa->top;
    pseqa->top=pseqa->top->next;
    free(ptemp);
    return n;
}
date top_seq(stk *pseq)
{
    return pseq->top->data;
}
int output_seq(stk* pseqa)
{
    date n;
    if(empty_seq(pseqa))
        return  0;
    n.x=pseqa->top->data.x;
    n.y=pseqa->top->data.y;
    pop_seq(pseqa);
    output_seq(pseqa);
    printf("(%d %d)",n.x,n.y);
}
int path(int migong[][100],int dirction[][2],int x1,int y1,int x2,int y2,int m,int n,stk* st)   //x1,为起点纵坐标，x2为终点的，m行，n列
{
    int i,j,k,g,h,b,x0,y0;
    date a;
    if(st==NULL)
        return 0;
    migong[x1][y1]=2;
    a.x=x1;
    a.y=y1;
    a.d=-1;
    push_seq(st,a);
    if(x1==x2&&y1==y2)
        return 1;

    while(!empty_seq(st))
    {
        a=top_seq(st);
        x0=a.x;
        y0=a.y;
        k=a.d+1;
        while(k<=3)
        {
            g=x0+direction[k][0];
            h=y0+direction[k][1];
            if(g>=0&&g<=n-1&&h>=0&&h<=m-1&&migong[g][h]==0)
                if(path(migong,direction,g,h,x2,y2,m,n,st)==1)
                    return 1;

            k=k+1;
        }
        if(!empty_seq(st))
        pop_seq(st);
    }
    return 2;
}
int main()
{
    int x1,x2,y1,y2,m,n,i,j;
    stk *st=NULL;
    scanf("%d %d",&m,&n);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    for(i=0;i<=m-1;i++)
        for(j=0;j<=n-1;j++)
        {
            scanf("%d",&migong[i][j]);
        }
    st=creat_seq();
    if(path(migong,direction,x1,y1,x2,y2,m,n,st)==1)
        output_seq(st);
    else
        printf("No Path!");
    return 0;
}

如有雷同,纯属巧合.