查找数组元素的最大值和最小值、众数问题

《查找数组元素的最大值和最小值、众数问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》上机实验报告专业班级学号学生姓名完成日期1.上机题目及实验环境1.1上机题目：1.1.1用分治法查找数组元素的最大值和最小值1.1.2众数问题1.2实验环境：CPU：IntelCorei32.30GHz内存：2.0G操作系统：Windows7软件平台：VisualC++2.算法设计与分析2.1查找数组最值2.1.1分治递归方法：l将max和min设置为静态全局变量；l将数据集array平均分为两个数据集；l分别求解两个数据集中的最大和最小值；l最终的最大和最小值通过与max和min

2、的值比较；l采用同样的处理方法递归处理以分好的数据集。2.1.2细节处理：l数组的大小为，n=0,1,2,3......l数组中的数字随机产生，数字的范围为1~100；l静态全局变量：max的初值为0，min的初值为101。2.2众数问题2.2.1快速排序算法：l设置两个变量i、j，排序开始的时候：i=left，j=right+1；l以第一个数组元素作为关键数据，赋值给temp，即temp=array[left]；l从j开始向前搜索，即由后开始向前搜索(--j)，找到第一个小于temp的值array

3、[j]；l从i开始向后搜索，即由前开始向后搜索(++i)，找到第一个大于temp的array[i]；l交换array[i]和array[j]的值；l重复搜索步骤，直到i=j；l将temp的值和array[j]的值交换，并以此为界，分别在对左右两边进行快速排序。3.核心代码3.1查找最值3.1.1流程图（如图1）将该数组均分，并分别对其求最值MaxAndMin（）比较、更新max和min的值开始该数组只有两个值结束（核心函数为voidMaxAndMin(intarray[N],intleft,intr

4、ight)）：图1.查找最值的流程图3.1.2核心代码如下：（注：max和min是静态全局变量）voidMaxAndMin(intarray[N],intleft,intright)//求最大值最小值函数，分治递归法{intmid;//数组的分界点if((left+1)==right)//分治的数组只有两个值时，更新max和min的值{if(array[left]

5、eft]>array[right]&&maxarray[left])//判断、更新最小值min=array[left];if(array[left]>array[right]&&min>array[right])min=array[right];}else{mid=(left+right)/2;//对数组进行分治MaxAndMin(array,left,mid);//对左边的数

6、组进行分治递归MaxAndMin(array,mid+1,right);//对右边的数组进行分治递归}}3.2众数问题结束以j为界，分别对左右两边的数组进行快排查找左边大于temp的值，右边小于temp的值，交换开始left

7、1;inttemp=array[left];//以第一个数为基准while(true){while(array[++i]temp);//从后面找小于基准的数if(i>=j)//当left>right时停止break;swap(array[i],array[j]);//交换两值}array[left]=array[j];array[j]=temp;intpart=j;//以靠左的较小值为界，对左右两部分数继续快排

8、quickSort(array,left,part-1);quickSort(array,part+1,right);}}4.运行与调试4.1查找数组最值产生随机数组并排序：（如图3、图4、图5）图3.随机数组之一及结果图4.随机数组之二及结果图5.随机数组之三及结果4.2众数问题4.2.1只有一个众数（如图6、图7）图6.只有一个众数的数组图7.只有一个众数的结果4.2.2没有众数（如图8、图9）图8.没有众数的数组图9.没有众数的结果4.2.3有两个众数（如图10