===============================================================================

                                                     2002 年 05 月 09 日（木）

            2002 年度「応用数理Ｃ３」「計算数学１」

                                                                    岩瀬順一

===============================================================================

== 020515a.c ==

/******************************************************************************

    ファイルからリストにデータを読み込む

ファイル名はコマンドラインで指定する。ファイルは一行につきデータ一つであり、
文字列と数値の間はタブ（一つとは限らない）で区切られているとする。
******************************************************************************/

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

#define OK 1
#define YES 1
#define NO 0

struct data {       /* Data 型を定義 */
    char *string;       /* 文字列データ */
    int number;         /* 数値データ */
    struct data *next;  /* 次へのポインタ */
};

typedef struct data Data;       /* struct data を Data と呼ぶ */

#define BUFSIZE 1024    /* バッファの大きさ */

int Data_add(Data *head, FILE *in);
Data *Data_construct(FILE *in);
void Data_printlist(Data *head);
void Data_print(Data *p);

int main(int argc, char *argv[]) {
    Data head;                          /* 先頭（ダミー） */
    FILE *in;

    if (argc != 2) {
        fprintf(stderr, "引数の数が違います.\n");
        return 1;
    }
    in = fopen(argv[1], "rt");
    if (in == NULL) {
        fprintf(stderr, "ファイル \"%s\" を開けません.\n", argv[1]);
        return 1;
    }
    head.next = NULL;
    while (Data_add(&head, in) == OK) {
        ;
    }
    Data_printlist(&head);
    return 0;
}


/* in から一行を読み込んで Data を作り、ダミーのヘッド head の次に追加 */
int Data_add(Data *head, FILE *in) {
    Data *tmp;

    tmp = Data_construct(in);
    if (tmp == NULL) {
        return NO;
    }
    tmp->next = head->next; head->next = tmp;
    return OK;
}


/* in から一行を読み込んで Data 型オブジェクトを作り、そのアドレスを返す */
Data *Data_construct(FILE *in) {
    int j;
    Data *p;
    static char buf[BUFSIZE+1];             /* バッファ */

    if ((p = malloc(sizeof(Data))) == NULL) {
        return NULL;
    }

    if (fgets(buf, BUFSIZE, in) == NULL) {
        free(p); return NULL;               /* 読み込めなかった場合 */
    }
    for (j=0; buf[j] != '\t'; j++) {        /* タブをさがす */
        ;
    }
    if ((p->string = malloc(j+1)) == NULL) {
        free(p); return NULL;
    }
    buf[j] = '\0';
    strcpy(p->string, buf);                 /* 文字列をコピー */
    while (buf[++j] == '\t') {              /* タブをスキップ */
        ;
    }
    p->number = atoi(buf+j);                /* 数値データを読み込む */
                                            /* next は初期化せず */
    return p;
}


/* ダミーのヘッド head から始まるリストを印字 */
void Data_printlist(Data *head) {
    Data *p;

    for (p = head->next; p != NULL; p = p->next) {
        Data_print(p);
    }
}


/* Data 型オブジェクト *p を印字 */
void Data_print(Data *p) {
    printf("%s\t%d\n", p->string, p->number);
}

== 020515b.c ==

/******************************************************************************

    ファイルからリストにデータを読み込み、検索する

ファイル名はコマンドラインで指定する。ファイルは一行につきデータ一つであり、
文字列と数値の間はタブ（一つとは限らない）で区切られているとする。
******************************************************************************/

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

#define OK 1
#define YES 1
#define NO 0

struct data {       /* Data 型を定義 */
    char *string;       /* 文字列データ */
    int number;         /* 数値データ */
    struct data *next;  /* 次へのポインタ */
};

typedef struct data Data;       /* struct data を Data と呼ぶ */

#define BUFSIZE 1024    /* バッファの大きさ */

int Data_add(Data *head, FILE *in);
Data *Data_construct(FILE *in);
Data *Data_listsearchstring(Data *head, char* s);
int Data_stringcmp(Data *p, char *s);
void Data_print(Data *p);

int main(int argc, char *argv[]) {
    Data head;                          /* 先頭（ダミー） */
    Data *p;
    FILE *in;

    if (argc != 3) {
        fprintf(stderr, "引数の数が違います.\n");
        return 1;
    }
    in = fopen(argv[1], "rt");
    if (in == NULL) {
        fprintf(stderr, "ファイル \"%s\" を開けません.\n", argv[1]);
        return 1;
    }
    head.next = NULL;
    while (Data_add(&head, in) == OK) {
        ;
    }
    p = Data_listsearchstring(&head, argv[2]);  /* argv[2] を探す */
    if (p == NULL) {
        printf("見つかりません.\n");
    } else {
        Data_print(p);
    }
    return 0;
}


/* in から一行を読み込んで Data を作り、ダミーのヘッド head の次に追加 */
int Data_add(Data *head, FILE *in) {
    Data *tmp;

    tmp = Data_construct(in);
    if (tmp == NULL) {
        return NO;
    }
    tmp->next = head->next; head->next = tmp;
    return OK;
}


/* in から一行を読み込んで Data 型オブジェクトを作り、そのアドレスを返す */
Data *Data_construct(FILE *in) {
    int j;
    Data *p;
    static char buf[BUFSIZE+1];         /* バッファ */

    if ((p = malloc(sizeof(Data))) == NULL) {
        return NULL;
    }

    if (fgets(buf, BUFSIZE, in) == NULL) {
        free(p); return NULL;           /* 読み込めなかった場合 */
    }
    for (j=0; buf[j] != '\t'; j++) {    /* タブをさがす */
        ;
    }
    if ((p->string = malloc(j+1)) == NULL) {
        free(p); return NULL;
    }
    buf[j] = '\0';
    strcpy(p->string, buf);             /* 文字列をコピー */
    while (buf[++j] == '\t') {          /* タブをスキップ */
        ;
    }
    p->number = atoi(buf+j);            /* 数値データを読み込む */
                                        /* next は初期化せず */
    return p;
}


/* ダミーのヘッド head から始まるリストから s を検索 */
Data *Data_listsearchstring(Data *head, char* s) {
    Data *p;

    for (p = head->next; p != NULL; p = p->next) {
        if (strcmp(p->string, s) == 0) {
            return p;
        }
    }
    return NULL;
}


/* Data 型オブジェクト *p の string と文字列 s を比較。一致すれば 0 */
int Data_stringcmp(Data *p, char *s) {
    return strcmp(p->string, s);
}


/* Data 型オブジェクト *p を印字 */
void Data_print(Data *p) {
    printf("%s\t%d\n", p->string, p->number);
}

== 020515c.c ==

/******************************************************************************

    リストへのデータの追加・リストからのデータの削除

******************************************************************************/

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

#define OK 1
#define YES 1
#define NO 0

struct data {       /* Data 型を定義 */
    char *string;       /* 文字列データ */
    int number;         /* 数値データ */
    struct data *next;  /* 次へのポインタ */
};

typedef struct data Data;       /* struct data を Data と呼ぶ */

#define BUFSIZE 1024    /* バッファの大きさ */

int Data_add(Data *head, FILE *in);
Data *Data_construct(FILE *in);
int Data_delete(Data *head, Data *p);
void Data_destruct(Data *p);
Data *Data_listsearchstring(Data *head, char* s);
int Data_stringcmp(Data *p, char *s);
void Data_printlist(Data *head);
void Data_print(Data *p);

int main() {
    Data head;                          /* 先頭（ダミー） */
    static char buf[BUFSIZE+1];

    head.next = NULL;

    do {
        printf("> ");                   /* プロンプト */
        fgets(buf, BUFSIZE, stdin);     /* ユーザがキーボード入力 */
        if (buf[0] == 'q') {            /* 一文字目が q なら終了 */
            break;
        } else if (buf[0] == 'p') {     /* p なら全体を印字 */
            Data_printlist(&head);
        } else if (buf[0] == 'a') {     /* a ならデータ追加 */
            printf("「作曲家名tab生年」のスタイルで入力せよ.\n");
            if (Data_add(&head, stdin) == NO) {
                fprintf(stderr, "メモリが足りません.\n");
            }
        } else if (buf[0] == 'd') {     /* d ならデータ削除 */
            Data *p;

            printf("誰を？\n");
            fgets(buf, BUFSIZE, stdin); /* ユーザが入力 */
            buf[strlen(buf)-1] = '\0';  /* '\n' を '\0' に置き換える */
            p = Data_listsearchstring(&head, buf);
            if (p == NULL) {
                printf("見つかりません.\n");
            } else {
                printf("削除しますか？\n");
                fgets(buf, BUFSIZE, stdin);     /* ユーザが入力 */
                if (buf[0] == 'y' || buf[0] == 'Y') {
                    if (Data_delete(&head, p) == NO) {
                        fprintf(stderr, "とてつもなく変です.\n"); return 1;
                    }
                }
            }
        } else {
            printf("入力エラーです.\n");
        }
    } while (1);

    return 0;
}


/* in から一行を読み込んで Data を作り、ダミーのヘッド head の次に追加 */
int Data_add(Data *head, FILE *in) {
    Data *tmp;

    tmp = Data_construct(in);
    if (tmp == NULL) {
        return NO;
    }
    tmp->next = head->next; head->next = tmp;
    return OK;
}


/* in から一行を読み込んで Data 型オブジェクトを作り、そのアドレスを返す */
Data *Data_construct(FILE *in) {
    int j;
    Data *p;
    static char buf[BUFSIZE+1];         /* バッファ */

    if ((p = malloc(sizeof(Data))) == NULL) {
        return NULL;
    }

    if (fgets(buf, BUFSIZE, in) == NULL) {
        free(p); return NULL;           /* 読み込めなかった場合 */
    }
    for (j=0; buf[j] != '\t'; j++) {    /* タブをさがす */
        ;
    }
    if ((p->string = malloc(j+1)) == NULL) {
        free(p); return NULL;
    }
    buf[j] = '\0';
    strcpy(p->string, buf);             /* 文字列をコピー */
    while (buf[++j] == '\t') {          /* タブをスキップ */
        ;
    }
    p->number = atoi(buf+j);            /* 数値データを読み込む */
                                        /* next は初期化せず */
    return p;
}


/* ダミーのヘッド head から始まるリストから p を削除（して破壊） */
int Data_delete(Data *head, Data *p) {
    Data *q;

    for (q = head; q->next != NULL; q = q->next) {
        if (q->next == p) {             /* 見つかった */
            q->next = p->next; Data_destruct(p); return OK;
        }
    }
    return NO;
}


/* p （の指す Data 型オブジェクト）を破壊 */
void Data_destruct(Data *p) {
    free(p->string); free(p);
}


/* ダミーのヘッド head から始まるリストから s を検索 */
Data *Data_listsearchstring(Data *head, char* s) {
    Data *p;

    for (p = head->next; p != NULL; p = p->next) {
        if (strcmp(p->string, s) == 0) {
            return p;
        }
    }
    return NULL;
}


/* Data 型オブジェクト *p の string と文字列 s を比較。一致すれば 0 */
int Data_stringcmp(Data *p, char *s) {
    return strcmp(p->string, s);
}


/* ダミーのヘッド head から始まるリストを印字 */
void Data_printlist(Data *head) {
    Data *p;

    for (p = head->next; p != NULL; p = p->next) {
        Data_print(p);
    }
}


/* Data 型オブジェクト *p を印字 */
void Data_print(Data *p) {
    printf("%s\t%d\n", p->string, p->number);
}

== 020515d.c ==

/******************************************************************************

    二分木を利用した単語の出現頻度カウントプログラム

******************************************************************************/

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

struct tnode {
    char *word;                     /* 単語 */
    int count;                      /* カウント */
    struct tnode *left;             /* 左の子へのポインタ */
    struct tnode *right;            /* 右の子へのポインタ */
};

typedef struct tnode Tnode;

#define BUFSIZE 1024    /* バッファの大きさ */

char *freadword(FILE *in);
Tnode *Tnode_add(Tnode* tp, char *s);
Tnode *Tnode_construct(char *s);
void Tnode_printtree(Tnode* tp);
void Tnode_print(Tnode *p);

int main(int argc, char *argv[]) {
    FILE *in;
    char *s;
    Tnode *root = NULL;

    if (argc != 2) {
        fprintf(stderr, "引数の数が違います.\n");
        return 1;
    }
    in = fopen(argv[1], "rt");
    if (in == NULL) {
        fprintf(stderr, "ファイル \"%s\" を開けません.\n", argv[1]);
        return 1;
    }

    while ((s = freadword(in)) != NULL) {   /* 単語を読み込んでは */
        root = Tnode_add(root, s);          /* 木につけ加える */
    }
    Tnode_printtree(root);                  /* 木の印字 */

    return 0;
}

/* in から読み込んだ次の単語を大文字にして返す。（いわゆる）日本語は不可 */
char *freadword(FILE *in) {
    static char buf[BUFSIZE+1] = "";
    static char *bufp = buf;                /* 次の word の先頭候補 */
    char *p;

    while (1) {
        while (!isalpha(*bufp) && *bufp != '\0') {      /* 非欧字をスキップ */
            bufp++;
        }
        if (*bufp == '\0') {                /* 行末まで単語がなかった */
            bufp = buf;
            if (fgets(buf, BUFSIZE, in) == NULL) {
                return NULL;                /* 読み込めなかった場合 */
            }
            continue;
        }
        p = bufp;
        while (isalpha(*bufp)) {            /* 単語の終わりの次を探す */
            *bufp = toupper(*bufp); bufp++;
        }
        if (*bufp == '\0') {                /* 不完全行の場合は \n がなくて */
            *(bufp+1) = '\0';               /* すぐ \0 がくるので別処理 */
        }
        *bufp++ = '\0';                     /* ++ は次の呼び出しに備えて */
        return p;
    }
}


/* 木 p 以下に s を“加える”。p が NULL 以外のときの返り値は p 自身 */
Tnode *Tnode_add(Tnode *p, char *s) {
    int result;

    if (p == NULL) {
        return Tnode_construct(s);
    } else {
        result = strcmp(s, p->word);
        if (result < 0) {                       /* 小さければ左の部分木へ */
            p->left = Tnode_add(p->left, s);
        } else if (result > 0) {                /* 大きければ右の部分木へ */
            p->right = Tnode_add(p->right, s);
        } else {                                /* 一致すればカウントを増す */
            p->count++;
        }
        return p;
    }
}


/* s から Tnode を構成 */
Tnode *Tnode_construct(char *s) {
    Tnode *p;

    if ((p = malloc(sizeof(Tnode))) == NULL) {
        return NULL;
    }
    if ((p->word = malloc(strlen(s)+1)) == NULL) {
        free(p); return NULL;
    }
    strcpy(p->word, s);
    p->count = 1;
    p->left = p->right = NULL;
    return p;
}


/* 木 p を印字 */
void Tnode_printtree(Tnode *p) {
    if (p == NULL) {
        return;
    }
    Tnode_printtree(p->left);
    Tnode_print(p);
    Tnode_printtree(p->right);
}


/* p の指す Tnode を印字 */
void Tnode_print(Tnode *p) {
    printf("%4d %s\n", p->count, p->word);
}

== 020515e.c ==

/******************************************************************************

    二分木を利用した単語の出現頻度カウントプログラム（出力が深さつきの版）

        注）020515d.c からの変更点のみを示す。

******************************************************************************/

その１）

void Tnode_printtree(Tnode* tp, int depth);

その２）

    Tnode_printtree(root, 0);               /* 木の印字 */

その３）

/* 木 p を印字。深さつき */
void Tnode_printtree(Tnode *p, int depth) {
    if (p == NULL) {
        return;
    }
    Tnode_printtree(p->left, depth + 1);
    printf("%2d ", depth);
    Tnode_print(p);
    Tnode_printtree(p->right, depth + 1);
}