词频统计

散列表应用:文件中单词词频统计
例:给定一个英文文本文件,统计文件中所有单词出现的频率,并输出词频最大的前10%的单词及其词频,假设单词字符定义为大小写字母、数字和下划线,其他字符均认为是单词分隔符,不予考虑

分析

  • 关键:对新读入的单词在已有的单词表中查找,如果已经存在,则将该单词的词频加1;如果不存在,则插入该单词并记词频为1
  • 如何设计该单词表的数据结构才可以进行快速的查找和插入:应用散列表
int main(){
    int TableSize=10000;                    //散列表估计大小
    int wordcount=0,length;
    HashTable H;
    ElementType word;
    FILE*fp;
    char document[30]="HarryPotter.txt";    //要被统计词频的文件名
    H=InitializeTable(TableSize);           //建立散列表
    if((fp=fopen(document,'r'))==NULL)FatalError("无法打开文件!\n");
    while(!feof(fp)){
        length=GetAWord(fp,word);           //从文件中读取一个单词
        if(length>3){                       //只考虑适当长度的单词
            wordcount++;                    //统计文件中单词总数
            InsertAndCount(word,H);          
        }
    }
    fclose(fp);
    printf("该文档总共出现%d个有效单词,",wordcount);
    Show(H,10.0/100);                       //显示词频前10%的所有单词
    //统计最大词频:
    //用一组数统计从1到最大词频的单词数
    //计算前10%的词频应该是多少
    //输出前10%的单词
    DestroyTable(H);                        //销毁散列表
    return 0;
}

电话聊天狂人

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

输入格式

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

输出格式

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

输入样例

4                        
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例

13588625832 3

分析

解法1-排序

  • 第1步:读入最多21052*10^5个电话号码,每个号码存为长度为11的字符串
  • 第2步:按字符串非递减顺序排序
  • 第3步:扫描有序数组,累计同号码出现的次数,并且更新最大次数
  • 此方法编程快捷简单,但无法扩展解决动态插入的问题

解法2-直接映射

  • 第1步:创建有2×10102\times10^{10}个单元的整数数组,保证每个电话号码对应唯一的单元下标:数组初始化为0
  • 第2步:对读入的每个电话号码,找到以之为下标的单元,数值累计1次
  • 第3步:顺序扫描数组,找出累计次数最多的单元
  • 此方法编程简单快捷,动态插入快
  • 但下标范围已经超过了unsigned long,需要2×1010×2bytes37GB2\times10^{10}\times2bytes≈37GB,为了2×1052\times10^5个号码扫描2×10102\times10^{10}个单元

解法3-带“智商“的散列

  • 分离链接法
  • 将最后5位用于散列

程序框架

int main(){
    创建散列表;
    读入号码插入表中;
    扫描表输出狂人;
    return 0;
}

HashTable的定义 ——> NextPrime ——> CreateTable
Hash,Find ——> Insert

扫描整个散列表:更新最大通话次数、更新最小号码+统计人数

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);
    DestroyTable(H);
    return 0;
}

输出狂人

void ScanAndOutput(HashTable H){
    int i,MaxCnt=PCnt=0;
    ElementType MinPhone;
    List Ptr;
    MinPhone[0]='\0';
    for(i=0;i<H->TableSizel;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");
}

HashTable的定义

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
    int Count;(新增)
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

#define MAXTABLESIZE 1000000
int Hash(int Key,int P){            //除留余数法散列函数
    return Key%P;
}
int NextPrime( int N )
{ // 返回大于N且不超过MAXTABLESIZE的最小素数 
    int i, p = (N%2)? N+2 : N+1; //从大于N的下一个奇数开始 

    while( p <= MAXTABLESIZE ) {
        for( i=(int)sqrt(p); i>2; i-- )
            if ( !(p%i) ) break; // p不是素数 
        if ( i==2 ) break; // for正常结束,说明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; // 从该链表的第1个结点开始 
    // 当未到表尾,并且Key未找到时 
    while( P && strcmp(P->Data, Key) )
        P = P->Next;

    return P; // 此时P或者指向找到的结点,或者为NULL 
}
bool Insert( HashTable H, ElementType Key )
{
    Position P, 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插入为H->Heads[Pos]链表的第1个结点 
        NewCell->Next = H->Heads[Pos].Next;
        H->Heads[Pos].Next = NewCell; 
        return true;
    }
    else { // 关键词已存在 
        printf("键值已存在");
        return false;
    }
}

ac代码

//map的应用!
#include<iostream>
#include<map>
#include<string>
using namespace std;
map<string,int>id;
string num1,num2,minphn;
int n,maxc,countc;
void crazyman();
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num1>>num2;
        id[num1]++,id[num2]++;
    }
    crazyman();
}
void crazyman(){
    for(auto i:id){
        if(i.second>maxc)maxc=i.second,minphn=i.first,countc=1;
        else if(i.second==maxc)countc++;
    }
    cout<<minphn<<' '<<maxc;
    if(countc>1)cout<<' '<<countc;
    cout<<endl;
} 

QQ帐户的申请与登陆

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是:据说现在的QQ号码已经有10位数了。

输入格式

输入首先给出一个正整数N(105)N(≤10^5),随后给出N行指令。每行指令的格式为:“命令符(空格)QQ号码(空格)密码”。其中命令符为“N”(代表New)时表示要新申请一个QQ号,后面是新帐户的号码和密码;命令符为“L”(代表Login)时表示是老帐户登陆,后面是登陆信息。QQ号码为一个不超过10位、但大于1000(据说QQ老总的号码是1001)的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。

输出格式

针对每条指令,给出相应的信息:
1)若新申请帐户成功,则输出“New: OK”;
2)若新申请的号码已经存在,则输出“ERROR: Exist”;
3)若老帐户登陆成功,则输出“Login: OK”;
4)若老帐户QQ号码不存在,则输出“ERROR: Not Exist”;
5)若老帐户密码错误,则输出“ERROR: Wrong PW”。

输入样例

5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com

输出样例

ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

ac代码

// 还是map
#include<iostream>
#include<map>
#include<string>
#define digitn 100500
using namespace std;
int n;
char command;
string id,pw;
map<string,string>qq;
void judgeqq(char,const string&,const string&),insert(string,string);
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>command>>id>>pw;
        judgeqq(command,id,pw);
    }
}
void judgeqq(char cd,const string&idstr,const string&pwstr){
    if(cd=='N'){
        if(qq.find(idstr)!=qq.end())cout<<"ERROR: Exist"<<endl;
        else{
            qq[idstr]=pwstr;
            cout<<"New: OK"<<endl;
        }
    }else if(cd=='L'){
        if(qq.find(idstr)==qq.end())cout<<"ERROR: Not Exist"<<endl;
        else if(qq[idstr]!=pwstr)cout<<"ERROR: Wrong PW"<<endl;
        else cout<<"Login: OK"<<endl;
    }
}