【实验目的】
掌握熟悉地跪于分治策略算法设计。
【实验内容】
设T[0:n-1]是n个元素的一个数组。对任一元素x，设S(x)={i|T[i]=x}。当|S(x)|>n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0:n]是否有一个主元素。
【实验条件】
Microsoft Visual C++ 6.0
【需求分析】
算法需要求出在数组T[0:n]中出现次数最多的元素x出现的次数k.，如果k>(n+1)/2,则此数组有主元素，否则没有。
【设计原理】
算法需要求出在数组T[0:n]中出现次数最多的元素x出现的次数k.，如果k>(n+1)/2,则此数组有主元素，否则没有。先用Select算法求出数组中第（n+1）/2大的数，然后扫描数组，记录第（n+1）/2大的数在数组中出现的次数，如果k>(n+1)/2,则此数组有主元素，否则没有。
【概要设计】
数据：
a[N]：用于存放数组T[0:n-1];
int sign：如果存在主元素，sign=true；否则：sign=false;
函数：
int Partition(int a[],int p,int t,int x);
//数组划分，将小于等于x的元素移到x左边，大于x的元素移到x右边。
void Swap(int &x,int &y);
//交换元素x和y。
void QuickSort(int a[],int p,int r);
//快速排序。
int Select(int a[],int p,int r,int k);
//线性时间选择，找到第k大的数。
int MainNum(int a[],int p,int r);
//判断是否具有主元素。
【详细设计】
#include<iostream>
#include <ctime>
using namespace std;
//函数声明
int Partition(int a[],int p,int t,int x);
void Swap(int &x,int &y);
void QuickSort(int a[],int p,int r);
int Select(int a[],int p,int r,int k);
int MainNum(int a[],int p,int r);
//Select算法
int Select(int a[],int p,int r,int k)
{
if(r-p<75)
{
QuickSort(a,p,r);
return a[p+k-1];
}
for(int i=0;i<=(r-p-4)/5;i++)
{
QuickSort(a,p+5*i,p+5*i+4);
Swap(a[p+i],a[p+5*i+2]);
}
cout<<endl;
//找中位数的中位数。
int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
int s=Partition(a,p,r,x),
j=s-p+1;
int num=0;
int c=s,d=0;
//将与x相等的元素集中在一起。
while(c>d)
{
while(a[c--]==x);
while(c>d&&a[d++]!=x);
Swap(a[d-1],a[c+1]);
}
for(d=0;d<=j;d++)
if(a[d]==x)
num++;
cout<<"将与中位数相等的元素集中在一起后的数组为："<<endl;
for(int cc=0;cc<r-p;cc++)
cout<<a[cc]<<" ";
cout<<endl;
s=s-num+1;
j=s-p+1;
if(num>=1)
{
if((j<=k)&&(k<=j+num-1))
return a[s];
else
return Select(a,s+num+1,r,k-j-num);
}
else if(k<=j)
return Select(a,p,s,k);
else return Select(a,s+1,r,k-j);
}
//MainNum算法
int MainNum(int a[],int p,int r)
{
int t=Select(a,p,r,(r-p+2)/2),
mark=0;
for(int i=p;i<=r;i++)
{
if(a[i]==t)
mark++;
}
//*******debug***********//
cout<<"该数组的中位数为："<<t<<endl;
cout<<"出现的次数为："<<mark<<endl;
if(mark>(r-p+2)/2)
return 1;
else
return 0;
}
void QuickSort(int a[],int p,int r)
{
if(p<r)
{
int q=Partition(a,p,r,a[p]);
QuickSort(a,p,q-1);//对左半段排序
QuickSort(a,q+1,r);//对右半段排序
}
}
int Partition(int a[],int p,int r,int x)
{
//将<x的元素交换到左边区域
//将>x的元素交换到右边区域
int i=p,
j=r+1,
t;
for(i;i<j;i++)
if(a[i]==x)
{
t=i;
break;
}
while(true)
{
while(a[--j]>x);
while((i<j)&&a[++i]<=x);
if(i>=j)break;
Swap(a[i],a[j]);
}
Swap(a[t],a[j]);
return j;
}
//交换元素x,y
void Swap(int &x,int &y)
{
int t;
t=x;
x=y;
y=t;
}
void main(void)
{
int n=0;
cout<<"请输入数组元素个数：";
cin>>n;
int *a=new int[n];
//输出随机数列
srand((unsigned)time(0));
for(int i=0;i<n;i++)
{
a[i]=rand()%2;
cout<<a[i]<<" ";
}
cout<<endl;
n=100;
int y=MainNum(a,0,n-1);
if(y==0)
cout<<"该数组没有主元素！"<<endl;
else
cout<<"该数组存在主元素:"<<a[n/2]<<endl;
评论