算法实验报告 算法实现题 2-1 众数问题 给定含有 n 个元素的多重集合 S，每个元素在 S 中出现的次数称为该元素的重数。 多重数集 S 中的重数最大的元素称为众数。 例如， S={1,2,2,2,3,5}。 多重集 S 得众数是 2，其重数为 3。 算法设计： 对于给定的由 n 个自然数组成多重数集 S，计算 S 的众数及其重数。 数据输入： 输入数据由文件名为 input.txt 的文本文件提供。文件的第 1 行为多重集 S 中元 素个数 n；在接下来的 n 行中，每行有一个自然数。 结果输出： 将计算结果输出到文件 output.txt。输出文件有两行，第 1 行是众数，第 2 行 是重数。 输入文件示例 input.txt 6 1 2 2 2 输出文件示例 output.txt 2 3 

算法实验报告 3 5 运行代码： #include #include using namespace std; //存储数y与出现频率 class Number{ public: Number(){count = 0;} int value; int count; }; void write(char* filename,int size,Number *num); void mode(int *a,int size,Number *num); void quickSort(int*,int,int); int Partition(int*,int,int); int main() { int size=0; int frequency=0; char* inFileName = "D:\\C++\\input.txt"; char* outFileName = "D:\\C++\\output.txt"; ifstream input(inFileName,ios::in); //从文件读取数据 input >> size; 

算法实验报告 int *a = new int[size]; for(int i=0; i>a[i]; input.close(); //对数组用快排排序 quickSort(a,0,size-1); Number *num = new Number[size]; mode(a,size,num); write(outFileName,size,num); system("pause"); return 0; } //将众数与重数写入文件，如果有多个，则将所有结果依次写入文件 void write(char* filename,int size,Number *num) { int max = 0,i; for( i=1; inum[max].count) max = i -1; ofstream output; output.open(filename,ios::out); output << num[max].value << "\n" << num[max].count << endl; for(i=0; i x to right while(true) { while(arr[++i]x); if(i>=j)break; swap(arr[i],arr[j]); 

算法实验报告 } arr[p]=arr[j]; arr[j]=x; return j; } //快排 void quickSort(int *arr,int p,int r) { if(p

算法实验报告 利用快速排序可以在 O（n）平均时间内将数据集排好序，再花费 O（n）遍历数 据集找到众数与重数，总的时间复杂度为 O（n）。