題目的意思是給出需要發(fā)送信息的名單，和已經發(fā)送信息的名單，統(tǒng)計出還需要給多少人發(fā)送。此題使用快速排序和二分查找復雜度方面已經可以承受，但是考慮到名單上名字可能有重復，需要判重，比較麻煩，所以使用的是字典樹。
另外ACM中一個測試數據包含多組數據，所以在計算完一組數據之后不能忘記釋放內存，否則會超過內存限制。當然，高中的信息學競賽釋放不釋放就無所謂了……
以下是我的代碼：
#include<stdio.h>
#include<stdlib.h>
typedef struct TREE
{
long sign;
struct TREE *node[26];
}tree;
long ans;
tree *root;
void deal(char *s)
{
while(*s)
{
if((*s)>='A'&&(*s)<='Z')
(*s)+='a'-'A';
s++;
}
}
tree* newnode()
{
tree *p;
long i;
p=(tree*)malloc(sizeof(tree));
for(i=0;i<26;i++)
p->node[i]=NULL;
p->sign=0;
return p;
}
void visit(tree *p,char *s,int bj)
{
long pos=(*s)-'a';
if(p->node[pos]!=NULL)
p=p->node[pos];//已有該葉子
else
{
if(bj==0) return;//插入時才新建
p->node[pos]=newnode();
p=p->node[pos];
}
if(s[1]!=0)
visit(p,s+1,bj);
else
{
if(p->sign!=bj) ans+=(bj?1:-1);
p->sign=bj;
}
}
void release(tree *p)
{
long i;
for(i=0;i<26;i++)
if(p->node[i]!=NULL)
release(p->node[i]);
free(p);
}
int main()
{
long n,m,i;
char s[11];
FILE *fin,*fout;
fin=fopen("message.in","r");
fout=fopen("message.out","w");
fscanf(fin,"%ld",&n);
while(n!=0)
{
fscanf(fin,"%ld",&m);
ans=0;
root=newnode();
for(i=1;i<=n;i++)
{
fscanf(fin,"%s",s);
deal(s);
visit(root,s,1);
}
for(i=1;i<=m;i++)
{
fscanf(fin,"%s",s);
deal(s);
visit(root,s,0);
}
release(root);
fprintf(fout,"%ld\n",ans);
fscanf(fin,"%ld",&n);
}
fclose(fin);
fclose(fout);
return 0;
}
posted on 2010-01-06 21:03
lee1r 閱讀(208)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構