迷宫问题,实验报告(共10篇)

1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划迷宫问题,实验报告(共10篇)武汉纺织大学数学与计算机学院数据结构课程设计报告迷宫问题求解学生姓名：学号：班级：指导老师：报告日期：一、问题描述以一个mxn的长方矩阵表示迷宫，1和0分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。二、需求分析1、以二维数组maze1010表示迷宫，数组中以元素1表示通路，0表示障碍，迷宫的大小理论上可以不限制，但现在只提供10*10大小迷宫。2、迷宫的入口和出口需由用户自行设置。3、以长方形矩阵的形式将迷宫及其通路输出，输出中“#”表示迷宫通路，“1”表示障碍。4、本程序只求出一条成功的通路。但是只要对函数进行小量的修改，就可以求出其他全部的路径。5、程序执行命令为：输入迷宫；、求解迷宫；、输出迷宫。三、概要设计1、设定栈的抽象数据类型定义：ADTzhan基本操作：InitStack(SqStack&S)操作结果：构造一个空栈push初始条件：栈已经存在操作结果：将e所指向的数据加入到栈

2、s中pop初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素getpop初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素stackempty(*s)初始条件：栈已经存在操作结果：判断栈是否为空。若栈为空，返回1，否则返回0ADTzhan2、设定迷宫的抽象数据类型定义ADTmigong基本操作：Statusprint(MazeTypemaze)；/显示迷宫StatusPass(MazeTypemaze,PosTypecurpos);/判断当前位置是否可通StatusFootPrint(MazeType&maze,PosTypecurpos);/标记当前位置已经走过StatusMarkPrint(MazeType&maze,PosTypecurpos);/标记当前位置不可通PosTypeNextPos(PosTypecurpos,DirectiveTypedi);/进入下一位置ADTyanshu3、本程序包括三个模块a、主程序模块voidmain()初始化；迷宫求解；迷宫输出；b、栈模块实现栈的抽象数据类型c、迷宫模块实现迷宫的抽象数据类型四、流程图五、数

3、据结构typedefstruct/位置结构introw;/行位置intcol;/列位置PosType;typedefstruct/迷宫类型intarr1010;MazeType;typedefstructintstep;/当前位置在路径上的序号PosTypeseat;/当前的坐标位置DirectiveTypedi;/往下一个坐标位置的方向SElemType;typedefstruct/栈类型SElemType*base;/栈的尾指针SElemType*top;/栈的头指针intstacksize;/栈的大小SqStack;六、调试结果和分析a)测试结果实际程序执行过程如下图所示：数据结构集中上机试验报告班级：学号：0310XX姓名：燕文静题目：编制一个求解迷宫通路的程序以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。实验要求：实现一个以链表作存储结构的栈类型。然后编写一个求解迷宫的非递归程序。求得的通路以三元组的形式输出，其中指示迷宫中的一个坐标，d表示走到下一坐标的方向。实验过程：1.基

4、本算法以及分析：本程序主要是以链表构造栈的形式，寻找迷宫路径，根据创立的结点，输入结点里的一些数据，如下structStack/构造栈intMaze_x,Maze_y;/定义迷宫X，Y坐标Stack*next;/定义栈指针;程序由主函数开始，首先，定义一个二维数组迷宫。选择开始坐标点，然后，开始入栈，利用各个位置的判断循环建立结点，记录各个位置的数据，若走进死胡同则退栈，并且判断是否栈空，找到路径并到达出口后将栈倒置，使其按从入口到出口的顺序输出，之后调用迷宫图案输出函数，使其按要求输出。2.程序源代码：迷宫问题#include#includeusingnamespacestd;structStack/构造栈intMaze_x,Maze_y,Maze_z;/定义迷宫X，Y坐标,z方向Stack*next;/定义栈指针;Stack*ps;/链头指针voidPop()/出栈函数Stack*p;p=ps;ps=ps-next;deletep;voidpush(intx,inty,intz)/进栈函数Stack*t;t=newStack;t-Maze_x=x;t-Maze_y=y;t-Maze

5、_z=z;t-next=ps;ps=t;voidMazepath(inta10,inti,intj)/迷宫路线寻找函数aij=2;intc,d,m=1;/定义变量c,d为出口坐标,变量m作为走过的步数coutcd;while(i!=c|j!=d)/判断是否到达出口if(aij+1=0)/判断右边是否可行push(i,j,1);j+;aij=2;/标记走过的位置elseif(ai+1j=0)/判断下边是否可行push(i,j,2);i+;aij=2;/标记走过的位置elseif(aij-1=0)/判断左边是否可行push(i,j,3);j-;aij=2;/标记走过的位置elseif(ai-1j=0)/判断上边是否可行push(i,j,4);i-;aij=2;/标记走过的位置else/四个方向都不可行，退栈inte1,e2;Stack*p;p=ps;ps=ps-next;e1=p-Maze_x;e2=p-Maze_y;ae1e2=3;/标记走过的死胡同坐标deletep;/删除栈顶元素i=ps-Maze_x;j=ps-Maze_y;if(ps=NULL)/判断栈空否coutnext=NUL

6、L;while(ps!=NULL)/倒置栈中的数据,使其从开始坐标输出Stack*t;l;t=ps;ps=ps-next;t-next=pk-next;pk-next=t;Stack*k=pk;pk=pk-next;delete(k);/释放PK空间while(pk!=NULL)/输出走过的坐标coutMaze_xMaze_yMaze_znext;deletek;coutab;Mazepath(Maze,a,b);coutnext(5)输出迷宫通路的字符图形voidprintonglu2()此函数根据堆栈内栈顶与“次栈顶”的位置关系决定输出字符，或，其中2=，3=，4=，5=所有的操作都是在备份矩阵backup上。出口位置输出inti，z，j；Mlink*p=stack；p不空if(p-rowp-next-row)backupp-next-rowp-next-col=5;下一位置在下elseif(p-rownext-row)backupp-next-rowp-next-col=2;下一位置在上elseif(p-colp-next-col)backupp-next-rowp-next-c

7、ol=4;下一位置在右else;下一位置在左利用for循环，i，j为循环控制变量输出备份矩阵backup为0是输出“”为1是输出“”为2是输出“”为3是输出“”为4是输出“”为5是输出“”为6是输出“”另外在输出语句上，与矩阵输出相同，标明了行号与列号3、主函数voidmenu()定义迷宫数组矩阵mazeM+2N+2定义辅助数组abcM+2N+2以用来在可以在第一次产生迷宫中重复选择入口与出口定义变量k以用来控制循环定义整型变量x1，y1，用于存储入口。定义整型变量x2，y2，用于存储出口。定义整型变量x用于接收mazepash的返回值。输入入口与出口。如果x=1则条用函数printonglu1();printonglu2();否则提示无通路。界面开始会显示：数据结构一、【实验构思】(10%)实验实现基本思路：若当前位置可通，则纳入当前路径，并继续朝下一个位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。设以栈记录当前路径，则栈顶中存放的是当前路径上最后一个通道块。由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的才操作即为出栈。二、【实验设计(Design)】(20%)抽象数据类型：typedefstructintx;/当前位置的横坐标inty;/当前位置的纵坐标chartype;/当前位置的属性：墙壁或通道(0/1)boolisfoot;/判断当位置是否已走过,true代表已走过Position;/当前位置信息typedefstructintorder;/脚步在地图上的序号Positionseat;/行走的当前位置intaspect;/下一步的方向Block;/脚步typedefstructintwidth;/地图的长度intheight;/地图的宽度Position*site;/地图内的各个位置Maze;/地图typedefstructBloc

《迷宫问题,实验报告(共10篇)》由会员bin****86分享，可在线阅读，更多相关《迷宫问题,实验报告(共10篇)》请在金锄头文库上搜索。