资源描述：
《迷宫设计论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1引言本课程设计主要解决设计一个迷宫以及在给出入口和出口的情况下求解-条通路的问题。利用“穷举求解”的方法來判定当前位置是否可通以及利用栈“先进后岀”的特点来存放当前位置可通的信息。1.1课程设计目的在我们对一个具休的问题进行分析时，往往要抽象出一个模型，设计一个算法来实现所需要达到的功能。在此程序中，我们主要是综合运用所学过的知识，冋顾VC++编程的同时，熟悉并掌握数据结构中的算法分析与设计。同时，要掌握类C语言的算法转换成C程序并上机调试的基础；通过本次课程设计，进一步巩固《C语言》和《数据结构》课程所
2、学的知识，特别是加强数据结构的理解与运用，熟悉面向对彖的程序设计方法；通过此次课程设计的实践，锻炼自身程序设计的能力以及用c语言解决实际问题的能力，为以后后续课程的学习以及走上社会打好基础。1.2课程设计内容根据对题目的分析和设想，首先，设计一个链式栈存储结构，动态的对迷宫数据进行操作（主要为入栈和出栈）；其次，定义一个二维数组和一个备份数组，用于存放迷宫数据，并在构建迷宫屮，要完成对手动建立迷宫和自动建立迷宫方法的设计，并能输出原始迷宫信息和原始图形信息；再次，当程序接受外部输入一组入口、出口数据后，能完
3、成对该迷宫矩阵计算出是否存在通路的情况，若存在通路，则分别用坐标通路和图形通路输出该通路，否则输出无通路的信息；最后，设计完成实现多次输入入口和出口数据后，计算出不同结果的情况，并能分别显示出对应信息。1.3概要设计计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退冋，换一个方向继续探索,直至出口位置，求得-•条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解⑴。可以用二维数组存储迷宫数据，通常设定入口点的下标为(1,1
4、),出口点的下标为(n,n)o为处理方便起见，可以迷宫的四周加一•圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。最后，以方阵、坐标和图形形式输出迷宫及其通路。2程序设计说明2.1定义抽象数据类型1、设定迷宫的抽象数据类型为ADTmaze{数据对象：D二{a.i,jG{C'■、'L、'一、'!'、},0<=i<=m+l,0<=j<=n+l,m,n<=50}数据关系:R={ROW,COL}R0W={
5、ai-1,j,ai,jwD,i=l,,m+1,j=0,n+1}COL
6、={
7、ai,j-1,ai,jGD,i=l,,m+1,j=0,n+1}基木操作：create(&maze[][N+2],a,b)初始条件:二维数组maze[a4-2][b+2]已存在,其中自第1行至第a+l行、每行中门第1列至第b+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构造迷宫的0-1数组，以“0”表示通路，以“1”表示障碍，并在迷宫四周加上一圈障碍。prin(&maze[][N+2],a,b)初始条件：迷宫maze已被赋值。操作结果：打卬maze迷宫0-1
8、矩阵以及图形矩阵，'□'表示通路，'■‘表示障碍。MazcPath(&maze,xl,x2,yl,y2)初始条件：迷宫maze已被赋值。操作结果：从入口(xl,yl)开始，判定当前位置是否可通，可通就入栈并判断下一个方向是否可通，按具体情况做入栈和出栈处理，直到出口(x2,y2)为止。printonglul()初始条件：栈stack不空。操作结果：出栈，得到一条从入口到出口的通路printonglu2(int3,intb)初始条件：迷宫H13ZC已存在。操作结果：若迷宫H13ZC中存在一条通路，则按照如下规
9、定改变迷宫maze的状态；以字符'f'、'一'、—''('、表示当前路径上往卜•一位置的方向，字符“阳”表示出口，打印迷宫矩阵。}ADTmaze2.2定义栈结构体及二维数组1、定义堆栈结构typedefstructnode〃堆栈结构{introw;〃行intcol;〃列structnode*next;}Mlink;Mlink*stack;//定义一个栈2、定义二维数组intmaze[M+2][N+2];intbackup[M+2][N+2];〃备份数组2.3主程序模块main(){设置背景颜色；输入矩阵的大
10、小a,b;建立矩阵；备份矩阵；While(k!=0)｛打卬原始矩阵以及图形矩阵；输入入口和岀口位置；判定有无通路；输出结果;输入k值，判定下一步的操作;3详细实现3.1流程图(1)主耍设计思想流程如下3.1图所示:(2)详细设计流程图通过对木问题的分析与概括和程序的分析，可得出如下3.2图的详细设计程序流程图:图3.2程序流程图3.2算法说明该程序用于解决设计一个迷宫，并在此基础上给出一组入口和出口数据后能判定从
