数据结构集中上机实验报告.doc

XX大学 信息与计算科学专业 2008级《数据结构》集中上机 设计题目： 迷宫求解一、实验内容 2 二、需求分析 2 三、总体设计 2 （一）存储结构 2 （二）流程图 3 四、详细设计 3 （一）基本算法解析 3 （二）为实现算法，需要的象的数据类型 4 (三)函数的调用关系 5 （四）算法时间、空间复杂度 5 五、代码 5 六、运行结果分析 10 （一）迷宫路径探索成功 10 （二）迷宫路径未找到的情况 13 （三）程序的优缺点与改进 13 七、参考文献 14 八、心得体会 14 一、实验内容 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出　　可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；InitStack；压入新数据元素Push；栈顶元素出栈Pop。 （2）构造求迷宫路径函数。其中定义了二维数组maze[M][N]存取迷宫数据；输出找到的通路MazePath。 （3）建立一个迷宫initmaze。其中包括输入迷宫行数列数以及各行各列；加一圈围墙并输出迷宫。 三、总体设计 （一）存储结构： 首先用二维数组存储迷宫数据，迷宫数据由用户输入。 一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。 从入口出发，顺着某一个方向进行探索，若能走通，继续往前走，否则沿原路退回，换 一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到但没能到达出口，则所设置的迷宫没有通路。 迷宫的入口点的下标（a,b），出口点的下标（m,n）。为方便，可在迷宫周围加一周障碍。对于迷宫的任意位置，均可约定有东西南北4个方向可以走通。经过的位置把0变成-1，输出迷宫路径。 2本程序有三个模块; 主程序模块 三个模块即其对象，实现栈链表抽象数据类型 迷宫存储迷宫，寻路径，输出迷宫。 （二）流程图 四、详细设计 （一）基本算法解析： 首先用二维数组存储迷宫数据，迷宫数据由用户输入。 一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。 迷宫的过程可以模拟成一个有哪些信誉好的足球投注网站的过程。每到一处，总让它按东西南北四个方向顺序试探下一个位置，如果某方向可以通过，并且不曾到达，则前进一步，在新的位置上继续进行探索。如果4个方向都走不通或者曾经到达过，则退回一步，在原来的位置上继续试探下一位置。 每前进一步或后退一步，都要进行判断，若前进到了出口处，则说明找到了一条通路，若退回到了入口处，则说明不存在通路。 用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（a,b）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为期寻找一条从入口点到出口点的通路。 二维数组的0行m+1列元素全置成“1”，表示迷宫的外墙，第一行第一列元素和第m行m列元素置成“0”，表示迷宫的入口和出口。 假设当前所在位置是（x,y）。延某个方向前进一步，它可能到达的位置最多有4。 如果用结构体Element elem记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用结构体Element elem确定 while(!StackEmpty(S1)) //栈不为空 有路径可走 { Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; 从迷宫的入口位置开始，沿图示方向顺序依次进行有哪些信誉好的足球投注网站。定义一个栈，按从入口到出口存取路径，在有哪些信誉好的足球投注网站过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中，当前位置“-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。 如果没有新位置入栈，则返回到上一个位置。 一直到达出口。 总之，入口出发，顺着某一个方向进行探索，若能走通，则继续往前进，否则沿着原路返回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 迷宫的入口点在位置（1,1），出口点在位置（m,n）。为处理方便，可在迷宫的四周加一周障碍。对于迷宫的任一位置，均可定为东南西北四个方向可通。 （二）为实现算法，需要的象的数据类型 InitStack() 构造空栈 StackEmpty() 判断栈是否为空 Push() 压入新数据元素 Pop()