算法實(shí)驗(yàn)報(bào)告-眾數(shù)問題

算法實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)?zāi)康慕o定含有n個(gè)元素的多重集合S，每個(gè)元素在S中出現(xiàn)的次數(shù)稱為該元素的重?cái)?shù)。多重?cái)?shù)集S中的重?cái)?shù)最大的元素稱為眾數(shù)。例如，S={1,2,2,2,3,5}。多重集S得眾數(shù)是2，其重?cái)?shù)為3。對于給定的由n個(gè)自然數(shù)組成多重?cái)?shù)集S，計(jì)算S的眾數(shù)及其重?cái)?shù)。二、實(shí)驗(yàn)環(huán)境 Windows7+VisualStudio2010三、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)思路利用快速排序?qū)?shù)據(jù)集S排序，再遍歷整個(gè)數(shù)組，利用Number類記錄每個(gè)數(shù)出現(xiàn)的頻率，從而找出集合的眾數(shù)和重?cái)?shù)。相關(guān)模塊#include<iostream>#include<fstream>usingnamespacestd;//存儲數(shù)y與出現(xiàn)頻率classNumber{public: Number(){count=0;} intvalue; intcount;};voidwrite(char*filename,intsize,Number*num);voidmode(int*a,intsize,Number*num);voidquickSort(int*,int,int);intPartition(int*,int,int);intmain(){ intsize=0; intfrequency=0; char*inFileName="H:\\C++\\Algorithms\\in2.txt"; char*outFileName="H:\\C++\\Algorithms\\out2.txt"; ifstreaminput(inFileName,ios::in); //從文件讀取數(shù)據(jù) input>>size; int*a=newint[size]; for(inti=0;i<size;++i) input>>a[i]; input.close(); //對數(shù)組用快排排序 quickSort(a,0,size-1); Number*num=newNumber[size]; mode(a,size,num); write(outFileName,size,num); system("pause"); return0;}//將眾數(shù)與重?cái)?shù)寫入文件，如果有多個(gè)，則將所有結(jié)果依次寫入文件voidwrite(char*filename,intsize,Number*num){ intmax=0; for(inti=1;i<size;++i) if(num[i].count>num[max].count) max=i-1; ofstreamoutput; output.open(filename,ios::out); output<<num[max].value<<"\n"<<num[max].count<<endl; for(inti=0;i<size;++i) if(num[max].count==num[i].count&&max!=i) output<<num[i].value<<"\n"<<num[i].count<<endl; output.close();}//劃分intPartition(int*arr,intp,intr){ inti=p,j=r+1; intx=arr[p]; //sort<xtoleft,>xtoright while(true) { while(arr[++i]<x&&i<r); while(arr[--j]>x); if(i>=j)break; swap(arr[i],arr[j]); } arr[p]=arr[j]; arr[j]=x; returnj;}//快排voidquickSort(int*arr,intp,intr){ if(p<r) { intq=Partition(arr,p,r); quickSort(arr,p,q-1);//sorttheleftpart quickSort(arr,q+1,r);//sorttherightpart }}//找出眾數(shù)與重?cái)?shù)voidmode(int*a,intsize,Number*num){ intcount=1;//某個(gè)數(shù)出現(xiàn)的次數(shù)//遍歷排好序的數(shù)組，計(jì)算出每個(gè)數(shù)出現(xiàn)的次數(shù) for(inti=0;i<size-1;++i) { if(a[i]==a[i+1]) count++; else { num[i].value=a[i]; num[i].count=count; count=1; } } num[size-1].value=a[siz