云南大学软件学院数据结构实验4

实验难度： A B C 序号 学号 姓名 成绩指导教师 （签名）学期：2017 秋季学期 任课教师: 实验题目: 组员及组长: 承担工作： 联系电话: 电子邮件: 完成提交时间： 年 月 日云南大学软件学院 数据结构实验报告一、 【实验构思（Conceive ） 】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计等相关知识，对问题进行概要性地分析）首先输入迷宫数据，在计算机的屏幕上显示一个 8 行 8 列的矩阵表示迷宫。矩阵中的每个数据或为通路（以 0 表示），或为墙（以 1 表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。假设以栈 S 记录“当前路径” ，则栈顶中存放的是“当前路径上最后一个通道块” 。由此， “纳入路径”的操作为“当前位置入栈” ；从当前路径删除前一通道块的操作为“出栈” 。若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径坐标。二、 【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的定义和基本操作说明，程序包含的模块以及各模块间的调用关系，关键算法伪码描述及程序流程图等，如有界面则需包括界面设计，功能说明等）1、定义坐标（X， Y）:struct Coor int row; int column; int direction; ; 2、定义方向：struct Move int row;int column;3、定义/链表结点：struct LinkNode Coor data;LinkNode *next;4、定义栈：class stackprivate:LinkNode *top; public:stack(); stack(); void Push(Coor data); Coor Pop(); Coor GetPop(); void Clear(); bool IsEmpty(); ;5.流程图：三、 【实现（Implement） 】(30%)（本部分应包括：抽象数据类型各操作的具体实现代码、 关键操作的具体算法实现、 函数实现，主程序实现等，并给出关键算法的时间复杂度分析。如有界面则需包括界面的关键实现方法等。 ）1.定义迷宫定义移动的 4 个方向：Move move4=0,1,1,0,0,-1,-1,0;2.几个函数功能的描述:stack(); /构造函数，置空栈stack(); /析构函数void Push(Coor data); /把元素 data 压入栈中Coor Pop(); /使栈顶元素出栈Coor GetPop(); /取出栈顶元素void Clear(); /把栈清空bool IsEmpty(); /判断栈是否为空bool Mazepath(int *maze,int m,int n); /寻找迷宫 maze 中从（0 ， 0）到（m,n ）的路径/到则返回 true,否则返回 falsevoid PrintPath(stack p); /输出迷宫的路径void PrintPath2(int m,int n,stack p,int *maze); /输出路径void Restore(int *maze,int m,int n); /恢复迷宫3.主函数实现：int main()system(color f5);int m=0,n=0;int *maze; /定义二维指针存取迷宫cout =0&ch=1) cout#include#include#define true 1#define false 0using namespace std;struct Coor /定义描当前位置的结构类型int row;int column;int direction;struct Move /定义下一个位置的方向int row;int column;struct LinkNode /链表结点Coor data;LinkNode *next;class stack /定义栈private:LinkNode *top;public:stack(); /构造函数，置空栈stack(); /析构函数void Push(Coor data); /把元素 data 压入栈中Coor Pop(); /使栈顶元素出栈Coor GetPop(); /取出栈顶元素void Clear(); /把栈清空int IsEmpty(); /判断栈是否为空;stack:stack() /构造函数，置空栈top=NULL;stack:stack() /析构函数void stack:Push(Coor x)/把元素 data 压入栈中LinkNode *TempNode;TempNode=new LinkNode;TempNode-data=x;TempNode-next=top;top=TempNode;Coor stack:Pop() /使栈顶元素出栈Coor Temp;LinkNode *TempNode;TempNode=top;top=top-next;Temp=TempNode-data;delete TempNode;return Temp;Coor stack:GetPop() /取出栈顶元素return top-data;void stack:Clear() /清空栈top=NULL;int stack:IsEmpty() /判断是否空栈if(top=NULL)return true;elsereturn false;Move move4=0,1,1,0,0,-1,-1,0; /定义移动的 4 个方向int Mazepath(int *maze,int m,int n); /寻找迷宫 maze 中从（ 0，0）到（m,n ）的路径，找到则返回 true,否则返回 falsevoid PrintPath(stack p); /输出迷宫的路径void PrintPath2(int m,int n,stack p,int *maze); /输出路径void Restore(int *maze,int m,int n); /恢复迷宫int* GetMaze(int /获取迷宫/返回存取迷宫的二维指针int main()system(color f5);int m=0,n=0;int *maze; /定义二维指针存取迷宫cout ab;coutmazeij;/给迷宫的四周加一堵墙，即把迷宫四周定义为 1for(i=0;i=1)coutchoose;if(choose=1)PrintPath(p); /坐标显示输出Restore(maze,m,n);elsePrintPath2(m,n,p,maze); /矩阵显示输出Restore(maze,m,n);return 1; /表示成功找到路径if(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column)/如果没有新位置入栈，则返回到上一个位置p.Pop();q.Pop();return 0; /表示查找失败，即迷宫无路经void PrintPath(stack p) /输出路径coutdata=p.Pop(); /取栈 p 的顶点元素，即第一个位置t.Push(temp-data); /第一个位置入栈 tdelete temp; /释放空间while(!p.IsEmpty() /栈 p 非空，则反复转移temp=new LinkNode;temp-data=p.Pop(); /获取下一个位置/得到行走方向a=t.GetPop().row-temp-data.row; /行坐标方向b=t.GetPop().column-temp-data.column;/列坐标方向if(a=1) temp-data.direction=1; /方向向下，用 1 表示else if(b=1) temp-data.direction=2; /方向向右，用 2 表示else if(a=-1) temp-data.direction=3;/方向向上，用 3 表示else if(b=-1) temp-data.direction=4;/方向向左，用 4 表示t.Push(temp-data); /把新位置入栈delete temp;cout坐标（row,column,direction）中 x 在指向当前位置所在的行数，y 指向当前位置所在的列数，;coutdirection 表示下一位置走向。endl;/输出路径，包括行坐标，列坐标，下一个位置方向while(!t.IsEmpty() /栈非空，继续输出data=t.Pop();cout(data.row,data.column,data.direction,; /输出行坐标，列坐标switch(data.direction) /输出相应的方向case 1:cout)n;break;case 2:cout)n;break;case 3:cout)n;break;case 4:cout)n;break;case 0:cout)n;break;void PrintPath2(int m,int n,stack p,int *maze)/输出路径cout迷宫的路径为n;for (int i = 0; i m+2; +i )for (int j = 0; j n+2; +j)cout mazeij ;cout endl;void Restore(int *maze,int m,int n)/恢复迷宫int i,j;for(i=0;im+2;i+) /遍历指针for(j=0;jn+2;j+)if(mazeij=8) /恢复探索过位置，即把-1 恢复为 0mazeij=0;