C - 自己参照的構造体 (ノード、部分木、再帰)

プログラミング言語C 第2版 ANSI規格準拠
B.W. カーニハン D.M. リッチー (著)
石田 晴久 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: C
• Clang (コンパイラ)

プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)の第6章(構造体)、6.5(自己参照的構造体)、演習6-2を解いてみる。

その他参考書籍

• プログラミング言語Cアンサー・ブック 第2版 (クロビス・L．トンド、スコット・E．ギンペル(著)、矢吹 道郎(翻訳))

演習 6-2.

コード

sample.c

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

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

#define MAXWORD 100
#define BUFSIZE 100

struct tnode *addtree(struct tnode *, char *, int, int *);
void treeprint(struct tnode *);
struct tnode *talloc(void);
char *strdup(char *);
int cmp(struct tnode *, char *, int, int *);
int getword(char *word, int lim);
int getch(void);
void ungetch(int);
char buf[BUFSIZE];
int bufp = 0;
enum { NO, YES };

int main(int argc, char *argv[])
{
    /* テスト用の変数名 */
    int bbbbbb,
        bbbbbba,
        bbbbbbab,
        bbbbbbabc,
        bbbbbbabcd,
        bbbbbbabcde,
        a,
        aa,
        aaa,
        aaaa,
        aaaaa,
        aaaaaa,
        aaaaaab,
        aaaaaabc,
        aaaaaabcd,
        aaaaaabcde,
        aaaaaabcdef,
        bbbbbbaa,
        bbbbbbaaa,
        bbbbbbaab;
    aaaaaabcde = bbbbbbabcde = 10;
    
    struct tnode *root;
    char word[MAXWORD];
    int n;
    int found;
    root = NULL;
    n = atoi((++argv)[0] + 1);
    found = NO;
    while (getword(word, MAXWORD) != EOF) {
        if(isalpha(word[0]) && strlen(word) >= n)
            root = addtree(root, word, n, &found);
        found = NO;
    }
    treeprint(root);
    return 0;
}

struct tnode *addtree(struct tnode *p, char *w, int n, int *found)
{
    int cond;
    
    if (p == NULL) {
        p = talloc();
        p->word = strdup(w);
        p->match = *found;
        p->left = p->right = NULL;
    } else if ((cond = cmp(p, w, n, found)) < 0)
        p->left = addtree(p->left, w, n, found);
    else if (cond > 0)
        p->right = addtree(p->right, w, n, found);
    return p;
}

void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        if (p->match)
            printf("%s\n", p->word);
        treeprint(p->right);
    }
}

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

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

int cmp(struct tnode *p, char *w, int n, int *found)
{
    int i;
    char *s = p->word;
    for (i = 0; *w == *s; i++, w++, s++)
        if (*w == '\0')
            return 0;
    if (i >= n) {
        p->match = YES;
        *found = YES;
    }
    return *w - *s;
}

int getword(char *word, int lim)
{
    int c, d, e;
    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 (c == '/') 
        if ((d = getch()) == '*') {
            while (e = getch())
                if (e == '*')
                    if((e = getch()) == '/')
                        break;
                    else 
                        ungetch(e);
            c = e;
        } else
            ungetch(d);
    *w = '\0';
    return c;
}

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

入出力結果(Terminal)

$ cat sample.c | ./a.out -6
aaaaaa
aaaaaab
aaaaaabc
aaaaaabcd
aaaaaabcde
aaaaaabcdef
bbbbbb
bbbbbba
bbbbbbaa
bbbbbbaaa
bbbbbbaab
bbbbbbab
bbbbbbabc
bbbbbbabcd
bbbbbbabcde
$