数据结构栈求解迷宫问题C语言版.doc

(完整word版)数据结构栈求解迷宫问题C语言版数据结构栈求解迷宫问题(C语言版) /*数据结构C语言版 栈求解迷宫问题P50-52 利用栈求解迷宫问题编译环境：Dev-C+ 4.9.9.2日期：2011年2月12日 */*头文件*/ 迷宫坐标位置类型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03表示东北) SElemType;/ 全局变量 MazeType m; / 迷宫数组int curstep=1; / 当前足迹,初值为1 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 P46 typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈/*实现*/ /构造一个空栈Sint InitStack(SqStack *S)/ 为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;/ 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S)if(S.top = S.base)return 1;elsereturn 0;/插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e)if(*S).top - (*S).base >= (*S).stacksize)/ 栈满，追加存储空间(*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹/ 当迷宫m的b点的序号为1(可通过路径)，return 1; 否则，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;/ 使迷宫m的a点的序号变为足迹(curstep)，表示经过 void FootPrint(PosType a)ma.xa.y=curstep;/ 根据当前位 置及移动方向，返回下一位置 PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移动方向,依次为东南西北 c.x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b) mb.xb.y=-1;/ 算法3.3 P51/ 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入栈当前位置及状态 curstep+; / 足迹加1 if(curpos.x=end.x&&curpos.y=end.y) / 到达终点(出口) return 1;curpos=NextPos(curpos,e.di);else/ 当前位置不能通过 if(!StackEmpty(S)Pop(&S,&e); / 退栈到前一位置 curstep-;/ 前一位置处于最后一个方向(北) while(e.di=3&&!StackEmpty(S)MarkPrint(e.seat); / 留下不能通过的标记(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di<3) / 没到最后一个方向(北) e.di+; / 换下一个方向探索Push(&S,e);curstep+;/ 设定当前位置是该新方向上的相邻块curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/ 输出迷宫的结构 void Print(int x,int y) int i,j;for(i=0;i<x;i+)for(j=0;j<y;j+)printf("%3d",mij);printf("n");int main()PosType begin,end;int i,j,x,y,x1,y1;printf("请输入迷宫的行数,列数(包括外墙)：(空格隔开)");scanf("%d%d", &x, &y);for(i=0;i<x;i+) / 定义周边值为0(同墙) m0i=0;/ 迷宫上面行的周边即上边墙 mx-1i=0;/ 迷宫下面行的周边即下边墙 for(j=1;j<y-1;j+)mj0=0;/ 迷宫左边列的周边即左边墙 mjy-1=0;/ 迷宫右边列的周边即右边墙 for(i=1;i<x-1;i+)for(j=1;j<y-1;j+)mij=1; / 定义通道初值为1 printf("请输入迷宫内墙单元数：");scanf("%d",&j);printf("请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n");for(i=1;i<=j;i+)scanf("%d%d",&x1,&y1);mx1y1=0; / 定义墙的值为0 printf("迷宫结构如下:n");Print(x,y);printf("请输入起点的行数,列数：（空格隔开）");scanf("%d%d",&begin.x,&begin.y);printf("请输入终点的行数,列数：（空格隔开）");scanf("%d%d",&end.x,&end.y);if(MazePath(begin,end) / 求 得一条通路 printf("此迷宫从入口到出口的一条路径如下:n&quot;);Print(x,y); / 输出此通路 elseprintf("此迷宫没有从入口到出口的路径n");system("pause");return 0;/*输出效果：请输入迷宫的行数,列数(包括外墙)：(空格隔开)5 5请输入迷宫内墙单元数：2请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)1 23 2迷宫结构如下:0 0 0 0 00 1 0 1 00 1 1 1 00 1 0 1 00 0 0 0 0请输入起点的行数,列数：（空格隔开）1 1请输入终点的行数,列数：（空格隔开）3 3此迷宫从入口到出口的一条路径如下:0 0 0 0 00 1 0 1 00 2 3 4 00 1 0 5 00 0 0 0 0请按任意键继续. . .*/