统计输入中所有单词出现的次数

/* 程序功能：统计输入中所有单词的出现次数
 * 创建时间：2015-01-30
 * 作者：elijah
 * 思路：
 * 用二叉树构造：
 * 每个不同的单词在树中都是一个节点，每个节点包含：
 * （1）一个指向该单词内容的指针
 * （2）一个统计出现次数的计数值
 * （3）一个指向左子树的指针
 * （4）一个指向右子树的指针
 * 任何节点最多拥有两个子树，也可能只有一个或一个都没有
 * 对节点的所有操作保证，任何节点的左子树只包含按字典序小于
 * 该节点中单词的那些单词，右子树只包含按字典序大于该节点
 * 中单词的那些单词。*/

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define MAXWORD    100
#define BUFFSIZE 100

struct _tnode_ *talloc(void);
struct _tnode_ *addtree(struct _tnode_ *, char *);
char *mystrdup(char *s);
void treeprint(struct _tnode_ *);
int getword(char *, int);
int comment(void);
int getch(void);
void ungetch(int);

struct _tnode_ {
    char *word;
    int count;
    struct _tnode_ *left;
    struct _tnode_ *right;
};

char buff[BUFFSIZE];
int bufp = 0;

/* word frequency count */
int main()
{
    struct _tnode_ *root;
    char word[MAXWORD];

    while (EOF != getword(word, MAXWORD)) {
        if (isalpha(word[0]))
            root = addtree(root, word);
    }
    treeprint(root);

    return 0;
}

int getch(void)
{
    return (bufp > 0)? buff[--bufp] : getchar();
}

void ungetch(int c)
{
    if (bufp >= BUFFSIZE)
        printf("ungetch: too many characters\n");
    else
        buff[bufp++] = c;
}

int getword(char *word, int lim)
{
    int c, d;
    char *w = word;

    while (isspace(c = getch()));

    if (c != EOF)
        *w++ = c;
    if (isalpha(c) || c == '_' || c == '#') {
        for (; --lim > 0; w++) {
            if (!isalnum(*w = getch()) && *w != '_') {
                ungetch(*w);
                break;
            }
        }
    } else if (c == '\'' || c == '"') {
        for (; --lim > 0; w++) {
            if ((*w = getch()) == '\\')
                *++w = getch();
            else if (*w == c) {
                w++;
                break;
            } else if (*w == EOF)
                break;
        }
    } else if (c == '/') {
        if ((d = getch()) == '*')
            c =  comment();
        else
            ungetch(d);
    }
    *w = '\0';
    return c;
}

/* comment: skip over comment and return a character */
int comment(void)
{
    int c;

    while (EOF != (c = getch())) {
        if (c == '*') {
            if ((c = getch()) == '/')
                break;
            else
                ungetch(c);
        }
    }
    return c;
}

char *mystrdup(char *s)
{
    char *p;

    p = (char *)malloc(strlen(s) + 1);        /* +1 for '\0' */
    if (NULL != p)
        strcpy(p, s);

    return p;
}

/* addtree: add a node with w, at or below p */
struct _tnode_ *addtree(struct _tnode_ *p, char *w)
{
    int cond;

    if (NULL == p) {                /* a new word has arrived */
        p = talloc();                /* make a new node */
        p->word = mystrdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(w, p->word)) == 0)
        p->count++;
    else if (cond < 0)                /* less than into left subtree */
        p->left = addtree(p->left, w);
    else                           /* greater than into right subtree */
        p->right = addtree(p->right, w);

    return p;
}
				
					
						
							点击(此处)折叠或打开
						
					
					
						/* treeprint: in-order print of tree p */
void treeprint(struct _tnode_ *p)
{
    if (NULL != p) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

/* make a tnode */
struct _tnode_ *talloc(void)
{
    return (struct _tnode_ *)malloc(sizeof(struct _tnode_));
}