算法实验报告-众数问题

算法实验报告一、实验目的给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重数集S中的重数最大的元素称为众数。例如，S={1,2,2,2,3,5}。多重集S得众数是2，其重数为3。对于给定的由n个自然数组成多重数集S，计算S的众数及其重数。二、实验环境 Windows7+VisualStudio2010三、实验内容设计思路利用快速排序将数据集S排序，再遍历整个数组，利用Number类记录每个数出现的频率，从而找出集合的众数和重数。相关模块#include<iostream>#include<fstream>usingnamespacestd;//存储数y与出现频率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); //从文件读取数据 input>>size; int*a=newint[size]; for(inti=0;i<size;++i) input>>a[i]; input.close(); //对数组用快排排序 quickSort(a,0,size-1); Number*num=newNumber[size]; mode(a,size,num); write(outFileName,size,num); system("pause"); return0;}//将众数与重数写入文件，如果有多个，则将所有结果依次写入文件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 }}//找出众数与重数voidmode(int*a,intsize,Number*num){ intcount=1;//某个数出现的次数//遍历排好序的数组，计算出每个数出现的次数 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