数据结构课程设计---迷宫.doc

数据结构课程设计论文题目： 迷宫 学院： 信息工程学院 专业： 信息管理与信息系统 班级： 信息管理与信息系统本（1）班 姓名： * 学号： 指导教师： 设计时间： 课程设计任务书一、设计任务随机生成一个迷宫图，从迷宫中找寻出路，将迷宫的左上角作入口，右下角作出口，寻找从入口点到出口点的一条通路，并将通路信息显示出来。 二、 设计要求1. 基本要求：（1） 对系统进行功能模块分析、控制模块分析；（2） 系统设计要完成题目所要求的功能；（3） 编程简练、可用，尽可能的使系统的功能更加完善和全面；（4） 说明书、流程图清晰、美观。2. 创新要求 在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。三、 设计期限设计进度及完成情况表日期内容12.12-12.14选取参考书，查阅相关文献资料，完成资料收集和系统分析工作12.15-12.18创建相关数据结构，录入源程序12.19-12.21调试程序，并记录调试中的问题，初步完成课程设计论文12.23上交数据结构课程设计报告，并回答指导老师提出的相关问题前言随着科技的日益发展，在当今知识爆炸的年代，计算机毫无疑问成为了人们日常生活中不可或缺的工具，而在计算机及其应用的各个领域中，都会用到各种各样的数据结构，学会分析研究计算机加工对象的特征，选择合适的数据结构和存储表示，以及编制相应的实现算法，是学习计算机不可或缺的知识技能。数据结构可以说是编程的灵魂，它不是一门语言所以没有关键字。它只是给程序开发人员一个开发思路而已，讲的主要是已经成熟的编程思想和算法，而且几乎适用于所有开发语言。就好像学习英语一样，学习编程语言让你会说英语，记住很多英语单词，熟悉英语的很多语法。而学习数据结构能让你你出很漂亮的英语文章。当然，在数据结构中迷宫是一个非常经典的问题，许多做课程设计的学生都可能选择迷宫这一课题。解决迷宫有很多种方法，在我的设计中我采用的是递归法，本方法在数据结构中运用的还是比较多的，当然还有回溯法运用的也比较普遍。至于其他的方法一般就不常见了，因为在学生熟悉和能够运用的方法中，这两种方法是运用广泛的，在许多高校，老师提倡的和教导的最基本的也是这两种方法。迷宫在数据结构中是比较简单的，容易让学生入门和对计算机产生兴趣，更容易让学生树立起信心。数据结构是一种工具，在日常生活中运用的比较多，学好数据结构可以提高以后再计算机方面编程的能力和实践能力。本论文包括五个章节，包括需求分析、总体设计、详细设计、编码与调试、总结。在整个课程设计的实践中，我们小组成员团结协作，共同交流，一起努力解决遇到的问题，学习到编写和调试代码要细心、耐心，才能最终完成整个课程设计。同时，在实践中，得到了老师许多宝贵意见，其他同学也提出了许多有益的建议，谨此一并致以诚挚的谢意。 由于个人水平有限，论文中有些许不当之处，望老师批评指正。 目录第1章 需求分析41.1性能需求与功能需求41.2课题设计的目的与意义4第2章 总体设计62.1课题设计的总体思路62.2整个程序的流程图72.3 课题设计界面8 第3章 详细设计93.1 main()主函数9 3.2 Init ()初始化函数 9 3.3 MapRand( )迷宫生成函数 9 3.4 PrMap( )迷宫显示函数 9 3.5 FindWay( )系统自动探索10 3.6 PeopleFind( )人工探索10 3.7 Result( )结果处理函数113.8 Close()图形关闭函数11第4章 编码与调试12第5章 总结20附录21参考文献第1章 需求分析1.1性能需求与功能需求 性能需求：随着社会经济和人们物质生活的不断提高，人们对精神生活的需求也越来越高，在现今社会里，人们对诸如智商、情商等的重视无疑反映了对精神生活的态度。当然具体到我们每个人来说，想必大多数人小时候都玩过魔方、迷宫吧。作为这种智力游戏，人们是百玩不厌的。正是鉴于这种需求，本设计运用计算机语言及其算法，将人的意志赋予机器实现，使人们不必在陷于枯燥的重复劳动，从而将更多的精力投入到未知领域的探索上。功能需求：本设计的关键在于将人的思想自动化，有所编软件的自动的搜索可行路径。因此，软件必须拥有自动搜索并记录可行路径的功能，除此之外，软件还应设置人机交互接口，以便能够人为地建立迷宫图；当然对于迷宫问题还有很多需要考虑的地方，比如由用户自己探索可行路径，但由于本设计侧重于迷宫的求解算法设计，并非以游戏的形式为初衷，一定有不全之处，望读者见谅。1.2课题设计的目的与意义一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。而进行课程设计实践操作能够使我们更好地巩固课本知识，对课本知识有更深一步的了解，了解迷宫求解相关方面的知识，能小组合作完成较为简单的程序的设计并独立完成课程设计的论文，通过课程设计，达到增强巩固数据结构知识的目的，使知识更加全面化，系统化。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种看法导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。 数据结构课程设计是学习数据结构课程的一个重要的环节，能巩固和加深课堂教学中所学习到的内容，提高学生学习的实践和实际工作能力，为以后的学习奠定好的基础和学习态度及方法。通过课程设计，使学生加强团队合作的意识，并且能够综合运用课本知识来解决实际问题，加强分析问题、解决问题和动手的能力。第2章 总体设计2.1课题设计的总体思路（1） 程序的设计，首先要考虑迷宫的表示，这是一个二维关系图，典型的存储方式是选择二维数组，数据元素的值只有两种状态，所以取值为0或1，其中0表示通路，1表示墙壁即此路不通，这里将二维数组取名为map，将最外面一圈设为墙壁，作为一个封闭图形，只留下入口点和出口点为通路。（2） 图形的显示就可以根据数组元素的值来确定，如果是人工探索，则根据按键来确定探索物的位置坐标，利用循环语句即可实现；如果是人工探索，则根据按键来确定探索物的位置坐标，利用循环语句即可实现；如果是系统自动检索，并在8个方向检索，则问题相对复杂，采用递归的方法实现。 （3） 迷宫作为线性结构的典型应用，大多数是用递归方法实现，用0代表通路，1代表此路不通。本程序采用了一个美观逼真的迷宫图，而且是随机生成的，迷宫的大小为N*N，N预定义为常数，修改N的数值，可以改变迷宫的大小（只要不超过屏幕显示范围），用白色表示可走的路，蓝色表示此路不可以通过，并画出整个程序的流程图，让整个程序的设计思路一目了然。 （4） 若设定的迷宫存在通路，如果采用的是系统自动探索的运行方式，则会显示出所走过的路径；如果采用的是人工探索方式，没有记录所走过的路径，只显示找的通路信息； （5） 程序执行的命令为：生成迷宫、求解迷宫、输出迷宫的解。 2.2整个程序的流程图 图2-1 整个程序的流程图2.3 课题设计界面 图2-2 人工探索通路图系统运行首先出现提示字符串“please select hand（1）else auto”，询问是选择人工探索还是系统自动探索，当用户出现字符1按回车键后出现一个迷宫图，红色矩形块（表示探索物）出现在左上角，这是可以按代表8个方向的字符选择通路，遇到墙壁不能通行，按回车键结束探索，如果这是探索物移动到右下角出口，则显示找到通路信息，否则显示没有找到通路信息，在提示信息后，如果输入的字符不是1 ，则系统自动查找通路，如果没有找到通路，则显示没有找到通路信息，如果找到通路，则用红色标记走过的路径第3章 详细设计3.1 main（）主函数首先，确定是进行人工探索还是系统自动探索，通过输入字符来选定，选定之后调用图形初始化函数，紧接着调用迷宫生成函数及迷宫显示函数，然后根据输入的字符调用人工探索函数或自动探索函数。探索完毕进行处理，最后关闭图形系统，程序结束。if(ch=1)PeopleFind(map);/人工搜索elseFindWay(map,1,1);/系统自动从下标1,1的地方开始搜索3.2 Init（）初始化函数由于迷宫图是在图形方式显示的，所以要进行图形初始化工作。3.3 MapRand（）迷宫生成函数用数组map表示一个迷宫，要随机生成迷宫，数组元素的值利用随机函数生成0或1的数。将最外面一圈设为墙壁即不可通过，作为一个封闭图形，只留下入口点和出口点为通路。for(i=0;iN;i+)for(j=0;jN;j+)if(i=0|i=N-1|j=0|j=N-1)/最外面一圈为墙壁map1j=1;elseif(i=1&j=1|i=N-2|&j=N-2)/出发点与终点表示为可走的mapij=0;elsemapij=random(2);/其他的随机生成0或13.4 PrMap（）迷宫显示函数根据数组map的值输出迷宫图，利用函数setfillstyle（）设置图形实体填充样式，bar（）函数输出矩形块，每个块的大小为12*12单位，块与块间距为3，如果数组元素值为0，则填充为白色，值为1显示填充为蓝色，一个数组元素对应一个矩形块。数组元素的下标为矩形块的中心坐标，利用两重循环语句可以完成迷宫图的显示。3.5 FindWay（）系统自动探索从下标（1，1）开始探索，依次按照右下、下、右、上、右上、左下、左、左上的顺序前进，若该方向上的值为0，则前进一步，然后作相应的标记，表示该探索物在某一方向探索过，而在另一个方向上探索，若8个方向均已探索过，则不能再前进，需要沿着原来的路径回溯一步，然后重复上述过程直到出口。判断8个方向的顺序前三个是判断右下、下、右、这样的话可以以最短的路径找到迷宫出口。因为要回溯，所以实现的方法可以有两种；一种是非递归型方法，设置一个堆栈，记录所有走过的路径，前进时入栈，回溯时可以出栈；另一种是递归方法，不必设堆栈，但递归的方法其实就是栈的应用，只不过栈由系统安排，对用户是不可见的。本程序采用了后者实现。在递归过程中凡是已经走过的路，做标记为1，防止来回徘徊而最终无法找到出口。由于走过的路数组元素要改变为1，为了8个方向的递归和回溯，所以做了一个函数WayCopy（）把旧迷宫数组拷贝到新迷宫数组。同时设计一个全局变量yes，如果到了出口，yes赋值为1 ，探索结束。为了显示所走过的路径，把具体的路线保存在二维数组way中。Wayn0代表所走路径的行下标，wayn1代表所走路径的列下标，其中的n代表走的步数，根据way数组将走过的路径用红色显示。3.6 PeopleFind（）人工探索首先输出迷宫图以及人工控制操作图示。红色探索物出现在左上角，采用人工控制8个方向的移动，由于8个方向，用光标键只能控制4个方向，为了统一，采用了临近的8个字符q、w、e、a、d、z、x、c代表8个方向，按了字符后，对应方向不是墙壁，可以将红色探索无移动到相应位置，按回车键表示人工操作，如果此时map数组元素的坐标是目标出口，则yes赋值为1，表示探索成功，否则赋值为0。由于探索物在不停地移动，要在新位置显示，并将走过的路恢复为白色通路，可以调用函数DrawPeople（&x,&y,n）完成，参数x和y代表所走过的行坐标和列坐标，n代表所选的方向，根据n的值将x和y进行相应的变化。void PeopleFind(int (*map)N)int x,y;char c=0;/接收按键的变量x=y=1;/人工查找的初始位置setcolor(11);/设置当前画线颜色line(500,200,550,200);/从当前点开始用增量（x，y）画一直线(int x1,int y1,int x2,int y2)outtextxy(570,197,d);/绘制并填充一个扇形(int x,int y,char far*textstring)3.7 Result（）结果处理函数因为采用了两种探索方式，但最终结果是找到和没找到两种情况，所以在程序中设计了全局变量yes，根据yes的值进行处理，如果yes为0调用函数NotFind()，显示没找到通路信息，否则调用函数Find()。如果是系统自动探索，Find()会显示出所走过的路径，如果是人工探索，没有记录所走过的路径，只显示找到通路信息。if(yes)/如果找到Find();else/没找到路NotFind();3.8 Close()图形关闭函数调用函数closegraph()关闭图形函数系统，程序结束。第4章 编码与调试#include/图形函数#include/其它函数#include/此行为文件包含，告诉系统必须包含文件stdio.h，此文件为输入和输出提供支持。#include/字符屏幕操作函数#include/接口函数#define N 20 /迷宫的大小可以改变int oldmapNN;/递归用的数组，用全局变量节约时间int yes=0;/yes是判断是否找到路的标志，1找到，0没找到int way1002,wayn=0;/way数组是显示路线用的，wayn是统计走了几个格子void Init(void);/图形初始化void Close(void);/图形关闭void DrawPeople(int *x,int *y,int n);/画人工探索物图void PeopleFind(int (*x)N);/人工探索void WayCopy(int (*x)N,int(*y)N);/为了8个方向的递归，把旧迷宫图拷贝给新数组int FindWay(int (*x)N,int i,int j);/自动搜索函数void MapRand(int (*x)N);/随机生成迷宫函数void PrMap(int (*x)N);/输出迷宫图函数void Result(void);/输出结果处理void Find(void);/成功处理void NotFind(void);/失败处理/主函数void main(void)int mapNN;/迷宫数组char ch;clrscr();/清除正文模式窗口printf(n please select hand(1) else auton);/选择搜索方式scanf(%c,&ch);Init();/图形初始化MapRand(map);/生成迷宫PrMap(map);/显示迷宫图if(ch=1)PeopleFind(map);/人工搜索elseFindWay(map,1,1);/系统自动从下标1,1的地方开始搜索Result();/输出结果Close();/图形初始化void Init(void)int gd=DETECT,gm;initgraph(&gd,&gm,c:tc);/画人工控制图void DrawPeople(int *x,int *y,int n)/如果将以下两句注释掉，则显示人工走过的路径setfillstyle(SOLID_FILL,WHITE);/设置白色实体填充样式(int patttern,int color)bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);/画一个二维条形图(int left,int top,int rigth,int bottom)/恢复原通路switch(n)/判断x和y的变化，8个方向的变化case 1:(*x)-;break;/上case 2:(*x)-;(*y)+;break;/右上case 3:(*y)+;break;/右case 4:(*x)+;(*y)+;break;/右下case 5:(*x)+;break;/下case 6:(*x)+;(*y)-;break;/左下case 7:(*y)-;break;/左case 8:(*x)-;(*y)-;break;/左上setfillstyle(SOLID_FILE,RED);/新位置显示探索物bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);/人工手动查找void PeopleFind(int (*map)N)int x,y;char c=0;/接收按键的变量x=y=1;/人工查找的初始位置setcolor(11);/设置当前画线颜色line(500,200,550,200);/从当前点开始用增量（x，y）画一直线(int x1,int y1,int x2,int y2)outtextxy(570,197,d);/绘制并填充一个扇形(int x,int y,char far*textstring)line(500,200,450,200);outtextxy(430,197,a);line(500,200,500,150);outtextxy(497,130,w); line(500,200,500,250);outtextxy(497,270,x);line(500,200,450,150);outtextxy(445,130,q);line(500,200,550,150);outtextxy(550,130,e);line(500,200,450,250);outtextxy(445,270,z);line(500,200,550,250);outtextxy(550,270,c)/以上是画8个方向的控制介绍setcolor(YELLOW);/设置当前画线颜色(int color)outtextxy(420,290,Press Enter to end);/按回车键结束setfillstyle(SOLID_FILL,RED);/设置填充模式和颜色bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/入口位置显示while(c!=13)/如果按下的不是回车键c=getch();/接收字符后开始各个方向的探索if(c=w&mapx-1y!=1)DrawPeople(&x,&y,1);/上elseif(c=e&mapx-1y+1!=1)DrawPeople(&x,&y,2);/右上elseif(c=d&mapxy+1!=1)DrawPeople(&x,&y,3);/右elseif(c=c&mapx+1y+1!=1)DrawPeople(&x,&y,4);/右下elseif(c=x&mapx+1y!=1)DrawPeople(&x,&y,5);/下elseif(c=z&mapx+1y-1!=1)DrawPeople(&x,&y,6);/左下elseif(c=a&mapxy-1!=1)DrawPeople(&x,&y,7);/左elseif(c=q&mapx-y-1!=1)DrawPeople(&x,&y,8);/左上setfillstyle(SOLID_FILL,WHITE);/消去红色探索物，恢复原迷宫图bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);if(x=N-2&y=N-2)/人工控制找成功的话yes=1;/如果成功标志为1/拷贝迷宫数组void WayCopy(int(*oldmap)N,int(*map)N)int i,j;for(i=0;iN;i+)for(j=0;jN;j+)oldmap(ij=mapij;/递归找路int FindWay(int (*map)N,int i,int j)if(i=N-2&j=N-2)/走到路口yes=1;/标志为1，表示成功return;mapij=1;/走过的地方变为1WayCopy(oldmap,map);/拷贝迷宫图if(oldmapi+1j+1=0&!yes)/判断右下方是否可走FindWay(oldmap,i+1,j+1);if(yes)/如果到达出口了，再把值赋给显示路线的way数组，也正是这个原因，所以具体路线是从最后开始保存waywayn0=i;waywayn+1=jreturn; WayCopy(oldmap,map); if(oldmapi+1j=0&!yes)/判断下方是否可以走，如果标志yes已经是1，则不用找下去了 FindWay(oldmap,i+1,j); if(yes) waywayn0=i; waywayn+1=j; return; WayCopy(oldmap,map); if(oldmapij+1=0&!yes)/判断右方是否可以走 FindWay(oldmap,i,j+1); if(yes) waywayn0=i; waywayn+1=j; return; WayCopy(oldmap,map); if(oldmapi-1j=0&!yes)/判断上方是否可以走 FindWay(oldmap,i-1,j); if(yes) waywayn0=i;waywayn+1=j;return; WayCopy(oldmap,map); if(oldmapi-1j+1=0&!yes)/判断右上方是否可以走 FindWay(oldmap,i-1,j+1); if(yes) waywayn0=i;waywayn+1=j;return; WayCopy(oldmap,map); if(oldmapi+1j-1=0&!yes)/判断左下方是否可走 FindWay(oldmap,i+1,j-1);if(yes)waywayn0=i;waywayn+1=j;return; WayCopy(oldmap,map); if(oldmapij-1=0&!yes)/判断左方是否可走 FindWay(oldmap,i,j-1);if(yes)waywayn0=i;waywayn+1=j;return; WayCopy(oldmap,map); if(oldmapi-1j-1=0&!yes)/判断左上方是否可走 FindWay(oldmap,i-1,j-1);if(yes)waywayn0=i;waywayn+1=j;return; return;/开始的随机迷宫图void MapRand(int (*map)N)int i,j;cleardevice();/清除图形屏幕randomize();/随机数发生器for(i=0;iN;i+)for(j=0;jN;j+)if(i=0|i=N-1|j=0|j=N-1)/最外面一圈为墙壁map1j=1;elseif(i=1&j=1|i=N-2|&j=N-2)/出发点与终点表示为可走的mapij=0;elsemapij=random(2);/其他的随机生成0或1/输出迷宫图void PrMap(int (*map)N)int i,j;for(i=0;iN;i+)for(j=0;j=0;i-)bar(100+wayi1*15-6,50+wayi0*15-6,100+wayi1*15+6,50+wayi0*15+6);sleep(1);/控制时间显示bar(100+(N-2)*15-6,50+(N-2)*15-6,100+(N-2)*15+6,50+(N-2)*15+6);/在目标点标红色setcolor(GREEN);settextstyle(0,0,2);/设置字体大小outtextxy(130,400,Find a way!);/没找到通路vo