給出一個昵稱列表，統計每個昵稱出現的次數（昵稱中只可能出現大小寫字母，一律按小寫字母處理）。其中昵稱個數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 閱讀(262)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構