数据结构迷宫源代码(共7页).doc

精选优质文档-倾情为你奉上#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>#include <time.h>#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2 #define STACK_INIT_SIZE 100#define STACKINCREMENT 10/栈的顺序存储表示typedef struct int x;/*列*/ int y;/*行*/PosType;/坐标位置类型typedef struct int ord;/通道块在路径上的序号 PosType seat;/通道块在迷宫中的坐标位置 int di;/从此通道块走向下一通道块的方向SElemType;/栈的元素类型typedef struct SElemType *base;SElemType *top;int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/基本操作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;/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack *S,SElemType *e) if(S->top=S->base) return ERROR; *e=*(S->top-1); return OK;int Push(SqStack *S,SElemType *e)/插入元素e作为新的栈顶元素 if(S->top-S->base>=S->stacksize)/*栈满，追加存储空间*/ S->base = (SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(SElemType); if(!S->base) exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT; *S->top+=*e; return OK;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORint Pop(SqStack *S,SElemType *e) if(S->top=S->base) return ERROR; *e=*-S->top; return OK;int StackEmpty(SqStack *S) return(S->top=S->base) ;/迷宫程序typedef struct int lie;/*列数*/ int hang;/*行数*/ char a999999;MazeType;/*迷宫类型*/*随机生成迷宫*/int generatemaze( MazeType *maze)int i,j;maze->a00=2; maze->a+maze->hang+maze->lie=3;/*设置外墙*/maze->a0maze->lie='!'maze->amaze->hang0='!'for(j=1;j<maze->lie;j+) maze->a0j='!'maze->amaze->hangj='!'for(i=1;i<maze->hang;i+) maze->ai0='!'maze->aimaze->lie='!'srand(unsigned)time( NULL );rand(); for(i=1; i <maze->hang; i+) for(j=1;j<maze->lie;j+) if (rand()>=RAND_MAX/4) maze->aij =' ' /' ' 暗示出路 else maze->aij ='!' /'!'暗示无出路 return OK;int Pass(MazeType *maze, PosType curpos )/判断当前位置可否通过if (curpos.x < 1) | (curpos.x >= maze->lie) return ERROR;if (curpos.y < 1) | (curpos.y >= maze->hang) return ERROR;if (maze->acurpos.ycurpos.x=' ') return OK; else return ERROR;int FootPrint(MazeType *maze,PosType curpos)/留下足迹 maze->acurpos.ycurpos.x='*' return OK;int MarkPrint(MazeType *maze,PosType curpos)/留下不能通过的标记 maze->acurpos.ycurpos.x='' return OK;PosType NextPos(PosType curpos,int di)/返回当前位置的下一位置 PosType pos=curpos; switch(di) case 1:/右东 pos.x+; break; case 2:/下南 pos.y+; break; case 3:/左西 pos.x-; break; case 4:/上北 pos.y-; break; return pos;/若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERRORint MazePath(MazeType *maze,PosType start,PosType end) PosType curpos; SqStack *S=(SqStack *)malloc(sizeof(SqStack); InitStack(S); SElemType *e; e=(SElemType *)malloc(sizeof(SElemType); curpos=start;/设定当前位置为入口位置 int curstep = 1;/探索第一步 do if(Pass(maze,curpos)/当前位置可通过 FootPrint(maze,curpos); e->ord=curstep; e->seat=curpos; e->di=1; Push(S,e); if(curpos.x=end.x&&curpos.y=end.y) return (OK); curpos=NextPos(curpos,1); curstep+; else if(!StackEmpty(S) Pop(S,e); while(e->di=4&&!StackEmpty(S)/栈不空但栈顶位置四周均不通 MarkPrint(maze,e->seat);Pop(S,e); if(e->di<4)/栈不空且栈顶位置四周有其他位置未探索 e->di+;Push(S,e); curpos=e->seat; curpos=NextPos(curpos,e->di); while(!StackEmpty(S);return ERROR;void PrintMaze(MazeType *maze)/打印迷宫 int i,j,k,n; int c999,d999; for(i=0,k=0;i<=maze->hang;i+)for(j=0;j<=maze->lie;j+)printf("%c ",maze->aij);if(maze->aij='*')ck=i;dk=j;k+; printf("n"); n=k; for(k=0;k<n;k+) printf("<%d,%d>",ck,dk); printf("n"); printf("n");int main() int zmg; char ch; printf(" 数据结构课程设计-迷宫问题求解 nn"); printf(" |-|n"); printf(" | |n"); printf(" | |n"); printf(" | |n"); printf(" | |n"); printf(" | XXXX XXXXXXXXXXXXXX |n"); printf(" | XXXXXXX |n"); printf(" |-|n"); getchar(); do system("cls"); fflush(stdin); MazeType *maze=(MazeType *)malloc(sizeof(MazeType); /设置迷宫的长宽不含外墙 printf("请输入迷宫的列数（不含外墙时）:"); scanf("%d",&maze->lie); printf("请输入迷宫的行数（不含外墙时）:"); scanf("%d",&maze->hang); generatemaze(maze); printf("随机创建迷宫n"); PrintMaze(maze); getchar(); getchar(); PosType start,end; start.x=1;start.y=1; end.x=maze->lie-1;end.y=maze->hang-1; zmg=MazePath(maze,start,end); if(zmg) printf("此迷宫通路为n"); PrintMaze(maze); else printf("此迷宫无通路n"); /getchar(); printf("再次尝试？（Y/N）?"); scanf("%c",&ch); while(ch='Y'|ch='y'); return 0;专心-专注-专业