数据结构实验报告-栈和队列.doc

《数据结构实验报告-栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2008级数据结构实验报告实验名称：实验二栈和队列学生姓名：班级：班内序号：学号：日期：2009年11月8日1．实验要求a.实验目的通过选择下面五个题目之一进行实现，掌握如下内容：Ø进一步掌握指针、模板类、异常处理的使用Ø掌握栈的操作的实现方法Ø掌握队列的操作的实现方法Ø学习使用栈解决实际问题的能力Ø学习使用队列解决实际问题的能力b.实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算

2、法的迷宫如下图所示。2.程序分析2.1存储结构存储结构:队列顺序存储结构示意图如下:2.2关键算法分析核心算法思想：1.如果采用直接递归的方式，用栈很容易实现路径的输出，但是这条路径不一定是最短路径。为了改进算法，达到输出最短路径的目标，采用队列的实现方式。2.为查找最短路径，使用了“图”中的算法：广度优先搜索。关键算法思想描述和实现：关键算法1：为寻求最短路径，采用广度优先搜索算法，使用队列实现路径存储，队列中每个元素用结构体存储系，包含迷宫坐标、队列中的序号、父节点的序号，实现了对路径的记录。C++实现：structNode{intparent_id;//保存父

3、节点的位置intnode_id;//当前节点的序号，以便传递给孩子节点intx,y;//当前结点对应的坐标}Q[10*10];//每个节点包含迷宫坐标、队列中的序号、父节点的序号，多个节点形成队列关键算法2：遍历每个位置四周的位置，将没有走过的位置入队，形成树形的队列，通过出队操作就能找到最短路径。C++实现：boolGetNextPos(int*i,int*j,intcount){switch(count){case1:(*j)++;return1;//右case2:(*i)++;return1;//下case3:(*j)--;return1;//左case4:(

4、*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：广度优先搜索算法的实现，找到最短路径。广度优先算法在此相当于树的层序遍历，如下图：在迷宫地图中，关键算法三通过不断调用关键算法二就能将地图中可以走的位置入队，形成类似上图的树形结构，之后广度搜索到最浅深度即为最短路径。

5、例如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(

6、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），从父节点又可

7、以同理找到它的父节点第三号节点。这样就能实现逆序找到路径。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)是否合法是广度优先搜索标记最短路径输出最短路径结束测试条件：以实验题目中给出的迷宫图进行测试。测试时固定终点位置，