北邮数据结构实验二题目3

北京邮电大学电信工程学院第1页北京邮电大学电信工程学院第1页2008级数据结构实验报告实验名称：实验二栈和队列学生姓名：班级：2008211113班内序号：学号：日期：2009年11月8日实验要求a.实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力b.实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。2.程序分析2.1存储结构存储结构:队列顺序存储结构示意图如下:2.2关键算法分析核心算法思想：如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。为查找最短路径，使用了“图”中的算法：广度优先搜索。关键算法思想描述和实现：关键算法1：为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。C++实现：structNode { int parent_id; //保存父节点的位置 int node_id; //当前节点的序号，以便传递给孩子节点 int x,y; //当前结点对应的坐标 }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,intk){ 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++实现：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]) { EnQueue(i,j,k); Map[i][j]=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=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.程序运行结果开始输出迷宫图输出迷宫图输入x,y输入x,y否否(x,y)是否合法(x,y)是否合法是是广度优先搜索广度优先搜索标记最短路径标记最短路径输出最短路径输出最短路径结结束测试条件：以实验题目中给出的迷宫图进行测试。测试时固定终点位置，选择不同的起点位置进行测试，测试各个位置下的输出是否正常。测试结论：本程序对于测试地图在不同起始和终止位置输出都完全正确。

4.总结1、在最初尝试编写代码时，采用的是递归算法。虽然用栈实现代码很简单，只需要向四个方向不断递归即可，但是使用栈并不能保证输出的路径是最佳路径。所以在完成了递归算法之后，我开始思索如何能输出最短路径。查找大量资料，结论是用栈很难实现，即使要实现也需要不断比较各种路径的长短，然后不断更新最短路径。偶然发现迪杰斯特拉算法，后又学习广度优先搜索算法，才用队列才最终使得问题得以解决。2、在将新算法应用到迷宫问题过程中，遇到不少困难，反复琢磨和看书才将其解决。由于顺序队列的出队入队操作加上了赋值和标记位置、建立链表关系，实际将一个顺序队列以指针的作用，变成了一棵树的结构，而树的深度恰好能反映最短路径。3、从一个小小的迷宫问题，引出了许多知识，这种探索式的学习是很有意义的。从迷宫基本的递归和回溯到栈的运用和理解，再到队列的运用，后又到树与图以及队列的综合运用，将很多知识点串联起来了，加深了理解。同时探索式地学习迪杰斯特拉算法也收获颇多。4、改进：本题为了实现代码的简便，没有采用链队结构，因而浪费了一定的空间，特别是当迷宫的边长很长的时候，空间复杂度