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-3を解いてみる。

その他参考書籍

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

演習 6-3.

コード

sample.c

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

struct linenums {
    int linenum;
    struct linenums *p;
};

struct tnode {
    char *word;
    struct linenums *nums;
    struct tnode *left;
    struct tnode *right;
};

#define MAXWORD 100
#define BUFSIZE 100
#define NOISEWORDN 10

struct tnode *addtree(struct tnode *, char *, int);
void addlinenum(struct tnode *, int);

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

int main()
{
    struct tnode *root;
    char word[MAXWORD];
    int linenum = 1;
    
    root = NULL;
    while (getword(word, MAXWORD) != EOF) {
        if(isalpha(word[0]) && !noiseword(word))
            root = addtree(root, word, linenum);
        else if (word[0] == '\n')
            linenum++;
    }
    treeprint(root);
    return 0;
}

struct tnode *addtree(struct tnode *p, char *w, int n)
{
    int cond;
    if (p == NULL) {
        p = talloc();
        p->word = strdup(w);
        p->nums = lalloc();
        p->nums->linenum = n;
        p->nums->p = NULL;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(w, p->word)) == 0)
        addlinenum(p, n);
    else if (cond < 0)
        p->left = addtree(p->left, w, n);
    else
        p->right = addtree(p->right, w, n);
    return p;
}

void addlinenum(struct tnode *p, int n)
{
    struct linenums *tmp;
    tmp = p->nums;
    while (tmp->linenum != n && tmp->p != NULL)
        tmp = tmp->p;
    if (tmp->linenum != n) {
        tmp->p = lalloc();
        tmp->p->linenum = n;
        tmp->p->p = NULL;
    }
}

void treeprint(struct tnode *p)
{
    struct linenums *tmp;
    if (p != NULL) {
        treeprint(p->left);
        printf("%-10s ", p->word);
        for (tmp = p->nums; tmp != NULL; tmp = tmp->p)
            printf("%d ", tmp->linenum);
        printf("\n"); 
        treeprint(p->right);
    }
}

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

struct linenums *lalloc(void)
{
    return (struct linenums *) malloc(sizeof(struct linenums));
}

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

int noiseword(char *word)
{
    char *nw[NOISEWORDN] = { "a", "A",
                             "an", "An",
                             "the", "The",
                             "and", "AND",
                             "i", "I"
                           };
    int i;
    
    for (i = 0; i < NOISEWORDN; i++)
        if (strcmp(word, nw[i]) == 0)
            return YES;
    return NO;
}

int getword(char *word, int lim)
{
    int c;
    char *w = word;
    
    while (isspace(c = getch()) && c != '\n')
        ;
    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)
{
    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.txt
Ah Love! could you and I with Fate conspire
To grasp this sorry Scheme of Things entire,
Would not we shatter it to bits -- and then
Re-mould it nearer to the Heart's Desire!
ah love! could you and i with fate conspire
to grasp this sorry scheme of things entire,
would not we shatter it to bits -- and then
re-mould it nearer to the heart's desire!
!@#$%Ah Love! could you and I with Fate conspire
!@#$%To grasp this sorry Scheme of Things entire,
!@#$%Would not we shatter it to bits -- and then
!@#$%Re-mould it nearer to the Heart's Desire!
!@#$%ah love! could you and i with fate conspire
!@#$%to grasp this sorry scheme of things entire,
!@#$%would not we shatter it to bits -- and then
!@#$%re-mould it nearer to the heart's desire!
$ cat sample.txt | ./a.out
Ah         1 9 
Desire     4 12 
Fate       1 9 
Heart      4 12 
Love       1 9 
Re         4 12 
Scheme     2 10 
Things     2 10 
To         2 10 
Would      3 11 
ah         5 13 
bits       3 7 11 15 
conspire   1 5 9 13 
could      1 5 9 13 
desire     8 16 
entire     2 6 10 14 
fate       5 13 
grasp      2 6 10 14 
heart      8 16 
it         3 4 7 8 11 12 15 16 
love       5 13 
mould      4 8 12 16 
nearer     4 8 12 16 
not        3 7 11 15 
of         2 6 10 14 
re         8 16 
s          4 8 12 16 
scheme     6 14 
shatter    3 7 11 15 
sorry      2 6 10 14 
then       3 7 11 15 
things     6 14 
this       2 6 10 14 
to         3 4 6 7 8 11 12 14 15 16 
we         3 7 11 15 
with       1 5 9 13 
would      7 15 
you        1 5 9 13 
$