数据结构实验：哈希表

浅浅的花香味﹌ 2022-08-10 04:58 225阅读 0赞

## 数据结构实验：哈希表 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

在n个数中，找出出现次数最多那个数字，并且输出出现的次数。如果有多个结果，输出数字最小的那一个。

## 输入 ##

单组数据，第一行数字n（1<=n<=100000)。  
接下来有n个数字，每个数字不超过100000000

## 输出 ##

出现次数最多的数字和次数。

## 示例输入 ##

3
    1 1 2

## 示例输出 ##

1 2

## 提示 ##

## 来源 ##

## 示例程序 ##

#include <stdio.h>   
    #include <stdlib.h>   
    #define M 100000   
    typedef struct node   
    {   
        int num,time;   
        struct node *next;   
    }*A,B;   
    A head[M];   
    int main()   
    {   
        A p,q,r;   
        int n,i,fig=0,ci=0;   
        int a;   
        for(i=0; i<M; i++)   
        {   
            head[i]=(A)malloc(sizeof(B));   
            head[i]->next=NULL;   
        }   
        scanf("%d",&n);   
        for(i=0; i<n; i++)   
        {   
            scanf("%d",&a);   
            int y=a%M;   
            p=head[y]->next;   
            q=head[y];   
            while(p!=NULL)   
            {   
                if(p->num == a)   
                {   
                    p->time++;   
                    if(p->time > ci)   
                    {   
                        fig=p->num;   
                        ci=p->time;   
                    }   
                    else if(p->time==ci)   
                    {   
                        if(p->num < fig)   
                            fig=p->num;   
                    }   
                    break;   
                }   
                q=p;   
                p=p->next;   
            }   
            if(p==NULL)   
            {   
                r=(A)malloc(sizeof(B));   
                r->num=a;   
                r->time=1;   
                q->next=r;   
                r->next=NULL;   
                if(r->time > ci)   
                {   
                    fig=r->num;   
                    ci=r->time;   
                }   
                else if(r->time==ci)   
                {   
                    if(r->num < fig)   
                        fig=r->num;   
                }   
            }   
        }   
        printf("%d %d\n",fig,ci);   
        return 0;   
    }