这是我的字典树写法
#include
#include
#include
#include
#define SPACE 60000
struct node{
int fre;
struct node *nodePtr[26];
};
struct Word{
char word[35];
struct Word *next;
};
struct node *head;
FILE *in,*out;
struct Word a[SPACE];
struct Word *end[SPACE];
int ind[5000];
int n;
void tolow(char sr[]){
int i;
for(i=0;sr[i]!='\0';i++){
sr[i]=tolower(sr[i]);
}
}
int readWord(char sr[]){
char c;
int i=0;
for(c=fgetc(in);!isalpha(c);c=fgetc(in)){
if(c==EOF)
return 0;
}
for(;isalpha(c);c=fgetc(in)){
sr[i++]=c;
}
sr[i]='\0';
ungetc(c,in);
return 1;
}
void insertNode(char sr[]){
int i,k;
struct node p=head;
for(i=0;sr[i]!='\0';i++){
if(p->nodePtr[sr[i]-'a']==NULL){
p->nodePtr[sr[i]-'a']=(struct node)malloc(sizeof(struct node));
for(k=0;k
p->nodePtr[sr[i]-'a']->nodePtr[k]=NULL;
}
p->nodePtr[sr[i]-'a']->fre=0;
}
p=p->nodePtr[sr[i]-'a'];
}
p->fre++;
}
void visitNode(struct node p,int length,char buffer[]){
int i;
for(i=0;i
if(p->nodePtr[i]!=NULL){
buffer[length]=i+'a';
if(p->nodePtr[i]->fre>0){
int freq=p->nodePtr[i]->fre;
buffer[length+1]='\0';
if(strlen(a[freq].word)==0){
strcpy(a[freq].word,buffer);
a[freq].next=NULL;
end[freq]=&a[freq];
ind[n++]=freq;
}
else{
struct Word *q=end[freq];
q->next=(struct Word)malloc(sizeof(struct Word));
strcpy(q->next->word,buffer);
end[freq]=q->next;
q->next->next=NULL;
}
}
visitNode(p->nodePtr[i],length+1,buffer);
}
}
}
int cmp(const void a,const void *b){
return *(int *)b-(int *)a;
}
int main(void){
char sr[35];
char buffer[100];
int i,j;
struct Word q;
in=fopen("article.txt","r");
out=fopen("wordfreq.txt","w");
head=(struct node)malloc(sizeof(struct node));
for(i=0;i
head->nodePtr[i]=NULL;
}
head->fre=0;
while(readWord(sr)){
tolow(sr);
insertNode(sr);
}
fclose(in);
visitNode(head,0,buffer);
qsort(ind,n,sizeof(int),cmp);
for(i=0;i
for(q=&a[ind[i]];q!=NULL;q=q->next)
fprintf(out,"%s %d\n",q->word,ind[i]);
}
fclose(out);
for(i=0,j=0;i
for(q=&a[ind[i]];q!=NULL;q=q->next){
printf("%s %d\n",q->word,ind[i]);
j++;
if(j>=100){
return 0;
}
}
}
return 0;
}