C语言用二叉树统计一个源文件中每个单词的次数


由于出现的单词不确定，所以用二叉树实现:

  1. //TreeNode.h  
  2.  
  3. typedef struct _TreeNode 
  4. { 
  5.      int count; //出现的次数  
  6.      char* word;//单词本身   
  7.      struct _TreeNode* left; 
  8.      struct _TreeNode* right;   
  9.          
  10. }TreeNode; 
  11.  
  12. //给TreeNode分配内存   
  13. TreeNode* talloc(void) 
  14. { 
  15.    return (TreeNode*)malloc(sizeof(TreeNode));         
  16. } 
  17.  
  18. //打印tree   
  19. void tprint(TreeNode* root) 
  20. { 
  21.      //打印left->self->right  
  22.      if(root!=NULL) 
  23.      { 
  24.          tprint(root->left); 
  25.          printf("%4d %s\n",root->count,root->word);   
  26.          tprint(root->right);                 
  27.      } 
  28. } 
  29.  
  30. //把单词添加节点的合适位置   
  31. TreeNode* addNode(TreeNode* node,const char* word) 
  32. { 
  33.     int con;       
  34.     TreeNode* tmp;   
  35.     if(node==NULL) 
  36.     { 
  37.         node = talloc(); 
  38.         node->count=1;             
  39.         node->word=strdup(word); 
  40.         node->left=node->right=NULL; 
  41.     }else if((con=strcmp(word,node->word))<0) 
  42.     { 
  43.        tmp = addNode(node->left,word); 
  44.        node->left=tmp;     
  45.     }else if(con>0) 
  46.     { 
  47.        tmp = addNode(node->right,word);   
  48.        node->right=tmp;     
  49.     }else{ 
  50.        node->count++;     
  51.     }     
  52.     return node; 
  53. } 
  54. /** 
  55. 从指定的流中读取单词  
  56. */ 
  57. int getWord(char* ch,size_t n,FILE* f) 
  58. { 
  59.    int c; 
  60.    char* p = ch; 
  61.    while(isspace(c=fgetc(f))) 
  62.          ; 
  63.   if(c!=EOF) 
  64.        *p++=c; 
  65.   if(!isalpha(c)) 
  66.   { 
  67.      *p='\0';             
  68.      return c; 
  69.   } 
  70.   for(;--n>0;p++) 
  71.   { 
  72.      if(!isalnum(*p=fgetc(f))) 
  73.      {               
  74.         ungetc(*p,f);                         
  75.         break; 
  76.      }             
  77.   } 
  78.    *p='\0'; 
  79.    return c;       
  80.                  
  81. } 
  82. //是否tree占用的内存   
  83. void treeFree(TreeNode* root) 
  84. { 
  85.    if(root!=NULL) 
  86.    { 
  87.       treeFree(root->left);             
  88.       free(root->word); //释放节点的word占用的内存   
  89.       free(root);       //是否节点占用的内存           
  90.       treeFree(root->right);             
  91.    }   
  92. } 
  93. //Test.c  
  94. #include <stdio.h>  
  95. #include <stdlib.h>  
  96. #include "TreeNode.h"  
  97.  
  98. #define MAX 100  
  99. int main(int argc, char *argv[]) 
  100. { 
  101.   FILE* f; 
  102.   char w[MAX]={0}; 
  103.   char* fname="TreeNode.h"; 
  104.   if((f=fopen(fname,"r"))!=NULL) 
  105.   { 
  106.     TreeNode* root = NULL; 
  107.     while((getWord(w,MAX,f)!=EOF)) 
  108.      { 
  109.           if(isalpha(w[0])) 
  110.               root = addNode(root,w);                         
  111.      } 
  112.     tprint(root);   
  113.     treeFree(root);                             
  114.     fclose(f);                                     
  115.   }else{ 
  116.          printf("open %s error\n",fname);   
  117.  } 
  118.   getchar();     
  119.   return 0; 
  120. } 

相关内容