资源描述：
《数据结构课程设计--随机漫步》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构课程设计三班级：06计本（1）姓名：魏建平学号：20060724035题目：数据结构教材第62页，第二章附加题第9题：“随机漫步”问题，即使用计算机“模拟”蟑螂漫步。要解决的问题是（1）打印蟑螂进行的合法移动总次数。（2）打印实验中每一块瓷砖被经历的次数。一、需求分析1、数据存储结构分析：对于此“蟑螂漫步”问题的模拟，最主要的是数据存储结构的设计。对此，首先想到了两种结构：链表和数组。首先分析链表形式的存储结构。我们看到，“蟑螂漫步”问题中，蟑螂的移动是随机的。从一个地方出发可以随机向周围8个方位移动。如果使用链表的存储形式，固然可以记录蟑螂对每一块瓷砖的访问次数，但是
2、，要实现“随机”二字确实非常不可取。通常链表是一个数据域一个链域，要实现从一个结点向周围8个结点都能移动，那么要增加7个链域。这是很不安全的，且增加之后也不再是链表，而是一个“网”。结合问题初始提到的把房间划分成N*M个方格的思维，我认为选择二维数组作为数据存储结构是最好不过的。一来，不会造成指针的混乱；二来，能非常方便的解决蟑螂的随机移动问题。把整个可移动的房间放入一个坐标中。我们可以用一组坐标（ibut,jbug）来表示蟑螂的起始坐标。坐标原点规定为二维数组的第一个元素，即“数组名[0][0]”。对于蟑螂的随机移动的表示，我们引入两个辅助数组imove[k]和jmove[k
3、]。且imove[]={-1,0,1,1,1,0,-1,-1}jmove[]={1,1,1,0,-1,-1,-1,0}其中K为随机数。而两个辅助数组中的每一个值代表蟑螂的移动方位，因此移动后的坐标可以这样表示：（ibug+imove[k],jbug+jmoge[k]）。通过随机数K的变化就巧妙的表示了蟑螂的随机移动。2、该试验结束条件是每一个方格都被至少进入一次，也许出现一直不终止的情况，即有方格一直没有被进入，所以程序中应该设置实验过程中进入方块的最大次数，保证程序能够终止。3、程序执行命令：（1）提示用户输入进行模拟矩阵的行列数；（2）提示用户输入蟑螂初始时在矩阵中的位置；
4、（3）输入过程中能自动检验输入字符是否合法，如果不合法，给出相应的提示。4、测试数据（1）输入矩阵行与列分别为：1515起始位置为：（10，10）（结果见后面测试结果部分）；（2）输入矩阵行与列分别为：3919起始位置为：（1，1）（结果见后面测试结果部分）。二、概要设计1、解决问题的各种操作：（1）漫步函数：voidmanbu(intn,intm,intibug,intjbug)；（2）方格计数器初始化函数：voidchuzhi(intn,intm)；（3）判断每个方格是否都至少进入了一次函数：boolpanduan(intn,intm)；（4）漫步的密度函数：voidmid
5、u(intn,intm)；（5）计算移动总次数函数：voidcishu(intn,intm)；2、主程序Voidmain(){接受命令（输入模拟矩阵的行列数）；接受命令（输入蟑螂初始所在位置）；处理命令；输入结果；}3、函数之间的调用关系：一、详细设计（一）第一种设计程序分析1、主函数需要的全程量#include#include#include#includeusingnamespacestd;intimove[]={-1,0,1,1,1,0,-1,-1};intjmove[]={1,1,1,0,-1,-
6、1,-1,0};inth=0,z=0,k,a=0;intwu[40][20];charch;2、漫步函数：voidmanbu(intn,intm,intibug,intjbug)//漫步函数{chuzhi(n,m);wu[ibug][jbug]=1;srand((unsigned)time(NULL));for(intj=1;j<=50000;j++){k=rand()%8;if(ibug+imove[k]>=n
7、
8、ibug+imove[k]<0
9、
10、jbug+jmove[k]>=m
11、
12、jbug+jmove[k]<0)continue;//如果越界，则跳到下一次循环ibug=ib
13、ug+imove[k];jbug=jbug+jmove[k];//监视横坐标和纵坐标wu[ibug][jbug]++;if(j>m*n){if(panduan(n,m))break;}}}3、方格计数器初始化函数：voidchuzhi(intn,intm)//方格计数器初始化为0{for(inti=0;i
