全球旧事资料 分类
实习报告、
题目:编制一个求解迷宫通路的程序班级:计算机04(2)姓名:王金锭学号:04120087完成日期:060301一.需求分析:
1.以二维数组Mazem2
2表示迷宫其中Maze0j和Mazem1j0j
1及Mazei0Mazei
10im1为添加的一圈障碍数组中以元素值为0表示通路1表示障碍限定迷宫的大小m
102.用户以文件的形式输入迷宫的数据文件中的第一行的数据为迷宫的行数m和列数
;从第二行至第m1每行
个数为迷宫值,同一行中的两个数字之间用空白字符相隔。3.迷宫的入口位置和出口位置可由用户随时设定。4.若设定的迷宫存在通路,则以长方阵形式将迷宫及其通路输出到标准输出文件即终端上,其中,字符“#”表示障碍,字符“*”表示路径上的位置,字符“”表示“死胡同”,即曾途径然而不能到达出口的位置,余者用空格符印出。若设定的迷宫不存在通路,则报告相应信息。5.本程序给出一条成功的通路,并且可以通过用户输入把所有的通路输出到指定的文件中。6.测试数据见原题,当入口位置为1,1,出口位置为9,8时,输出数据为:
二.概要设计:
1.设定栈的抽象数据类型定义:ADTStack数据对象:Daiai∈I
tSeti12…
0数据关系:ai1aiai1ai∈Di12…
基本操作:I
itStackS操作结果:构造一个空栈。DestroyStackS
f初始条件:栈S已存在操作结果:将S清空为空栈。ClearStackS初始条件:栈S已存在。操作结果:将S清为空栈。StackLe
gthS初始条件:栈S已存在。操作结果:返回栈S的长度。StackEmptyS初始条件:栈S已存在。操作结果:若S为空栈,则返回TURE,否则返回FAULE。GetTopSe初始条件:栈S已存在。操作结果:若S不空,则以e返回栈顶元素。PushSe初始条件:栈S存在。操作结果:在栈S的栈顶插入新的栈顶元素e。PopSe初始条件:栈S已存在。操作结果:删除S的栈顶元素,并以e返回其值。StackTraverseSvisit初始条件:栈S已存在。操作结果:从栈底到栈顶依次对S中的每个元素调用visit。ADTStack
2求解迷宫中的一条通路的伪码算法
设定当前位置的初值为入口位置do若当前位置可通则将当前位置插入栈顶若该位置是出口位置则结束否则切换当前位置的东邻方块为新的当前位置否则若栈不空且栈顶位置尚有其他方向未被搜索则设定新的当前位置为沿顺时针方向旋转找到的栈顶苇子后的下一个相邻块若栈不空但粘顶位置的四周均不可通则删去栈顶位置若栈不空则重新测试新的栈顶位置直至找r
好听全球资料 返回顶部