众数问题.cpp

给定含有n个元素的多重集合s

#include"iostream"
#include"fstream"
using namespace std;
#define N 50000        //数组的长度（元素的数量不能超过这个数）

//快速排序子函数
void exchange(int &a,int &b){
	int temp;
	temp=a;a=b;b=temp;
}
//快速排序子函数
int partition(int A[],int p,int r){
	int x,i,j;
	x=A[r];
	i=p-1;
	for(j=p;j<=r-1;j++)
		if(A[j]<=x){
			i+=1;
			exchange(A[i],A[j]);
		}
	exchange(A[i+1],A[r]);
	return i+1;
}
//快速排序
void quicksort(int A[],int p,int r){
	int q;
	if(p<r){
		q=partition(A,p,r);
		quicksort(A,p,q-1);
		quicksort(A,q+1,r);
	}
}


int main(){
	int number;                        //存储读入的元素个数 
	int a[N];                          //存储读入的多重集元素
	int b[N];                          //存储多重集中各不相同的元素
	int c[N];	                       //存储跟b[N]相应的元素的个数
	int counter;                       //计算相同元素的个数
	int max;                           //存储c[N]中最大的数，即重数
	int p;                             //记下c[N]中第一个最大的数的位置
	int i,j,k;                         //一般的循环比较计数变量
	ifstream infile;
	ofstream ofile;
	cout<<"读入多重集元素个数：";
	infile.open("F:\\测试数据\\分治法\\众数问题\\test\\mode5.in");//读入文件路径
	infile>>number;
	cout<<number<<endl;
	cout<<"读入多重集元素..."<<endl;
	i=0;
	while(1){
		infile>>a[i];
		if(infile.eof()!=0)break;
		i++;
	}

	quicksort(a,0,number-1);             //快速排序
	
	i=0;
	k=0;
	for(;i<number;){                     //统计元素个数
		j=i+1;
		counter=1;
		while(a[j]==a[i]&&j<number){
			counter++;
			j++;
		}
		b[k]=a[i];
		c[k]=counter;
		k++;
		i=i+counter;
	}
	max=c[0];
	p=0;
	i=1;
	while(i<k){                          //找出重数并记下第一个众数的位置
		if(c[i]>max){
			max=c[i];
			p=i;
		}
		i++;
	}
	ofile.open("F:\\测试数据\\分治法\\众数问题\\out_data1.2.out");//输出文件路径
	cout<<"众数："<<b[p]<<"   ";              //输出众数
	ofile<<"众数："<<b[p]<<"   ";
	for(i=p+1;i<k;i++){                       //继续查找输出和第一个众数相同重数的其他众数
		if(c[i]==max){
			cout<<b[i]<<"   ";
			ofile<<b[i]<<'\t';
		}
	}
	cout<<endl;
	ofile<<endl;
	cout<<"重数："<<max<<endl;                //输出重数
	ofile<<"重数："<<max<<endl;
	infile.close();
	ofile.close();
	return 0;
}