数据结构迷宫源代码

#includestdio.h#includemalloc.h#includestdlib.h#includestring.h#includetime.h#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW-2#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10//栈的顺序存储表示typedefstruct{intx;/*列*/inty;/*行*/}PosType;//坐标位置类型typedefstruct{intord;//通道块在路径上的序号PosTypeseat;//通道块在迷宫中的坐标位置intdi;//从此通道块走向下一通道块的方向}SElemType;//栈的元素类型typedefstruct{SElemType*base;SElemType*top;intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//基本操作intInitStack(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;returnOK;}//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORintGetTop(SqStack*S,SElemType*e){if(S-top==S-base)returnERROR;*e=*(S-top-1);returnOK;}intPush(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;returnOK;}//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORintPop(SqStack*S,SElemType*e){if(S-top==S-base)returnERROR;*e=*--S-top;returnOK;}intStackEmpty(SqStack*S){return(S-top==S-base);}//迷宫程序typedefstruct{intlie;/*列数*/inthang;/*行数*/chara[999][999];}MazeType;/*迷宫类型*//*随机生成迷宫*/intgeneratemaze(MazeType*maze){inti,j;maze-a[0][0]=2;maze-a[++maze-hang][++maze-lie]=3;/*设置外墙*/maze-a[0][maze-lie]='!';maze-a[maze-hang][0]='!';for(j=1;jmaze-lie;j++){maze-a[0][j]='!';maze-a[maze-hang][j]='!';}for(i=1;imaze-hang;i++){maze-a[i][0]='!';maze-a[i][maze-lie]='!';}srand((unsigned)time(NULL));rand();for(i=1;imaze-hang;i++)for(j=1;jmaze-lie;j++){if(rand()=RAND_MAX/4)maze-a[i][j]='';//''暗示出路elsemaze-a[i][j]='!';//'!'暗示无出路}returnOK;}intPass(MazeType*maze,PosTypecurpos)//判断当前位置可否通过{if((curpos.x1)||(curpos.x=maze-lie))returnERROR;if((curpos.y1)||(curpos.y=maze-hang))returnERROR;if(maze-a[curpos.y][curpos.x]=='')returnOK;elsereturnERROR;}intFootPrint(MazeType*maze,PosTypecurpos)//留下足迹{maze-a[curpos.y][curpos.x]='*';returnOK;}intMarkPrint(MazeType*maze,PosTypecurpos)//留下不能通过的标记{maze-a[curpos.y][curpos.x]='@';returnOK;}PosTypeNextPos(PosTypecurpos,intdi)//返回当前位置的下一位置{PosTypepos=curpos;switch(di){case1://右东pos.x++;break;case2://下南pos.y++;break;case3://左西pos.x--;break;case4://上北pos.y--;break;}returnpos;}//若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERRORintMazePath(MazeType*maze,PosTypestart,PosTypeend){PosTypecurpos;SqStack*S=(SqStack*)malloc(sizeof(SqStack));InitStack(S);SElemType*e;e=(SElemType*)malloc(sizeof(SElemType));curpos=start;//设定当前位置为入口位置intcurstep=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-di4)//栈不空且栈顶位置四周有其他位置未探索{e-di++;Push(S,e);curpos=e-seat;curpos=NextPos(curpos,e-di);}}}}while(!StackEmpty(S));returnERROR;}voidPrintMaze(MazeType*maze)//打印迷宫{inti,j,k,n;intc[999],d[999];for(i=0,k=0;i=maze-hang;i++){for(j=0;j=maze-lie;j++){printf(%c,maze-a[i][j]);if(maze-a[i][j]=='*'){c[k]=i;d[k]=j;k++;}}printf(\n);}n=k;for(k=0;kn;k++)printf(%d,%d,c[k],d[k]);printf(\n);printf(\n);}intmain(){intzmg;charch;printf(数据结构课程设计--迷宫问题求解\n\n);printf(|----------------------------------------|\n);printf(||\n);printf(||\n);printf(||\n);printf(||\n);printf(|XXXXXXXXXXXXXXXXXX|\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();PosTypestart,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);}elseprintf(此迷宫无通路\n);//getchar();printf(再次尝试？（Y/N）?);scanf(%c,&ch);}while(ch=='Y'||ch=='y');return0;}