単連結リストの整列 #7 比較と交換の確認

C

隣接交換法での要素の比較と交換の様子を表示してみる。

test_node.c
...snip
#include <time.h>
...snip
static int index(node_t *first_node, node_t *node)
{
    int i = 0;
    node_t *p;
    for (p = first_node; p != NULL && p != node; p = p->next) i++;
    if (p == NULL) return 0;
    return i;
}

#ifndef DEBUG
#define DEBUG 0
#endif
#if DEBUG != 0
#define node_swap(p) \
    printf("swap %d and %d\n", index(first_node, p->next), index(first_node, p->next->next)), \
    node_swap(p), \
    node_print(first_node)
#endif

static void node_sort(node_t *first_node)
{
    node_t *p, *q;
    if (first_node == NULL || first_node->next == NULL || first_node->next->next == NULL) return;
    for (q = NULL; q != first_node->next->next; q = p->next) {
        for (p = first_node; p->next->next != q; p = p->next) {
            if (DEBUG) printf("compare %d and %d\n", index(first_node, p->next), index(first_node, p->next->next));
            if (p->next->val > p->next->next->val) node_swap(p);
        }
    }
}

#if DEBUG != 0
#undef node_swap
#endif

#ifndef N_DATA
#define N_DATA 9
#endif

int main(void)
{
    int i;
    node_t *first_node = node_new(0);
    srand(time(NULL));
    for (i = 0; i < N_DATA; i++) {
        node_append(first_node, (int)(rand() / (RAND_MAX + 1.0) * 900) + 100);
    }
    node_print(first_node);
    node_sort(first_node);
    node_print(first_node);
    return 0;
}

整列やリストに関わる関数のうち元のコードからの変更はnode_sort関数に一文加えるだけである。
さらに、表示のための補助用に新たに関数indexを定義している。
これは引数として渡した要素について、リストの先頭要素を1とする先頭要素からの序数を返す。
また、main関数で整列すべきデータを3桁の乱数にし、N_DATA個のデータを持つリストを作成する。

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_node test_node.c -s -DN_DATA=5 -DDEBUG=1

$ ./test_node
711 938 807 302 893
compare 1 and 2
compare 2 and 3
swap 2 and 3
711 807 938 302 893
compare 3 and 4
swap 3 and 4
711 807 302 938 893
compare 4 and 5
swap 4 and 5
711 807 302 893 938
compare 1 and 2
compare 2 and 3
swap 2 and 3
711 302 807 893 938
compare 3 and 4
compare 1 and 2
swap 1 and 2
302 711 807 893 938
compare 2 and 3
compare 1 and 2
302 711 807 893 938

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_node test_node.c -s -DN_DATA=0 -DDEBUG=1

$ ./test_node

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_node test_node.c -s -DN_DATA=1 -DDEBUG=1

$ ./test_node
732
732

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_node test_node.c -s -DN_DATA=2 -DDEBUG=1

$ ./test_node
738 669
compare 1 and 2
swap 1 and 2
669 738
669 738

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_node test_node.c -s -DN_DATA=3 -DDEBUG=1

$ ./test_node
744 958 630
compare 1 and 2
compare 2 and 3
swap 2 and 3
744 630 958
compare 1 and 2
swap 1 and 2
630 744 958
630 744 958

$ gcc -std=c89 -pedantic -Wall -Wextra -Werror -o test_node test_node.c -s -DN_DATA=10

$ ./test_node
748 714 454 871 129 326 581 849 178 632
129 178 326 454 581 632 714 748 849 871

コンパイル時にDEBUGを非零に設定すると比較と交換のたびにその旨を表示し、
また、交換のたびにリストの状態を表示する。
リストに1個もデータが無い（N_DATA=0）ような場合も含めうまく動作しているようだ。