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

1、长 春 大 学课 程 设 计 任 务 书题目名称 走迷宫游戏 院 （系） 计算机科学技术学院 课程名称 数据结构课程设计 班 级 网络10406 学生姓名 指导教师 起止日期 2012.7.162012.7.20 课程设计任务书技术参数）及要求题目名称（包括主要题目名称：走迷宫游戏设计目的1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。设计

2、要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细

3、设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。5.程序调试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。7.编写课程设计说明书，封面和说明书纸到教务处网站下载，装订格式如

4、下：一、封面；二、目录；三、说明书正文，主要内容包括：1设计题目；2设计目的；3算法思想分析；4算法描述与实现；5结论设计内容及工作量【问题描述】以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】1首先用二维数组存储迷宫数据，迷宫数据由用户输入。2一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。3可以用多

5、种方法实现，但至少用两种方法，用三种以上可加分。【实现提示】1计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。2有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就

6、会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。主要参考资料数据结构程序设计题典李春葆等编 清华大学出版社数据结构(C语言版) 黄国瑜 叶乃菁编 清华大学出版社数据结构课程设计苏仕华 等编 机械工业出版社进 度 计 划 表阶段日期计划完成工作量指导教师检查意见备注7.16分析题目，查阅资料；7.177.18算法设计，编码，调试；7.19编码、调试运行；撰写设计说明书；7.20答辩设计总结：考核成绩及评语 指导教师签字 年 月 日教研室意见教研室主任签字 年 月 日长 春 大 学课 程 设 计 说 明 书题目名称 走迷

7、宫游戏 院（系）计算机科学技术学院 专业（班级） 网络10406 学生姓名 指导教师 起止日期2012.7.20 目录一、设计题目2二、设计目的2三、算法思想析3 1、类的分析与计3 2、程序设计流图3四、算法描述与现 51、概要计52、调试析53、测试果7五、总结与会10六、程序码11七、参考献16一、设计题目1、题目：走迷宫游戏2、问题描述以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。3、基本要求（1）、首先用二维数组存储迷宫数据，迷宫数据由用户输入。（2）、一个以链表作存储结构的

8、栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。（3）、可以用多种方法实现，但至少用两种方法，用三种以上可加分。二、设计目的1、需求分析与设计要求随着社会经济和人们物质生活的不断提高，人们对精神生活的需求也越来越高，在现今社会里，人们对诸如智商、情商等的重视无疑反映了对精神生活的态度。当然具体到我们每个人来说，想必大多数人小时候都曾玩过魔方、迷宫吧。作为这种智力游戏，人们是百玩不厌的。正是鉴于这种需求，本设计应用计算机语言及其算法，将人的意志

9、赋予机器实现，使人们不必再陷于枯燥的重复劳动，从而将更多的精力投入到对未知领域的探索上。这次课程设计要求我们在了解并掌握数据结构与算法的设计方法的基础上，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。同时要求在提高综合运用所学的理论知识和方法独立分析和解决问题的能力的同时，训练用系统的观点和软件开发一般规范进行软件开发的方法，培养一个软件工作者所应具备的科学的工作方法和作风。三、算法思想分析1、类的分析与设计由于计算机解谜宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个

10、方向再继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。首先，迷宫图用方块表示，每个方块或为通道，或为墙。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移

11、开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北

12、）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径”上最后一个通道块。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。2、程序设计流程图（1）程序主要项目主函数数据存储栈的初始化及入栈出栈函数走过通道留下的痕迹探索从出口到入口的路径切换当前探索位置输出迷宫信息（2）程序运行主流程开始建立迷宫并确定当前位置当前位置是否可通NY朝默认方向继续探索换下一个方向探索结束 四、算法描述与实现1、概要设计以二维数组mazemapMN表示迷宫，数组中0表示通路，1表示障碍，3表示求解之后的迷宫路径。M为迷宫的宽，N为迷宫的长。 程序设置一个

13、演示迷宫，另外可由用户自己输入迷宫数据建立迷宫。用户根据提示输入迷宫的长和宽，入口和出口，以及迷宫每一行的数据，同样用1表示障碍，0表示通路，迷宫周边用1表示。以图形显示出迷宫，用“墙”表示障碍，“口”表示路径。若存在路径，则显示出路径，否则提示没有路径。2、调试分析（1）设定栈的抽象数据类型定义ADT Stack 数据对象：D=ai|ai属于ElemSet,i=1,2,3,4,n,n>=0 数据关系：R1=<ai-1,ai>|ai-1,ai属于D,i=1,2,3.n基本操作： InitStack(&s) 操作结果：构造一个空栈s DestroyStack(&

14、s) 初始条件：栈s已存在 操作结果：张s被撤销ClearStack(&s) 初始条件：栈s已存在 操作结果：将s清为空栈StackEmpty(s) 初始条件：栈s已存在 操作结果：若s为空栈，则返回true，否则返回falseGetTop(s,&e) 初始条件：栈s存在且非空 操作结果：用e返回s的栈顶元素Push(&s,e) 初始条件：栈s已存在 操作结果：插入s的栈顶元素为ePop(&s,&e) 初始条件：栈s存在且非空 操作结果：删除s的栈顶元素，并用e返回值ADT Stack（2）设定迷宫的数据类型ADT maze数据对象：D=aij|aij属

15、于“墙”，“口”，“ ”，i<m,j<n,m,n<100数据关系：R=ROW，COLROW=<ai-1 j,aij>|ai-1 j,aij属于D COL=<aij,ai j-1>|ai-1 j,aij属于D基本操作：Initmaze(&maze,row,col) 初始条件：二维数组mazerowcol已存在。 基本操作：用1表示障碍，0表示通路，由用户输入。 Mazepath(&maze,start,end) 初始条件：迷宫maze以被赋值。 操作结果：找出一条迷宫路径。若没有路径，则提示没有。Printmaze(maze)初始条件：迷

16、宫maze已存在 操作结果：以字符形式显示出迷宫ADT maze（3）程序三个模块设计 主程序模块 void main() 初始化； Dowhile(命令!=退出)栈模块-实现栈的抽象数据类型迷宫模块-实现迷宫的抽象数据类型各模块的调用关系如下： 主程序模块à迷宫模块à栈模块球迷宫一条从入口到出口的路径算法可描述如下：do若当前位置可通，则将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻块为当前位置； 否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转到栈顶位置的下一相邻块 若栈不空但栈顶位置的四周均不通 则删除

17、栈顶位置；若栈不空，则重新测试新的栈顶位置，知道找到下一个可通的相邻块或出栈至栈空；while(栈不空)；迷宫建立模块：此模块的调试主要在于能否成功将迷宫用二维数组矩阵储存，能否成功调用File_Save(int maze50,int x,int y)函数，保存文件文件的调取模块：此模块的调试主要在于对文件打开不成功时的应对。3、测试结果（1）进入程序后显示主页面图1主页面（2）按任意键继续下一步图2 迷宫路径（3）按任意键后自己构建迷宫图3构建迷宫例：迷宫过后，会提示用户输入迷宫。选测试迷宫数据如下Maze66= 1，1，1，1，1，1， 1，0，1，0，0，1， 1，0，1，0，1，1，

18、1，0，0，0，1，1， 1，0，1，0，0，1， 1，1，1，1，1，1；迷宫入口坐标(1,1)，出口(1,4)，如图所示图4构建迷宫（4）按回车键可得到自己构建的迷宫地图，如图所示图5迷宫地图（5）按Q键即退出程序图6退出程序五、总结和体会通过迷宫求解的编程练习思考数据结构的使用，比如对栈、指针、链表等的深入了解，让我们感受到了数据结构及其算法的重要。此外还熟悉了各种函数的应用。通过编程我知道了想要写出好的程序，需要有扎实的基础，这样才会遇到一些基本算法时做的游刃有余。在编程时，我们要有丰富的想象力，不拘泥于固定的思维方式，试试别人从没想过的方法。丰富的想象力是建立在丰富的知识的基础上，所

19、以我们要通过多个途径来帮助自己建立较丰富的知识结构。在编程时，遇到了很多的困难，需要我们多与别人交流。在编程时我们也看到了有良好的编程风格是十分重要的，至少在时间效率上就体现了这一点。六、程序源码#include<iostream>#include<windows.h>#include<conio.h>#define MAXSIZE 100using namespace std;int signMAXSIZEMAXSIZE;/标记矩阵，当相应块走过后，值变为1typedef structint x;int y;PosType;typedef structin

20、t ord; PosType seat;int di;SElemType;typedef structint m;int n;int mapMAXSIZEMAXSIZE;MazeType;class Stackpublic:SElemType dataMAXSIZE;int top;Stack(void)top=-1;void push(SElemType e)top+;datatop.ord=e.ord;datatop.di=e.di;datatop.seat=e.seat;void pop(SElemType &e)e.di=datatop.di;e.ord=datatop.ord

21、;e.seat=datatop.seat;top-;int empty()if(top=-1)return 1;elsereturn 0;void FootPrint(PosType ps)signps.xps.y=1;int Pass(MazeType mazemap,PosType ps)if(mazemap.mapps.xps.y=0&&signps.xps.y=0)return 1;else return 0;PosType NextPos(PosType ps,int di)PosType temp;switch(di)case 1:temp.x=ps.x+1;tem

22、p.y=ps.y;break;case 2:temp.x=ps.x;temp.y=ps.y-1;break;case 3:temp.x=ps.x-1;temp.y=ps.y;break;case 4:temp.x=ps.x;temp.y=ps.y+1;break;return temp;int MazePath(MazeType &mazemap,PosType start,PosType end)Stack st;SElemType e;PosType curpos=start;int curstep=1;for(int i=0;i<mazemap.m;i+)for(int j

23、=0;j<mazemap.n;j+)signij=0;doif(Pass(mazemap,curpos)FootPrint(curpos);e.ord=curstep;e.seat=curpos;e.di=1;st.push(e);if(curpos.x=end.x&&curpos.y=end.y)for(int i=0;i<=st.top;i+)mazemap.mapst.datai.seat.xst.datai.seat.y=3;/cout<<"("<<st.datai.seat.x<<",&qu

24、ot;<<st.datai.seat.y<<")"<<"t"return 1;curpos=NextPos(curpos,1);curstep+;elseif(!st.empty()st.pop(e);while(e.di=4&&!st.empty()FootPrint(e.seat);st.pop(e);if(e.di<4)e.di+;st.push(e);/cout<<"("<<(e.seat).x<<","<&

25、lt;(e.seat).y<<")"<<endl;curpos=NextPos(e.seat,e.di);while(!st.empty();return 0;void printmaze(MazeType mazemap,PosType start,PosType end)for(int i=0;i<mazemap.m;i+)cout<<"tt"for(int j=0;j<mazemap.n;j+)if(1=mazemap.mapij)cout<<"墙"else if(i=

26、start.x&&j=start.y)cout<<"口"else if(i=end.x&&j=end.y)cout<<"口"else if(3=mazemap.mapij)cout<<"口"else cout<<" "cout<<endl;void usermaze()MazeType usermap;PosType m_start,m_end;cout<<"输入迷宫宽度:"<<e

27、ndl;cin>>usermap.n;cout<<"输入迷宫高度:"<<endl;cin>>usermap.m;for(int i=0;i<usermap.m;i+)cout<<"输入第"<<i+1<<"行迷宫图"<<endl;for(int j=0;j<usermap.n;j+)cin>>usermap.mapij;cout<<"输入迷宫入口横坐标:"<<endl;cin

28、>>m_start.x;cout<<"输入迷宫入口纵坐标:"<<endl;cin>>m_start.y;cout<<"输入迷宫出口横坐标:"<<endl;cin>>m_end.x;cout<<"输入迷宫出口纵坐标:"<<endl;cin>>m_end.y;cout<<"下面是您输入的迷宫地图:"<<endl<<endl;printmaze(usermap,m_s

29、tart,m_end);if(MazePath(usermap,m_start,m_end)cout<<"按任意键显示路径··· ···"<<endl;getch();printmaze(usermap,m_start,m_end);cout<<endl<<endl;cout<<"tt"<<"迷宫路径如上"<<endl<<endl;elsecout<<"没有路

30、径!"<<endl;void demomaze()MazeType mazemap;PosType start,end;start.x=1,start.y=1;end.x=8,end.y=8;mazemap.m=10,mazemap.n=10;for(int i=0;i<10;i+)for(int j=0;j<10;j+)mazemap.mapij=1;mazemap.map11=mazemap.map12=mazemap.map14=mazemap.map15=mazemap.map16=mazemap.map18=0;mazemap.map21=mazem

31、ap.map22=mazemap.map24=mazemap.map25=mazemap.map26=mazemap.map28=0;mazemap.map31=mazemap.map32=mazemap.map33=mazemap.map34=mazemap.map37=mazemap.map38=0;mazemap.map41=mazemap.map45=mazemap.map46=mazemap.map47=mazemap.map58=0;mazemap.map51=mazemap.map52=mazemap.map53=mazemap.map55=mazemap.map56=mazem

32、ap.map57=mazemap.map58=0;mazemap.map61=mazemap.map63=mazemap.map64=mazemap.map65=mazemap.map67=mazemap.map68=0;mazemap.map71=mazemap.map75=mazemap.map78=0;mazemap.map82=mazemap.map83=mazemap.map84=mazemap.map85=mazemap.map86=mazemap.map87=mazemap.map88=0;/*1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,*/printmaze(mazemap,start,en