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.4(構造体へのポインタ)、6.5(自己参照的構造体)、演習6-4を解いてみる。

その他参考書籍

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

演習 6-4.

コード

sample.c

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

#define MAXWORD 100
#define MAXNODES 1000

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

struct tnode *ptr[MAXNODES];
int nodes = 0;

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

int main(int argc, char *argv[])
{
    struct tnode *root;
    char word[MAXWORD];
    int i;
    
    root = NULL;
    while (getword(word, MAXWORD) != EOF) {
        if (isalpha(word[0])) {
            root = addtree(root, word);
        }
    }
    store_node(root);
    sort_tnodes();
    for (i = 0; i < nodes; i++) {
        printf("%d: %s\n", ptr[i]->count, ptr[i]->word);
    }
    return 0;
}

struct tnode *talloc(void);

struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;
    
    if (p == NULL) {
        p = talloc();
        p->word = 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 if(cond > 0) {
        p->right = addtree(p->right, w);
    }
    return p;
}

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

void store_node(struct tnode *p)
{
    if (p != NULL) {
        store_node(p->left);
        if (nodes < MAXNODES) {
            ptr[nodes++] = p;
        }
        store_node(p->right);
    }
}

void sort_tnodes(void)
{
    int gap, i, j;
    struct tnode *tmp;
    
    for (gap = nodes / 2; gap > 0; gap /=2) {
        for (i = gap; i < nodes; i++) {
            for (j = i - gap; j >= 0; j -= gap) {
                if ((ptr[j]->count) >= (ptr[j + gap]->count)) {
                    break;
                }
                tmp = ptr[j];
                ptr[j] = ptr[j + gap];
                ptr[j + gap] = tmp;
            }
        }
    }
}

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

#define BUFSIZE 100

char buf[BUFSIZE];
int bufp = 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)

$ curl http://www.example.com | ./a.out
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100  1270  100  1270    0     0   2021      0 --:--:-- --:--:-- --:--:--  3060
5: width
4: html
4: color
4: a
4: body
4: div
4: p
3: background
3: px
3: auto
3: em
3: padding
3: meta
3: margin
3: text
2: style
2: type
2: http
2: title
2: border
2: utf
2: Example
2: Domain
2: in
2: Helvetica
2: for
2: radius
2: domain
2: content
2: head
2: examples
2: h1
2: charset
1: Neue
1: doctype
1: coordination
1: asking
1: example
1: font
1: be
1: Sans
1: Open
1: You
1: Arial
1: Content
1: iana
1: information
1: More
1: is
1: initial
1: This
1: equiv
1: may
1: media
1: device
1: name
1: none
1: or
1: org
1: illustrative
1: href
1: permission
1: prior
1: css
1: decoration
1: sans
1: scale
1: serif
1: documents
1: domains
1: this
1: max
1: to
1: established
1: use
1: used
1: family
1: viewport
1: visited
1: link
1: without
1: www
$