數(shù)據(jù)結(jié)構(gòu)熊貓燒香實(shí)驗(yàn)報(bào)告(含源碼)

PAGE實(shí)驗(yàn)任務(wù)與目的（簡(jiǎn)單介紹實(shí)驗(yàn)內(nèi)容，說明實(shí)驗(yàn)任務(wù)和目的）“熊貓燒香”是在網(wǎng)絡(luò)中傳播的一種著名病毒?，F(xiàn)在某實(shí)驗(yàn)室的網(wǎng)絡(luò)不幸感染了這種病毒。從教材P126的圖6.5可以看到，實(shí)驗(yàn)室的機(jī)器排列為一個(gè)M行N列的矩陣，每臺(tái)機(jī)器只和它相鄰的及其直接相連。開始時(shí)有T臺(tái)機(jī)器被感染，每臺(tái)遭遇的熊貓變種類型都不同，分別記為Type1，Type2，…..，Typer。每臺(tái)機(jī)器都具有一定級(jí)別的防御能力，將防御級(jí)別記為L(zhǎng)(0<L<1000)。“熊貓燒香”按照下列規(guī)則迅速在網(wǎng)絡(luò)中傳播：（1）病毒只能從一臺(tái)被感染的及其傳到另一臺(tái)沒有被感染的機(jī)器；（2）如果一臺(tái)機(jī)器已經(jīng)被某個(gè)變種的病毒感染過，就不能再被其他變種感染；（3）病毒的傳播能力每天都在增強(qiáng)。第1天，病毒只能感染它可以到達(dá)的、防御級(jí)別為1的機(jī)器，而防御級(jí)別大于1的機(jī)器可以阻止它從自己處繼續(xù)傳播。第D天，病毒可以感染它可以達(dá)到的、防御級(jí)別不超過D的機(jī)器，而只有防御級(jí)別大于D的機(jī)器可以阻止它從自己處繼續(xù)傳播。（4）同一天之內(nèi)，Type1變種的病毒先開始傳播，感染所有它可能感染的及其，然后是Type2變種、Type3變種…….依次進(jìn)行傳播。實(shí)驗(yàn)要求是：當(dāng)整個(gè)網(wǎng)絡(luò)被感染后，計(jì)算有多少臺(tái)機(jī)器被某個(gè)特定變種所感染?！据斎胍蟆砍绦虻妮斎霐?shù)據(jù)由input.txt文件讀入，文件包含若干組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第1行包含2個(gè)整數(shù)M和N(1≤M，N≤500),接下來是一個(gè)M*N的矩陣表示網(wǎng)絡(luò)的初試感染狀態(tài)，其中用負(fù)整數(shù)-L表示未被感染、防御級(jí)別為Ｌ的機(jī)器，正整數(shù)Typei表示該機(jī)器被Typei類型的病毒變種感染。下一行給出一個(gè)正整數(shù)Q，是將要查詢的變種的個(gè)數(shù)。接下去的Q行里，每行給出一個(gè)變種類型。當(dāng)M或N為０時(shí)，表示全部測(cè)試結(jié)束，不要對(duì)該數(shù)據(jù)做任何處理。【輸出要求】對(duì)每一組測(cè)試，在一行里輸出被某個(gè)特定變種所感染的機(jī)器數(shù)量，并測(cè)試結(jié)果寫入output.txt文件。本實(shí)驗(yàn)訓(xùn)練的內(nèi)容包括六個(gè)方面：（1）面向?qū)ο蟪绦蛟O(shè)計(jì)方法，類模板的應(yīng)用；（2）采用合適的求解問題算法，如廣度優(yōu)先搜索、Dijkstra算法、并查集等；（3）矩陣存儲(chǔ)；（4）文件的讀寫操作；（5）程序測(cè)試計(jì)劃、用例的設(shè)計(jì)和測(cè)試方法。——————————————————————————————————————2、實(shí)驗(yàn)思路（詳細(xì)描述解決問題的整體思路、涉及的算法思想及數(shù)據(jù)結(jié)構(gòu)等）我們采用了并查集的方法，首先，我們考慮了這樣一個(gè)問題：在第n天的時(shí)候，計(jì)算機(jī)病毒只可以感染防御等級(jí)小于等于n的計(jì)算機(jī)，所以，在對(duì)計(jì)算機(jī)進(jìn)行感染或者分類時(shí)，只需要考慮防御等級(jí)小于等于n的計(jì)算機(jī)，其他的計(jì)算機(jī)忽略不考慮。 每一天開始，我們需要對(duì)計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行一次分組操作，將低于某一等級(jí)的區(qū)域歸為一個(gè)集合，并為集合設(shè)立虛擬根節(jié)點(diǎn)，集合中所有的結(jié)點(diǎn)的父母親指針都指向虛擬根結(jié)點(diǎn)，在劃分集合時(shí)，如之前所說的，不考慮小于等于天數(shù)的防御等級(jí)的計(jì)算機(jī)。 分組操作首先由一個(gè)循環(huán)開始，從二維矩陣的第一個(gè)數(shù)開始，m*n依次查找，如果滿足要求（非病毒，防御等級(jí)<=天數(shù)，未被訪問過），則將該結(jié)點(diǎn)設(shè)為虛擬結(jié)點(diǎn)，然后對(duì)其上下左右進(jìn)行查找，同樣尋找滿足要求的結(jié)點(diǎn)，如果找到，則對(duì)其進(jìn)行遞歸查找，一直找到最后一個(gè)結(jié)點(diǎn)為止，它們的父母親指針都指向虛擬根結(jié)點(diǎn)，然后繼續(xù)m*n的循環(huán)，直到循環(huán)所有的結(jié)點(diǎn)。 當(dāng)分組操作完成以后，則從病毒開始對(duì)網(wǎng)絡(luò)內(nèi)計(jì)算機(jī)進(jìn)行感染，首先將病毒設(shè)為根結(jié)點(diǎn)，即有多少種類型的病毒存在，就有多少個(gè)根結(jié)點(diǎn)，以根結(jié)點(diǎn)作為開始，建立單鏈表，依次存儲(chǔ)被感染的結(jié)點(diǎn)。首先對(duì)根結(jié)點(diǎn)病毒的上下左右依次尋找，看是否又可以被感染的計(jì)算機(jī)，如果有，則這個(gè)結(jié)點(diǎn)所在區(qū)域的所有計(jì)算機(jī)全部被感染，并將此區(qū)域所有結(jié)點(diǎn)的父母結(jié)點(diǎn)指針指向根結(jié)點(diǎn)，單鏈表順序?yàn)榘醇戏峙鋾r(shí)的順序，即虛擬根結(jié)點(diǎn)首先指向根結(jié)點(diǎn)。 然后按單鏈表的順序進(jìn)行感染，一直到單鏈表尾端。并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（DisjointSets）的合并及查詢問題。常常在使用中以森林來表示。voidUnion(intx,inty){fx=getfather(x);fy=getfather(y);if(fy!=fx)father[fx]=fy;}二、實(shí)驗(yàn)結(jié)果與分析1、程序結(jié)構(gòu)（程序結(jié)構(gòu)圖，主要函數(shù)的功能描述，算法實(shí)現(xiàn)的細(xì)節(jié)等）實(shí)現(xiàn)細(xì)節(jié)：為了保證每天的分組更加高效，我們?cè)诮Y(jié)點(diǎn)類中加入了標(biāo)識(shí)位，如果該結(jié)點(diǎn)已經(jīng)在訪問虛擬根結(jié)點(diǎn)時(shí)被分組，則不對(duì)該結(jié)點(diǎn)進(jìn)行掃描；同時(shí)我們還添加了標(biāo)記結(jié)點(diǎn)坐標(biāo)的位置的整形標(biāo)量x，y。在分組函數(shù)和感染函數(shù)中，要傳遞的值都是坐標(biāo)，然而從一個(gè)結(jié)點(diǎn)的信息中無法得知它所在位置，通過添加坐標(biāo)，就使這個(gè)問題得到解決；由于每天病毒所能感染的計(jì)算機(jī)范圍不一樣，所有要進(jìn)行天數(shù)的循環(huán)遞增，但遞增到什么時(shí)候呢？我們發(fā)現(xiàn)，當(dāng)計(jì)算機(jī)網(wǎng)絡(luò)中防御等級(jí)最高的結(jié)點(diǎn)，它的防御等級(jí)就代表了最長(zhǎng)的感染時(shí)間，即一定是天數(shù)等于防御等級(jí)的這一天所有的計(jì)算機(jī)都被感染。所以我們只需要保存最高的防御等級(jí)，在循環(huán)時(shí)加以限制，就可以解決問題；病毒發(fā)威感染計(jì)算機(jī)網(wǎng)絡(luò)時(shí)，存在一個(gè)感染次序的問題，我們采用了單鏈表存儲(chǔ)病毒序列，每一天從單鏈表的首部開始感染周圍結(jié)點(diǎn)所以只需要一邊感染，并將感染的計(jì)算機(jī)位置放在單鏈表的尾部，即可完成當(dāng)天的全部感染任務(wù)；感染時(shí)，對(duì)病毒上下左右進(jìn)行幾次查找滿足可被感染的條件的結(jié)點(diǎn)，如果找到，則找到該結(jié)點(diǎn)所在區(qū)域的虛擬根節(jié)點(diǎn)，并感染整個(gè)區(qū)域，將整個(gè)區(qū)域所有結(jié)點(diǎn)的父母指針指向病毒的根結(jié)點(diǎn)。NNet[i][j]是否滿足要求(非病毒，等級(jí)不大于天數(shù)，未被訪問)開始輸入數(shù)據(jù)第day天循環(huán)直到感染全部對(duì)上下左右遞歸查找在同一區(qū)域的結(jié)點(diǎn)設(shè)為虛擬根節(jié)點(diǎn)從根結(jié)點(diǎn)開始感染，以單鏈表為順序，對(duì)上下左右查找Net[i][j]是否滿足要求(非病毒、防御等級(jí)大于天數(shù))感染其所在區(qū)域，取消該區(qū)域虛擬根節(jié)點(diǎn)輸出結(jié)果統(tǒng)計(jì)分組函數(shù)（以一個(gè)方向?yàn)槔└腥竞瘮?shù)（以一個(gè)方向?yàn)槔┎⒉榧?/================================并查集=======================================voidXMSX::union_find(){ inti,j; for(day=-1;day>=high_level;day--) //第day天，使用負(fù)數(shù)，便于與防御等級(jí)比較 { cout<<"第"<<-day<<"天"<<endl; for(i=0;i<m+2;i++) { for(j=0;j<n+2;j++) { net[i][j].visit=0; } } //每天開始標(biāo)識(shí)位置零 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) //當(dāng)滿足該結(jié)點(diǎn)（非病毒、防御等級(jí)不大于天數(shù)、未被訪問） { root_x=i; //記錄虛擬根節(jié)點(diǎn)坐標(biāo) root_y=j; p=&net[i][j]; //保存根結(jié)點(diǎn) group(i,j); //執(zhí)行分組 p=&net[i][j]; while(p!=NULL) { cout<<p->type_level<<"("<<p->parent->x<<","<<p->parent->y<<")"; p=p->child; } //每天的分組完成后輸出當(dāng)天分組情況 cout<<endl; } } } cout<<endl; computer*index; for(intk=0;k<count;k++) //按病毒的型號(hào)順序進(jìn)行感染，每個(gè)病毒以其單鏈表次序依次感染 { cout<<virus_type[k]<<"號(hào)病毒開始感染"<<endl; index=list_end[k]->parent; //保存病毒根結(jié)點(diǎn) while(index!=NULL) { infect(index->x,index->y,k); //從根結(jié)點(diǎn)按單鏈表順序依次感染，直到空 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;//記錄計(jì)算機(jī)網(wǎng)絡(luò)大小 introot_x,root_y;//臨時(shí)變量，用于記錄虛擬根節(jié)點(diǎn)的位置 intday;//當(dāng)前天數(shù) intcount;//病毒數(shù) intnum;//待查詢的病毒數(shù) inthigh_level;//最高的防御等級(jí) intvirus_type[100];//病毒種類 intvirus_search[100];//待查找的病毒種類 computernet[100][100];//計(jì)算機(jī)網(wǎng)絡(luò) computer*list_end[100];//單鏈表表尾 computer*p;//臨時(shí)變量public: voidenter();//輸入函數(shù) voidprint();//將計(jì)算機(jī)網(wǎng)絡(luò)輸出在屏幕中 voidinfect(inta,intb,intk); //感染函數(shù)，對(duì)位置在（a，b）的結(jié)點(diǎn)進(jìn)行遞歸感染，感染類型為virus_type[k] voidgroup(inta,intb); //集合劃分函數(shù)，對(duì)位置在（a，b）的結(jié)點(diǎn)遞歸查找滿足條件的結(jié)點(diǎn) voidunion_find(); //并查集，分組并感染 voidcount_type(); //統(tǒng)計(jì)不同種病毒的數(shù)目并輸出};//==============================輸入函數(shù)=======================================voidXMSX::enter(){ inti,j,k; //定義三個(gè)整型變量用于循環(huán) count=0;//輸入前，病毒數(shù)為0 high_level=0;//輸入前，最高防御等級(jí)為0 ifstreaminfile; infile.open("input.txt");//文件夾輸入 infile>>m>>n;//輸入行數(shù)和列數(shù) for(i=0;i<m+2;i++) //m+2即增加了墻 { for(j=0;j<n+2;j++) //n+2即增加了墻 { net[i][j].type_level=0; //先令所有的計(jì)算機(jī)防御等級(jí)為0 net[i][j].child=NULL; //所有的計(jì)算機(jī)孩子指針指向空 net[i][j].parent=&net[i][j]; //所有的計(jì)算機(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; //文件夾輸入計(jì)算機(jī)的防御等級(jí)或病毒型號(hào) if(net[i][j].type_level>0) //當(dāng)防御等級(jí)大于0時(shí)，即為病毒型號(hào) { virus_type[count]=net[i][j].type_level; //記錄病毒型號(hào)序列 list_end[count]=&net[i][j]; //此時(shí)將第count號(hào)病毒單鏈表的尾指針指向該病毒 //即將病毒作為自己?jiǎn)捂湵淼念^結(jié)點(diǎn) count++; //count加1，當(dāng)掃描完所有病毒以后，count即為病毒總數(shù) } elseif(net[i][j].type_level<high_level) //如果該計(jì)算機(jī)的防御等級(jí)大于最高防御等級(jí) { high_level=net[i][j].type_level; //則將其設(shè)為最高防御等級(jí) } } } infile>>num; //輸入需要查找的病毒數(shù)目 for(k=0;k<num;k++) infile>>virus_search[k];//輸入需要查找的病毒型號(hào) }//==============================輸出矩陣=======================================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;}//==============================分組函數(shù)=======================================voidXMSX::group(inta,intb)//給分組函數(shù)一個(gè)坐標(biāo)(a,b)，即可為這個(gè)坐標(biāo)所在區(qū)域分組{ net[a][b].visit=1; //表示這個(gè)坐標(biāo)已經(jīng)被訪問過 if(net[a-1][b].type_level<0&&net[a-1][b].type_level>=day&&net[a-1][b].visit==0) //當(dāng)這個(gè)坐標(biāo)的上方結(jié)點(diǎn)滿足（非病毒、防御等級(jí)不大于天數(shù)、未被訪問）時(shí) { net[a-1][b].parent=&net[root_x][root_y]; //將上方結(jié)點(diǎn)的父母指針指向虛擬根節(jié)點(diǎn) p->child=&net[a-1][b]; //區(qū)域單鏈表表尾的孩子指針指向該結(jié)點(diǎn) p=p->child; //將表尾向后推移 group(a-1,b); //遞歸對(duì)上方結(jié)點(diǎn)求分組 } if(net[a][b+1].type_level<0&&net[a][b+1].type_level>=day&&net[a][b+1].visit==0) //當(dāng)這個(gè)坐標(biāo)的右方結(jié)點(diǎn)滿足（非病毒、防御等級(jí)不大于天數(shù)、未被訪問）時(shí) { 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) //當(dāng)這個(gè)坐標(biāo)的下方結(jié)點(diǎn)滿足（非病毒、防御等級(jí)不大于天數(shù)、未被訪問）時(shí) { 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) //當(dāng)這個(gè)坐標(biāo)的左方結(jié)點(diǎn)滿足（非病毒、防御等級(jí)不大于天數(shù)、未被訪問）時(shí) { net[a][b-1].parent=&net[root_x][root_y]; p->child=&net[a][b-1]; p=p->child; group(a,b-1); }}//==============================感染函數(shù)=======================================voidXMSX::infect(inta,intb,intk)//給出一個(gè)坐標(biāo)以及病毒型號(hào)，即以該病毒感染此結(jié)點(diǎn)所在區(qū)域{ if(net[a-1][b].type_level<0&&net[a-1][b].type_level>=day) //當(dāng)非病毒，防御等級(jí)不大于天數(shù)時(shí) { p=net[a-1][b].parent; //保存該結(jié)點(diǎn)所在區(qū)域的虛擬根節(jié)點(diǎn) list_end[k]->child=p; //將k號(hào)病毒鏈表尾部孩子指針指向虛擬根節(jié)點(diǎn) p->type_level=list_end[k]->type_level; //該區(qū)域所有結(jié)點(diǎn)的防御等級(jí)改為病毒型號(hào) p->parent=list_end[k]->parent; //取消虛擬根節(jié)點(diǎn)， while(p->child!=NULL) //以原始病毒為根結(jié)點(diǎn) { 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天，使用負(fù)數(shù)，便于與防御等級(jí)比較 { cout<<"第"<<-day<<"天"<<endl; for(i=0;i<m+2;i++) { for(j=0;j<n+2;j++) { net[i][j].visit=0; } } //每天開始標(biāo)識(shí)位置零 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) //當(dāng)滿足該結(jié)點(diǎn)（非病毒、防御等級(jí)不大于天數(shù)、未被訪問） { root_x=i; //記錄虛擬根節(jié)點(diǎn)坐標(biāo) root_y=j; p=&net[i][j]; //保存根結(jié)點(diǎn) group(i,j); //執(zhí)行分組 p=&net[i][j]; while(p!=NULL) { cout<<p->type_level<<"("<<p->parent->x<<","<<p->parent->y<<")"; p=p->child; } //每天的分組完成后輸出當(dāng)天分組情況 cout<<endl; } } } cout<<endl; computer*index; for(intk=0;k<count;k++) //按病毒的型號(hào)順序進(jìn)行感染，每個(gè)病毒以其單鏈表次序依次感染 { cout<<virus_type[k]<<"號(hào)病毒開始感染"<<endl; index=list_end[k]->parent; //保存病毒根結(jié)點(diǎn) while(index!=NULL) { infect(index->x,index->y,k); //從根結(jié)點(diǎn)按單鏈表順序依次感染，直到空 cout<<"("<<index->x<<","<<index->y<<")被"<<virus_type[k]<<"感染"<<endl; index=index->child; } cout<<endl; } } }//==============================統(tǒng)計(jì)函數(shù)=======================================voidXMSX::count_type(){ intvirus_count[100]; //用于統(tǒng)計(jì)不同類型的病毒數(shù)目 for(inti=0;i<count;i++)virus_count[i]=0; //先置零 cout<<"感染后計(jì)算機(jī)網(wǎng)絡(luò)狀態(tài)："<<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號(hào)病毒，則k號(hào)病毒的計(jì)數(shù)加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]++; //若是所查詢的病毒，則該病毒計(jì)數(shù)加1 } } } cout<<"最后病毒數(shù)目統(tǒng)計(jì)結(jié)果如下："<<endl; for(i=0;i<num;i++)cout<<virus_search[i]<<"號(hào)病毒"<<virus_count[i]<<"個(gè)"<<endl; cout<<endl; cout<<"病毒感染鏈表如下："<<endl; for(i=0;i<count;i++) { cout<<virus_type[i]<<"號(hào)病毒"<<endl; computer*index; index=list_end[i]->parent; while(index!=NULL) { cout<<"("<<index->x<<","<<index->y<<")"<<endl; index=index->child; } cout<<endl; }}//================================主函數(shù)======================================= intmain(){ XMSXobj; obj.enter(); obj.print(); obj.union_find(); obj.count_type(); system("PAUSE"); return0;} ——————————————————————————————————————測(cè)試設(shè)計(jì)與數(shù)據(jù)（設(shè)計(jì)充足合理的測(cè)試用例，說明測(cè)試策略）分別進(jìn)行一下測(cè)試，，當(dāng)病毒在中間部位時(shí)，當(dāng)病毒數(shù)量較多時(shí)，當(dāng)計(jì)算機(jī)網(wǎng)絡(luò)較大時(shí)（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