《数据结构实验报告熊猫烧香.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告熊猫烧香.docx（11页珍藏版）》请在三一办公上搜索。
1、数据结构实验报告熊猫烧香数据结构课程设计报告书 姓名: 辅导老师: 班级: 学号: 日期: 1 一、 课程设计题目： 熊猫烧香(浙大) 二、 课程设计内容： 1、设计要求： 模拟一个实验室的机器网络被病毒感染的过程，每台机器只和它相邻的机器直接相连。开始时有T太机器被感染，每台遭遇的熊猫变种类型都不同，分别记为Type1,Type2,TypeT。每台机器都具有一定级别的防御能力，记为L。 2、病毒的传播规则： 病毒只能从一台被感染的机器传到另一台没有被感染的机器。 如果一台机器已经被某个变种的病毒感染过，就不能再被其他变种感染。 病毒的传播能力每天都在增强。以D代表病毒的攻击等级，初始值为1，
2、每天增加1，可以感染所有可以到达的防御级别小于病毒自身攻击级别的机器。当L大于D的时候可以组织病毒从自己处继续传播。 同一天内，由1号变种病毒先开始传播，感染所有它可能感染的机器，然后Type2、Type3依次经行传播。 3、程序的要求： 输入要求： 输入由若干组测试数据组成。 每组数据的第一行包含2个整数M和N，接下来是一个M*N的矩阵表示网络的初始感染状态，其中的正、负整数的意义如题目描述中所定义。 下面一行给出一个正整数Q，是将要查询的变种的个数。接下去的Q行里，每行给出一个变种的类型。 当M或N为0时，表示全部测试结束，不要对该数据做任何处理。 输出要求： 对每一组进行测试，在一行里输
3、出被某个特定变种所感染的机器的数量。 输入输出例子： 输入： 3 4 1 -3 -2 -3 -2 -1 -2 2 -3 -2 -1 -1 2 1 2 0 0 输出： 9 3 2 三、 算法设计： 确定所需要的模块及模块之间的关系： 定义结构体： struct VertexType 节点 struct MGraph 邻接矩阵 邻接矩阵存储网络状态 MGraphCreat MGraphInit 查找病毒源 virfind( ) 传播病毒 virspread 传播完成统计每种病毒变种数量 virCount 每天状态 病毒总数 四、 程序正确性验证 ： 3 4 5 由以上测试结果分析可知：程序正确的完
4、成了题目要求的基本操作，并且添加了每天病毒传播的状态显示，而且背景和字体分别设置了颜色变化，使单调的黑屏界面变成彩色界面，交互性好。 五、 课程设计过程中出现的主要问题、原因及解决方法： 1、开始定义结构体时，节点的几个域定义划分不明确，随着后续程序的需要逐渐明确清晰。 2、编写病毒传播程序代码时初定使用广度优先遍历算法，但具体实现起来参数传递不好处理，就改为直接查找到病毒源后向四个方向分别判断传播，实现起来更加简单便捷。 3、为了看清病毒传播的每天的变化，在传播函数里添加了输出每天状态的代码。 4、为了多次测试方便，在main函数里加上了循环语句，实现一次运行多次测试。 6 六、 课程设计的
5、主要收获： 通过这次课程设计我也着实又感受了一次编程的乐趣，从中也学到了不少知识。虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课程设计。 我感受最深的一点是：以前用C+编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细
6、斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。 另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。 我以前对算法一直有些害怕，总是看不明白究竟一些算法是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的函数实现了新的功能，真是受益良多啊！ 在这次实验中，我对
7、参数的调用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。 总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的 七、 对今后课程设计的建议： 课程设计能使学生充分体验到数据结构在编程方面的重要性，锻炼自己动手能力，个人建议今后课程设计题目设计涉及方面更加广泛，实验时也允许多人组队，培养学生的团队精神，总之通过课程设计会使大家学习到很多新东西，对编程有更深的体会。感谢老师的辛苦工作，身体健康，工作顺利。 7 源代码： #include using namespace std; #define MAXNODE 500 typ
8、edef struct VertexType /结点信息 int day; /第几天被感染的 int dl; /防御级别 int r,c; /行列号 int vt; /病毒类型 VertexType; typedef struct MGraph /邻接矩阵 VertexType mMAXNODEMAXNODE; /结点数 int row,cloum,vtnum; /行列数、感染的数目 MGraph; MGraph mg; /定义图 typedef struct Queue /队列 8 VertexType dataMAXNODE; int front,rear; Queue; void MGr
9、aphInit /初始化 for (int i=0;img.row;i+) for (int j=0;jmg.cloum;j+) mg.mij.vt=0;/全部初始化为0 mg.mij.dl=0; mg.mij.day=0; mg.mij.r=i; mg.mij.c=j; mg.vtnum=0; void MGraphCreat 9 MGraphInit; cout * 请逐行输入网络的初识状态：endl; for (int i=0;img.row;i+) /for cout ; for (int j=0; ja; if (a0) else /if mg.mij.dl=0-a;/输入负数表示防
10、御等级 mg.mij.vt=a; /输入正数表示病毒等级 /MGraphCreat void virSpread(VertexType v,int nowday) Queue Q; Q.front=Q.rear=0; /定义变量并初始化队列 10 Q.rear=(Q.rear+1)%MAXNODE; Q.dataQ.rear=v; while (Q.front=0&mg.mv.r-1v.c.vt=0&mg.mv.r-1v.c.dl=0&mg.mv.r+1v.c.vt=0&mg.mv.r+1v.c.dl=0&mg.mv.rv.c-1.vt=0&mg.mv.rv.c-1.dl=0&mg.mv.rv
11、.c+1.vt=0&mg.mv.rv.c+1.dl=nowday)/右 mg.mv.rv.c+1.vt=v.vt; Q.rear=(Q.rear+1)%MAXNODE; Q.dataQ.rear=mg.mv.rv.c+1; void virFind /寻找病毒源 int virtype=1; /初始病毒变种为1 int i,j; int nowday=1; /初识天数为第一天 while(mg.vtnum(mg.row*mg .cloum) mg.vtnum=0; /初识病毒总数为0 while (virtype=mg.row ) 12 for (i=0;img.row;i+) for (i=
12、0;img.row;i+) /统计到第nowday天的病毒总数 for (j=0;j0)/被感染 13 /while for (j=0;jmg.cloum;j+) if (mg.mij.vt=virtype)/找到病毒源 /if virSpread(mg.mij,nowday);/调用传播函数 /for /for virtype+; /寻找下一种病毒的传播源 /if mg.vtnum+;/病毒总数加1 /for /for if (mg.vtnum=0) cout 网络安全，没有病毒！endl;exit(0); else cout * 第nowday天病毒传播状态为：endl; for (i=0
13、;img.row;i+) /统计到第nowday天的病毒总数 cout ; for (j=0;jmg.cloum;j+) if (mg.mij.vt!=0)/被感染 else cout(0-mg.mij.dl) ;/没感染 14 coutmg.mij.vt ;/病毒 /for coutendl; /for coutendl; /virFind int virCount /传播完后各种病毒统计 system(color e0); /控制台变色黄底黑字 int i,j,k, ctMAXNODE; /ct存放各种病毒变种的数量 for (int m=1;mMAXNODE-1;m+) 15 ctm=0
14、; /while nowday+; /循环下一天 virtype=1; /下一天任然从第一种变种开始传播 for (i=0;img.row;i+) /for cout * 感染完后病毒的变种的数目：endl; for (k=1;kMAXNODE-1;k+) coutendl; if (ctk!=0) cout * 变种类型为k的变种数目是：ctkendl; for (j=0;jmg.cloum;j+) /for ctmg.mij.vt+; return 0; /virCount int main system(color 5f); 16 cout 熊猫烧香程序欢迎您endl; int count=1; /测试次数 while (true) cout *endl; cout 第count次测试 endlendl; /cout *endl; count+; cout * 输入行列数目：endl; coutmg.rowmg.cloum; / 输入行列数 if (mg.row0&mg.cloum0) else exit(0); MGraphCreat; /创建 virFind; /遍历传播 virCount; /变种统计 /while return 0; /main 17
