数据结构课程设计

1、数据结构课程设计实习报告题目：模拟走迷宫过程学号：姓名：年级：学院：专业：完成日期：授课教师:1.题目模拟走迷宫过程2.要求习题内容:模拟走迷宫过程。1使用二维数组保存迷宫；2设计算法，从入口进入迷宫，在有出口的情况下，找到出口;3改进算法，找到从入口到出口的最短路径。要求:编写递归方法mazeTravers熊迷宫。该方法需要两个参数：表示迷宫的N*N字符数组和迷宫的起始位置。在mazeTraverse试图找到出口的过程中，将字符#放入路径中走过的每一格。每走一步，方法都应显示整个迷宫，以便用户能看清是怎样走出迷宫的。算法介绍：有一个简单的走迷宫算法，它保证能找到出口（假定有出口）。如果没有出

2、口，就重新回到出发点。将右手放在身体右边的墙壁上，开始向前走。始终不要将手从墙上移开。如果迷宫向右转，就跟着墙壁向右边走。只要不将手从墙壁上移走，最终都将达到迷宫的出口。也许有其他比刚才所选的更短的路径，但是只要遵循这个算法，保证能走出迷宫。输入数据格式：下列由符号“1”和“0”组成的网格是一个表示迷宫的二维数组。其中，“1”号表示迷宫的墙，“0”表示穿越迷宫的可能路径中的方格。只有在数组中含有符号（0）的地方才可以走。1111111111入口*J01111111100010000001010101111011101000010100001110100111010101010010101010

3、11010101010100000000101111110111010000001000111111111111出口以输出数据格式:1111111111111XXX1XXXXXX1入口XX1X1X1111X1111X1XXXX1X11XXXX111X1XX1111X101X1X11XX1X101X1X111X1X101X1X11XXXXXXXX1X11111111111111XXX1XXXXXX1入口XX1X1X1111X1X1出口XXX1111X1XXXX11XXXX111X11111X101X11XX1X101X1X111X1X101X1X11XXXXXXXX1X13.程序实现3.1 程序

4、运行及编译环境Windowsxp系统,VC+6.03.2 程序描述该程序使用递归的方法，完成对一个由数字01构成的矩阵迷宫，0表示通路1表示墙壁，通过程序的调用可以在原矩阵中标记出一条从出口到入口间的最短路径。3.3 实现功能介绍该程序应具有的功能，可采用ipo图（即输入一处理一输出图）的形式。说明：如果该程序只有单一功能时可以直接描述其输入项、输出项等等各个部分，否则按照各个子功能模块分别介绍。3.3.1 子功能模块1该函数为程序的核心，函数通过递归的方法找到一条从起始点（有函数的参数x,y引入）到终点（全局常量x2,y2）的路径，并将路径在原来迷宫数组中标记出来（将经过的位置数字0改为6）

5、。注意由于递归函数的水用，标记路径的过程实际上与走迷宫的过程相反，即从终点到起始点。代码如下：从迷宫中坐标（x,v）的位置寻找通向终点（m,n）的路径若找到则返回true,否则返回falseboolSeekPath（intx,inty）/i作为循环变量，代表从当前位置移动到下一个位置的方向inti;/g和h作为下一个位置的行坐标和列坐标intg,h;达到递归出口，返回true结束程序if（x=x2）&&（y=y2）returntrue;/依次按每个方向寻找通向终点的路径，i=0,1,2,3分别为东南西北for（i=0;i<4;i+）求出下一个位置的行坐标和列坐标g=x+m

6、ovei0;h=y+movei1;若下一个位置可通行同时没有被访问过，则从该位置寻找if(mazegh=0)&(markgh=0)(置mark数组中对应位置为1,表明已访问过markgh=1;当条件成立时，表明从(g,h)到终点存在通路将对应位置中maze数组中的值给为6,对走过的通路进行标记，同时返回true结束递归否则进入下一轮循环，向下一个方向试探if(SeekPath(g,h)mazegh=6;returntrue;从当前位置(g,h)没有找到通往终点的路径，应返回falsereturnfalse;3.3.1.1 输入项迷宫得起点由函数的参数(x,y)引入，终点由全局常量(x2

7、,y2)引入，数组maze口口mark口口为全局变量，以上数据均为int型3.3.1.2 输出项不直接输出，只返回是否找到路径回falseo路径不通,返回，换一个3.3.1.3 数据结构的定义3.3.1全局数据结构3.3.2 局部数据结构3.3.1.4算法及程序说明函数为递归函数递归出口为找到迷宫出口循环试探每个方向的下一个位置，当mazehg的值为0且markhg的值为0,即位置可走且没有被走过时，选择该位置，改变markhg为1,即该位置走过，然后将此位置作为当前位置，递归调用函数，寻找下一个可行位置。当四个方向不可行时，则向他的上一级调用函数返回false,退回前一个节点，换一个方向寻找可行路径。以此类推，直到找到迷宫出口返回true,或者所有可行路径均不可达返SeekPath(x2,y2)终止点3.4 运行结果刘菁'数据结构*递归实现迷宫DebugT递归实现迷宫.111116111111011111601061111-10,101fl-0101TL1B1