迷宫问题实验报告

武汉纺织大学数学与计算机学院数据结构课程设计报告迷宫问题求解学生姓名：学号：班级：指导老师：报告日期：一、问题描述以一个mxn的长方矩阵表示迷宫，1和0分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。二、需求分析1、以二维数组maze[10][10]表示迷宫，数组中以元素1表示通路，0表示障碍，迷宫的大小理论上可以不限制，但现在只提供10*10大小迷宫。2、迷宫的入口和出口需由用户自行设置。3、以长方形矩阵的形式将迷宫及其通路输出，输出中“#”表示迷宫通路，“1”表示障碍。4、本程序只求出一条成功的通路。但是只要对函数进行小量的修改，就可以求出其他全部的路径。5、程序执行命令为：（1）输入迷宫；（2）、求解迷宫；（3）、输出迷宫。三、概要设计1、设定栈的抽象数据类型定义：ADTzhan{基本操作：InitStack(SqStack&S)操作结果：构造一个空栈push（*s，*e）初始条件：栈已经存在操作结果：将e所指向的数据加入到栈s中pop（*s,*e）初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素getpop（*s，*e）初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素stackempty(*s)初始条件：栈已经存在操作结果：判断栈是否为空。若栈为空，返回1，否则返回0}ADTzhan2、设定迷宫的抽象数据类型定义ADTmigong{基本操作：Statusprint(MazeTypemaze)；//显示迷宫StatusPass(MazeTypemaze,PosTypecurpos);//判断当前位置是否可通StatusFootPrint(MazeType&maze,PosTypecurpos);//标记当前位置已经走过StatusMarkPrint(MazeType&maze,PosTypecurpos);//标记当前位置不可通PosTypeNextPos(PosTypecurpos,DirectiveTypedi);//进入下一位置}ADTyanshu3、本程序包括三个模块a、主程序模块voidmain(){初始化；迷宫求解；迷宫输出；}b、栈模块——实现栈的抽象数据类型c、迷宫模块——实现迷宫的抽象数据类型四、流程图五、数据结构typedefstruct//位置结构{introw;//行位置intcol;//列位置}PosType;typedefstruct//迷宫类型{intarr[10][10];}MazeType;typedefstruct{intstep;//当前位置在路径上的序号PosTypeseat;//当前的坐标位置DirectiveTypedi;//往下一个坐标位置的方向}SElemType;将入口、出口位置传入方法里判断当前位置是否可通将元素入栈是否到达迷宫出口右边是否存在通路上边是否存在通路左边是否存在通路下边是否存在通路存储结点入栈循环结束，无解迷宫有解迷宫typedefstruct//栈类型{SElemType*base;//栈的尾指针SElemType*top;//栈的头指针intstacksize;//栈的大小}SqStack;六、调试结果和分析a)测试结果实际程序执行过程如下图所示：参考文献[1]严蔚敏、吴伟民：《数据结构（C语言版）》[M]，清华大学出版社2007年版[2]谭浩强：《C语言设计（第三版）》[M]，清华大学出版社2005年版心得体会通过这段时间的课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在设计此程序时，刚开始感到比较迷茫，然后一步步分析，试着写出基本的算法，思路渐渐清晰，最后完成程序。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。在遇到描写迷宫路径的算法时，我感到有些困难，后来经过一步步分析和借鉴书本上的穷举求解的算法，最后把算法写出来。这次课程设计让我更加深入了解很多方面的知识，如数组的运用等等。在程序的编写中不要一味的模仿，要自己去摸索，只有带着问题反复实践，才能熟练地掌握和运用。附录、源代码#includestdio.h//头文件#includemalloc.h#includestdlib.h#includestring.h#defineOK1//宏定义#defineERROR0#defineOVERFLOW-2typedefintStatus;//函数的返回值typedefintDirectiveType;//下一个通道方向#defineSTACK_INIT_SIZE500//栈的最大值#defineSTACKINCREMENT10//增量//-----------存储结构typedefstruct{introw;intcol;}PosType;typedefstruct{intstep;//当前位置在路径上的序号PosTypeseat;//当前的坐标位置DirectiveTypedi;//往下一个坐标位置的方向}SElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;//栈的存储typedefstruct{intarr[10][10];}MazeType;//迷宫类型//---------函数声明StatusInitStack(SqStack&S);StatusPop(SqStack&S,SElemType&e);StatusPush(SqStack&S,SElemTypee);StatusStackEmpty(SqStackS);StatusMazePath(MazeType&maze,PosTypestart,PosTypeend);StatusPass(MazeTypemaze,PosTypecurpos);StatusFootPrint(MazeType&maze,PosTypecurpos);PosTypeNextPos(PosTypecurpos,DirectiveTypedi);StatusMarkPrint(MazeType&maze,PosTypecurpos);Statusprint(MazeTypemaze);voidmain(){PosTypestart,end;MazeTypea;printf(请输入迷宫数据\n);for(inti=0;i10;i++)//接受输入的迷宫数据{for(intj=0;j10;j++){scanf(%d,&a.arr[i][j]);}}printf(请输入起始位置：行列);//用户自定义起始点与终点scanf(%d%d,&start.row,&start.col);printf(请输入结束位置：行列);scanf(%d%d,&end.row,&end.col);if(MazePath(a,start,end))//寻找路径print(a);elseprintf(没有找到路径\n);}StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//为栈申请存储地址if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//endInitStackStatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);//如果没有这句话就会在原地打转，导致在死胡同堵死S.top--;returnOK;}//endPopStatusPush(SqStack&S,SElemTypee){*S.top=e;S.top++;returnOK;}//endPushStatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;}//endStackEmptyStatusMazePath(MazeType&maze,PosTypestart,PosTypeend){PosTypecurpos;curpos=start;intcurstep=1;SElemTypee;SqStackS;InitStack(S);do{if(Pass(maze,curpos))//当前位置可以通过，即未曾走过的模块{e.step=curstep;e.seat=curpos;e.di=1;FootPrint(maze,curpos);//留下足迹Push(S,e);//加入到路径栈中if(curpos.col==end.col&&curpos.row==end.row)//达到终点（出口）returnOK;curpos=NextPos(curpos,1);//下一位置是当前位置的东邻curstep++;//探索下一步}//endifelse{//当前位置不能通过if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MarkPrint(maze,e.seat);Pop(S,e);//留下不能通过的标记，并回退一步}//endwhileif(e.di4){e.di++;//换一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向的相邻快}//endif}//endif}//endelse}while(!StackEmpty(S));//endifprintf(\n\n);for(inti=0;i10;i++){for(intj=0;j10;j++){printf(%d,maze.arr[i][j]);}printf(\n);}returnERROR;}//endMazePathStatusPass(MazeTypemaze,PosTypecurpos){if(maze.arr[curpos.row][curpos.col]==0)//判断当前路径对应数组值是否等于0，即当前路径是否可通returnOK;elsereturnERROR;}StatusFootPrint(MazeType&maze,PosTypecurpos){maze.arr[curpos.row][curpos.col]=2;//为当前路径留下可以通过的标志returnOK;}//endPassPosTypeNextPos(PosTypecurpos,DirectiveTypedi){PosTypepos=curpos;switch(di){case1:pos.col++;//向东寻找break;case2:pos.row++;//向西寻找break;case3:pos.col--;//向南寻找break;case4:pos.row--;//向北寻找break;}returnpos;}//endNextPosStatusMarkPrint(MazeType&maze,PosTypecurpos){maze.arr[curpos.row][curpos.col]=3;//为当前路径留下不可通过的标志returnOK;}//endMarkPrintStatusprint(MazeTypemaze)//迷宫的输出显示{inti,j;printf(\n\n);for(i=0;i10;i++){for(j=0;j10;j++){switch(maze.arr[i][j]){case0:printf();break;case1:printf(1);break;case2:printf(#);break;case