迷宫老鼠_数据结构与算法

《迷宫老鼠_数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.问题：迷宫老鼠问题的解答2.算法的基本思想：定义一个字符型二维数组，通过调用随机函数给数组赋值，从而在每次运行程序的时候得到不同的数组值，从而用其代表一个随机的迷宫地图。该问题的解决关键是如何判断是否存在可行的路径，如果存在如何记录并找出来。该程序是通过栈来解决的，其中栈是用数组实现的。基本思想如下，先随机产生一个迷宫（二维数组中‘’代表可走的位置，‘0’代表迷宫中的障碍物，“*”是围墙），定义一个寻找路径的函数，其返回值为真假。函数中先定义一个栈，将其置空初始化。目标放在开始处，将其置为‘Z’，然后判断目标当前位置是否在出口位置，如果不在

2、则以此判断目标当前位置的前后左右是否可以走，成立的条件是不能碰到围墙，并且要走到的位置为‘’，可以走的话就让目标行进到该位置然后将方向（0代表右，1代表下，2代表左，3代表上）入栈，如果四个方向都走不通了，判断栈是否为空，如果为空则函数返回false即失败了，老鼠走不出去；如果栈不为空，取出栈顶元素并弹栈，接着判断取出的栈顶元素进而判断出最近一步的方向，然后让目标逆着该方向移动一步。如果判断目标当前位置在出口处，函数返回true即成功了老鼠可以出去，定义一个新栈将原来栈中的元素逆序存储起来。将当前迷宫中为‘Z’的位置置为‘’，将目标置于开始处，

3、取栈顶元素来判断方向，相应移动目标，紧随弹栈，如此循环直到新栈为空为止。每移动一步将迷宫画一次。如此则能动态的描绘出老鼠所走的路径。3.主要数据结构：线性表中的栈4.主要函数功能：程序中一共有三个函数如下所示（1）迷宫初始化函数voidMigonglaoshu::Migong()（2）迷宫输出函数voidMigonglaoshu::Display()const（3）利用栈找到并存储老鼠的可行路径函数boolMigonglaoshu::Path()此外还有一些最基本的函数，包括通过指针来实现栈的一系列操作函数，类的构造函数和析构函数。在这些基本函

4、数的支持下使得本程序可以执行。将栈置空：voidMakeNull()将一个元素压入栈中：voidPush(intx,STACKS)弹栈voidPop(STACKS)取出栈顶元素intTop(STACKS)判断栈是否为空boolEmpty(STACKS)构造函数给类的变量赋值Migonglaoshu::Migonglaoshu(inth,intw):row(h),col(w)析构函数Migonglaoshu::~Migonglaoshu()5.算例：算例1（老鼠不能逃出）请输入迷宫的行数和列数（1010）：1530请输入迷宫的行数和列数（1010

5、）1530*******************************ZOOOOOOOOOOOOOOO**OOOOOOOOOOOO**OOOOO**OOOOOOOO**OOOOOOOOOOOOOOO**OOOOOO**OOOOOOOOOOOO**OOOOOOOO**OOOOOOO**OOOOOOO**OOOO**OOOOOOOOOO**OOOOOO*******************************请按任意键继续...老鼠不能逃走!算例2（老鼠成功逃出）请输入迷宫的行数和列数（1010）：1530******************

6、*************ZOOOOOO**OOOOO**OOOOOOOOOO**OOOOOO**OOOOOOOO**OOOO**OOOOOOOOOO**OOOOOO**OOO**OOOOOOOOOOOO**OOOOOOOOOOOO**OOOOOOOOO**OOOOOOOOO*******************************请按任意键继续...*******************************ZOOOOOO**ZZZZZOOOOO**OOOZOOOOOOO**OOZZZZZZZZZZOOOO**OOOOZOOOO**OZ

7、ZOOO**OOOOZOOOOOO**OOOZOOO**OZZZZZZOO**OOOOOOOZOOOOO**OOOOOOOOZOOOO**OOOOOOOZZZZZOO**OOOOOOOOOZZZZZ*******************************老鼠成功逃出迷宫!Pressanykeytocontinue6.算法性能分析：（1）输入：外部可以输入迷宫的行数和列数。（2）输出：程序输出结果为初始化以后的迷宫以及老鼠可以走出去的前提下老鼠每一步是如何移动的（即前后左右）。（3）确定性：算法中每一条语句都有明确的含义。（4）有限性：算法

8、中的所有循环结构都有正确合适的控制条件，不论老鼠能否走出去，都不会陷入死循环。程序运行有限步以后就会停止，然后输出结果。（5）可行性：算法中的每一个运