数据结构课设--迷宫

数据结构课设--迷宫

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计 课程设计题目：迷宫算法

院（系）：计算机学院 专 业：计算机科学与技术 班 级：84010103 学 号：2008040101061 姓 名： 李雪城 指导教师： 丁一军

数据结构课设--迷宫

沈阳航空航天大学课程设计报告

目 录

1 课程设计介绍 ............................................................................................................ 2 1.1 课程设计内容 ....................................................................................................... 2 1.2 课程设计要求 ....................................................................................................... 2 2 课程设计原理 ............................................................................................................ 2 2.1 课设题目粗略分析 ............................................................................................... 2 2.1.1迷宫的建立 .................................................................................................... 2 2.1.2迷宫的存储 .................................................................................................... 2 2.1.3迷宫路径的搜索 ............................................................................................ 2 2.2 原理图介绍 ........................................................................................................... 3 2.2.1功能模块图 .................................................................................................... 3 2.2.2 流程图分析 ................................................................................................... 3 3 数据结构分析 ............................................................................................................ 5 3.1概要设计 ................................................................................................................ 5 3.1.1 本程序设计思路 ........................................................................................... 5 3.1.2 本程序包含的函数 ....................................................................................... 5 3.2 详细设计 ............................................................................................................... 5 3.2.1节点类型和指针类型 .................................................................................... 5 3.2.2 迷宫的操作 ................................................................................................... 5 3.2.3输出结果 ........................................................................................................ 7 4 调试与分析 ................................................................................................................ 8 4.1 调试分析 ............................................................................................................... 8 4.2 测试结果 ............................................................................................................. 8 4.2.1当输入的行列数超过预设范围 .................................................................... 8 4.2.2当输入的行列数未超过预设范围 ................................................................ 9 参考文献 ........................................................................................................................ 10 附 录（关键部分程序清单） ................................................................................... 11

数据结构课设--迷宫

1 课程设计介绍

1.1 课程设计内容

编写算法能够生成迷宫，并求解迷宫的路径（求解出任意一条到出口的路径即可）。迷宫有上下左右四个方向的走法。

1.2 课程设计要求

1．不必演示求解过程，只需输出迷宫求解的路径。 2．参考相应的资料，独立完成课程设计任务。 3．交规范课程设计报告和软件代码。

2 课程设计原理

2.1 课设题目粗略分析

2.1.1迷宫的建立

迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 2.1.2迷宫的存储

迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。其中M，N分别表示迷宫最大行、列数，本程序M、N的最大值为39、39，当然，也可根据需要调整其大小。 2.1.3迷宫路径的搜索

首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路

数据结构课设--迷宫

径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，

且未找到通往出口的路径，则表明不存在从入口到出口的路径。根据这种算法可以找到路径。

2.2 原理图介绍

2.2.1功能模块图

图2.2.1 功能模块图

如图2.2.1所示，功能模块图。

2.2.2 流程图分析

数据结构课设--迷宫

图2.2.2迷宫路径算法流程图

如图2.2.2所示,迷宫路径算法流程图。

数据结构课设--迷宫

3 数据结构分析

3.1概要设计

3.1.1 本程序设计思路

(1)构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵 (2)生成迷宫，即为二维数组maze[M+2][N+2]赋值 (3)构建一个队列用于存储迷宫路径

(4)建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况 (5)实现搜索算法 (6)屏幕上显示操作过程 3.1.2 本程序包含的函数 (1)主函数 main()

(2)生成迷宫函数 s_maze() (3)将迷宫打印成图形 print_maze()

(4)打印迷宫路径 (若存在路径) result_maze() (5)入队 enqueue() (6)出队 dequeue()

(7)判断队列是否为空 is_empty() (8)访问节点 visit() (9)搜索迷宫路径 mazepath()

3.2 详细设计

3.2.1节点类型和指针类型

迷宫矩阵类型：int maze[M+2][N+2];为方便操作使其为全局变量

迷宫中节点类型及队列类型：struct point{int row,col,predecessor} queue[512] 3.2.2 迷宫的操作

(1)生成迷宫

void s_maze(int m,int n){ 定义i,j为循环变量

数据结构课设--迷宫

for(i<=m) for(j<=n)

输入maze[i][j]的值 }

(2)打印迷宫图形

void print_maze(int m,int n)

{用i,j循环变量，将maze[i][j]输出 □、■} (3)打印迷宫路径

void result_maze(int m,int n)

{用i,j循环变量，将maze[i][j]输出 □、■、☆} (4)搜索迷宫路径

①迷宫中队列入队操作

void enqueue(struct point p) { 将p放入队尾，tail++} ②迷宫中队列出队操作

struct point dequeue(struct point p) { head++,返回que[head-1]} ③判断队列是否为空

int is_empty()

{ 返回head==tail的值，当队列为空时，返回0} ④访问迷宫矩阵中节点

void visit(int row,int col,int maze[41][41]) {建立新的队列节点

visit_point,将其值分别赋为

row,col,head-1,maze[row][col]=2,表示该节点以被访问过;调用enqueue(visit_point),将该节点入队} ⑤路径求解

void mazepath(int maze[41][41],int m,int n)

{ 先定义入口节点为struct point p={0,0,-1},从maze[0][0]开始访问。如果入口处即为障碍，则此迷宫无解，返回0 ，程序结束。否则访问入口节点，

数据结构课设--迷宫

将入口节点标记为访问过maze[p.row][p.col]=2,调用函数enqueue(p)将该节点入队。

判断队列是否为空，当队列不为空时，则运行以下操作： { 调用dequeue()函数，将队头元素返回给p，

如果p.row==m-1且p.col==n-1,即到达出口节点，即找到了路径，结束

如果p.col+1<n且maze[p.row][p.col+1]==0,说明未到迷宫右边界，

且其右方有通路,则visit(p.row,p.col+1,maze),将右边节点入队标记已访问

如果p.row+1<m且maze[p.row+1][p.col]==0,说明未到迷宫下边界，

且其下方有通路,则visit(p.row+1,p.col,maze),将下方节点入队标记已访问

如果p.row-1>0且maze[p.row-1][p.col]==0,说明未到迷宫上边界，

且其上方有通路,则visit(p.row,p.col+1,maze),将上方节点入队标记已访问

如果p.col-1>0且maze[p.row][p.col-1]==0,说明未到迷宫左边界，

且其左方有通路,则visit(p.row,p.col-1,maze),将左方节点入队标记已访问 }

访问到出口(找到路径)即p.row==m-1且p.col==n-1,则逆序将路径标记为3即maze[p.row][p.col]==3;

while(p.predecessor!=-1)

{p=queue[p.predecessor]; maze[p.row][p.col]==3;}

最后将路径图形打印出来。 3.2.3输出结果

请输入行列数(如果超出预设范围则提示重新输入)

s_maze(m,n);

print_maze(m,n); mazepath(maze,m,n); if(X!=0) result_maze(m,n);

数据结构课设--迷宫

4 调试与分析

4.1 调试分析

在调试程序时，一开始用的是栈进行存储，但发现寻找的路径是多条或不一定是最短路径，不利于实现这一算法。因此改用队列存储，查找到理想的迷宫路径。

在实现这个算法过程中，要将访问过的结点都做标记，而且还应该注意队列中未经过却是非障碍结点的表示。所以要对多种结点加以区分（包括障碍点、有用的非障碍结点和无用的非障碍结点）。

4.2 测试结果

4.2.1当输入的行列数超过预设范围

图4.2.1 当输入的行列数超过预设范围

数据结构课设--迷宫

4.2.2当输入的行列数未超过预设范围

图4.2.2 当输入的行列数超过预设范围

数据结构课设--迷宫

参考文献

[1]《数据结构》（用面向对象方法与C++描述），殷人昆等，清华大学出版社 [2]《算法与数据结构习题精解和实验指导》，宁正元等，清华大学出版社

数据结构课设--迷宫

附 录（关键部分程序清单）

程序代码

#include"stdlib.h" #include"stdio.h" #define N 39 #define M 39 int X;

int maze[N+2][M+2]; struct point{ int row,col,predecessor; }queue[512]; int head=0,tail=0;

void s_maze(int m,int n){ int i,j; printf("\n\n"); printf("请按行输入迷宫，0表示通路，1表示障碍:\n\n"); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&maze[i][j]); }

void print_maze(int m,int n){ int i,j; printf("\n迷宫生成结果如下:\n\n"); printf("迷宫入口\n"); printf("↓"); for(i=0;i<m;i++) {printf("\n"); for(j=0;j<n;j++) {if(maze[i][j]==0) printf("□"); if(maze[i][j]==1) printf("■");} } printf("→迷宫出口\n"); }

void result_maze(int m,int n){ int i,j; printf("迷宫通路(用☆表示)如下所示：\n\n"); for(i=0;i<m;i++) {printf("\n"); for(j=0;j<n;j++) {if(maze[i][j]==0||maze[i][j]==2) printf("□");

数据结构课设--迷宫

if(maze[i][j]==1) printf("■"); if(maze[i][j]==3) printf("☆"); } } }

void enqueue(struct point p){ queue[tail]=p; tail++; }

struct point dequeue(){ head++; return queue[head-1]; }

int is_empty(){ return head==tail; }

void visit(int row,int col,int maze[41][41]){ struct point visit_point={row,col,head-1}; maze[row][col]=2; enqueue(visit_point); }

int mazepath(int maze[41][41],int m,int n){ X=1; struct point p={0,0,-1}; if(maze[p.row][p.col]==1)

{printf("\n===============================================\n"); printf("此迷宫无解\n\n");X=0;return 0;} maze[p.row][p.col]=2; enqueue(p); while(!is_empty()) {p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) break; if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze); if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze); if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze); if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze); } if(p.row==m-1&&p.col==n-1) {printf("\n============================================\n"); printf("迷宫路径为：\n"); printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; while(p.predecessor!=-1)

数据结构课设--迷宫

{p=queue[p.predecessor]; printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; } } else

{printf("\n================================================\n"); printf("此迷宫无解！\n\n");X=0;} return 0; }

void main() {int m,n;

printf("生成迷宫:\n");

printf("\n请输入行数：");scanf("%d",&m); printf("\n");

printf("请输入列数：");scanf("%d",&n); while((m<=0||m>39)||(n<=0||n>39)) {printf("\n输入的行列数超出预设范围(0-39,0-39),请重新输入：\n\n"); printf("请输入行数：");scanf("%d",&m); printf("\n");

printf("请输入列数：");scanf("%d",&n); } s_maze(m,n); print_maze(m,n); mazepath(maze,m,n); if(X!=0) result_maze(m,n); printf("\n\nPress Enter Contiue!\n"); }

数据结构课设--迷宫

沈阳航空工业学院课程设计报告

本文来源：https://www.bwwdw.com/article/gkzj.html