课 程 设 计 报 告
学生姓名:
学 号:
学 院 :
理学院
班 级 :
题 目 : 漫步迷宫
指导教师: 职称:
年 月 日
目 录
目 录.........................................................................................................................2
一、选题背景..........................................................................................................1
1.1 解决的主要问题和达到的技术要求......................................................1
1.2 指导思想.....................................................................................................1
随机生成一个矩阵,这个矩阵根据实际情况输入一个文件中,然后把该文
件导入程序中,可以随意的选着出口和入口,通过搜索,把出口和入口之间
的所有路径选择出来,通过比较选择出最短的路径。最后显示出具体的矩阵
位置。......................................................................................................................1
二、算法设计..........................................................................................................2
2.1 设计原理及方案选择.................................................................................2
2.2 方案的特点.................................................................................................2
3.1 程序总体概述.............................................................................................3
3.2 创建一个简易的栈.....................................................................................4
3.3 创建迷宫矩阵.............................................................................................4
3.4 找到一条最短通路.....................................................................................4
3.5 程序调用关系.............................................................................................5
3.6 程序运行.....................................................................................................6
4.1 示例 1..........................................................................................................6
4.2 示例 2..........................................................................................................7
4.3 示例 3..........................................................................................................7
六、课程设计心得体会........................................................................................10
参考文献................................................................................................................11
源程序....................................................................................................................12
2
一、选题背景
1.1 解决的主要问题和达到的技术要求
主要可以解决数学建模中两地有多条通路,怎么选择一条路,使这条路
的里程最短,或者根本没有路。
迷宫的规格(即行数与列数),状态设置(即各方格能否通行的状态),
以及入口和出口的位置,均可以由输入随机确定。求得的最短路径,可以以
从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时,可
以报告无路径的信息。采用结构化程序设计方法,对各个模块的功能及参数
作必要的说明。
1.2 指导思想
随机生成一个矩阵,这个矩阵根据实际情况输入一个文件中,然后把该
文件导入程序中,可以随意的选着出口和入口,通过搜索,把出口和入口之
间的所有路径选择出来,通过比较选择出最短的路径。最后显示出具体的矩
阵位置。
1
二、算法设计
2.1 设计原理及方案选择
首先从文件中读入迷宫矩阵,在这儿设计到文件数据的读写。
接着要从出口和入口选择出最短的路径。从初始点开始出发,开始想四
周“探测”,如果能够到达,那么把这个位置存入到一个设定的数据栈中,然
后以到达的位置开始,重新探测,如此循环下去。如果最后能够到达出口位
置,那么输出走出的轨迹,否则,不能够到达。
在这个程序的设计当中,我们力求程序的简洁、简单、方便、逻辑的清
晰。为了方便演示,我们采用了从文本中读入数据,给出了几个运行示例。
考虑到工作量的原因,我们不可能做到规模很大,因此消减了一些非核心功
能,比如未做 GUI 界面。
2.2 方案的特点
1、思路清晰,简洁。
2、符合我们的日常生活逻辑习惯。
3、充分的利用了数据结构的知识,包括栈的使用,活学活用。
2
三、程序及功能说明
3.1 程序总体概述
对于一个 m n 的迷宫矩阵,其中 0 位置表示可以到达的位置,1 表示
不能到达的位置。首先从文件中输入一个迷宫矩阵,然后设置一个栈,从出
发位置开始,依次按右、下、左、上的次序进行试探,如果能够到达,即迷
宫矩阵的值为 0,那个这个位置进行入栈操作。如果都不能进行到达,那么
这个位置进行出栈操作,亦即退回到前一个位置。如此进行循环,直到到达
出迷宫位置。如果不能够出迷宫,那么输出信息,否则把出迷宫的路径输出。
开始
打开指定文件,读取
数据到迷宫矩阵
输出迷宫矩阵
输入起始位置和终点位置
创建一个栈
依次按序检验右、下、左、上,
找出能到达的位置
越 界 , 或
不 能 到 达
出点
输出栈中存储的通路
输出不可到达信息
结束
3