数据结构课程设计报告

湖北工业大学。

数据结构及应用课程设计。

题目：求解迷宫问题

学院理学院。

专业班级：电子信息科学与技术11电科1

姓名姚思琪

学号： 1111121133

指导教师：杨晓艳

成绩。目录。

课程设计目的 3

迷宫问题的提出与分析 4

正文 5一、采用c++语言定义相关的数据类型 5

二、各模块的算法分析 6

三、程序流程图 9

四、程序调试结果。

1、程序的初始欢迎界面调试结果 10

2、迷宫的创建10

3、迷宫路径的输出11

4、无路径时的输出12

程序设计心得 13

参考文献 14

附录 15源程序（带注释） 15

一、课程设计的目的。

本程序主要是对任意给定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。

1、生成迷宫：根据提示输入数据，然后生成一个m行n列的迷宫。

2、探索迷宫路径：由输入的入口位置开始，对相邻的（上，下，左，右）四个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通道块”，朝着“来向”之外的其它方向继续探索。

3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后弹出路径坐标，输出在屏幕上。

关键字：栈，栈的存储结构，出栈与入栈，递归。

2、迷宫问题的提出与分析。

迷宫问题最早出现在古希腊神话中。据说，半人半神的英雄西修斯在克里特的迷宫中勇敢地杀死半人半牛的怪物，并循着绳索掏出迷宫。希腊史学家希罗多德曾探访过那里。

他描述说，整个迷宫由12座带顶院落构成，所有院落都由通道连接，形成3000个独立的室。后来的参观者也说，一旦进入迷宫，如果没有向导，根本无望走出。尽管人们并不清楚迷宫的具体情况，人类的聪明之处，就在于可以对走过的地方进行标记，遇到死胡同则返回到上一个标记的位置选择另一个方向进行搜索，这种方法被称为回溯法。

回溯法的思想是：对一个包含多个分支打节点，按照一定的顺序向分支节点搜索；当发现某个支点没有分支时，就回溯退回到该节点的上一个节点，继续搜索这个节点的其他尚未搜索过的分支。这样的搜索过程一直继续到搜索到有解或搜索完所有可能的分支而没有解为止。

下面对迷宫问题进行分析求解：

在迷宫中用1和0分别表示迷宫中的通路和障碍。首先，输入迷宫数据，在计算机的屏幕上显示一个m行n列的矩阵表示迷宫。矩阵中的每个数据或为通路（以0表示），或为墙（以1表示），所求路径必须是简单路径，即在求得的路径上不能重复出现同一道块。

其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳入当前路径”，并继续朝“下一个位置”探索，即切换“下一位置”为“当前位置”，如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置”指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈s记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。

由此，“纳入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。

最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径图。

#include<>

#define maxsize 100

#define null 0

typedef struct定义迷宫。

int maze[maxsize][maxsize]; 二维数组存放迷宫信息。

int maze_x,maze_y迷宫的行数和列数。

maze;maze a;

typedef struct point栈链的每个节点定义。

int vex_x,vex_y节点的横纵坐标

int direction下一个节点的方向。

struct point *next指向下一个节点。

point;

二、各模块的算法分析。

1、创建一个二维数组存放迷宫行列数信息，初始化迷宫。

maze creat初始化迷宫迷宫。

int i,j;

maze a;

printf(“请输入迷宫的行数和列数：")

scanf("%d%d",&

for(i=1;i<=

return a;

2、迷宫路径输出的实现。

void printmazepath(point *p,maze road)

int i,j迷宫路径的输出实现。

char m[maxsize][maxsize];

printf("迷宫路径图示如下：");

for(i=1;i<=

for(j=1;j<=

while(p)

p=p->next;

for(i=1;i<=

for(j=1;j<=

break;

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了