迷宫求解课程设计报告.docxVIP

数据结构实验报告

题目：迷宫问题

姓名

学号

任务分配

孙盛

20084045048

问题分析

罗剑

20084045042

代码实现

杨滢钢

20084045045

论文编写

需求分析

以结构体Maze表示迷宫，其中BuideMaze调用建立迷宫；Seat用来记录迷宫坐标；SqTack用来记录当前路径；数组；SElemType表示当前位置；Display用于显示栈中所有元素；BuideMaze用于根据用户要求建立一个迷宫地图。

本程序根据需要产生一个迷宫，0表示有障碍，1表示通路；MazePath为求解迷宫。

迷宫的入口为左上角，出口为右下角。

本程序只求出一条成功的通路。

概要设计

为了实现上述操作，以栈为存储结构。

本程序包含三个模块：

主程序模块:实现人机交互。

迷宫生产模块：根据需要产生一个迷宫模型。

路径查找模块：实现通路的查找。

求解迷宫中一条通路的伪代码：

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(SqStackS) //函数参数：SqStackS

{ //函数返回值类型：bool

S.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]

//Seatstart起点坐标

//Seatend终点坐标

//函数返回值类型：bool建立成功那么返回1，反之返回0。

Void BuideMaze(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],i