数据结构迷宫实验报告.docx

数据结构迷宫实验报告.docx

《数据结构迷宫实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构迷宫实验报告.docx（28页珍藏版）》请在冰点文库上搜索。

数据结构迷宫实验报告

（本实验项目方案受“教育部人才培养模式创新实验区（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.设定迷宫的抽象数据类型定义：

ADTMaze{

数据对象：

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∈D,i=1,…,row+1,j=0,…,col+1}

COL={|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已存在。

操作结果：

若迷宫存在一条通路，将路径输出至屏幕，以“→”“←”“↑”“↓”表示可行路径，“※”表示途径过却无法到达出口的位置；若不存在通路，报告相应信息。

}ADTMaze；

2.设定栈的抽象数据类型定义：

ADTStack{

数据对象：

D={ai|ai∈CharSet,i=1,2,…,n,n≥0}

数据关系：

R1={|ai-1,ai∈D,i=2,…,n}

基本操作：

InitStack（&S）

操作结果：

构造一个空栈。

Push（&S,e）

初始条件：

栈S已存在。

操作结果：

在栈S的栈顶插入新的栈顶元素e。

Pop（&S,&e）

初始条件：

栈S已存在.

操作结果：

删除S的栈顶元素，并以e返回其值。

}ADTStack；

3.本程序包含三个模块

1）主程序模块：

voidmain（）

{

初始化;

do{

接受命令;

处理命令;

}while（命令!

=退出）;

}

2）栈模块——实现栈抽象数据类型；

3）迷宫模块——实现迷宫抽象数据类型。

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

主程序模块

迷宫模块

栈模块

三、【实现描述（Implement）】（30%）

（本部分应包括：

抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。

）

1.迷宫与栈类型

intmaze[M][N],row,col;

typedefstruct//存放迷宫访问到点的行，列，方向

{

intm,n,direc;

}MazeType,*LMazeType;

typedefstruct

{

LMazeTypetop;//路径第一个元素的位置

LMazeTypebase;//路径最后一个元素的位置

intstacksize;//栈大小

intover;//溢出

}Stack;

2.栈操作函数

voidInit_hand_Maze（intmaze[M][N],intm,intn）

{

inti,j;

for（i=1;i<=m+1;i++）

for（j=1;j<=n+1;j++）

{

maze[i][j]=1;

}

cout<<"请按行输入迷宫，0表示通路，1表示障碍:

"<

for（i=1;i

for（j=1;j

cin>>maze[i][j];

for（i=1;i

{

for（j=1;j

{

if（maze[i][j]!

=0&&maze[i][j]!

=1）{

cout<<"您输入有误，请重新输入";

Init_hand_Maze（maze,m,n）;

}

}

}

}

时间复杂度为O（m*n）

voidInit_automatic_Maze（intmaze[M][N],intm,intn）//自动生成迷宫

{

inti,j;

cout<<"\n迷宫生成中……\n\n";

system（"pause"）;

for（i=1;i

for（j=1;j

maze[i][j]=rand（）%2;//随机生成0、1

时间复杂度为O（m*n）

StatusPush（Stack&S,MazeTypee）//将路径上的点依次压栈

{

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;

returnOK;

}

StatusPop（Stack&S,MazeType&e）//将能走通的路径的点依次出栈

{

if（S.top==S.base）returnERROR;

e=*--S.top;

returnOK;

}

3.求解迷宫

StatusMazePath（Stack&S,MazeType&e,intmaze[M][N],intm,intn）

{

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;//表示存满一条路径

returnOK;

}

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）//回到上一位置并同时改变方向走下一步

{

case0:

//退回后，列坐标减一，行坐标加一，下一方向向下

e.n--;

e.m++;

e.direc=1;

break;

case1:

//退回后，行坐标减一，列坐标减一，下一方向向左

e.m--;

e.n--;

e.direc=2;

break;

case2:

//退回后，列坐标加一，行坐标减一，下一方向向上

e.n++;

e.m--;

e.direc=3;

break;

case3:

//无需退回，路径，出栈

Pop（S,e）;

break;

}

}

}

}while（S.top!

=S.base&&S.over!

=1）;

returnOK;

}

时间复杂度为O（m*n）

4.打印路径

intPrintPath（StackS,intmaze[M][N],introw,intcol）

{

if（S.top==S.base）

{

cout<<"\n===============================================\n";

cout<<"此迷宫无解\n\n";

returnERROR;

}

MazeTypee;

while（S.top!

=S.base）

{

Pop（S,e）;

maze[e.m][e.n]=（e.direc+10）;

}

cout<<"\n===============================================\n";

cout<<"路径为:

"<

inti,j;

for（i=1;i

{

for（j=1;j

{

switch（maze[i][j]）

{

case0:

cout<<"□";

break;

case1:

cout<<"■";

break;

case2:

cout<<"※";

break;

case10:

cout<<"→";

break;

case11:

cout<<"↓";

break;

case12:

cout<<"←";

break;

case13:

cout<<"↑";

break;

}

}

cout<

}

cout<<"完成!

"<

returnOK;

}

5.主函数

intmain（）

{

switch（i）

{

case1:

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;

case2:

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;

case3:

cycle=（-1）;break;

default:

cout<<"\n";cout<<"你的输入有误!

\n";

break;

}

}

}

四、【测试结果（Testing）】（10%）

（本部分应包括：

对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）

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

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

四、【实验总结】（10%）

（本部分应包括：

自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）

1.本次实验核心算法明晰，思路明确，易于实现。

遇到的问题是，迷宫的外围若未设置障碍，用此程序采用的求解迷宫路径的算法无法获得正确结果。

2.本程序的MazePath算法代码不够简洁，但不影响算法实现。

3.本次实验由于时间问题和知识水平有限，还存在一些问题，比如：

界面比较单调，整个程序的功能还不完善，还有界面做的有些简单，菜单没有做好，可进行的操作太少，这些都有待进一步改善。

4．本次实验使我对迷宫游戏的原理有了一定的了解，但做出的结果离真正的迷宫还有很大差距，还需要进一步完善，需要自己课下学习更多的知识。

五、【项目运作描述（Operate）】（10%）

（本部分应包括：

项目的成本效益分析，应用效果等的分析。

）

本程序可基本实现题目的要求，但仍不够完善。

比如对于有多种路径的迷宫只能显示一条路径，当输入的路径超过范围时只能取前几个范围内的数据，而无法将这一消息告诉用户，这些问题还有待解决。

六、【代码】（10%）

（本部分应包括：

完整的代码及充分的注释。

注意纸质的实验报告无需包括此部分。

格式统一为，字体:

Georgia,行距:

固定行距12，字号:

小五）

#include//库中包含system（"pause"）和rand（）函数

#include//c语言里的库

#include

#include

#defineOK1

#defineERROR0

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

#defineOVERFLOW-1

#defineM49

#defineN49

usingnamespacestd;

intmaze[M][N];

typedefintStatus;

typedefstruct

{

intm,n,direc;

}MazeType,*LMazeType;

typedefstruct

{

LMazeTypetop;

LMazeTypebase;

intstacksize;

intover;

}Stack;

voidInit_hand_Maze（intmaze[M][N],intm,intn）

{

inti,j;

for（i=1;i<=m+1;i++）

for（j=1;j<=n+1;j++）

{

maze[i][j]=1;

}

cout<<"请按行输入迷宫，0表示通路，1表示障碍:

"<

for（i=1;i

for（j=1;j

cin>>maze[i][j];

for（i=1;i

{

for（j=1;j

{

if（maze[i][j]!

=0&&maze[i][j]!

=1）{

cout<<"您输入有误，请重新输入";

Init_hand_Maze（maze,m,n）;

}

}

}

}

voidInit_automatic_Maze（intmaze[M][N],intm,intn）//自动生成迷宫

{

inti,j;

cout<<"\n迷宫生成中……\n\n";

system（"pause"）;

for（i=1;i

for（j=1;j

maze[i][j]=rand（）%2;//随机生成0、1

}

voidPrintMaze（intmaze[M][N],introw,intcol）

{

inti,j;

cout<<"迷宫如图所示."<

for（i=1;i

{

for（j=1;j

{

if（maze[i][j]==1）

cout<<"■";

else

cout<<"□";

}

cout<

}

}

StatusInitStack（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;

returnOK;

}

StatusPush（Stack&S,MazeTypee）

{

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;

returnOK;

}

StatusPop（Stack&S,MazeType&e）

{

if（S.top==S.base）returnERROR;

e=*--S.top;

returnOK;

}

StatusMazePath（Stack&S,MazeType&e,intmaze[M][N],intm,intn）

{

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;//表示存满一条路径

returnOK;

}

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）//回到上一位置并同时改变方向走下一步

{

case0:

e.n--;

e.m++;

e.direc=1;

break;

case1:

e.m--;

e.n--;

e.direc=2;

break;

case2:

e.n++;

e.m--;

e.direc=3;

break;

case3:

Pop（S,e）;

break;

}

}

}

}while（S.top!

=S.base&&S.over!

=1）;

returnOK;

}

intPrintPath（StackS,intmaze[M][N],introw,intcol）

{

if（S.top==S.base）

{

cout<<"\n===============================================\n";

cout<<"此迷宫无解\n\n";

returnERROR;

}

MazeTypee;

while（S.top!

=S.base）

{

Pop（S,e）;

maze[e.m][e.n]=（e.direc+10）;

}

cout<<"完成!

"<

cout<<"\n===============================================\n";

cout<<"路径为:

"<

inti,j;

for（i=1;i

{

for（j=1;j

{

switch（maze[i][j]）

{

case0:

cout<<"□";

break;

case1:

cout<<"■";

break;

case2:

cout<<"※";

break;

case10:

cout<<"→";

break;

case11:

cout<<"↓";

break;

case12:

cout<<"←";

break;

case13:

cout<<"↑";

break;

}

}

cout<

}

cout<<"入口"<

cout<<"完成!

"<

returnOK;

}

intmain（）

{

inti,m,n,maze[M][N],cycle=0;

while（cycle!

=（-1））

{

cout<<"********************************************************************************\n";

cout<<"欢迎进入迷宫求解系统\n";

cout<

cout<<"设计者:

冯静懿20091120080\n";

cout<<"********************************************************************************\n";

cout<<"☆手动生成迷宫请按：

1\n";

cout<<"☆自动生成迷宫请按：

2\n";

cout<<"☆