基础实验5-2.2 电话聊天狂人 (25分)-散列表

基础实验5-2.2 电话聊天狂人 (25分)-散列表

 

解题思路:

用散列表(链表结构)

1、计算散列表长度(取比输入数据大一点的素数p)

2、构造散列函数

3、读入数据,求出散列位置插入

4、一边遍历散列表,一边求出现最多的电话狂人

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <math.h>
#define KeyLength 11
#define ElemType char
typedef enum {false,true
             } bool;
typedef struct LNode {
    ElemType Data[KeyLength+1];
    struct LNode *Next;
    int cnt;
}*List,LNode;
typedef struct {
    int TableSize;
    List *HashList;
}*HashTable;
//判断是否是素数 bool IsPrime(int n) { if(n==0||n==1) return false; if(n>2) { int i; for(i=2; i<=sqrt(n)+1; i++) { if(n%i==0)return false; } } return true; }
//求比n大的第一个素数 int NextPrime(int n) { int i=n+1; while(1) { if(IsPrime(i)) return i; i++; } return i; }
//初始化散列表 HashTable CreateHash(int size) { HashTable H=(HashTable)malloc(sizeof(HashTable)); H->TableSize=NextPrime(size); H->HashList=(List*)malloc(sizeof(List)*H->TableSize); int i; for(i=0; i<H->TableSize; i++) { H->HashList[i]=(LNode*)malloc(sizeof(LNode)); H->HashList[i]->Next=NULL; } return H; }
//构造散列函数 int Hash(HashTable H,int key) { return key%H->TableSize; }
//插入 void Insert(HashTable H,ElemType Value[]) { int key=Hash(H,atoi(Value+KeyLength-5));//atoi(Value+KeyLenght-5)取键值的最后5位 int flag=0; LNode *p=H->HashList[key]; while(p->Next) { if(!strcmp(p->Next->Data,Value)) { p->Next->cnt++; flag=1; break; } p=p->Next; } if(!flag) { LNode *s=(LNode *)malloc(sizeof(LNode)); strcpy(s->Data,Value); s->Next=NULL; s->cnt=1; p->Next=s; p=s; } }
//遍历求电话狂人 void FindMaxCnt(HashTable H) { LNode *p; int i,maxcnt=0,count; char min[KeyLength+1]; for(i=0; i<H->TableSize; i++) { p=H->HashList[i]->Next; while(p) { if(p->cnt>maxcnt) { maxcnt=p->cnt; count=1; strcpy(min,p->Data); } else if(p->cnt==maxcnt) { count++; if(strcmp(p->Data,min)<0) { strcpy(min,p->Data); } } p=p->Next; } } printf("%s %d",min,maxcnt); if(count>1) printf(" %d",count); } int main() { int n; scanf("%d",&n); int i; char str[KeyLength+1]; HashTable H=CreateHash(2*n); for(i=0; i<n; i++) { scanf("%s",str); Insert(H,str); scanf("%s",str); Insert(H,str); } FindMaxCnt(H); return 0; }

 

上一篇:7.3


下一篇:课后习题 2-14 针对带头结点的单链表,试编写以下函数