数据结构程序设计(迷宫问题)

《数据结构程序设计(迷宫问题)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、合肥工业大学数据结构课程设计报告课程设计名称：迷宫问题的数据结构C++描述班级：信息与计算科学1班姓名：刘石清20106583张任重20106607指导老师：王青山王琦1.实验目的及要求1）、设计目标（问题描述）迷宫问题：编写一个程序求解迷宫问题。迷宫以m行n列的长方阵表示，0和1分别表示迷宫中通路和障碍。设计一个程序，对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。算法要点：创建迷宫，试探查找路径，输出解                 2）、 需求分析1、本程序实现迷宫的探索

2、过程.以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径2.实验内容1）、设计概述(a)开发平台：Visual

3、C++6.0(b)参考书籍：1.数据结构C++描述熊岳山陈怀义编著2、《数据结构与算法》黄定 黄煜廉 编著 3、《数据结构辅导与提高》徐孝凯 编著 2）、处理流程(a)画出功能结构图(b)画出主要数据结构的类图class类名DataType//定义描述迷宫中当前位置的类型数据成员访问控制权限数据类型变量名;public:intx;//x代表当前位置的行坐标inty;//y代表当前位置的列坐标intpre;//pre表示移动到下一步的方向class类名Move//定义下一个位置的方向数据成员访问控制

4、权限数据类型变量名;public:intx;inty;class类名Node//结点数据成员访问控制权限数据类型变量名;public:DataTypedata;Node*next;class类名stack数据成员访问控制权限数据类型变量名;private:Node*top;//指向第一个结点的栈顶指针成员函数访问控制权限返回值类型函数名(参数列表)public:stack();//构造函数，置空栈~stack();//析构函数voidPush(DataTypedata);//把元素data压入栈中

5、DataTypePop();//使栈顶元素出栈DataTypeGetPop();//取出栈顶元素voidClear();//把栈清空boolIsEmpty();//判断栈是否为空，如果为空则返回1，否则返回03）、源程序#include#include#includeusingnamespacestd;classDataType//定义描述迷宫中当前位置的类型{public:intx;//x代表当前位置的行坐标inty;//y代表当前位置的列坐

6、标intpre;//pre表示移动到下一步的方向};classMove//定义下一个位置的方向{public:intx;inty;};classNode//链表结点{public:DataTypedata;Node*next;};classstack//下面定义栈{private:Node*top;//指向第一个结点的栈顶指针public:stack();//构造函数，置空栈~stack();//析构函数voidPush(DataTypedata);//把元素data压入栈中DataTypePop

7、();//使栈顶元素出栈DataTypeGetPop();//取出栈顶元素voidClear();//把栈清空boolIsEmpty();//判断栈是否为空，如果为空则返回1，否则返回0};stack::stack()//构造函数，置空栈{top=NULL;}stack::~stack()//析构函数{}voidstack::Push(DataTypex)//进栈{Node*TempNode;TempNode=newNode;TempNode->data=x;TempNode->next=top;

8、top=TempNode;}DataTypestack::Pop()//栈顶元素出栈{DataTypeTemp;Node*TempNode=NULL;TempNode=top;top=top->next;Temp=TempNode->data;deleteTempNode;returnTemp;}DataTypestack::GetPop()//取出栈顶元素{returntop->data;}voidstack::Clear()//把栈清空{top=NULL;}boolstack: