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

合肥学院计算机科学与技术系课程设计报告2008 2009 学年第二学期课程数据结构与算法课程设计名称迷宫问题学生名称陈建华专业班级08计本（2）班指导教师王昆仑 2010年6月一、问题分析和任务定义1题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，完成迷宫的组织与存储，并实现迷宫的路由算法。即对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论2.设计要求：(1)N和M是用户可配置的，缺省值为50和50。(2)迷宫的入口和出口分别在左上角和右下角。(3)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。(4) 以二维数组存储迷宫数据。3.问题描述：迷宫是一个矩形区域如图（a）所示，它有一个入口和一个出口，其内部包含能穿越的强或障碍。迷宫老鼠问题就是要寻找一条从入口到出口的路径。 对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。（1，1）表示入口位置，（n,m）表示出口位置；从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。这样，如图（a）所示的迷宫就可以用图（b）所示的矩阵来描述。其中，a11=0表示入口,anm=0表示出口；若aij表示从入口到出口路径上的某个位置，则应该有aij=0经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。0 1 1 1 1 1 0 0 0 00 0 0 0 0 1 0 1 0 00 0 0 1 0 1 0 0 0 00 1 0 1 0 1 0 1 1 00 1 0 1 0 1 0 1 0 00 1 1 1 0 1 0 1 0 10 1 0 0 0 1 0 1 0 10 1 0 1 1 1 0 1 0 01 0 0 0 0 0 0 1 0 00 0 0 0 0 1 1 1 0 0 (a) (b)4.测试用例：手动绘制迷宫正确的输入数据：0 0 0 0 1 01 1 1 0 1 00 1 0 0 0 11 0 1 1 1 1手动绘制迷宫正确的输出结果：随机绘制迷宫错误的输出结果：此迷宫没有通路！注：用一个二维数组表示迷宫，数组中的每个元素表示一个小方格，0和1分别表示迷宫中的通路和障碍。用（i，j）的形式表示迷宫中各个位置的坐标。二、数据结构的选择和概要设计1.数据结构的选择解决此问题需要运用到链栈的数据结构。因为求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。所以，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。2.数据结构的定义（1）栈的定义栈（stack）是只能对一端的数据元素进行操作，即限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。栈是满足下列条件的数据结构：（1）有限个具有相同数据类型的数据元素的集合，D=ai|i=1,2,3,n，ai为数据元素。（2）数据元素之间的关系R=|ai ，ai +1D。（3）a1为栈底元素，an为栈顶元素；入栈时，数据元素按a1，a2，an，的次序进栈，出栈的第一个元素应为栈顶元素an。用途：用来保存从迷宫入口到迷宫出口的路径。（2）迷宫坐标的定义：typedef struct node/链栈结构int row; /行int col; /列struct node * next;mlink;用途：该结构体用来存储迷宫中的行坐标和列坐标。（3）迷宫最大行列数定义：#define MaxX 50 /迷宫最大行数#define MaxY 50 /迷宫最大列数用途：用来定义迷宫的最大尺寸为50*50。2.函数之间关系：在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。（三）详细设计（流程图表示）主要对框架和主要的函数表示一下：1.程序结构图：选择菜单开 始调用行数列数输入函数选择1显示函数调用结 束选择2选择3出入口函数调用判断函数调用路径显示函数调用YN路径判断函数调用2：判断路径函数流程图：开 始输入出口和入口判断入口是否为1入口进栈Y显示无出路N返回到菜单向其中一个方向寻找判断是否为1Y定点进栈判断是否为出口四上机调试1.调试过程中遇到的错误和问题（1）在编译框中显示“timeundeclared identifier”即没有定义time函数。双击错误信息，根据编译软件的提示找到了错误信息行然后发现在程序的的开头没有输入“#include。加一个该函数，编译通过。（2）在编译框中显示“nonstandard extension used：zero-sized array in struct/union”和“class mazehas an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。（3）在没有语法上的错误，运行时出现死循环，在方向判断上的算法有点错误，就是入口进栈时，在下一个点上没有通路时，就会出栈，如果出栈的话，就会使判断的函数的条件符合，就不能继续的往下寻找，这就是算法的错误，在确认以后就容易修改了，定义一个指针指向栈的下一个地址，这时栈在判断时不会出现上述的情况了。改正以后算法运行正常。（4）在图形输出上，原本想用一个二维数组来存储数据，但在运行出现错误，这就需要另一个辅助数组了，先对辅助数组进行初始化为一，找到通路就将辅助数组的值赋为0。这一步在算法上没有了错误。（5）在通路显示上不符合要求，这就出现在输出函数上了，检查时发现，循环条件i和j是从0开始的，所以辅助数组内的行数和列数都要减1，在改正以后程序运行正常，即能正常输出正确的路径。（6）在执行程序时发现输出迷宫路径坐标出现了重复。经过对上面出现的错误信息的仔细分析，发现在访问迷宫的某一位置后，没有对访问过的位置的值置1。即需要在程序的正确位置加入“gij=1”这一程序段，加入之后，这一问题便迎刃而解。3.算法的时间和空间性能分析由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。 链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。4.算法设计、调试的经验和体会在进行程序设计时，要有良好的设计风格。即要有恰当的标识符即模块名、变量名、常量名、子程序名等。这些名字应能反映它所代表的实际东西，应有一定的实际意义，使其能够见名知意，这样有助于程序员和其他人对程序的理解。同时在编写程序时，要对每一个程序段加上注释，这样可以有助于程序员和其他人对程序的理解，以便能熟练的操作程序。还有在编写程序时要注意对程序的视觉组织，因为一个程序写得密密麻麻，分不出层次常常是很难看懂的。也使得程序的正确性大大降低。在进行程序设计时，仅仅有良好的设计风格还是远远不够的。还需要程序员有过硬的基本功。比如：在编写程序时，应避免过多的循环嵌套和条件嵌套。应利用括号使逻辑表达式和算术表达式的运算次序清晰直观。要使程序模块化应使模块功能尽可能单一化，模块间的耦合性能够清晰可见，等等。所谓程序调试，是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。这是保证计算机程序正确性的必不可少的步骤。编完计算机程序，必须送入计算机中测试。程序调试分以下几步进行： 第一步：用编译程序把编制的源程序按照一定的书写格式送到计算机中，编译程序会根据使用人员的意图对源程序进行增、删或修改。 第二步：把送入的源程序翻译成机器语言，即用编译程序对源程序进行语法检查并将符合语法规则的源程序语句翻译成计算机能识别的“语言”。如果经编译程序的检查，发现有语法错误，那就必须用编译程序来修改源程序中的语法错误，然后再编译，直至没有语法错误为止。 第三步：使用计算机中的连接程序，把翻译好的计算机语言程序连接起来，并扶植成一个计算机能真正运行的程序。在连接过程中，一般不会出现连接错误，如果出现了连接错误，说明源程序中存在子程序的调用混乱或参数传递错误等问题。这时又要用编译程序对源程序进行修改，再进行编译和连接，如此反复进行，直至没有连接错误为止。第四步：将修改后的程序进行数据测试，这时可以定义几个原始数据去试运行，并把输出结果与手工处理的正确结果相比较。如有差异，就表明计算机的程序存在有逻辑错误。这类错误在所有的错误当中最为可怕。如果程序不大，可以用人工方法去模拟计算机对源程序的这几个数据进行修改处理；如果程序比较大，人工模拟显然行不通，这时只能将计算机设置成单步执行的方式，一步步跟踪程序的运行。一旦找到问题所在，仍然要用编译程序来修改源程序，接着仍要编译、连接和执行，直至无逻辑错误为止。经过对程序的编制，调试和运行，使我更好的掌握了栈的基本性质，进一步熟悉掌握了有关栈的基本操作和有关迷宫问题的解决方法。同时更进一步掌握了有关类的操作和熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。五测试结果及其分析手动绘制迷宫正确的输入数据：（1）手工绘制时，先输入行数和列数，再操作界面的提示操作，输入矩阵的格式，确认一下，这时函数会给出迷宫的图形界面，输入出入口的坐标，确认一下，会给出路径的坐标和图形界面，调试的界面如下：（2）自动生成迷宫： 这个操作只要输入行数和列数，确认一下会自动生成迷宫，同时给出图形界面，接下来的操作和手动的操作相同，具体的调试过程如下：（3）退出： 输入给出的操作提示符，即可退出该程序：调试过程如下：六.用户使用说明1.编译环境：Visual C+6.0的集成化环境2.操作过程 运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。七.参考文献1 王昆仑，李红。数据结构与算法。北京：中国铁道出版社，2007。2 谭浩强。C+程序设计。北京：清华大学出版社，2004。3 胡学钢。数据结构。北京：高等教育出版社，2006。4 胡学钢。数据结构与算法设计指导。北京:清华大学出版社，1999。5 郑莉，董渊，张瑞丰。C+语言程序设计（第三版）。北京：清华大学出版社，20036 黄国兴，张炯民。数据结构与算法。北京：机械工业出版社，2004八.附录#includeiostream#includestdio.h/#includetime.h#includemalloc.h#define M 50#define N 50typedef struct node/链栈结构int row; /行int col; /列struct node * next;mlink;mlink *stack;/定义一个栈int m,n,x1,x2,y1,y2;/定义全局变量int mgMN;/*/void shuru()printf(输入行数：n);scanf(%d,&m);printf(输入列数：n);scanf(%d,&n);/*/void chushi()for(int i=0;i=m+1;i+)for(int j=0;j=n+1;j+)mgij=1; /初始化矩阵,将最外围置为1/*/void churukou()printf(n输入迷宫入口：n);scanf(%d%d,&x1,&y1);printf(输入迷宫出口：n);scanf(%d%d,&x2,&y2); /*/void showplay(int mgM+2)/迷宫输出int i,j;printf(迷宫矩阵如下(0可通)：n);for(i=1;i=m;i+)printf(n);for(j=1;j=n;j+)printf(%d ,mgij);printf(n迷宫图形如下(白色可通)：n);for(i=1;i=m;i+)printf(n);for(j=1;jrow=x1;p-col=y1;p-next=NULL;stack=p; /将入口放入堆栈mgstack-rowstack-col=1;/标志入口已访问while(!(stack-row=NULL&stack-col=NULL)&(!(stack-row=x2&stack-col=y2)/循环条件直到找到输入的出口if(mgstack-rowstack-col+1=0)/下面位置可通p=(mlink *)malloc(sizeof(mlink);p-row=stack-row;p-col=stack-col+1;p-next=stack; /入栈stack=p;mgstack-rowstack-col=1;/将访问过的标记为1else if(mgstack-rowstack-col-1=0)/上面可通p=(mlink *)malloc(sizeof(mlink);p-row=stack-row;p-col=stack-col-1;p-next=stack; /入栈stack=p;mgstack-rowstack-col=1;/将访问过的标记为1else if(mgstack-row+1stack-col=0)/右面可通p=(mlink *)malloc(sizeof(mlink);p-row=stack-row+1;p-col=stack-col;p-next=stack; /入栈stack=p;mgstack-rowstack-col=1;/将访问过的标记为1else if(mgstack-row-1stack-col=0)/左面可通p=(mlink *)malloc(sizeof(mlink);p-row=stack-row-1;p-col=stack-col;p-next=stack; /入栈stack=p;mgstack-rowstack-col=1;/将访问过的标记为1else /不可通 返回上一点if (stack-next!=NULL)/堆栈里布置一个顶点则出栈并返回循环p=stack;stack=stack-next; /出栈free(p); /释放空间else /堆栈里只有一个顶点即入口，此时若释放空间出栈会使循环 /控制语句无法比较（因为stack-col,stack-row都已不存在，)stack-row=NULL;stack-col=NULL;stack-next=NULL;if (stack-row=x2&stack-col=y2) return (1);else return (0);else return(0);/*/void tonglu()/将坐标的顶点输出mlink *q;int i,j;int aMN;for(i=0;im;i+)/辅助数组初始化for(j=0;jrow,q-col);q=q-next;q=stack;while (q!=NULL)/循环条件aq-row-1q-col-1 = 0;/将路径中的点赋给辅助数组aq=q-next;for(i=0;im;i+)/将路径以图形的界面输出for(j=0;jn;j+)if(aij)printf();/1的情况elseprint