数据结构-迷宫实验报告.doc

云南大学软件学院 数据结构实验报告

（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）

实验难度： A □ B □ C □

实验难度
A □ B □ C □
承担任务
（难度为C时填写）

指导教师评分
（签名）

【实验题目】
实验4.数组的表示极其应用

【问题描述】
以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【基本要求】
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如；对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，…。

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）
一、【实验构思（Conceive）】(10%)
（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）
本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：
选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。
可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。

二、【实验设计(Design)】(20%)
（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
1. 设定迷宫的抽象数据类型定义：
ADT Maze {
数据对象：D = { ai, j | ai, j ∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row, col≤18 }
数据关系：R = { ROW, COL }
ROW = { < ai-1, j, ai, j > | ai-1, j, ai, j ∈D, i=1, … , row+1, j=0, … , col+1}
COL = { < ai, j-1, ai, j > | ai, j-1, ai, j ∈D, i=0, … , row+1, j=1, … , col+1}
基本操作：
Init_hand_Maze( Maze, row, col)
初始条件：二维数组Maze[][]已存在。
操作结果：手动初始化迷宫，0表示通路，1表示障碍。

Init_automatic_Maze( Maze, row, col)
初始条件：二维数组Maze[][]已存在。
操作结果：自动初始化迷宫，0表示通路，1表示障碍。
PrintMaze( Maze)
初始条件：迷宫Maze已存在。
操作结果：将迷宫输出到屏幕，“□”表示通路，“■”表示障碍。
MazePath( Maze)
初始条件：迷宫Maze已存在。
操作结果：计算路径。
PrintPath( Maze)
初始条件：迷宫Maze已存在。
操作结果：若迷宫存在一条通路，将路径输出至屏幕，以“→”“←”“↑”“↓”表示可行路径，“※”表示途径过却无法到达出口的位置；若不存在通路，报告相应信息。
} ADT Maze；

2. 设定栈的抽象数据类型定义：
ADT Stack {
数据对象：D = { ai | ai ∈ CharSet, i=1, 2, … , n, n≥0 }
数据关系：R1 = { < ai-1, ai > | ai-1, ai ∈D, i=2, … , n}
基本操作：
InitStack(&S)
操作结果：构造一个空栈。
Push(&S, e)
初始条件：栈S已存在。
操作结果：在栈S的栈顶插入新的栈顶元素e。
Pop(&S, &e)
初始条件：栈S已存在 .
操作结果：删除S的栈顶元素，并以e返回其值。
} ADT Stack；

3. 本程序包含三个模块
1)主程序模块：
void main()
{
初始化;

do {
接受命令;
处理命令;
} while (命令! = 退出);
}
2)栈模块——实现栈抽象数据类型；
3)迷宫模块——实现迷宫抽象数据类型。

4各模块之间的调用关系如下：

主程序模块

迷宫模块

栈模块

三、【实现描述（Implement）】(30%)
（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）
1. 迷宫与栈类型
int maze[M][N], row, col ;
typedef struct //存放迷宫访问到点的行，列，方向
{
int m,n,direc;
}MazeType,*LMazeType;
typedef struct
{
LMazeType top; //路径第一个元素的位置
LMazeType base; //路径最后一个元素的位置
int stacksize; //栈大小
int over; //溢出
}Stack;

2. 栈操作函数
void Init_hand_Maze(int maze[M][N],int m,int n)
{

int i,j;
for(i=1;i<=m+1;i++)
for(j=1;j<=n+1;j++)
{
maze[i][j]=1;
}
cout<<"请按行输入迷宫，0表示通路，1表示障碍:"<<endl;
for(i=1;i<m+1;i++)
for(j=1;j<n+1;j++)
cin>>maze[i][j];

for(i=1;i<m+1;i++)
{
for(j=1;j<n+1;j++)
{
if(maze[i][j]!=0&&maze[i][j]!=1){
cout<<" 您输入有误，请重新输入";
Init_hand_Maze(maze,m,n);
}
}
}
}
时间复杂度为O(m*n)

void Init_automatic_Maze(int maze[M][N],int m,int n) //自动生成迷宫
{
int i,j;
cout<<"\n迷宫生成中……\n\n";
system("pause");
for(i=1;i<m+1;i++)
for(j=1;j<n+1;j++)
maze[i][j]=rand()%2; //随机生成0、1
时间复杂度为O(m*n)

Status Push(Stack &S, MazeType e) //将路径上的点依次压栈
{
if(S.top-S.base>=S.stacksize)
{
S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(MazeType));

if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}

Status Pop(Stack &S, MazeType &e) //将能走通的路径的点依次出栈
{
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}

3. 求解迷宫
Status MazePath(Stack &S, MazeType &e, int maze[M][N], int m, int n)
{
do
{
if(maze[e.m][e.n]==0)//0可通，1不可通，2为已走过
{
Push(S,e);
maze[e.m][e.n]=2;
if(e.m==m&&e.n==n)
{
S.over=1;//表示存满一条路径
return OK;
}
else {
e.n++;
e.direc=0;//来这一点时的方向，0右1下2左3上
MazePath(S,e,maze,m,n);
}
}
else
{
if(S.top!=S.base&&S.over!=1)
{
switch(e.direc) //回到上一位置并同时改变方向走下一步
{

case 0: //退回后，列坐标减一，行坐标加一，下一方向向下
e.n--;
e.m++;
e.direc=1;
break;
case 1: //退回后，行坐标减一，列坐标减一，下一方向向左
e.m--;
e.n--;
e.direc=2;
break;
case 2: //退回后，列坐标加一，行坐标减一，下一方向向上
e.n++;
e.m--;
e.direc=3;
break;
case 3: //无需退回，路径，出栈
Pop(S,e);
break;
}
}
}
}while(S.top!=S.base&&S.over!=1);
return OK;
}
时间复杂度为O(m*n)

4. 打印路径
int PrintPath(Stack S,int maze[M][N],int row,int col)
{
if(S.top==S.base)
{
cout<<"\n===============================================\n";
cout<<"此迷宫无解\n\n";
return ERROR;
}
MazeType e;
while(S.top!=S.base)
{
Pop(S,e);
maze[e.m][e.n]=(e.direc+10);

}
cout<<"\n===============================================\n";
cout<<"路径为:"<<endl;
int i,j;
for(i=1;i<row+1;i++)
{
for(j=1;j<col+1;j++)
{
switch(maze[i][j])
{
case 0:
cout<<"□";
break;
case 1:
cout<<"■";
break;
case 2:
cout<<"※";
break;
case 10:
cout<<"→";
break;
case 11:
cout<<"↓";
break;
case 12:
cout<<"←";
break;
case 13:
cout<<"↑";
break;
}
}
cout<<endl;
}
cout<<"完成!"<<endl;
return OK;
}

5. 主函数
int main()

{
switch(i)
{
case 1:
Init_hand_Maze(maze,m,n);
PrintMaze(maze,m,n);
InitStack(S);
MazePath(S,start,maze,end.m,end.n);
PrintPath(S,maze,m,n);
break;
case 2:
Init_automatic_Maze(maze,m,n);
PrintMaze(maze,m,n);
InitStack(S);
MazePath(S,start,maze,end.m,end.n);
PrintPath(S,maze,m,n);
break;
case 3:
cycle=(-1);break;
default:
cout<<"\n";cout<<"你的输入有误!\n";
break;
}
}
}

四、【测试结果（Testing）】(10%)
（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）

手动生成迷宫寻找路径结果正确。

自动声称迷宫寻找路径结果正确。

四、【实验总结】(10%)
（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）
1. 本次实验核心算法明晰，思路明确，易于实现。遇到的问题是，迷宫的外围若未设置障碍，用此程序采用的求解迷宫路径的算法无法获得正确结果。
2. 本程序的MazePath算法代码不够简洁，但不影响算法实现。
3. 本次实验由于时间问题和知识水平有限，还存在一些问题，比如：界面比较单调，整个程序的功能还不完善，还有界面做的有些简单，菜单没有做好，可进行的操作太少，这些都有待进一步改善。
4．本次实验使我对迷宫游戏的原理有了一定的了解，但做出的结果离真正的迷宫还有很大差距，还需要进一步完善，需要自己课下学习更多的知识。

五、【项目运作描述（Operate）】(10%)
（本部分应包括：项目的成本效益分析，应用效果等的分析。）

本程序可基本实现题目的要求，但仍不够完善。比如对于有多种路径的迷宫只能显示一条路径，当输入的路径超过范围时只能取前几个范围内的数据，而无法将这一消息告诉用户，这些问题还有待解决。

六、【代码】(10%)
（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）
#include<stdlib.h> //库中包含system("pause")和rand()函数
#include<stdio.h> //c语言里的库
#include<iostream>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -1
#define M 49
#define N 49
using namespace std;
int maze[M][N];

typedef int Status;
typedef struct
{
int m,n,direc;
}MazeType,*LMazeType;

typedef struct
{
LMazeType top;
LMazeType base;
int stacksize;
int over;
}Stack;

void Init_hand_Maze(int maze[M][N],int m,int n)
{
int i,j;
for(i=1;i<=m+1;i++)
for(j=1;j<=n+1;j++)
{
maze[i][j]=1;
}
cout<<"请按行输入迷宫，0表示通路，1表示障碍:"<<endl;
for(i=1;i<m+1;i++)
for(j=1;j<n+1;j++)
cin>>maze[i][j];

for(i=1;i<m+1;i++)
{
for(j=1;j<n+1;j++)
{
if(maze[i][j]!=0&&maze[i][j]!=1){
cout<<" 您输入有误，请重新输入";
Init_hand_Maze(maze,m,n);
}
}
}
}

void Init_automatic_Maze(int maze[M][N],int m,int n) //自动生成迷宫
{
int i,j;
cout<<"\n迷宫生成中……\n\n";
system("pause");
for(i=1;i<m+1;i++)
for(j=1;j<n+1;j++)
maze[i][j]=rand()%2; //随机生成0、1
}

void PrintMaze(int maze[M][N],int row,int col)
{
int i,j;
cout<<"迷宫如图所示."<<endl;
for(i=1;i<row+1;i++)

{
for(j=1;j<col+1;j++)
{
if(maze[i][j]==1)
cout<<"■";
else
cout<<"□";
}
cout<<endl;
}
}

Status InitStack(Stack &S)
{
S.base=(LMazeType)malloc(STACK_INIT_SIZE * sizeof(MazeType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
S.over=0;
return OK;
}

Status Push(Stack &S,MazeType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(MazeType));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}

Status Pop(Stack &S,MazeType &e)
{
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}

Status MazePath(Stack &S,MazeType &e,int maze[M][N],int m,int n)
{
do
{
if(maze[e.m][e.n]==0)//0可通，1不可通，2为已走过
{
Push(S,e);
maze[e.m][e.n]=2;
if(e.m==m&&e.n==n)
{
S.over=1;//表示存满一条路径
return OK;
}

else {
e.n++;
e.direc=0;//来这一点时的方向，0右1下2左3上
MazePath(S,e,maze,m,n);
}
}
else
{
if(S.top!=S.base&&S.over!=1)
{
switch(e.direc) //回到上一位置并同时改变方向走下一步
{
case 0:
e.n--;
e.m++;
e.direc=1;
break;
case 1:
e.m--;
e.n--;
e.direc=2;
break;
case 2:
e.n++;
e.m--;
e.direc=3;
break;
case 3:
Pop(S,e);
break;
}
}
}

}while(S.top!=S.base&&S.over!=1);
return OK;
}

int PrintPath(Stack S,int maze[M][N],int row,int col)
{
if(S.top==S.base)
{
cout<<"\n===============================================\n";
cout<<"此迷宫无解\n\n";
return ERROR;
}
MazeType e;
while(S.top!=S.base)
{
Pop(S,e);
maze[e.m][e.n]=(e.direc+10);
}
cout<<"完成!"<<endl;
cout<<"\n===============================================\n";
cout<<"路径为:"<<endl;

int i,j;
for(i=1;i<row+1;i++)
{
for(j=1;j<col+1;j++)
{
switch(maze[i][j])
{
case 0:
cout<<"□";
break;
case 1:
cout<<"■";
break;
case 2:
cout<<"※";
break;
case 10:
cout<<"→";
break;
case 11:
cout<<"↓";
break;
case 12:
cout<<"←";
break;
case 13:
cout<<"↑";
break;
}
}
cout<<endl;
}

cout<<"入口"<<endl;
cout<<"完成!"<<endl;
return OK;
}
int main()
{
int i,m,n,maze[M][N],cycle=0;
while(cycle!=(-1))
{
cout<<"********************************************************************************\n";
cout<<" 欢迎进入迷宫求解系统\n";
cout<<endl;
cout<<" 设计者:冯静懿 20091120080\n";
cout<<"********************************************************************************\n";
cout<<" ☆ 手动生成迷宫 请按：1\n";
cout<<" ☆ 自动生成迷宫 请按：2\n";
cout<<" ☆ 退出 请按：3\n\n";
cout<<"********************************************************************************\n";
cout<<"\n";
cout<<"请选择你的操作：\n";
cin>>i;
switch(i)

{
case 1:
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输入列数：";
cin>>n;
while((m<1||m>49)||(n<1||n>49))
{
cout<<"\n抱歉，你输入的行列数超出预设范围(1-49,1-49),请重新输入：\n\n";
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输入列数：";
cin>>n;
}
Init_hand_Maze(maze,m,n);
PrintMaze(maze,m,n);
MazeType start,end;
cout<<"请输入起点m n:"<<endl;

cin>>start.m>>start.n;
start.direc=0;
cout<<"请输入终点m n:"<<endl;
cin>>end.m>>end.n;
Stack S;
cout<<"寻找路径..."<<endl;
InitStack(S);
MazePath(S,start,maze,end.m,end.n);
PrintPath(S,maze,m,n);
system("pause");
cout<<"\n\nPress Enter Contiue!\n";
getchar();
while(getchar()!='\n'); //接受一个输入，当为回车时执行break跳出，否则一直执行接受数据
break;
case 2:
cout<<"\n请输入行数：";
cin>>m;
cout<<"\n";
cout<<"请输