majo.cpp

给定含有n 个元素的多重集合S = {a1, a2,., an }

/*
	问题描述：给定含有 n 个元素的多重集合S 每个元素在S中出现的次数称为该元素的重数。
	多重集S中重数大于 n/2的元素称为主元素。例如，S={2，2，4，2，1，2，5，2，2，8}。 
	多重集S的主元素是2，其重数为6。  
	算法设计：对于给定的 n 个元素的多重集合S 试设计一个O(n)时间算法，计算S的主元素。 
	数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行多重集S中元素个数n；
	接下来的 1 行中有n 个正整数。 
	结果输出:将计算出的S的主元素输出到文件output.txt中。当 S 中没有主元素时输出0。 

*/

#include <stdlib.h>
#include <string.h>
#include <fstream.h>

long int *array_t;			//定义动态数组存放正整数
long int *array_max;		//定义动态数组存各个多重集正整数

void main(){

	long int i = 0,j = 0;
	long int num_max,num_now,num_temp = 0; //正整数num_max个，读入的正整数值num_now，正整数值最大num_temp
	long int sum_add=0;			//最大的多重集		
	long int num_main=0;		//主元素
	
	ifstream in_f("input.txt");
	ofstream out_f("output.txt");
	
	in_f >> num_max; 		//读第一行的多重集S中元素个数n

	if((array_t = new long int[num_max]) == NULL)
	{
		cout<<"can't allocate more memory,terminating.";
		exit(1);
	}

	for(i=0;i<num_max;i++)	//读入正整数并赋值给动态数组array_t
	{
		in_f >> num_now;
		array_t[i] = num_now;
		
		if(num_temp < array_t[i])	//找出值最大的赋给num_temp
		{
			num_temp = array_t[i];
		}
	}

	if((array_max = new long int[num_temp]) == NULL)
	{
		cout<<"can't allocate more memory,terminating.";
		exit(1);
	}
	
	for(i=0;i<num_max;i++)		//有用到的动态数组赋初值
	{
		j = array_t[i];

		if(array_max[j-1] != 0)	//找出重数最大值及元素值
		{
			array_max[j-1] = 0;
		}
	}

	for(i=0;i<num_max;i++)
	{
		j = array_t[i];
		array_max[j-1]++;				//判断读入正整数则其累加

		if(sum_add < array_max[j-1])	//找出重数最大值及元素值
		{
			sum_add = array_max[j-1];
			num_main = j;
		}
	}
	
	delete []array_t;
	delete []array_max;

	if(sum_add > num_max/2)		//判断出现次数最多的正整数是否满足主元素
		out_f << num_main;		//是输出主元素
	else
		out_f << 0;				//输出0
}