数据结构与算法分析(C语言)习题2.19 编写一个程序求解主要元素。

数据结构与算法分析(C语言)习题2.19
题目描述：

首先找出主要元素的一个候选元(这是难点)。这个候选元是唯一有可能是主要元素的元素。第二步确定是否这个候选元是主要元素。为了找出候选元，构造第二个数组BB。比较A1A1和A2A2，如果它们相等则取其中之一加到数组BB中；否则什么都不做；然后比较A3A3和A4A4，按同样的方式处理，其次类推直到读完这个数组，然后递归的寻找数组B中的候选元，它也是AA的候选元. (为什么?)
a, 递归如何终止?
b, 当N是奇数时, 如何处理?
c, 该算法的运行时间是多少?
d, 我们如何避免使用附加数组BB?
e, 编写一个程序求解主要元素.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/*已知一个数组a，和他的元素个数n。求该数组的主要元素，若存在则返回该元素，否则返回-1,前提-1不是数组中元素*/
int
Search(int a[],int n)
{
int *b;
b=(int *)malloc(n*sizeof(int));
/*基准情况*/
if(n==0)	return -1;	//没有主要元素
if(n==1)
return a[0];
/*递归调用*/
else
{
int i=0,j=0;
for(i=0;i<n/2*2;i+=2)
{
if(a[i]==a[i+1])
{
b[j]=a[i];
j++;
}
}
if(i==n-1)	//说明是奇数个
{
b[j]=a[n-1];
j++;
}
//得到数组b和b中元素的个数j
return Search(b,j);
/*返回值:返回该主要元素*/
}
}
int check(int a[],int n)	//验证Search函数得到的是否为主要元素。
{
int answer = Search(a,n);
if(answer==-1)	return -1;
else	//验证过程
{
int count=0;
for(int i=0;i<n;i++)
{
if(a[i]==answer)	count++;
}
if(count>n/2)	return answer;
else	return -1;
}
}
int main()
{
int a[]={3,3,7,2,7,7,2,7,7,7,7,7};
int a1[]={3,4,4};
int no[]={3,3,4,2,4,4,2,4};
int wh[]={3,3,4,2,4,2,4,5};
int b=check(wh,sizeof(wh)/sizeof(int));	//可用a和a1来测试
a为偶数个，a1为奇数个,no和wh为不存在主要元素。
printf("%d",b);
return 0;
}

这里没有讨论时间复杂度，应该是O(n) 。
关于 第四小题 d 避免使用附加数组B 。欢迎讨论。

最后

以上就是神勇心锁为你收集整理的数据结构与算法分析(C语言)习题2.19 编写一个程序求解主要元素。的全部内容，希望文章能够帮你解决数据结构与算法分析(C语言)习题2.19 编写一个程序求解主要元素。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。