数据结构-迷宫实验报告.doc

（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A □ B □ C □ 实验难度 A □ B □ C □ 承担任务 （难度为C时填写） 指导教师评分 （签名） 【实验题目】 实验4.数组的表示极其应用 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(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%) （本部分）Design)】(20%) （本部分）ADT Maze { 数据对象：D = { ai, j | ai, j ∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row, col≤18 } 数据关系：R = { ROW, COL } ROW = { ai-1, j, ai, j | ai-1, j, ai, j ∈D, i=1, … , row+1, j=0, … , col+1}COL = { ai, j-1, ai, j | 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) 初始条件：迷宫Maze已存在。 操作结果：将迷宫输出到屏幕，“□”表示通路，“■”表示障碍。 MazePath( Maze) 初始条件：迷宫Maze已存在。 操作结果：计算路径。 PrintPath( Maze) 初始条件：迷宫Maze已存在。 操作结果：若迷宫存在一条通路，将路径输出至屏幕，以“→”“←”“↑”“↓”表示可行路径，“※”表示途径过却无法到达出口的位置；若不存在通路，报告相应信息。 } ADT Maze； 2. 设定栈的抽象数据类型定义： ADT Stack { 数据对象：D = { ai | ai ∈ CharSet, i=1, 2, … , n, n≥0 } 数据关系：R1 = { ai-1, ai | ai-1, ai ∈D, i=2, … , n} 基本操作： InitStack(S) 操作结果：构造一个空栈。 Push(S, e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(S, e) 初始条件：栈S已存在 . 操作结果：删除S的栈顶元素，并以e返回其值。 } ADT Stack； 3. 本程序包含三个模块 1)主程序模块： void main() { 初始化; do { 接受命令; 处理命令; } while (命令! = 退出); } 2)栈模块——实现栈抽象数据类型； 3)迷宫模块——实现迷宫抽象数据类型。 4各模块之间的调用关系如下： 主程序模块 迷宫模块 栈模块Implement）】(30%) （本部分1. 迷宫与栈类型 int maze[M][N], row, col ; typedef struct //存放迷宫访问到点的行，列，方向 { int m,n,