数据结构课程设计迷宫问题求解.doc

扬州大学信息工程学院

《数据结构》
---课程设计报告

题目： 迷宫问题
班级： 计科1301
学号： 131404126
姓名： 张艳
指导教师： 王丽爱

目 录
1 课程题目
2 需求分析
2.1 功能与数据需求
2.1.1 题目要求的功能
2.1.2 扩展功能
2.2 界面需求
2.3 开发环境与运行需求
3 概要设计
3.1主要数据结构
3.2程序总体结构
3.3各模块函数说明
4 详细设计
4.1算法分析与设计
4.2主要程序段设计
5 测试
6 附程序源代码

一、设计题目
迷宫问题
二、需求分析
2.1 功能与数据需求
迷宫求解
问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
2.1.1 题目要求的功能
基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）, （2,2,2）
（3,2,3）, （3,1,2）,…。
测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
1
1
1
1
0
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
0
0
0

1 2 3 4 5 6 7 8

2.1.2 扩展功能
（1）编写递归形式的算法，求得迷宫中所有可能的通路；
（2）以方阵形式输出迷宫及其通路
2.2 界面需求
请求输入进入程序
请求输入起始位置
请求输入终点位置
输出方阵迷宫
输出路径
输出方阵路径

2.3 开发环境与运行需求
Visual C++6.0
三、概要设计
3.1主要数据结构

定义模块
函数模块

主函数

输入起始位置，终点位置
判断首节点是否为通路
判断路径能否走通
对坐标标记

是否到达迷宫出口处

左边是否存在通路

下边是否存在通路

右边是否存在通路

上边是否存在通路

存储路径，将路径入栈
有解迷宫
无解迷宫
Y
N
Y
N
Y
输出迷宫
选择路径

3.3各模块函数说明
typedef struct{
int pos_x[length];//进栈坐标
int pos_y[length];
int top;
int base;
}Stack; //新建结构体
void initStack(Stack *p) //初始化栈
Push(Stack *p,int x,int y,int d) //入栈具体操作 Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标 initMaze(int Maze[10][9])//建立迷宫
Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解 menu();//调用菜单函数 main();//实现迷宫求解的主函数
带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h。
JesephRing()函数是实现问题要求的主要函数。
void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。
void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head,以m为初始报数上限值实现问题要求。
void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。
四、详细设计
迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。
每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。
用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。
二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。
JesephRing()函数作为主要函数，其算法思想是：从1至m对带头结点的单循环链表循环计数，到m时，输出该结点的编号值，将该结点的密码作为新的m值，再从该结点的下一个结点起重新自1起循环计数；如此下去，直到单循环链表空时循环过程结束。
（1）数据类型DataType定义如下：
typedef struct{
int number;
int cipher;
} DataType;
（2）带头结点单循环链表抽象数据类型SCLinList。
（3）带头结点单循环链表抽象数据类型的结点结构定义如下：
typedef struct node{
DataType data;
struct node *next;
} SCLNode;
五、测试数据及运行结果

使用说明
1应用程序功能的详细说明
按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口
2应用程序运行环境要求
Microsoft Visual C++6.0
3输入数据类型、格式和内容限制
4输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开
六、附程序源代码
#include <stdio.h>
#include <malloc.h>
#include<stdlib.h>
#include<conio.h>
#define length 50
#define d direction //用d代表所走路径的方向
int n=-1;
int step=0; //记录步骤数
typedef struct{
int pos_x[length];//进栈坐标
int pos_y[length];
int top;
int base;
}Stack; //新建结构体

void initStack(Stack *p)
{
p->top=p->base=0;
}//初始化栈.

Push(Stack *p,int x,int y,int d) //入栈具体操作
{
step++;
d=0;
n=n+1;
p->top=p->top+1;
p->pos_x[n]=x;
p->pos_y[n]=y;
}

Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标
{
step++;
d=0;
n=n-1;
p->top=p->top-1;
read[0]=p->pos_x[n];
read[1]=p->pos_y[n];
}

initMaze(int Maze[10][9])//建立迷宫函数.
{
int i;
for (i=0;i<=9;i++) {Maze[0][i]=1;}
for (i=0;i<=10;i++) {Maze[i][0]=1;}
for (i=0;i<=9;i++) {Maze[10][i]=1;}
for (i=0;i<=10;i++) {Maze[i][9]=1;}
Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1][6]=0;Maze[1][7]=1;Maze[1][8]=0;
Maze[2][1]=0;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=1;Maze[2][8]=0;
Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=0;Maze[3][8]=1;
Maze[4][1]=0;Maze[4][2]=1;Maze[4][3]=1;Maze[4][4]=1;Maze[4][5]=0;Maze[4][6]=0;Maze[4][7]=1;Maze[4][8]=0;
Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=1;Maze[5][5]=0;Maze[5][6]=0;Maze[5][7]=0;Maze[5][8]=0;
Maze[6][1]=0;Maze[6][2]=1;Maze[6][3]=0;Maze[6][4]=0;Maze[6][5]=0;Maze[6][6]=1;Maze[6][7]=0;Maze[6][8]=1;
Maze[7][1]=0;Maze[7][2]=1;Maze[7][3]=1;Maze[7][4]=1;Maze[7][5]=1;Maze[7][6]=0;Maze[7][7]=0;Maze[7][8]=1;
Maze[8][1]=1;Maze[8][2]=1;Maze[8][3]=0;Maze[8][4]=0;Maze[8][5]=0;Maze[8][6]=1;Maze[8][7]=0;Maze[8][8]=1;
Maze[9][1]=1;Maze[9][2]=1;Maze[9][3]=0;Maze[9][4]=0;Maze[9][5]=0;Maze[9][6]=0;Maze[9][7]=0;Maze[9][8]=0;
}
Print( )//打印出迷宫界面
｛
int m,n，j,sum；
int Maze[10][9];
printf("迷宫(1代表墙即不通,0代表可通过)\n");
printf(" ");
for(j=1;j<=8;j++) { printf("%4d",j);}
printf("\n");
for(m=0;m<=10;m++)
{
for(n=0;n<=9;n++)
{
printf("%4d",Maze[m][n]);
sum++;
if(sum%10==0) printf("\n");
}
}
｝

Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解函数
{
int x,y;
int read[2];
x=rukou_x;
y=rukou_y;
printf("第%d步:",step);
printf("(%d,%d,%d)\n",x,y,d);
if(x==chukou_x&&y==chukou_y)
{
printf("到达出口坐标共走了%d步\n",step);return 0;
}
else if(Maze[x][y+1]==0) {y=y+1;d=1;Push(p,x,y,d);Maze[x][y-1]=1;Maze[x][y]=1;}
else if(Maze[x+1][y]==0) {x=x+1;d=2;Push(p,x,y,d);Maze[x-1][y]=1;Maze[x][y]=1;}
else if(Maze[x][y-1]==0) {y=y-1;d=3;Push(p,x,y,d);Maze[x][y+1]=1;Maze[x][y]=1;}
else if(Maze[x-1][y]==0) {x=x-1;d=4;Push(p,x,y,d);Maze[x+1][y]=1;Maze[x][y]=1;}
else
{
Pop(p,read,d);
x=read[0];
y=read[1];
if(p->top==p->base) {printf("找不到出口\n");return 0;}
}
Ways(p,Maze,x,y,chukou_x,chukou_y,d);
return 1;
}
menu()
{
printf("\t\t************************************\n");
printf("\t\t* 欢迎进入课程设计 *\n");
printf("\t\t* 迷宫求解程序 *\n");
printf("\t\t* 菜单: *\n");
printf("\t\t***进入迷宫***请输入1 *\n");
printf("\t\t***退出迷宫***请输入2 *\n");
printf("\t\t************************************\n");
}

int main()
{
Stack *p;
Stack S;
int Maze[10][9]; //定义迷宫
int elem_1[1],elem_2[1],a,j;
int rukou_x,rukou_y,d=0;
int chukou_x,chukou_y;
int sum=0;
p=&S;
initMaze(Maze);
system("color 5f");//dos窗口背景颜色函数
menu();//调用菜单函数
printf("请输入您的选择:");
scanf("%d",&a);
if(a==1){
Print( ) //打印迷宫图.；
printf("请输入入口坐标:");
scanf("%d",&elem_1[0]);
scanf("%d",&elem_1[1]);
rukou_x=elem_1[0];rukou_y=elem_1[1];
printf("请输入出口坐标:"); //迷宫入口坐标.
scanf("%d",&elem_2[0]);
scanf("%d",&elem_2[1]);
chukou_x=elem_2[0];chukou_y=elem_2[1];//迷宫出口坐标.
if(elem_1[0]>10||elem_1[1]>9||elem_2[0]>10||elem_2[1]>9||
elem_1[0]<0||elem_1[1]<0||elem_2[0]<0||elem_2[1]<0)
{
printf("输入的入口或出口坐标错误\n");} //首先判断输入坐标是否正确

else
{ printf("\n");
printf("说明(x,y,z)x,y代表坐标点;\n");
printf("z代表上个坐标到达这个坐标所走的方向,0为初始值,1234分别代表向右、下、左、上方向\n");
printf("查找路径的具体步骤:\n");
initStack(p);
Push(p,rukou_x,rukou_y,d);
Ways(p,Maze,rukou_x,rukou_y,chukou_x,chukou_y,d);
}
system("pause");
system("cls");
return main();
}
else{
printf("欢迎您的再次光临,再见!\n");
}
system("pause");
}

14