题目的意思是给出需要发送信息的名单，和已经发送信息的名单，统计出还需要给多少人发送。此题使用快速排序和二分查找复杂度方面已经可以承受，但是考虑到名单上名字可能有重复，需要判重，比较麻烦，所以使用的是字典树。
另外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 阅读(211)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构