资源描述：
《数据结构-迷宫实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□B□C□实验难度A□B□C□承担任务（难度为C时填写）指导教师评分（签名）【实验题目】实验4.数组的表示极其应用【问题描述】以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中
2、:(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如；对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，…。（下面的内容由学生填写，格式统一为，字体:楷体,行距:固定行距18，字号:小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验的目的是设计一个程序，实现手动或者自动生成
3、一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在
4、迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）1.设定迷宫的抽象数据类型定义：ADTMaze{数据对象：D={ai,j
5、ai,j∈{‘■’、‘□’、‘※’、‘→’、‘←’、‘↑’、‘↓’},0≤i≤row+1,0≤j≤col+1,row,col≤18}数据关系：R={ROW,COL}ROW={
6、ai-1,j
7、,ai,j∈D,i=1,…,row+1,j=0,…,col+1}COL={
8、ai,j-1,ai,j∈D,i=0,…,row+1,j=1,…,col+1}基本操作：Init_hand_Maze(Maze,row,col)初始条件：二维数组Maze[][]已存在。操作结果：手动初始化迷宫，0表示通路，1表示障碍。Init_automatic_Maze(Maze,row,col)初始条件：二维数组Maze[][]已存在。操作结果：自动初始化迷宫，0表示通路，1表示障碍。PrintMaze(Maze)初始
9、条件：迷宫Maze已存在。操作结果：将迷宫输出到屏幕，“□”表示通路，“■”表示障碍。MazePath(Maze)初始条件：迷宫Maze已存在。操作结果：计算路径。PrintPath(Maze)初始条件：迷宫Maze已存在。操作结果：若迷宫存在一条通路，将路径输出至屏幕，以“→”“←”“↑”“↓”表示可行路径，“※”表示途径过却无法到达出口的位置；若不存在通路，报告相应信息。}ADTMaze；2.设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai
10、ai∈CharSet,i=1,2,…,n,n≥0}数据关系：R
11、1={
12、ai-1,ai∈D,i=2,…,n}基本操作：InitStack(&S)操作结果：构造一个空栈。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S已存在.操作结果：删除S的栈顶元素，并以e返回其值。}ADTStack；3.本程序包含三个模块1)主程序模块：voidmain(){初始化;do{接受命令;处理命令;}while(命令!=退出);}2)栈模块——实现栈抽象数据类型；3)迷宫模块——实现迷宫抽象数据类型。4各模块之间的调用
13、关系如下：主程序模块迷宫模块栈模块三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）1.迷宫与栈类型intmaze[M][N],row,col;typ
