数据结构课程设计迷宫问题

1、数据结构课程设计学 院：信息科学与工程学院专 业：计算机科学与技术2008 年 10 月 20 日数据结构课程设计一、说明：1、课程设计题目均选自数据结构习题集 ，请你根据所给页码及题目查阅相应内容，任选 其一确定自己设计的题目；2、题目一般分为基本要求和选做内容，选做内容将作为答优的基本要求；3、课程设计的成绩分为两部分：系统演示+设计报告。4、演示部分的检查在 12 教 803 室，在课程设计结束后一周。5、时间：第 8 周周一无课时间，第 8 周周六、周日 8:00-12:00,1:00-5:00 ，第 9 周周一无 课时间。地点 12 教五楼机房。二、题目：P77: 0.3- 海龟作图

2、；P80: 1.3- 集合的并、交和差运算（或者 1.4- 长整数四则运算） ；P105: 2.9- 迷宫问题；P152: 5.7- 表达式类型的实现；P153: 5.8- 全国交通咨询模拟。三、报告要求：完成以上实验内容并写出实验报告，报告应具有以下内容：1、实验内容2、概要设计3 、详细设计4、测试数据及程序运行情况5 、实验过程中出现的问题及解决方法6、实验体会四、实验报告要求全部为打印稿，格式统一（见附件实验报告格式） ，在程序演示检查完成 后一并教给老师。五、课程设计期间有问题，请到 12教803室找王永燕 ,周劲老师。1、实验内容【问题描述】以一个mx n的长方阵表示迷宫，0和1分

3、别表示迷宫中的通路和障碍。设计一个程序，对 任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】 首先实现一个链表作存储结构的栈类型， 然后编写一个求解迷宫的非递归程序。 求得的通路 以三元组（ i,j,d ）的形式输出，其中： （i,j ）指示迷宫中的一个坐标， d 表示走到下一坐 标的方向。【实现提示】 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若 能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一 条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解。 可以二维数组存储迷宫数据

4、，通常设定入口点的下标为（ 1， 1），出口点的下标为（ n,n）。 为处理方便起见， 可以迷宫的四周加一圈障碍。 对于迷宫任一位置， 均可约定有东、 南、西、 北四个方向可通。【选作内容】（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。2、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或 ppt 及实验） ADT T isData 当前位置的行坐标、当前位置的列坐标、走到下一位置的方向 end ADT T ADT Linknode isData 数据域、指针域OperationLinknode / 构造函数 用于构造结点 e

5、nd ADT LinkNode ADT Stack is Data栈顶指针OperationStack / 构造函数 输入：无 初始化栈：置空栈stack / 析构函数Push 输入：要进栈的项 e 前置条件：无 动作：把 e 压入栈顶 输出：无 后置条件：栈顶增加了一个新结点，栈顶指针指向新结点Pop 输入：无 前置条件：栈非空 动作：弹出栈顶元素 输出：返回栈顶元素的值 后置条件：删除栈顶元素GetPop 动作：返回栈顶元素的值Clear 动作：清空栈empty动作 : 检查栈顶指示是否等于 NULL 输出：栈空时返回 1，否则返回 0 end ADT Stack2) 功能模块设计(如主程

6、序模块设计)in t* GetMaze(i nt & m,i nt &n)返回存取迷宫的二维指针0)到(m,n)的路径bool Mazepath(int *maze,int m,int n)寻找迷宫 maze中从(0，void Prin tPath(Stack p) /输出路径void Restore(i nt *maze, int m,i nt n)/恢复迷宫主程序：用于调用其它函数3) 模块层次调用关系图调用调用类Class Stack调用调用Restore 把-1恢复成0GetMaze获得数组Prin tPath 输出路径调用 MazePath探索迷宫路径r、调用结点类C

7、lass Li nkNode<丿3、详细设计并对主要的模块1) 实现概要设计中定义的所有的类的定义及类中成员函数, 写出伪码算法。Class T无成员函数Class Li nkNode 无成员函数Class Stack Stack() top=NULL; Stack()void Push(T e)Li nkNode *P;P=new Lin kNode;P->data=e;P->n ext=top;top=P;T Pop()T Temp;Li nkNode *P;P=top;top=top->next;Temp=P->data;delete P; return T

8、emp;T GetPop() return top->data; void Clear(); bool empty();2) 输入的形式和输入值的范围 int* GetMaze(int &m,int &n)int *maze;/定义二维指针存取迷宫int i=0,j=0;coutvv"请输入迷宫的长和宽："；int a,b;cin>>a>>b;/输入迷宫的长和宽coutvv"请输入迷宫内容:n"m=a；n=b;/m,n 分别代表迷宫的行数和列数maze=new int *m+2;/申请长度等于行数加 2 的二

9、级指针for(i= 0;ivm+2;i+)/申请每个二维指针的空间mazei=new intn+2;for(i=1;iv=m;i+)/输入迷宫的内容， 1代表可通， 0代表不通for(j=1;jv=n;j+)cin>>mazeij;for(i=0;ivm+2;i+) mazei0=mazein+1=1;for(i=0;ivn+2;i+) maze0i=mazem+1i=1;return maze;/返回存贮迷宫的二维指针 maze;以二维数组的形式，一行一行的输入，定义二维指针来存储输入的二维数组， 这样就能灵活的自定义数组范围。本题中二维数组为 9行 8列，因为入口为 （1,1）

10、,在外面多加一圈障碍（ 2行 2列）都赋值为 1。3）输出的形式描述括号内的内容分别表示为 （行坐标 ,列坐标 ,数字化方向 ,方向 ），由这些数据 可以得到此迷宫的一条通路。coutvv'('vvdata.xvv','vvdata.yvv','vvdata.dirvv"," /输出行坐标，列坐标switch(data.dir)/输出相应的方向 case 1:cout<<" W)eak;case 2:cout<<"n"break;case 3:cout<<&qu

11、ot; nT)eak;case 4:cout<<"n"break;case 0:cout<<"）n"break;1：南2：东3：北4：西4）功能描述三个类：class T 定义描述迷宫中当前位置的数据类型其公有变量为：x（行坐标）、y （列坐标）、dir（东南西北四个方向）Class LinkNode 链表结点定义其公有变量为：T data, next域Class Stack 链栈存储定义及功能实现 主要函数功能：创建栈、进栈、出栈、取栈顶值、清空栈等。int* GetMaze（int &m,int &n） 存取迷

12、宫的二维指针函数， 申请 11行10列的指针 空间， 输入二位数组的内容， 输入形式如上。完成后返回二维指 针，得到二维数组。bool Mazepath（int *maze,int m,int n）寻找迷宫 maze中从（0，0）至U（m,n）的路 径，到则返回true,否则返回false。定义两个栈p,q,分别存储比 较过程和存储路径，如果 x 行 y 列有元素值为 0，则 xy 进栈 p, 并设 mazexy=-1. 当没有新元素进栈 p 时，说明当前元素周围 没有路径可以通过， 让其出栈， 直到退回到有路径可以再走的元 素那里， 然后再判断此路是否能通下去。循环反复，判断能否走 到最后。

13、void Restore（int *maze,int m,int n） 用于恢复判断路径时被设为 -1的值变为 0。 void PrintPath（Stack q）把函数Mazepath生成的栈p出栈，后存入另一定义的栈 t,逐一比较存入t的值和p栈顶的值，即可得出四个方向。然后 输出。int main（） 主函数4、测试数据及程序运行情况测试数据迷宫的测试数据如下：左上角（ 1， 1）为入口，右下角（ 4， 4）为出口。 0 1 1 10 1 1 10 0 0 11 1 0 0 运行结果如下： 迷宫路径为 括号内的内容分别表示为（行坐标，列坐标，数字化方向，方向）1，1，1，J)2，1，1，

14、J)3，1，2，T)3，2，2，T)3，3，1，J)4，3，2，T)4，4，0）迷宫路径探索成功！5、实验过程中出现的问题及解决方法1）程序运行时就遇到了问题，程序没有错误但是无法运行，也不知哪里出了错误，最后只好重新运行VC程序；2）在输出路径时显示的数字化方向和方向不一致，通过实践调试将方向设置为1 J; 3f;2宀；4J后显示正确。6、实验体会通过这次课程设计使我能够熟悉链栈的基本操作和应用，利用链表和栈解决简单的实际应用问题。锻炼了我解决问题的能力，充分体会到算法的时间复杂度和空间复杂度的特性。这次实验使我知道先设计大致的程序模块在进行详细的程序设计使一种很好的程序设计 习惯，对我们更

15、加全面详尽的了解实现程序的功能用重要的作用。7.附录：程序代码如下：#include<iostream>/标注命名空间#include<fstream>/ 文件流using namespace std;/ struct DataType /名称空间标识符 std定义描述迷宫中当前位置的结构类型public:int x;/x代表当前位置的行坐标int y;/y代表当前位置的列坐标int pre;/0:无效,1: J ,2: t ,3: f ,4: J;struct Move int x;int y;链表结点struct LinkNode /DataType data;Li

16、nkNode *next; ;struct Stack / private:定义栈LinkNode *top;/指向第一个结点的栈顶指针public:Stack(); /构造函数，置空栈Stack(); /析构函数void Push(DataType data); DataType Pop(); DataType GetPop(); void Clear(); bool IsEmpty();Stack:Stack()top=NULL;Stack:Stack() 执行析构函数 /* LinkNode *p=top; while(top!=NULL) p=top; top=top->next

17、;/把元素 data 压入栈中使栈顶元素出栈取出栈顶元素把栈清空判断栈是否为空，如果为空则返回1，否则返回 0/构造函数，置空栈析构函数与构造函数相反，当对象脱离其作用域时, 系统自动/ delete p;*/void Stack:Push(DataType e) / LinkNode *TempNode; TempNode=new LinkNode;TempNode->data=e;TempNode->next=top; top=TempNode;DataType Stack:Pop() /DataType Temp;LinkNode *TempNode;TempNode=top

18、; top=top->next;Temp=TempNode->data; delete TempNode;return Temp;DataType Stack:GetPop() / return top->data;void Stack:Clear() /把元素 x 压入栈中使栈顶元素出栈取出栈顶元素把栈清空top=NULL;判断栈是否为空，如果为空则返回 1，否则返回 0bool Stack:IsEmpty() /if(top=NULL) return true;else return false;定义当前位置移动的 4 个方向int move42=0,1,1,0,0,-1

19、,-1,0; / bool Mazepath(int *maze,int m,int n);II寻找迷宫maze中从(0, 0)到(m,n)的路径II 到则返回 true, 否则返回 void PrintPath(Stack p); II void Restore(int *maze,int m,int n); int* GetMaze(int &m,int &n); IIIIfalseII输出迷宫的路径恢复迷宫获取迷宫返回存取迷宫的二维指针int main()int m=0,n=0;int *maze; maze=GetMaze(m,n); IIIIIIif(Mazepath

20、(maze,m,n) II定义迷宫的长和宽 定义二维指针存取迷宫 调用 GetMaze(int &m,int &n) 函数，得到迷宫 调用 Mazepath(int *maze,int m,int n)函数获取路径cout<<" 迷宫路径探索成功 !n"else cout<<" 路径不存在 !n"return 0;返回存取迷宫的二维指针定义二维指针存取迷宫int* GetMaze(int &m,int &n)IIint *maze;IIint i=0,j=0;cout<<" 请

21、输入迷宫的长和宽int a,b;cin>>a>>b;II输入迷宫的长和宽cout<<" 请输入迷宫内容 :n"m=a;n=b; IIm,n分别代表迷宫的行数和列数maze=new int *m+2; II 申请长度等于行数加 2的二级指针 for(i=0;i<m+2;i+) II 申请每个二维指针的空间mazei=new intn+2;for(i=1;i<=m;i+) II输入迷宫的内容， 0代表可通， 1代表不通for(j=1;j<=n;j+) cin>>mazeij;cout<<"

22、是否保存新迷宫？ n"II 保存新迷宫char choose;cin>>choose;if(choose='Y'|choose='y')char ch;ofstream fop("Newtest.txt"); / / 以二进制方式打开 hfmTree.dat 文件， 并当重 新运行时覆盖原文件for(i=1;i<=m;i+)for(j=1;j<=n;j+)ch='0'+mazeij;fop<<ch;fop<<endl;flush(cout);/ 将缓冲区的内容马上送进

23、cout| 把输出缓冲区刷新fop.close();/ 关闭文件/ 给迷宫的四周加一堵墙，即把迷宫四周定义为 1for(i=0;i<m+2;i+)mazei0=mazein+1=1;for(i=0;i<n+2;i+)maze0i=mazem+1i=1;返回存贮迷宫的二维指针mazereturn maze; /;bool Mazepath(int *maze,int m,int n)/寻找迷宫maze中从（0, 0）到（m,n）的路径/到则返回 true, 否则返回 falseStack q,p; /定义栈 p、q, 分别存探索迷宫的过程和存储路径DataType Temp1,Tem

24、p2; int x,y,loop;Temp1.x=1;Temp1.y=1; q.Push(Temp1); / p.Push(Temp1); maze11=-1;/while(!q.IsEmpty() / Temp2=q.GetPop(); /将入口位置入栈 标志入口位置已到达过栈 q 非空，则反复探索获取栈顶元素if(!(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) p.Push(Temp2);/ 如果成功入栈，则把上一个探索的位置存入栈 p for(loop=0;loop<4;loop+) /探索当前位置的

25、4 个相邻位置把最后一个位置入栈输出路径恢复路径表示成功找到路径x=Temp2.x+moveloop0; / y=Temp2.y+moveloop1; / if(mazexy=0) /Temp1.x=x;Temp1.y=y; mazexy=-1; / q.Push(Temp1); / if(x=(m)&&(y=(n) /Temp1.x=m;Temp1.y=n;Temp1.pre=0; p.Push(Temp1); / PrintPath(p); / Restore(maze,m,n); / return 1;/计算出新位置 x 位置值 计算出新位置 y 位置值 判断新位置是否可

26、达标志新位置已到达过新位置入栈成功到达出口if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) / 如果没有成功入栈，则返回到上一个位置p.Pop();q.Pop();return 0;/ 表示查找失败void PrintPath(Stack p)/ 输出路径cout<<" 迷宫的路径为 n"cout<<" 括号内的内容分别表示为 ( 行坐标 , 列坐标 , 数字化方向 , 方向 )n" Stack t; / 定义一个栈，按从入口到出口存取路径 int a,b;/申请空间/取栈 p 的顶点元素顶点元素入栈 t 释放空间栈 p 非空，则反复转移DataType data; LinkNode *temp; temp=new LinkNode; temp->data=p.Pop(); t.Push(temp->data); / delete temp;/while(!p.IsEmpty() /temp=new LinkNode; temp->data=p.Pop()