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

                                                     2002 年 05 月 22 日（水）

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

                                                                    岩瀬順一

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

== 020522a.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;         /* 数値データ */
};

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

#define N 20            /* 配列の大きさ */
#define BUFSIZE 1024    /* バッファの大きさ */

Data a[N];              /* Data 型の配列 */
int arraysize;          /* 配列に実際に保持されているデータ数 */

int Data_read(Data *p, FILE *in);
int Data_read2array(Data *p, FILE *in, int size);
int Data_isarraysorted(Data *p, int arraysize);
int Data_arraybsearchstring(Data *p, int arraysize, char *s);
int Data_stringcmp(Data *p, char *s);
void Data_print(Data *p);

int main(int argc, char *argv[]) {
    int i;
    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;
    }

    arraysize = Data_read2array(a, in, N);  /* 配列に読み込む */
    if (Data_isarraysorted(a, arraysize) == NO) {
        fprintf(stderr, "データがソートされていません.\n");
        return 1;
    }

    i = Data_arraybsearchstring(a, arraysize, argv[2]); /* argv[2] を探す */
    if (i == -1) {
        printf("見つかりません.\n");
    } else {
        Data_print(a+i);
    }

    return 0;
}


/* in から配列 p に最大 size 個読み込み、読めた個数を返す */
int Data_read2array(Data *p, FILE *in, int size) {
    int i;

    for (i=0; i<size; i++) {            /* 配列の要素にデータを読み込む */
        if (Data_read(p+i, in) == NO) {
            return i;
        }
    }
    return size;
}


/* FILE *in から Data *p へ Data 型オブジェクトを読み込む。成功 OK / 失敗 NO */
int Data_read(Data *p, FILE *in) {
    int j;

    static char buf[BUFSIZE+1];         /* 一行ずつ処理するためのバッファ */

    if (fgets(buf, BUFSIZE, in) == NULL) {
        return NO;                      /* 読み込めなかった場合 */
    }
    for (j=0; buf[j] != '\t'; j++) {    /* タブをさがす */
        ;
    }
    p->string = malloc(j+1);            /* メモリを要求 */
    if (p->string == NULL) {
        fprintf(stderr, "メモリが足りません.\n");
        return NO;
    }
    buf[j] = '\0';
    strcpy(p->string, buf);             /* 文字列をコピー */
    while (buf[++j] == '\t') {          /* タブをスキップ */
        ;
    }
    p->number = atoi(buf+j);            /* 数値データを読み込む */
    return OK;
}


/* 配列 p 内のデータがソート済みであるかどうかを返す */
int Data_isarraysorted(Data *p, int arraysize) {
    int i;

    for (i=0; i<arraysize-1; i++) {
        if (strcmp(p[i].string, p[i+1].string) > 0) {
            return NO;
        }
    }
    return YES;
}


/* サイズ arraysize の Data 型の配列 p から string が s であるものを探し */
/* 添字（見つからなければ -1）を返す。二分探索バージョン */
int Data_arraybsearchstring(Data *p, int arraysize, char *s) {
    int left, right;

    left = 0, right = arraysize - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        int result = Data_stringcmp(p + middle, s);

        if (result > 0) {
            right = middle - 1;
        } else if (result == 0) {
            return middle;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}


/* 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);
}

== 020522b.c ==

/* サイズ arraysize の Data 型の配列 p から string が s であるものを探し */
/* 添字（見つからなければ -1）を返す。二分探索バージョン（その２） */
/* ループ内の比較が一度であることが特徴 */
int Data_arraybsearchstring(Data *p, int arraysize, char *s) {
    int left, right;

    left = 0, right = arraysize - 1;
    while (left <= right) {
        int middle = (left + right) / 2;

        if (Data_stringcmp(p + middle, s) > 0) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
        /* ここにくるとき left == right + 1 であることに注意 */
    if (right == -1 || Data_stringcmp(p + right, s) != 0) {
        return -1;
    } else {
        return right;
    }
}

== 020522c.c ==

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

    二分木からの削除

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

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

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

typedef struct tnode Tnode;

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

char *freadword(FILE *in);
Tnode *Tnode_search(Tnode **pp, char *s);
Tnode *Tnode_delete(Tnode *root, Tnode *p);
Tnode *Tnode_extractmax(Tnode **pp);
Tnode *Tnode_construct(char *s);
void Tnode_destruct(Tnode *p);
void Tnode_printtree(Tnode* tp, int depth);
void Tnode_print(Tnode *p);

int main() {
    char buf[BUFSIZE+1];
    Tnode *root = NULL;
    Tnode *p;

    while (printf("? "), fgets(buf, BUFSIZE, stdin) != NULL) {
        p = Tnode_search(&root, buf);   /* 木から探す */
        if (p) {                        /* 見つかれば…… */
            root = Tnode_delete(root, p);   /* 削除 */
        }
        Tnode_printtree(root, 0);       /* 木の印字 */
    }
    return 0;
}


/* 木 p 以下に s を探して返す。なければ加え、NULL を返す */
Tnode *Tnode_search(Tnode **pp, char *s) {
    int result;

    if (*pp == NULL) {
        *pp = Tnode_construct(s); return NULL;
    } else {
        result = strcmp(s, (*pp)->word);
        if (result < 0) {                       /* 小さければ左の部分木へ */
            return Tnode_search(&((*pp)->left), s);
        } else if (result > 0) {                /* 大きければ右の部分木へ */
            return Tnode_search(&((*pp)->right), s);
        } else {                                /* 一致すればアドレスを返す */
            return *pp;
        }
    }
}


/* p 以下から q を削除し、削除後の新しい木を返す */
Tnode *Tnode_delete(Tnode *p, Tnode *q) {
    int result;

    result = strcmp(p->word, q->word);
    if (result > 0) {
        p->left = Tnode_delete(p->left, q); return p;
    } else if (result < 0) {
        p->right = Tnode_delete(p->right, q); return p;
    } else {    /* 見つかったとき */
        if (p->right == NULL) {
            Tnode_destruct(p); return p->left;
        }
        if (p->left == NULL) {
            Tnode_destruct(p); return p->right;
        }
        q = Tnode_extractmax(&(p->left));
        q->left = p->left, q->right = p->right;
        Tnode_destruct(p); return q;
    }
}


/* *pp 以下で最大のものを木から取り除いてそれを返す */
Tnode *Tnode_extractmax(Tnode **pp) {
    Tnode *q, *q2;

    if ((*pp)->right == NULL) {
        q = *pp; *pp = q->left; return q;   /* このときのみ *pp が変わる */
    }
    for (q = *pp; q->right->right != NULL; q = q->right) {
        ;
    }
    q2 = q->right; q->right = NULL; return q2;
}


/* 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->left = p->right = NULL;
    return p;
}


/* p の指す Tnode を破壊 */
void Tnode_destruct(Tnode *p) {
    free(p->word); free(p);
}


/* 木 p を印字。深さつき */
void Tnode_printtree(Tnode *p, int depth) {
    int i;

    if (p == NULL) {
        return;
    }
    Tnode_printtree(p->left, depth + 1);
    for (i=0; i<depth; i++) {
        printf("  ");
    }
    Tnode_print(p);
    Tnode_printtree(p->right, depth + 1);
}


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

== 020522d.c ==

void Tnode_delete(Tnode **pp, Tnode *q);


    while (printf("? "), fgets(buf, BUFSIZE, stdin) != NULL) {
        p = Tnode_search(&root, buf);   /* 木から探す */
        if (p) {                        /* 見つかれば…… */
            Tnode_delete(&root, p);     /* 削除 */
        }
        Tnode_printtree(root, 0);       /* 木の印字 */
    }


/* *pp 以下から q を削除。*pp を新しい木に置き換えることも */
void Tnode_delete(Tnode **pp, Tnode *q) {
    int result;

    result = strcmp((*pp)->word, q->word);
    if (result > 0) {
        Tnode_delete(&((*pp)->left), q);
    } else if (result < 0) {
        Tnode_delete(&((*pp)->right), q);
    } else {    /* 見つかったとき */
        if (q->right == NULL) {
            Tnode_destruct(q); *pp = q->left; return;
        }
        if (q->left == NULL) {
            Tnode_destruct(q); *pp = q->right; return;
        }
        q = Tnode_extractmax(&(q->left));
        q->left = (*pp)->left, q->right = (*pp)->right;
        Tnode_destruct(*pp); *pp = q;
    }
}