数据结构栈和队列迷宫问.docx

数据结构栈和队列迷宫问.docx

ID:61510466

大小:150.74 KB

页数:9页

时间:2021-02-08

数据结构栈和队列迷宫问.docx_第1页
数据结构栈和队列迷宫问.docx_第2页
数据结构栈和队列迷宫问.docx_第3页
数据结构栈和队列迷宫问.docx_第4页
数据结构栈和队列迷宫问.docx_第5页
资源描述:

《数据结构栈和队列迷宫问.docx》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、数据结构实验报告1.实验目的通过选择下面五个题目之一进行实现,掌握如下内容:·进一步掌握指针、模板类、异常处理的使用·掌握栈的操作的实现方法·掌握队列的操作的实现方法·学习使用栈解决实际问题的能力·学习使用队列解决实际问题的能力2.实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下:心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口,测试算法的迷宫如下图所示。提示:1、可以使用递归或非递归两种方法实现2、老鼠能够记住已经走过的路,不会反复走重复的路径3、可以

2、自己任意设置迷宫的大小和障碍4、使用“穷举求解”的方法2.程序分析2.1存储结构存储结构:顺序栈datadatadataA1A2A3A2A1toptoptop(1)空栈(2)A1A2入栈(3)A3出栈2.2关键算法分析1.试探方向:(1)基本思想每个点有4个方向去试探,如当前点的坐标(x,y),与其相邻的4个点的坐标都可根据与该点的相邻方位而得到,如图所示。因为出口在(m,n),因此试探顺序规定为:从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题,方便的求出新点的坐标,将从正东开始沿顺时针进行的这4个方向(用0,1,2,3表示东、南、西、北)的坐标增量放在一个结构数组

3、move[4]中,在move数组中,每个元素有两个域组成,x:横坐标增量,y:纵坐标增量。(x,y)与点(x,y)相邻的4个点及坐标(x,y+1)(x,y-1)(x+1,y)(x-1,y)xy00111020-13-10增量move数组(2)基本代码structitem{intx;//行inty;//列};itemmove[4];2.寻找路径(1)基本思想:利用栈的结构,走过的路入栈,如果不能走出栈,采用遍历法,因此栈内存储的数据就是寻一条路径。当到达了某点而无路可走时需返回前一点,再从前一点开始向下一个方向继续试探。因此,压入栈中的不仅是顺序到达的各点的坐标,而且还要有从前一点到

4、达本点的方向,即每走一步栈中记下的内容为(行,列,来的方向)。(2)代码栈构造函数:voidseqstack::Push(intx,inty,intd)//入栈{if(top>=StackSize-1)throw"上溢";top++;data[top].d=d;data[top].x=x;data[top].y=y;}寻找路径:intseqstack::findpath(inta,intb){itemmove[4]={{0,1},{1,0},{0,-1},{-1,0}};//定义移动结构intx,y,d,i,j;Push(a,b,-1);//起点坐标入栈while(top!=-1)

5、{d=data[top].d+1;x=data[top].x;y=data[top].y;Pop();//出栈while(d<4)//方向是否可以移动{i=x+move[d].x;j=y+move[d].y;//移动后坐标if(Map[i][j]==0)//是否能移动{Push(x,y,d);//移动前坐标入栈x=i;y=j;Map[x][y]=-1;if(x==m&&y==n)//判断是否为终点坐标{Push(x,y,-1);return1;}elsed=0;}elsed++;}}return0;}(1)伪代码a)栈初始化;b)将入口点坐标及到达该点的方向(设为-1)入栈c)wh

6、ile(栈不空){栈顶元素=(x,y,d)出栈;求出下一个要试探的方向d++;while(还有剩余试探方向时){if(d方向可走)则{(x,y,d)入栈;求新点坐标(i,j);将新点(i,j)切换为当前点(x,y);if((x,y)==(m,n))结束;else重置d=0;}elsed++;}}(2)时间复杂程度时间复杂程度为O(1)2.3其他在运行时可选择是否自己构造地图,实现函数如下:voidcreatmap()//自创地图函数{for(inti=1;i<9;i++){for(intj=1;j<9;j++)Map[i][j]=0;}Map[8][9]=1;printmap();

7、cout<<"请设置障碍物位置:(x,y)。(0,0)结束"<>p>>q;if(p==0&&q==0){cout<<"设置完成"<

8、

9、q<=0

10、

11、p>=9

12、

13、q>=9){cout<<"输入错误!"<>q>>p;m=p

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。