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

软件 学 院 软件工程+电子商务2009 专 业 2 班 一、课程设计(论文)题目 迷宫问题

二、课程设计(论文)工作自 2010 年 12月 27 日起至 2011 年 1月 2 日止

三、课程设计(论文) 地点: 创新大楼实训中心 四、课程设计(论文)内容要求： 1．本课程设计的目的

（1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。 （2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软 件设计的能力。

（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设 计的基本能力。

2．课程设计的任务及要求 1）基本要求：

（1）对系统进行功能模块分析、控制模块分析； （2）系统设计要能完成题目所要求的功能；

（3）编程简练，可用，尽可能的使系统的功能更加完善和全面； （4）说明书、流程图要清楚； （5）提高学生的论文写作能力； （6）特别要求自己完成；

2）创新要求：

在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。

3）课程设计论文编写要求

（1）要按照书稿的规格打印与写课程设计论文 （2）论文包括目录、正文、小结、参考文献、附录等 （3）课程设计论文装订按学校的统一要求完成

4）课程设计进度安排

内容 天数 地点

构思及收集资料 1 图书馆 编码与调试 3 实验室

撰写论文 1 图书馆、实验室

学生签名：

20011 年 1 月 3日

课程设计(论文)评审意见

（1）基本算法 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （2）设计分析 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （3）调试分析 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （4）论文内容 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （5）答辩分析 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （6）格式规范性及考勤是否降等级：是（ ）、否（ ）

评阅人： 职称： 讲师

2011 年 1月4日

目录

一、 需求分析 ............................................................................................ 1 二、 概要设计 ............................................................................................ 2 三、 详细设计 ............................................................................................ 5 四、 调试分析及测试 .............................................................................. 15 五、 个人工作及创新 .............................................................................. 18 六、 小结 .................................................................................................. 19 参考文献 ...................................................................................................... 20

数据结构课程设计

一、 需求分析

1.选题理由

本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题， 迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。

2.基本原理分析

迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。

以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。

3.功能要求

（1）以一个二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]和Maze[i][n+1] (0<=i<=m+1)为做外层的一圈障碍。数组中以0表示通路，1表示障碍，限定迷宫的大小为：m,n<=10。

（2）用户需用文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，用0，1输入，同行中的两个数字之间用空白字符相隔。

（3）迷宫的入口位置和出口位置可由用户随时设定。

（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“#”表示障碍，“*”表示路径，“@”表示曾途经该位置但不能到达出口，其余位置用空格符表示。若设定迷宫不存在通路则报告相应信息

（5）本程序只求出一条成功的通路。

（6）程序执行的命令为：1，创建迷宫；2，求解迷宫；3，输出迷宫的解。

1

数据结构课程设计

二、

概要设计

1、数据结构及其抽象数据类型的定义。 （1）栈的抽象数据类型 ADT Stack{

数据对象：D={ai| ai∈CharSet,i=1,2„n,n>=0} 数据关系：R1={| ai-1, ai∈D,i=2,„n} 基本操作： InitStack(&S)

操作结果：构造一个空栈S。 DestroyStack(&S)

初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(&S)

初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S)

初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S)

初始条件：栈S已存在。

操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 GetTop(S，&e)

初始条件：栈S已存在。

操作结果：若栈S不空，则以e返回栈顶元素。 Push(&S， e)

初始条件：栈S已存在。

操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(&S，&e)

初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse（S，visit（）） 初始条件：栈S已存在。

操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。} ADT Stack

（2）迷宫的抽象数据类型

2

数据结构课程设计

ADT maze{

数据对象：D={ai,j| ai,j∈{ '

','#','@','*'},0<=i<=m+1,0<=j<=n+1,m,n<=10}

数据关系：R={ROW,COL} 基本操作：

InitMaze(&M,a,row,col)

初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。

操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符‘#’表示障碍，并在迷宫四周加上一圈障碍。

MazePath(&M)

初始条件：迷宫M已被赋值。

操作结果：若迷宫M中存在一条通路，则按以下规定改变迷宫M的状态：以字符’*’表示路径上的位置，字符‘@’表示“死胡同”，否则迷宫的状态不变。

PrintMaze（M）

初始条件：迷宫M已存在。

操作结果：以字符形式输出迷宫。 } ADT maze

2、整体框架

本程序包含三个模块

（1）栈模块——实现栈抽象数据类型 （2）迷宫模块——实现迷宫抽象数据类型 （3）主程序模块：

void mian() {

初始化； Do{

接受命令； 处理命令；

}while(命令!=“退出”)； }

3

数据结构课程设计

各模块之间的调用关系如图一：

图一：调用关系图

函数的调用关系图反映了程序的层次结构如图二：

图二 ：函数的调用关系图

4

数据结构课程设计

三、 详细设计

源程序:

#include #include #include

#define MAXLEN 10//迷宫包括外墙最大行列数目 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

typedef int Status; // 坐标位置类型 typedef struct{ int r,c;

} PosType;//迷宫中r行c列的位置

//迷宫类型

typedef struct { int r; int c;

char arr[MAXLEN][MAXLEN];//可取' ','*','@','#' }MazeType;

typedef struct{

//int step; // 当前位置在路径上的“序号” PosType seat; //当前的坐标位置 int di; //往下一坐标位置的方向 }SElemType;

//结点类型

typedef struct NodeType{ SElemType data; NodeType *next; }NodeType,*LinkType;

5

数据结构课程设计

//栈类型

typedef struct { LinkType top; int stacksize; }SqStack;

PosType start; PosType end; MazeType maze; bool found;

//创建栈

Status InitStack(SqStack &S) {

S.top=(LinkType)malloc(sizeof(NodeType)); S.top->next=NULL; S.stacksize=0; return OK; }

//进栈

Status Push(SqStack &S,SElemType &e) {

LinkType p;

p=(NodeType*)malloc(sizeof(NodeType)); p->data=e;

p->next=S.top; S.top=p;

S.stacksize++; return OK; }

//判断是否为栈空

Status StackEmpty(SqStack S) {

if(S.top->next==NULL) return OK; return ERROR;

6

数据结构课程设计

}

//出栈

Status Pop(SqStack &S,SElemType &e) {

LinkType p;

if(StackEmpty(S)) return ERROR; p=S.top; e=p->data;

S.top=S.top->next; S.stacksize--; free(p); return OK; }

//销毁栈

Status DestroyStack(SqStack &S) {

LinkType p;

while(S.top!=NULL) {

p=S.top;

S.top=S.top->next; free(p); }//一个一个删除

if(S.top==NULL) return OK; else return ERROR; }

//曾走过但不是通路标记并返回OK

Status MarkPrint(MazeType &maze,PosType curpos) {

maze.arr[curpos.r][curpos.c]='@';//\"@\"表示曾走过但不通 return OK; }

//曾走过而且是通路标记并返回OK

7

数据结构课程设计

Status FootPrint(MazeType &maze,PosType curpos) {

maze.arr[curpos.r][curpos.c]='*';//\"*\"表示可通 return OK; }

//选择下一步的方向

PosType NextPos(PosType &curpos,int i) {

PosType cpos; cpos=curpos;

switch(i){ //1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1; break;

case 2 : cpos.r+=1; break;

case 3 : cpos.c-=1; break;

case 4 : cpos.r-=1; break; }

return cpos; }

//判断当前位置是否可通

Status Pass(MazeType &maze, PosType curpos) {

if(maze.arr[curpos.r][curpos.c]==' ') return TRUE; else return FALSE; }

//创建迷宫

//按照用户输入的二维数组（0或1），设置迷宫maze的初值，包括加上边缘一圈的值

void InitMaze(MazeType &maze, char a[MAXLEN][MAXLEN], int row, int col)

{

8

数据结构课程设计

maze.r=row; maze.c=col;

for(int i=0;i<=col+1;i++){ a[0][i]='1'; a[row+1][i]='1'; }

for(i=0;i<=row+1;i++){ a[i][0]='1'; a[i][col+1]='1'; }

for(i=0;i<=maze.r+2;i++){

for(int j=0;jif(a[i][j]=='1') maze.arr[i][j]='#'; else maze.arr[i][j]=' '; } } }

//求迷宫路径的伪码算法：

Status MazePath(MazeType &maze,PosType start,PosType end) {

//求解迷宫maze中，从入口start到出口end的一条路径，若存在，返回TRUE,否则返回FALSE

PosType curpos; SqStack S; SElemType e; InitStack(S);

curpos=start;//设定“当前位置”为“入口位置” //curstep=1; //探索第一步 found=false; do{

if(Pass(maze,curpos)) {

//当前位置可以通过，即是未曾走到过的通道块留下足迹 FootPrint(maze,curpos);//做可以通过的标识

9

数据结构课程设计

//e.step=curstep; e.seat=curpos;

e.di=1; //为栈顶元素赋值

Push(S,e); //加入路径

if(curpos.r==end.r && curpos.c==end.c) found=true;//如果到达终点返回true

else{

curpos=NextPos(curpos,1);//下一位置是当前位置的东邻 } }

else //当前位置不能通过 if(!StackEmpty(S)){ Pop(S,e);

while(e.di==4 && !StackEmpty(S)){

MarkPrint(maze,e.seat); //留下不能通过的标记 Pop(S,e); }

if(e.di<4){

e.di++; //换下个方向

Push(S,e); //

curpos=NextPos(e.seat,e.di); //进行探索 } }

}while(!StackEmpty(S)&&!found); DestroyStack(S); return found; }

//将标记路径信息的迷宫（字符型方阵）输出到终端(包括外墙)

void PrintMaze(MazeType &maze) {

for(int i=0;i<=maze.r+2;i++){ for(int j=0;j<=maze.c+2;j++){

printf(\" %c\输出迷宫 }

10

数据结构课程设计

printf(\"\\n\"); } }

//系统初始化

void Initialization() {

system(\"cls\");

printf(\" welcome to the game!!! \"); printf(\"\\n************************************************\"); printf(\"\\n*创建迷宫--c 执行迷宫--m 输出迷宫--p 退出--q*\"); printf(\"\\n************************************************\"); printf(\"\\n\\n 操作:-\"); }

//读入操作命令符，显示提示信息 void ReadCommand(char &cmd) { do{

if(cmd=='c') {

printf(\"\\n******************************************\"); printf(\"\\n*选择操作 :执行迷宫--m *\"); printf(\"\\n* 退出--:q *\");

printf(\"\\n******************************************\"); printf(\"\\n\\n 操作:-\"); }

else if(cmd=='m'){

printf(\"\\n******************************************\"); printf(\"\\n*选择操作 :输出迷宫--p *\"); printf(\"\\n* 退出--:q *\");

printf(\"\\n******************************************\"); printf(\"\\n\\n 操作:-\"); }

else if(cmd=='p'){

printf(\"\\n******************************************\"); printf(\"\\n*选择操作 :执行迷宫--c *\");

11

数据结构课程设计

printf(\"\\n* 退出--:q *\");

printf(\"\\n******************************************\"); printf(\"\\n\\n 操作:-\"); }

cmd=getchar();

}while(!(cmd=='c'||cmd=='m'||cmd=='p'||cmd=='q')); }

//解释cmd--具体执行 void Interpre(char cmd) {

switch(cmd){ case 'c':{

int rnum, cnum, i=0,m=1,n=1; char a2[MAXLEN][MAXLEN]; char input[1]; char data[1000];

printf(\"\\n请输入迷宫数据文件名！\\n\"); scanf(\"%s\ FILE *fp;

fp=fopen(input,\"r\"); if(!fp) {

printf(\"\\n不能打开文件\\n\"); break; }

while(!feof(fp)) {

fscanf(fp,\"%s\ if(i==0) {

rnum=(int)data[i]-(int)'0'; }

if(i==1) {

cnum=(int)data[i]-(int)'0'; }

12

数据结构课程设计

if(i>=2) {

if(n>cnum){m++;n=1;} a2[m][n]=data[i]; n++; } i++; }

fclose(fp);

InitMaze(maze, a2, rnum, cnum); printf(\"\\n迷宫建立完成！！\\n\"); break; }

case 'm':{

printf(\"\\n请输入迷宫入口的坐标，以空格为间隔:--\"); scanf(\"%d %d\

printf(\"\\n请输入迷宫出口的坐标，以空格为间隔:--\"); scanf(\"%d %d\ MazePath(maze, start, end); break; }

case 'p':{ if(found) {

printf(\"\\n求解迷宫的结果如下--\\n\"); PrintMaze(maze); }

else printf(\"\\n找不到路径！\\n\"); } } }

void main() {

char cmd;

Initialization(); do{

13

数据结构课程设计

ReadCommand(cmd); //读入一个操作符命令 Interpre(cmd); //解释执行命令操作符 }while(cmd!='q'); }

四、 调试分析及测试

1、调试分析：

（1）本程序有一个核心算法，即求迷宫的路径，在调试的时候，出现了两个问题：没有想到要用‘@’记号，导致迷宫走不出来；没有设置‘found’，

14

数据结构课程设计

不知何时跳出。

（2）原本栈的元素e中除了di—往下一坐标位置的方向和seat—当前的坐标位置，还有一个step—当前位置在路径上的序号，后来发现step没什么用，就删掉了。

（3）函数ReadCommand中，cmd=getchar();的位置找不准，最后是试出来的。

（4）调试的时候多次出现，没有错误，但是dos环境下就是执行不起来，所以采用了一些输出变量，判断到底是哪里出了问题。

（5）本程序中三个主要的算法：InitMaze，MazePath和MarkPrint的时间复杂度均为O（m*n）, 本程序的空间复杂度也为O（m*n）（栈所占最大空间）

2、使用说明和运行结果：

（1）首先以文件形式输入迷宫数据，如图三：

图三

（2）进入演示程序后，会出现以下界面如图四：

图四

（3）进入“创建迷宫”的命令后，即提示输入迷宫数据的文件名，结束符为“回车符”，该命令执行之后输出“迷宫建立完成”，且输出下面可执行的操作。如图五：

15

数据结构课程设计

图五

（4）进入“执行迷宫”的命令后，即提示输入迷宫入口，出口的坐标，结束符为“回车符”，该命令执行之后表示迷宫路径已寻找完成或未找到路径。请注意：若迷宫中存在路径，执行此命令后，迷宫状态已经改变，若要重复执行此命令，需重新输入迷宫数据。如图六：

图六

（5）进入“输出迷宫”的命令后，即输出迷宫求出路径之后的状态。‘#’表示障碍，‘@’ 表示曾走过但不通，‘*’表示路径。如图七：

16

数据结构课程设计

图七

（6）进入“退出”的命令后，按任意键结束。如图八：

图八

3、缺点与改进：

（1）在定义函数Mazepath的时候，开始的循环语句的结束条件不对，没有出路时，导致一直出现了不正确的结果，最后没有新位置入栈，则返回上一个位置，否则没有路径。

（2）只是以文件形式输入迷宫 ，如果迷宫数据量大时，要先建好文件还是很浪费时间，如果以随机产生函数自动产生迷宫会更好 。

五、 个人工作及创新

为了准备这次课程设计我查找了很多的资料，对于迷宫问题的求解中迷宫的产生方式有很多的不同，有的是直接输入迷宫，有的是用文件输入，有

17

数据结构课程设计

的是随机函数产生，我的课设是参考了用文件输入的方法，这样做相比直接输入迷宫操作要更简单。当然用随机函数产生迷宫 比如用：

for (i = 0; i < MAX_ROW; i++) for(j = 0; j < MAX_COL; j++)

{ maze[i][j] = (int) (rand() % 2); } maze[1][0] = 1; /* start point */

maze[MAX_ROW - 1][MAX_COL - 2] = 1; /* end point */}

这样产生迷宫要更加的方便。结果也有不确定性，可能可以有通路也可能没有。

对于迷宫的求解都是采用的“穷举求解”的方法，用到了一些栈的知识。 把以前学过的栈的基本操作实际应用了一番也使有了更加清楚的认识。 在求解迷宫的算法中，先设定当前位置的初值为入口位置，然后

Do{

若当前位置可通，

则｛将当前位置插入栈顶；

若该位置是出口位置，则结束；

否则切换当前位置的东邻方块为新的当前位置； ｝ 否则｛

若栈不为空且栈顶位置尚有其它方向未被探索，

则设定新的当前位置为延顺时针方向旋转找到的栈顶位置的下 一相邻块；

若栈不空但栈顶位置四周均不通， 则｛删去栈顶位置；

若栈不为空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；｝ ｝ }

求解迷宫的算法大概就是这么个思路。

六、 小结

要能很好的掌握编程，仅仅通过几个简单的程序的编写是无法达成的，更需要的是大量的积累和深入研究才可能。在程序的编写中也不能一味的向

18

数据结构课程设计

已有的程序进行模仿，而要自己去探索，去寻找最好的解决方法，只有带着问题去反复实践，才能更熟练的掌握和运用，当然，对现有的程序也要多去接触，因为有些程序是我们在短时间内无法想出来的，我们也应该去参考别人的作品，这样可以节约时间获得更多的知识。最重要的是持之以恒，要经常性的复习原来接触到的程序，这样才能保证我们有足够的经验去面对程序问题。

参考文献

[1]. 严蔚敏，吴伟民数据结构（C语言版）.清华大学出版社.2007 [2]. 严蔚敏，数据结构题集（C语言版）.清华大学出版社.2007

19

数据结构课程设计

[3]. 谭浩强 ，C程序设计（第四版）.清华大学出版社.2007

20