数据结构-迷宫实验报告

云南大学

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

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

实验难度： A □ B □ 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) //自动生成迷宫 {

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;

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)

云南大学

return OK; }

Status Pop(Stack &S, MazeType &e) //将能走通的路径的点依次出栈

{

if(S.top==S.base)return ERROR; e=*--S.top; return OK; }

3. 求解迷宫

Status MazePa …… 此处隐藏：6571字，全部文档内容请下载后查看。喜欢就下载吧 ……