単連結リストの整列 #16 整数を整列する

さっそくlsortを使って整列させてみる。
とりあえず、今までと同様にint型を要素が保持する場合について書いてみる。

test_lsort.c

#include <stdio.h>
#include "lsort.h"

#define UNUSED_ARG(x) (void)(x)

typedef struct tag_int_node int_node_t;
struct tag_int_node {
    int_node_t *next;
    int val;
};

static int sup(const void *x, const void *y, void *arg)
{
    UNUSED_ARG(arg);
    return ((int_node_t *)x)->val > ((int_node_t *)y)->val;
}

static void print(int_node_t *node)
{
    int_node_t *p;
    for (p = node; p != NULL; p = p->next) {
        printf(p->next == NULL ? "%d\n" : "%d ", p->val);
    }
}

#define NNODES 5

int main(void)
{
    int i;
    int_node_t p[NNODES], *q, *node = p;
    for (i = 0, q = p; i < NNODES; i++) {
        p[i].next = i < NNODES - 1 ? ++q : NULL;
        p[i].val = NNODES - i;
    }
    print(node);
    lsort(&node, sup, NULL);
    print(node);
    return 0;
}

int型のメンバvalを持つint_node_t型が今回整列する単連結リストの要素である。
p[0]が先頭要素であり、&p[0]、すなわち p が先頭要素のアドレスである。
変数nodeは先頭要素のアドレスを保持するためにあり、
初期状態では、このpの値がアドレスとして格納されている。
関数lsortへはnodeのアドレスを第一引数として渡すことになる。
順位定義関数supでは順位比較にエクストラデータは不要なので、
lsortの第三引数にはNULLを渡しており、supでもその第三引数は使用していない。

実行すると、

5 4 3 2 1
1 2 3 4 5

昇順に整列した。