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

その他参考書籍

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

演習 6-4.

コード

sample.c

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

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

#define MAXWORD 100
#define BUFSIZE 100

struct tnode *addtree(struct tnode *, char *);

struct tnode *talloc(void);
char *strdup(char *);
int getword(char *word, int lim);
int getch(void);
void ungetch(int);
void qsort(struct tnode *tnodes[], int, int);
void swap(struct tnode *tnodes[], int, int);
void append(struct tnode *, struct tnode *tnodes[]);
char buf[BUFSIZE];
int bufp = 0;
int n = 0;
enum { NO, YES };

int main()
{
    struct tnode *root;
    char word[MAXWORD];
    struct tnode *tnodes[1000];
    root = NULL;
    int i;
    
    while (getword(word, MAXWORD) != EOF)
        if(isalpha(word[0]))
            root = addtree(root, word);

    append(root, tnodes);

    qsort(tnodes, 0, n - 1);
    
    for (i = 0; i < n; i++)
        printf("%d %s\n", tnodes[i]->count, tnodes[i]->word);
    return 0;
}

void append(struct tnode *p, struct tnode *tnodes[])
{
    if (p != NULL) {
        append(p->left, tnodes);
        tnodes[n++] = p;
        append(p->right, tnodes);
    }
}

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
        p->right = addtree(p->right, w);
    return p;
}

void qsort(struct tnode *tnodes[], int left, int right)
{
    int i, last;
    if (left >= right)
        return;
    swap(tnodes, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++)
        if ((tnodes[i]->count - tnodes[left]->count) < 0)
            swap(tnodes, ++last, i);
    swap(tnodes, left, last);
    qsort(tnodes, left, last - 1);
    qsort(tnodes, last + 1, right);
}

void swap(struct tnode *tnodes[], int i, int j)
{
    struct tnode *tmp;
    
    tmp = tnodes[i];
    tnodes[i] = tnodes[j];
    tnodes[j] = tmp;
}

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 getword(char *word, int lim)
{
    int c;
    char *w = word;
    
    while (isspace(c = getch()))
        ;
    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
2 heart
2 i
2 Desire
2 Fate
2 Heart
2 I
2 love
2 Re
2 Ah
2 would
2 Love
2 Would
2 Scheme
2 desire
2 Things
2 To
2 re
2 fate
2 scheme
2 ah
2 things
4 mould
4 shatter
4 entire
4 sorry
4 nearer
4 the
4 of
4 then
4 s
4 you
4 conspire
4 this
4 grasp
4 we
4 not
4 with
4 could
4 bits
8 it
8 and
10 to
$ cat sample.c | ./a.out
1 isalnum
1 too
1 isspace
1 YES
1 main
1 characters
1 many
1 d
1 sizeof
1 getchar
1 stdio
1 break
1 strcmp
1 enum
1 strcpy
1 ctype
1 string
1 NO
1 strlen
2 isalpha
2 printf
2 malloc
2 define
2 while
2 EOF
3 j
3 cond
3 h
3 include
3 buf
3 BUFSIZE
3 for
3 getword
3 strdup
3 lim
3 talloc
3 MAXWORD
3 tmp
4 else
4 s
4 getch
4 ungetch
5 root
5 bufp
5 qsort
5 append
5 NULL
5 addtree
5 swap
6 last
6 count
6 n
8 return
8 c
10 right
12 if
12 void
12 word
12 w
14 char
14 left
15 i
22 struct
22 tnode
24 p
24 int
25 tnodes
$