数据结构课程设计报告迷宫问题.doc

数据结构课程设计报告题 目： 迷宫问题 院 （系）： 信息科学与工程学院 专业班级： 软件工程1103班 学生姓名： 文康 甘路唐 杨文立 学 号： 指导教师： 徐鹏 20 13 年 6 月 8 日至20 13 年 6 月 21 日华中科技大学武昌分校制 数据结构 课程设计任务书一、设计题目迷宫：（程序员：文康，测试员：杨文立，文档员：甘路唐）二、设计主要内容以一个m*n的长方形矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。程序允许玩家手动控制进行游戏，支持再次游戏的功能，如果通过迷宫，询问玩家是否再次挑战游戏，并设有：再次生成一个迷宫，显示路径，返回主菜单界面的选择功能。支持玩家多种选择。在迷宫的主菜单界面，玩家可以选择进行游戏，退出游戏等多项功能。迷宫必须界面清楚，美观。具有友好的用户界面。三、原始资料设计一个m*n的矩阵来表示迷宫，左上角00为起点，右下角m-1n-1为终点；设0为通路，1为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向8个方向行走。程序能自动或者手动生成一个迷宫，判断是否能从起点经过迷宫走到终点。如果能，输出从入口到出口的路径；如果不能，则提示四、要求的设计成果1、课程设计任务书2、程序源代码3、测试文档4、课程设计报告五、进程安排序号课程设计内容学时分配备注1搜集资料、分析与结构化设计2天2各个模块程序设计4天3系统调试与测试2天4答辩及编写课程设计报告2天合计10天六、主要参考资料1何钦铭等编著数据结构课程设计杭州：浙江大学出版社，20072耿国华等编著数据结构用c语言描述北京：高等教育出版社，20113徐健等编著数据结构上机指导与习题解析南京：南京大学出版社，20074陈建新等编著数据结构实验指导与课程设计教程北京：科学出版社，2010 指导教师（签名）：20 年 月 日一、简介1.1问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图a所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图a本次实验要求以一个m*n的长方形矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。程序允许玩家手动控制进行游戏，支持再次游戏的功能，如果通过迷宫，询问玩家是否再次挑战游戏，并设有：再次生成一个迷宫，显示路径，返回主菜单界面的选择功能。支持玩家多种选择。在迷宫的主菜单界面，玩家可以选择进行游戏，退出游戏等多项功能。迷宫必须界面清楚，美观。具有友好的用户界面。1.2设计要求：要求设计程序输出如下：(1) 建立一个大小为mn的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。（3）用一种标志（如数字8）在迷宫中标出该条通路；（4）在屏幕上输出迷宫和通路；（5）上述功能可用菜单选择。二、算法说明2.1 问题分析：2.1.1迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。2.1.2迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组mazem+2n+2,然后用它的前m行n列来存放元素，即可得到一个mn的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。(注：其中m，n分别表示迷宫最大行、列数，本程序m、n的缺省值为39、39，当然，用户也可根据需要，调整其大小。)2.1.3迷宫路径的搜索首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍， 就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。以矩阵【 0 0 1 0 1 ，1 0 0 1 0，1 0 0 0 1，0 0 1 0 0】为例，来示范一下。首先，将位置(0,0)(序号0)放入队列中，其前节点为空，从它开始搜索，其标记变为2，由于其只有一个非障碍位置，所以接下来移动到(0,1)(序号1)，其前节点序号为0，标记变为2，然后从(0,1)移动到(1,1)(序号2)，放入队列中，其前节点序号为1，(1,1)存在(1，2)(序号3)、(2，1)(序号4)两个可移动位置，其前节点序号均为2.对于每一个非障碍位置，它的相邻非障碍节点均入队列，且它们的前节点序号均为该位置的序号，所以如果存在路径，则从出口处节点的位置，逆序就可以找到其从出口到入口的通路。如下表所示： 0 1 2 3 4 5 6 7 8 9 10(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)(3,4)-10122345679由此可以看出，得到最短路径：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 搜索算法流程图如下所示： 2.2 概要设计2.2.1主要模块构建一个二维数组mazem+2n+2用于存储迷宫矩阵自动或手动生成迷宫，即为二维数组mazem+2n+2赋值构建一个队列用于存储迷宫路径建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况实现搜索算法屏幕上显示操作菜单 2.2.2设定栈的抽象数据类型定义基本操作：int initstack(sqstack &s)操作结果：构造一个空栈s；int stackempty(sqstack s)初始条件：栈s已存在。操作结果：若栈为空则返回true，否则返回false；gettop（s，&e）初始条件：栈s已经存在；操作结果：若栈不为空，则以e返回栈顶元素。int push(sqstack &s,selemtype e)初始条件：栈已经存在。操作结果：在栈的顶部插入新的栈顶元素；int pop(sqstack &s,selemtype &e)初始条件：栈已经存在；操作结果：删除栈顶元素，并以e返回其值。2.2.3 设定迷宫的抽象数据类型基本操作：void creatmaze(int r,int l)初始条件：mazetype maze已经存在，其中从第一行到最后一行，每一行的第一个元素和最后一个元素都为*，从第一列的到最后一列，每一列的第一个和最后一个元素的值为*；操作结果：构成迷宫的int型数组，以#表示障碍，_表示通路。 mazepath(posit start,posit end)初始条件：迷宫已经初始化；操作结果：若迷宫中存在一条通路，则在程序运行过程中走过的路径赋值为1；并在入口处赋值为-1。若迷宫中不存在通路则打印 no path。print()初始条件：迷宫存在通路；操作结果；以数字数组的形式输出迷宫。 footprint(posit a)操作结果：使迷宫的m的a点的值变为足迹。 nextpos(posit c,int di)操作结果：调整迷宫行进的方向，寻找出路。2.2.4.程序核心模块1）主程序模块int main()postype start,end;int r,l;coutrl;creatmaze(r,l);coutstart.rowstart.line;coutend.rowend.line;coutendl;if(mazepath(start,end)cout迷宫的通路：endl（其中*表示外墙，#表示迷宫内障碍物,.为通路）endlendl;printmaze(r,l);else cout迷宫没有通路！endl;free(s.base);return 0;2）栈模块3）迷宫模块各模块的调用关系如下：4）求解迷宫的通路的伪码算法：设定当前位置的处值为入口位置；do若当前的位置可通。则将当前的位置插入栈顶；若该位置为出口位置，则结束；否则切换当前位置的东邻的为新的当前位置；否则若栈不为空且栈的顶位置尚有其他的方向没有被探索，则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；若栈不空但栈顶的四周均不可通过，则删去栈顶位置；若栈不为空，则重新测试新的栈顶位置；只至找到一个可通过的块至栈空；1. 坐标的位置的类型typedef structint line;int row;postype;2 .迷宫类型void creatmaze(int r,int l)/定义迷宫的墙为*，通路为_，障碍为#int i,j;for(i=0;ir;i+)mazei0=*;/左面墙mazeil-1=*;/右面墙for(j=1;jl-1;j+)maze0j=*;/上面墙mazer-1j=*;/下面墙for(i=1;ir-1;i+)for(j=1;jl-1;j+)mazeij=_;coutnum;cout请依次输入障碍物的坐标：endl;int x,y;for(i=1;ixy;mazexy=#;coutendl创建的迷宫的如下：endlendl;printmaze(r,l);coutendl;3 .栈类型typedef structint ord; /通道块在路径上的序号postype seat; /通道块在迷宫中的坐标位置int di; /从此通道块走向下一通道块的方向 东1；南2；西3；北4selemtype;4.迷宫的路径的算法int mazepath(postype start,postype end)initstack(s);curpos=start;/ 设定当前位置为入口位置curstep=1;/第一步doif(pass(curpos)/当前位置可以通过（未曾走过）footprint(curpos);/留下足迹e.ord=curstep;e.seat=curpos;e.di=1;push(s,e);/加入路径if(curpos.row=end.row&curpos.line=end.line)/到达终点return true;curpos=nextpos(curpos,1);/下一位置是当前位置的东邻curstep+;/探索下一步/ifelse/当前位置不能通过if(!stackempty(s)pop(s,e);while(e.di=4&!stackempty(s)markprint(e.seat);/留下不能通过的标志pop(s,e);/退回一步/curstep-;/whileif(e.dilast每一个点是否遍历完 即：pointcount=0？在可以遍历的方向中随机选择一个方向遍历并且把选择的元素标志为flag同时把x，y的坐标更新到和当前点的坐标，说明当前点不可再一次遍历了pointcount-1说明有一个点已经遍历过了，再把tail赋值为p1的地址屏幕输出迷宫结 束五、任务分配l 程序员：文康。主要任务：负责算法设计，编写源代码。l 测试员：杨文立。主要任务：负责设计测试用程序，并对实验结果进行整理分析，最后完成实验报告的第三、四部分，即测试结果与分析探讨部分。l 文档员：甘路唐。主要任务：负责撰写实验报告的第一、二部分内容，即实验内容简介与算法描述。同时完成整个文档的整合，是整篇报告排版、文字风格统一。六、总结在一个系统开发的过程中编码不是重要的，重要的是分析系统、建立起系统模型。在分析一个系统前，分析人员必须要对将要开发的系统所涉及到的各方面知识有一个认识，然后将系统的模型建立起来。而且一个成功的软件要符合用户的需要，要以用户为中心，开发出用户想要的软件，而不能自以为是、想当然的做。在程序编写中，我认识到软件要有简便的界面，良好的程序风格。拥有这些条件，程序的可读性才会好，开发的复杂度才能大大减少，修改代码时更加容易下手。我认为，所谓友好的界面，就是用户需要的界面，力求简便全面。所以设计一个界面时，开发人员必须要了解用户的想法，从用户的角度去设计，当然，开发不能全听用户的意见，在详细分析了系统后，开发人员可以向用户提出一些修改的意见，在双方多次交流后定出程序所需的功能，以决定界面的实现。在编码中，良好的编程风格与习惯是提高工作效率的一个重要方面，而且良好的编程风格与习惯也是使软件便于维护的基础。那如何是良好的编程风格与习惯呢？我认为主要是程序的模块化、必要的注释。所谓模块化就是使程序的功能实现分成多个单独的功能模块，而不能在一大段代码中实现多个功能，如果这样做，别的人是非常难读懂你的程序。必要的注释，显而易见是要在程序的编写中加入对程序的说明，原因就是为了别人能读懂你的程序，过一段时间后你自己还能读懂自己的程序。最后说明下这次课程设计给我感受最深的有三点：1进行管理系统开发这样的工作，要有恒心，要能静下新来做，而不能浮躁。2要善于同别人交流与合作，善于获取各种有用的资源。3要真真实实的多查资料，多问，多看。参考文献1何钦铭等编著数据结构课程设计杭州：浙江大学出版社，20072耿国华等编著数据结构用c语言描述北京：高等教育出版社，20113徐健等编著数据结构上机指导与习题解析南京：南京大学出版社，20074陈建新等编著数据结构实验指导与课程设计教程北京：科学出版社，2010附录：源代码/迷宫游戏程序主文件migong.cpp#include #include #include migong.h#include gamestart.h#include resource.hint x_row=0;/迷宫的起始点位置的x坐标int y_col=0;/迷宫的起始点位置的y坐标int left=0;/初始化向左的方向标志位leftint right=0;/初始化向右的方向标志位rightint up=0;/初始化向上的方向标志位upint down=0;/初始化向下的方向标志位downint current_row;int current_col; /玩家的初始位置在迷宫数组中的行列数int player_x =210; /玩家的初始位置x坐标int player_y =160; /玩家的初始位置y坐标int pointcount; /迷宫总点数int mazemaprowcol;/定义迷宫地图数组extern vector pvec; /声明路径点容器/using std:vector;/point pt=0,0; /定义鼠标触点位置/const int keysize_width=100;/const int keysize_height=50;const int key1_x=325;/(gameengine:getgameengine()-getwidth()-keysize_width)/2;const int key1_y=195;/(gameengine:getgameengine()-getheight()-keysize_height)/2;/const rect rt1=200+10*row+10-90,100,200+10*row+10-90+100,150;/const rect rt2=200,100,300,150;/const rect rt3=key1_x,key1_y,key1_x+100,key1_y+50;/rect rt4=250,400,250,450;/rect rt5=250,550,350,600; bool move =false; /判断是否有位置移动 bool delay=false; /判断启动显示延时与否 int start_select = main_menu;/初始化界面为进入主菜单 int select_button; /判断玩家鼠标选中哪个键/游戏初始化 bool gameinitialize(hinstance hinstance)/* 构造游戏引擎实例句柄，并初始化引擎参数 */创建引擎g_pge=new gameengine(hinstance,text(g_strtitle),text(g_strtitle),0,0,false,32,800,600);if(g_pge=null) return false;/初始化引擎参数g_pge-setframedelay(15) ;/设置游戏帧延时为15毫秒g_pge-setpause(false);/设置暂停状态为falseif(!g_pge-creategamewindow()/创建游戏窗口messagebox(null,修改显示模式失败!rn程序退出!,错误,mb_ok| mb_iconerror);return false;/退出程序return true;/游戏逻辑void gameaction(hwnd hwnd)long ntick=timegettime();/获取当前时间g_nfrequency=1000/(ntick-g_lpretime);/计算游戏频率g_lpretime=ntick;/记录当前时间 if(delay=true) /延时函数if(start_select=game_migong & select_button=show_path)/如果是在迷宫界面delay=true当且仅当点击show_path时if(timegettime() - g_timedelaystart5000)/启动显示延时1秒delay=false; /关闭延时if (start_select=main_menu)/如果是在主菜单界面if(timegettime() - g_timedelaystart500) /在主菜单界面延时设为500保证视觉效果 /select_button=non_key; delay=false; /显示延时可以参考这个函数 if(current_row=row-1 & current_col=col-1)if(messagebox(g_pge-getwindow(),高手果然不同凡响 你赢了rn要继续游戏吗？,你赢了,mb_yesno|mb_defbutton2|mb_iconasterisk)=idyes) gamestart(hwnd); /重新开始 elsedestroywindow(hwnd);/退出程序 invalidaterect(hwnd,null,false);/强制刷新窗口 updatewindow(hwnd); void gamepaint(hdc hdc) hdc dc=createcompatibledc(hdc); /创建兼容的设备环境setbkmode(hdc,transparent); /设置背景模式为透明settextcolor(hdc,rgb(128,0,128); /设置文字颜色为紫色 hbitmap hjiantou=(hbitmap)loadimage(null,resourcejiantou.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hstart_key=(hbitmap)loadimage(null,resourcestart_key.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hquit_key=(hbitmap)loadimage(null,resourcequit_key.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hshow_next=(hbitmap)loadimage(null,resourceshow_next.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hshow_path=(hbitmap)loadimage(null,resourceshow_path.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hreturn_to_menu=(hbitmap)loadimage(null,resourcereturn_to_menu.bmp,image_bitmap,0,0,lr_loadfromfile);hbitmap hmigong_bg=(hbitmap)loadimage(null,resourcemigong_bg.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hmenu_bg=(hbitmap)loadimage(null,resourcemenu_bg.bmp,image_bitmap,0,0,lr_loadfromfile); hbitmap hplayer=(hbitmap)loadimage(null,resourceplayer.bmp,image_bitmap,0,0,lr_loadfromfile) hbitmap hwall=(hbitmap)loadimage(null,resourcewall.bmp,image_bitmap,0,0,lr_loadfromfile); /载入位图 if(start_select = main_menu) selectobject(dc,hmenu_bg); bitblt(hdc,0,0,800,600,dc,0,0,srccopy); /绘制主菜单背景 if(select_button != start_key) selectobject(dc,hstart_key); bitblt(hdc,key1_x,key1_y,150,35,dc,0,0,srccopy); /绘制开始游戏按钮 if(select_button != start_key2) selectobject(dc,hstart_key); bitblt(hdc,key1_x,key1_y+60,150,35,dc,0,0,srccopy); /绘制开始游戏按钮 selectobject(dc,hstart_key); /bitblt(hdc,key1_x,key1_y+60,150,35,dc,0,0,srccopy); /绘制第二个按钮bitblt(hdc,key1_x,key1_y+230,150,35,dc,0,0,srccopy); /绘制第三个按钮 if(select_button != quit_key) selectobject(dc,hquit_key);bitblt(hdc,key1_x,key1_y+300,150,35,dc,0,0,srccopy); /绘制退出游戏按钮 deleteobject(selectobject(dc,hquit_key); deleteobject(hmenu_bg); deleteobject(hstart_key); deleteobject(hquit_key); h if(pointcount = 0)if(start_select = game_migong | start_select=game_migong2) /如果每一个遍历点都遍历到了就打印地图，生成得迷宫是没有边界 /或是迷宫2八方向游戏中随机生成 selectobject(dc,hmigong_bg); /将背景位图选入设备环境bitblt(hdc,0,0,800,600,dc,0,0,srccopy); /绘制背景selectobject(dc,hshow_next); /将show_next位图选入设备环境 bitblt(hdc,600,150,125,50,dc,0,0,srccopy); /绘制这个太难？按钮selectobject(dc,hshow_path); /将show_path位图选入设备环境bitblt(hdc,600,320,125,50,dc,0,0,srccopy); /绘制show path按钮selectobject(dc,hreturn_to_menu); /将return_to_menu位图选入设备环境bitblt(hdc,600,490,125,50,dc,0,0,srccopy); /绘制返回主菜单按钮 selectobject(dc,hwall); /将墙位图选入设备环境 for(int i=0;icol+2;+i)bitblt(hdc,200+10*i,150,10,10,dc,0,0,srccopy); /绘制迷宫最上面的的围墙 for(int j=0;jgetstarttime(); /计算游戏运行时间 int nbits=getdevicecaps(hdc,bitspixel); /获取屏幕颜色位数 int nscreenwidth=getsystemmetrics(sm_cxscreen); /获取屏幕像素宽度 int nscreenheight=getsystemmetrics(sm_cyscreen); /获取屏幕像素高度 /格式化字符串，将结果存入str sprintf(str,游戏运行时间：%d s 帧频：%d 显示模式：%d bit,%d*%d,ngametime/1000, g_nfrequency, nbits,nscreenwidth,nscreenheight); textout(hdc,10,10,str,strlen(str); /输出字符串 selectobject(dc,hwall); /将墙位图选入设备环境for(int r=0;rrow;+r)if(r=0) /入口不能输出围墙 char in5;sprintf(in,入); textout( hdc,185,145,in,strlen(in) ); /显示入口 else bitblt(hdc,200,160+10*r,10,10,dc,0,0,srccopy); /绘制迷宫最左面的的围墙for(int c=0;ccol;+c) if(mazemaprc!=flag) /如果迷宫数组的元素是墙的话就绘制墙bitblt(hdc,210+10*r,160+10*c,10,10,dc,0,0,srccopy);if(r=row-1)/显示出口 char out5; sprintf(out,出); textout( hdc,200+10*row+20,150+10*r+15,out,strlen(out) );else bitblt(hdc,200+10*row+10,160+10*r,10,10,dc,0,0,srccopy); /绘制迷宫最右面的的围墙 if(delay=true)/如果检测到延时被启动if(start_select=game_migong & select_button=show_path)/判断是在哪里启动延时char cheshi50; settextcolor(hdc,rgb(255,255,0);/设置字体颜色为黄色logfont lf=0;/创建默认逻辑字体lf.lfheight=40;/设置字体高度lf.lfwidth =20;/设置字体宽度lf.lfweight=800;/设置字体粗细lf.lfcharset=default_charset;/设置字符集strcpy(lf.lffacename,华文行楷);/设置字体hfont hfont=createfontindirect(&lf);/创建字体hfont hfontold=(hfont)selectobject(hdc,hfont);/选用字体sprintf(cheshi,仙人指路:); textout(hdc,100,100,cheshi,strlen(cheshi);/用完就删的好习惯selectobject(hdc,hfontold);/替换字体deleteobject(hfont);/删除字体 / for(int i=0;itop;+i)/unsigned int sizehpen hpen; /定义画笔 hpen=createpen (ps_solid,2.5,rgb(0,0,0);/创建画笔selectobject(hdc,hpen);/将刚创建的画笔选入设备环境point temp_pt=row,col;for(unsigned int ix =0;ix!=pvec.size()-1;+ix) /将路径点容器中的点连成线 if(pvecix.x !=row | pvecix.y != col )movetoex(hdc,200+10*pvecix.x+5,150+10*pvecix.y+5,null);lineto(hdc,200+10*pvecix+1.x+5,150+10*pvecix+1.y+5); /简单的划线setpixel(hdc,200+10*pvecix.x+5,150+10*pvecix.y+5,rgb(192,14,235);/改变每个路径像素点颜色(可有可无)/if(select_button!=show_path) deleteobject(selectobject(hdc,getstockobject(black_pen);/通过把备用的黑色画笔选入设备环境来得到需要被删除的画笔的句柄 /然后删除之 /按下效果处理:if(start_select= main_menu & select_button= start_key)/在主菜单界面且鼠标选择按钮为开始迷宫游戏 hbitmap hstart_key2=(hbitmap)loadimage(null,resourcestart_key2.bmp,image_bitmap,0,0,lr_loadfromfile); selectobject(dc,hstart_key2); bitbl