迷宫求解课程设计报告

数据结构实验报告题目：迷宫问题姓名学号任务分配孙盛20084045048问题分析罗剑20084045042代码实现杨滢钢20084045045论文编写一．需求分析1．以结构体Maze表示迷宫，其中BuideMaze调用建立迷宫；Seat用来记录迷宫坐标；SqTack用来记录当前路径；数组；SElemType表示当前位置；Display用于显示栈中所有元素；BuideMaze用于根据用户要求建立一个迷宫地图。2．本程序根据需要产生一个迷宫，0表示有障碍，1表示通路；MazePath为求解迷宫。3．迷宫的入口为左上角，出口为右下角。4．本程序只求出一条成功的通路。二．概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块：（1）主程序模块:实现人机交互。（2）迷宫生产模块：根据需要产生一个迷宫模型。（3）路径查找模块：实现通路的查找。（4）求解迷宫中一条通路的伪代码：do{若当前位置可同，则{将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；}否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。}}}while(栈不空)三．详细分析与源程序#includeiostream.h#includestdlib.h#includeiomanip.h#defineSTACK_INIT_SIZE100//初始栈大小#defineSTACKINCREAMENT10//添加栈的长度#defineSIZE_OF_MAPH20//迷宫高度#defineSIZE_OF_MAPW20//迷宫长度//MazeCell功能：用来描述迷宫组成单元的信息typedefstruct{intPass;//Pass:当Pass为1时，表示导通块；为0则表示障碍块；boolFootprint;//Footprint:当Footprint为1时，表示留下足迹，反之，表示未经此地。}MazeCell;//SElemType功能：此为栈的元素，用来表示当前位置，（栈用来描述当前路径）typedefstruct{intord;//ord:通道块的序号intx;//x:当前位置的横坐标inty;//y:当前位置的纵坐标intdi;//di:搜索方向1向东，2向南，3向西，4向北}SElemType;//SqTack功能：此为栈，用来记录当前路径typedefstruct{SElemType*base;//*base栈底指针，指向起点SElemType*top;//*top栈顶指针，指向路径的末点intstacksize;//stacksize栈的容量}SqStack;//Seat功能：用来记录迷宫坐标，此结构体为中间变量，纯粹为方便编程而建立typedefstruct{intx;//x:用来记录横坐标inty;//y:用来记录纵坐标}Seat;//InitStack功能：此函数用于初始化一个栈boolInitStack(SqStack&S)//函数参数：SqStack&S{//函数返回值类型：boolS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base){return0;}S.top=S.base;S.stacksize=STACK_INIT_SIZE;return0;}//BuideMaze功能：此函数的功能是用于根据用户要求建立一个迷宫地图，将用户输入的//整形数组形状给迷宫数组//函数参数：MazeCellMap[SIZE_OF_MA[SIZE_OF_MAP]//Seat&start起点坐标//Seat&end终点坐标//函数返回值类型：bool建立成功则返回1，反之返回0。VoidBuideMaze(MazeCellMap[SIZE_OF_MAPH][SIZE_OF_MAPW],intma[SIZE_OF_MAPH][SIZE_OF_MAPW]){for(inti=0;iSIZE_OF_MAPH;i++){for(intj=0;jSIZE_OF_MAPW;j++){Map[i][j].Pass=ma[i][j];Map[i][j].Footprint=0;}}}//Pass功能：此函数用于判断当前点是否可通，如果可通则返回1，反之返回0。boolPass(Seatcurpos,MazeCellMap[SIZE_OF_MAPH][SIZE_OF_MAPW]){//参数Seatcurpos当前块的坐标，//MazeCellMap[SIZE_OF_MAP][SIZE_OF_MAP]迷宫地图//函数返回值类型：bool若当前块可通则返回1，反之则返回0。if(Map[curpos.x][curpos.y].Pass==0){return0;}elseif(Map[curpos.x][curpos.y].Footprint==1){return0;}else{return1;}}//FootPrint功能：此函数用于在当前路径下留下脚印。//Seatcurpos当前坐标//MazeCellMap[SIZE_OF_MAP][SIZE_OF_MAP]迷宫地图//函数返回值类型：无voidFootPrint(Seatcurpos,MazeCellMap[SIZE_OF_MAPH][SIZE_OF_MAPW]){Map[curpos.x][curpos.y].Footprint=1;}boolPush(SqStack&S,SElemTypee)//栈插入函数{if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType));if(!S.base){return0;}S.top=S.base+S.stacksize;S.stacksize=S.stacksize+STACKINCREAMENT;}*S.top++=e;return1;}boolPop(SqStack&S,SElemType&e)//栈取出最上面的元素，将值给e{if(S.base==S.top)returnfalse;S.top--;e=*S.top;returntrue;}//NextPos功能：此函数用于将坐标为x,y位置的di方向位置切换为当前位置。//Seatcurpos当前坐标，intdi方向，intx,y坐标，函数返回值类型：无voidNextPos(intx,inty,Seat&curpos,intdi){if(di==1){curpos.y=y+1;curpos.x=x;}elseif(di==2){curpos.x=x+1;curpos.y=y;}elseif(di==3){curpos.y=y-1;curpos.x=x;}elseif(di==4){curpos.x=x-1;curpos.y=y;}}//PutIn功能：向数组里输入元素//intmap[]将得到的数组给map,intWei迷宫的长度,intHig迷宫的高度,返回值类型：无voidPutIn(intmap[],int&Wei,int&Hig){intw,h;cout如果您想输入的迷宫大于所规定的大小，您只需修改SIZE_OF_MAPH和SIZE_OF_MAPendl;cout请输入迷宫的长度(长度小于等于SIZE_OF_MAPW-2)：;cinw;cout请输入迷宫的高度(高度小于等于SIZE_OF_MAPW-2)：;cinh;cout1表示导通块；0表示障碍块endl;Wei=w;Hig=h;for(inti=0;iSIZE_OF_MAPH;i++)for(intj=0;jSIZE_OF_MAPW;j++)*(map+i*SIZE_OF_MAPW+j)=0;for(intis=1;ish+1;is++){cout请输入第is行:;for(intjs=1;jsw+1;js++){intpoint;cinpoint;*(map+is*SIZE_OF_MAPW+js)=point;}coutendl;}}//Display功能：用于显示栈中所有元素voidDisplay(SqStackS){inti=1;SElemType*p;p=S.base;cout从base到top:endl;coutdi搜索方向:di=1向东，di=2向南，di=3向西，di=4向北endl;while(p!=S.top)//从base到top打印元素{cout第i步:;cout((*p).y;cout,(*p).x;cout,(*p).di)endl;p++;i++;}}voidDisplayMaze(intma[SIZE_OF_MAPH][SIZE_OF_MAPW],intw,inth){cout迷宫为(1代表可以通过；0代表不可以通过):endl;for(inti=0;ih+2;i++){for(intj=0;jw+2;j++){coutma[i][j];}coutendl;}coutendl;}//MazePath功能：组织所有子函数，求解迷宫//函数返回值类型：int迷宫有解则返回1，反之则返回0；intMazePath(MazeCellMap[SIZE_OF_MAPH][SIZE_OF_MAPW],Seatstart,Seatend){SElemTypee;SqStackS;//定义一个栈InitStack(S);//初始化栈Seatcurpos;//定义当前位置intcurstep;//计步器curstep=1;//计步器计1curpos.x=start.x;//curpos.y=start.y;//当前位置设为起点cout起点是:start.ystart.xendl;cout终点是:end.yend.xendl;///////////////////////////////////////////////////////////////////////////////下面的循环是求解迷宫的核心程序////////////////////////////////////////////////////////////////////////////do{if(Pass(curpos,Map))//如果当前块可通，则进行如下操作{FootPrint(curpos,Map);//留下脚印e.ord=curstep;//记下计步器e.x=curpos.x;//记下行数e.y=curpos.y;//记下列数e.di=1;//设一个方向为东方Push(S,e);//压栈操作，将当前位置纳入当前路径if(curpos.x==end.x&&curpos.y==end.y)//如果当前块为终点，进行如下操作{//coutok!;//Display(S);//调用显示栈的子程序显示结果return1;//函数返回1}//else//如果当前位置不是终点，进行如下操作{//NextPos(curpos.x,curpos.y,curpos,1);//切换东方向的位置为当前位置curstep++;//计步器自增1}}//ifelse{if(S.base!=S.top)//如果当前块不通，且栈不为空（说明还有解）{Pop(S,e);//将栈顶元素弹出进行观察while(e.di==4&&(S.top-S.base))//如果栈顶元素四方均不通{Pop(S,e);//弹出下一个