迷宫问题课程设计报告

第一章: 设计问题描述与分析.......................................................................................................1 1.1. 课程设计内容........................................................................................................................1

1.2. 问题分析..................................................................................................................................1

1.3．功能实现.................................................................................................................................2 1.4．运行环境.................................................................................................................................3 第二章: 算法设计与流程图...........................................................................................................4 2.1.主函数的流程图.....................................................................................................................4 2.2.概要设计...................................................................................................................................5 2.4 详细设计...................................................................................................................................6

2.4.1. 节点类型和指针类型.....................................................................................................6 2.4.2. 迷宫的操作......................................................................................................................6

（1）生成迷宫.............................................................................................................6 （2）打印迷宫矩阵与字符图形....................................................................................7 （3）迷宫求解路由求解操作........................................................................................7

（4）打印迷宫通路坐标................................................................................................8 (5)输出迷宫通路的字符图形.....................................................................................8 2.4.3. 主函数............................................................................................................................9

第三章：调试分析...........................................................................................................................10 第四章：使用说明......................................................................................................................11 第五章：测试结果......................................................................................................................12 附录1...................................................................................................................................................19 附录2.............................................................................................................................................19

程序设计综合课程设计

第一章：设计问题描述与分析

1.1.课程设计内容：

该系统是由C 语言编写的生成一个N×M(N行M列)的迷宫，完成迷宫的组织和存

储，并实现迷宫路由算法。基本要求1、 N和M是用户可配置的，缺省值为50和50。2、迷宫的入口和出口分别在左上角和右下角。

提示：（1）可以使用二维数组maze[M+2][N+2]表示迷宫，其中M,N为迷宫的行、列数，当元素值为0时表示该点是通路，当元素值为1时表示该点是墙。老鼠在每一点都有4种方向可以走，可以用数组move[4]来表示每一个方向上的横纵坐标的偏移量，可用另一个二维数组mark[M+2][N+2]记录节点的访问情况。（2）可以选用深度优先算法或广度优先算法实行，迷宫可由自动或手动生成。测试用例应该包含有解迷宫和无解迷宫。

1.2. 问题分析

本程序要求实现迷宫问题的相关操作，包括迷宫的组织和存储，并实现迷宫路由算法（即查找迷宫路径）。程序所能达到的：具体包括迷宫的建立，迷宫的存储（迷宫由自动生成或手动生成），迷宫中路径的查找

迷宫是一个矩形区域，迷宫存在一个入口和一个出口，其内部包含了不能穿越的墙或者障碍。迷宫的建立即是建立这样一个迷宫矩阵，用于存储迷宫信息，包括可穿越的路和不可穿越的墙或者障碍，分别用0表示通路，1表示障碍。对于迷宫矩阵，用m×n的矩阵来描述，m和n分别代表迷宫的行数和列数。这样，则迷宫中的每个位置都可以用其行号和列号来指定。从入口到出口的路径是由一组位置构成的。每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的上、下、左、右的邻居。

为了描述迷宫中位置（i ，j）处有无障碍，规定，当位置（i ，j）处有一个障碍时，其值为1，否则为0.这样迷宫就可以用0、1矩阵来描述，在构造矩阵时，为了操作方便会将矩阵四周置为1（不通）。

对于查找迷宫路由问题

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

1

程序设计综合课程设计

径，搜索工作结束。否则，考察其上、下、左、右位置上的邻居是否是障碍，若不是就移动到这个相邻位置上，然后对于这个位置开始搜索通往出口的路径。如果不成功，就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索出现重复，则将已搜索过的位置标记为1。同时为保留过搜索的痕迹，在考察相邻位置之前，将当前位置保存在一个堆栈中，如果所有相邻的非障碍位置均被搜索过，且未能找到通往出口的路径，则表明不存在从入口到出口的路径。且对于此，实现的是深度优先遍历算法，如果查找到路径，则为从入口到出口的路径。

下面实现如何利用堆栈实行深度优先遍历算法进行迷宫最短路径的查找。

以矩阵 1 1 1 1 1 1 1

1 0 0 1 0 1 1

1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1

首先，将位置（1，1）放入堆栈中，从它开始搜索，标记。由于其只有一个非障碍位置，所以接下来移动到（1，2），防止稍后的搜索再经过这个位置。

从（1，2）移动到（2，2），放入堆栈中，（2，2）存在（2，3）、（3，2）两个可移动位置。标记已被搜索过，对于每一个非障碍位置，它的相邻非障碍节点均入队列，实现了深度优先遍历算法。所以如果存在路径，则从出口处节点的位置，逆序则可以找到其从出口到入口的通路。实现了查找路径。

1.3．功能实现：

1、数据输入形式和输入值的范围：生成迷宫时可选择手动或者自动生成；手动输入迷宫矩阵时以0 表示无障碍为通路，1 表示该点有障碍为墙。所有输入中，元素的值均为整数。

2、结果的输出形式：当完成迷宫生成后，会提示输入入口与出口，进入迷宫路由查找算法，如找到出口，则打印出路径矩阵坐标，并显示显示迷宫生成图形 3、测试数据：

a、进入界面，选择2，自动生成 b、输入入口与出口

2

程序设计综合课程设计

c、查看结果

1.4．运行环境：

运行环境为DOS

3

程序设计综合课程设计

第二章：算法设计与流程图

2.1.主函数的流程图： 判断入口是否为通路 Y N N 循环结束，无通路 将该位置入栈，并标记为1 栈不为空且栈顶非出口 Y Y N Y 栈顶位置上面可通？ N Y 栈顶位置右面可通？ N 栈顶位置左面可通？ N 栈顶出栈 循环结束 栈顶位置下面可通？ 找出通路，链栈内即为通路 N 栈顶为出口？ Y Y

图1迷宫算法流程图

4

程序设计综合课程设计

2.2概要设计

1、为了实现上述功能，需要：①构造一个二维数组maze[M+2][N+2]用于存储迷

宫矩阵,构造一个二维数组backup[M+2][N+2]用于备份迷宫矩阵；②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值并备份；③将构造一个堆栈用于存储迷宫路由；④建立迷宫节点struct Mlink，用于存储迷宫中每个访问过的节点。⑤实现迷宫路由算法，用深度优先遍历实现查找迷宫路径。如找到路径则显示路径，否则提示无通路。同时显示生成迷宫。⑥在屏幕上显示操作菜单。

2、本程序包含6 个函数： ( 1 )主函数 main( ) ( 2 )生成迷宫函数 create( ) ( 3 )打印迷宫矩阵与图形函数prin( ) ( 4 )寻找迷宫路由Mazepath( ) ( 5 )输出迷宫通路坐标printonglu1( ) ( 6 )输出迷宫生成图形printonglu2( ) 各函数之间的关系如下图（图2）所示：

函数关系图：

create( )

prin( )

main() Mazepath( )

printonglu1( )

printonglu2( )

图 2各函数间关系图

5

程序设计综合课程设计

2.3详细设计

实现概要设计中定义的所有数据类型，对各个操作给出伪代码算法。对于主程序

和各个模块也给出相应的伪代码算法。 1.节点类型和指针类型

迷宫矩阵类型：

Mlink *stack; 全局变量堆栈，存储迷宫通路 int abc[M+2][N+2] 辅助数组 int maze[M+2][N+2]; 迷宫矩阵

int backup[M+2][N+2]; 备份矩阵，便于操作，定义为全局变量 迷宫中节点类型及队列类型：

struct Mlink { int row ,col ; struct node * next;} Mlink; 2.迷宫的操作

(1)生成迷宫

void create(int maze[][N+2]) {定义变量i,j,flag;

srand( (unsigned)time( NULL ) ) 以时间产生随机种子 利用for初始化迷宫矩阵与备份矩阵，包括边界全置为1 利用for将迷宫置为0

选择迷宫生成方式1为手动生成，2为自动生成，输入值并赋给flag flag=1{

以i , j 控制迷宫中行列数的循环输入

以0 表示通路，以1 表示障碍,给maze[i][j]赋值，不包括边界。 循环结束，完成迷宫生成} flag=2{

定义变量i1，j1用以接收随机值

以i , j 控制迷宫中行列数的循环赋值操作 以0 表示通路，以1 表示障碍 用for(c=1;c<=M*N;c++) {

6

程序设计综合课程设计

i1=(int)(rand()%M)+1;

j1=(int)(rand()%N)+1; maze[i1][j1]=int(rand()%2);

}随机定位矩阵一点，给maze[i1][j1]赋一个随机值，这样可以增加迷

宫通路的概率，循环结束，完成迷宫生成}

以i , j 控制迷宫中行列数的循环赋值操作，将maze[][]备份到backup[][];} (2)打印迷宫矩阵与字符图形 void prin(int maze[][N+2]){ 此函数主要用于将迷宫矩阵显示出来 定义变量i，j，z； for(z=1;z<=N;z++)

{if(z<10)

printf(\"%d \

else

printf(\"%d\

} 此语句用来标明列号

用 for 控制循环 在第一重循环里，使用语句{ printf(\"\\n\");

if(i<10) printf(\"%d \

else printf(\"%d\以此用来标明行号

以 i, j 控制迷宫中行列数的循环操作，将maze[i][j]显示出来 并用字符□，■分别代表可通与不可通} （3）迷宫求解路由求解操作{ Mlink *p;用以操作堆栈

①入口若不通，return（0）否则下一步 ②将其入栈

③未找到出口并且堆栈不空{

1）栈顶位置以下是否可通，可通则返回②，否则2）， 2）栈顶位置以上是否可通，可通则返回②，否则3)，

7

程序设计综合课程设计

3）栈顶位置以右是否可通，可通则返回②，否则4)，

4）栈顶位置以左是否可通，可通则返回②，否则出栈并返回，} ④如果栈顶为出口，return （1）；否则return （0）；} （4）打印迷宫通路坐标 void printonglu1(){ Mlink *q;用以操作堆栈 q=stack q不空{

输出q指向的坐标 q=q->next} }

(5)输出迷宫通路的字符图形 void printonglu2(){

此函数根据堆栈内栈顶与“次栈顶”的位置关系决定输出字符↑，←，→或↓，其中2=↑，3=←，4=→，5=↓所有的操作都是在备份矩阵backup[][]上。

出口位置输出㊣

int i，z，j；Mlink *p=stack； p不空{

if(p->row>p->next->row) backup[p->next->row][p->next->col]=5; 下一位置在下

else if(p->rownext->row) backup[p->next->row][p->next->col]=2;下一位置在上

else if(p->col>p->next->col) backup[p->next->row][p->next->col]=4;下一位置在右

else ; 下一位置在左}

利用for循环，i，j为循环控制变量输出备份矩阵backup[][]{ 为0是输出“□” 为1是输出“■”

8

程序设计综合课程设计

为2是输出“↑” 为3是输出“←” 为4是输出“→” 为5是输出“↓” 为6是输出“㊣”}

另外在输出语句上，与矩阵输出相同，标明了行号与列号（该功能为王教授所要求而后加的） } 3.主函数

void menu(){

定义迷宫数组矩阵maze[M+2][N+2]

定义辅助数组abc[M+2][N+2] 以用来在可以在第一次产生迷宫中重复选择入口与出口

定义变量k以用来控制循环

定义整型变量 x1，y1 ，用于存储入口。 定义整型变量 x2，y2 ，用于存储出口。 定义整型变量x用于接收mazepash的返回值。 输入入口与出口。 如果x=1则条用函数{ printonglu1(); printonglu2();} 否则提示无通路。} 界面开始会显示： 1,手动建立 2,自动建立

按提示操作，输入入口与出口，回车即会看到结果

9

程序设计综合课程设计

第三章：调试分析

在调试过程中，开始用堆栈实现了路径的查找并调试成功，但输出的结果仅仅只是路径坐标，看起来不形象，于是想到了用字符来表示图形并标出通路，虽然不是太完美，但比之之前好好多了

在实现这一算法过程，注意将访问过的节点进行标记，并且在遍历过程中对矩阵数组是“破坏性”遍历，在算法完成后，矩阵已被破坏，堆栈中会存用路径，为了再原矩阵中用字符图形表示出通路，在建立矩阵后会迷宫矩阵备份一下，当然或许会有更好的处理方法。

1 0

程序设计综合课程设计

第四章：使用说明

程序名为迷宫.exe，运行环境为DOS，程序执行后显示： 建立迷宫矩阵(选择1或者2)： 1,手动建立 2,自动建立进 请输入您的选择：

在输入选择后输入数字选择执行不同的迷宫建立。按要求输入入口与出口

1 1

程序设计综合课程设计

第五章：测试结果

1.主页面

图3 主页面

1 2

程序设计综合课程设计

2.选择自动建立

图4 迷宫自动生成中

1 3

程序设计综合课程设计

3，自动生成迷宫，上面为数组矩阵，其中0可通，1障碍。下面为字符图形，其中白色可通，黑色障碍

图5 打印出的迷宫矩阵与迷宫图形

1 4

程序设计综合课程设计

4，根据提示输入入口与出口

图6 输入入口与出口

1 5

程序设计综合课程设计

5，回车后输出路径

图7 打印出的迷宫路径

1 6

程序设计综合课程设计

6，输入一个非“0”继续

图8 输入非“0”继续走该迷宫

1 7

程序设计综合课程设计

7，输入入口与出口，无通路

图9 无通路

1 8

程序设计综合课程设计

附录1：

附录2：

源代码：

#include #include #include #include #define M 20 #define N 20

typedef struct node//堆栈结构 {

int row; //行 int col; //列 struct node * next;

}Mlink;

Mlink *stack;//定义一个栈 int backup[M+2][N+2]; //备份数组

/*********************************建立迷宫矩阵**************************/

void create(int maze[][N+2])//建立迷宫 {

int i,j,flag;

srand( (unsigned)time( NULL ) ); //以时间产生随机种子 for(i=0;i<=M+1;i++)

for(j=0;j<=N+1;j++)

maze[i][j]=1;//将四周置为1

1 9

程序设计综合课程设计

for(i=1;i<=M;i++) for(j=1;j<=N;j++) { }

printf(\"建立迷宫矩阵(选择1或者2)：\\n1,手动建立\\n2,自动建立\\n

maze[i][j]=0;//初始化矩阵 backup[i][j]=0;//初始化备份矩阵

请输入您的选择：\\n\");

if(flag==2){ //自动建立迷宫

int c,i1,j1;

for(c=1;c<=M*N;c++){ //矩阵初始为“0”，随机选

scanf(\"%d\if(flag==1)//手动建立迷宫 { }

printf(\"手动建立迷宫矩阵(0表示可通1表示障碍):\\n\"); for(i=1;i<=M;i++)

for(j=1;j<=N;j++)

scanf(\"%d\

择位置赋予一个随机的0或1， i1=(int)(rand()%M)+1;

j1=(int)(rand()%N)+1;

maze[i1][j1]=int(rand()%2); //随机矩阵 按照王教授的要

求这样可以产生更多的“0”即通路

}

2 0

}

printf(\"自动生成中……\\n\"); system (\"pause\");

程序设计综合课程设计

}

for(i=1;i<=M;i++)

for(j=1;j<=N;j++)

backup[i][j]=maze[i][j];//备份数组矩阵

/***************************华丽的分割线*******************************/

/********************************打印迷宫矩阵*****************/ void prin(int maze[][N+2]) {

int i,j;

printf(\"迷宫矩阵如下(0可通)：\\n \"); int z;

for(z=1;z<=N;z++) //在矩阵上方标明列号 {if(z<10)

printf(\"%d \

else }

for(i=1;i<=M;i++) { }

printf(\"\\n迷宫图形如下(白色可通)：\\n\"); printf(\" \");

for(z=1;z<=N;z++) //在图形上方标明列号

2 1

printf(\"%d\

printf(\"\\n\");

if(i<10) printf(\"%d \矩阵左方标明行号 else printf(\"%d\for(j=1;j<=N;j++)

printf(\"%d \

程序设计综合课程设计

}

{if(z<10)

printf(\"%d \

else }

for(i=1;i<=M;i++) { }

printf(\"\\n\");

if(i<10) printf(\"%d \矩阵左方标明行号 else printf(\"%d\for(j=1;j<=N;j++) { }

if(maze[i][j]==0) printf(\"□\"); if(maze[i][j]==1) printf(\"■\"); printf(\"%d\

/*******************************分割线***************************/

int Mazepath(int maze[][N+2],int x1,int x2,int y1,int y2) {

Mlink *p;

if(maze[x1][y1]==0){

p=(Mlink *)malloc(sizeof(Mlink)); p->row=x1; p->col=y1; p->next=NULL;

stack=p; //将入口放入堆栈

maze[stack->row][stack->col]=1;//标志入口已访问

2 2

程序设计综合课程设计

while((!(stack->row==NULL&&stack->col==NULL))&&(!(stack->row==x2&

&stack->col==y2)))//未找到出口并且堆栈不空

{

if(maze[stack->row][stack->col+1]==0)//下面位置可通 { }

else if(maze[stack->row][stack->col-1]==0)//上面可通 {

p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row; p->col=stack->col-1; p->next=stack; //入栈 stack=p;

maze[stack->row][stack->col]=1;//标记已访问 p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row; p->col=stack->col+1;

p->next=stack; //入栈 stack=p;

maze[stack->row][stack->col]=1;//标记已访问

}

else if(maze[stack->row+1][stack->col]==0)//右面可通 {

p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row+1; p->col=stack->col;

p->next=stack; //入栈 stack=p;

maze[stack->row][stack->col]=1;//标记已访问

2 3

程序设计综合课程设计

循环

}

else if(maze[stack->row-1][stack->col]==0)//左面可通 { }

else //不可通 返回上一点 {

if (stack->next!=NULL){//堆栈里布置一个顶点则出栈并返回p=(Mlink *)malloc(sizeof(Mlink)); p->row=stack->row-1; p->col=stack->col;

p->next=stack; //入栈 stack=p;

maze[stack->row][stack->col]=1;//标记已访问

p=stack;

stack=stack->next; //出栈 free(p); //释放空间 }

else //堆栈里只有一个顶点即入口，此时

若释放空间出栈会使循环

{ //控制语句无法比较（因为

stack->col,stack->row都已不存在，)

}

if (stack->row==x2&&stack->col==y2) return (1);

2 4

}

stack->row=NULL; stack->col=NULL; stack->next=NULL;}

程序设计综合课程设计

} }

else return (0);

else return(0);

/****************************输出坐标通路*******************/ void printonglu1() { }

/*******************************分割线**********************/

/**********************输出图形通路**************************/ //2时输出↑，3时输出←，4时输出→，5时输出↓

void printonglu2() {

printf(\"图形通路如下：\\n\"); int z;

2 5

Mlink *q;

printf(\"其中的一条通道为：\\n\");

q=stack;

printf(\"出口<--\"); while (q!=NULL) {

printf(\"(%d%3d)<--\q=q->next;

}

printf(\"入口\\n\");

程序设计综合课程设计

printf(\" \");

for(z=1;z<=N;z++) //图形上方标明列号 {if(z<10)

printf(\"%d \

else } int i,j; Mlink *p; p=stack;

backup[p->row][p->col]=6; while (p->next!=NULL) {

if(p->next->col!=NULL) {

if( p->row > p->next->row ) printf(\"%d\

backup[p->next->row][p->next->col]=5;//下一节点在下

else if(p->rownext->row)

backup[p->next->row][p->next->col]=2;//下一节点在上

else if(p->col>p->next->col)

backup[p->next->row][p->next->col]=4;//下一节点在右

}

for(i=1;i<=M;i++) {

printf(\"\\n\");

2 6

}

else backup[p->next->row][p->next->col]=3;//下一节点在左

else ; p=p->next;

程序设计综合课程设计

}

}

if(i<10) printf(\"%d \图形左方标明行号

else printf(\"%d\for(j=1;j<=N;j++) { }

if(backup[i][j]==0) printf(\"□\"); if(backup[i][j]==1) printf(\"■\"); if(backup[i][j]==2) printf(\"↑\"); if(backup[i][j]==3) printf(\"←\"); if(backup[i][j]==4) printf(\"→\"); if(backup[i][j]==5) printf(\"↓\"); if(backup[i][j]==6) printf(\"㊣\");

void main() {

system(\"color f0\"); //背景该为白色 int k=1;

int maze[M+2][N+2];//迷宫矩阵 create(maze); //建立迷宫

int abc[M+2][N+2],p,q; //备份数组以重复使用迷宫 for(p=0;p<=M+2;p++)

for(q=0;q<=N+2;q++)

abc[p][q]=maze[p][q];

while(k!=0){ int x,x1,x2,y1,y2;

prin(maze); //打印迷宫矩阵 printf(\"\\n输入迷宫入口：\\n\");

2 7

程序设计综合课程设计

} }

scanf(\"%d%d\ printf(\"输入迷宫出口：\\n\"); scanf(\"%d%d\ x=Mazepath(maze,x1,x2,y1,y2); if(x==1) //迷宫可通 {

printonglu1(); //打印坐标通路 printonglu2();//打印图形通路 printf(\"\\n\");

}

else printf(\"无通路！\\n\");//不可通 for(p=0;p<=M+2;p++)

for(q=0;q<=N+2;q++){

backup[p][q]=abc[p][q]; maze[p][q]=abc[p][q];

}

printf(\"输入0结束:\\n\"); scanf(\"%d\

2 8

计算机科学与技术学院

《C高级语言程序设计》课程设计报告

（ 2014 / 2015 学年 第 1 学期）

学生姓名： 张峰耀 学生专业： 软件工程 学生班级： 软件132001班 学生学号： 201320020138 指导教师： 李富萍

2015年01月07日

计算机科学与技术学院

课程设计任务书

课程设计名称 课程设计题目 学生姓名 《C高级语言程序设计》课程设计 迷宫问题 张峰耀 专业班级 软件132001班 学号 201320020138 课程设计任务内容 [问题描述] 本程序要求实现迷宫问题的相关操作，包括迷宫的组织和存储，并实现迷宫路由算法（即查找迷宫路径）。 [基本要求] （1）基本要求1、 N和M是用户可配置的，缺省值为50和50。 （2）迷宫的入口和出口分别在左上角和右下角。 [测试要求] 程序所能达到的具体包括： （1）迷宫的建立。 （2）迷宫的存储（迷宫由自动生成或手动生成）。 （3）迷宫中路径的查找。 指导教师： 时 间： 年 月 日

程序设计综合课程设计

计算机科学与技术学院

课程设计成绩评审表

课程设计名称 课程设计题目 学生姓名 同组人 指导教师 李富萍 设计成绩 《C高级语言程序设计》课程设计 迷宫问题 张峰耀 专业班级 软件132001班 学号 201320020138 评价内容 签 字： 时 间： 年 月 日