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

课程设计报告

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

课题名称____________迷宫问题______________

专业_____________________________

班级_______________________________

学号______________________________

姓名_____________________________

指导教师______________________________

2012年6月9日

课程设计任务书

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

课题迷宫问题

专业班级___________

学生姓名________________

学号_________________

指导老师__________________

审批____________________

任务书下达日期：2012年6月9日

任务完成日期：2012年6月16日

设计内容与设计要求

1.设计内容：

1）问题描述

以一个M*N的长方阵表示迷宫,0和1分别表示迷宫中的通路和墙壁。设计一个程序，

对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。

2）基本要求

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

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

到下一个坐标的方向。

b.编写递归形式的算法，求得迷宫中所有可能的通路.

3）测试数据

迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。

UU1U0U10

00100010

00001101

01110010

00010000

01000101

01111001

11000101

11000000

4）实现提示

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺看某一个方向进行探

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

置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通

路。

可以二维数组存储迷宫数据，通常设定入口点的下标为（1,1）,出口点的下标为（m,

n）o为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、

南、西、北四个方向可通C

2.设计要求：

•课程设计报告规范

1）需求分析

a.程序的功能。

b.输入榆出的要求。

2）概要设计

a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，

它们之间有什么关系等。

3）详细设计

a.采用C语言定义相关的数据类型。

b.写出各模块的类C码算法。

c.画出各函数的调用关系图、主要函数的流程图。

4）调试分析以及设计体会

a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误

的输入及输出结果。

b.程序调试中遇到的问题以及解决问题的方法。

c.课程设计过程经验教训、心得体会。

5）使用说明

用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。

6）书写格式

见附带说明。

7）附录

a.参考书目

b.源程序清单（带注释）

•考核方式

指导老师负责脸收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计

报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成

绩。具体考核标准包含以下几个部分：

①平时出勤（占10%）

②系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）

③程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）

④设计报告（占30%）

注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。

⑤独立完成情况（占10%）。

•课程验收要求

①运行所设计的系统。

②回答有关问题。

③提交课程设计报告纸质稿。

④提交源程序、设计报告文档电子稿。

⑤依内容的创新程度，完善程序情况及对程序讲解情况打分。

二、进度安排

附：

课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。

正文的格式:一级标即用3号里体.二线标题用四号宋体加粗.正文用小四号定体:行距为22c

正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求西出模块图）；三、主要功能的实现（至少要有

一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注择"

正文总字数要•求在5000字以上（不含程序原代码）。

目录

一、任务书..............................................2

二、基本算法............................................7

三、需求分析...........................................7

a.程序的功能..........................................7

b.输入输出的要求.....................................7

c.程序算法分析........................................8

四、概要设计............................................8

i.设计中非递归程序的模块结构图.....................8

ii.程序的数据结构和数据库结构分析..................9

iii.试探方向的设计....................................10

iv.达某点，以避免发生死循环.......................11

五、详细设计...........................................11

a.伪码设计............................................11

b.mgpath()流程图...................................12

六、调试分析............................................13

七、总结.................................................14

八、评分表..............................................16

九、附录(源代码清单).................................17

一、基本算法

走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西

南、西、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不

曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过,

则退回一步，在原来的位置上继续试探下一位置。

每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；

若退回到了入口处，则说明不存在通路,

用一个字符类型的二维数组表示迷宫，数组中每个元素取值“（）”（表示通路）或“1”

（表示墙壁）。迷宫的入口点在位置（1,1）处，出口点在位置（m,m）处。设计一个模

拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。

二维数组的第。行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的

边界；第1行第1列元素和第m行第m列元素置成“（）”，表示迷宫的入口和出口；其

余元素值用随机函数产生。

假设当前所在位置是（x,y）o沿某个方向前进一步，它可能到达的位置最多有8个。

如果用二维数组move记录8个方向上行下标增量和列下标增量，则沿第i个方向向

进一步，可能到达的新位置坐标可利用move数组确定:

x=x+move[i][0]

y=Y+m（）ve[i][l|

从迷宫的入口位置开始，沿图示方向顺序依次进行搜球

在搜索过程中，母前进一步，在所到位苴处做标记

（表示这个位置在通路上），并将该位置的坐标压入栈中。

每次后退的时候，先将当前所在位置处的通路标记"”改

成死路标记“X”(表示这个位置曾到达过但走不通，以后

不要重复进入)，然后将该位置的坐标从栈顶弹出。

搜索到出口位置时，数组中那些值为“”的元素形成一条

通路。

二、需求分析

a.程序的功能。

(i)实现一个以链表作存储结构的栈类型，以非递归算法求取所有通路和最

短路径

(ii)以一个递归算法，对任意输入的迷宫矩阵(1代表不通，0代表通路)

求出所有通路

b.输入输出的要求。

(i)求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中

的一个坐标，d表示走到下一个坐标的方向。

(ii)输出迷宫示意图

c、程序算法分析

1.迷宫的建立：

迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示

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

2.迷宫的存储：

迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位气

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

虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元

素，即可得到一个mXn的二维数组，这样(0,0)表示迷宫入口位置，表示

迷宫出口位置。

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

39,当然，用户也可根据需要，调整其大小。

3.迷宫路径的搜索：

首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路

径，搜索工作结束。否则搜索其上、下、左、右位竟是否是障碍，若不是障碍,

就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择

另一个相邻的位置，并从它开始搜索路径。为防止搜索重交出现，则将已搜食

过的位竞标记为2,同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当

前位置保存在一个枝中，如果所有相邻的非障碍位置均被搜索过，且未找到通

往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历

的算法，如果找到路径，则为最短路径。

三、概要设计

i)设计中非递归程序的模块结构图

图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用关系，虚线方框表

示文件的组成

main()

mapath()

mgpath():求解迷宫问题，即输出从(1,1)至"(M,N)的全部路径和最短路径(包

含最短路径长度)。当找到一条路径时，不使用return语句退出，而是出栈一次，重新

回溯走另一条路径，并用minlen记录最短路径长度，Path数组记录最短路径。

ii)程序的数据结构和数据库结构分析

设迷宫为m行n列，利用maze[m][n]来表示一个迷宫,maze[i][j]=O或1;其中：。表

示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四

个角点有2个方向，其它边濠点有3个方向，为使问题简单化我们用ma2c[m+2][n+2]来

表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，毋个点的试探方向全部

为4,不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一

致。

如图3.4表示的迷宫是一个6X8的迷宫。入口坐标为（1,1）,出口坐标为（m,n）o

入口(1,1)

出口（6,8）

图1用maze[m+2][n-2]表示的迷宫

迷宫的定义如下:

#definem6/*迷宫的实际行*/

#definen8/*迷宫的实际列*/

intmaze[m+2][n+2];

iii.试探方向的设计

示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标（x,乃，与其相邻的4

个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在（m,n）,因

此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化

问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0,1,2,

3表示东、南、西、北）的坐标增量放在一个结构数组move[4]中，在move数组中，

每个元素有两个域组成，x：横坐标增量，尸：纵坐标增量。Move数组如图3所示。

move数组定义如下：

typedefstruct{

intx;〃行

int//歹4

}item;

itemmove[4];

这样对move的设计会很方便地求出从某点（x,y）按某一方向v（04vW3）到达的

新点（/,/）的坐标：/=x+movc[v].x,/=y+moveM.y0

（x-1»

।

（X,v-1）<-----（x,------*（X,y+1）

I

（x+1,y）

图2与点（x,y）相邻的4个点及坐标

y

iii>栈的设计

当到达了某点而无路可走时需返回前一点,

一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前

一点到达本点的方向，即每走一步栈中记下的内容为（行，列，来的方向）。对于图1所

示迷宫，依次入栈为:

top

—>

3,4,0

3,3,0

3,2,1

栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向

2,2,0

向下走的，对于图3迷宫，走的路线为：

2,1,1

1,1,0

(1,1)。(2,1),(2,2)。(3,2),0,3%（3,4）0（下脚标表示方向），当无路可走，则应回溯,

对应的操作是出栈，沿下一个方向即方向继续试探。

栈中元索是一个由行、列、方向组成的三元组，栈元索的设计如下：

typcdefstrucr{

intx,y,d;/*横纵坐标及方向*/

[datatype;

栈的定义为：SeqScacks;

iv、达某点，以避免发生死循环：

一种方法是另外设置一个标志数组mark[mHn],它的所有元素都初始化为0,一旦到

达了某一点(/,/)之后，使置1,下次再试探这个位置时就不能再走了。另

一种方法是当到达某点后使mazcW]"]置-1,以便区别未到达过的点，同样乜

能起到防止走重复点的目的，此处采用后一方法，算法结束前可恢复原迷宫。

四、详细设计

a.伪码设计

(1)栈初始化；

(2)将入口点坐标及到达该点的方向(设为-1)人栈

(3)while(栈不空)

{栈顶元素=>(x,y,d)

出栈；

求出下一个要试探的方向d++;

while(还有剩余试探方向时)

{if(d方向可走)

则{(x,y,d)入栈；

求新点坐标

将新点(i,j)切换为当前点(x,y);

if((x,y)==(m,n))结束;

else重置d=0;

}

elsed++;

)

}

算法如下：

intpath(int&mazc,intm,intn,intmove)

//m,n为maze的一、二维长度，move为结构体数组存放了试探的4个方向

坐标

{ScqStacks;

datetypetemp;

>ntx,y,d,i,j;

tcmp.x=l;temp.y=l;temp.d=-l;

Push_SeqStack(s,temp);阿

while(!Empty_SeqStack(s)){

Pop_ScqStack(s,&temp);

x=tcmp.x;y=tcmp.y；d=tcmp.d+l;

while(d<4){

i=x+move[d].x;j=y+move[d].y；

if(maze[i]|j]==0){

temp={x,y,d);

Push_SeqStack(s,temp);

x=i;y=j；mazc[x][y]=-1;

if(x==m&&y==n)return1;/*迷宫有路*/

elsed=0;

}

elsed++;

}/*while(d<4)*/

}/*\vhilc(!Empty_SeqStack(s))*/

return0;/*迷宫无路*/

)

栈中保存的就是一条迷宫的通路。

b.mgpath()流程图

五、调试分析

a、迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。

00100010

00100010

00001101

01110010

00010000

01000101

01111001

11000101

11000000

•G:\c++.c\数据结构课程设计\cc\De

b、程序溯试截图

1）递归算法程序求所有路径，

预设测试迷宫，输出迷

宫图黑色方块代表墙壁

ii）运行程序得出所有通路，

以图的方式输出，圆圈代

表路径（程序截图如右）

£°G:\c++.c保据胭课程断■谜言l\Debug\迷言Lexe・

迷音所有路径如下：▲

三元组〈1*，心）”1,"表示送宫巾的一个坐标,（1“01；16;2J;30;

1：<1,1,2><2,1,2〉<3,1,2)<4,1,2><5,1,1)

<5,2,1)<5,3,2〉<6,3,1〉<6,4,1)<6,5,0)

<5,5,0)<4,5,1><4,6,2〉<5,6,1)<5,7,2)

<6,7,2)<7,7,2><8,7,2)<9,7,1)<9,8,-1>

2：<1,1,2〉<2,1,2><3,1,2〉<4,1.2〉

<5,2.1〉<5,3,2><6,3,1〉<6,4,1〉<6,5,0)

<5,5,1><5,6,1><5,7,2》<6,7,2〉<7,7,2〉

<8,7,2><9,7,1><9,8,-1>

最理路径如下:

长度：18

路径：<1,1,1><2,1,1><3,1,|><4,1,|>

<5,2,->><5,3,|<6,5,，)

<5,5,->><5,7,1><6,7,!><7,7」)

<8,7,|><9,7,—〉<9,8,终点〉

Pressanykeytocontinue

▼

iii）输入上表给出的测试矩阵，运行源代码清单1,以三元组输出所有通路，及最短路

径，程序运行截图（如上）

六、总结

经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是

翻阅资料。在此期间我失落过，也曾一度热情高涨。点点滴滴令我回味无长。这次课程

设计使我体会到只有做到细心耐心，恒心才能做好事情。

这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据

结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及

文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编

译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。通过课程设

计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。

而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很

能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识来源

于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测

试之后的课程设计对我们的作用是非常大的。

这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远

远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为

社会服务，从而提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思

是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。

当然，很多也时用错了方法，总是实现不了。同时在设计的过程中发现了自己的不足之

处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。

根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点：

1、认真上好专业实验课，多在实践中锻炼自己。

2、写程序的过程中要考虑周到，严密。

3、在做设计的时候要有信心，有耐心，切勿浮躁。

4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便

能节省调试程序的时间。

每个实险通常都要花费很久的时间才能理清一个程序的思路，而且要不断的调试程

序才能把程序调试正确，同时还要做到界面的输出也是需要美化的。这次课程设计终于

顺利完成了，在设计中遇到了很多专业知识问题，最后在老师的辛勤指导下，也完成了

课程设计。

通过这次的课程设计，让我更加了解到数据结构的重要性。以及它对我们专业的

发展发挥的作用。对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。让我

知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，

一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课

程设计必将成为我人生旅途上一个非常美好的回忆！同时在做课程设计时要能够从多方

面去考虑，去研究，用多种并法去实现要求。此次课程设计，学到了很多课内学不到的

东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅，今后的制

作应该能够更轻松，自己也都能够解决并高质量的完成项目。

评分表

理学院课程设计评分表

课题名称：迷宫问题

项目评价

设计方案的合理性与创造性

设计与调试结果

设计说明书的质量

答辩陈述与回答问题情况

课程设计周表现情况

综合成绩

教师签名：______________

日期：

附录

A、参考书目

1、《数据结构教程（第3版）》李春葆尹为民编著清华大学出版社出版

2、《数据结构教程（第三版）上级实险指导》李春葆尹为民编著清华大学出版社出版

3、《数据结构（学习指导、尖脸指导、课程设计）》陈媛编著机械工业出版社出版

B、源程序清单（带注释）

i）非递归算法求迷宫源程序

/*实现一个以链表作存储结构的栈类型，然后编写

*一个求解迷宫的非递归程序。求得的通路以三元组

*（i,j,d）的形式输出，其中：（i,j）指示迷宫中

*的一个坐标，d表示走到下一个坐标的方向。

*/

#include<stdio.h>

#includc<string>

#defineM9〃行数

#defineN8〃列数

#defineMaxSize10()〃栈最多元素个数

intmg[M+2][N+2]={〃迷宫测试数据矩阵，左上角（1,1）为入口，右

下角(9,8)为出口

(1,1,1,1,1,1,1,1,1,1),

{i,o,o,i,o,o,o,i,o,i},

{1,0,1,1,0,o,o,i,o,i(>

(1,0,0,0,0,1,1,04,1),

{1,0,13,1,0,0,1,0,1),

(1,0,0,0,1,0,0,0,0,1),

(1,0,1,0,0,0,1,0,1,1),

{l,o,l,1,1,1,0,0,1,1),

{1,1,1,0,0,0,1,0,1,1),

(1,1,1,0,0,0,0,0,0,1),

{1,1,1,1,1,1,1,1,1,1}

};

struct

intiuntjuntdi;

}Stack[MaxSize],Path[MaxSize];〃定义栈和存放最短路径的数组

inttop=-l;〃栈顶指针

intcouncil;〃路径数计数

intminlen=MaxSize;//最短路径长度

voidmgparhQ〃踏径为：。,1)>(M,N)

(

inti,j,di,find,k;

top++;〃进栈

Stack[top].i=l;

Stack|top].j=l;

Stack[top].di=-l;mg[l][l]=-l;〃初始结点进栈

while(top>-l)〃栈不空时循环

i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;

if(i=二M&&尸二N)〃找到了出口，输出路径

prinrf(n%4d:*',count++);

for(k=0;kv=top；k++)

{〃以三元组输出路径

printf(H(%d,%d,%d)",Stack[k].i,Stack[k].j,Stack[k].di);

if((k+l)%5==0)printf("\n\tM);〃输出时每5个结点换一

行

printfC'\n");

if(top+l<minlen)〃比较找最短路径

(

for(k=0;k<=top;k++)

Path[k]=Stack[k];

minlen=top+l;

mg(Stack[top].i][Stack[top].j]=0;//让该位置变为其他路径可走

结点

top-;

i=Stack[top].i;j=Stack[topl.j;di=Stack[top].di;

}

find=0;

while(di<4&&find==0)〃找下一个可走结点

{di++;

switch(di)

{

case0:i=Stack[top].i-l;j=Stack[top].j;break;

casel:i=Stack[top].i;j=Stack[top].j+l；brcak;

case2:i=Stack[top].i+l;j=Stack[top].j;break;

case3:i=Stack|top].i,j=Stack[top].j-l;brcak;

}

if(mg[i][i]==0)find=l;

}

if(find==l)〃找到了下一个可走结点

{Stack[top].di=di;〃修改原栈顶元素的di值

top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-l;//下一个可走结点

进栈

mg[i][j]=-1;〃避免重复走到该结点

}

eke〃没有路径可走，则退我

(

mg[Stack[top].i][Stackftop]j]=0;//让该位置变为其他路径可走结

点

top-;

}

}

printf("最短路径如下:\n")；

printf("长度:%d\n",minlen);

printf("路径:");