迷宫实验报告.doc

文档介绍：迷宫实验报告
实验内容
迷宫问题。假设迷宫由m行n列构成，有一个出口和一个入口，入口坐标为（1,1），出口坐标为（m,n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。
（1）用C语言实现
}ADT MAZE；
⒊ 本程序模块结构
⑴ 主函数模块
void main(){
初始化迷宫和栈；
创建迷宫；
输出迷宫；
搜索路径；
输出路径；
｝
⑵ 栈模块——实现栈抽象数据类型；
⑶ 迷宫模块——实现迷宫抽象数据类型；
各模块之间的调用关系如下：
主程序模块　　　　　　
迷宫模块

栈模块
详细设计
1、基本数据类型操作
⑴ 栈模块
① typedef struct{
int order;
Position seat;
int direction;
}SElemType;//步数、方向及位置
//栈定义
② typedef struct lnode{
SElemType *base;
SElemType *top;//设两指针便于判断栈是否为空
int stacksize;//栈当前可使用的最大容量
}SqStack;
③ 参数设置：
#define STACK_INIT_SIZE 100
#define STACKINCRENT 10
//----------基本操作的算法描述--------------------
Status InitStack(SqStack &s){ // 构造一个空栈
=(SelemType )malloc(STACK_INIT_SIZE*SizeOf(SelemType));
if(!)exit(OVERLOW); // 存储分配失败
=;
=STACK_INIT_SIZE;
return ok;
}
Status StackEmpty(Sqstack &S){ // 若S为空返回TRUE，否则返回FALSE
return ==;
}
Status GetTop(SqStack &S,Selemtype &e){
// 栈不空，用e返回s的栈顶元素及OK，否则返回ERROR
if(==)return ERROR;
e=*(-1);
return ok;
}
Status Push(Sqstack &S,SelemType &e){ // 插入元素e为新的栈顶元素
if(->=){// 栈满追加存储空间
=(SelemType)realloc(,(+STACKICREMENT)Sizeof(Selemtype));
if(!) exit(OVERFLOW) // 存储分配失败
=+; // 确定新的栈顶指针
+=STACKINCREMENT;// 已分配空间增加
}
*++=*e;
return ok;
}
Status Pop(Sqstack &s,SelemType &e){
// 若栈不变，则删除栈顶元素，用e返回其值及ok,否则false
if(=o=)
return ERROR;
*e=*--; // 顶指针减小，用e返回其数据
return ok;
}
⑵ 迷宫模块：
① 迷宫的数据类型
#define MAXLENGTH 50 // 迷宫的最大长度
#define MAXWIDTH 50 // 屏幕宽度，迷宫的最大宽度
//元素类型
typedef int Status;
typedef struct{
int row;
int col;
}Position; //位置坐标
//迷宫定义
typedef int ElemType;
typedef struct MAZE{
ElemType Maze[MAXLENGTH][MAXWIDTH]; // 迷宫的物理状态描述
int length,width; // 迷宫的大小
Position start,end; // 开始与结束位置与栈