演習6-3 K&R プログラミング言語C

演習6-3

行番号のリストを構造体 lines として定義した。
tnode に行番号リストへのポインタを追加する。

ただ、lines 中の pword を使ってないので、相互参照になっていないような・・・。

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

#define MAXWORD 100
#define MAXNLINES 1024
#define BUFSIZE 100

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

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

struct lines {
    struct tnode *pword;      /* 対象文字列のノードへのポインタ */
    int number[MAXNLINES];    /* 行番号の配列 */
    int count;                /* 行番号の数、(numberの長さ) */
};

struct tnode *addtree(struct tnode *, char *, int);
struct lines *addline(struct tnode *, struct lines *, int);
void treeprint(struct tnode *);
void linesprint(struct lines *);
int is_noize_word(char *);
char *tolower_str(char *);
int getword(char *, int);
int num_of_line = 1;

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

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

    return 0;
}

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

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

    if (p == NULL) {  /* 新しい単語がきた */
        p = talloc(); /* 新しいノードをつくる */
        p->word = my_strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
        p->lines = addline(p, NULL, nline);
    } else if ((cond = strcmp(w, p->word)) == 0) {
        p->count++;         /* 繰り返された単語 */
        addline(p, p->lines, nline);
    } else if (cond < 0) {  /* より小さければ、左部分木へ */
        p->left = addtree(p->left, w, nline);
    } else { /* 大きければ、右部分木へ */
        p->right = addtree(p->right, w, nline);
    }
    return p;
}

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

/* addline : 行番号リストに行番号を追加する */
struct lines *addline(struct tnode *p, struct lines *l, int nline)
{
    if (l == NULL) {  /* 新しい行番号リスト */
        l = lalloc();
        l->pword = p;
        l->number[0] = nline;
        l->count = 1;
    } else if (l->number[l->count-1] != nline) { /* 配列最後の数字が nline と等しければ (すでに行番号が登録されていれば) */
        l->number[l->count++] = nline;
    }
    return l;
}

/* linesprint : 行番号リストを順序立てて印字 */
void linesprint(struct lines *l)
{
    int i;

    printf("\tLINES : ");
    for (i=0; i<l->count; i++) {
        printf("%d%s", l->number[i], (i == l->count-1) ? "" : ", ");
    }
    printf("\n");
}

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

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

/* ノイズ単語かどうかをチェックする */
int is_noize_word(char *word)
{
    int i;
    char *noize_word[] = { "the", "and", "be", "is", "are", "am", "were", "in", "on", "of", "a" };
    int len = sizeof noize_word/sizeof noize_word[0];

    for (i = 0; i<len; i++) {
        if (strcmp(tolower_str(word), noize_word[i]) == 0) {
            return 0;
        }
    }
    return 1;
}

/* 文字列を小文字にする */
char *tolower_str(char *str)
{
    char *p = str;

    while (*str) {
        *str = tolower(*str);
        str++;
    }
    return p;
}

/* 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;
}

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

    while (isspace(c = getch())) {
        if (c == '\n')
            num_of_line++;
    }
    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;
}

実行結果

$ ./word_count <sample.txt
   2 above
        LINES : 8, 21
  11 after
        LINES : 12, 13, 22, 25, 26, 27
   2 all
        LINES : 27, 30
   1 also
        LINES : 17
   1 appear
        LINES : 10
以下略 ...
プログラミング言語C 第2版 ANSI規格準拠
B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726
«
»