用C语言解决迷宫设计与寻找通路的问题.doc

用C语言解决迷宫设计与寻找通路的问题 摘 要 本课程设计主要解决设计一个迷宫以及在给出一组入口和出口的情况下，求出一条通路的问题。在课程设计中，系统开发平台为Windows 2000，程序设计语言采用Visual C+6.0，数据结构采用链式栈存储结构，程序运行平台为Windows 98/2000/XP。对于迷宫设计问题，首先假设了用“0”表示此道路可通，“1”表示不可通，即障碍，然后采用了简单的以时间产生随机种子（0，1变量）和人工输入0-1变量的方法产生迷宫矩阵。对求解迷宫通路问题，采用“穷举求解”的方法和设计一个“先进后出”的栈来存放当前位置路径，最后得出一条动态行走迷宫的通路。在程序设计中，采用了结构化与面向对象两种解决问题的方法。程序通过调试运行，初步实现了设计目标。 关键词 程序设计；C+6.0；链式栈存储结构；0-1；穷举求解 1 引 言本课程设计主要解决设计一个迷宫以及在给出入口和出口的情况下求解一条通路的问题。利用“穷举求解”的方法来判定当前位置是否可通以及利用栈“先进后出”的特点来存放当前位置可通的信息。1.1 课程设计目的在我们对一个具体的问题进行分析时，往往要抽象出一个模型，设计一个算法来实现所需要达到的功能。在此程序中，我们主要是综合运用所学过的知识，回顾VC+编程的同时，熟悉并掌握数据结构中的算法分析与设计。同时，要掌握类C语言的算法转换成C程序并上机调试的基础；通过本次课程设计，进一步巩固C语言和数据结构课程所学的知识，特别是加强数据结构的理解与运用，熟悉面向对象的程序设计方法；通过此次课程设计的实践，锻炼自身程序设计的能力以及用C语言解决实际问题的能力，为以后后续课程的学习以及走上社会打好基础。1.2 课程设计内容根据对题目的分析和设想，首先，设计一个链式栈存储结构，动态的对迷宫数据进行操作（主要为入栈和出栈）；其次，定义一个二维数组和一个备份数组，用于存放迷宫数据，并在构建迷宫中，要完成对手动建立迷宫和自动建立迷宫方法的设计，并能输出原始迷宫信息和原始图形信息；再次，当程序接受外部输入一组入口、出口数据后，能完成对该迷宫矩阵计算出是否存在通路的情况，若存在通路，则分别用坐标通路和图形通路输出该通路，否则输出无通路的信息；最后，设计完成实现多次输入入口和出口数据后，计算出不同结果的情况，并能分别显示出对应信息。1.3 概要设计计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解1。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。最后，以方阵、坐标和图形形式输出迷宫及其通路。 2 程序设计说明2.1 定义抽象数据类型1、设定迷宫的抽象数据类型为ADT maze 数据对象：D= ai，j 、，0=i=m+1,0=j=n+1,m,n=50 数据关系：R= ROW，COL ROW=| ai-1, j, ai，jD,i=1,m+1,j=0,n+1 COL=| ai，j-1 ,ai，j D,i=1,m+1,j=0,n+1基本操作： create(&mazeN+2,a,b)初始条件：二维数组mazea+2b+2已存在，其中自第1行至第a+1行、每行中自第1列至第b+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构造迷宫的0-1数组，以“0”表示通路，以“1”表示障碍，并在迷宫四周加上一圈障碍。prin(&mazeN+2,a,b) 初始条件：迷宫maze已被赋值。 操作结果：打印maze迷宫0-1矩阵以及图形矩阵，表示通路，表示障碍。 MazePath( &maze,x1,x2,y1,y2)初始条件：迷宫maze已被赋值。操作结果：从入口（x1,y1）开始，判定当前位置是否可通，可通就入栈并判断下一个方向是否可通 ，按具体情况做入栈和出栈处理，直到出口（x2,y2）为止。printonglu1() 初始条件：栈stack不空。 操作结果：出栈，得到一条从入口到出口的通路printonglu2(int a,int b)初始条件：迷宫maze已存在。操作结果：若迷宫maze中存在一条通路，则按照如下规定改变迷宫maze的状态；以字符、表示当前路径上往下一位置的方向，字符“”表示出口,打印迷宫矩阵。 ADT maze2.2 定义栈结构体及二维数组1、定义堆栈结构typedef struct node /堆栈结构int row; /行int col; /列struct node *next;Mlink;Mlink *stack;/定义一个栈 2、定义二维数组 int mazeM+2N+2;int backupM+2N+2; /备份数组2.3 主程序模块 main() 设置背景颜色； 输入矩阵的大小a,b; 建立矩阵； 备份矩阵； While(k!=0) 打印原始矩阵以及图形矩阵； 输入入口和出口位置； 判定有无通路； 输出结果； 输入k值，判定下一步的操作； 3 详细实现3.1 流程图 （1）主要设计思想流程如下3.1图所示：开始 设计栈结构体创建迷宫矩阵设计各种所需的函数设计main函数结束 图3.1 主要设计思想流程图 （2）详细设计流程图通过对本问题的分析与概括和程序的分析，可得出如下3.2图的详细设计程序流程图： 开始输入数组行列值建立迷宫矩阵并备份迷宫信息判断变量k是否为0打印迷宫矩阵原始信息输入入口和出口坐标信息判定MazePath值是否为1NY结束输出坐标通路以及图形通路输出无通路NY用局部备份数组信息还原迷宫矩阵和全局备份数组 图3.2 程序流程图3.2 算法说明该程序用于解决设计一个迷宫，并在此基础上给出一组入口和出口数据后能判定从该入口位置起是否有通路达到出口位置，有通路则输出坐标通路和图形通路两种方式，否则输出无通路的信息。本程序分两大模块，迷宫模块和主程序模块，迷宫模块又包括建立迷宫矩阵函数、输出迷宫矩阵原始信息函数、判断通路函数和输出最终信息函数（包括输出坐标通路函数和输出图形通路函数两种）五大函数，主程序模块主要为调用函数和while语句来判定是否重复执行操作。其中建立迷宫矩阵函数包括手动建立和自动建立两种功能，手动建立即人为的输入0-1数据，直至达到二维数组大小的要求，自动建立是利用时间来产生随机种子，从而建立满足大小的二维数组矩阵；输出迷宫矩阵原始信息函数的功能是首先输出带有行列号的0-1矩阵，再输出以表示通路，表示障碍的图形矩阵；判断通路函数首先判定由实参传递过来的入口坐标位置是否可通，然后再决定是否将其入栈，之后再执行后续操作，即若入口可通，则入栈，然后判定该位置的四方相邻的方向，若有一个方向的相邻位置可通，则将该相邻位置入栈，依次方法穷举求解下去，若能到达出口位置，最后将出口位置入栈并返回函数值“1”，否则返回函数值“0”；输出坐标通路函数的功能是若存在通路，则利用栈“先进后出”的特点输出从入口到出口的一条通路；输出图形通路函数的功能是若存在通路，利用栈中元素作比较，将栈中元素的信息和二维数组作比较，将二维数组对应位置上的图形改为、并输出。在主程序中，首先调用建立迷宫矩阵函数建立一个迷宫，然后用while语句来选择是否重复执行来求取不同通路。 3.3 主要算法设计（1）、结构体的定义 typedef struct node /堆栈结构int row; /行int col; /列struct node *next;Mlink;Mlink *stack;/定义一个栈 （2）、主要函数声明 void create(int mazeN+2,int a,int b)/建立迷宫 void prin(int mazeN+2,int a,int b) /打印迷宫矩阵int Mazepath(int mazeN+2,int x1,int x2,int y1,int y2)/判定迷宫通路void printonglu1() /输出坐标通路void printonglu2(int a,int b) /输出图形通路void main() /主函数 system(color f0); /背景为白色 int k=1,a,b; int mazeM+2N+2;/迷宫矩阵 int abcM+2N+2,p,q; /备份数组以重复使用迷宫 printf(建立迷宫!n); printf(输入迷宫矩阵的行列数M,N!n); scanf(%d%d,&a,&b); create(maze,a,b); /建立迷宫 for(p=0;p=a+2;p+) for(q=0;q=b+2;q+) abcpq=mazepq; while(k!=0) （3）、主要变量说明 M、N：预定义M和N的值，表示二维数组的大小； a、b：用于接收外部输入的值，按操作者意愿建立一定大小的迷宫； p:：栈指针，动态分配地址值； row、col：二维数组的行列值，分别接收变量a、b的值，使二维数组大小为mazeab； next：指向下一节点指针。4 运行环境与结果4.1 运行环境Microsoft Visual C+6.0。Visual C+(简称VC)是Microsoft公司推出的目前使用极为广泛的基于Windows平台的C+可视化开发环境。Visual C+6.0提出的控制台应用程序对学习和掌握标准的C/C+内容非常有利。“可视”的资源编辑器与MFC类以及应用程序向导，为快速高效的开发出功能强大的Windows应用程序提供了极大的方便。利用Visual C+6.0进行Internet、数据库及多媒体等多方面的程序开发也很容易2。4.2 运行过程中遇到的问题与处理方法在设计本程序之初，本人遇到的第一个问题就是如何建立一个迷宫矩阵，难道要手动的一个个输入数据吗？如果建立10阶以上的矩阵不是要输入100个以上的元素，这对现实来说是不可行的。经过翻查资料后，我才知道能利用时间产生随机种子，所用函数为srand(time()，再用i1=(int)(rand()%a)+1；j1=(int)(rand()%b)+1；mazei1j1=(int)(rand()%2)语句产生0-1变量，并且这种方法是经过验证的产生0元素较多的方法，即通过这种方法产生的迷宫矩阵有多条通路。基于这种方法和我们惯常的想法，我在编算法时提供了“手动建立”和“自动建立”两种方法来创建迷宫矩阵。随着程序设计的深入，我便遇到了第二个问题，与其说是问题，不如说是选择。在判定迷宫中是否存在通路时，要设计一个栈来存放数据，在选择用链式栈还是顺序栈之间我徘徊了很久，因为在网上我看到的类似算法中都是用顺序栈来实现迷宫通路的判定，进而构建了一些关于栈的相关算法，程序不仅显得冗长而且多了些不必要的操作，如判定栈是否空或满，而用链栈不仅不需要判定栈满，也只是涉及栈的入栈和出栈操作，程序简洁明了，因此我就废弃前人的成果自己另写了个算法，这对我来说确实是个挑战。之后虽然又遇到了几个问题，但都是小问题，一下就解决了，所以在此不再说明。4.3 运行结果与分析（1）、自动建立迷宫矩阵情形对程序进行编译运行后，窗口弹出如图4.1的信息： 图4.1 自动建立20*20迷宫矩阵这是在操作者输入矩阵的行列数M、N并选择功能键“2（自动建立）”后所显示的界面。当我们再按下键盘上的任意键后，界面就会显示如图4.2图4.3中的信息： 图4.2 自动建立20阶矩阵后的迷宫数字信息 图4.3自动建立20阶矩阵后的迷宫图形信息界面中在显示上示信息后并立刻弹出如下信息，如图4.4： 图4.4 等待输入入口和出口的运行界面在本次输入中，输入的一组数据如上图所示为入口（1/1）、出口（20/20），当输入完成后，按回车键，程序就进入到基于前面输入的数据判定迷宫中是否存在一条从入口到出口的通路，并在判定完成后显示如图4.5、4.6中的信息： 图4.5 存在通路时的坐标通路 图4.6 存在通路时的图形通路其中“输入0结束”表示在完成上述操作后，如果你从键盘上输入数字“0”，则此程序就会结束，相反，如果输入的是非0，则程序会跳转到如下图界面，对同一迷宫矩阵进行不同的判定。 图4.7 重新确定入口和出口数据界面此图中的信息不仅包含已经重新输入了迷宫入口（1、1）出口（17、4）的信息，更包含了在重新输入数据后完成对该迷宫矩阵的判定，次时判定为“无通路！” (2) 手动建立迷宫矩阵情形 当我们要建立的迷宫矩阵的阶数小于等于10时，我们可选择手动建立它，如图4.8就是其中的情形： 图4.8 选择手动建立迷宫的界面 如上图在我们选择了功能键“1”后，我们就要手动输入0或者1来建立迷宫矩阵，建立的迷宫矩阵信息如图4.9所示： 图4.9 手动建立迷宫的情形 输入完数据后，按回车键，就会显示如下相关信息，如图4.10所示 图4.10 手动建立后的迷宫的数字和图形矩阵 在显示完上示信息后，界面又会弹出如下信息给你输入入口和出口数据，如图4.11所示： 图4.11 等待输入入口和出口数据的运行界面 在上示界面中，当我们输入如上信息，入口（1、1），出口（10、8）后，程序立刻判定出结果“无通路”，之后“在输入0结束”的提示下，我输入“1”后，显示如下信息，如图4.12所示： 图4.12 再次进入等待输入入口和出口数据的界面 在这界面中，当输入入口（3、1）出口（10、8）数据后，经判定后显示如下信息，如图4.13、4.14所示： 图4.13 存在通路时的坐标通路 图4.14 存在通路时的图形通路 在显示上示信息后，根据“输入0结束”语句，我们可重复判定该迷宫的在不同入口，出口情形下的通路情况。在这我选择了“0”结束了程序的运行。5 结束语 通过本次课程设计使我意识到自身许多方面的不足以及让我学到了以前没有学过的知识，使我对课程设计有了更深层次的认识和理解，懂得了灵活运用；也让我意识到理论和实践想结合的重要性。在课程设计中，困难遇到过，也徘徊过，可是最终都被我一一解决了，我想说只要我们肯努力，愿意付出劳动，就能够得到属于我们自己所期望的东西，只要自己认真，敢于拼搏，勇于实践，我们就会有收获。 在此，我由衷的向我的指导老师 老师表示忠心的感谢，是她的悉心指导、严格要求和多次为我们细心的解疑和矫正，才使我的课程设计有了较为完善的一面，才使我有了能力的提高，并使我得到了充分的锻炼。参考文献1 严蔚敏，吴伟民数据结构（C语言版）. 北京：清华大学出版社，19972 郑阿奇，丁有和，郑进，周怡君Visual C+实用教程北京：电子工业出版社，2005，63 Stephen prata. C.Primer.Plus第五版.北京：北京邮电大学，20044 太平洋网站，/Info/38/Info15372/：2010-5-5附录：结构化设计源程序清单/程序名称：迷宫设计问题.cpp/程序功能：应用数据结构，采用C语言设计程序，实现迷宫的设计与判定通路/程序作者： /最后修改日期：2010/7/2#include#include#include#include#include#define M 50#define N 50typedef struct node /堆栈结构int row; /行int col; /列struct node *next;Mlink;Mlink *stack;/定义一个栈int backupM+2N+2; /备份数组/*建立迷宫矩阵*/void create(int mazeN+2,int a,int b)/建立迷宫int i,j,flag;srand(unsigned)time(NULL); /以时间产生随机种子for(i=0;i=a+1;i+)for(j=0;j=b+1;j+)mazeij=1;/将四周置为for(i=1;i=a;i+)for(j=1;j=b;j+)mazeij=0;/初始化矩阵backupij=0;/初始化备份矩阵printf(建立迷宫矩阵(选择或者)：n1,手动建立n2,自动建立n请输入您的选择：n);scanf(%d,&flag);if(flag=1)/手动建立迷宫printf(手动建立迷宫矩阵(0表示可通表示障碍):n);for(i=1;i=a;i+)for(j=1;j=b;j+)scanf(%d,&mazeij);if(flag=2) /自动建立迷宫int c,i1,j1;for(c=1;c=a*b;c+) /矩阵初始为“”，随机选择位置赋予一个随机的或， i1=(int)(rand()%a)+1;j1=(int)(rand()%b)+1;mazei1j1=(int)(rand()%2); /随机矩阵这样可以产生更多的“”即通路printf(自动生成中n);system (pause);for(i=1;i=a;i+)for(j=1;j=a;j+)backupij=mazeij;/备份数组矩阵/*打印迷宫矩阵*void prin(int mazeN+2,int a,int b)int i,j,z;printf(迷宫矩阵如下(0可通)：n );for(z=1;z=b;z+) /在矩阵上方标明列号if(z10) printf(%d ,z); else printf(%d ,z);for(i=1;i=a;i+)printf(n); if(i10) printf(%d ,i); /矩阵左方标明行号else printf(%d ,i);for(j=1;j=b;j+)printf(%d ,mazeij);printf(n迷宫图形如下(白色可通)：n);printf( );for(z=1;z=b;z+) /在图形上方标明列号if(z10) printf(%d ,z); else printf(%d,z);for(i=1;i=a;i+)printf(n);if(i10) printf(%d ,i); /矩阵左方标明行号else printf(%d,i);for(j=1;jrow=x1; p-col=y1; p-next=NULL; stack=p; /将入口放入堆栈 mazestack-rowstack-col=1;/标志入口已访问while(!(stack-row=NULL&stack-col=NULL)&(!(stack-row=x2&stack-col=y2)/未找到出口并且堆栈不空if(mazestack-row+1stack-col=0) /下面可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row+1;p-col=stack-col;p-next=stack; /入栈stack=p;mazestack-rowstack-col=1; /标记已访问else if(mazestack-rowstack-col+1=0) /右面位置可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row;p-col=stack-col+1;p-next=stack; /入栈stack=p;mazestack-rowstack-col=1;/标记已访问else if(mazestack-row-1stack-col=0) /左面可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row-1;p-col=stack-col;p-next=stack; /入栈stack=p;mazestack-rowstack-col=1;/标记已访问else if(mazestack-rowstack-col-1=0)/上面可通p=(Mlink *)malloc(sizeof(Mlink);p-row=stack-row;p-col=stack-col-1;p-next=stack; /入栈stack=p;mazestack-rowstack-col=1;/标记已访问else /不可通返回上一点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 printonglu1()Mlink *q;int i=1;printf(其中的一条通道为：n); q=stack; printf( 出口-); while (q!=NULL) if(i%5=0) printf(n); printf(%d%3drow,q-col); q=q-next; i+; printf(入口n);/*分割线*/*输出图形通路*/2时输出，时输出，时输出，时输出void printonglu2(int a,int b)printf(图形通路如下：n);int z;printf( );for(z=1;z=b;z+) /图形上方标明列号if(zrowp-col=6;while (p-next!=NULL)if(p-next-col!=NULL)if( p-row p-next-row ) backupp-next-rowp-next-col=5;/下一节点在下else if(p-rownext-ro