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

100 阅读 0 评论 66 点赞

我是靠谱客的博主神勇心锁，这篇文章主要介绍数据结构与算法分析(C语言)习题2.19 编写一个程序求解主要元素。，现在分享给大家，希望可以做个参考。

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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;
}