用c语言统计一个大文件中的 英语单词的频率，如何提高速度性能，不担心空间内存问题

这是我的字典树写法
#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;
}

你的文件中单词的数量一共有多少？量变引起质变，不同的数量级算法肯定也不一样

就速度性能来说，字典树的做法已经是下限了，不可能再低了，我个人觉得的。

只是个建议：可以试一下哈希表，毕竟指针跳转也是有开销的，并且无法利用计算机的缓存机制提高效率，每个单词的每个字母都进行一次指针跳转（字典树）还是会影响效率的。

有很多可用的字符串哈希函数还是挺不错的，我比较喜欢http://www.cse.yorku.ca/~oz/hash.html 的djb2

而且自己实现哈希表的话可以按照自己的意愿rehash，这样也可以一定程度上控制空间复杂度。