数据结构-迷宫-实验报告与代码

一．需求分析本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。程序执行的命令：1创建迷宫；2求解迷宫；3输出迷宫求解；二．算法设计本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系程序基本结构：设定栈的抽象数据类型定义：ADTStack{数据对象：D={ia|ia∈CharSet，i=1,2,3,…..,n,n=0;}数据关系：R={1ia，ia|1ia，ia∈D,i=2,…,n}设置迷宫的抽象类型ADTmaze{数据对象：D={ai|ai∈‘’，‘@’，‘#’，‘1’,i=1,2,…,n,n=0}数据关系：R={r,c}r={ai-1,ai|ai-1,ai∈D,i=1,2,…,n,}c=ai-1,ai|ai-1,ai∈D,i=1,2,…,n,}结构体定义：typedefstruct//迷宫中x行y列的位置{intx;inty;}PosType;typedefstruct//栈类型{intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一通道块的“方向”}MazeType;typedefstruct{MazeType*base;MazeType*top;intstacksize;}MazeStack;基本函数：StatusInitStack(MazeStack&S)//新建一个栈StatusPush(MazeStack&S,MazeType&e)//入栈StatusPop(MazeStack&S,MazeType&e)//出栈StatusStackEmpty(MazeStack&S)//判断是否为空StatusMazePath(PosTypestart,PosTypeend)//迷宫路径求解voidFootPrint(PosTypepos)PosTypeNextPos(PosTypecurPos,int&i)voidMakePrint(PosTypepos)三．程序设计根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。1界面设计1）迷宫界面2）迷宫路径显示2主要功能1)入栈操作StatusPush(MazeStack&S,MazeType&e)//入栈操作{if(S.top-S.base=S.stacksize){S.base=(MazeType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(MazeType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}2）出栈操作StatusPop(MazeStack&S,MazeType&e)//出栈{if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}3）判断栈是否为空StatusStackEmpty(MazeStack&S)//判断是否为空{if(S.base==S.top)returnOK;returnERROR;}4）迷宫路径求解StatusMazePath(PosTypestart,PosTypeend)//迷宫路径求解{PosTypecurpos;MazeStackS;MazeTypee;intcurstep;InitStack(S);curpos=start;//设定当前位置为入口位置curstep=1;//探索第一步cout起点:(start.y,start.x)endl;do{if(Pass(curpos))//当前位置可以通过，即是未曾走到的通道块{FootPrint(curpos);//留下足迹e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);//加入路径if(curpos.x==end.x&&curpos.y==end.y){cout\n终点(e.seat.y,e.seat.x);returnTRUE;//到达终点（出口）}curpos=NextPos(curpos,e.di);//下一位置是当前位置的东邻++curstep;//探索下一步}else//当前位置不能通过{if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MakePrint(e.seat);//留下不能通过的标记Pop(S,e);cout倒退到(e.seat.y,e.seat.x);}if(e.di4){++e.di;//换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻块}}}}while(!StackEmpty(S));returnFALSE;}5）探索下一个位置PosTypeNextPos(PosTypecurPos,int&i){switch(i)//顺时针方向{case1:++curPos.x;//东if(mazeMap[curPos.y][curPos.x]!=2)break;--curPos.x;case2:i=2;++curPos.y;//南if(mazeMap[curPos.y][curPos.x]!=2)break;--curPos.y;case3:i=3;--curPos.x;//西if(mazeMap[curPos.y][curPos.x]!=2)break;++curPos.x;case4:i=4;--curPos.y;//北if(mazeMap[curPos.y][curPos.x]==2){++curPos.y;mazeMap[curPos.y][curPos.x]=0;}break;}returncurPos;}6）标记走过的路径voidFootPrint(PosTypepos){mazeMap[pos.y][pos.x]=2;//将走过的路径设为2}7）标记作废路径voidMakePrint(PosTypepos){cout\n(pos.y,pos.x)走不通，作废;mazeMap[pos.y][pos.x]=0;//将走不通的块替换为墙壁}3函数调用intmain(){PosTypemazeStart,mazeEnd;mazeStart.x=1;//开始与结束点mazeStart.y=1;mazeEnd.x=8;mazeEnd.y=8;cout迷宫:endl;for(inti=0;i10;++i){for(intj=0;j10;++j)coutmazeMap[i][j];coutendl;}coutendlendl;if(MazePath(mazeStart,mazeEnd))cout\n走通迷宫endl;elsecout\n走不通迷宫endl;system(PAUSE);return0;}四．测试与分析1、在编程序时迷宫的出入栈掌握的还好，可是编到迷宫方向的选择，与迷宫路径错误的情况时，不知道怎么处理，然后自己通过看书和网上查阅资料基本解决了问题。2、在写代码的过程中，没有弄清使用指针与引用之后，结构体如何使用。当使用指针的时候要使用‘.’，当使用引用或数的时候，要使用‘-’。源程序：#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-2#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintStatus;typedefstruct//迷宫中x行y列的位置{intx;inty;}PosType;typedefstruct//栈类型{intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一通道块的“方向”,//1:东2:北3:西（顺时针)}MazeType;typedefstruct{MazeType*base;MazeType*top;intstacksize;}MazeStack;#includeiostreamusingnamespacestd;StatusInitStack(MazeStack&S);StatusPush(MazeStack&S,MazeType&e);StatusPop(MazeStack&S,MazeType&e);StatusStackEmpty(MazeStack&S);StatusMazePath(PosTypestart,PosTypeend);StatusPass(PosType&pos);voidFootPrint(PosTypepos);PosTypeNextPos(PosTypecurPos,int&i);voidMakePrint(PosTypepos);//迷宫地图，0表示墙壁，1表示通路,入口:mazeMap[1][1],出口mazeMap[8][8]intmazeMap[10][10]={//0,1,2,3,4,5,6,7,8,9{0,0,0,0,0,0,0,0,0,0},//0{0,1,1,0,1,1,1,0,1,0},//1{0,1,1,0,1,1,1,0,1,0},//2{0,1,1,1,1,0,0,1,1,0},//3{0,1,0,0,0,1,1,1,1,0},//4{0,1,1,1,0,1,1,1,1,0},//5{0,1,0,1,1,1,0,1,1,0},//6{0,1,0,0,0,1,0,0,1,0},//7{0,0,1,1,1,1,1,1,1,0},//8{0,0,0,0,0,0,0,0,0,0}//9};intmain(){PosTypemazeStart,mazeEnd;mazeStart.x=1;//开始与结束点mazeStart.y=1;mazeEnd.x=8;mazeEnd.y=8;cout迷宫:endl;for(inti=0;i10;++i){for(intj=0;j10;++j)coutmazeMap[i][j];coutendl;}coutendlendl;if(MazePath(mazeStart,mazeEnd))cout\n走通迷宫endl;elsecout\n走不通迷宫endl;system(PAUSE);return0;}StatusInitStack(MazeStack&S)//新建一个栈{S.base=(MazeType*)malloc(STACK_INIT_SIZE*sizeof(MazeType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(MazeStack&S,MazeType&e)//入栈{if(S.top-S.base=S.stacksize){S.base=(MazeType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(MazeType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMEN