数组主元素（考研题）数据结构用链表_c语言

【问题描述】 已知一个整数序列A，长度为N，其中若存在a且a的个数大于N/2则称为A的主元素。 例如：0 5 5 3 5 7 5 5 则主元素为 5 又如：0 5 5 3 5 1 5 7 则没有主元素。 假设整数序列中的各个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出主元素。 若存在主元素，则输出该元素，否则输出-1。

【输入形式】 一个整数数组

【输出形式】 主元素 或 -1

【样例输入】 0 5 5 3 5 7 5 5

【样例输出】 5

一起加油吧!!!

#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define OVERLOW 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 5
typedef int ElemType;
typedef struct SqList{
    ElemType *elem;
    int length;
    int listsize;
}SqList;
int InitList_Sq(SqList *L)
{
    L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int));
    if(!L->elem)
        return OVERLOW;
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;

    return OK;
}
int Zen (SqList *L)
{

    if(L->length >= L->listsize)
    {
        int *newsize = (L->listsize + LISTINCREMENT) * sizeof(int);
        int *newbase = (int*)realloc(L->elem,newsize);
        if(!newbase)
            return OVERLOW;
        L->elem = newbase;
        L->listsize = L->listsize + LISTINCREMENT;
    }
    return OK;
}
int DestroyList_Sq(SqList *L)
{
    if(!L->elem)
        return OVERLOW;
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
    return OK;
}

int ClearList_Sq(SqList *L)
{
    if(!L->elem)
        return OVERLOW;
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
    return OK;
}

int ListLength_Sq(SqList *L)
{
    if(!L->elem)
        return OVERLOW;
    return L->length;
}
int ListEmpty_Sq(SqList *L)
{
    if(!L->elem)
        return OVERLOW;
    return OK;
}
void GetElem(SqList *L, int i, int *e)
{
    if(!L->elem)
        return OVERLOW;
    *e = L->elem[i-1];
}
int LocateElem(SqList *L, int e)
{
    int k;
    int i;
    if(!L->elem)
        return OVERLOW;
    for(i = 1; i < L->length; i++)
    {
        if(L->elem[i-1] == e)
        {
            return i;

        }
    }
    return OVERLOW;
}

int PriorElem(SqList *L, int cur_e, int *pre_e)
{
    if(!L->elem)
        return OVERLOW;
    int i;
    for(i=0; i<L->length; i++)
    {
        if(L->elem[i] == cur_e)
        {
            *pre_e = L->elem[i-1];
        }
    }
    return *pre_e;
}

int NextElem(SqList *L, int cur_e, int *next_e)  //求当前元素的后继元素
{
    if(!L->elem)
        return OVERLOW;
    int i;
    for(i=0; i<L->length; i++)
    {
        if(L->elem[i] == cur_e )
        {
            *next_e = L->elem[i+1];
        }
    }
    return *next_e;

}
int ListInsert(SqList *L, int i, int e) //在i位置前插入e
{
    if(i < 1 || i > L->length+1)
        return OVERLOW;
    int j;
    for(j=L->length-1; j >= i-1; j--)
        L->elem[j+1] = L->elem[j];
    L->elem[i-1] = e;
    L->length++;
    return OK;
}
int ListDelete_Sq(SqList *L, int i, int *e) //删除第i个元素，把值带给e
{
    if(i < 1 || i > L->length+1)
        return OVERLOW;
    int *p;
    p = L->elem+i-1;
    int *q;
    q = L->elem + L->length - 1;
    *e = *p;
    for(p++; p <= q; p++)
    {
        *(p-1) = *p;
    }
    L->length--;
    return OK;
}
void NumPairs_Max(SqList *L)
{
    int i, j;
    int max = 0;
    int pos;
    for(i = 0; i < L->length; i++)
    {
        for(j = i+1; j < L->length; j++)
        {
            pos = L->elem[i] - L->elem[j];
            if(pos > max)
            {
                max = pos;
            }
        }
    }
    printf("%d", max);

}
int MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc)
{
    Lc->length = La->length + Lb->length;
    Lc->elem = (int*)malloc(Lc->listsize * sizeof(int));
    if(Lc->elem)
        return OVERLOW;
    int *pa;
    pa = La->elem;
    int *pb;
    pb = Lb->elem;
    int *pc;
    pc = Lc->elem;
    int pa_last = La->elem + La->length - 1;
    int pb_last = Lb->elem + Lb->length - 1;
    while(pa <= pa_last && pb <= pb_last)
    {
        if(*pa <= *pb)
        {
            *pc++ = *pa++;
        }
        else
            *pc++ = *pb++;
    }
    while(pa <= pa_last)
    {
        *pc++ = *pa++;
    }
    while(pb <= pb_last)
    {
        *pc++ = *pb++;
    }

    return OK;
}
void Listinto(SqList *p)
{
    p->elem = NULL;
    p->length = 0;
    p->listsize = 0;
}
void checksize(SqList *p)//申请空间
{
    if(p->length== p->listsize)
    {
        int newlength;
        if(p->listsize == 0)
            newlength = p->listsize = 2;
        else
            newlength = 2*(p->listsize);
        ElemType *s = (ElemType*)realloc(p->elem, newlength*sizeof(ElemType));
        if(s == NULL)
        {
            printf("申请空间错误");
            exit(-1);
        }
        p->elem = s;
        p->listsize = newlength;
    }
}
void putinto(SqList *p)
{
    if(p ->listsize == 0)
        printf("顺序列表为空");
    int i = 0;
    for(i = 0; i < p->length; i++)
    {
        printf("%d ", p->elem[i]);
    }
}
void into(SqList *p, int x)
{
    checksize(p);
    p->elem[p->length] = x;
    p->length++;
}
void find(SqList *p, int p_length)
{
    int i, j, s = 0;
    int n;
    int m = p_length / 2;

    for(i = 0; i < p_length; i++)
    {
        n = 1;
        for(j = i + 1; j < p_length; j++)
        {
            if(p ->elem[i] == p->elem[j])
            {
                n++;
            }
            if(n > m)
            {
                printf("%d ", p->elem[i]);
                s++;
                break;
            }
        }
        if( s!=0 )
           break;
    }
    if(s == 0)
    {
         if(p->length == 1)
            printf("1");
         else
            printf("-1");
    }

}
int main()
{
    int i, n;
    SqList *q = (SqList*)malloc(sizeof(SqList));
    Listinto(q);
    int arr[100];
    for(i = 0; i < 100; i++)
    {
        scanf("%d", &arr[i]);
        into(q, arr[i]);
        char ch = getchar();
        if(ch != ' ')
            break;
    }
    int a;
    find(q, q->length);

    return 0;
}