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

数据结构实验报告-栈和队列(迷宫图最短路径).doc 广东机电职业技术学院信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院 目录 一、实验要求(需求 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ).............................................................................................. 1 a. 实验目的 .............................................................................................................. 1 b. 实验 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 .............................................................................................................. 2 c(程序功能.............................................................................................................. 2 二、程序分析................................................................................................................... 2 2.1 存储结构 ............................................................................................................ 2 2.2 关键算法分析 ..................................................................................................... 3 三、程序运行分析............................................................................................................ 7 1.程序运行流程图: ................................................................................................. 7 2.程序运行结果截图:.............................................................................................. 8 四(总结........................................................................................................................ 10 五、附录.........................................................................................................................11 一、实验要求(需求分析) a. 实验目的 通过实验，掌握如下内容: 第1页 广东机电职业技术学院信息工程学院 , 进一步掌握指针、模板类、异常处理的使用 , 掌握队列的操作的实现方法 , 学习使用队列解决实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的能力 , 学习使用图的广度优先搜索解决实际问题的能力 b. 实验内容 利用队的结构实现迷宫求解问题。迷宫求解问题如下: 心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。 c(程序功能 输入起始点的坐标，输出走出迷宫最短路径的长度。 二、程序分析 2.1 存储结构 存储结构: 队列顺序存储结构 示意图如下: 第2页 广东机电职业技术学院信息工程学院 2.2 关键算法分析 核心算法思想: 1. 如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路 径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。 2. 为查找最短路径，使用了“图”中的算法:广度优先搜索。 关键算法思想描述和实现: 关键算法1: 为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。 C++实现: struct Node { int parent_id; //保存父节点的位置 int node_id; //当前节点的序号，以便传递给孩子节点 int x,y; //当前结点对应的坐标 }Q[10*10]; //每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列 关键算法2: 第3页 广东机电职业技术学院信息工程学院 遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作 就能找到最短路径。 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节点的坐标就是出 第4页 广东机电职业技术学院信息工程学院 口坐标，当层序搜索到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: 使用队列指针查找父节点的方式，从队尾回溯到队首，标记出最短路径。 队列的元素示意图如下: 入队之后的队列如下图: „„„„ 7 4 7 13 5 6 3 7 ，4)，通过第三个元素7就能找到第七号例如从13号节点可以读出它在迷宫地图中的坐标(7 节点，也即其父节点(5，6)，从父节点又可以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。 第5页 广东机电职业技术学院信息工程学院 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)。 第6页 广东机电职业技术学院信息工程学院 三、程序运行分析 1.程序运行流程图: 开始 输出迷宫图 输入x,y 否 (x,y)是否合法 是 广度优先搜索 标记最短路径 输出最短路径 结 束 第7页 广东机电职业技术学院信息工程学院 2.程序运行结果截图: 第8页 广东机电职业技术学院信息工程学院 测试条件: 以实验题目中给出的迷宫图进行测试。 测试时固定终点位置，选择不同的起点位置进行测试，测试各个位置下的输出是否正常。 测试结论: 本程序对于测试地图在不同起始和终止位置输出都完全正确。 第9页 广东机电职业技术学院信息工程学院 四(总结 1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。 2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系，实际将一个顺序队列以指针的作用，变成了一棵树的结构，而树的深度恰好能反映最短路径。 3、从一个小小的迷宫问题，引出了许多知识，这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解，再到队列的运用，后又到树与图以及队列的综合运用，将很多 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 串联起来了，加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。 4、改进:本题为了实现代码的简便，没有采用链队结构，因而浪费了一定的空间，特别是当迷宫的边长很长的时候，空间复杂度以O(n*n)增长，程序效率将大大降低，因而如果是计算复杂的迷宫，可以考虑将本程序的顺序队列稍加修改变为链队，实现动态分配内存，以节省空间消耗。 5、进一步的思考:此方法只能输出一条最短路径，如何能输出所有最短路径,初步算法是将同一深度的节点全部遍历，如果后续还有同样长度的路径则输出该路径，如果没有则只有一条最短路径。 第10页 广东机电职业技术学院信息工程学院 五、附录 源代码: //本程序在windows7 、visual studio2008 环境下调试运行成功 #include 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 { 第11页 广东机电职业技术学院信息工程学院 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<<"初始地图如下:"<>i>>j; if(Map[i][j]) {cout<<"不能从该处出发，请重新输入～"<