《数据结构程序设计(迷宫问题)》由会员分享，可在线阅读，更多相关《数据结构程序设计(迷宫问题)（17页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学数据结构课程设计报告 课程设计名称：迷宫问题的数据结构 C+描述班 级：信息与计算科学 1 班姓 名：刘石清 20106583张任重 20106607指 导 老 师：王青山 王琦1.实验目的及要求1） 、设计目标（问题描述）迷宫问题：编写一个程序求解迷宫问题。迷宫以 m 行 n 列的长方阵表示，0 和 1 分别表示迷宫中通路和障碍。设计一个程序，对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。算法要点：创建迷宫，试探查找路径，输出解2） 、 需求分析1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演
2、示程序中规定的运算命令，然后程序就探索路径并输出路径。 2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径2. 实验内容1） 、设计概述(a) 开发平台：Visual C+ 6.0(b) 参考书籍：1.数据结构 C+描述 熊岳山 陈怀义 编著 2、 数据结构与算法黄定 黄煜廉 编著 3、 数据结构辅导与提高徐孝凯 编著 2） 、处理流程(a)画
3、出功能结构图(b)画出主要数据结构的类图class 类名 DataType /定义描述迷宫中当前位置的类型访问控制权限 数据类型 变量名; 数据成员public:int x; /x 代表当前位置的行坐标int y; /y 代表当前位置的列坐标int pre; /pre 表示移动到下一步的方向class 类名 Move /定义下一个位置的方向访问控制权限 数据类型 变量名; 数据成员public:int x; int y;class 类名 Node /结点访问控制权限 数据类型 变量名; 数据成员public:DataType data;Node *next;class 类名 stack访问控制
4、权限 数据类型 变量名; 数据成员private:Node *top; /指向第一个结点的栈顶指针访问控制权限 返回值类型 函数名(参数列表) 成员函数public:stack(); /构造函数，置空栈stack(); /析构函数void Push(DataType data);/把元素 data 压入栈中DataType Pop(); /使栈顶元素出栈DataType GetPop(); /取出栈顶元素void Clear(); /把栈清空bool IsEmpty(); /判断栈是否为空，如果为空则返回 1，否则返回 03） 、源程序#include#include#includeusing
5、 namespace std;class DataType /定义描述迷宫中当前位置的类型public:int x; /x代表当前位置的行坐标int y; /y代表当前位置的列坐标 int pre; /pre表示移动到下一步的方向; class Move /定义下一个位置的方向 public:int x; int y;class Node /链表结点public:DataType data;Node *next;class stack /下面定义栈private:Node *top; /指向第一个结点的栈顶指针public:stack(); /构造函数，置空栈stack(); /析构函数voi
6、d Push(DataType data);/把元素data压入栈中DataType Pop(); /使栈顶元素出栈DataType GetPop(); /取出栈顶元素void Clear(); /把栈清空bool IsEmpty(); /判断栈是否为空，如果为空则返回1，否则返回0;stack:stack() /构造函数，置空栈top=NULL;stack:stack() /析构函数void stack:Push(DataType x) /进栈Node *TempNode;TempNode=new Node;TempNode-data=x;TempNode-next=top;top=Temp
7、Node;DataType stack:Pop() /栈顶元素出栈DataType Temp;Node *TempNode=NULL; TempNode=top;top=top-next;Temp=TempNode-data;delete TempNode;return Temp;DataType stack:GetPop() /取出栈顶元素return top-data;void stack:Clear() /把栈清空top=NULL;bool stack:IsEmpty() /判断栈是否为空，如果为空则返回1，否则返回0if(top=NULL) return true;else retur
8、n false;/*Description: 外部函数的声明部分*/bool findpath(int *maze,int m,int n); /寻找迷宫路径 void PrintPath(stack p); /输出路径void Restore(int *maze,int m,int n); /恢复迷宫Move move4=0,1,1,0,0,-1,-1,0; /定义当前位置移动的4个方向(上，右，下，左)int* readFile (int int* writeFile(int /*Description: main.cpp*/void main() cout从文件中读取直接自行输入ch;i
9、f(ch=a)maze=readFile(m,n);flag=1;else if(ch=b)maze=writeFile(m,n);flag=1;else coutc;if(c=n) flag1=1;else flag=0;coutb; /输入迷宫的长和宽couta; coutmazeij;coutchoose;if(choose=Y|choose=y)char ch;string str;coutstr; ofstream open(str.c_str(); for(i=1;idata=p.Pop(); t.Push(temp-data); /第一个位置入栈delete temp; whil
10、e(!p.IsEmpty() /栈p非空，则转移temp=new Node;temp-data=p.Pop(); /获取下一个位置/得到行走方向row=t.GetPop().x-temp-data.x; /行坐标方向 column=t.GetPop().y-temp-data.y; /列坐标方向if(row=1) temp-data.pre=1; /向下，用1表示else if(column=1) temp-data.pre=2; /向右，用2表示else if(row=-1) temp-data.pre=3; /向上，用3表示else if(column=-1) temp-data.pre=
11、4; /向左，用4表示t.Push(temp-data); /把新位置入栈delete temp;while(!t.IsEmpty() /栈非空，继续输出data=t.Pop();cout (data.x,data.y,; switch(data.pre) /输出相应的方向 case 0:cout)n;break;case 1:cout向下)n;break;case 2:cout向右)n;break;case 3:cout向上)n;break;case 4:cout向左)n;break;/*Description: 恢复路径函数*/void Restore(int *maze,int m,in
12、t n) /恢复迷宫int i,j;for(i=0;im+2;i+) /遍历指针for(j=0;jn+2;j+) if(mazeij=-1) /恢复探索过位置，即把-1恢复为0mazeij=0;4）、运行结果3. 实验总结分析1)、时间和空间分析该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比，迷宫长为m，宽为 n，在最好情况下的时间和空间复杂度均为 O（m+n） ，在最差情况下均为 O（m*n） ，平均情况在它们之间2)、程序的优点a. 进入演示程序后即显示文本方式的用户界面b. 本程序模块划分比较合理，且利用指针存储迷宫，操作方便。能按照玩游戏人的意愿任意输入迷宫大小，并且可以保存新输入的迷宫，方便退出游戏后仍可打开自己定义文件查看迷宫。3)、自我评价、经验体会等通过这次课程设计，体会如下：、进一步熟悉掌握了有关栈的基本操作；、对迷宫有了更多的认识3、更进一步掌握有关类的操作4、由于对栈的算法推敲不足，使程序调试时费时不少
