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

数 据 结 构实验报告书广东机电职业技术学院2011年5月目录一、实验要求（需求分析）3a. 实验目的3b. 实验内容3c程序功能3二、程序分析42.1 存储结构42.2 关键算法分析4三、程序运行分析81.程序运行流程图：82.程序运行结果截图：9四总结11五、附录122010级数据结构实验报告实验名称： 迷宫求解问题学生姓名： 黄若海班 级： 软件1004班学 号： 日 期： 2011年6月2日一、实验要求（需求分析）a. 实验目的通过实验，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握队列的操作的实现方法 学习使用队列解决实际问题的能力 学习使用图的广度优先搜索解决实际问题的能力b. 实验内容利用队的结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。c程序功能输入起始点的坐标，输出走出迷宫最短路径的长度。二、程序分析2.1 存储结构 存储结构: 队列顺序存储结构示意图如下: 2.2 关键算法分析核心算法思想：1. 如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。2. 为查找最短路径，使用了“图”中的算法：广度优先搜索。关键算法思想描述和实现：关键算法1：为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。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; /右 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：广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：在迷宫地图中，关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。例如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;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;/保证遍历当前坐标的所有相邻位置关键算法4：使用队列指针查找父节点的方式，从队尾回溯到队首，标记出最短路径。队列的元素示意图如下：入队之后的队列如下图：563774713 例如从13号节点可以读出它在迷宫地图中的坐标（7，4），通过第三个元素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.程序运行结果截图：测试条件：以实验题目中给出的迷宫图进行测试。测试时固定终点位置，选择不同的起点位置进行测试，测试各个位置下的输出是否正常。测试结论：本程序对于测试地图在不同起始和终止位置输出都完全正确。四总结1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系，实际将一个顺序队列以指针的作用，变成了一棵树的结构，而树的深度恰好能反映最短路径。3、从一个小小的迷宫问题，引出了许多知识，这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解，再到队列的运用，后又到树与图以及队列的综合运用，将很多知识点串联起来了，加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。4、改进：本题为了实现代码的简便，没有采用链队结构，因而浪费了一定的空间，特别是当迷宫的边长很长的时候，空间复杂度以O（n*n）增长，程序效率将大大降低，因而如果是计算复杂的迷宫，可以考虑将本程序的顺序队列稍加修改变为链队，实现动态分配内存，以节省空间消耗。5、进一步的思考：此方法只能输出一条最短路径，如何能输出所有最短路径？初步算法是将同一深度的节点全部遍历，如果后续还有同样长度的路径则输出该路径，如果没有则只有一条最短路径。五、附录源代码:/本程序在windows7 、visual studio2008 环境下调试运行成功#includeusing namespace std;voidEnQueue(int i,int j,int k); /入队一个节点voidDeQueue(int *i,int *j,int *k); /获取当前节点的序号和对应的迷宫坐标，然后出列boolGetNextPos(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,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();inti,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 *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;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(k != -1)i = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;cout 0 1 2 3