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

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