数据结构实验报告栈和队列(迷宫图最短路径)

《数据结构实验报告栈和队列(迷宫图最短路径)》由会员分享，可在线阅读，更多相关《数据结构实验报告栈和队列(迷宫图最短路径)（15页珍藏版）》请在装配图网上搜索。

1、广东机电职业技术学院信息工程学院目录一、实验要求（需求分析）3a. 实验目的3b. 实验内容3c程序功能3二、程序分析42.1 存储结构42.2 关键算法分析4三、程序运行分析81.程序运行流程图：82.程序运行结果截图：9四总结11五、附录12一、实验要求（需求分析）a. 实验目的通过实验，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握队列的操作的实现方法 学习使用队列解决实际问题的能力 学习使用图的广度优先搜索解决实际问题的能力b. 实验内容利用队的结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成

2、了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。c程序功能输入起始点的坐标，输出走出迷宫最短路径的长度。二、程序分析2.1 存储结构 存储结构: 队列顺序存储结构示意图如下: 2.2 关键算法分析核心算法思想：1. 如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。2. 为查找最短路径，使用了“图”中的算法：广度优先搜索。关键算法思想描述和实现：关键算法1：为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储

3、系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。C+实现：struct Nodeintparent_id;/保存父节点的位置intnode_id;/当前节点的序号，以便传递给孩子节点int x,y; /当前结点对应的坐标Q10*10; /每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列关键算法2：遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作就能找到最短路径。C+实现：bool GetNextPos(int *i ,int *j,int count) switch(count) case 1:(*j)+; return 1; /右

4、 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)Qrear.x = i;Qrear.y = j;/保存当前节点对应的坐标位置Qrear.parent_id = k;/保存父节点的序号Qrear.node_id = rear; /保存当前节点序号rear+;关键算法3：广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：在迷宫地图中，关键算法三通过不断调

5、用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。例如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);Map11 = 1;/起点入队,标记起点已走过while(true)count = 1;DeQu

6、eue(&i,&j,&k);n = i,m = j; /保存当前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij) EnQueue(i,j,k);Mapij = 1;if(i = 8 & j = 9) return;/到达终点,(8,9)是默认终点，可以任意修改i = n; j = m;/保证遍历当前坐标的所有相邻位置关键算法4：使用队列指针查找父节点的方式，从队尾回溯到队首，标记出最短路径。队列的元素示意图如下：入队之后的队列如下图：563774713 例如从13号节点可以读出它在迷宫地图中的坐标（7，4），通过第三个元素7就能找到第七号节点，也

7、即其父节点（5，6），从父节点又可以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。C+实现：k = rear-1;while(k != -1)i = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;时间复杂度与空间复杂度：算法一和二时间复杂度与空间复杂度均为O(1)。算法三占用空间为迷宫边长n的平方，故空间复杂度为O(n*n)。最多走n*n步,最少走1步，故时间复杂度为O(n*n/2)。三、程序运行分析1.程序运行流程图：开始输出迷宫图输入x,y否(x,y)是否合法是广度优先搜索标记最短路径输出最短路径结 束2.程序运行结果截图：测试条件：以实验题目

8、中给出的迷宫图进行测试。测试时固定终点位置，选择不同的起点位置进行测试，测试各个位置下的输出是否正常。测试结论：本程序对于测试地图在不同起始和终止位置输出都完全正确。四总结1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复

9、琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系，实际将一个顺序队列以指针的作用，变成了一棵树的结构，而树的深度恰好能反映最短路径。3、从一个小小的迷宫问题，引出了许多知识，这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解，再到队列的运用，后又到树与图以及队列的综合运用，将很多知识点串联起来了，加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。4、改进：本题为了实现代码的简便，没有采用链队结构，因而浪费了一定的空间，特别是当迷宫的边长很长的时候，空间复杂度以O（n*n）增长，程序效率将大大降低，因而如果是计算复杂的迷宫，可以考虑将本程序

10、的顺序队列稍加修改变为链队，实现动态分配内存，以节省空间消耗。5、进一步的思考：此方法只能输出一条最短路径，如何能输出所有最短路径？初步算法是将同一深度的节点全部遍历，如果后续还有同样长度的路径则输出该路径，如果没有则只有一条最短路径。五、附录源代码:/本程序在windows7 、visual studio2008 环境下调试运行成功#includeusing namespace std;voidEnQueue(int i,int j,int k); /入队一个节点voidDeQueue(int *i,int *j,int *k); /获取当前节点的序号和对应的迷宫坐标，然后出列boolGet

11、NextPos(int *i ,int *j,int count); /得到下一个邻接点的位置voidShortestPath_BFS(int i,int j); /广度优先遍历寻找最短路径voidShortestPath(); /输出最短路径 voidPrint(); /输出迷宫形状 int Map1010 = 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,

12、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 Nodeintparent_id;/保存父节点的位置intnode_id;/当前节点的序号，以便传递给孩子节点int x,y;/当前结点对应的坐标Q10*10;/每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列 int front = 0,rear = 0;/队列头指针和尾指针void main()cout程序说明：n1.输出路径为最短路径；n2.默认的出口在最右下角，如有需要可以调整。nn;cout初始地图如下：endl; Print();int

13、i,j;reinput:cout请输入起点坐标（x,y）： ij;if(Mapij) cout不能从该处出发，请重新输入！endl;goto reinput; ShortestPath_BFS(i,j);cout最短路径之一如下：endl;ShortestPath();void EnQueue(int i,int j,int k)Qrear.x = i;Qrear.y = j;/保存当前节点对应的坐标位置Qrear.parent_id = k;/保存父节点的序号Qrear.node_id = rear; /保存当前节点序号rear+;void DeQueue(int *i,int *j,int

14、 *k)*i = Qfront.x;*j = Qfront.y;*k = Qfront.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;

15、EnQueue(i,j,-1);Map11 = 1;/起点入队,标记起点已走过while(true)count = 1;DeQueue(&i,&j,&k);n = i,m = j; /保存当前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij) EnQueue(i,j,k);Mapij = 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

16、(k != -1)i = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;cout 0 1 2 3 4 5 6 7 8 9endl;for(i = 0;i 10;i+)couti;for(j = 0;j 10;j+)if(Mapij=2)sum+; cout;elsecout;coutendl;cout最短路径长度： sumendl;void Print()cout 0 1 2 3 4 5 6 7 8 9endl;for(int i = 0;i 10;i+)couti;for(int j = 0;j 10;j+)if(Mapij) cout;else cout;coutendl;第15页