数据结构集中上机 试验报告 班级：031021 学号：03102017 姓名：燕文静 题目：编制一个求解迷宫通路的程序 以一个 M*N 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 实验要求： 实现一个以链表作存储结构的栈类型。然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i , j , d）的形式输出，其中（i , j ）指示迷宫中的一个坐标，d 表示走到下一坐标的方向。 实验过程： 1.基本算法以及分析： 本程序主要是以链表构造栈的形式，寻找迷宫路径，根据创立的结点，输入结点里的一些数据，如下 struct Stack //构造栈 { int Maze_x,Maze_y; //定义迷宫 X，Y 坐标 Stack * next; //定义栈指针 } ; 程序由主函数开始，首先，定义一个二维数组迷宫。选择开始坐标点，然后，开始入栈，利用各个位置的判断循环建立结点，记录各个位置的数据，若走进死胡同则退栈，并且判断是否栈空，找到路径并到达出口后将栈倒置，使其按从入口到出口的顺序输出，之后调用迷宫图案输出函数，使其按要求输出。 二．概要设计 1. 抽象数据类型定义为： ADT stack{ 数据对象：D={ai|ai∈LinkList, i=1,2,...n, n≥0} 数据关系：R1={|ai-1,ai∈D|=2,„„n } ，即当前结点与下一个结点的关系 基本操作： stack(); 构造函数，建立一个空栈； 操作结果：通过字符串 a 构造两个位数不限的长整数。 void Push(DataType data); 初始条件：已存在栈 操作结果：把元素 data 压入栈顶 DataType Pop(); 初始条件：已存在栈，且非空 操作结果： 栈顶元素出栈，且删除栈顶元素 DataType GetPop(); 初始条件：已存在栈，且非空 操作结果：获取栈顶元素 void Clear(); 初始条件：已存在栈 操作结果：把当前的栈清空 bool IsEmpty(); 初始条件：已存在栈 操作结果：如果栈为空，则结果为“真”，否则为“假” }ADT OrderedList 2.程序源代码： #include #include using namespace std; struct Stack //构造栈 { int Maze_x,Maze_y,Maze_z; //定义迷宫 X，Y坐标,z方向 Stack * next; //定义栈指针 }; Stack *ps; //链头指针 void Pop() //出栈函数 { Stack *p; p = ps; ps=ps->next; delete p; } void push(int x,int y,int z) //进栈 ...
