迷宫求解课程设计(含引言、需求分析、伪代码、数据结构、代码分析、附录)

引言

数据结构是一门理论性很强、思维抽象、难度较大的课程，是基

础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程

序设计语言、离散数学等，后续课程有操作系统、编译原理、数

据库原理、软件工程等。通过本门课程的学习，我们应该能透彻

地理解各种数据对象的特点，学会数据的组织方法和实现方法，

并进一步培养良好的程序设计能力和解决实际问题的能力，而且

该课程的研究方法对我们学生在学校和离校后的工作和学习，也

有重要意义。数据结构是电子信息科学与技术专业的一门核心专

业基础课程，在该专业的课程体系中起着承上启下的作用，学好

了数据结构对于提高理论认知水平和实践能力有着极为重要的

作用。学习数据结构的最终目的是为了获得求解问题问能力。对

于现实世界中的问题，应该能从中抽象出一个适当的数学模型，

该数学模型在计算机内部的数据结构来表示，然后设计一个解此

数学模型的算法，在进行编程调试，最后活的问题的解答。

基于此原因，现在我们开设数据结构课程设计。针对数据结构课

程的特点，着眼于培养我们的实践能力。实习课程是为了加强编

程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结

构课程实践，无论是理论知识，还是动手能力，同学们都会有不

同程度的提高。

一、需求分析

本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向

前探索，若能走通，则继续往前走；否则沿原路退回，换一个方

向再继续探索，直至所有可能的通路都探索到为止。为了保证在

任何位置上都能沿原路退回，显然需要用一个后进先出的结构来

保存从入口到当前位置的路径。因此，在求迷宫通路的算法中要

应用“栈”的思想假设“当前位置”指的是“在搜索过程中的某

一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的

基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续

朝“下一位置”探索，即切换“下一位置”为“当前位置”，如

此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”

退回到“前一通道块”，然后朝着除“来向”之外的其他方向继

续探索；若该通道块的四周4个方块均“不可通”，则应从“当

前路径”上删除该通道块。所谓“下一位置”指的是当前位置四

周4个方向（上、下、左、右）上相邻的方块。假设以栈记录“当

前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由

此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上

删除前一通道块”的操作即为“出栈”。

二、数据结构

1. 数据结构设计考虑

1) 建立一个二维数组表示迷宫的路径（0表示通道，1表示墙壁）；

2) 创建一个栈，用来存储“当前路径”，即“在搜索过程中某一

时刻所在图中某个方块位置”。

2. 逻辑结构存储结构

1) 创建一个Int类型的二维数组int maze[n1][n2],用来存放0

和1 （0表示通道，1表示墙壁）；

2) 创建一个结构体用来储存数组信息(数组的横坐标X，数组的

纵坐标Y，方向C)结构体：

typedef struct node

{

int x;

int y;

int c;

}linkstack;

3) 创造一个栈包括(top表示栈顶元素)

linkstack top[n1*n2];

三、算法设计

首先，创建数组的大小，此数组大小要求用户自己输入。具体算

法：

printf("输入迷宫大小(提示:行列数不能超过

50!):"); //在此提示用户输入数组大小的界限

scanf("%d",&g); //再次用scanf来输入使用者要

创建的迷宫大小，并且把值赋给g这个参量，用于对与迷宫数组

的创建

printf("大小创建完毕,请输入迷宫:\n"); //用来提示用

户要进行下面操作

其次，用户自己定义迷宫的内容(其中自定义迷宫入口(1,0),迷

宫的出口为(g-2、h-1)),迷宫的生成算法：

void shuzu(int g,int h){ //创建数组函数,设定

参量并从主函数中获得要使用的参量

int a,b;

for(a=0;a<g;a++)

for(b=0;b<h;b++)

scanf("%d",&maze[a][b]);

} //使用循环来给数组赋值，也就是用来创建

迷宫的格式，这是一个自定义的迷宫创建，其中的0和1分别是

表示通路和障碍，定义的数组其实就是迷宫的设计图

第三，产生迷宫(其中自定义迷宫入口(1,0),迷宫的出口为(g-2、

h-1))，算法：

void scsu(int g,int h){ //创建迷宫输出函数,设

定参量并从主函数中获得要使用的参量

int a,b;

printf("生成的迷宫是:\n"); //提示要现实

的内容是什么

for(a=0;a<g;a++)

{ for(b=0;b<h;b++)

printf(maze[a][b]?"#":" ");

printf("\n"); //使用循环语句来实

现迷宫的实化，输出迷宫

}

}

最后，迷宫寻路，在寻路的时候，我们应从入口(1、0)进入迷宫，

当迷宫的入口处有障碍或者出口被堵，再或者没有通路时整个程

序结束，并输出迷宫无解的提示。如果迷宫求解过程中没有出现

无解情况，那么在 …… 此处隐藏：4231字，全部文档内容请下载后查看。喜欢就下载吧 ……