数据结构课程设计-迷宫求解

1、数据结构课程设计数据结构课程设计迷宫求解 院 系： 网络工程 班 级： 网络09 1班 姓 名： 合 作 者： 指导教师： 2010 年 12 月 20 日数据结构课程设计任务书一、题目： 迷宫求解二、设计要求（1）李斌（组长）、尚贺和张雪城组成设计小组。（2）小组成员分工协作完成。要求每个成员有自己相对独立的模块，同时要了解其他组员完成的内容。（3）查阅相关资料，自学具体课题中涉及到的新知识。（4）采用结构化、模块化程序设计方法设计，功能要完善，界面美观。（5）所设计的系统要至少应用一个课程中或者与其密切相关的算法。（6）按要求写出课程设计报告。其主要内容包括：封皮、课程设计任务书，指导教师

2、评语与成绩、目录、概述、软件总体设计、详细设计、软件的调试、总结、附录：带中文注释的程序清单、参考文献。报告一律用a4纸打印，中文字体为宋体，西文字体用time new roma，一律用小四号字，行距采用“固定值”18磅，首行缩进2字符。总体设计应配合软件总体模块结构图来说明软件应具有的功能。详细设计阐述本人设计模块部分的设计思想、应用到的理论和算法、程序流程等等，调试的叙述应配合出错场景的抓图来说明出现了哪些错误，如何解决的。（7）课程设计报告中的软件总体设计、详细设计、软件的调试等主体内容要以文字描述、图表等形式为主，可配以主要核心代码，在附录中附程序清单。三、课程设计工作量由于是设计小组

3、团结协作完成设计任务，一般每人的程序量在200行有效程序行左右，不得抄袭。四、课程设计工作计划2010年12月20日，指导教师讲课，学生根据题目准备资料；2010年12月21日，设计小组进行总体方案设计和任务分工；2010年12月22日2010年12月27日，每人完成自己承担的程序模块并通过独立编译；2010年12月28日2009年12月30日，将各模块集成为一个完整的系统，并录入足够的数据进行调试运行；2010年12月31日，验收、开始撰写报告；2011年01月4日前，提交课程设计报告。 指导教师签章： 教研室主任签章 数据结构课程设计指导教师评语与成绩指导教师评语：课程设计表现成绩： 课程

4、设计验收成绩： 课程设计报告成绩： 课程设计 总成绩： 指导教师签章 2011年 01 月 04 日目 录第1章 概述51.1 性能需求51.2 功能需求5第2章 概要设计62.1 功能模块设计62.2 算法分析与设计7第3章 详细设计83.1 迷宫求解功能模块设计83.2 文件的存取模块设计8第4章 调试分析与测试结果104.1 调试分析104.2 测试结果10第5章 总结13参考文献14附录15第1章 概述1.1 性能需求随着社会经济和人们物质生活的不断提高，人们对精神生活的需求也越来越高，在现今社会里，人们对诸如智商、情商等的重视无疑反映了对精神生活的态度。当然具体到我们每个人来说，想必

5、大多数人小时候都曾玩过魔方、迷宫吧。作为这种智力游戏，人们是百玩不厌的。正是鉴于这种需求，本设计应用计算机语言及其算法，将人的意志赋予机器实现，使人们不必再陷于枯燥的重复劳动，从而将更多的精力投入到对未知领域的探索上。1.2 功能需求本设计的关键在于将人的想法自能化，由所编软件自动的搜索可行路径。因此，软件必须拥有自动搜索并记录可行路径的功能，除此之外，软件还应设置人机交互接口，以便能够人为的建立迷宫图；软件要能保存以输入的迷宫图，并能调取外部现有的迷宫图；当然对于迷宫问题还有很多要考虑的地方，比如由用户自己来探索可行路径，但由于本设计侧重于迷宫求解的算法设计，并非以游戏的形式为初衷，定有不全

6、之处。第2章 概要设计2.1 功能模块设计本设计主要分为个模块：初始化栈模块、迷宫建立模块、迷宫求解模块、文件的保存与调取模块。1. 初始化栈模块，由initstack(sqstack &s)、push(sqstack &s,selemtype e)、pop(sqstack &s,selemtype &e)、stackempty(sqstack s)函数构成，此模块是解决问题的关键算法，贯穿整个设计的始终。2. 迷宫建立模块，由initmaze(int mazemn)构成，此模块用于用户自己设计并建立迷宫。3. 迷宫求解模块：由mazepath(posttype start,posttype

7、end,int mazemn,int diradd42)构成，此模块是基于栈的特点与迷宫实际相结合来实现的。4. 文件的保存与调取模块：由file_save(int maze50,int x,int y)、file_get(int mazemn)构成，此模块用来存储用户建立的迷宫，并方便其调取外部的现有迷宫。流程图如下：开 始初始化栈模块迷宫建立模块迷宫求解模块文件的保存与调取模块结 束2.2 算法分析与设计栈：假设栈s=(a1,a2,an),则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,an的次序进栈，退栈的第一个元素为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，

8、栈又称为后进先出的线性表。由于计算机解谜宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。首先，迷宫图用方块表示，每个方块或为通道，或为墙。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳

9、入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北）上相邻的方块。假设以栈s记录“当前路径”，则栈顶中存放的是“当前路径”上最后一个通道块。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。其中需要说明的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不

10、仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入路径的通道块（否则只能在死胡同内转圈）。此软件的主要实现均是按照上述分析设计而成。第3章 详细设计3.1 迷宫求解功能模块设计此模块主要由函数mazepath(posttype start,posttype end,int mazemn,int diradd42)来实现，当然此功能实现主要基于对栈的操作。模块用：typedef structint x;int y;posttype;typedef structint x,y;int d;/*1表示右，2表示下，3表示左，4表示上*/selemtype;来表示坐标类型及

11、迷宫中每一方块的属性（包括坐标、下一步的方向），用1和0分别表示墙和通路并用二维数组存储，从而将实际问题转化成数学模型，方便程序的设计，以实现其自能化。具体的程序实现可参见附录。3.2 文件的存取模块设计此模块由file_save(int maze50,int x,int y)、file_get(int mazemn)来实现，此功能主要是对文件的操作。其中file *fp;是对文件指针的定义，if(fp = fopen(str,w)=null)return;和if(fp=fopen(str,rb)=null)return;分别是以写和读的方式打开文件，以便对文件进行相应的操作，最后以fclos

12、e(fp);来关闭文件。以向文件中写数据为例的部分程序实现如下：file *fp;int i,j;char str=;coutstr;if(fp = fopen(str,w)=null)return;fprintf(fp,%d ,x);fprintf(fp,%d ,y);fprintf(fp,n);for(i = 0;i x;i +)for(j = 0;j y;j +)fprintf(fp,%d ,mazeij);fprintf(fp,n);fclose(fp);具体功能的程序实现可参见附录。(文件存储流程图如下)开 始定义文件指针fp输入字符串str定义i ,j以“w”打开文件成功？返回空y

13、向文件中输出数据x ,yi = 0yix？i = 0jy？nyj+向文件输出mazeiji+关闭文件结 束第4章 调试分析与测试结果4.1 调试分析1. 迷宫求解模块：此模块的调试主要在于迷宫中每个方块出栈入栈的时机及对栈本身的操作。2. 文件的存取模块：此模块的调试主要在于对文件输入、输出操作及文件打开不成功时的应对。4.2 测试结果1迷宫求解模块：根据调试分析进行测试预期结果：程序能够自动搜索下一步的方向，并能记录已经走过的方向。实际测试结果：程序只能沿着固定的方向搜索，而不能退回到该方块继续从其他方向开始搜索。程序部分代码如下：while(!stackempty(s1) /*栈不为空 有

14、路径可走*/ pop(s1,elem); i=elem.x; j=elem.y; while(d4) /*试探东南西北各个方向*/ a=i+diraddd0; b=j+diraddd1; if(a=end.x & b=end.y & mazeab=0) /*如果到了出口*/ elem.x=i; elem.y=j; elem.d=d; push(s1,elem); elem.x=a; elem.y=b; elem.d=886; /*方向输出为-1 判断是否到了出口*/ push(s1,elem); printf(n0=右 1=下 2=左 3=上 886为走出迷宫nn通路为:(行坐标,列坐标,方向

15、)n);更正：在代码pop(s1,elem); i=elem.x; j=elem.y; 后加一条语句：d=elem.d+1; /*下一个方向 */更正后实际运行结果图如下：此结果与预期结果一致。2. 文件的存取模块：根据调试分析进行测试预期结果：可从外部文件中调取数据。实际测试结果：调取数据时产生混乱。部分程序代码如下：file *fp;int i,j,pos2;char str=;coutstr;if(fp=fopen(str,rb)=null)return;for(i = 0;i 2;i +)fscanf(%d ,&posi);for(i=0;ipos0;i+)for(j =0;jpos1

16、;j+)fscanf(fp,%d ,&mazeij);printf(%d ,mazeij);printf(n);fclose(fp);更正：将fscanf(%d ,&posi);改为fscanf(fp,%d ,&posi);。更正后实际运行结果图如下：此结果与预期结果一致。第5章 总结通过迷宫求解的编程练习思考数据结构的使用，比如对栈、指针、链表等的深入了解，让我们感受到了数据结构及其算法的重要。此外还熟悉了各种函数的应用。对于我们初学者来说，学习编写迷宫求解，对我们掌握了解数据结构的知识有很大的帮助。我们通过编程实践，还能拓展思路，让我们主动去寻找所需要的算法，怎样提高程序的质量等。通过编程

17、我知道了想要写出好的程序，需要有扎实的基础，这样才会遇到一些基本算法时做的游刃有余。在编程时，我们要有丰富的想象力，不拘泥于固定的思维方式，试试别人从没想过的方法。丰富的想象力是建立在丰富的知识的基础上，所以我们要通过多个途径来帮助自己建立较丰富的知识结构。在编程时，我们遇到了很多的困难，这就需要我们多与别人交流。在编程时我们也看到了有良好的编程风格是十分重要的，至少在时间效率上就体现了这一点。现在自己也能运用数据结构的算法编写小程序了，却没想到的是算法并没想象的那么简单（还有这份文档）。这两周，我们整天为了编程而忙碌，但看到自己的迷宫求解程序终于完成了，我们还是觉得很开心。当一切都完成以后，

18、除了学会运用基本的算法外，我们也学会了许多别的东西。首先，我们学会了合作。合作，必然会产生分歧；学会去解决分歧，留下更多的是友谊。其次，我们学会了分工。分工是为了更好的合作，分工才能提高合作的效率。最后，我们学会了奋斗。我们相信，通过在北华大学的四年学习，我们定能写出更精彩的程序，描绘出更精彩的人生。在这里，我们要感谢指导我们课程设计的薛曼玲老师，给予我们悉心的指导。老师多次询问我们编写进程，并为我们指点迷津，帮助我们开拓研究思路，精心点拨、热枕鼓励。老师一丝不苟的工作作风，严谨求实的态度以及踏踏实实的精神，不仅授我以文，更教会我做人，给以终生受益无穷之道。我还要感谢我们开发小组的另外2名同学

19、，在设计中给予我很大的帮助。正是由于我们团结协作，才顺利地完成了课程设计任务。在设计中，我确实感到了团队合作的力量。课程设计完成之后，留下的必将是美好的回忆。参考文献1谭浩强主编. c语言程序设计（第三版）.北京：清华大学出版社2009.2严蔚敏、吴伟民主编. 数据结构（c语言版）.北京：清华大学出版社 2010附录#include #include #include #include #define stack_init_size 100#define stackincrement 10#define ok 1#define error 0#define overflow -2#define

20、 m 50#define n 50typedef int status;typedef structint x;int y;posttype;typedef structint x,y;int d;/*1表示右，2表示下，3表示左，4表示上*/selemtype;/*/栈*/typedef struct sqstackselemtype * base;selemtype * top;int stacksize;sqstack;status initstack(sqstack &s) s.base=(selemtype *)malloc(stack_init_size*sizeof(selemt

21、ype); if(!s.base) exit(overflow); s.top=s.base; s.stacksize=stack_init_size; return ok;status stackempty(sqstack s) if (s.base=s.top) return ok; else return error;status push(sqstack &s,selemtype e) if(s.top-s.base=s.stacksize) s.base=(selemtype *)realloc(s.base, (s.stacksize+stackincrement)*sizeof(

22、selemtype); if(!s.base) exit(overflow); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; *s.top+=e; return ok;status pop(sqstack &s,selemtype &e) if(s.top=s.base) return error; e=*-s.top; return ok;/*迷宫求解*/*求迷宫路径函数*/ void mazepath(posttype start,posttype end,int mazemn,int diradd42) int i,j,d;

23、int a,b; selemtype elem,e; sqstack s1, s2; initstack(s1); initstack(s2); mazestart.xstart.y=2; /*入口点作上标记 */elem.x=start.x; elem.y=start.y; elem.d=-1; /*开始为-1*/ push(s1,elem); while(!stackempty(s1) /*栈不为空 有路径可走*/ pop(s1,elem); i=elem.x; j=elem.y; d=elem.d+1; /*下一个方向 */while(d(%d,%d,%d),e.x,e.y,e.d);

24、return; /*跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(_)o.*/ if(mazeab=0) /*找到可以前进的非出口的点*/ mazeab=2; /*标记走过此点 */elem.x=i; elem.y=j; elem.d=d; push(s1,elem); /*当前位置入栈*/ i=a; /*下一点转化为当前点 */j=b; d=-1; d+; printf(no road!n); /*建立迷宫*/ void file_save(int maze50,int x,int y)/存储数据到文件file *fp;int i,j;cha

25、r str=;coutstr;if(fp = fopen(str,w)=null)return;fprintf(fp,%d ,x);fprintf(fp,%d ,y);fprintf(fp,n);for(i = 0;i x;i +)for(j = 0;j y;j +)fprintf(fp,%d ,mazeij);fprintf(fp,n);fclose(fp);printf(your maze has been saved as your file!n);void file_get(int mazemn)/从文件中抽取数据file *fp;int i,j,pos2;char str=;coutstr;if(fp=fopen(str,r)=null)return;for(i = 0;i 2;i +)fscanf(fp,%d ,&posi);for(i=0;ipos0;i+)for(j =0;jpos1;j+)fscanf(fp,%d ,&mazeij);printf(%d ,mazeij);printf(n);fclose(fp);void initmaze(int mazemn) int i,j; int m,n; /*迷宫行,列 */char c;printf(input mode row: m=); scanf(%d,