数据结构实验报告——栈和队列
20##级数据结构实验报告
实验名称： 实验二 栈和队列
学生姓名：
班 级：
班内序号：
学 号：
日 期： 20##年11月8日
1．实验要求
a. 实验目的
通过选择下面五个题目之一进行实现，掌握如下内容：
Ø 进一步掌握指针、模板类、异常处理的使用
Ø 掌握栈的操作的实现方法
Ø 掌握队列的操作的实现方法
Ø 学习使用栈解决实际问题的能力
Ø 学习使用队列解决实际问题的能力
b. 实验内容
利用栈结构实现迷宫求解问题。迷宫求解问题如下：
心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。
2. 程序分析
2.1 存储结构
存储结构:
队列顺序存储结构
示意图如下:
2.2 关键算法分析
核心算法思想：
1. 如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。
2. 为查找最短路径，使用了“图”中的算法：广度优先搜索。
关键算法思想描述和实现：
关键算法1：
为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。
C++实现：
struct Node
{
int parent_id; //保存父节点的位置
int 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：
广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：
在迷宫地图中，关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。例如H节点的坐标就是出口坐标，当层序搜索到H时就终止了，入队工作结束，不再将I和J入队。通过关键算法四逆序就能找到最短路径A->B->C。其实最短路径不一定只有一条，例如J点也可能是出口坐标，但是当搜索到H时就停止了，故此算法只是输出了所有最短路径中可能的一条。
C++实现：
void ShortestPath_BFS(int i ,int j)
{
int count,m,n,k;
EnQueue(i,j,-1); Map[1][1] = 1; //起点入队,标记起点已走过
while(true)
{
count = 1;
DeQueue(&i,&j,&k);
n = i,m = j; //保存当前位置
while(GetNextPos(&i,&j,count))
{
count++;
if(!Map[i][j])
{
EnQueue(i,j,k); Map[i][j] = 1;
if(i == 8 && j == 9) return; //到达终点,(8,9)是默认终点，可以任意修改
}
i = n; j = m; //保证遍历当前坐标的所有相邻位置
}
}
}
关键算法4：
使用队列指针查找父节点的方式，从队尾回溯到队首，标记出最短路径。
队列的元素示意图如下：
入队之后的队列如下图：
…………
例如从13号节点可以读出它在迷宫地图中的坐标（7，4），通过第三个元素7就能找到第七号节点，也即其父节点（5，6），从父节点又可以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。
C++实现：
k = rear-1;
while(k != -1)
{
i = Q[k].x; j = Q[k].y;
Map[i][j] = 2;
k = Q[k].parent_id;
}
时间复杂度与空间复杂度：
算法一和二时间复杂度与空间复杂度均为O(1)。
算法三占用空间为迷宫边长n的平方，故空间复杂度为O(n*n)。最多走n*n步,最少走1步，故时间复杂度为O(n*n/2)。
3. 程序运行结果
测试条件：
以实验题目中给出的迷宫图进行测试。
测试时固定终点位置，选择不同的起点位置进行测试，测试各个位置下的输出是否正常。
测试结论：
本程序对于测试地图在不同起始和终止位置输出都完全正确。
4. 总结
1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。
2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系，实际将一个顺序队列以指针的作用，变成了一棵树的结构，而树的深度恰好能反映最短路径。
3、从一个小小的迷宫问题，引出了许多知识，这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解，再到队列的运用，后又到树与图以及队列的综合运用，将很多知识点串联起来了，加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。
4、改进：本题为了实现代码的简便，没有采用链队结构，因而浪费了一定的空间，特别是当迷宫的边长很长的时候，空间复杂度以O（n*n）增长，程序效率将大大降低，因而如果是计算复杂的迷宫，可以考虑将本程序的顺序队列稍加修改变为链队，实现动态分配内存，以节省空间消耗。
5、进一步的思考：此方法只能输出一条最短路径，如何能输出所有最短路径？初步算法是将同一深度的节点全部遍历，如果后续还有同样长度的路径则输出该路径，如果没有则只有一条最短路径。
附录源代码:
//本程序在windows7 、visual studio2008 环境下调试运行成功
#include<iostream>
using namespace std;
void EnQueue(int i,int j,int k); //入队一个节点
void DeQueue(int *i,int *j,int *k); //获取当前节点的序号和对应的迷宫坐标，然后出列
bool GetNextPos(int *i ,int *j,int count); //得到下一个邻接点的位置
void ShortestPath_BFS(int i,int j); //广度优先遍历寻找最短路径
void ShortestPath(); //输出最短路径
void Print(); //输出迷宫形状
int Map[10][10] = {{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1}};
struct Node
{
int parent_id; //保存父节点的位置
int node_id; //当前节点的序号，以便传递给孩子节点
int x,y; //当前结点对应的坐标
}Q[10*10]; //每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列
int front = 0,rear = 0; //队列头指针和尾指针
void main()
{
cout<<"程序说明："<<'\n'<<"1.输出路径为最短路径；"<<'\n'<<"2.默认的出口在最右下角，如有需要可以调整。"<<'\n'<<'\n';
cout<<"初始地图如下："<<endl;
Print();
int i,j;
reinput:
cout<<"请输入起点坐标（x,y）： "<<endl;
cin>>i>>j;
if(Map[i][j]) {cout<<"不能从该处出发，请重新输入！"<<endl;goto reinput;}
ShortestPath_BFS(i,j);
cout<<"最短路径之一如下："<<endl;
ShortestPath();
}
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++;
}
void DeQueue(int *i,int *j,int *k)
{
*i = Q[front].x;
*j = Q[front].y;
*k = Q[front].node_id;
front++; //出列一个节点
}
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 ShortestPath_BFS(int i ,int j)
{
int count,m,n,k;
EnQueue(i,j,-1); Map[1][1] = 1; //起点入队,标记起点已走过
while(true)
{
count = 1;
DeQueue(&i,&j,&k);
n = i,m = j; //保存当前位置
while(GetNextPos(&i,&j,count))
{
count++;
if(!Map[i][j])
{
EnQueue(i,j,k); Map[i][j] = 1;
if(i == 8 && j == 9) return; //到达终点,(8,9)是默认终点，可以任意修改
}
i = n; j = m; //保证遍历当前坐标的所有相邻位置
}
}
}
void ShortestPath()
{
int i,j,k,sum(0) ;
k = rear-1;
while(k != -1)
{
i = Q[k].x; j = Q[k].y;
Map[i][j] = 2;
k = Q[k].parent_id;
}
cout<<" 0 1 2 3 4 5 6 7 8 9"<<endl;
for(i = 0;i < 10;i++)
{
cout<<i;
for(j = 0;j < 10;j++)
if(Map[i][j]==2)
{sum++; cout<<"□";}
else
cout<<"■";
cout<<endl;
}
cout<<"最短路径长度： "<<sum<<endl;
}
void Print()
{
cout<<" 0 1 2 3 4 5 6 7 8 9"<<endl;
for(int i = 0;i < 10;i++)
{
cout<<i;
for(int j = 0;j < 10;j++)
if(Map[i][j]) cout<<"■";
else cout<<"□";
cout<<endl;
}
}
第二篇：数据结构实验报告__栈和队列
实验报告数据结构数据结构实验报告
课程院实验地点姓
学实验二栈和队列：迷宫问题求解实验时间实验成绩批改日期一、实验目的
二、掌握栈和队列的顺序存储结构；
三、掌握栈和队列的操作特性；
1/19
四、掌握基于顺序栈和链队列的基本操作的实现方法。
二、实验内容
1、设计数据结构存储迷宫；
2、设计存储结构保存从入口到出口的通路；
3、设计算法完成迷宫问题的求解；
4、分析算法的时间复杂度。
三、实验实现
1、用栈实现求迷宫从出口到入口的一条路径（不一定是最短路径）（1）顺序栈结构SeqStack.h
constintStackSize=64;//10只是示例性的数据，可以根据实际问题具体定义template<classT>
classSeqStack
{
public:
SeqStack();
~SeqStack(){}
voidPush(Tx);
TGetTop();
TPop();
intEmpty();
voidPrint();//定义模板类SeqStack//构造函数，栈的初始化//析构函数//将元素x入栈//将栈顶元素弹出//判断栈是否为空//输出栈中元素
2/19
private:
Tdata[StackSize];
inttop;//存放栈元素的数组//栈顶指针，指示栈顶元素在数组中的下标};
template<classT>
SeqStack<T>::SeqStack()
{
top=-1;
}
template<classT>
voidSeqStack<T>::Push(Tx)
{
if(top==StackSize-1)throw"上溢";top++;
data[top]=x;
}
template<classT>
TSeqStack<T>::Pop()
{
Tx;
if(top==-1)throw"下溢";
3/19
x=data[top--];
returnx;
}
template<classT>
TSeqStack<T>::GetTop(){
if(top!=-1)returndata[top];}
template<classT>
intSeqStack<T>::Empty(){
if(top==-1)return1;elsereturn0;
}
template<classT>
voidSeqStack<T>::Print(){
while(top!=-1)
{
Ttemp;
temp=Pop();
4/19
cout<<temp.x<<'\t'<<temp.y<<'\t'<<temp.d<<'\n';}
}
（2）主函数实现
a、四方向查找
#include<iostream.h>
#include"SeqStack.h"
constintN=10;
typedefstruct{
intx,y,d;
}DataType;
structDirectInc{
intdx,dy;
};
constDirectIncmove[4]={{0,1},{1,0},{0,-1},{-1,0}};voidmazepath(intmaze[N][N])
{
DataTypetemp;
intg,h,v,i,j;
SeqStack<DataType>S;//栈（*S）已建立temp.x=1;temp.y=1;temp.d=-1;//入口位置及方向maze[1][1]=-1;
5/19
S.Push(temp);
while(!S.Empty())
{
temp=S.GetTop();i=temp.x;j=temp.y;v=temp.d+1;if(v==4)S.Pop();
while(v<4)
{
g=i+move[v].dx;h=j+move[v].dy;
if(maze[g][h]==0)
{
temp.x=g;temp.y=h;temp.d=v;
S.Push(temp);
maze[i][j]=-1;i=g;j=h;
if(i==N-2&&j==N-2)
{
S.Print();
return;
}
elsev=0;
}
else
{
6/19
v++;
if(v==4)S.Pop();
}
}//endwhile(v<4)
}//endwhile(!S.Empty())
}
voidmain(){
intmaze[N][N]={{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
cout<<"从出口到入口的路径为\n(xy代表坐标d代表方向(东0，南
3))\nx\ty\td"<<endl;
mazepath(maze);
}
运行结果：
7/191，西2，北
b、八方向查找
#include<iostream.h>
#include"SeqStack.h"
constintN=10;
typedefstruct{
intx,y,d;
}DataType;
structDirectInc{
intdx,dy;
};
constDirectIncmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};voidmazepath(intmaze[N][N])
{
DataTypetemp;
intg,h,v,i,j;
8/19
SeqStack<DataType>S;//栈（*S）已建立temp.x=1;temp.y=1;temp.d=-1;//入口位置及方向maze[1][1]=-1;
S.Push(temp);
while(!S.Empty())
{
temp=S.GetTop();i=temp.x;j=temp.y;v=temp.d+1;if(v==8)S.Pop();
while(v<8)
{
g=i+move[v].dx;h=j+move[v].dy;
if(maze[g][h]==0)
{
temp.x=g;temp.y=h;temp.d=v;
S.Push(temp);
maze[i][j]=-1;i=g;j=h;
if(i==N-2&&j==N-2)
{
S.Print();
return;
}
elsev=0;
9/19
}
else
{
v++;
if(v==8)S.Pop();
}
}//endwhile(v<8)
}//endwhile(!S.Empty())
}
voidmain(){
intmaze[N][N]={{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
cout<<"从出口到入口的路径为\n(xy代表坐标d代表方向(东0,东南1,南2,西南3,西4,西北5,北6,东北7))\nx\ty\td"<<endl;
10/19
mazepath(maze);
}
运行结果：
2、用队列实现求迷
宫问题从入口到出口的最短路径（1）链队列结构CirQueue.hconstintQueueSize=100;//定义存储队列元素的数组的最大长度template<classT>//定义模板类CirQueue
11/19
classCirQueue
{
public:
CirQueue();
~CirQueue();
voidEnQueue(Tx);TDeQueue();
TGetQueue();
intEmpty();
TGet(inti);
intGetFront(){returnfront;}intGetRear(){returnrear;}private:
Tdata[QueueSize];intfront,rear;
位置
};
template<classT>
CirQueue<T>::CirQueue(){
front=rear=0;
}
12/19//构造函数，置空队//析构函数//将元素x入队//将队头元素出队//取队头元素（并不删除）//判断队列是否为空//存放队列元素的数组//队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的
template<classT>
CirQueue<T>::~CirQueue()
{}
template<classT>
voidCirQueue<T>::EnQueue(Tx){
if((rear+1)%QueueSize==front)throw"上溢";rear=(rear+1)%QueueSize;
data[rear]=x;
}
template<classT>
TCirQueue<T>::DeQueue()
{
if(rear==front)throw"下溢";front=(front+1)%QueueSize;returndata[front];
}
template<classT>
TCirQueue<T>::GetQueue()
{
inti;
if(rear==front)throw"下溢";
13/19//队尾指针在循环意义下加1//在队尾处插入元素//队头指针在循环意义下加1//读取并返回出队前的队头元素，注意队头指针//指向队头元素的前一个位置
i=(front+1)%QueueSize;//注意不要给队头指针赋值returndata[i];
}
template<classT>
intCirQueue<T>::Empty(){
if(front==rear)
return1;
else
return0;
}
template<classT>
TCirQueue<T>::Get(inti){
if(i>=0&&i<=rear)returndata[i];}
（2）主函数实现（八方向查找）#include<iostream.h>
#include"CirQueue.h"
constintM=6,N=8;
typedefstruct{intx,y,pre;}DataType;structDirectInc
14/19
{
intdx,dy;
};
DirectIncmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};voidPrintShortPath(CirQueue<DataType>Q)
{
inti=Q.GetRear();
do{
DataTypee=Q.Get(i);
cout<<'('<<e.x<<','<<e.y<<')'<<"pre:"<<e.pre<<endl;
i=e.pre;
}while(i!=-1);
cout<<endl<<"WholeQueue:"<<endl;
for(intu=1;u<=Q.GetRear();u++)
{
DataTypee=Q.Get(u);
cout<<'('<<e.x<<','<<e.y<<')'<<"pre:"<<e.pre<<endl;
}
}
voidRestore(intmaze[M+2][N+2])
{
inti,j;
15/19
for(i=1;i<=M;i++)
for(j=1;j<=N;j++)
if(maze[i][j]==-1)maze[i][j]=0;
for(i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
cout<<maze[i][j]<<"";
cout<<endl;
}
}
voidShortPathQue(CirQueue<DataType>*Q,intmaze[M+2][N+2]){
inti,j,g,h,v,find=0;
DataTypee={1,1,-1};
Q->EnQueue(e);
maze[1][1]=-1;
while(!Q->Empty()&&!find)
{
e=Q->DeQueue();
i=e.x;
j=e.y;
for(v=0;v<8;v++)
16/19
{
g=i+move[v].dx;
h=j+move[v].dy;
if(maze[g][h]==0)
{
e.x=g;
e.y=h;
e.pre=Q->GetFront();
Q->EnQueue(e);
maze[g][h]=-1;
if(g==M&&h==N)
{
PrintShortPath(*Q);
Restore(maze);
find=1;
}//if(g)
}//if(maze)
}//for
}//while
if(!find){cout<<"nopath!"<<endl;}}//end
voidmain()
17/19
{
CirQueue<DataType>Q;
intmaze[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},
{1,1,0,1,0,1,0,1,0,1},
{1,0,1,0,0,1,1,1,1,1},
{1,0,1,1,1,0,0,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,1,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}};
cout<<"走出迷宫的正确路径为:\n";ShortPathQue(&Q,maze);
}
运行结果：
18/19
四、实
验心得体会
通过本实验，我初步了解了栈和队列的顺序存储结构；掌握栈和队列的操作特性；掌握基于顺序栈和链队列的基本操作的实现方法。
我感觉最大的不足就是对c++编程不够熟悉，经常犯一些比较低级的错误，程序录入时，不时会有一些“马虎“，应多加注意。
19/19
- 数据结构栈和队列实验报告
-
数据结构顺序栈实验报告
一设计人员相关信息1设计者姓名学号和班号12地信李晓婧120xx2429832设计日期20xx3上机环境VC60二程序设计相关信息…
-
数据结构出栈、入栈实验报告
数据结构实验报告院系应用科技学院专业电子信息工程姓名学号班1实验目的123熟悉栈的定义和栈的基本操作掌握顺序存储栈和链接存储栈的基…
-
数据结构实验报告(栈的应用)
实习报告题目编制一个演示表达式求值的操作的程序班级计算机信息安全姓名学号完成日期需求分析本演示程序中元素限定为int整型和char…
-
数据结构实验报告二栈的应用
数据结构实验指导书姓名修凌云姓名李赛赛信息与计算科学教研室实验一栈及其应用实验目的熟悉栈的基本概念熟练掌握并实现栈的基本操作以及两…
-
栈和队列实验报告
规格为A4纸或A3纸折叠注1实验报告的内容一实验目的二实验原理三实验步骤四实验结果五讨论分析完成指定的思考题和作业题六改进实验建议…
-
算法与数据结构栈与队列实验报告
实验二栈和队列实现四则运算实验二栈和队列实现四则运算一实验目的及要求1掌握栈和队列的基本操作建立插入删除查找合并2掌握用栈和队列的…
-
数据结构实验报告 栈和队列
20xx级数据结构实验报告实验名称实验二栈和队列日期20xx年11月15日1实验要求实验目的通过选择下面五个题目之一进行实现掌握如…
-
栈和队列实验报告
栈的顺序表示和实现一实验目的1了解栈和队列的特性2掌握栈的顺序表示和实现3掌握栈的链式表示和实现4掌握队列的顺序表示和实现5掌握队…
- 数据结构栈和队列实验报告