C //练习 6-4 编写一个程序，根据单词的出现频率按降序打印输入的各个不同单词，并在每个单词的前面标上它的出现次数。

C程序设计语言 （第二版） 练习 6-4

练习 6-4 编写一个程序，根据单词的出现频率按降序打印输入的各个不同单词，并在每个单词的前面标上它的出现次数。

注意：代码在win32控制台运行，在不同的IDE环境下，有部分可能需要变更。

IDE工具：Visual Studio 2010

?

代码块：

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

#define MAXWORD 1000
#define BUFSIZE 100
#define IN 1
#define OUT 0

char buf[BUFSIZE];
int bufp = 0;

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

struct wnode {
    int number;
    struct words *words;
    struct wnode *left;
    struct wnode *right;
};

struct words {
    char *word;
    struct words *next;
};

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

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

int getword(char *word, int lim){
    int c;
    char *w = word;
    static int lineBeginning = 1; 
    static int afterSlash = 0;
    int afterStar = 0;

    if(isspace(c = getch())){
        afterSlash = 0;
	}
    while(isspace(c)){
        if(c == '\n'){
            lineBeginning = 1;
		}
        c = getch();
    }

    if(c != EOF){
        *w++ = c;
	}

    if(c == '#' && lineBeginning == 1){
        while((c = getch()) != '\n' && c != EOF)
            ;
        return getword(word, lim);
    }
    lineBeginning = 0;

    if(c == '\\'){
        afterSlash = afterSlash ? 0 : 1;
	}
    else if(c == '/' ){
        if((c = getch()) == '*' && !afterSlash){
            while((c = getch()) != EOF){
                if(c == '/'){
                    if(afterStar){
                        return getword(word, lim);
					}
                }
                else if(c == '*' && !afterSlash){
                    afterStar = 1;
				}
                else if(c == '\\'){
                    afterSlash = afterSlash ? 0 : 1;
				}
                else{
                    afterStar = 0;
                    afterSlash = 0;
                }
            }
        }

        afterSlash = 0;
        if(c != EOF){
            ungetch(c);
		}
    }

    else if(c == '\"'){
        if(!afterSlash){
            --w;
            while((c = getch()) != EOF){
                if(c == '\"' && !afterSlash){
                    break;
				}
                else if(c == '\\'){
                    afterSlash = afterSlash ? 0 : 1;
				}
                else{
                    afterSlash = 0;
				}
                *w++ = c;
            }
            *w = '\0';
            if(c == EOF){
                return EOF;
			}
            else{
                return getword(word, lim);
			}
        }
        afterSlash = 0;
    }

    if(!isalpha(c) && c != '_'){
        *w = '\0';
        if(c != '\\'){
            afterSlash = 0;
		}
        return c;
    }

    afterSlash = 0;

	for( ; --lim > 0; ++w){
        if(!isalnum(*w = getch()) && *w != '_'){
            ungetch(*w);
            break;
        }
	}
    *w = '\0';
    return word[0];
}

struct tnode *talloc(void) {
    return (struct tnode *)malloc(sizeof(struct tnode));
}

struct wnode *numwordalloc(void) {
    return (struct wnode *)malloc(sizeof(struct wnode));
}

struct words *wordsalloc(void) {
    return (struct words *)malloc(sizeof(struct words));
}

char *_strdup(char *s) {
    char *p;
    p = (char *)malloc(strlen(s) + 1);
    if(p != NULL){
        strcpy(p, s);
	}
    return p;
}

void printwords(const struct words* w, const int count) {
    if (w != NULL) {
        printf("%4d\t%s\n", count, w->word);
        w = w->next;
    }
}

void treeprint(const struct wnode *p) {
    if(p != NULL){
        treeprint(p->left);
        printwords(p->words, p->number);
        treeprint(p->right);
    }
}

struct tnode *addtree(struct tnode *p, char *w) {
    int cond;

    if(p == NULL){
        p = talloc();
        p->word = _strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    }
    else if((cond = strcmp(w, p->word)) == 0){
        p->count++;
	}
    else if(cond < 0){
        p->left = addtree(p->left, w);
	}
    else{
        p->right = addtree(p->right, w);
	}
    return p;
}

struct words *addword(struct words* list, char *w) {
    if(list == NULL){
        list = wordsalloc();
        list->word = _strdup(w);
        list->next = NULL;
    } 
	else{
        list->next = addword(list->next, w);
    }
    return list;
}

struct wnode *addwtree(struct wnode *p, int count, char* w) {
    if(p == NULL){
        p = numwordalloc();
        p->number = count;
        p->words = NULL;
        p->words = addword(p->words, w);
    }
	else if(count > p->number){
        p->left = addwtree(p->left, count, w);
	}
    else{
        p->right = addwtree(p->right, count, w);
	}
    return p;
}

struct wnode *traverse(const struct tnode *p, struct wnode *q) {
    if(p != NULL){
        q = traverse(p->left, q);
        q = addwtree(q, p->count, p->word);
        q = traverse(p->right, q);
    }
    return q;
}

int main() {
    struct tnode *root;
    struct wnode *wroot;

    char word[MAXWORD];

    root = NULL;
    wroot = NULL;

    while(getword(word, MAXWORD) != 'x')
        if(isalpha(word[0]))
            root = addtree(root, word);

    wroot = traverse(root, wroot);
    treeprint(wroot);
    return 0;
}