主元素(Version1.0)

亦凉 2023-01-22 12:50 28阅读 0赞

已知一个整数序列A=(a0,a1,…,an−1)，其中0≤ai≤n,0≤i<n)。若某元素在数据序列中重复出现的次数为m，且m≥n/2，则称x为A的主元素。

如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。

假设顺序表A中有n个元素，请设计算法，找出A的主元素，若存在主元素，则输出主元素；否则输出A中没有主元素的信息。

### 输入 ###

每组数据有两行，第一行为一个整数n，代表数组中有n个元素。第二行为数组中的n个元素（元素之间用空格分隔）。

### 输出 ###

每组数据输出一行，若数组中存在主元素，输出主元素的值，若数组中不存在主元素，则输出A中没有主元素。

### 输入示例1 ###

5  
    1 2 3 4 5

### 输出示例1 ###

There is no main element.

### 输入示例2 ###

7  
    4 5 5 5 1 5 7

### 输出示例2 ###

The main element of A is 5.

\[程序代码\]

#include<stdio.h>
    void InitArray(short *, short);
    short MainElement(short *, short);
    int main()
    {
        /* 数据序列中元素的个数 */
        short N;
        while(scanf("%hd", &N) != 1 || N < 1)
        {
            while(getchar() != '\n') ;
            printf("请输入合法数据.\n");
        }
        /* 定义数据序列 */
        short value[N];
        /* 初始化数据序列 */
        InitArray(value, N);
        /* 寻找数据序列中的主元素 */
        short temp = MainElement(value, N);
        if(temp == -1)
        {
            /* 没找到主元素 */
            printf("There is no main element.\n");
        }
        else
        {
            /* 找到主元素 */
            printf("The main element of A is %hd\n", temp);
        }
    }
    /* 寻找数据序列中的主元素 */
    short MainElement(short *p, short N)
    {
        short i, j;
        short sum = 0;
        for(i = 0; i < N; i ++)
        {
            for(j = 0, sum = 0; j < N; j ++)
            {
                if(j != i)
                {
                    if(*(p + i) == *(p + j))
                    {
                        sum ++;
                    }
                }
                if(sum >= N / 2)
                {
                    return *(p + i);
                }
            }
        }
        /* 程序执行至此, 说明没找到主元素 */
        return -1;
    }
    /* 初始化数据序列 */
    void InitArray(short *p, short N)
    {
        short i = 0;
        while(i < N)
        {
            scanf("%hd", p + i);
            i ++;
        }
    }

\[运行结果\]

![2021051922170386.png][]

[2021051922170386.png]: /images/20221020/3ad40a5d1339436987883a2ac022e099.png