C - Word frequency counter

以你之姓@ 2022-11-15 11:35 101阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

/*
     * Write a program that prints the distinct words in its input sorted into 
     * decreasing order of frequency of occurrence. Precede each word by its count.
     *
     * WordFrequencyCounter.c - by FreeMan
     */
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <assert.h>
    
    typedef struct WORD
    {
        char *Word;
        size_t Count;
        struct WORD *Left;
        struct WORD *Right;
    } WORD;
    
    /*
      Assumptions: input is on stdin, output to stdout.
    
      Plan: read the words into a tree, keeping a count of how many we have,
            allocate an array big enough to hold Treecount (WORD *)'s
            walk the tree to populate the array.
            qsort the array, based on size.
            printf the array
            free the array
            free the tree
            free tibet (optional)
            free international shipping!
    */
    
    #define SUCCESS                      0
    #define CANNOT_MALLOC_WORDARRAY      1
    #define NO_WORDS_ON_INPUT            2
    #define NO_MEMORY_FOR_WORDNODE       3
    #define NO_MEMORY_FOR_WORD           4
    #define NONALPHA "1234567890 \v\f\n\t\r+=-*/\\,.;:'#~?<>|{}[]`!\"�$%^&()"
    
    int ReadInputToTree(WORD **DestTree, size_t *Treecount, FILE *Input);
    int AddToTree(WORD **DestTree, size_t *Treecount, char *Word);
    int WalkTree(WORD **DestArray, WORD *Word);
    int CompareCounts(const void *vWord1, const void *vWord2);
    int OutputWords(FILE *Dest, size_t Count, WORD **WordArray);
    void FreeTree(WORD *W);
    char *dupstr(char *s);
    
    int main(void)
    {
        int Status = SUCCESS;
        WORD *Words = NULL;
        size_t Treecount = 0;
        WORD **WordArray = NULL;
    
        /* Read the words on stdin into a tree */
        if (SUCCESS == Status)
        {
            Status = ReadInputToTree(&Words, &Treecount, stdin);
        }
    
        /* Sanity check for no sensible input */
        if (SUCCESS == Status)
        {
            if (0 == Treecount)
            {
                Status = NO_WORDS_ON_INPUT;
            }
        }
    
        /* Allocate a sufficiently large array */
        if (SUCCESS == Status)
        {
            WordArray = malloc(Treecount * sizeof * WordArray);
            if (NULL == WordArray)
            {
                Status = CANNOT_MALLOC_WORDARRAY;
            }
        }
    
        /* Walk the tree into the array */
        if (SUCCESS == Status)
        {
            Status = WalkTree(WordArray, Words);
        }
    
        /* Quick sort the array */
        if (SUCCESS == Status)
        {
            qsort(WordArray, Treecount, sizeof * WordArray, CompareCounts);
        }
    
        /* Walk down the WordArray outputting the values */
        if (SUCCESS == Status)
        {
            Status = OutputWords(stdout, Treecount, WordArray);
        }
    
        /* Free the word array */
        if (NULL != WordArray)
        {
            free(WordArray);
            WordArray = NULL;
        }
    
        /* Free the tree memory */
        if (NULL != Words)
        {
            FreeTree(Words);
            Words = NULL;
        }
    
        /* Error report and we are finshed */
        if (SUCCESS != Status)
        {
            fprintf(stderr, "Program failed with code %d\n", Status);
        }
        return (SUCCESS == Status ? EXIT_SUCCESS : EXIT_FAILURE);
    }
    
    void FreeTree(WORD *W)
    {
        if (NULL != W)
        {
            if (NULL != W->Word)
            {
                free(W->Word);
                W->Word = NULL;
            }
            if (NULL != W->Left)
            {
                FreeTree(W->Left);
                W->Left = NULL;
            }
            if (NULL != W->Right)
            {
                FreeTree(W->Right);
                W->Right = NULL;
            }
        }
    }
    
    int AddToTree(WORD **DestTree, size_t *Treecount, char *Word)
    {
        int Status = SUCCESS;
        int CompResult = 0;
    
        /* Safety check */
        assert(NULL != DestTree);
        assert(NULL != Treecount);
        assert(NULL != Word);
    
        /* Ok, either *DestTree is NULL or it isn't (deep huh?) */
        if (NULL == *DestTree)  /* This is the place to add it then */
        {
            *DestTree = malloc(sizeof **DestTree);
            if (NULL == *DestTree)
            {
                /* Horrible - we're out of memory */
                Status = NO_MEMORY_FOR_WORDNODE;
            }
            else
            {
                (*DestTree)->Left = NULL;
                (*DestTree)->Right = NULL;
                (*DestTree)->Count = 1;
                (*DestTree)->Word = dupstr(Word);
                if (NULL == (*DestTree)->Word)
                {
                    /* Even more horrible - we've run out of memory in the middle */
                    Status = NO_MEMORY_FOR_WORD;
                    free(*DestTree);
                    *DestTree = NULL;
                }
                else
                {
                    /* Everything was successful, add one to the tree nodes count */
                    ++ *Treecount;
                }
            }
        }
        else /* We need to make a decision */
        {
            CompResult = strcmp(Word, (*DestTree)->Word);
            if (0 < CompResult)
            {
                Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
            }
            else if (0 > CompResult)
            {
                Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
            }
            else
            {
                /* Add one to the count - this is the same node */
                ++(*DestTree)->Count;
            }
        }
    
        return Status;
    }
    
    int ReadInputToTree(WORD **DestTree, size_t *Treecount, FILE *Input)
    {
        int Status = SUCCESS;
        char Buf[8192] = { 0 };
        char *Word = NULL;
    
        /* Safety check */
        assert(NULL != DestTree);
        assert(NULL != Treecount);
        assert(NULL != Input);
    
        /* For every line */
        while (NULL != fgets(Buf, sizeof Buf, Input))
        {
            /* Strtok the input to get only alpha character words */
            Word = strtok(Buf, NONALPHA);
            while (SUCCESS == Status && NULL != Word)
            {
                /* Deal with this word by adding it to the tree */
                Status = AddToTree(DestTree, Treecount, Word);
    
                /* Next word */
                if (SUCCESS == Status)
                {
                    Word = strtok(NULL, NONALPHA);
                }
            }
        }
    
        return Status;
    }
    
    int WalkTree(WORD **DestArray, WORD *Word)
    {
        int Status = SUCCESS;
        static WORD **Write = NULL;
    
        /* Safety check */
        assert(NULL != Word);
    
        /* Store the starting point if this is the first call */
        if (NULL != DestArray)
        {
            Write = DestArray;
        }
    
        /* Now add this node and it's kids */
        if (NULL != Word)
        {
            *Write = Word;
            ++Write;
            if (NULL != Word->Left)
            {
                Status = WalkTree(NULL, Word->Left);
            }
            if (NULL != Word->Right)
            {
                Status = WalkTree(NULL, Word->Right);
            }
        }
    
        return Status;
    }
    
    /*
     * CompareCounts is called by qsort. This means that it gets pointers to the
     * data items being compared. In this case the data items are pointers too.
     */
    int CompareCounts(const void *vWord1, const void *vWord2)
    {
        int Result = 0;
        WORD *const *Word1 = vWord1;
        WORD *const *Word2 = vWord2;
    
        assert(NULL != vWord1);
        assert(NULL != vWord2);
    
        /* Ensure the result is either 1, 0 or -1 */
        if ((*Word1)->Count < (*Word2)->Count)
        {
            Result = 1;
        }
        else if ((*Word1)->Count > (*Word2)->Count)
        {
            Result = -1;
        }
        else
        {
            Result = 0;
        }
    
        return Result;
    }
    
    int OutputWords(FILE *Dest, size_t Count, WORD **WordArray)
    {
        int Status = SUCCESS;
        size_t Pos = 0;
    
        /* Safety check */
        assert(NULL != Dest);
        assert(NULL != WordArray);
    
        /* Print a header */
        fprintf(Dest, "Total Words : %lu\n", (unsigned long)Count);
    
        /* Print the words in descending order */
        while (SUCCESS == Status && Pos < Count)
        {
            fprintf(Dest, "%10lu %s\n", (unsigned long)WordArray[Pos]->Count, WordArray[Pos]->Word);
            ++Pos;
        }
    
        return Status;
    }
    
    
    /*
     * dupstr: Duplicate a string
     */
    char *dupstr(char *s)
    {
        char *Result = NULL;
        size_t slen = 0;
    
        /* Sanity check */
        assert(NULL != s);
    
        /* Get string length */
        slen = strlen(s);
    
        /* Allocate enough storage */
        Result = malloc(slen + 1);
    
        /* Populate string */
        if (NULL != Result)
        {
            memcpy(Result, s, slen);
            *(Result + slen) = '\0';
        }
    
        return Result;
    }
    
    // Output:
    /*
    These are short, famous texts in English from classic sources like the Bible or Shakespeare. Some texts have word definitions and explanations to help you. Some
     of these texts are written in an old style of English. Try to understand them, because the English that we speak today is based on what our great, great, great
    , great grandparents spoke before! Of course, not all these texts were originally written in English. The Bible, for example, is a translation. But they are all
     well known in English today, and many of them express beautiful thoughts.
    ^Z
    Total Words : 66
             5 English
             4 great
             4 texts
             4 in
             3 are
             3 of
             2 is
             2 today
             2 them
             2 written
             2 all
             2 the
             2 Bible
             2 these
             2 to
             2 Some
             2 and
             1 word
             1 definitions
             1 have
             1 explanations
             1 Shakespeare
             1 help
             1 you
             1 or
             1 like
             1 sources
             1 an
             1 old
             1 style
             1 Try
             1 understand
             1 classic
             1 because
             1 that
             1 we
             1 speak
             1 from
             1 famous
             1 based
             1 on
             1 what
             1 our
             1 short
             1 grandparents
             1 spoke
             1 before
             1 Of
             1 course
             1 not
             1 These
             1 were
             1 originally
             1 The
             1 for
             1 example
             1 a
             1 translation
             1 But
             1 they
             1 well
             1 known
             1 many
             1 express
             1 beautiful
             1 thoughts
    
    */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter