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

《数据结构实验报告——栈和队列(迷宫图最短路径).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、广东机电职业技术学院信息工程学院数据结构实验报告书广东机电职业技术学院2011年5月第16页广东机电职业技术学院信息工程学院目录一、实验要求（需求分析）3a.实验目的3b.实验内容3c．程序功能3二、程序分析42.1存储结构42.2关键算法分析4三、程序运行分析81.程序运行流程图：82.程序运行结果截图：9四．总结11五、附录122010级数据结构实验报告实验名称：迷宫求解问题学生姓名：黄若海班级：软件1004班学号：07100415日期：2011年6月2日第16页广东机电职业技术学院信息工程学院一、实验要求（需求分析）a.实验目的通过实验，掌握如下内容：Ø进一步掌握指针、模板

2、类、异常处理的使用Ø掌握队列的操作的实现方法Ø学习使用队列解决实际问题的能力Ø学习使用图的广度优先搜索解决实际问题的能力b.实验内容利用队的结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。c．程序功能输入起始点的坐标，输出走出迷宫最短路径的长度。第16页广东机电职业技术学院信息工程学院二、程序分析2.1存储结构存储结构:队列顺序存储结构示意图如下:2.2关键算法分析核心算法思想：1.如果采

3、用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。2.为查找最短路径，使用了“图”中的算法：广度优先搜索。关键算法思想描述和实现：关键算法1：为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。C++实现：第16页广东机电职业技术学院信息工程学院structNode{intparent_id;//保存父节点的位置intnode_id;//当前节点的序号，以便传递给孩子节点intx,y;//当前结点对应

4、的坐标}Q[10*10];//每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列关键算法2：遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作就能找到最短路径。C++实现：boolGetNextPos(int*i,int*j,intcount){switch(count){case1:(*j)++;return1;//右case2:(*i)++;return1;//下case3:(*j)--;return1;//左case4:(*i)--;return1;//上default:return0;}}voidEnQueue(inti,intj,

5、intk){Q[rear].x=i;Q[rear].y=j;//保存当前节点对应的坐标位置Q[rear].parent_id=k;//保存父节点的序号Q[rear].node_id=rear;//保存当前节点序号rear++;}关键算法3：广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：第16页广东机电职业技术学院信息工程学院在迷宫地图中，关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。例如H节点的坐标就是出口坐标，当层序搜索到H时就终止了，入队工作结束，不再将I和J入队。

6、通过关键算法四逆序就能找到最短路径A->B->C。其实最短路径不一定只有一条，例如J点也可能是出口坐标，但是当搜索到H时就停止了，故此算法只是输出了所有最短路径中可能的一条。C++实现：voidShortestPath_BFS(inti,intj){intcount,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]){EnQ

7、ueue(i,j,k);Map[i][j]=1;if(i==8&&j==9)return;//到达终点,(8,9)是默认终点，可以任意修改}i=n;j=m;//保证遍历当前坐标的所有相邻位置}}}第16页广东机电职业技术学院信息工程学院关键算法4：使用队列指针查找父节点的方式，从队尾回溯到队首，标记出最短路径。队列的元素示意图如下：入队之后的队列如下图：563774713…………例如从13号节点可以读出它在迷宫地图中的坐标（7，4），通过第三个元素7就能找到第七号节点，也即其父节