PTA 数据结构电话聊天狂人

左手的ㄟ右手 2022-04-14 05:06 191阅读 0赞

7-1 电话聊天狂人 （25 分）

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

### 输入格式: ###

输入首先给出正整数N（≤105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。

### 输出格式: ###

在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。

### 输入样例: ###

4
    13005711862 13588625832
    13505711862 13088625832
    13588625832 18087925832
    15005713862 13588625832

### 输出样例: ###

13588625832 3

#include <cstdio>
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #define OVERFLOW -1
    #define MAXTABLESIZE 1000000
    typedef long long int ElemType;
    typedef struct LNode  //链表
    {
        ElemType data;
        int cnt;
        LNode* next;
    }LNode,*LinkList;
    typedef struct TbNode  //哈希表
    {
        int tablesize;  //表的最大长度
        LinkList heads;  //链表头结点数组
    }TbNode,*HashTable;
    int NextPrime(int n)  //获取大于n的第一个素数
    {
        int i, p = (n % 2) ? n + 2 : n + 1;
        while (p < MAXTABLESIZE) {
            for (i = sqrt(p); i > 2; i--)
                if (!(p%i))
                    break;
            if (i == 2)
                break;
            else
                p += 2;
        }
        return p;
    }
    int Hash(ElemType key,int size)
    {
        return key % size;
    }
    HashTable CreateHashTable(int size)
    {
        HashTable H = (HashTable)malloc(sizeof(HashTable));
        if(!H)
            exit(OVERFLOW);
        H->tablesize = NextPrime(size);
        H->heads = (LinkList)malloc(H->tablesize*sizeof(LNode));
        for(int i=0;i<H->tablesize;i++)
        {
            H->heads[i].data = 0;
            H->heads[i].cnt = 0;
            H->heads[i].next = NULL;
        }
        return H;
    }
    LNode* Find(HashTable H,ElemType key)
    {
        int pos = Hash(key,H->tablesize);
        LNode* p = H->heads[pos].next;
        while(p && p->data != key)
        {
            p = p->next;
        }
        return p;
    }
    void Insert(HashTable H,ElemType key)
    {
        int pos = Hash(key,H->tablesize);
        LNode* p = Find(H,key);
        if(!p)  //未找到key，则将key插入
        {
            LinkList pNew = (LinkList)malloc(sizeof(LNode));
            if(!pNew)
                exit(OVERFLOW);
            pNew->data = key;
            pNew->cnt = 1;
            pNew->next = H->heads[pos].next;
            H->heads[pos].next = pNew;
        }
        else  //找到key，则计数增加
        {
            p->cnt++;
        }
    }
    void FindMax(HashTable H)
    {
        int MaxCnt = -1,NumberofMaxCnt = 0;
        ElemType MinPhone;
        for(int i=0;i<H->tablesize;i++)
        {
            LNode* p = H->heads[i].next;
            while(p)
            {
                if(p->cnt > MaxCnt)
                {
                    MaxCnt = p->cnt;
                    MinPhone = p->data;
                    NumberofMaxCnt = 1;
                }
                else if(p->cnt == MaxCnt)
                {
                    NumberofMaxCnt++;
                    if(MinPhone > p->data)
                        MinPhone = p->data;
                }
                p = p->next;
            }
        }
        std::cout<< MinPhone << " " << MaxCnt;
        if(NumberofMaxCnt > 1)
            std::cout<< " " << NumberofMaxCnt;
        std::cout << std::endl;
    }
    int main()
    {
        int n;
        std::cin >> n;
        ElemType key;
        HashTable H = CreateHashTable(n);
        while(n--)
        {
            std::cin >> key;
            Insert(H,key);
            std::cin >> key;
            Insert(H,key);
        }
        FindMax(H);
        return 0;
    }