Serendip

Web Studio

演習6-2

グループの情報をリストにして保持する。
リストの各要素は、グループ名、グループに属する tnode へのポインタの配列、グループに属する tnode の数、次のノードへのポインタで構成される。

始めに tnode によるツリーを作成し、そのツリーからグループリストを生成する。
グループリストの先頭ノードは印字の際のアクセスに利用するダミーノードとなっている。

コメントや文字列中の単語の排除は、演習6-1 のものを利用している。

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

#define MAXWORD 100
#define MAXGROUPWORD 100
#define BUFSIZE 100
#define DEFAULT_GROUP_NAME_LENGTH 6

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

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

struct gnode { /* グループのデータ */
    char *word; /* グループ名文字列 */
    struct tnode *list[MAXGROUPWORD]; /* 各 tnode へのポインタの配列 */
    int count; /* グループに属する tnode の数 */
    struct gnode *next; /* 次のノード */
};

struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
int skip_char(void);

enum boolean { FALSE, TRUE };
enum skipping_state { COMMENT_START, IN_COMMENT, COMMENT_END, IN_STR_C, OTHER };

struct gnode *addgroup(struct gnode *, struct tnode *);
struct gnode *append_list(struct gnode *root, struct tnode *p);
void gprint(struct gnode *);

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

int len = DEFAULT_GROUP_NAME_LENGTH;

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

    if (argc > 1) {
        len = atoi(argv[1]);
    }

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

    /* グループリストの先頭ノード */
    groot = galloc();
    groot->word = "";
    groot->list[0] = NULL;
    groot->count = 0;
    groot->next = NULL;

    addgroup(groot, root);
    gprint(groot);

    return 0;
}

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

/* addgroup : 木 p をグループ分け */
struct gnode *
addgroup(struct gnode *g, struct tnode *p)
{
    if (p != NULL) {
        addgroup(g, p->left);
        append_list(g, p);
        addgroup(g, p->right);
    }

    return g;
}

/* append_list : 対象ワードをグループリストに登録 */
struct gnode *
append_list(struct gnode *g, struct tnode *p)
{
    char *s;

    s = my_strdup(p->word);
    s[len] = '\0';

    if (g == NULL) {
        g = galloc();
        g->word = s;
        g->next = NULL;
        g->list[0] = p;
        g->count = 1;
    } else if (strncmp(g->word, p->word, len) == 0) {
        if (g->count < MAXGROUPWORD) {
            g->list[g->count] = p;
            g->count++;
        } else {
            fprintf(stderr, "too many word to regist\n");
        }
    } else {
        g->next = append_list(g->next, p);
    }
    return g;
}

/* gprint : グループリストを印字 */
void gprint(struct gnode *g)
{
    int i;

    if (g != NULL) {
        if (g->count > 1) {
            printf("%s\n", g->word);
            for (i = 0; i<g->count; i++) {
                printf("\t%s\n", g->list[i]->word);
            }
        }
        gprint(g->next);
    }
}

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

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

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

int skip_char(void)
{
    int c, getch(void);
    int escaped = FALSE;
    void ungetch(int);
    int type = OTHER;

    while ((c = getch()) != EOF) {
        switch (c) {
        case '/':
            if (type == OTHER) {
                type = COMMENT_START;
            } else if (type == COMMENT_END) {
                type = OTHER;
            }
            escaped = FALSE;
            break;
        case '*':
            if (type == COMMENT_START) {
                type = IN_COMMENT;
            } else if (type == IN_COMMENT) {
                type = COMMENT_END;
            }
            escaped = FALSE;
            break;
        case '"':
            if (!escaped) {
                if (type == OTHER) {
                    type = IN_STR_C;
                } else if (type == IN_STR_C) {
                    type = OTHER;
                }
            }
            escaped = FALSE;
            break;
        case '\\':
            if (type == IN_STR_C) {
                escaped = TRUE;
            }
            break;
        default:
            escaped = FALSE;
            break;
        }

        if (!isspace(c) && type == OTHER) {
            return c;
        }
    }
    return c;
}

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

    c = skip_char();

    if (c != EOF) {
        *w++ = c;
    }
    if (!isalpha(c)) {
        *w = '\0';
        return c;
    }
    for ( ; --lim > 0; w++) {
        if (!isalnum(*w = getch()) && *w != '_') {
            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;
}

実行結果

$ ./gcount 4 <gcount.c
COMM
        COMMENT_END
        COMMENT_START
getc
        getch
        getchar
isal
        isalnum
        isalpha
skip
        skip_char
        skipping_state
strc
        strcmp
        strcpy

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

posted with amazlet at 09.11.27

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

Amazon.co.jp で詳細を見る