2024年4月14日发(作者：)

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同程度的提高。

一、 需求分析

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

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

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

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

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

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

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

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

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

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

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

探索;若该通道块的四周 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 来输入使用者要

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

的创建

printf ( ”大小创建完毕，请输入迷宫 ； //用来提

示用户要进行下面操作

其次,用户自己定义迷宫的内容 (其中自定义迷宫入口(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++)

％d”， ＆maze[a] [b])；