统计文件中每个单词的出现次数

统计文件中每个单次的出现次数是C语言经典案例之一,当然如果你对shell编程比较精通的话,也可以直接用shell语句统计出来。

本文阐述的是用C语言实现单词统计,应用的数据结构为二叉树,所以需要读者十分了解二叉树的基本性质,回归代码需求,平衡二叉树拥有很高的查找效率,此外树型结构的插入效率也至关重要,对于二叉树插入和平衡操作是“先插入最后做平衡”还是“边插入边做平衡”,我曾经对比过二者的实际效率,处理的文件是上千万行的文本数据,通过计算二者的处理时间来对比二者的效率,最后得到的结论是“边插入边做平衡”的效率比“先插入最后做平衡”高了几十倍。究其缘由,边插入边作平衡降低了后续数据插入的时间,从而使二叉树始终为平衡二叉树,因为平衡二叉树拥有很高的查找效率。

本文二叉树的实现和平衡原理源自于机械工业出版社的《数据结构原书第二版》,教材将二叉树的平衡分为四种:左单旋、左双旋、右单旋、右双旋,而经实际测试表明:上述四种平衡方法拥有很高的代码效率,其中的实现原理不再赘述。

选择好应用的数据结构后,一个切实的问题摆在面前:如何一个单词一个单词的读取文件的内容?方法可能有很多种,但是哪种效率又是最高的呢?这也是曾经困扰我的问题,其实越是编程的小细节越考验开发人员的基本功,所以说平时多看书、多学习、多实践是提高自身水平的不二法则。言归正传,因为单词与单词中间仅仅是一个空格(或若干个空格),而读取单词也应该是一个连续的过程,所以应该在一个循环中不断读取单词,而且每次跳过间隔符(空格、回车、TAB键)继续读取下一个单词,直到读取到文件尾为止,可能有很多中实现方法,但是通常我还是习惯用fscanf,因为fscanf可以自动跳过间隔符继续读取下个内容,代码如下

    char word[WORDSIZE];

    while(fscanf(fp, "%s", word) != EOF)
    {
        ...
    }

这样每次读取的单词便存储在了word中,能够自动跳过间隔符继续读取内容是选择函数的关键。

-------------------------------------------------------------------------------------------------------------------------

具体代码如下

#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #define handle_error(msg) {perror(msg);exit(EXIT_FAILURE);} struct tnode {     char *word;     int count;     int height; //record node's height     struct tnode *left;     struct tnode *right; }; int max(int a, int b) {     if(a >= b)         return a;     return b; } int height_tree(struct tnode *root) {     if(root == NULL)         return -1;     else         return root->height; } struct tnode *sing_rotate_with_left(struct tnode *p2) {     struct tnode *p1;     p1 = p2->left;     p2->left = p1->right;     p1->right = p2;     p2->height = max(height_tree(p2->left), height_tree(p2->right)) + 1;     p1->height = max(height_tree(p1->left), height_tree(p1->right)) + 1;        return p1; } struct tnode *sing_rotate_with_right(struct tnode *p2) {     struct tnode *p1;     p1 = p2->right;     p2->right = p1->left;     p1->left = p2;     p2->height = max(height_tree(p2->left), height_tree(p2->right)) + 1;     p1->height = max(height_tree(p1->left), height_tree(p1->right)) + 1;     return p1; } struct tnode *double_rotate_with_left(struct tnode *p) {     p->left = sing_rotate_with_right(p->left);     return sing_rotate_with_left(p); } struct tnode *double_rotate_with_right(struct tnode *p) {     p->right = sing_rotate_with_left(p->right);     return sing_rotate_with_right(p); } struct tnode *insert_balance(struct tnode *root, char *word) {     int    result;     if(root == NULL)     {         root = (struct tnode *)malloc(sizeof(struct tnode));         if(root == NULL)             handle_error("malloc()->root");         root->word = strdup(word);//strdup实现原理:p = malloc; p = word; return p;         //root->word = word;    //此时root->word与word均指向同一地址,而其中内容为最后一次fscanf获得的字符串         root->count = 1;         root->height = 0;         root->left = NULL;         root->right = NULL;     }     else if((result = strcmp(word, root->word)) == 0)//若上面写成root->word = word;则每次判断时,此条件恒定成立,造成程序错误     {         root->count++;     }     else if(result < 0)     {         root->left = insert_balance(root->left, word);         if(height_tree(root->left) - height_tree(root->right) == 2)         {             if(strcmp(word, root->left->word) < 0)                 root = sing_rotate_with_left(root);             else                 root = double_rotate_with_left(root);         }     }     else     {         root->right = insert_balance(root->right, word);         if(height_tree(root->right) - height_tree(root->left) == 2)         {             if(strcmp(word, root->right->word) > 0)                 root = sing_rotate_with_right(root);             else                 root = double_rotate_with_right(root);         }     }     root->height = max(height_tree(root->left), height_tree(root->right)) + 1;     return root; } void travel_tree(struct tnode *root) {     if(root != NULL)     {         travel_tree(root->left);         printf("%s\t%d\n", root->word, root->count);         travel_tree(root->right);     } } void destroy_tree(struct tnode *root) {     if(root == NULL)         return ;     destroy_tree(root->left);     destroy_tree(root->right);     free(root); } static void draw_tree(struct tnode *root, int level) {     int i;     if(root == NULL)         return ;     draw_tree(root->right, level+1);     for(i = 0; i < level; i++)         printf("    ");     printf("%s %d\n", root->word, root->count);     draw_tree(root->left, level+1); } int main(int argc, char *argv[]) {     FILE *fp;     char word[1024];//注意字符字符数组的大小     struct tnode *root = NULL;     if(argc < 2)     {         printf("Usage: %s <filename>\n", argv[0]);         exit(EXIT_FAILURE);     }     fp = fopen(argv[1], "r");     if(fp == NULL)         handle_error("fopen()");     while(fscanf(fp, "%s", word) != EOF)     {         root = insert_balance(root, word);     }     travel_tree(root); //  draw_tree(root, 0);     destroy_tree(root);     fclose(fp);     return 0; }

相关文章
相关标签/搜索