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

                                                     2002 年 05 月 29 日（水）

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

                                                                    岩瀬順一

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

== 020529c.c の訂正 ==

/* 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 {    /* 見つかったとき。p == q に注意 */
        if (p->right == NULL) {
            Tnode_destruct(p); return q->left;
        }
        if (p->left == NULL) {
            Tnode_destruct(p); return q->right;
        }
        q = Tnode_extractmax(&(p->left));
        q->left = p->left, q->right = p->right;
        Tnode_destruct(p); return q;
    }
}


== 020529b.c ==

/* 素朴なソート（その１） */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define N 23        /* ソートするものの個数 */
#define MAX 99      /* 数値データは 0 ... MAX */

#define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; }

int myrand(int max);
void print(void);
void sort(void);

int a[N];

main() {
    int i;

    srand((unsigned)time(NULL));        /* 現在時刻で乱数の種を初期化 */

    for (i=0; i<N; i++) {
        a[i] = myrand(MAX);
    }
    print();
    sort();
    print();
    return;
}


/* 0 ... max の範囲の乱数を返す。max <= RAND_MAX でなければならない */
int myrand(int max) {
    int r;

    if (max == INT_MAX) {
        return rand();
    }

    while (1) {
        r = rand();
        if (RAND_MAX % (max+1) != max && r/(max+1) == RAND_MAX/(max+1)) {
            continue;
        } else {
            return r % (max+1);
        }
    }
}


/* 配列を印字 */
void print(void) {
    int i;

    for (i=0; i<N; i++) {
        printf(" %2d", a[i]);
    }
    putchar('\n');
}


/* 配列をソート。前から見ていって最初に逆転しているところを入れかえる */
void sort(void) {
    int i;

    do {
        for (i=0; i<N-1; i++) {
            if (a[i] > a[i+1]) {
                swap(i, i+1);
                print();        /* swap() を呼ぶごとに印字する */
                break;
            }
        }
    } while (i != N-1);
}


== 020529c.c ==

/* 素朴なソート（その２） */

/* 配列をソート。「最大のものを最後へ」の方針で */
void sort(void) {
    int i, m;

    for (m=N-1; m>0; m--) {
        for (i=0; i<m; i++) {
            if (a[i] > a[i+1]) {
                swap(i, i+1);
                print();        /* swap() を呼ぶごとに印字する */
            }
        }
    }
}