Serendip

Web Studio

演習6-4

単語の発生頻度順に単語リストを保存するツリーを作成する構造体 freq を定義する。
tnode から freq へデータをコピーして freq を印字する。

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

#define MAXWORD 100
#define BUFSIZE 100

char buf[BUFSIZE];  /* ungetch 用のバッファ */
int bufp = 0;       /* buf 中の次の空き位置 */

struct tnode {           /* 木のノード */
    char *word;          /* テキストへのポインタ */
    int count;           /* 出現回数 */
    struct tnode *left;  /* 左の子供 */
    struct tnode *right; /* 右の子供 */
};

struct freq {               /* 単語の発生頻度順のノード */
    char *(word[MAXWORD]);  /* 単語リスト配列へのポインタ */
    int word_count;         /* 単語リストのサイズ */
    int count;              /* 単語の発生頻度数 */
    struct freq *left;      /* 左の子ノード */
    struct freq *right;     /* 右の子ノード */
};

struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
struct freq *falloc(void);
struct freq *tnode_cp_to_freq(struct tnode *, struct freq *);
struct freq *word_cp_to_freq(struct tnode *, struct freq *);
void freqprint(struct freq *);

/* 単語の頻度カウント */
int main(void)
{
    struct tnode *root;
    struct freq *frequency;
    char word[MAXWORD];

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

    frequency = NULL;
    frequency = tnode_cp_to_freq(root, frequency);
    freqprint(frequency);

    return 0;
}

struct tnode *talloc(void);
char *my_strdup(char *);

/* addtree : p の位置あるいはその下に w のノードを加える */
struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;

    if (p == NULL) {  /* 新しい単語がきた */
        p = talloc(); /* 新しいノードをつくる */
        p->word = my_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;
}

/* treeprint : 木 p を順序立てて印字 */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

/* talloc : tnode をつくる */
struct tnode *talloc(void)
{
    return (struct tnode *) malloc(sizeof(struct tnode));
}

/* my_strdup : s の複製をつくる */
char *my_strdup(char *s)
{
    char *p;

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

/* tnode を freq へコピーする */
struct freq *
tnode_cp_to_freq(struct tnode *p, struct freq *f)
{
    if (p != NULL) {
        tnode_cp_to_freq(p->left, f);
        f = word_cp_to_freq(p, f);
        tnode_cp_to_freq(p->right, f);
    }
    return f;
}

/* word を f に追加する */
struct freq *
word_cp_to_freq(struct tnode *p, struct freq *f)
{
    if (f == NULL) { /* 新しい単語がきた */
        f = falloc();
        f->word[0] = p->word;
        f->word_count = 1;
        f->count = p->count;
        f->left = f->right = NULL;
    } else if (f->count == p->count) { /* 等しければ、単語を追加 */
        f->word[f->word_count] = p->word;
        f->word_count++;
    } else if (f->count < p->count) { /* 小さければ、左部分木へ */
        f->left = word_cp_to_freq(p, f->left);
    } else { /* 大きければ、右部分木へ */
        f->right = word_cp_to_freq(p, f->right);
    }
    return f;
}

void freqprint(struct freq *f)
{
    int i;

    if (f != NULL) {
        freqprint(f->left);
        printf("%4d", f->count);
        for (i=0; i<f->word_count; i++) {
            printf(" %s", f->word[i]);
        }
        printf("\n");
        freqprint(f->right);
    }
}

/* falloc : freq をつくる */
struct freq *falloc(void)
{
    return (struct freq *) malloc(sizeof(struct freq));
}

/* getword : 入力から次の語または文字を求める */
int getword(char *word, int lim)
{
    int c, getch(void);
    void ungetch(int);
    char *w = word;

    while (isspace(c = getch()))
        ;
    if (c != EOF) {
        *w++ = c;
    }
    if (!isalpha(c)) {
        *w = '\0';
        return c;
    }
    for ( ; --lim > 0; w++) {
        if (!isalnum(*w = getch())) {
            ungetch(*w);
            break;
        }
    }
    *w = '\0';
    return word[0];
}

int getch(void) /* (押し戻された可能性もある) 1文字をとってくる */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* 文字を入力に押し戻す */
{
    if (bufp > BUFSIZE)
        fprintf(stderr, "ungetch : too many characters\n");
    else
        buf[bufp++] = c;
}

プログラミング言語C 第2版 ANSI規格準拠

posted with amazlet at 09.11.27

B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726

Amazon.co.jp で詳細を見る