数据结构课程设计
深度与广度优先搜索:迷宫问题
目 录
1 设计题目................................................................................................................. 1
2 设计分析................................................................................................................. 1
3 设计实现................................................................................................................. 3
4测试方法.................................................................................................................. 3
4.1测试目的............................................................................................................... 8
4.2 测试输入.............................................................................................................. 8
4.3 正确输出.............................................................................................................. 9
4.4 实际输出.............................................................................................................. 9
4.5 错误原因(若无错误此节可以省略)............................................................ 11
5 分析与探讨........................................................................................................... 11
5.1 测试结果分析.................................................................................................... 11
5.2 探讨与改进........................................................................................................ 11
6 设计小结............................................................................................................... 11
1 设计题目
a)迷宫问题求解的目标:寻找一条从入口点到出口点的通路。(迷宫可表示为一个二维平面图形,将迷宫的左上角作入口,右下角作出口。)例如,可以设计一个8*8矩阵maze[8][8]来表示迷宫,如下所示:
0 1 0 0 0 0 1 1
0 0 0 1 0 0 1 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 1 1 1 1 1 0
1 0 0 1 1 0 0 0
1 0 1 0 0 0 1 1
1 0 1 1 0 1 0 0
左下角maze[0][0]为起点,右下角maze[7][7]为终点;设“0”为通路,“1”为墙,既无法穿越。假设一只老鼠从起点出发,目的为右下角终点,可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。
b)设计程序要求:能自动生成或者手动生成这样一个8*8矩阵;针对这个矩阵,程序判断是否能从起点经过迷宫走到终点。如果不能,请指出;如果能,请用图形界面标出走出迷宫的路径。
2 设计分析
a)首先明确题目中的已知条件:
·迷宫是一个8*8大小的矩阵。
·从迷宫的左上角进入,右下角为迷宫的终点。
·maze[i][j]=0代表第i+1行第j+1列的点是通路;maze[i][j]=1代表该点是墙,无法通行。
·迷宫有两种生成方式:手工设定和自动生成。
·当老鼠处于迷宫中某一点的位置上,它可以向8个方向前进,分别是:“上、下、左、右、左上、左下、右上、右下”8个方向。
·要实现这个程序,首先要考虑如何表示这个迷宫。在实例程序中使用二维数组,maze[N+2][N+2]来表示这个迷宫,其中N为迷宫的行、列数。当值为“0”时表示该点是通路,当值为“1”时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以用行号row和列号col表示。
b)为什么指定maze[N+2][N+2]表示迷宫,而不是使用maze[N][N]来表示迷宫?
·原因是当老鼠跑到迷宫的边界点时就有可能跳出迷宫;而使用maze[N+2][N+2]就可以把迷宫的外面再包一层“1”,这样就能阻止老鼠走出格。
c)老鼠再每一点都有8种方向可以走,分别是:North,NorthEast,East,SouthEast,East,South,SouthWest,West,NorthWest.可以用数组move[8]来表示在每一个方向上的横纵坐标的偏移量,见表2—1。根据这个数组,就很容易计算出沿某个方向行走后的下一点的坐标。
表2—1 8种方向move的偏移量
d)迷宫问题可以用深度优先搜索方法实现。当老鼠当老鼠在迷宫中移动的时候,可能会有多种移动选择方向。程序需要记录并用栈来保存当前点的坐标,然后任意选取一个方向进行移动。由于应用栈保存了当前通道上各点的坐标,所以当前各方向上都走不通时可以返回上一个点,然后选择另一个方向前进。
·可定义element结构用于存储每一步的横纵坐标和方向。
typedef struct{
short int row;
short int col;
short int dir;
}element;
Element stack[MAX _STACK_SIZE];
根据表2—1可推算出每次移动后的坐标。设当前的坐标是(row,col),移动的方向是dir,移动后的点是next,则有
next_row=row+move[dir].vert;
next_col=col+move[dir].horiz;
·可用另一个二维数组mark[N+2]来记录哪些点已经被访问过。当经过点maze[row][col]时,相应地将mark[row][col]的值从0置为1。
e)本程序支持自动生成迷宫。利用random(2)函数可随机产生0或1,来支持迷宫的自动生成。注意maze[N][N]和maze[1][1]一定要等于0,因为他们分别是起点和终点。
f)如果找到了一条走出迷宫的路径,则需要在屏幕中打印出走出迷宫的信息。这里要用到graphics.h。为画出效果图,可使用circle()函数画圆,outtexttxy()函数标记文字,并用line()函数来划线。
g)程序的主要函数如下:
·函数void add(int*top,element item),将当前步的信息item压入到作为全局变量的栈stack(栈顶为top)中。
·函数element delete(int * top),返回stack中栈顶的元素。
·函数void path(void),采用深度优先搜索算法,首先取出栈顶元素作为当前点选择一个方向前进到下一个点(如果能走得话);然后,将下一个点压入栈,并将二维数组mark中对应的值改为1,表示该点已经走到了。反复执行上面两步,当走到一个点不能再走下去了(已经尝试了各个方向并失败),并且这个点不是终点,则这个点的上一个点会从栈中被跑抛出,从而“回朔”到上一点;当遇到终点时,程序结束,找到一条路径;当在程序循环过程中遇到栈为空,则说明该迷宫根本无法走到终点。
3 设计实现
/******This program can be compiled under VC6.0******/
#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>
#include<time.h>
#include<conio.h>
#define N 8
#define MAX_STACK_SIZE N*N /*最大栈容量 */
#define TRUE 1
#define FALSE 0
#define LEN (300/N)
/******结构体记录每一步的横坐标,纵坐标和方向******/
typedef struct {
short int row;
short int col;
short int dir;
}element;
element stack[MAX_STACK_SIZE];
/******结构体记录水平和垂直的偏移量******/
typedef struct {
short int vert;
short int horiz;
}offsets;
offsets move[8]; /* 8个方向的move */
int maze[N+2][N+2]; /*二维数组记录迷宫*/
int mark[N+2][N+2]; /*记录迷宫中每点是否可到达*/
int EXIT_ROW = N, EXIT_COL = N;
/******在栈中加入一个元素******/
void add(int *top, element item){
if (*top >= MAX_STACK_SIZE - 1){
printf("The stack is full!\n");
return;
}
stack[++*top] = item;
}
/******返回栈中顶部的元素******/
element delete_top(int *top){
if (*top == -1){
printf("The stack is empty ! \n");
exit(1);
}
return stack[(*top)--];
}
/******输出走出迷宫的路径******/
void path(void){
int i, j, k, row, col, next_row, next_col, dir, found = FALSE;
int gd=VGA;
int gm=VGAHI;
/*--------------------------------------------------------------*\
| i ---> 用来循环计数 |
| row , col ---> 当前位置的坐标 |
| next_row ---> 移动后的位置的横坐标 |
| next_col ---> 移动后的位置的纵坐标 |
| dir ---> 移动的方向 |
| found ---> 标志路径是否发现 |
\*--------------------------------------------------------------*/
element position;
int top = 0;
mark[1][1] = 1; /* maze[1][1]已经被走过了*/
stack[0].row = 1;
stack[0].col = 1;
stack[0].dir = 1; /*第一步的状态*/
move[0].vert = -1; move[0].horiz = 0 ;
move[1].vert = -1; move[1].horiz = 1 ;
move[2].vert = 0 ; move[2].horiz = 1 ;
move[3].vert = 1 ; move[3].horiz = 1 ;
move[4].vert = 1 ; move[4].horiz = 0 ;
move[5].vert = 1 ; move[5].horiz = -1;
move[6].vert = 0 ; move[6].horiz = -1;
move[7].vert = -1; move[7].horiz = -1;
initgraph(&gd,&gm,""); /* 指定了八个方向*/
/*---------------------------------------------------------------------------*\
| 主要算法描述: |
| 当stack不为空,移动到stack顶部的位置 |
| 试着向各个方向移动,如果可以移动就移动到 |
| 下一个位置并把它标志成1。 |
| 然后保存状态并加入到stack中 |
| 如果路径被破坏,或者不存在,就将其删除 |
| 并返回到上一点继续遍历其他方向的点 |
| 直到一条路径被发现。 |
\*-----------------------------------------------------------------------------*/
while ( top > -1 && !found) { /*stack不为空*/
position = delete_top(&top); /*删除stack中的元素*/
row = position.row;
col = position.col;
dir = position.dir;
while (dir < 8 && !found) {
next_row = row + move[dir].vert;
next_col = col + move[dir].horiz;
if (next_row == EXIT_ROW && next_col == EXIT_COL)
found = TRUE; /*发现路径*/
else if ( !maze[next_row][next_col] &&
!mark[next_row][next_col])
/*如果这点没有被走过并且可以走*/
{
mark[next_row][next_col] = 1; /*设成1*/
position.row = row;
position.col = col;
position.dir = ++dir;
add(&top, position); /*加入到stack*/
row = next_row;
col = next_col;
dir = 0; /* 移动到下一个点 */
}
else ++dir; /*尝试其他方向*/
}
}
for(j=1;j<=N;j++)
for(k=1;k<=N;k++){
setcolor(WHITE);
circle(j*LEN,k*LEN,10);
setcolor(MAGENTA);
outtextxy(j*LEN-2,k*LEN-2,maze[k][j]?"1":"0");
}
if (found){ /* 如果发现路径,则打印出来*/
outtextxy(20,10,"The path is:");
setcolor(YELLOW);
for (i=0; i <top;i++){
line(stack[i].col*LEN, stack[i].row*LEN,stack[i+1].col*LEN,stack[i+1].row*LEN);
}
line(stack[i].col*LEN, stack[i].row*LEN,col*LEN,row*LEN);
line(col*LEN, row*LEN,EXIT_COL*LEN,EXIT_ROW*LEN);
}
else outtextxy(20,10,"The maze does not have a path");
/* 否则打印不存在信息*/
}
void main(){
int i, j, c;
srand(time(0));
system("cls");
for (i=0;i<N+2;i++)
{
maze[0][i]=1;
maze[i][0]=1;
maze[N+1][i]=1;
maze[i][N+1]=1;
} /* 将迷宫的四周设为1(墙壁) */
printf("Would you like to input the maze by youself?\nYes or No?");
c = getchar();
if(c=='Y' || c== 'y'){
printf("Enter the %d * %d maze:\n",N,N); /*手动输入*/
for (i=1; i<N+1; i++)
for(j=1; j<N+1; j++){
scanf("%d",&maze[i][j]);
}
}
else{
printf("The maze is created by the computer:\n");
for (i=1; i<N+1; i++)
for(j=1; j<N+1; j++){
maze[i][j]=rand()%2;
}
maze[N][N] = 0;
maze[1][1] = 0;
for(i=1;i<N+1;i++){
for(j=1;j<N+1;j++)
printf("%3d",maze[i][j]);
printf("\n");
}
}
path(); /* 调用函数path() */
getch();
}
4测试方法
4.1测试目的
针对迷宫生成方式不同,本程序的测试分为两类:手动输入迷宫测试和计算机自动生成迷宫测试。另外,根据测试用例不同也可以分为两类:有解迷宫测试无解迷宫测试。即检查是否可以自动生成或手动生成一个m*n的迷宫,并判断生成的迷宫图是否可从入口不经过重复点通过路“0”走向出口。
4.2 测试输入
a)按Y或y手动生成迷宫矩阵(有解迷宫):先输入8*8的矩阵
b)按任意键自动生成迷宫矩阵(有解迷宫):
c) 按任意键自动生成迷宫矩阵(无解迷宫):
4.3 正确输出
不管是手动生成还是自动生成迷宫,走数字为零的点且不经过重复点走向出口。如果没有通路则失败。
4.4 实际输出
a)给出的迷宫路线如图:
b)对于自动生成电脑路线(有解迷宫),给出的迷宫路线:
c) 对于有些自动生成的迷宫(无解迷宫),可能不可以完成走迷宫:
4.5 错误原因
走迷宫失败原因是从入口通向出口的路上被墙“1”给堵住了,则无法走向出口。即没有一条从入口到出口的通路。
5 分析与探讨
5.1 测试结果分析
a.手动生成的迷宫图是由一个8*8的矩阵构成的,这是由最大栈容量MAX_STACK_SIZE决定的,0为路,1为墙,并且可以上、下、左、右、左上、左下、右上、右下行走,且不会走已经走过的点。最终从左上入口点开始到右下出口点结束。
b.自动生成的迷宫图同样遵循迷宫行走法则。
5.2 探讨与改进
上述的实验代码及实验结果都是在vc中进行的。因为turbo c现在有很多人不用且我习惯用的是vc,所以我用vc写。教学中给的代码适合在turbo C中进行,从源代码到现在代码的改进以及为完成实验要求。需先在vc中安装graphics.h和graphics.lib文件。并修改一些方法如random(2)改成rand()%2,clrscr()改成system(“cls”),randomize()改成srand(time(0)),delete改为delete_top,并需加入time.h和conio.h文件。由此可见c和c++还是有区别的。安装了graphics文件后,vc能更好的绘制图。且最终的结果也是对的。
6 设计小结
在这次为期五个半天的课程设计里,也让我从中有所收获。虽说是五个半天,但在课后还是花了不少时间。
首先就由于用的是C语言编写,所以又拿起了大一的C教材课本,以此来弥补一些知识,但最主要的还是数据结构教材。看教材中的程序时,发现一个程序设计就是算法与数据结构的结合体,看程序有时都看不懂,更别提自己编译了,觉得自己在这方面需要掌握的内容还有很多狠多。
在这次课程设计中,碰到了一个可以说是很巨大的难题,在编译的时候,用了很多编译软件,可是就是不行,“#include<graphics,h>”,这其实是TC里的一个图形库,在visual C里编译时不行的,会显示有一个错误,但在turbo C 3.0也碰到了问题,代码不可以完全输入到编辑器中,导致最后还是无法运行。最后在网上找了有关的代码,安装了相关图形文件进去,试了试,对代码进行了改动,终于成功,期间问了同学,探讨问题,互帮互助,攻克难题。
通过这段时间的课程设计,我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力,使我掌握了程序设计的基本技能,提高了我适应实际,实践编程的能力。
总的来说,这次课程设计让我获益匪浅,对数据结构也有了进一步的理解和认识。但也让我认识到我还有很多的不足,需要大量的学习,以此来达到能力的提高及熟练的应用。