北京邮电大学电信工程学院
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页