迷宫求解课程设计说明书.doc

数据结构课程设计设计说明书迷宫问题求解学生姓名学号班级成绩指导教师计算机科学与技术系2011年 9 月 9 日数据结构课程设计评阅书题 目迷宫问题求解学生姓名学号指导教师评语及成绩成绩： 教师签名： 年 月 日答辩教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。课程设计任务书2011 2012 学年第 一 学期专业： 学号： 姓名： 课程设计名称： 数据结构课程设计 设计题目： 迷宫问题求解 完成期限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周设计依据、要求及主要内容（可另加附页）： 输入一个任意大小的迷宫数据，设置入口、出口及障碍，借助栈结构求解走出迷宫的路径并输出。1.遵循结构化程序设计思想，采用C/C+实现。 2.界面友好，操作简便，容错性。 基本要求如下： 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果；7）编写课程设计报告；以上要求中前三个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导教师（签字）： 教研室主任（签字）： 批准日期： 2011年 8 月 29 日摘 要设计了一个寻找迷宫出口路径的程序，该程序具有设置任意大小的迷宫数据，通过设置的迷宫入口出口及障碍，探索出一条简单路径并输出的功能。该程序采用VC作为软件开发环境，借助栈先入后出的特点，先将入口作为检索的起点，顺着某个方向向前探索，若能走通，则继续往前走；否则沿原路返回，换个方向在继续探索，直到所有可能的通路都探索到为止，最后把探索到的路径输出。关键词：迷宫路径；探索；输出目 录1.课题描述12.问题分析和任务定义23.逻辑设计34.详细设计44.1迷宫数据的存储44.2当前位置可通性的判断及探索方向的改变54.3无通路时沿原路返回64.4路径信息入栈和出栈74.5 当前探索位置的切换84.6最终探索路径的输出及标记94.7打印迷宫信息105.程序代码115.1文件包含和结构体的定义115.2栈的初始化及入栈出栈函数115.3申请迷宫大小及障碍的设置125.4通道可通性测试135.5为走过的通道留下足迹135.6探索位置的切换135.7入口到出口的路径探索145.8打印迷宫信息155.9主函数166.程序测试18总结21参考文献221.课题描述本次课题是实现迷宫问题的求解，利用C语言设计一个能实现输入一个任意大小的迷宫数据，利用二维数组来储存设置的入口、出口及障碍，借助栈先入后出的结构特性保存迷宫探索过程中留下的路径信息，以便在遇到障碍时沿原路返回，在探索结束后输出栈中保存的最终路径。2.问题分析和任务定义迷宫求解的实现依赖于路径探索的算法，路径探索的算法采用的是“穷举求解”的方法。因此有以下问题：(1)数据存储结构的选择。(2)当前位置的可通性判断及探索方向的改变。(3)道路不通时沿原路返回的算法。(4)路径信息的入栈和出栈。(5)最终路径的输出。3.逻辑设计程序要实现路径探索及输出即要实现当前位置可通性的判断；路径可通时朝默认方向继续向前探索，路径不可通时沿原路返回改变探索方向，输出最终探索结果。其关系如图3.1 所示。图3.1 迷宫路径探索功能结构4.详细设计4.1迷宫数据的存储Maze是指向指针的指针，用行h和列l来存储迷宫的大小，使用malloc申请一个二维数组，根据用户输入的障碍坐标在maze数组的相应位置存入1作为障碍标记，直到用户输入0 0结束障碍的设置。该模块的执行过程如图4.1 所示。图4.1 迷宫数据的存储4.2当前位置可通性的判断及探索方向的改变当前位置curpos的坐标在maze数组中对应位置储存的数据若非1和8即为可通在此留下足迹，由变量di来记录下一个探索方向，把下一个位置作为当前位置并继续探索，若当前位置不可通，则后退一步按顺时针方向改变探索方向。操作流程如图4.2所示。图4.2 可通性的判断及探索方向的改变4.3无通路时沿原路返回借助栈先入后出的特性，把探索过的路径信息e压入栈s中。若当前位置curpos的下一个探索方向的变量值di为4时，表示当前位置周围四个方向均无通道，沿原路退回一步将路径信息e逐个出栈，一退直到di<4，改变方向继续探索。该模块的执行过程如图4.3所示。图4.3 无通路时沿原路返回4.4路径信息入栈和出栈当前位置curpos可通时maze数组中的对应位置留下足迹，标记下一个探索方向，若栈s满则追加栈空间，路径信息入e栈*s.top=e，s.top+。若当前位置不可通且栈不为空则后退一步，路径信息e出栈e=*-s.top并改变探索方向。程序的操作流程如图4.4所示。图4.4路径信息入栈和出栈4.5 当前探索位置的切换利用二维数组来确定当前探索位置curpos。方向变量e.di的数值为1时，则横坐标加1；e.di的数值为2时，则纵坐标加1；e.di的数值为3时，则横坐标减1；e.di的数值为4时，则纵坐标减1。程序的操作流程如图4.5所示。图4.5当前探索位置的切换4.6最终探索路径的输出及标记迷宫探索结束时若找不到出口则输出寻找不到路径。若成功找到出口则根据栈s储存的路径坐标信息e在迷宫数据maze数组的相应位置标记2。程序的操作流程如图4.6所示。图4.6最终探索路径的输出及标记4.7打印迷宫信息根据栈s储存的路径坐标信息在迷宫数据mazexx的不同输出不同的符号，分别表示迷宫的障碍和走出迷宫的路径。程序的操作流程如图4.7所示。图4.7打印迷宫信息5.程序代码5.1文件包含和结构体的定义#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define STACK_INIT_SIZE 10int h,l;/保存迷宫大小的行数和列数typedef structint x;int y;point;/定义坐标变量结构体typedef structpoint pos;/保存当前路径的坐标int di;/保存下一个探索方向的标记值selemtype;/定义路径信息结构体typedef structselemtype *base;/栈顶selemtype *top;/栈底int stacksize;/栈的容量sqstack;/栈的定义point start,end;/迷宫出入口的声明5.2栈的初始化及入栈出栈函数/栈的初始化int initstack(sqstack &s)/申请栈的空间s.base=(selemtype *)malloc(STACK_INIT_SIZE*sizeof(selemtype);if(!s.base)/判断栈是否申请成功exit(-2);s.top=s.base;/使栈为空s.stacksize=STACK_INIT_SIZE;/给栈的容量赋值return 1;/入栈函数int push(sqstack &s,selemtype e)if(s.top-s.base>=s.stacksize)/判断栈是否已满s.base=(selemtype *)realloc(s.base,(s.stacksize+10)*sizeof(selemtype);/栈满时追加申请空间if(!s.base) exit(0);s.top=s.base+s.stacksize;s.stacksize+=10;*s.top=e;/元素入栈s.top+;return 1;/出栈函数int pop(sqstack &s,selemtype &e)/栈不为空时元素出栈if(s.top=s.base)exit(0);e=*-s.top;return 1;5.3申请迷宫大小及障碍的设置/迷宫大小初始化int *initmaze()int *maze;/指向二维数组的指针printf("设置迷宫的行和列(如3 3)");scanf("%d%d",&h,&l);/用malloc函数动态申请一个二维数组maze=(int*)malloc(sizeof(int)*h);for(int i=0;i<h;i+)mazei=(int*)malloc(sizeof(int)*l);return maze;/迷宫障碍设置函数void setza(int *maze)char n,m;int x,y;printf("设置入口的坐标(如1 1)");scanf("%d%d",&y,&x);/设置入口坐标while(!(y=h|y=1|x=l|x=1)&&(x<=l&&y<=h)&&(x!=0&&y!=0)printf("请把入口设置在迷宫的边缘n");scanf("%d%d",&y,&x);/设置入口坐标start.x=x-1;start.y=y-1;printf("设置出口的坐标(如2 3)"); scanf("%d%d",&y,&x);/设置出口坐标while(!(y=h|y=1|x=l|x=1)&&(x<=l&&y<=h)&&(x!=0&&y!=0)&&!(y=start.y+1&&x=start.x+1)printf("请把出口设置在迷宫的边缘,不要与入口重合n");scanf("%d%d",&y,&x);/设置出口坐标end.x=x-1;end.y=y-1;printf("设置障碍的坐标n");scanf("%d%d",&n,&m);/设置障碍坐标/当输入# #时结束障碍设置while(!(n=0&&m=0)mazen-1m-1=1;scanf("%d%d",&n,&m);5.4通道可通性测试/当前位置可通性测试int pass(int *maze,point curpos)/根据maze二维数组储存的数值判断当前位置是否可通if(mazecurpos.ycurpos.x!=1&&mazecurpos.ycurpos.x!=8)return (true);else return(false);5.5为走过的通道留下足迹/留下足迹void footprint(int *maze,point curpos)mazecurpos.ycurpos.x=8;5.6探索位置的切换/当前探索位置到下一个探索位置坐标的切换point nextpos(point curpos,int a)switch(a)case 1:/向右移动if(curpos.x<l-1)curpos.x+;break;case 2:/向下移动if(curpos.y<h-1)curpos.y+;break;case 3:/向左移动if(curpos.x>0)curpos.x-;break;case 4:/向上移动if(curpos.y>0)curpos.y-;break;return curpos;5.7入口到出口的路径探索/路径探索函数int mazepath(int *maze,point start,point end,sqstack &s,selemtype e)initstack(s);/栈的初始化为路径信息入栈做准备point curpos=start;/把迷宫入口作为探索的起始位置doif(pass(maze,curpos)footprint(maze,curpos);/若当前位置可通，则留下足迹e.pos=curpos;/把当前位置的坐标赋值给路径信息元素e.pose.di=1;/标记下一个探索位置的方向push(s,e);/当前路径信息入栈/若当前位置为迷宫出口则返回true结束探索if(curpos.x=end.x&&curpos.y=end.y)return (true);curpos=nextpos(curpos,e.di);/切换当前位置继续判断可通性else/当前位置不可通if(s.top!=s.base)/栈不为空pop(s,e);/路径信息出栈while(e.di=4&&s.top!=s.base)/退回一步后，检查一下个探索位置的方向标记值/若e.di=4且栈不为空，则将路径信息元素不断出栈，/直到e.di小于4为止pop(s,e);if(e.di<4)/若当前位置标记的下一个探索方向的值小于4e.di+;/e.di自增改变探索方向push(s,e);/改变下一个探索方向后将元素信息再次入栈curpos=nextpos(e.pos ,e.di);/切换当前位置继续判断可通性while(s.top!=s.base);/若栈不为空则继续执行路径探索循环return (false);/寻找不到路径返回false5.8打印迷宫信息/打印迷宫信息void printmaze(int *maze)int k;char b=1;/把迷宫障碍和最终路径分别标记为a和b两种字符/逐行输出迷宫信息for(k=0;k<l+2;k+)if(start.y=0&&start.x+1=k)|(end.y=0&&end.x+1=k)printf("- ");else printf("");printf("n");for(int i=0;i<h;i+)if(start.x=0&&start.y=i&&start.y!=0&&start.y!=h-1)|(end.x=0&&end.y=i&&end.y!=0&&end.y!=h-1)printf("- ");else printf("");for(int j=0;j<l;j+)if(mazeij=1)/mazexx的值为1则输出方块printf("");else if(mazeij=2)/否则mazexx的值为2则输出b字符printf("%c ",b);elseprintf(" ");/mazexx的值为不为1也不为2则输出空格if(start.x=l-1&&start.y=i&&start.y!=0&&start.y!=h-1)|(end.x=l-1&&end.y=i&&end.y!=0&&end.y!=h-1)printf("- ");else printf("");printf("n");for(k=0;k<l+2;k+)if(start.y+1=h&&start.x+1=k)|(end.y+1=h&&end.x+1=k)printf("- ");else printf("");printf("n");5.9主函数void main()sqstack s;/栈的声明selemtype e;/路径信息元素声明int *maze;/指向迷宫信息的指针声明bool flag=1;/程序循环使用的旗帜while(flag)printf(" 寻找迷宫的出口n");printf(" n");printf(" * *n");printf(" * 程序使用说明: *n");printf(" * *n");printf(" * 输入横纵坐标请用整数,并用空格将其分开 *n");printf(" * *n");printf(" * 障碍物的设置以0 0作为结束标志 *n");printf(" * *n");printf(" * 欢迎使用! *n");printf(" * *n");printf(" n");maze=initmaze();/迷宫大小初始化setza(maze,start,end);/迷宫障碍和出入口的设置printf("开始寻找出路?(entrt)n");getchar();/程序暂停getchar();system("cls");/清屏/打印迷宫信息printf("迷宫大小为%d行%d列n",h,l);printf("入口坐标为:%d,%d",start.y+1,start.x+1);printf("出口坐标为:%d,%dn",end.y+1,end.x+1);printf("设置的迷宫如下图所示:n");printmaze(maze);/当成功探索到路径是输出路径if(mazepath(maze,s,e)=true)printf("从出口到入口的路径坐标依次为:n"); /当栈不为空时把探索到的路径信息依次出栈while(s.top!=s.base)pop(s,e);mazee.pos.ye.pos.x=2;/在maze数组的对应数据为最终路径标记记号printf("(%d,%d)",e.pos.y+1,e.pos.x+1);/输出路径坐标printf("n");printf("迷宫出路如下图所示:n");printmaze(maze);/打印迷宫信息及最终探索到的路径else printf("寻找不到路径n");printf("继续请按1,退出请按0.n选择:");scanf("%d",&flag);/选择是否继续使用该程序system("cls");6.程序测试设置4行4列的迷宫，设置迷宫入口不在边缘上提示出错，设置出口坐标与入口重合提示出错。迷宫草图如图6.1所示。程序运行图如图6.2设置4行列迷宫数据及6.3寻找不到路径探索结果所示。入出图6.1 4行4列的迷宫示意图图6.2 设置4行4列迷宫数据图6.3寻找不到路径的探索结果设置8行8列的迷宫使其入口在1 1,出口在8 8的位置根据迷宫草图6.4所示设置障碍。入 出图6.4 8行8列的迷宫示意图在程序中设置出入口和障碍坐标如图6.5所示图6.5设置8行8列的迷宫成功探索到迷宫路径的结果如图6.6所示图6.6成功探索到迷宫路径的结果总 结这是我第二次做课程设计，之前的设计经验让我有了下手的方向和技巧，使用模块化的编程不仅使代码清晰易读也使程序的调试方便了许多。迷宫问题求解这个程序的最大问题是寻找迷宫路径遇到障碍时改变方向和走入死胡同时往后退。程序从整体构思到算法设计以及编写，调试历经了种种困难和考验，通过查看资料与同学讨论总结得到了一些问题的解决方案；总结了一些常见问题的解决方法其中包括一些相对合理而简单程序算法。在这次课程设计当中让我在之前所学的c和数据结构知识得到了巩固也提高了综合应用能力。锻炼了自己的实践能力和耐心，程序中的每一处错误都要细心去分析修改，我从中也得到了许多课堂之外的东西更进一步体会到亲自实践和光看着书本学习的不同效果。 通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在程序设计方面有所发展。参考文献1何钦铭 ，颜晖.C语言程序设计M.北京：高等教育出版社,20082严蔚敏，吴伟民.数据结构(C语言版)M.北京：清华大学出版社,20073谭浩强.C程序设计题解与上机指导M. 北京：高等教育出版社,2005