迷宫问题的关键操作要点

课程设计任务书

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

设计起止日期

设计题目：迷宫问题的操作

设计任务（重要技术参数）：

学会运用数据构造建立迷宫问题，编造出迷宫并设计出走出迷宫的措施

硬件环境：处理器：英特尔第三代酷睿i3-3110M©2.40GHz双核

内存：4GB（三星DDR31333MHz）

主硬盘：希捷ST500LM0I2HN-M500MBB（500GB/5400

显示屏：二星SEC3649（14英寸）

软件环境:操作系统：Windows864位（DirectX11）

开发环境：VC++6.0

指导教师评语:

成绩：签字：

年月日

1、课程设计目的

为了配合《数据构造》课程的开设，通过设计一完整日勺程序，掌握数据

构造的应用、算法的编写、类C语言的J算法转换成C程序并用TC上机调试的基本

措施特进行题目为两个链表合并日勺课程设计。通过本次课程设计充足锻炼有关数

据构造中链表的创立、合并等措施以和怎样通过转化成C语言在微机上运行实现

等其他方面的能力。

2.课程设计的内容与规定

2.1问题描述：

迷宫问题是取自心理学时一种古典试验。在该试验中，把一只老鼠从一种无顶大

盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有

一种出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以抵达出口。对

同一只老鼠反复进行上述试验，一直到老鼠从入口走到出口，而不走错一步。老

鼠通过多次试验最终学会走通迷宫啊路线。设计一种计算机程序对任意设定FI勺矩

形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。

出口♦

图A

2.2设计规定：

规定设计程序输出如下：

（1）建立一种大小为mXnH勺任意迷宫（迷宫数据可由顾客输入或由程序自动生

成），并在屏幕上显示出来；

（2）找出一条通路的二元组（i,j）数据序列，（i.j）表达通路上某一点日勺坐标。

（3）用一种标志（如数字8）在迷宫中标出该条通路；

（4）在屏幕上输出迷宫和通路;

（5）上述功能可用菜单项选择择。

3.课程设计总体方案和分析

3.1问题分析：

1.迷宫的建立：

迷宫中存在通路和障碍，为了以便迷宫的创立，可用0表达通路，用1表达隙碍,

这样迷宫就可以用0、1矩阵来描述，

2.迷宫口勺存储：

迷宫是一种矩形区域，可以使用二维数组表达迷宫，这样迷宫的每一种位置都可

以用其行列号来唯一指定，不过二维数组不能动态定义其大小，我们可以考虑先

定义一种较大的二维数组maze[M+2][N+2],然后用它的前m行n列来寄存元素，

即可得到一种mXn口勺二维数组，这样（0,0）表达迷宫入口位置，表达迷

宫出口位置。

注：其中M,N分别表达迷宫最大行、列数，本程序M、N的缺省值为39、39,

当然，顾客也可根据需要，调整其大小。

3.迷宫途径日勺搜索：

首先从迷宫日勺入口开始，假如该位置就是迷宫出口，则已经找到了一条途径，搜

索工作结束。否则搜索其上、下、左、右位置与否是障碍，若不是障碍，就移动

到该位置，然后再从该位置开始搜索通往出口的途径；若是障碍就选择另一种相

邻的位置，并从它开始搜索途径。为防止搜索反复出现，则将已搜索过日勺位置标

识为2,同步保留搜索痕迹，在考虑进入下一种位置搜索之前，将目前位置保留

在一种队列中，假如所有相邻的非障碍位置均被搜索过，且未找到通往出口日勺途

径，则表明不存在从入口到出口的途径。这实现日勺是广度优先遍历的算法，暇如

找到途径，则为最短途径。

以矩阵00101为例，来示范一下

10010

10001

00100

首先，将位置（00（序号0）放入队列中，其前节点为空，从它开始搜索，其

标识变为2,由于其只有一种非障碍位置，因此接下来移动到（0,1）（序号1）,其前

节点序号为0,标识变为2,然后从（0,1）移动到（1,1）（序号2）,放入队列中，其前

节点序号为1,（1,1）存在（1,2）（序号3）、（2,1）（序号4）两个可移动位置，其前节

点序号均为2.对于每一种非障碍位置，它的相邻非障碍节点均入队列，且它们的

前节点序号均为该位置日勺序号，因此假如存在途径，则从出口处节点日勺位置，逆

序就可以找到其从出口到入口的通路。

如下表所示:

012345678

91()

(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)

(3,4)

-10122345679

由此可以看出，得到最短途径：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(()/)((),0)

搜索算法流程图如卜所示：

1.①构建一种二维数组maze[M+2][N+2]用于存储迷宫矩阵

②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值

③构建一种队列用于存储迷宫途径

④建立迷宫节点structpoinl,用于存储迷宫中每个节点的访问状况

⑤实现搜索算法

⑥屏幕上显示操作菜单

2.本程序包括1()个函数：

⑴主函数main。

(2)手动生成迷宫函数shoudong_maze()

⑶自动生成迷宫函数zidong_maze()

⑷将迷宫打印成图形print_maze()

(5)打印迷宫途径(若存在途径)result」naze()

(6)入队enqueue()

(7)出队dequeue()

(8)判断队列与否为空is_empty()

(9)访问节点visit()

(10)搜索迷宫途径mgpathO

3.3详细设计

实现概要设计中定义的所有数据类型和操作的J伪弋码算法

1.节点类型和指针类型

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

迷宫中节点类型和队列类型:structpoint)introw,col,predecessor)que[512]

2.迷宫的操作

(1)手动生成迷宫

voidshoudong_maze(intm,intn)

｛定义i,j为循环变量

for(i<=m)

for(j<=n)

输入maze[i皿时值

1

(2)目动生成迷宫

voidzidong_maze(intm,intn)

｛定义ij为循环变量

for(i<=m)

for(j<=n)

mazelij[jj=rand()%2〃由于rand()产生日勺随机数是从。到

RAND_MAX,RAND_MAX是定义在stdlib.h中时，其值至少为32767),要产生从X

到Y数，只需要这样写：k=rand()%(Y-X+l)+X;

)

(3)打印迷宫图形

voidprint_mazc(intm,intn)

｛用i,j循环变量,将输出口、■｝

⑷打印迷宫途径

voidresult_maze(intm,intn)

｛用i,j循环变量，将输出口、■、☆｝

⑸搜索迷宫途径

①迷宫中队列入队操作

voidenqueue(structpointp)

｛将p放入队尾，tail++)

②迷宫中队列出队操作

structpointdequeue(structpointp)

｛head++,返回que[head-l]｝

③判断队列与否为空

intis_empty()

｛返回head==tail的)值，当队列为空时,返回0｝

④访问迷宫矩阵中节点

voidvisit(introw,mtmaze[41J[41J)

(建立新的1队列节点visit_point,将其值分别赋为row,col,head-1,maze[row][col]=2,

表达该节点以被访问过;调用enqueue(visit_point),将该节点入队｝

⑤途径求解

voidmgpath(intmazc[41J[41].intn)

｛先定义入口节点为stmetpointp=｛0,0,-l｝，从maze⑼⑼开始访问。假如入口处即

为障碍，则此迷宫无解，返回0,程序结束。否则访问入口节点，将入口节点

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

判断队列与否为空，当队列不为空时，则运行如下操作：

｛调用dequeue。函数，将队头元素返回给p,

假如p.row=二m-1且p.col==n-l,即抵达出口节点，即找到了途径，结束

假如p.col+l<n且maze[p.row][p.col+l]==0,阐明未到迷宫右边界，且其右方有通

路，则visit(p.row,p.col+1,maze),将右边节点入队标」只已访问

假如p.row+l<m且maze[p.row+l][p.col]==0,阐明未到迷宫下边界，且其下方有

通路，则visit(p.row+l,p.col,maze),将下方节点入队标识已访问

假如p.col-l>0且maze[p.row][p.col-l]==0,阐明未到迷宫左边界，且其左方有通路,

则visit(p.row,p.col-l,maze),将左方节点入队标识已访问

假如p.row-l>()且maze[p.row-l][p.col]==0,阐明耒到迷宫上边界，且其上方有通

路，则visit(p.row,p.col+l,maze),将上方节点入队标',只已访问)

访问到出口(找到途径)即p.row==m-l且p.col==n-l厕逆序将途径标识为3即

maze[p.row][p.col]==3;

while(p.predecessor!=-1)

{p=qucuc[p.predecessor];mazc[p.row][p.col]==3;)

最终将途径图形打印出来。

3.菜单项选择择

whilc(cyclc!=(-l))

☆手动生成迷宫请按：1

☆自动生成迷宫请按：2

☆退出请按：3

scanf("％d”,&i);

switch(i)

{case1：请输入行列数(假如超过预设范围则提醒重新输入)

shoudong_maze(m,n);

print_maze(m.n);

mgpath(maze,m,n);

if(X!=O)result_maze(m,n);

case2:请输入行列数(假如超过预设范围则提醒重新输入)

zidong_maze(m,n);

print_maze(m,n);

mgpath(maze,m,n);

if(X!=O)result_maze(m,n);

case3：cycle=(-l);break;

)

注：详细源代码见附录

3.4调试分析

在调试过程中，首先使用H勺是栈进行存储、不过产生的途径是多条或

不是最短途径，因此通过算法比较，改用此算法

3.5测试成果

1.手动输入迷宫

C:\Docu>entsandSettings\ne,\桌面\Debug\Cppl.exe/口|X

欢迎进入迷宫求解系统

动生

成迷

请

舌

☆宫1

生

迷

动

宫

成

☆请2

退

出

☆请3

请选择你的操作：

1

请输入行数：44

请输入列数：4

抱歉，你输入的行列数超出预设范围＜。-39，。-39〉,请重新输入:

请输入行数：4

请输入列数：4

请按行输入迷宫，。表示通路，工表示障碍：

0001

0101

0011

0000

迷宫生成结果如下：

迷宫入口

□□□■

'D:\VC\MicrosoftVisualStudio\!^\D«bu9\NUM2.exe*

谓洽入行数：明

年■入列致，，

拒载・你"入的行列数超出预设团的(。79.。79).清藏默粕人,

请脸入打败，«♦

谓・入列数：4

苗按行“入迷含・8表示通路・1表示修当；

b。。1

biei

ee11

。eee

，官生成站果如下：

也才入口

4

□□□■

□□□□一连力出口

sttttttfttstBttttttttttBBtttttttattstttttattttttttttttsttttttttstc

墙宫路校为：

(3.3)

(3.2)

<3.1)

(2.1)

(2.0)

(1。)

(9.0)

连宫通路(用力表示)如下所示：

口C■

■口■

☆■■

:

a力

Pr・“Ent”Contiuet

啤3：0

2自动生成迷宫:

欢理进入迷宫求解系统

设计者:付古龙

☆乎动生成迷宫谓按，1

☆自动生成迷宫ltt«>2

☆退出谓按】？

口选择你的掾作;

it*入行数16

8”入列数：6

选力生成中

南接住•国继续・..

迷宫生成玷累如下:

迷宫入口

■■O

□■B

■■■Q

□□B

□□B

□■O

ssxzsxsxsssssxxstsss

比迷离无川

Pr»c«EnterContiuef

V%入息至：二

4.设计体会

通过本次时课程设计，使我学会了怎样去组织代码量较大大程序。与此同步,

也使我学会了某些对代码量较大H勺的程序进行编写、连接、编译运行、以和调试

和修改H勺技巧

这次日勺课程设计涉和到编程语言和数据构造H勺知识，规定和平时的I实比相对

较高。从本次内课程设计可以检查我们对C语言和数据构造口勺掌握状况，同步也

检查了我们对所学习过的知识的灵活运用状况。在创新性方面，这次的课程设计

虽然完毕了课程设计的任务，不过缺乏发明性的设计思想，在后来的学习过程中

还得继续努力。

5.参照文献

[1].严蔚敏编著.数据陶造（C语言版）.清华大学出版社，2023

[2].朱战立.编著.数据构造一一使用C语言.西安交通大学出版社，2023

[3].朱战立，张选平编著.数据机构学习指导和经典题解.西安交通大学出版社,

2023

[4].苏小红，孙志岗等编著.C语言大学实用教程（第2版）.电子工业出版社，

2023

[5].梁肇新编著.编程高手箴言.电子工业出版社，2023

附件：

#include"stdlib.h"

#include"stdio.h''

#defineN39

#defineM39

intX;

intmaze[N+2][M+2];

structpoint{

introw,col,predecessor;

}queue[512];

inthead=0,tail=0;

voidshoudong_maze(intm,intn){

intij;

printf(”\n\n”)；

printf("请按行输入迷宫，0表达通路，1表达障碍

for(i=0;i<m;i++)

for(j=0;j<n;j++)

scunf(”％d”,&muzc[i][j]);

}

voidzidong_maze(intm,intn){

intij；

printf(H\n迷宫生成中……\n\n*,);

systemC^pause");

for(i=0;i<m;i++)

for(j=0;j<n;j++)

maze[i][j]=rand()%2;

〃由于rand()产生的随机数是从。到RAND_MAX

//RAND_MAX是定义在stdlib.h中的，其值至少为32767)

〃要产生从X到Y的数，只需要这样写：k=rand()%(Y-X+l)+X;

)

voidprintmazefintn){

intij；

printf(',\n迷宫生成成果如下:\n\n”)；

printf("迷宫入口\n")；

printf("IH);

for(i=0;i<m;i++)

for(j=0;j<n;j++)

{if(maze[i][j]==O)printf("口");

if(maze[i]LjJ==Dprintf(,,BM);}

)

printf(”一迷宫出口\iT);

)

voidresult_maze(intmjntn){

intij;

printf("迷宫通路(用☆表达)如下所示：\n\t'*);

for(i=0;i<m;i++)

{printfCV");

for(j=Oy<n;j++)

{if(niaze[i][j]==0||niaze[i][jl==2)printf(H□**);

if(maze[i][j]==l)printf("■”);

if(mazefilfj]==3)printfC+”)；

)

)

)

voidenqueue(structpointp){

queue[tail1=p;

tail++;

)

structpointdequeue(){

head++；

returnqueue[head-l];

}

intis_empty(){

returnhead==tail;

}

voidvisit(introw,intcoljntmaze[41J[41J){

structpointvisit_point={row,col,head-1};

maze|row][col)=2;

enqueue(visit_point);

)

intmgpath(intmaze[41][41],intm,intn){

X=l：

structpointp={0,0,-l};

if(maze[p.rowl[p.col]==l)

{printf("\n===============================================\n");

printf("此迷宫无解\n\n");X=O;return0;)

maze[p.row][p.coll=2;

enqueue(p);

while(!is_enipty())

{p=dequeue();

if((p.row==m-l)&&(p.col==n-l))break;

if((p.col+l<n)&&(maze[p.row][p.col+l]==()))visit(p.row,p.col+1,maze);

if((p.row+l<m)&&(maze[p.row+l][p.col]==0))visit(p.row+l,p.col,maze);

if((p.col-l>=())&&(maze[p.rowj[p.col-l]==()))visit(p.row,p.col-l,maze);

if((p.row-l>=0)&&(maze[p.row-l][p.col]==0))visit(p.row-l,p.col,maze);

)

if(p.row==m-l&&p.col==n-l)

{printf(,'\n========================================================

=========\irf);

printfC迷宫途径为：\n-);

printf(n(%d,%d)\n*',p.row,p.col);

maze[p.row][p.col]=3;

while!p.predecessor!=-1)

{p=queue[p.predecessorj;

printf(',(%d,%d)\n,,,p.row,p.col);

maze[p.rowKp.col]=3;

)

)

else

{printf(n\n=============================================================

\n")；

printf(“此迷宫无解！\n\nH);X=O;}

return0;

}

voidmain()

{inti,m,n,cycle=0;

while(cyde!=(-l))

********\n”)；

printf(u欢迎进入迷宫求解系统\n”）;

printf('‘率*咨************工*************咨************************奉*****************

********\n“)：

printfC,☆手动生成迷宫请按：l\n“)；

printf(u☆自动生成迷宫请按：2\n");

printf(u☆退出请按：3\n\nM);

printf(”***************x**************************************※*京***