迷宫求解实验报告

《迷宫求解实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《编程实训》实验报告书专业：计算机科学与技术班级：Jji学号:姓名:指导教师:日期:31960144周*eg氺氺2016年6月30日目录一、需求分析31.任:#翻32.软件功能分析33.醐祕3二、概要设计31.功能模块图42.模块间调用关系43.主程序模块54.抽象数据类型描述5三、详细设计61.存储结构定义62.各功能模块的详细设计7叫、实现和调试71.主要的算法72.主要问题及解决83.测试执行及结果871、改进9六、附最91需求分析1.1任务要求以一个的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的

2、通路，或得出没有通路的结论。1.2软件功能分析设计一个迷宫，通过该程序可以找出通往岀门的最短路径。程序功能有三（1）创建迷宫；（2）求解迷宫；（3）输出迷宮的解。障碍物坐标:1317234243442概要设计2.1功能模块图栈的顺序存储表示#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据矣型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;基本操作的算法描述（1）置栈空voidInitStack（SeqSta

3、ck*S）{//将顺序栈賈空S->top=~l;(2)判栈空intStackEmpty(SeqStack氺S){returnS_〉top二=-l;}(3)判栈满intStackFull(SeqStack*SS){returnS->top==StackSize_l;}(4)进栈voidPush(S,x){if(StackFull(S))Error(z，Stackoverflow");//上溢，退出运行S->data[++S-〉top]=x;//栈顶指针加1后将x入找}(5)退栈DataTypePop(S){if(StackEmpty(S))Error(""Stac

4、kunderflow");//下溢，退出运行returnS-〉data[S_〉top—];//栈顶元素返回/rS•将栈顶指针减1}(6)取栈顶元素DataTypeStackTop(S){if(StackEmpty(S))Error(’’Stackisempty〃)；returnS-〉data[S-〉top];}2.2模块间调用关系Stack,h巾调用的base,h^include〈stdio.h〉^include〈stdlib.h>#include〈string.h〉#defineTRUE1#defineFALSE0#defineOK1#defineERROR0

5、#defineOVERFLOW-2typedefintStatus;2.3主程序模块主程序maze,c中调用的stack,h#defineINIT_STZR100//存储空间初始分配量defineINCREMENT10//存储空间分配增量typedefstruct{//迷宫屮r行c列的位置intr;intc;}PostType;typedefstruct{intord;//当前位置在路径上的序号PostTypcseat;//当前坐标intdi;//往下一坐标的方向}SElemType;//栈元素类型typedefstruct{SElemType*base;//栈

6、基址，构造前销毁后为空SElemTypc*top;//栈顶intstackSize;//栈容量}Stack;//桟类型StatusInitStack(Stack&S){//构造空栈sS.base=(SElemType*)malloc(IN1TSIZE氺sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top二S.base;S.stackSize=TNTT_STZE;returnOK;}//InitStackStatusStackEmpty(StackS){//若s为空返回TRUE,否则返回FALSEif

7、(S.top==S.base)returnTRUE;returnFALSE;}//StackEmptyStatusPush(Stack&S,SElemTypee){//插入元素e为新的栈顶元素if(S.top-S.base〉=S.stackSize){//栈满，加空间S.base=(SElemType*)realloc(S.base,(S.stackSize十INCREMENT)*size()f(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stackSize;S.stacksize+=

8、INCREMENT;}氺