迷宫求解.txt

这是有关数据结构的例程序

definition.h
========================================================
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10  //存储空间分配增量

typedef struct{
unsigned ord, x, y; //通道块在路径上的“序号”，通道快在迷宫中的“坐标位置”
short di;  //从此通道块走向下一通道块的“方向”
}ElemType;

typedef struct{
ElemType *top, *base; //栈顶指针和栈底指针
unsigned stacksize;   //当前已分配的存储空间，以元素为单位
}SqStack;

int InitStack(SqStack *);//创建一个空栈
int Push(SqStack *, ElemType);//插入栈顶
ElemType Pop(SqStack *);      //删除栈顶元素
void NextPos(unsigned *, unsigned *, short);//定位下一个位置
====================================================================

function.c
===============================================================
#include<stdio.h>
#include<malloc.h>
#include"definition.h"

int InitStack(SqStack *S) //创建一个空栈
{ S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) );
if(!S->base) //空间分配失败
  return 1;
//空间分配成功
S->top=S->base;//置栈顶指针
S->stacksize=INIT_SIZE;//栈大小
return 0;
}

int Push(SqStack *S, ElemType e) //插入栈顶
{ if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间
  S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof

(ElemType) );
  if(!S->base)//分配失败，返回1
   return 1;
  //分配成功
  S->top = S->base + S->stacksize;//置栈顶指针
  S->stacksize += INCREMENT;//栈大小
}

*S->top++ = e;//接收输入后，S->top指向栈顶元素的下一个位置

return 0;
}

ElemType Pop(SqStack *S) //删除栈顶元素
{ if(S->base == S->top){//空栈，返回0
  S->base->di=0;
  return *S->base;
}
return *( --(S->top) );//不空，栈顶指针下移（即删除栈顶元素），并且返回栈顶元素
}

void NextPos(unsigned *x, unsigned *y, short di)//定位下一个位置
{ switch(di){
case 1:
  ++(*x);
  break;
case 2:
  ++(*y);
  break;
case 3:
  --(*x);
  break;
case 4:
  --(*y);
  break;
default:
  break;
}
} ==============================================================================

main.c
===============================================
#include<stdio.h>
#include<malloc.h>
#include"definition.h"

int main()
{ SqStack S;
unsigned x, y, curstep;//迷宫坐标，探索步数
ElemType e;
char maze[10][10]={
  {'#',' ','#','#','#','#','#','#','#','#'},
  {'#',' ',' ','#',' ',' ',' ','#',' ','#'},
  {'#',' ',' ','#',' ',' ',' ','#',' ','#'},
  {'#',' ',' ',' ',' ','#','#',' ',' ','#'},
  {'#',' ','#','#','#',' ',' ',' ',' ','#'},
  {'#',' ',' ',' ','#',' ',' ',' ',' ','#'},
  {'#',' ','#',' ',' ',' ','#',' ',' ','#'},
  {'#',' ','#','#','#',' ','#','#',' ','#'},
  {'#','#',' ',' ',' ',' ',' ',' ',' ','#'},
  {'#','#','#','#','#','#','#','#',' ','#'},
};

printf("迷宫：\n");
for(x=0; x<10; x++){
  for(y=0; y<10; y++)
   printf("%c", maze[x][y]);
  printf("\n");
}

if( InitStack(&S) ){
  printf("创建堆栈失败。\n");
  return 1;
}

//入口坐标
x=1;
y=0;
curstep=1;//探索第一步
//进入迷宫
do{
  if(maze[y][x]==' '){//如果当前位置可以通过
   maze[y][x]='1';//留下足迹
   e.x=x;
   e.y=y;
   e.di=1;
   e.ord=curstep;
   Push(&S, e);//加入路径，即压栈
   if(x==8 && y==9)//到达终点
    break;
   NextPos(&x, &y, 1);//下一位置是当前位置的东邻
   curstep++;
  }
  else{//如果当前位置不能通过
   if(S.top != S.base){
    e=Pop(&S);
    while(e.di==4 && S.top!=S.base){
     maze[e.y][e.x]='0';//留下不能通过足迹
     e=Pop(&S);//退回一步，即出栈
    }
    if(e.di<4){
     e.di++;
     Push(&S, e);
     //重置坐标
     x=e.x;
     y=e.y;
     NextPos(&x, &y, e.di);//寻找下一位置
    }
   }
  }
}while(S.top != S.base);

printf("\n路线：\n");
for(x=0; x<10; x++){
  for(y=0; y<10; y++)
   printf("%c", maze[x][y]);
  printf("\n");
}

free(S.base);

return 0;
}