电话聊天狂人

数据结构

Word count: 1kReading time: 4 min

 2019/09/09   Share

电话聊天狂人

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

输入格式:

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

输出格式:

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

输入样例:

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例:

1	13588625832 3

题目分析

这道题是一道很典型的利用散列值存储快速查找得到结果的题目

由于存储的值较长且需要统计值出现的次数,我们可以采用散列中的链地址法来处理散列冲突也减小了散列表的空间

然后我们来观察存储的值的特点,我们知道电话号码的特点

前三位:网络识别号

中间四位:地区编码

后四位:用户号码(随机)

所以我们可以通过采取最后5位随机性最大的来存储

而且我们注意

如果有多个电话狂人则需要更新值最小的号码,且需要统计人数

代码实现

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define KEYLENGTH 11 //关键词最大长度
#define MAX 1000000
#define MAXD 5  //参与散列映射计算的字符个数
using namespace std;
typedef char ElementType[KEYLENGTH+1];
typedef int Index; //散列地址类型

typedef struct LNode *PtrToLNode;
struct LNode{
    ElementType Data;
    PtrToLNode Next;
    int Count;
};

typedef PtrToLNode Position;
typedef PtrToLNode List;

typedef struct TblNode *HashTable;
struct TblNode{
    int TableSize; //表的最大长度
    List Heads;    //指向链表头结点的数组
};

int Hash(int Key,int TableSize);
int NextPrime(int N);
HashTable CreateTable(int TableSize);
Position Find(HashTable H,ElementType Key);
bool Insert(HashTable H,ElementType Key);
void ScanAndOutput(HashTable H);


void ScanAndOutput(HashTable H)
{
    //扫描整个散列表,更新最大通话次数和更新最小号码且统计人数
    int MaxCnt=0;
    int PCnt=0;
    ElementType MinPhone;
    List Ptr;
    MinPhone[0]='\0';
    for(int i=0;i<H->TableSize;i++)
    {
        Ptr=H->Heads[i].Next;
        while(Ptr){
            if(Ptr->Count>MaxCnt){  //更新最大通话次数
                MaxCnt = Ptr->Count;
                strcpy(MinPhone,Ptr->Data);
                PCnt=1;
            }else if(Ptr->Count == MaxCnt){  //若最大通话次数相等则选择最小号码并增加次数
                PCnt++;
                if(strcmp(MinPhone,Ptr->Data)>0)
                {
                    strcpy(MinPhone,Ptr->Data);
                }
            }
            Ptr=Ptr->Next;
        }
    }

    printf("%s %d",MinPhone,MaxCnt);
    if(PCnt>1)printf(" %d",PCnt);
    printf("\n");
}



bool Insert(HashTable H,ElementType Key)
{
  Position P;
  Position NewCell;
  Index Pos;

  P=Find(H,Key);
  if(!P) //若关键词未找到
  {
      NewCell=(Position)malloc(sizeof(struct LNode));
      strcpy(NewCell->Data,Key);
      NewCell->Count=1;
      Pos=Hash(atoi(Key+(KEYLENGTH-MAXD)),H->TableSize);
      NewCell->Next=H->Heads[Pos].Next;
      H->Heads[Pos].Next=NewCell;
      return true;
  }
  else  //关键词已存在
  {
      P->Count++;
      return false;
  }
}

int NextPrime(int N)
{
    //返回大于N且不超过MAX的最小素数
    int i,p=(N%2)?N+2:N+1; //从大于N的下一个奇数开始
    while(p<=MAX)
    {
        for(i=(int)sqrt(p);i>2;i--)
            if(!(p%i)) break;
        if(i==2) break;  //说明p是素数
        else p+=2; //若不是则从下一个奇数继续寻找
    }
    return p;
}

HashTable CreateTable(int TableSize)
{
    HashTable H;
    int i;
    H=(HashTable)malloc(sizeof(struct TblNode));
    H->TableSize=NextPrime(TableSize);
    H->Heads=(List)malloc(H->TableSize*sizeof(struct LNode));
    for(i=0;i<H->TableSize;i++)
    {
        H->Heads[i].Data[0]='\0';
        H->Heads[i].Next=NULL;
        H->Heads[i].Count=0;
    }
    return H;
}

Position Find(HashTable H,ElementType Key)
{
    Position P;
    Index Pos;

    Pos=Hash(atoi(Key+KEYLENGTH-MAXD),H->TableSize); //初始化散列位置

    P=H->Heads[Pos].Next;
    while(P&&strcmp(P->Data,Key))
        P=P->Next;
    return P;
}

int Hash(int Key,int TableSize)
{
    return Key%TableSize;
}

int main()
{
    int N,i;
    ElementType Key;
    HashTable H;
    scanf("%d",&N);
    H=CreateTable(N*2); //创造散列表
    for(i=0;i<N;i++)
    {
        scanf("%s",Key);Insert(H,Key);
        scanf("%s",Key);Insert(H,Key);
    }
    ScanAndOutput(H);
    return 0;
}

Next Post

关键活动
Previous Post

Sort-with-Swap(0, i)

CATALOG

1. 电话聊天狂人
1.1. 题目分析
1.2. 代码实现

