- 1、本文档共17页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
嘉兴学院数据结构C课程设计选编
目录
问题描述....................................1
问题分析....................................1
数据结构描述............................1
算法设计....................................1
主程序代码................................4
程序运行结果..........................14
七.实验小结..................................151.问题描述:
给定一个M*N的迷宫图,求一条从指定入口到出口的路径。假设迷宫图如图M=10,N=1 ,其中的方块图表示迷宫。对于途中的每个方块,用空格表示通道,用阴影表示墙。要求所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。
2.问题分析:
为了表示迷宫,设置一个数组a,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块不可走。
3.数据结构描述:
在算法中用到的栈采用顺序栈存储结构,将栈定义如下:
Struct Box
{
Public int i;
Public int j;
Public int di;
};
Struct StType
{
Public Box[] data;
Public int top;
};
StType st=new StType();
4.算法设计:
求迷宫问题就是在一个指定的迷宫中求出入口到出口的路径。求解时,通常用的是“穷举求解”的方法。即从入口出发,顺某一方向向前试探,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续试探,直到所有可能的通路都试探完为止。
为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。
对于迷宫中的每个方块,有上、下、左、右4个方块相邻,第i行第j列的方块的位置记为(i,j),规定上方方块为方位0,并按顺时针方向递增编号。在试探过程中,假设从方位0到方位3的方向查找下一个可走的方块。
为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中。
求解迷宫(xi,yi)到(xe,ye)路径的过程是:先将入口进栈,在栈不空时循环:取栈顶方块(不退栈),若该方块是出口,则输出栈中所有方块即为路径。否则,找下一个可走的相邻方块,若不存在这样的方块,说明当前路径不可能走通,则回溯,也就是恢复当前方块为0后退栈。若存在这样的方块??则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(其初始方位设置为-1)。
求迷宫路径的回溯过程中,从前一方块找到一个可走相邻方块即当前方块后,再从当前方块找相邻可走方块,若没有这样的方块,说明当前方块不可能是从入口到出口路径上的一个方块,则从当前方块回溯到前一方块,继续从前一方块找另一个可走的相邻方块。
为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)的下一可走方块时,又试探到(i,j),这样可能会引起死循环。为此,在一个方块进栈后,将对应的a数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示该栈顶方块没有可走相邻方块),将其恢复为0。
求解一条从入口(xi,yi)到出口(xe,ye)的迷宫路径的算法如下:
Public bool mgpath(int xi,int yi,int xe,int ye)
{
Int I,j,k,di,find;
st.data=new Box[MaxSize];
st.top=-1; //初始化栈顶指针
st.top++; //初始入口方块进栈
st.data[st.top].i=xi;st.data[st.top].j=yi;
st.data[st.top].di=-1;a[xi,yi]=-1;
while (st.top -1) //栈不空时循环
{
i = st.data[st.top].i;
j = st.data[st.top].j;
di = st.
您可能关注的文档
最近下载
- 顶管专项施工组织设计与对策.pdf
- 小学书法社团教学计划(共14篇).docx
- 企业管理咨询 时段四作业(第七-八章).docx VIP
- 《抗生素合理使用》课件.pptx VIP
- 肉牛养殖技术:肉牛体脂肪与肌肉的沉积规律.doc
- Haier海尔家用电热水器 FCD-JTHC40-III 使用说明书.PDF VIP
- NFPA 855-2023 Standard for the Installation of Stationary Energy Storage Systems 固定储能系统安装标准.pdf
- 0508-美容美发与造型(美容)专业国家技能人才培养工学一体化课程设置方案(试用).docx VIP
- 堆垛机维护保养手册.doc
- 《小狗的房子》教学设计4篇.docx
文档评论(0)