1、数据结构数据结构课程设计课程设计三三 题目：题目：数据结构教材第 62 页，第二章附加题第 9 题： “随机漫步”问题，即使用计算机“模 拟”蟑螂漫步。要解决的问题是（1）打印蟑螂进行的合法移动总次数。 （2）打印实验中每 一块瓷砖被经历的次数。 一、一、 需求分析需求分析 1、数据存储结构分析： 对于此“蟑螂漫步”问题的模拟，最主要的是数据存储结构的设计。对此，首先想到了 两种结构：链表和数组。 首先分析链表形式的存储结构。我们看到， “蟑螂漫步”问题中，蟑螂的移动是随机的。 从一个地方出发可以随机向周围 8 个方位移动。 如果使用链表的存储形式， 固然可以记录蟑 螂对每一块瓷砖的访问次数，
2、但是，要实现“随机”二字确实非常不可取。通常链表是一个 数据域一个链域，要实现从一个结点向周围 8 个结点都能移动，那么要增加 7 个链域。这是 很不安全的，且增加之后也不再是链表，而是一个“网” 。 结合问题初始提到的把房间划分成 N*M 个方格的思维， 我认为选择二维数组作为数据存 储结构是最好不过的。一来，不会造成指针的混乱；二来，能非常方便的解决蟑螂的随机移 动问题。 把整个可移动的房间放入一个坐标中。我们可以用一组坐标（ibut,jbug）来表示蟑螂 的起始坐标。坐标原点规定为二维数组的第一个元素，即“数组名00” 。对于蟑螂的 随 机 移 动 的 表 示 ， 我 们 引 入 两 个
3、 辅 助 数 组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）提示用户输入进行模拟矩阵的行列数；
4、 （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、主程序 V oid main() 接受命令（输入模拟矩阵的行列数） ； 接受命令（输入蟑螂初始所在位置） ； 处理命令； 输入结果；
