6.词频统计、电话聊天狂人、QQ帐户的申请与登陆
词频统计
散列表应用：文件中单词词频统计
例：给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前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行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。
输出格式
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832输出样例
13588625832 3分析
解法1-排序
- 第1步：读入最多个电话号码，每个号码存为长度为11的字符串
- 第2步：按字符串非递减顺序排序
- 第3步：扫描有序数组，累计同号码出现的次数，并且更新最大次数
- 此方法编程快捷简单，但无法扩展解决动态插入的问题
解法2-直接映射
- 第1步：创建有个单元的整数数组，保证每个电话号码对应唯一的单元下标：数组初始化为0
- 第2步：对读入的每个电话号码，找到以之为下标的单元，数值累计1次
- 第3步：顺序扫描数组，找出累计次数最多的单元
- 此方法编程简单快捷，动态插入快
- 但下标范围已经超过了unsigned long，需要，为了个号码扫描个单元
解法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行指令。每行指令的格式为：“命令符（空格）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: OKac代码
// 还是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;
}
}本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 hetumessi's Blog！
相关推荐
评论
ValineGitalk
