《迷宫求解实验报告》由会员分享，可在线阅读，更多相关《迷宫求解实验报告（16页珍藏版）》请在金锄头文库上搜索。
1、编程实训实验报告书专 业：计算机科学与技术 班 级： 1班 学 号： 31960144 姓 名：周* 指导教师：周* 日 期：2016年6月30日 目录一、需求分析31.任务要求32.软件功能分析33.数据准备3二、概要设计31.功能模块图42.模块间调用关系43.主程序模块54.抽象数据类型描述5三、详细设计61.存储结构定义62.各功能模块的详细设计7四、实现和调试71.主要的算法72.主要问题及解决83.测试执行及结果8五、改进9六、附录91需求分析1.1任务要求以一个m*n的长方阵表示迷宫，和分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出
2、没有通路的结论。1.2软件功能分析设计一个迷宫，通过该程序可以找出通往出口的最短路径。程序功能有三（）创建迷宫；（）求解迷宫；（）输出迷宫的解。1.3数据准备迷宫的测试数据如下：左上角(1,1)为入口，右下角(9,8)为出口。001000100010001000001101011100100001000001000101011110011100010111000000障碍物坐标：1 31 72 32 73 53 63 84 24 34 44 75 46 26 66 87 27 37 47 57 88 18 28 68 89 19 22 概要设计2.1功能模块图栈的顺序存储表示#define S
3、tackSize 100 /假定预分配的栈空间最多为100个元素 typedef char DataType;/假定栈元素的数据类型为字符 typedef struct DataType dataStackSize; int top; SeqStack;基本操作的算法描述（1） 置栈空 void InitStack（SeqStack *S） /将顺序栈置空 S-top=-1; （2） 判栈空 int StackEmpty（SeqStack *S） return S-top=-1; （3） 判栈满 int StackFull（SeqStack *SS） return S-top=StackSiz
4、e-1; （4） 进栈 void Push（S，x） if (StackFull(S) Error(Stack overflow); /上溢，退出运行 S-data+S-top=x;/栈顶指针加1后将x入栈 （5） 退栈 DataType Pop（S） if(StackEmpty(S) Error(Stack underflow); /下溢，退出运行 return S-dataS-top-;/栈顶元素返回后将栈顶指针减1 （6） 取栈顶元素 DataType StackTop（S） if(StackEmpty(S) Error(Stack is empty); return S-dataS-t
5、op; 2.2模块间调用关系Stack.h中调用的base.h#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;2.3主程序模块主程序maze.c中调用的stack.h#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置 int r; int c;PostType;typedef s
6、truct int ord; /当前位置在路径上的序号 PostType seat;/当前坐标 int di; /往下一坐标的方向SElemType; /栈元素类型typedef struct SElemType* base;/栈基址,构造前销毁后为空 SElemType* top;/栈顶 int stackSize; /栈容量Stack; /栈类型Status InitStack(Stack &S) /构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW);/存储分配失败
7、 S.top=S.base; S.stackSize=INIT_SIZE; return OK;/InitStackStatus StackEmpty(Stack S) /若s为空返回TRUE,否则返回FALSE if(S.top=S.base) return TRUE; return FALSE;/StackEmptyStatus Push(Stack &S,SElemType e) /插入元素e为新的栈顶元素 if(S.top-S.base =S.stackSize)/栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREM
8、ENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; *S.top+=e; return OK;/pushStatus Pop(Stack &S,SElemType &e)/若栈不空删除栈/顶元素用e返回并返回OK，否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/PopStatus DestroyStack(Stack &S)/销毁栈S, free(S.
9、base); S.top=S.base; return OK;/DestroyStack2.4抽象数据类型描述栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,，an），则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。3 详细设计3.1存储结构定义typedef int Status;#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置int r;int c;PostType;typedef structint ord; /当前位置在路径上的序号PostType seat;/当前坐标int di; /往下一坐标的方向SElemType;/栈元素类型typedef structSElemType* b
