北京邮电大学电信工程学院

2008级数据结构实验报告

实验名称： 实验二 栈和队列 学生姓名： 班 级： 班内序号： 学 号：

日 期： 2009年11月8日

1．实验要求

a. 实验目的

通过选择下面五个题目之一进行实现，掌握如下内容： ? 进一步掌握指针、模板类、异常处理的使用 ? 掌握栈的操作的实现方法 ? 掌握队列的操作的实现方法 ? 学习使用栈解决实际问题的能力 ? 学习使用队列解决实际问题的能力 b. 实验内容

利用栈结构实现迷宫求解问题。迷宫求解问题如下：

心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。

第1页

北京邮电大学电信工程学院

2. 程序分析

2.1 存储结构

存储结构:

队列顺序存储结构 示意图如下:

2.2 关键算法分析

核心算法思想：

1. 如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路

径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。 2. 为查找最短路径，使用了“图”中的算法：广度优先搜索。

关键算法思想描述和实现： 关键算法1：

为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。

C++实现：

struct Node

第2页

北京邮电大学电信工程学院

{

int int

parent_id; node_id;

//保存父节点的位置

//当前节点的序号，以便传递给孩子节点

int x,y; //当前结点对应的坐标

}Q[10*10]; //每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列

关键算法2：

遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作就能找到最短路径。 C++实现：

bool GetNextPos(int *i ,int *j,int count) {

switch(count) {

case 1:(*j)++; return 1; //右 case 2:(*i)++; return 1; //下 case 3:(*j)--; return 1; //左 case 4:(*i)--; return 1; //上 default: return 0; } }

void EnQueue(int i,int j,int k) { }

Q[rear].x = i; Q[rear].y = j;

//保存当前节点对应的坐标位置

Q[rear].parent_id = k; Q[rear].node_id = rear; rear++;

//保存父节点的序号

//保存当前节点序号

关键算法3：

广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：

第3页