数据结构熊猫烧香实验报告（含源码）

1、实验任务与目的（简单介绍实验内容，说明实验任务和目的）

“熊猫烧香”是在网络中传播的一种著名病毒。现在某实验室的网络不幸感染了这种病毒。从教材P126的图6.5可以看到，实验室的机器排列为一个M行N列的矩阵，每台机器只和它相邻的及其直接相连。开始时有T台机器被感染，每台遭遇的熊猫变种类型都不同，分别记为Type1，Type2，?..，Typer。每台机器都具有一定级别的防御能力，将防御级别记为L(0

（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的循环，直到循环所有的结点。

当分组操作完成以后，则从病毒开始对网络内计算机进行感染，首先将病毒设为根结点，即有多少种类型的病毒存在，就有多少个根结点，以根结点作为开始，建立单链表，依次存储被感染的结点。首先对根结点病毒的上下左右依次寻找，看是否又可以被感染的计算机，如果有，则这个结点所在区

域的所有计算机全部被感染，并将此区域所有结点的父母结点指针指向根结点，单链表顺序为按集合分配时的顺序，即虚拟根结点首先指向根结点。

然后按单链表的顺序进行感染，一直到单链表尾端。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 void Union(int x,int y) {

fx = getfather(x); fy = getfather(y); if(fy!=fx)

father[fx]=fy; }

二、实验结果与分析

1、程序结构（程序结构图，主要函数的功能描述，算法实现的细节等）

实现细节：

为了保证每天的分组更加高效，我们在结点类中加入了标识位，如果该结点已经在访问虚拟根结点时被分组，则不对该结点进行扫描；

同时我们还添加了标记结点坐标的位置的整形标量x，y。在分组函数和感染函数中，要传递的值都是坐标，然而从一个结点的信息中无法得知它所在位置，通过添加坐标，就使这个问题得到解决；

由于每天病毒所能感染的计算机范围不一样，所有要进行天数的循环递增，但递增到什么时候呢？我们发现，当计算机网络中防御等级最高的结点，它的防御等级就代表了最长的感染时间，即一定是天数等于防御等级的这一天所有的计算机都被感染。所以我们只需要保存最高的防御等级，在循环时加以限制，就可以解决问题；

病毒发威感染计算机网络时，存在一个感染次序的问题，我们采用了单链表存储病毒序列，每一天从单链表的首部开始感染周围结点所以只需要一边感染，并将感染的计算机位置放在单链表的尾部，即可完成当天的全部感染任务；

感染时，对病毒上下左右进行几次查找满足可被感染的条件的结点，如果找到，则找到该结点所在区域的虚拟根节点，并感染整个区域，将整个区域所有结点的父母指针指向病毒的根结点。

开始 输入数据 第day天循环直到感染全部 感染其所在区域，取消该区域虚拟根节点 Net[i][j]是否满足要求(非病毒，等级不大于天数，未被访问) 统计 设为虚拟根节点 输出结果 Net[i][j]是否满足要求(非病毒、防御等级大于天数) 对上下左右递归查找在同一区域的结点 从根结点开始感染，以单链表为顺序，对上下左右查找

分组函数（以一个方向为例）

感染函数（以一个方向为例）

并查集

//================================并查集=======================================

void XMSX::union_find() { int i,j; for(day=-1;day>=high_level;day--) //第day天，使用负数，便于与防御等级比较 { cout<<\第\<<-day<<\天\<

\;

net[i][j].visit=0; } }

//每天开始标识位置零

for(i=1;i=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<type_level<<\<parent->x<<\<parent->y<<\

p=p->child;

} //每天的分组完成后输出当天分组情况 cout<

cout<parent; //保存病毒根结点 while(index!=NULL) { infect(index->x,index->y,k); //从根结点按单链表顺序依次感染，直到空 cout<<\<x<<\<y<<\被\<child; } cout<

源码：

本文来源：https://www.bwwdw.com/article/b20t.html