数据结构课程设计三

班级：06计本（1）姓名：魏建平学号：20060724035

题目：数据结构教材第62页，第二章附加题第9题：“随机漫步”问题，即使用计算机“模拟”蟑螂漫步。

要解决的问题是（1）打印蟑螂进行的合法移动总次数。（2）打印实验中每一块瓷砖被经历的次数。

一、需求分析。

1、数据存储结构分析：

对于此“蟑螂漫步”问题的模拟，最主要的是数据存储结构的设计。对此，首先想到了两种结构：链表和数组。

首先分析链表形式的存储结构。我们看到，“蟑螂漫步”问题中，蟑螂的移动是随机的。从一个地方出发可以随机向周围8个方位移动。

如果使用链表的存储形式，固然可以记录蟑螂对每一块瓷砖的访问次数，但是，要实现“随机”二字确实非常不可取。通常链表是一个数据域一个链域，要实现从一个结点向周围8个结点都能移动，那么要增加7个链域。这是很不安全的，且增加之后也不再是链表，而是一个“网” 。

结合问题初始提到的把房间划分成n*m个方格的思维，我认为选择二维数组作为数据存储结构是最好不过的。一来，不会造成指针的混乱；二来，能非常方便的解决蟑螂的随机移动问题。

把整个可移动的房间放入一个坐标中。我们可以用一组坐标（ibut,jbug）来表示蟑螂的起始坐标。坐标原点规定为二维数组的第一个元素，即“数组名[0][0]” 对于蟑螂的随机移动的表示，我们引入两个辅助数组imove[k]和jmove[k]。

且imove=jmove=其中k为随机数。而两个辅助数组中的每一个值代表蟑螂的移动方位，因此移动后的坐标可以这样表示：（ibug+imove[k],jbug+jmoge[k]）。

通过随机数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 <>

using namespace std;

int imove=

int jmove=

int h=0,z=0,k,a=0;

int wu[40][20];

char ch;

2、漫步函数：

void manbu(int n,int m,int ibug,int jbug)//漫步函数。

chuzhi(n,m);

wu[ibug][jbug]=1;

srand((unsigned)time(null));

for(int j=1;j<=50000;j++)

3、方格计数器初始化函数：

void chuzhi(int n,int m)//方格计数器初始化为0

for(int i=0;i

4、判断每个方格是否都至少进入了一次函数：

bool panduan(int n,int m)//判断每个方格是否都至少进入了一次，如果都进入了一次则为真反之为假。

for(int i=0;i

5、漫步的密度函数：

void midu(int n,int m)//漫步的密度。

for(int i=0;i

printf("");

6、计算移动总次数函数：

void cishu(int n,int m)//合法移动总次数。

for(int i=0;i

printf("%d",a);

a=0;7、主函数：

void main()

int q,r,s,e;

for(;;

8、函数调用关系图。

二）第二种设计程序：

#include

#include <>

using namespace std;

void main()

int seed = unsigned)time(null利用系统时间获取一个产生随机数的种子。

int m, n地板的瓷砖行列数。

int count辅助变量，计数蟑螂到过的瓷砖的块数。

int random随机数。

int ibug, jbug蟑螂的位置。

int imove[8] =

int **matrix计数蟑螂到过每一块瓷砖的数目矩阵。

cout <<输入地板瓷砖的行数输入地板瓷砖的行列数。

cin >>m;

cout <<输入地板瓷砖的列数";

cin >>n;

matrix = new int*[m动态创建matrix数组。

for (int i=0; i

for (i=0; i

cout <<请给出蟑螂的初始位置输入蟑螂的初始位置。

cin >>ibug >>jbug;

count = 1;

if (ibug>=m ||ibug<0 ||jbug>=n ||jbug<0) /验证蟑螂初始位置。

matrix[ibug][jbug] =1蟑螂初始位置坐标置1

srand(seed);

for (i=1; i<=50000; i蟑螂在地板上移动。

random = rand()%8;

if (ibug+imove[random]>=m ||ibug+imove[random]<0 ||

jbug+jmove[random]>=n ||jbug+jmove[random]<0)//当蟑螂移动到墙壁时，进入下一轮循环。

continue;

ibug +=imove[random改变蟑螂位置。

数据结构课程设计三

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了