C语言迷宫的设计

摘 要
随着科技的日益发展,计算机信息知识越来越被人们所认知和使用,在当今知识爆炸的时代计算机毫不疑问成为人们常用的日常工具,对于一个经常使用
计算机的人来说,如何用好软件是一个很重要的问题,它对人们日常的很多操作有很大的帮助,对于一个技术人员,经常会接触到原代码,这就必须学会使用C语言，虽然现在大多数的软件的设计是通过其他高级语言以及采用系统集成软件编译，但它们的核心还是离不开使用C语言来构建，因此，简易迷宫程序的实现有利与在以后的开发项目中提供良好的思维方式。
关键词: C语言　迷宫  编译 think58.com

[资料来源：http://THINK58.com]

目  录

内容来自think58 [资料来源：http://www.THINK58.com]

[资料来源：http://THINK58.com]

摘 要
第一章　c语言迷宫的系统要求和分析
1.1系统要求
1.2系统要求分析
第二章　c语言迷宫功能模块结构
2.1功能模块划分
2.2各个模块的功能
第三章　主要模块的算法说明
3.1程序总体思路
3.2初始化迷宫数组函数
3.3寻找路径函数Path
3.4路径树的节点结构体
第四章  开发工具的介绍
4.1 Turbo C语言概述
4.2 C 语言的特点
4.3 Turbo C 概述
4.4 Turbo C 2.0的安装和启动
总结
致谢
参考文献
附录
附录A  c语言迷宫的使用说明
附录B  主要代码 think58 [来源：http://think58.com]

第一章、系统要求和分析
1.1系统要求
1.      随机产生一个固定大小的迷宫图（迷宫有唯一的一个入口，一个出口）；
2.      用图形的方式画出迷宫图；
3.      根据该迷宫图作出判断，迷宫又从入口到出口的路线；
4.      如果有路线的话，找到其中的一条路线，并画出来；
5.      用穷举的方法找出所有的路线，找到其中步数最少的路线。
1.2系统要求分析
1.      要求1，迷宫要随机生成，需要使用随机函数，不需要迷宫一定有解。
2.      要求3-5可以合并为一个要求，即：判断迷宫是否有路线，如果有的话要找到步数最少的路线并画出来。
3.      要求2主要体现在程序最后运行形式上，只要最后程序使用图形输出即可。
4.      综上，程序要求随机生成一个迷宫，判断是否有最短路径，最后将迷宫图形化输出。 copyright think58

二、功能模块结构
2.1功能模块划分
主要分为图形驱动，欢迎画面，初始化迷宫数组，寻找路径，输出迷宫图形，结束画面，图形结束七个模块。这些函数模块各成体系，互不干扰，是系统的主要功能模块。
2.2各个模块的功能
1.      图形驱动函数Init：负责图形界面驱动的初始化。
2.      开始画面函数Welcome：负责生成开始画面。
3.      初始化迷宫数组函数MazeCreat：负责随机生成一个只有一个出口和一个入口的迷宫。
4.      路径寻找函数Path：负责寻找已经生成的迷宫的路径，调用函数TreeCreat生成第一个节点，循环调用函数TreeGrow生成整个树。
其中需要调用：
创建路径搜索树的根节点函数TreeCreat：负责生成搜索树的第一个节点。
路径搜索树的生长函数TreeGrow：负责判断传递给这个函数的节点在四个方向是否可以生成节点，如果可以就调用函数TreeNewPoint生成新节点，并调用函数LeafGrow将新节点增加到待搜索节点中。
在路径搜索树中生成新的节点函数TreeNewPoint：负责在函数TreeGrow所传递来的方向上生成新节点。
搜索树叶子链表的创建与增加函数LeafGrow：负责将新节点增加到待搜索节点链表中。 think58好，好think58 [资料来源：http://think58.com]
5.      输出迷宫图形函数Draw：负责将迷宫用图形化界面输出。
6.      结束画面函数GameOver：负责生成结束画面。
7.      图形结束函数Close：负责程序结束后关闭图形界面驱动。 think58.com [资料来源：http://THINK58.com]

第三章　主要模块的算法说明
3.1程序总体思路
1.      用一个N×N二维数组代表迷宫，所有有关迷宫的操作都在这个二维数组上进行0。在这个数组中，1代表有墙，0代表可以走的路，9代表入口，2代表树已经延伸到的路，5代表最短路径。
2.      首先调用迷宫生成函数MazeCreat，生成一个随机的迷宫并记录在二维数组上0。
3.      然后调用Path函数查找迷宫路径。
4.      最后将迷宫用图形输出。
3.2初始化迷宫数组函数MazeCreat
1.      生成迷宫边框，随机选择出入口是在迷宫的上下两边还是左右两边，选择后随即把出入口分到迷宫相对的两条边上，包括出入口位置都随机生成，用inRow,inLine,outRow,outLine这四个变量记录出入口的坐标。
2.      随机生成迷宫内部，具体做法是对迷宫内部每一个点进行随机数判断，当满足条件时把这个点标志为围墙，否则把这个点标记为通路。
3.3寻找路径函数Path
1.      使用两个结构体（tree和leaf）来保存这个算法所需要的参数。
2.      由于入口的特殊性，首先调用TreeCreat()函数生成路径搜索树的第一个节点，即树根，并把这个结构体的指针返回。

内容来自think58 [资料来源：http://THINK58.com]

3.      树根作为第一个节点进入TreeGrow函数，TreeGrow函数判断出第一次生长的方向（有且只有一个方向）并调用函数TreeNewPoint在这个方向上生成新节点，并调用函数LeafGrow将这个新节点增加到待搜索节点链表中。
4.      用指针leafHeadOld指向当前需要判断的节点链表，用指针以leafHeadNow指向下一轮判断中需要判断的节点链表。通过判断待搜索节点链表是否为空来控制循环，当链表为空时说明路径搜索树在上一轮生长过程中没有生长，即已经搜索完迷宫内所有可以到达的节点。
5.      函数TreeNewPoint会在每一次调用时判断新节点是否是出口，如果是将记录出口的结构体的指针赋值给outPoint。在整个路径搜索树生成后，如果outPoint不为初始值NULL说明有路，从出口倒推到入口并将经过的每个迷宫点的值标记为5。
6.      因为路径搜索树每次增长都要在所有分支上增长一个节点，故从树根到各个末端所走的路程是相同的，而且只有一个分支可以走到出口，而这条就是最短路径。
7.      TreeCreat的功能是：开辟一个连续的内存空间给结构体tree，然后根据入口坐标判断出唯一的前进方向并在结构体中标志其方向信息为0，不能前进的方向标志为3，最后将这个内存空间的指针返回。 copyright think58

[资料来源：http://THINK58.com]

TreeGrow的功能是：依次判断传递给这个函数的节点的四个方向，如果这个方向可以通行就调用函数TreeNewPoint生成新节点，并把指向新节点的指针传递给函数LeafGrow。
TreeNewPoint的功能是：根据函数TreeGrow传递来的方向生成新节点，并TreeGrow传递来父节点指针赋值给新节点的father。
LeafGrow的功能是：将函数TreeNewPoint传递来的新节点的指针加入到链表中，如果链表为空则创建链表。 think58.com

[来源：http://www.think58.com]

3.4 路径树的节点结构体
struct tree
  {int row;  /*用于记录该节点的行坐标*/
   int line;  /*用于记录该节点的列坐标*/
   int infoUp;    /*用于记录各个方向的属性*/
   int infoDown;  /*初始值为0，父节点方向为1*/
   int infoLeft;   /*有下一个节点为2*/
   int infoRight; /*没有下一个节点为3*/
   struct tree *father;    /*用于指向其父节点，初始值为NULL*/
  };
各个结构体成员的用途：
1)      每个点的坐标（int row, int line；用来表示这个点的坐标）；
2)      各个方向的属性（int infoUP, int infoDown, int infoLeft,int infoRigh；用来记录该节点在四个方向的情况，初始值为0，父节点方向为1，有下一个节点为2，没有下一个节点为3）；
3)      指向父节点的指针（struct tree *father；用来指向父节点，以便在完成整个迷宫路径搜索后倒推出最短路径）。
最后这个结构体各节点构成的是一个树，这个树除了根节点外每个节点都有一个指向其父节点的指针。而这棵树的所有节点将遍布从出口开始迷宫内可以到达每一个节点，最后通过出口处的节点向上遍历到根节点完成最短路径的标记。 内容来自think58 [资料来源：http://think58.com]
待搜索节点结构体
struct leaf
  {struct tree *point; /*指向新的树节点的指针*/
   struct leaf *next;  /*指向链表下一个节点的指针*/
  };/*待搜索节点的链表*/
结构体成员的用途：
1)      处于同一路径长度的路径树一个节点的指针（struct tree *point）；
2)      链表下一个节点的指针（struct leaf *next）；
最后这个结构体的各个节点将构成一个链表，路径长度每增长一次将创建一个新的链表以存储处于同一路径长度的路径树的节点的指针。而路径数的增长将挨个判断（调用TreeGrow函数）上一次存储的处于同一路径长度的路径树节点。

think58.com

[版权所有：http://think58.com]

 

本文来自think58

[版权所有：http://think58.com]