1、数据结构课程设计三班级：06 计本（1） 姓名：魏建平 学号：20060724035 题目：数据结构教材第 62 页，第二章附加题第 9 题：“随机漫步”问题，即使用计算机“模拟”蟑螂漫步。要解决的问题是（1）打印蟑螂进行的合法移动总次数。 （2）打印实验中每一块瓷砖被经历的次数。一、 需求分析1、数据存储结构分析：对于此“蟑螂漫步”问题的模拟，最主要的是数据存储结构的设计。对此，首先想到了两种结构：链表和数组。首先分析链表形式的存储结构。我们看到， “蟑螂漫步”问题中，蟑螂的移动是随机的。从一个地方出发可以随机向周围 8 个方位移动。如果使用链表的存储形式，固然可以记录蟑螂对每一块瓷砖的访问
2、次数，但是，要实现“随机”二字确实非常不可取。通常链表是一个数据域一个链域，要实现从一个结点向周围 8 个结点都能移动，那么要增加 7 个链域。这是很不安全的，且增加之后也不再是链表，而是一个“网” 。结合问题初始提到的把房间划分成 N*M 个方格的思维，我认为选择二维数组作为数据存储结构是最好不过的。一来，不会造成指针的混乱；二来，能非常方便的解决蟑螂的随机移动问题。把整个可移动的房间放入一个坐标中。我们可以用一组坐标（ibut,jbug）来表示蟑螂的起始坐标。坐标原点规定为二维数组的第一个元素，即“数组名00” 。对于蟑螂的随机移动的表示，我们引入两个辅助数组 imovek和 jmovek
3、。且 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、入字符是否合法，如果不合法，给出相应的提示。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
5、(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;cha
6、r 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;iq;printf(“请输入列数:“);cinr;printf(“请输入起始坐标:n“);cinse;if(q40|q40|rc
7、h;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 jm
8、ove8 = 1,1,1,0,-1,-1,-1,0;int *matrix; /计数蟑螂到过每一块瓷砖的数目矩阵cout m;cout n;matrix = new int*m; /动态创建 matrix 数组for (int i=0; i ibug jbug;count = 1;if (ibug=m | ibug=n | jbug=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
9、 (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、 “随机漫步”问题长久以来一直吸引着数学界的兴趣，但即便是最简单的随机漫步问题，解决起来是极其困难，本课程设计只是一个模拟的随机问
10、题，所以技术含量并不高。2、一开始设计了一个使用随机数的程序，运行起来相当的慢，要计算一个 15 行 15 列矩阵的“随机问题”需要运行差不多二个小时，后来经过改进，才形成第一种程序，运行速度非常的快。3、该程序设置进行得比较顺利，初始运行时只有几处小的错误，改正后就能正常运行了。五、 用户手册1、 本程序的运行环境为 DOS 操作环境，文件名为 walk.exe;2、本例演示程序简单明了，按提示输入即可。六、 时间复杂度和空间复杂度分析1、 时间复杂度分析：对于程序的第一种设计，是用函数划分功能模块的方式，将漫步问题的每个步骤划分为一个个功能函数，然后调用这些函数来实现漫步过程。可以看到其中
11、 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
12、语句之后的时间复杂度为： 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、 空间复杂度分析：很明显可以看出：第一种程序设计用的是一个固定大小的数组，而第二种程序设计用的是动态分配数组。其他方面均相差不大，对于空间复杂度的问题，最主要的就在于一个动态数组一个固定数组。动态数组能按照实时需要来分配合适的内存空间，而固定的数组则不能办到。当需要的数据小时，固定数组必然会浪费大量的内存空间；当需要大量数据时，固定数组必然会出错，不能达到需要。故而，使用动态数组能更好的满足需要且节约大量的内存空间，程序灵活性更大。七、 测试结果
