资源描述：
《数据结构课程设计报告―迷宫求解问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、课题设计1：迷宫求解一.需求分析：本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。二、概要设计：1.抽象数据类型定义：ADTFind{数据对象：D={ai?ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={?ai-1,ai∈D}基本操作： find(&S)初始条件：已初始化栈S，且栈为空操作结果：从栈Ｓ中找出相对应的数据关系，并输出结果}A
2、DTFind2.主程序的流程以及各程序模块之间的调用关系：(1).定义变量i、j、w、z为整形变量(2).输入迷宫二维数组maze(0:m,0:n)(3).调用子程序find()(4).结束程序三、相应的源程序如下：#include#includetypedefenum{ERROR,OK}Status;typedefstruct{introw,line;}PosType;typedefstruct{intdi,ord;PosTypeseat;}SElemType;typedefstruct{SElemType*base;SElemTy
3、pe*top;intstacksize;}SqStack;StatusInitStack(SqStack&S);StatusPush(SqStack&S,SElemType&a);StatusPop(SqStack&S,SElemType&a);StatusStackEmpty(SqStackS);StatusMazePath(intmaze[12][12],SqStack&S,PosTypestart,PosTypeend);voidInitmaze(intmaze[12][12],intsize);voidprintmaze(intmaze[12][12],intsi
4、ze);StatusPass(intmaze[12][12],PosTypeCurPos);voidMarkfoot(intmaze[12][12],PosTypeCurPos);PosTypeNextPos(PosTypeCurPos,intDir);voidprintpath(intmaze[12][12],SqStackS,intsize);voidmain(void){SqStackS;intsize,maze[12][12];for(intn=0;n<10;n++){printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):");scanf("
5、%d",&size);if(size<1
6、
7、size>10){printf("输入错误!");return;}Initmaze(maze,size);printmaze(maze,size);PosTypestart,end;printf("输入入口行坐标和列坐标:");scanf("%d",&start.row);scanf("%d",&start.line);printf("输入出口行坐标和列坐标:");scanf("%d",&end.row);scanf("%d",&end.line);if(MazePath(maze,S,start,end))printpath(
8、maze,S,size);elseprintf("找不到通路!");}}StatusMazePath(intmaze[12][12],SqStack&S,PosTypestart,PosTypeend){PosTypecurpos;intcurstep;SElemTypee;InitStack(S);curpos=start;curstep=1;do{if(Pass(maze,curpos)){Markfoot(maze,curpos);e.di=1;e.ord=curstep;e.seat=curpos;Push(S,e);if(curpos.row==end.
9、row&&curpos.line==end.line)returnOK;curpos=NextPos(curpos,1);curstep++;}else{if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){Markfoot(maze,e.seat);Pop(S,e);}if(e.di<4){e.di++;Push(S,e);curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));returnERROR;}voi
