数据结构课程设计--随机漫步.doc

数据结构课程设计三班级：06计本（1） 姓名：魏建平 学号：20060724035 题目：数据结构教材第62页，第二章附加题第9题：“随机漫步”问题，即使用计算机“模拟”蟑螂漫步。要解决的问题是（1）打印蟑螂进行的合法移动总次数。（2）打印实验中每一块瓷砖被经历的次数。一、 需求分析1、数据存储结构分析：对于此“蟑螂漫步”问题的模拟，最主要的是数据存储结构的设计。对此，首先想到了两种结构：链表和数组。首先分析链表形式的存储结构。我们看到，“蟑螂漫步”问题中，蟑螂的移动是随机的。从一个地方出发可以随机向周围8个方位移动。如果使用链表的存储形式，固然可以记录蟑螂对每一块瓷砖的访问次数，但是，要实现“随机”二字确实非常不可取。通常链表是一个数据域一个链域，要实现从一个结点向周围8个结点都能移动，那么要增加7个链域。这是很不安全的，且增加之后也不再是链表，而是一个“网” 。结合问题初始提到的把房间划分成N*M个方格的思维，我认为选择二维数组作为数据存储结构是最好不过的。一来，不会造成指针的混乱；二来，能非常方便的解决蟑螂的随机移动问题。把整个可移动的房间放入一个坐标中。我们可以用一组坐标（ibut,jbug）来表示蟑螂的起始坐标。坐标原点规定为二维数组的第一个元素，即“数组名00” 。对于蟑螂的随机移动的表示，我们引入两个辅助数组imovek和jmovek。且imove=-1,0,1,1,1,0,-1,-1 jmove=1,1,1,0,-1,-1,-1,0其中K为随机数。而两个辅助数组中的每一个值代表蟑螂的移动方位，因此移动后的坐标可以这样表示：（ibug+imovek,jbug+jmogek）。通过随机数K的变化就巧妙的表示了蟑螂的随机移动。2、该试验结束条件是每一个方格都被至少进入一次，也许出现一直不终止的情况，即有方格一直没有被进入，所以程序中应该设置实验过程中进入方块的最大次数，保证程序能够终止。3、程序执行命令：（1）提示用户输入进行模拟矩阵的行列数；（2）提示用户输入蟑螂初始时在矩阵中的位置；（3）输入过程中能自动检验输入字符是否合法，如果不合法，给出相应的提示。4、测试数据（1）输入矩阵行与列分别为：15 15 起始位置为：（10，10）（结果见后面测试结果部分）；（2）输入矩阵行与列分别为：39 19 起始位置为：（1，1）（结果见后面测试结果部分）。二、 概要设计1、解决问题的各种操作：（1）漫步函数：void manbu(int n,int m,int ibug,int jbug)；（2）方格计数器初始化函数：void chuzhi(int n,int m)；（3）判断每个方格是否都至少进入了一次函数：bool panduan(int n,int m)；（4）漫步的密度函数：void midu(int n,int m)；（5）计算移动总次数函数：void cishu(int n,int m)；2、主程序Void main()接受命令（输入模拟矩阵的行列数）；接受命令（输入蟑螂初始所在位置）；处理命令；输入结果；3、函数之间的调用关系：三、 详细设计（一）第一种设计程序分析1、主函数需要的全程量#include#include #include #include using namespace std;int imove=-1,0,1,1,1,0,-1,-1;int jmove=1,1,1,0,-1,-1,-1,0;int h=0,z=0,k,a=0;int wu4020;char ch;2、漫步函数：void manbu(int n,int m,int ibug,int jbug)/漫步函数chuzhi(n,m);wuibugjbug=1;srand(unsigned)time(NULL);for(int j=1;j=n|ibug+imovek=m|jbug+jmovekm*n) if(panduan(n,m) break; 3、方格计数器初始化函数：void chuzhi(int n,int m)/方格计数器初始化为0for(int i=0;in;i+)for(int j=0;jm;j+)wuij=0;4、判断每个方格是否都至少进入了一次函数：bool panduan(int n,int m)/判断每个方格是否都至少进入了一次，如果都进入了一次则为真反之为假for(int i=0;in;i+)for(int j=0;jm;j+)if(wuij=0)return false;5、漫步的密度函数：void midu(int n,int m)/漫步的密度for(int i=0;in;i+)for(int j=0;jm;j+)printf(%4d,wuij);printf(n);6、计算移动总次数函数：void cishu(int n,int m)/合法移动总次数for(int i=0;im;i+)for(int j=0;jq; printf(请输入列数:); cinr; printf(请输入起始坐标:n); cinse; if(q40|q40|rch;if(ch=y)continue;elsebreak;8、函数调用关系图（二）第二种设计程序：#include #include #include #include using namespace std;void main()int seed = (unsigned)time(NULL); /利用系统时间获取一个产生随机数的种子int m, n; /地板的瓷砖行列数int count; /辅助变量，计数蟑螂到过的瓷砖的块数int random; /随机数int ibug, jbug; /蟑螂的位置int imove8 = -1,0,1,1,1,0,-1,-1; /蟑螂移动数组int jmove8 = 1,1,1,0,-1,-1,-1,0;int *matrix; /计数蟑螂到过每一块瓷砖的数目矩阵cout m;cout n;matrix = new int*m; /动态创建matrix数组for (int i=0; im; i+)matrixi = new intn;for (i=0; im; i+)for (int j=0; jn; j+)matrixij = 0;cout ibug jbug;count = 1;if (ibug=m | ibug=n | jbug0) /验证蟑螂初始位置cout 错误的初始位置n;return;matrixibugjbug = 1; /蟑螂初始位置坐标置1srand(seed);for (i=1; i=m | ibug+imoverandom=n | jbug+jmoverandom=m*n) /检测蟑螂是否已经到过所有的瓷砖for (int j=0; jm; j+)for (int k=0; kn; k+)if (matrixjk != 0)count+;if (count=m*n) /若蟑螂到到过所有的瓷砖break; /退出循环count = 0;cout 蟑螂总共移动的次数为: i-1endl;cout 蟑螂所经过每一块瓷砖的次数为:n;for (i=0; im; i+) /输出蟑螂到过每一块瓷砖的次数for (int j=0; jn; j+)cout setw(4)matrixij;cout endl;for (i=0; im; i+) /数组matrixdelete matrixi;四、 调试分析1、“随机漫步”问题长久以来一直吸引着数学界的兴趣，但即便是最简单的随机漫步问题，解决起来是极其困难，本课程设计只是一个模拟的随机问题，所以技术含量并不高。2、一开始设计了一个使用随机数的程序，运行起来相当的慢，要计算一个15行15列矩阵的“随机问题”需要运行差不多二个小时，后来经过改进，才形成第一种程序，运行速度非常的快。3、该程序设置进行得比较顺利，初始运行时只有几处小的错误，改正后就能正常运行了。五、 用户手册1、 本程序的运行环境为DOS操作环境，文件名为walk.exe;2、本例演示程序简单明了，按提示输入即可。六、 时间复杂度和空间复杂度分析1、 时间复杂度分析：对于程序的第一种设计，是用函数划分功能模块的方式，将漫步问题的每个步骤划分为一个个功能函数，然后调用这些函数来实现漫步过程。可以看到其中 cishu()函数 midu()函数 panduan()函数 chuzhi()函数都有两个for循环，每一个函数的时间复杂度为O（M）*O（N）。在 manbu()函数中有一个for循环，要循环50000次。最坏情况下其时间复杂度为：O（50000）。所以程序总的时间复杂度为：O（M）*O（N）*3O（50000）*O（M）*O（N）。对于程序的第二种设计，是在主函数中一并实现所有过程。没有使用函数来封装功能。它总共包含了九个for语句。第一个for语句的时间复杂度为O（M）。进入第二个for之后为O（M）*O（N）。进入第四个for语句之后的时间复杂度为：O（M*N）+O（50000-M*N）*O（M）*O（N）。进入第七个for的时间复杂度为：O（M）*O（N）。最后一个for：O（M）。因此，第二种程序总时间复杂度为：O（M）O（M）*O（N）+ O（M*N）+O（50000-M*N）*O（M）*O（N）+ O（M）*O（N）+ O（M）。 2、 空间复杂度分析：很明显可以看出：第一