给出一个昵称列表，统计每个昵称出现的次数（昵称中只可能出现大小写字母，一律按小写字母处理）。其中昵称个数N<=100000，每个昵称长度L<=100，不同昵称的总数T不超过5000。
有以下几种思路：
（1）排序，字符串交换的时候只交换指针而不交换字符串本身，这样做理论上是可以接收的，没有尝试；
（2）字典树，直接在结点中记录出现的次数，最后遍历树即可，我是这么做的，全部数据用了3.92s；
（3）Hash Table，hash 函数的设计是把字符串当成26进制整数，迭代求出hash函数值，求hash函数值的时间复杂度为O(L)，总时间复杂度O(Ln)。
以下是我的代码，是用字典树实现的：
#include<stdio.h>
typedef struct NODE
{
struct NODE *son[26];
long count;
}Nick;
long test,n;
Nick *root;
Nick* newnode()
{
long i;
Nick *p;
p=(Nick*)malloc(sizeof(Nick));
p->count=0;
for(i=0;i<26;i++)
p->son[i]=NULL;
return p;
}
void ins(char *s,Nick *p)
{
long t;
t=*s-'a';
if(p->son[t]!=NULL)
p=p->son[t];
else
{
p->son[t]=newnode();
p=p->son[t];
}
if(s[1]==0)
p->count++;
else
ins(s+1,p);
}
void release(Nick *node)
{
long i;
if(node!=NULL)
{
for(i=0;i<26;i++)
release(node->son[i]);
free(node);
}
}
void travel(Nick *p,char *s,long dep)
{
long i,j;
if(p->count>0)
{
for(j=0;j<dep;j++)
printf("%c",s[j]);
printf(" %ld\n",p->count);
}
for(i=0;i<26;i++)
if(p->son[i]!=NULL)
{
s[dep]=i+'a';
travel(p->son[i],s,dep+1);
s[dep]=0;
}
}
void init()
{
long i,j,k;
char s[150]={0},out[150]={0};
scanf("%ld",&test);
for(i=1;i<=test;i++)
{
root=newnode();
scanf("%ld",&n);
for(j=1;j<=n;j++)
{
scanf("%s",s);
for(k=0;s[k]!=0;k++)
if(s[k]>='A'&&s[k]<='Z')
s[k]+='a'-'A';
ins(s,root);// Insert
}
travel(root,out,0);
release(root);// Release
printf("\n");
}
}
int main()
{
freopen("nickname.in","r",stdin);
freopen("nickname.out","w",stdout);
init();
return 0;
}
posted on 2010-01-06 19:58
lee1r 阅读(233)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构