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

1.问题：迷宫老鼠问题的解答2.算法的基本思想：定义一个字符型二维数组，通过调用随机函数给数组赋值，从而在每次运行程序的时候得到不同的数组值，从而用其代表一个随机的迷宫地图。该问题的解决关键是如何判断是否存在可行的路径，如果存在如何记录并找出来。该程序是通过栈来解决的，其中栈是用数组实现的。基本思想如下，先随机产生一个迷宫（二维数组中 代表可走的位置，0代表迷宫中的障碍物，“*”是围墙），定义一个寻找路径的函数，其返回值为真假。函数中先定义一个栈，将其置空初始化。目标放在开始处，将其置为Z，然后判断目标当前位置是否在出口位置，如果不在则以此判断目标当前位置的前后左右是否可以走，成立的条件是不能碰到围墙，并且要走到的位置为 ，可以走的话就让目标行进到该位置然后将方向（0代表右，1代表下，2代表左，3代表上）入栈，如果四个方向都走不通了，判断栈是否为空，如果为空则函数返回false即失败了，老鼠走不出去；如果栈不为空，取出栈顶元素并弹栈，接着判断取出的栈顶元素进而判断出最近一步的方向，然后让目标逆着该方向移动一步。如果判断目标当前位置在出口处，函数返回true即成功了老鼠可以出去，定义一个新栈将原来栈中的元素逆序存储起来。将当前迷宫中为Z的位置置为 ，将目标置于开始处，取栈顶元素来判断方向，相应移动目标，紧随弹栈，如此循环直到新栈为空为止。每移动一步将迷宫画一次。如此则能动态的描绘出老鼠所走的路径。3.主要数据结构：线性表中的栈4.主要函数功能：程序中一共有三个函数如下所示（1）迷宫初始化函数void Migonglaoshu:Migong()（2）迷宫输出函数void Migonglaoshu:Display()const （3）利用栈找到并存储老鼠的可行路径函数bool Migonglaoshu:Path()此外还有一些最基本的函数，包括通过指针来实现栈的一系列操作函数，类的构造函数和析构函数。在这些基本函数的支持下使得本程序可以执行。将栈置空：void MakeNull() 将一个元素压入栈中：void Push(int x,STACK S) 弹栈void Pop(STACK S) 取出栈顶元素int Top(STACK S) 判断栈是否为空bool Empty(STACK S)构造函数给类的变量赋值Migonglaoshu:Migonglaoshu(int h,int w):row(h), col(w) 析构函数Migonglaoshu:Migonglaoshu()5.算例： 算例1（老鼠不能逃出）请输入迷宫的行数和列数（10 10）：15 30请输入迷宫的行数和列数（10 10）15 30*ZOOOOO O OOOO OO O O O * O O OOO OO OO O O O* OO O O O *O OO OO OO O * O OO OOO OOO OOO OO O* O O OO O O *OOOOO O OO O O O O * O O OO O O O O* O OO O OO O * O OO O O O O* O O O O * O OO O O O OOO O* O O O O O O*请按任意键继续. . .老鼠不能逃走! 算例2（老鼠成功逃出）请输入迷宫的行数和列数（10 10）：15 30*ZO O O OO O * O O O O O *OOO OO O O O O O *OO O O OO * OO O O OO O O * O O OO * O OOO OO OOO O* OO O OO O * O O O* O OOO O O O O O O OO*O O O OOO OO OO O O * O O O OOO O O O* OO OOO O O OO *请按任意键继续. . .*ZO O O OO O *ZZZZZO O O O O *OOO ZOO O O O O O *OO ZZZZZZZZZZ O O OO * OO O OZOO O O * O ZZO OO * O OOO Z OO OOO O* OO O ZOO O * O ZZZZZZ O O* O OOO O O O ZO O O OO*O O O OOO OO ZOO O O * O O O OOO OZZZZZO O* OO OOO O O OOZZZZZ*老鼠成功逃出迷宫!Press any key to continue6.算法性能分析：（1）输入：外部可以输入迷宫的行数和列数。（2）输出：程序输出结果为初始化以后的迷宫以及老鼠可以走出去的前提下老鼠每一步是如何移动的（即前后左右）。（3）确定性：算法中每一条语句都有明确的含义。（4）有限性：算法中的所有循环结构都有正确合适的控制条件，不论老鼠能否走出去，都不会陷入死循环。程序运行有限步以后就会停止，然后输出结果。（5）可行性：算法中的每一个运算步骤都可以精确地执行，而且做又穷次运算后即可完成。7.程序运行环境：Microsoft Visual C+ 6.08.源码：#include#include#includeusing namespace std;const int East = 0;const int South = 1;const int West = 2;const int North = 3;const int pause = 30; /用指针的方式实现栈的各种操作struct nodeint val;node *next;typedef node * STACK;/将栈置空void MakeNull()STACK S;S=new node;S-next=NULL;/将一个元素压入栈中void Push(int x,STACK S)STACK stk;stk=new node;stk-val=x;stk-next=S-next;S-next=stk;/弹栈void Pop(STACK S)STACK stk;if(S-next)stk=S-next;S-next=stk-next;delete stk;/取出栈顶元素int Top(STACK S)if(S-next)return(S-next-val);else return NULL;/判断栈是否为空bool Empty(STACK S)if(S-next)return false;elsereturn true;/定义一个类（Migonglaoshu）class Migonglaoshupublic: Migonglaoshu(int row,int col); Migonglaoshu(); void Display()const; bool Path();private: const int row; const int col; char *Map; void Migong();/利用构造函数给类的变量赋值Migonglaoshu:Migonglaoshu(int h,int w):row(h), col(w)Map = new char *row; for (int i=0; irow; +i) Mapi = new charcol; Migong();/析构函数Migonglaoshu:Migonglaoshu() for (int i=0; irow; i+) delete Mapi; delete Map;/迷宫输出函数void Migonglaoshu:Display()const for (int i=0; irow; +i) for (int j=0; jcol; +j) cout Mapij; cout endl; /迷宫初始化函数void Migonglaoshu:Migong()srand(time(NULL); for (int i=0; irow; +i) for (int j=0; jcol; +j) if (i=0) | (j=0) | (i=row-1) | (j=col-1) Mapij = *; continue; if (rand() % 100 next=NULL; while (true) if(i=row-2 & j=col-2) int m, n;STACK newStack;newStack=new node;newStack-next=NULL; while (!Empty(Stack) Push(Stack-next-val,newStack); Pop(Stack); for (m=0; mrow; +m) for (n=0; ncol; +n)if (Mapmn = Z) Mapmn = ; m = 1; n = 1; Mapmn = Z;Maprow-2col-2= ; while (!Empty(newStack) flag = Top(newStack); switch (flag) case East: +n; break; case South: +m; break; case West: -n; break; case North: -m; break; Mapmn = Z; Sleep(pause); system(cls); Display(); Pop(newStack); return true; /East: if (j+1 col-1) & (Mapij+1 = ) Mapi+j = Z; Push(0,Stack); /South: else if (i+1 0) & (Mapij-1 = )Mapi-j = Z; Push(2,Stack); /North: else if (i-1 0) & (Mapi-1j = ) Map-ij = Z; Push(3,Stack); else if(Empty(Stack) return false;flag = Top(Stack);Pop(Stack); switch (flag) case East: -j;break; case South: -i; break; case West: +j;break;