数据结构熊猫烧香实验报告(含源码)

PAGE实验任务与目的（简单介绍实验内容，说明实验任务和目的）“熊猫烧香”是在网络中传播的一种著名病毒。现在某实验室的网络不幸感染了这种病毒。从教材P126的图6.5可以看到，实验室的机器排列为一个M行N列的矩阵，每台机器只和它相邻的及其直接相连。开始时有T台机器被感染，每台遭遇的熊猫变种类型都不同，分别记为Type1，Type2，…..，Typer。每台机器都具有一定级别的防御能力，将防御级别记为L(0<L<1000)。“熊猫烧香”按照下列规则迅速在网络中传播：（1）病毒只能从一台被感染的及其传到另一台没有被感染的机器；（2）如果一台机器已经被某个变种的病毒感染过，就不能再被其他变种感染；（3）病毒的传播能力每天都在增强。第1天，病毒只能感染它可以到达的、防御级别为1的机器，而防御级别大于1的机器可以阻止它从自己处继续传播。第D天，病毒可以感染它可以达到的、防御级别不超过D的机器，而只有防御级别大于D的机器可以阻止它从自己处继续传播。（4）同一天之内，Type1变种的病毒先开始传播，感染所有它可能感染的及其，然后是Type2变种、Type3变种…….依次进行传播。实验要求是：当整个网络被感染后，计算有多少台机器被某个特定变种所感染。【输入要求】程序的输入数据由input.txt文件读入，文件包含若干组测试数据。每组数据的第1行包含2个整数M和N(1≤M，N≤500),接下来是一个M*N的矩阵表示网络的初试感染状态，其中用负整数-L表示未被感染、防御级别为Ｌ的机器，正整数Typei表示该机器被Typei类型的病毒变种感染。下一行给出一个正整数Q，是将要查询的变种的个数。接下去的Q行里，每行给出一个变种类型。当M或N为０时，表示全部测试结束，不要对该数据做任何处理。【输出要求】对每一组测试，在一行里输出被某个特定变种所感染的机器数量，并测试结果写入output.txt文件。本实验训练的内容包括六个方面：（1）面向对象程序设计方法，类模板的应用；（2）采用合适的求解问题算法，如广度优先搜索、Dijkstra算法、并查集等；（3）矩阵存储；（4）文件的读写操作；（5）程序测试计划、用例的设计和测试方法。——————————————————————————————————————2、实验思路（详细描述解决问题的整体思路、涉及的算法思想及数据结构等）我们采用了并查集的方法，首先，我们考虑了这样一个问题：在第n天的时候，计算机病毒只可以感染防御等级小于等于n的计算机，所以，在对计算机进行感染或者分类时，只需要考虑防御等级小于等于n的计算机，其他的计算机忽略不考虑。 每一天开始，我们需要对计算机网络进行一次分组操作，将低于某一等级的区域归为一个集合，并为集合设立虚拟根节点，集合中所有的结点的父母亲指针都指向虚拟根结点，在划分集合时，如之前所说的，不考虑小于等于天数的防御等级的计算机。 分组操作首先由一个循环开始，从二维矩阵的第一个数开始，m*n依次查找，如果满足要求（非病毒，防御等级<=天数，未被访问过），则将该结点设为虚拟结点，然后对其上下左右进行查找，同样寻找满足要求的结点，如果找到，则对其进行递归查找，一直找到最后一个结点为止，它们的父母亲指针都指向虚拟根结点，然后继续m*n的循环，直到循环所有的结点。 当分组操作完成以后，则从病毒开始对网络内计算机进行感染，首先将病毒设为根结点，即有多少种类型的病毒存在，就有多少个根结点，以根结点作为开始，建立单链表，依次存储被感染的结点。首先对根结点病毒的上下左右依次寻找，看是否又可以被感染的计算机，如果有，则这个结点所在区域的所有计算机全部被感染，并将此区域所有结点的父母结点指针指向根结点，单链表顺序为按集合分配时的顺序，即虚拟根结点首先指向根结点。 然后按单链表的顺序进行感染，一直到单链表尾端。并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。常常在使用中以森林来表示。voidUnion(intx,inty){fx=getfather(x);fy=getfather(y);if(fy!=fx)father[fx]=fy;}二、实验结果与分析1、程序结构（程序结构图，主要函数的功能描述，算法实现的细节等）实现细节：为了保证每天的分组更加高效，我们在结点类中加入了标识位，如果该结点已经在访问虚拟根结点时被分组，则不对该结点进行扫描；同时我们还添加了标记结点坐标的位置的整形标量x，y。在分组函数和感染函数中，要传递的值都是坐标，然而从一个结点的信息中无法得知它所在位置，通过添加坐标，就使这个问题得到解决；由于每天病毒所能感染的计算机范围不一样，所有要进行天数的循环递增，但递增到什么时候呢？我们发现，当计算机网络中防御等级最高的结点，它的防御等级就代表了最长的感染时间，即一定是天数等于防御等级的这一天所有的计算机都被感染。所以我们只需要保存最高的防御等级，在循环时加以限制，就可以解决问题；病毒发威感染计算机网络时，存在一个感染次序的问题，我们采用了单链表存储病毒序列，每一天从单链表的首部开始感染周围结点所以只需要一边感染，并将感染的计算机位置放在单链表的尾部，即可完成当天的全部感染任务；感染时，对病毒上下左右进行几次查找满足可被感染的条件的结点，如果找到，则找到该结点所在区域的虚拟根节点，并感染整个区域，将整个区域所有结点的父母指针指向病毒的根结点。NNet[i][j]是否满足要求(非病毒，等级不大于天数，未被访问)开始输入数据第day天循环直到感染全部对上下左右递归查找在同一区域的结点设为虚拟根节点从根结点开始感染，以单链表为顺序，对上下左右查找Net[i][j]是否满足要求(非病毒、防御等级大于天数)感染其所在区域，取消该区域虚拟根节点输出结果统计分组函数（以一个方向为例）感染函数（以一个方向为例）并查集//================================并查集=======================================voidXMSX::union_find(){ inti,j; for(day=-1;day>=high_level;day--) //第day天，使用负数，便于与防御等级比较 { cout<<"第"<<-day<<"天"<<endl; for(i=0;i<m+2;i++) { for(j=0;j<n+2;j++) { net[i][j].visit=0; } } //每天开始标识位置零 for(i=1;i<m+1;i++) { for(j=1;j<n+1;j++) { if(net[i][j].type_level<0&&net[i][j].type_level>=day&&net[i][j].visit==0) //当满足该结点（非病毒、防御等级不大于天数、未被访问） { root_x=i; //记录虚拟根节点坐标 root_y=j; p=&net[i][j]; //保存根结点 group(i,j); //执行分组 p=&net[i][j]; while(p!=NULL) { cout<<p->type_level<<"("<<p->parent->x<<","<<p->parent->y<<")"; p=p->child; } //每天的分组完成后输出当天分组情况 cout<<endl; } } } cout<<endl; computer*index; for(intk=0;k<count;k++) //按病毒的型号顺序进行感染，每个病毒以其单链表次序依次感染 { cout<<virus_type[k]<<"号病毒开始感染"<<endl; index=list_end[k]->parent; //保存病毒根结点 while(index!=NULL) { infect(index->x,index->y,k); //从根结点按单链表顺序依次感染，直到空 cout<<"("<<index->x<<","<<index->y<<")被"<<virus_type[k]<<"感染"<<endl; index=index->child; } cout<<endl; } } }源码：#include<iostream>#include<fstream>usingnamespacestd;structcomputer{ inttype_level; intvisit; intx,y; computer*child; computer*parent;};classXMSX{private: intm,n;//记录计算机网络大小 introot_x,root_y;//临时变量，用于记录虚拟根节点的位置 intday;//当前天数 intcount;//病毒数 intnum;//待查询的病毒数 inthigh_level;//最高的防御等级 intvirus_type[100];//病毒种类 intvirus_search[100];//待查找的病毒种类 computernet[100][100];//计算机网络 computer*list_end[100];//单链表表尾 computer*p;//临时变量public: voidenter();//输入函数 voidprint();//将计算机网络输出在屏幕中 voidinfect(inta,intb,intk); //感染函数，对位置在（a，b）的结点进行递归感染，感染类型为virus_type[k] voidgroup(inta,intb); //集合划分函数，对位置在（a，b）的结点递归查找满足条件的结点 voidunion_find(); //并查集，分组并感染 voidcount_type(); //统计不同种病毒的数目并输出};//==============================输入函数=======================================voidXMSX::enter(){ inti,j,k; //定义三个整型变量用于循环 count=0;//输入前，病毒数为0 high_level=0;//输入前，最高防御等级为0 ifstreaminfile; infile.open("input.txt");//文件夹输入 infile>>m>>n;//输入行数和列数 for(i=0;i<m+2;i++) //m+2即增加了墙 { for(j=0;j<n+2;j++) //n+2即增加了墙 { net[i][j].type_level=0; //先令所有的计算机防御等级为0 net[i][j].child=NULL; //所有的计算机孩子指针指向空 net[i][j].parent=&net[i][j]; //所有的计算机父母指针指向自己 net[i][j].x=i; //在x，y中记录自己在矩阵中的位置 net[i][j].y=j; } } for(i=1;i<m+1;i++) { for(j=1;j<n+1;j++) { infile>>net[i][j].type_level; //文件夹输入计算机的防御等级或病毒型号 if(net[i][j].type_level>0) //当防御等级大于0时，即为病毒型号 { virus_type[count]=net[i][j].type_level; //记录病毒型号序列 list_end[count]=&net[i][j]; //此时将第count号病毒单链表的尾指针指向该病毒 //即将病毒作为自己单链表的头结点 count++; //count加1，当扫描完所有病毒以后，count即为病毒总数 } elseif(net[i][j].type_level<high_level) //如果该计算机的防御等级大于最高防御等级 { high_level=net[i][j].type_level; //则将其设为最高防御等级 } } } infile>>num; //输入需要查找的病毒数目 for(k=0;k<num;k++) infile>>virus_search[k];//输入需要查找的病毒型号 }//==============================输出矩阵=======================================voidXMSX::print(){ for(inti=1;i<m+1;i++) { for(intj=1;j<n+1;j++) { cout<<net[i][j].type_level<<""; } cout<<endl; } cout<<endl;}//==============================分组函数=======================================voidXMSX::group(inta,intb)//给分组函数一个坐标(a,b)，即可为这个坐标所在区域分组{ net[a][b].visit=1; //表示这个坐标已经被访问过 if(net[a-1][b].type_level<0&&net[a-1][b].type_level>=day&&net[a-1][b].visit==0) //当这个坐标的上方结点满足（非病毒、防御等级不大于天数、未被访问）时 { net[a-1][b].parent=&net[root_x][root_y]; //将上方结点的父母指针指向虚拟根节点 p->child=&net[a-1][b]; //区域单链表表尾的孩子指针指向该结点 p=p->child; //将表尾向后推移 group(a-1,b); //递归对上方结点求分组 } if(net[a][b+1].type_level<0&&net[a][b+1].type_level>=day&&net[a][b+1].visit==0) //当这个坐标的右方结点满足（非病毒、防御等级不大于天数、未被访问）时 { net[a][b+1].parent=&net[root_x][root_y]; p->child=&net[a][b+1]; p=p->child; group(a,b+1); } if(net[a+1][b].type_level<0&&net[a+1][b].type_level>=day&&net[a+1][b].visit==0) //当这个坐标的下方结点满足（非病毒、防御等级不大于天数、未被访问）时 { net[a+1][b].parent=&net[root_x][root_y]; p->child=&net[a+1][b]; p=p->child; group(a+1,b); } if(net[a][b-1].type_level<0&&net[a][b-1].type_level>=day&&net[a][b-1].visit==0) //当这个坐标的左方结点满足（非病毒、防御等级不大于天数、未被访问）时 { net[a][b-1].parent=&net[root_x][root_y]; p->child=&net[a][b-1]; p=p->child; group(a,b-1); }}//==============================感染函数=======================================voidXMSX::infect(inta,intb,intk)//给出一个坐标以及病毒型号，即以该病毒感染此结点所在区域{ if(net[a-1][b].type_level<0&&net[a-1][b].type_level>=day) //当非病毒，防御等级不大于天数时 { p=net[a-1][b].parent; //保存该结点所在区域的虚拟根节点 list_end[k]->child=p; //将k号病毒链表尾部孩子指针指向虚拟根节点 p->type_level=list_end[k]->type_level; //该区域所有结点的防御等级改为病毒型号 p->parent=list_end[k]->parent; //取消虚拟根节点， while(p->child!=NULL) //以原始病毒为根结点 { p=p->child; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; } list_end[k]=p; //表尾推移到单链表最尾端 } if(net[a][b+1].type_level<0&&net[a][b+1].type_level>=day) { p=net[a][b+1].parent; list_end[k]->child=p; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; while(p->child!=NULL) { p=p->child; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; } list_end[k]=p; } if(net[a+1][b].type_level<0&&net[a+1][b].type_level>=day) { p=net[a+1][b].parent; list_end[k]->child=p; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; while(p->child!=NULL) { p=p->child; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; } list_end[k]=p; } if(net[a][b-1].type_level<0&&net[a][b-1].type_level>=day) { p=net[a][b-1].parent; list_end[k]->child=p; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; while(p->child!=NULL) { p=p->child; p->type_level=list_end[k]->type_level; p->parent=list_end[k]->parent; } list_end[k]=p; }}//================================并查集=======================================voidXMSX::union_find(){ inti,j; for(day=-1;day>=high_level;day--) //第day天，使用负数，便于与防御等级比较 { cout<<"第"<<-day<<"天"<<endl; for(i=0;i<m+2;i++) { for(j=0;j<n+2;j++) { net[i][j].visit=0; } } //每天开始标识位置零 for(i=1;i<m+1;i++) { for(j=1;j<n+1;j++) { if(net[i][j].type_level<0&&net[i][j].type_level>=day&&net[i][j].visit==0) //当满足该结点（非病毒、防御等级不大于天数、未被访问） { root_x=i; //记录虚拟根节点坐标 root_y=j; p=&net[i][j]; //保存根结点 group(i,j); //执行分组 p=&net[i][j]; while(p!=NULL) { cout<<p->type_level<<"("<<p->parent->x<<","<<p->parent->y<<")"; p=p->child; } //每天的分组完成后输出当天分组情况 cout<<endl; } } } cout<<endl; computer*index; for(intk=0;k<count;k++) //按病毒的型号顺序进行感染，每个病毒以其单链表次序依次感染 { cout<<virus_type[k]<<"号病毒开始感染"<<endl; index=list_end[k]->parent; //保存病毒根结点 while(index!=NULL) { infect(index->x,index->y,k); //从根结点按单链表顺序依次感染，直到空 cout<<"("<<index->x<<","<<index->y<<")被"<<virus_type[k]<<"感染"<<endl; index=index->child; } cout<<endl; } } }//==============================统计函数=======================================voidXMSX::count_type(){ intvirus_count[100]; //用于统计不同类型的病毒数目 for(inti=0;i<count;i++)virus_count[i]=0; //先置零 cout<<"感染后计算机网络状态："<<endl; for(i=1;i<m+1;i++) { for(intj=1;j<n+1;j++) { cout<<net[i][j].type_level<<""; for(intk=0;k<count;k++) { if(net[i][j].type_level==virus_type[k])virus_count[k]++; //若是k号病毒，则k号病毒的计数加1 } } cout<<endl; } cout<<endl; for(i=0;i<100;i++)virus_count[i]=0; for(i=1;i<m+1;i++) { for(intj=1;j<n+1;j++) { for(intk=0;k<num;k++) { if(net[i][j].type_level==virus_search[k])virus_count[k]++; //若是所查询的病毒，则该病毒计数加1 } } } cout<<"最后病毒数目统计结果如下："<<endl; for(i=0;i<num;i++)cout<<virus_search[i]<<"号病毒"<<virus_count[i]<<"个"<<endl; cout<<endl; cout<<"病毒感染链表如下："<<endl; for(i=0;i<count;i++) { cout<<virus_type[i]<<"号病毒"<<endl; computer*index; index=list_end[i]->parent; while(index!=NULL) { cout<<"("<<index->x<<","<<index->y<<")"<<endl; index=index->child; } cout<<endl; }}//================================主函数======================================= intmain(){ XMSXobj; obj.enter(); obj.print(); obj.union_find(); obj.count_type(); system("PAUSE"); return0;} ——————————————————————————————————————测试设计与数据（设计充足合理的测试用例，说明测试策略）分别进行一下测试，，当病毒在中间部位时，当病毒数量较多时，当计算机网络较大时（1）.44-1-2-3-4-4-3-2-1-11-1-3-3-42-2212（2）.551-223-1-4-3-2-1-44-3-1-3-3-3-45-2-5-5-5-2-1-3512345（3）.10101-2-2-1-1-2-1-3