C++数据结构 迷宫问题

课程设计(论文)任务书软件学院软件工程+电子商务2009专业2班一、课程设计(论文)题目宫问题二、课程设计(论文)工作自2010年12月27日起至2011年1月2日止三、课程设计(论文)地点:四、课程设计(论文)内容要求：1本课程设计的目的(1) 巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。(2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。(3) 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2课程设计的任务及要求1) 基本要求:(1) 对系统进行功能模块分析、控制模块分析；-(2)系统设计要能完成题目所要求的功能;(3) 编程简练，可用，尽可能的使系统的功能更加完善和全面；(4) 说明书、流程图要清楚;(5) 提高学生的论文写作能力；(6) 特别要求自己独立完成；2) 创新要求：在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。3) 课程设计论文编写要求(1)要按照书稿的规格打印与写课程设计论文(2)论文包括目录、正文、小结、参考文献、附录等(3)课程设计论文装订按学校的统一要求完成4）课程设计进度安却乍内容天数地点构思及收集资料1图书馆编码与调试3实验室撰写论文1图书馆、实验室学生签名：20011年1月3日课程设计（论文）评审意见（1）基本算法（20分）：优（）、良（）、中（）、一般（、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（、差（）；（3）调试分析（20分）：优（）、良（）、中（）、一般（、差（）；（4）论文内容（20分）：优（）、良（）、中（）、一般（、差（）；（5）答辩分析（20分）：优（）、良（）、中（）、一般（、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）目录一、需求分析1二、概要设计2三、详细设计5四、调试分析及测试15五、个人工作及创新18六、小结19参考文献20数据结构课程设计一、需求分析1. 选题理由本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题，迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。2. 基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。3. 功能要求（1）以一个二维数组Mazem+2n+2表示迷宫，其中：MazeOj和Mazem+1j（0=j=n+1）及MazeiO和Mazein+1（0=i=m+1）为做外层的一圈障碍。数组中以0表示通路，1表示障碍，限定迷宫的大小为：m,n=0数据关系：R1=|ai-1,ai$D,i=2,口基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S，&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S，e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S，&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S，visit()初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。ADTStack2)迷宫的抽象数据类型ADTmaze数据对象：D=ai,j|ai,je,#,*,0=i=m+1,0=j=n+1,m,n;Same图二：函数的调用关系图三、详细设计源程序:#include#include#include#defineMAXLEN10/迷宫包括外墙最大行列数目#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;/坐标位置类型typedefstructintr,c;PosType;/迷宫中r行c列的位置/迷宫类型typedefstructintr;intc;chararrMAXLENMAXLEN;/可取，MazeType;typedefstruct/intstep;/当前位置在路径上的“序号”PosTypeseat;/当前的坐标位置intdi;/往下一坐标位置的方向SElemType;/结点类型typedefstructNodeTypeSElemTypedata;NodeType*next;NodeType,*LinkType;/栈类型typedefstructLinkTypetop;intstacksize;SqStack;PosTypestart;PosTypeend;MazeTypemaze;boolfound;/创建栈StatusInitStack(SqStack&S)S.top=(LinkType)malloc(sizeof(NodeType);S.top-next=NULL;S.stacksize=0;returnOK;/进栈StatusPush(SqStack&S,SElemType&e)LinkTypep;p=(NodeType*)malloc(sizeof(NodeType);p-data=e;p-next=S.top;S.top=p;S.stacksize+;returnOK;/判断是否为栈空StatusStackEmpty(SqStackS)if(S.top-next=NULL)returnOK;returnERROR;/出栈StatusPop(SqStack&S,SElemType&e)LinkTypep;if(StackEmpty(S)returnERROR;p=S.top;e=p-data;S.top=S.top-next;S.stacksize-;free(p);returnOK;/销毁栈StatusDestroyStack(SqStack&S)LinkTypep;while(S.top!=NULL)p=S.top;S.top=S.top-next;free(p);/一个一个删除if(S.top=NULL)returnOK;elsereturnERROR;/曾走过但不是通路标记并返回OKStatusMarkPrint(MazeType&maze,PosTypecurpos)maze.arrcurpos.rcurpos.c=;/表示曾走过但不通returnOK;/曾走过而且是通路标记并返回OKStatusFootPrint(MazeType&maze,PosTypecurpos)maze.arrcurpos.rcurpos.c二*;/*表示可通returnOK;/选择下一步的方向PosTypeNextPos(PosType&curpos,inti)PosTypecpos;cpos=curpos;switch(i)/1.2.3.4分别表示东,南,西,北方向case1:cpos.c+=1;break;case2:cpos.r+=1;break;case3:cpos.c-=1;break;case4:cpos.r-=1;break;returncpos;/判断当前位置是否可通StatusPass(MazeType&maze,PosTypecurpos)if(maze.arrcurpos.rcurpos.c=)returnTRUE;elsereturnFALSE;/创建迷宫/按照用户输入的二维数组(0或1),设置迷宫maze的初值，包括加上边缘一圈的值voidInitMaze(MazeType&maze,charaMAXLENMAXLEN,introw,intcol)maze.r=row;maze.c=col;for(inti=0;i=col+1;i+)a0i=1;arow+1i=1;for(i=0;i=row+1;i+)ai0=1;aicol+1=1;for(i=0;i=maze.r+2;i+)for(intj=0;jmaze.c+2;j+)if(aij=1)maze.arrij=#;elsemaze.arrij=;/求迷宫路径的伪码算法：StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)/求解迷宫maze中，从入口start到出口end的一条路径，若存在，返回TRUE,否则返回FALSEPosTypecurpos;SqStackS;SElemTypee;InitStack(S);curpos二start;/设定“当前位置为“入口位置/curstep=1;/探索第一步found=false;doif(Pass(maze,curpos)/当前位置可以通过，即是未曾走到过的通道块留下足迹FootPrint(maze,curpos);/做可以通过的标识/e.step=curstep;e.seat=curpos;e.di=1;/为栈顶元素赋值Push(S,e);/加入路径if(curpos.r二二end.r&curpos.c二二end.c)found二true;/如口果到达终点返回trueelsecurpos二NextPos(curpos,l);/下一位置是当前位置的东邻else/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(maze,e.seat);/留下不能通过的标记Pop(S,e);if(e.di4)e.di+;/换下个方向Push(S,e);/curpos=NextPos(e.seat,e.di);/进行探索while(!StackEmpty(S)&!found);DestroyStack(S);returnfound;/将标记路径信息的迷宫（字符型方阵）输出到终端（包括外墙）voidPrintMaze(MazeType&maze)for(inti=0;i=maze.r+2;i+)for(intj=0;j=2)if(ncnum)m+;n=1;a2mn=datai;n+;i+;fclose(fp);InitMaze(maze,a2,rnum,cnum);printf(n迷宫建立完成！n);break;，fcasem:printf(n请输入迷宫入口的坐标，以空格为间隔：-);scanf(%d%d,&start.r,&start.c);printf(n请输入迷宫出口的坐标，以空格为间隔：-);scanf(%d%d,&end.r,&end.c);MazePath(maze,start,end);break;，fcasep：if(found)printf(n求解迷宫的结果如下-n);PrintMaze(maze);elseprintf(n找不到路径！n);voidmain()charcmd;Initialization();do/读入一个操作符命令/解释执行命令操作符ReadCommand(cmd);Interpre(cmd);while(cmd!=q);调试分析及测试1、调试分析：(1) 本程序有一个核心算法，即求迷宫的路径，在调试的时候，出现了两个问题：没有想到要用记号，导致迷宫走不出来；没有设置found,不知何时跳出。(2) 原本栈的元素e中除了di往下一坐标位置的方向和seat当前的坐标位置，还有一个step当前位置在路径上的序号，后来发现step没什么用，就删掉了。(3) 函数ReadCommand中，cmd=getchar();的位置找不准，最后是试出来的。(4) 调试的时候多次出现，没有错误，但是dos环境下就是执行不起来，所以采用了一些输出变量，判断到底是哪里出了问题。(5) 本程序中三个主要的算法：InitMaze,MazePath和MarkPrint的时间复杂度均为O(m*n),本程序的空间复杂度也为O(m*n)(栈所占最大空间)2、使用说明和运行结果:(1)首先以文件形式输入迷宫数据，如图三:12-记事本丨回文1中E探辑E13式卫)樂也耳和(HJEFULU1U0C110-LUL-1)11C0:1n1n划FJ图三(2)进入演示程序后，会出现以下界面如图四:图四(3) 进入“创建迷宫”的命令后，即提示输入迷宫数据的文件名，结束符为“回车符”，该命令执行之后输出“迷宫建立完成”，且输出下面可执行的操作。如图五：图五(4) 进入“执行迷宫”的命令后，即提示输入迷宫入口，出口的坐标，结束符为“回车符”，该命令执行之后表示迷宫路径已寻找完成或未找到路径。请注意：若迷宫中存在路径，执行此命令后，迷宫状态已经改变，若要重复执行此命令，需重新输入迷宫数据。如图六：图六(5) 进入“输出迷宫”的命令后，即输出迷宫求出路径之后的状态。#表示障碍，表示曾走过但不通，*表示路径。如图七：图七(6) 进入“退出”的命令后，按任意键结束。如图八:图八3、缺点与改进：(1) 在定义函数Mazepath的时候，开始的循环语句的结束条件不对，没有出路时，导致一直出现了不正确的结果，最后没有新位置入栈，则返回上一个位置，否则没有路径。(2) 只是以文件形式输入迷宫，如果迷宫数据量大时，要先建好文件还是很浪费时间，如果以随机产生函数自动产生迷宫会更好。五、个人工作及创新为了准备这次课程设计我查找了很多的资料，对于迷宫问题的求解中迷宫的产生方式有很多的不同，有的是直接输入迷宫，有的是用文件输入，有的是随机函数产生，我的课设是参考了用文件输入的方法，这样做相比直接输入迷宫操作要更简单。当然用随机函数产生迷宫比如用：for(i=0;iMAX_ROW;i+)for(j=0;jMAX_COL;j+)mazeij=(int)(rand()%2);maze10=1;/*startpoint*/mazeMAX_ROW-1MAX_COL-2=1;/*endpoint*/这样产生迷宫要更加的方便。结果也有不确定性，可能可以有通路也可能没有。对于迷宫的求解都是采用的“穷举求解”的方法，用到了一些栈的知识。把以前学过的栈的基本操作实际应用了一番也使有了更加清楚的认识。在求解迷宫的算法中，先设定当前位置的初值为入口位置，然后Do若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东邻方块为新的当前位置；否则若栈不为空且栈顶位置尚有其它方向未被探索，则设定新的当前位置为延顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置四周均不通，则删去栈顶位置；若栈不为空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；求解迷宫的算法大概就是这么个思路。六、小结要能很好的掌握编程，仅仅通过几个简单的程序的编写是无法达成的，更需要的是大量的积累和深入研究才可能。在程序的编写中也不能一味的向已有的程序进行模仿，而要自己去探索，去寻找最好的解决方法，只有带着问题去反复实践，才能更熟练的掌握和运用，当然，对现有的程序也要多去接触，因为有些程序是我们在短时间内无法想出来的，我们也应该去参考别人的作品，这样可以节约时间获得更多的知识。最重要的是持之以恒，要经常性的复习原来接触到的程序，这样才能保证我们有足够的经验去面对程序问题。参考文献1 .严蔚敏，吴伟民数据结构（C语言版）清华大学出版社.20072 .严蔚敏，数据结构题集（C语言版）清华大学出版社.20073 .谭浩强，C程序设计（第四版）清华大学出版社.2007