迷宫求解课程设计报告

《迷宫求解课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告题目：迷宫问题姓名学号任务分配孙盛20084045048问题分析罗剑20084045042代码实现杨滢钢20084045045论文编写一．需求分析1．以结构体Maze表示迷宫，其中BuideMaze调用建立迷宫；Seat用来记录迷宫坐标；SqTack用来记录当前路径；数组；SElemType表示当前位置；Display用于显示栈中所有元素；BuideMaze用于根据用户要求建立一个迷宫地图。2．本程序根据需要产生一个迷宫，0表示有障碍，1表示通路；MazePath为求解迷宫。3．迷宫的入口为左上角，出口为右下角。4．本程序只求出一条成功的通路。二．概要设计为

2、了实现上述操作，以栈为存储结构。本程序包含三个模块：（1）主程序模块:实现人机交互。（2）迷宫生产模块：根据需要产生一个迷宫模型。（3）路径查找模块：实现通路的查找。（4）求解迷宫中一条通路的伪代码：do{若当前位置可同，则{将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；}否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。}}}while(栈不空)三

3、．详细分析与源程序#include#include#include#defineSTACK_INIT_SIZE100//初始栈大小#defineSTACKINCREAMENT10//添加栈的长度#defineSIZE_OF_MAPH20//迷宫高度#defineSIZE_OF_MAPW20//迷宫长度//MazeCell功能：用来描述迷宫组成单元的信息typedefstruct{intPass;//Pass:当Pass为1时，表示导通块；为0则表示障碍块；boolFootprint;//Footprint:当

4、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栈顶指针，指向路径的末点i

5、ntstacksize;//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.

6、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_MA

7、PW]){for(inti=0;i