12-2.c

《C语言程序设计实训》源代码

/*12-2.c*/
#define STACK_INIT_SIZE 100
#define STACKINCMENT 10
#define K 100
typedef struct{
	   selemtype *base;
	   selemtype *top;
	   int stacksize;
	   }sqstack;
sqstack s;
int initstack(sqstack *s)                          /*创建堆栈函数；*/
{
  (*s).base=(selemtype *)malloc(STACK_INIT_SIZE*sizeof(selemtype));
  if(!(*s).base) exit(OVERFLOW);
  (*s).top=(*s).base;
  (*s).stacksize=STACK_INIT_SIZE;
  return OK;
}
int destroystack(sqstack *s)                       /*摧毁栈函数；*/
{
  (*s).top=NULL;
  (*s).stacksize=0;
  free((*s).base);(*s).base=NULL;
  return OK;
}
int clearstack(sqstack &s)                   /*清空栈函数；*/
{
  s.top=s.base;
  s.stacksize=STACK_INIT_SIZE;
  return OK;
}
int stackempty(sqstack s)                    /*检测栈是否空函数；*/
{
  if(s.top==s.base) return TRUE;
  else return FALSE;
}
int stacklength(sqstack s)                   /*求栈长函数；*/
{
  if(s.top>s.base) return ((int)(s.top-s.base));
  else return 0;
}
int gettop(sqstack s,selemtype &e)          /*求栈顶元素函数；*/
{
  if(s.top==s.base) return ERROR;
  e=*(s.top-1);
  return OK;
}
int push(sqstack &s,selemtype e)            /*入栈函数；*/
{
  if(s.top-s.base>=s.stacksize)
  {
	 s.base=(selemtype*)realloc(s.base,(s.stacksize+STACKINCMENT)*sizeof(selemtype));
	 if(!s.base) exit(OVERFLOW);
	 s.top=s.base+s.stacksize;
	 s.stacksize+=STACKINCMENT;
  }
  *s.top++=e;
  return OK;
}
int pop(sqstack &s,selemtype &e)             /*出栈函数；*/
{
  if(s.top==s.base) return ERROR;
  e=*--s.top;
  return OK;
}
int stacktraver(sqstack s,int (*visit)(selemtype *se))/*对栈元素作visit为*/
{                                                    /*入口的函数规定的操*/
  selemtype p;                                         /*作；*/
  int result;
  if(s.top==s.base) return ERROR;
  p=s.base;
  while(!(p==s.top))
  {
   result=(*visit)(p);
   p++;
  }
  return OK;
}
int pass(postype curpos)                /*判断当前位置是否可通过函数；*/
{
  if(maze[curpos.x][curpos.y].td==1&&
  maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0)
	 return 1;
  else return 0;
}
void footprint(postype curpos)         /*给当前位置作探察标记；*/
{
  maze[curpos.x][curpos.y].foot=1;
}
void markprint(postype seat)           /*给当前位置作不可通过标记；*/
{
  maze[seat.x][seat.y].mark=-1;
}
postype nextpos(postype seat,int di)         /*按给定方向找出下一探察位置*/
{
  switch(di) {
  case 1: seat.y++;return(seat);
  case 2: seat.x++;return(seat);
  case 3: seat.y--;return(seat);
  case 4: seat.x--;return(seat);
  default: exit(1);
  }
}
int mazepath(mazetype maz,postype start,postype end) /*找迷宫路径函数；*/
{
  postype curpos;
  int curstep;
  selemtype e;
  initstack(&s);
  curpos=start;curstep=1;
  do{
	 if(pass(curpos)){
		footprint(curpos);
		e.ord=curstep;e.seat=curpos;e.di=1;
		setcolor(BLUE);
		circle(100+20*curpos.y+9+K,100+20*curpos.x+9,8);
		delay(300);
		setcolor(YELLOW);
		circle(100+20*curpos.y+9+K,100+20*curpos.x+9,8);
		push(s,e);
		if(curpos.x==end.x&&curpos.y==end.y) return(TRUE);
		curpos=nextpos(curpos,1);
		curstep++;
	 }
	 else {
		if(!stackempty(s)) {
		   pop(s,e);
		   while(e.di==4&&!stackempty(s))
			  {
				markprint(e.seat);pop(s,e);
				setcolor(BLUE);
				circle(100+20*e.seat.y+9+K,100+20*e.seat.x+9,8);
				delay(300);
				setcolor(YELLOW);
				circle(100+20*e.seat.y+9+K,100+20*e.seat.x+9,8);
			  }
		   if(e.di<4) {
				e.di++;push(s,e);
				curpos=nextpos(e.seat,e.di);
		   }
		}
	 }
  }while(!stackempty(s));
 return (FALSE);
}