数据结构课程设计VIP免费

数据结构课程设计实习报告题目：模拟走迷宫过程号：专业：完成日期：授课教师：1.题目模拟走迷宫过程。2.要求习题内容：模拟走迷宫过程。1使用二维数组保存迷宫；2设计算法，从入口进入迷宫，在有出口的情况下，找到出口；3改进算法，找到从入口到出口的最短路径。要求：编写递归方法mazeTraverse走迷宫。该方法需要两个参数：表示迷宫的N*N字符数组和迷宫的起始位置。在mazeTraverse试图找到出口的过程中，将字符#放入路径中走过的每一格。每走一步，方法都应显示整个迷宫，以便用户能看清是怎样走出迷宫的。算法介绍：有一个简单的走迷宫算法，它保证能找到出口（假定有出口）。如果没有出口，就重新回到出发点。将右手放在身体右边的墙壁上，开始向前走。始终不要将手从墙上移开。如果迷宫向右转，就跟着墙壁向右边走。只要不将手从墙壁上移走，最终都将达到迷宫的出口。也许有其他比刚才所选的更短的路径，但是只要遵循这个算法，保证能走出迷宫。输入数据格式：下列由符号“1”和“0”组成的网格是一个表示迷宫的二维数组。其中，“1”号表示迷宫的墙，“0”表示穿越迷宫的可能路径中的方格。只有在数组中含有符号（0）的地方才可以走。100010000001A.口01010111101111010000101100001110100出111101010101100101010101110101010101100000000101111111011101100000010001111111111111输出数据格式:1111111111111XXX1XXXXXX1入口XX1X1X1111X1111X1XXXX1X1出口1XXXX111X1XX1111X101X1X11XX1X101X1X111X1X101X1X11XXXXXXXX1X11111111111111XXX1XXXXXX1入口XX1X1X1111X1111X1XXXX1X1出口1XXXX111X1XX1111X101X1X11XX1X101X1X111X1X101X1X11XXXXXXXX1X13.程序实现3.1程序运行及编译环境Windowsxp系统,VC++6.03.2程序描述该程序使用递归的方法,完成对一个由数字01构成的矩阵迷宫,0表示通路1表示墙壁,通过程序的调用可以在原矩阵中标记出一条从出口到入口间的最短路径。3.3实现功能介绍该程序应具有的功能，可采用PO图(即输入一处理一输岀图)的形式。说明：如果该程序只有单一功能时可以直接描述其输入项输、出项等等各个部分,否则按照各个子功能模块分别介绍。3.3.1子功能模块1该函数为程序的核心，函数通过递归的方法找到一条从起始点(有函数的参数x,y引入)到终点(全局常量x2,y2)的路径，并将路径在原来迷宫数组中标记出来(将经过的位置数字0改为6)。注意由于递归函数的水用，标记路径的过程实际上与走迷宫的过程相反，即从终点到起始点。代码如下：〃从迷宫中坐标仗，y)的位置寻找通向终点m，门)的路径若找到则返回fee,否则返回falseboolSeekPath(intx,inty){//i作为循环变量，代表从当前位置移动到下一个位置的方向inti;//g和h作为下一个位置的行坐标和列坐标intg,h;//达到递归岀口，返回tee结束程序if((x==x2)&&(y==y2))returntrue;/依次按每个方向寻找通向终点的路径，0,1,2,3分别为东南西北for(i=0;iv4;i++){/求岀下一个位置的行坐标和列坐标g=x+move[i][0];h=y+move[i][1];〃若下一个位置可通行同时没有被访问过，则从该位置寻找if((maze[g][h]==0)&(mark[g][h]==O)){//置mark数组中对应位置为7,表明已访问过mark回[h]=1;〃当条件成立时，表明从(，h)到终点存在通路加将对应位置中maze数组中的值给为6,对走过的通路进行标记，同时返回ue结束递归〃否则进入下一轮循环，向下一个方向试探if(SeekPath(g,h)){maze[g][h]=6;returntrue;}}}〃从当前位置g,h)没有找到通往终点的路径，应返回sereturnfalse;}3・3・1・1输入项迷宫得起点由函数的参数X,y)引入，终点由全局常量X2,y2)引入，数组maze[][]mark[][为全局变量，以上数据均为nt型3.3.1.2输出项不直接输出，只返回是否找到路径3.3.1.3数据结构的定义3.3.1全局数据结构3.3.2局部数据结构3.3.1.4算法及程序说明函数为递归函数递归出口为找到迷宫出口循环试探每个方向的下一个位置，当maze[h][g]的值为0且mark[h][g]的值为0,即位置可走且没有被走过时，选择该位置，改变mark[h][g]为1即该位置走过，然后将此位置作为当前位置，递归调用函数，寻找下一个可行位置。当四个方向不可行时，则向他的上一级调用函数返回Se，退回前一个...