数据结构C语言迷宫课程设计报告

迷宫

课程设计

4星 · 超过85%的资源需积分: 50 44 浏览量更新于2023-03-16 评论 4 收藏 137KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

北京化工大学

课程设计报告

课程名称数据结构课程设计

设计题目迷宫问题（栈）

专业、班级计算机科学与技术

班

学号

姓名

指导教师

设计时间

年月日

一、引言（简要说明设计题目的目的、意义、内容、主要任务等）

目的及意义：

迷宫问题是取自心理学的一个实验。通过运用 C 语言对迷宫的设计和求解，更好的掌握链

栈的定义、操作和应用；掌握结构体数组的定义、操作和应用；了解建立迷宫问题数学模型的

方法。同时让我们通过对迷宫的求解，更好的理解数据结构中的“穷举求解”算法，理论和实践相

结合，提高我们的兴趣的同时，增加我们对栈的应用理解和“穷举求解”算法的应用。

内容：

利用 C 语言编写一个随机的迷宫。首先进入菜单进行选择：

1. 随机生成迷宫；

2. 随机生成有通路的迷宫；

3. 随机生成有通路的迷宫并求解；

4. 手动求解迷宫；

0. 退出。

随机生成迷宫是利用随机函数 srand((unsigned) time(NULL))对创建的二维结构体数组中

的点进行随机分布。每个点利用随机数%3 产生出来的只有 0、1、2 三个数字，其中将 0 设置

为墙，1、2 设置为通路。再将整个二维矩阵利用双层 for 循环打印显示出来，就生成了随机迷

宫。

随机生成有通路的迷宫也是利用随机函数 srand((unsigned) time(NULL))产生 0 到 9 十

个随机数，通过产生的随机数来定义墙或者通路，生成一个二维随机迷宫，先对该生成迷宫进

行求解，如果求解成功则将此迷宫打印输出，如果求解不成功，则执行循环，直到求解出有通

路的迷宫为止。

手动求解迷宫则是利用手动输入坐标，来标记迷宫中的通路点，从而找到迷宫的通路。当

输入坐标点为通路时会提示你输入下一个相邻坐标点，当输入坐标点不为通路时或者与上一座

标点不相邻时，系统会视为非法坐标，让用户重新输入，直到找到迷宫出口时，会自动打印输

入用户输入的坐标点通路。如果用户无法找到迷宫通路，可以通过输入-1,-1 坐标来退出。

对于迷宫的求解，采用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若

能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条

通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。“穷举求解”方法

利用 do{}while()循环来对迷宫进行向下遍历搜索，将可通过的合法路径压入栈中，沿着此合

法路径的一个方向进行搜索，当进入死胡同时，则执行退栈操作，继续沿该合法点的剩余方向

进行探索，如若该点所有方向均搜索完毕，则再次执行退栈操作，继续沿剩余新退出栈的点的

剩余方向进行向下搜索，如此循环下去，直到栈为空，则退出 do{}while()循环，完成迷宫的

求解。

主要任务：

<1>用 C 语言编写程序可以随机生成二维迷宫；

<2>用 C 语言编写程序可以随机生成二维有通路的迷宫；

<3>用“穷举求解”方法求解随机生成二维有通路的迷宫；

<4>实现手动输入坐标法求解随机生成二维有通路的迷宫；

<5>实现能在手动输入时打断输入退出以及每项功能执行完毕后清屏任务。

二、正文（课程设计的主要内容，包括实验与观测方法和结果、仪器设备、计算方法、编

程原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正

文内容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严

谨，符合各学科、专业的有关要求。）

(1) 课程设计题目：C 语言编写迷宫问题（栈）。

(2) 设计要求：

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求

得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d 表示走到

下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（ 1，1，1），

（1，2，2）， (3，2，3)，(3，1，2)，…。

(3) 结构功能描述：

① 存储结构：

首先建立存储结，根据题目要求存储结构要求为链栈。

声明一个链栈：

typedef struct linknode

{

ElementUnit data; //数据域

struct linknode *next; //指针域

}LiStack;

该链栈包含两个部分，一个数据域，一个指针域；也就是说这个链栈中的每个数据

都分成两个部分，一部分存放的是数据，另一部分则存放的下一个数据的地址，即指

针。对于链栈的应用，我们只是掌握头节点的信息，后面的数据的存储位置都有其上

一个数据所确定，而且每次都只能取栈顶元素，要满足栈的先进后出的性质。

② 迷宫结构

一个迷宫是由一个二维矩阵构成的，这样构建迷宫就转变成为了构建一个二维矩阵的数

学问题。而构建一个二维矩阵首先要确定矩阵的存储结构，即二维结构体数组的存储

结构，该存储结构中的每个元素要包含二维坐标 x,y，还有下一个坐标的方向 di，该点

是否是通路 pass，该点是否要标记为求解通路的路径 foot。

typedef struct PositionUnit

{

int x;//横坐标

int y;//纵坐标

}PositionUnit;

二维矩阵每个元素单元的二维平面基本属性定义。二维矩阵的每个点由横、纵坐标

组成。

typedef struct ElementUnit

{

剩余11页未读，继续阅读

lgmltz

2015-05-25

关于使用穷举法求解的，用链栈作为存储结构，不怎么实用

masonzry

粉丝: 1
资源: 2

会员权益专享

数据结构C语言迷宫课程设计报告

评论1

会员权益专享

最新资源

数据结构C语言迷宫课程设计报告

评论1

回溯法求解走迷宫问题（八个方向）

数据结构课程设计——迷宫问题

C例子：走迷宫（C语言实现）

数据结构c语言版课程设计走迷宫

数据结构c语言迷宫求解问题课程设计

c语言迷宫问题数据结构课程设计

数据结构C语言版课程设计学生信息管理系统

c语言课程设计报告之迷宫,C语言课程设计-迷宫游戏

迷宫小游戏数据结构c语言

数据结构c语言版迷宫代码

数据结构c语言版慕课

数据结构c语言版专升本习题

东北大学数据结构c语言实验

数据结构c语言版电子书

c语言数据结构迷宫问题

全局数据结构 c语言

c语言程序课程设计单机游戏

数据结构c语言习题讲解

清华大学数据结构c语言代码

数据结构c语言版随书光盘

会员权益专享

最新资源