migong.c

是软件技术数据结构方向的现成的课程设计

#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#define N 10

typedef struct lnode                               /*定义结构体*/
{
int x;
int y;
int d;
    struct lnode *next;
}lnode,*link;                       

typedef struct                                   /*定义堆栈*/
{
link base;
link top;
}*stack;                          

stack creat()                              /*堆栈分配空间*/
{
stack s;
s->base=(link)malloc(sizeof(lnode));        /*利用malloc函数分配空间*/


if(s->base==NULL)                             /*堆栈满*/
{
  printf("Overflow");
  exit(0);
}
s->base->x=50;                                  /*给base分配空间*/
s->base->y=50;
s->base->d=50;
s->base->next=NULL;
s->top=s->base;
return s;
}                                              

stack push(stack s,int r,int c,int D)              /*进栈*/
{                                                  
link p;                                              /*定义p并分配空间*/
p=(link)malloc(sizeof(lnode));
p->x=r;                                                /*给栈中的x,y,z的data赋值*/
p->y=c;
p->d=D;
p->next=s->top;
s->top=p;

return s;
}                                                                  

stack pop(stack s)
{
link p;
if(s->top==s->base)
{
  printf("It's empty.\nthere is no access to enter.\n");
  exit(0);
}
p=s->top;
s->top=s->top->next;
free(p);
return s;
}


stack found(stack s,int a[N][N],int b[4][2])
{
int r=1,c=1,D=0,i=0,D0=0,f=0;
while(r!=8|c!=9)
{
  if(a[r][c]==0)
  {
   if(f)                           /*当不能沿栈顶结点所指的方向走时,f为真*/
    s->top->d=D;
   D0=(D+2)%4;                     /*D0为准备退回时的方向*/
   D=0;                       /*指该元素指向下一个元素的方向*/

   s=push(s,r,c,D);
   a[s->top->x][s->top->y]=5;      /*入栈的元素，对应的数组元素做相应的改变*/
   f=0;
   if(D==D0)
   {
    D=D+1;
    f=1;
   }
  }
  else
  {
   f=1;
   D=D+1;
   if(D==D0)
   {
    D=D+1;
   }

   if(D>3)
   {
    a[s->top->x][s->top->y]=2;     /*出栈的元素，对应数组元素做相应的改变*/
    s=pop(s);
    D=s->top->next->d;
    D0=(D+2)%4;

   }
  }
  for(i=0;i<4;i++)
                if(i==D)                  /*根椐D的方向来确定下一结点的坐标*/
  {
   r=s->top->x+b[i][0];
   c=s->top->y+b[i][1];
   break;
  }
}
if(s->top!=s->base)                                  /*栈非空则输出*/
  printf("success to find!\n");
else
  printf("No access to go out\n");
return s;

}

void print(int a[N][N])
{
int i,j;
for(i=0;i<N;i++)
{
  for(j=0;j<N;j++)
   printf("%3d",a[i][j]);
  printf("\n\n");
}
}

void main()
{
stack s;
int a[N][N]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,1,1,1,1,1,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
int b[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
s=creat();
printf("the map is:\n");
print(a);
printf("please enter to find\n");
getch();
s=found(s,a,b);
printf("the result map is:\n");
print(a);
getch();
}