単連結リストの整列 #18 文字列を整列する

ナル文字終端な文字列をデータとして持つ要素についての整列を行ってみる。

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

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

typedef struct tag_snode snode_t;
struct tag_snode {
    snode_t *next;
    char *val;
};

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

static int sub(const void *x, const void *y, void *arg)
{
    UNUSED_ARG(arg);
    return strcmp(((snode_t *)x)->val, ((snode_t *)y)->val) < 0;
}

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

int main(void)
{
    int i;
    snode_t p[] = {
        {NULL, "peach"}, {NULL, "apple"}, {NULL, "strawberry"}, {NULL, "orange"}, {NULL, "banana"},
        {NULL, NULL}
    }, *q, *node = p;
    for (i = 0, q = p; (++q)->val != NULL; i++) p[i].next = q;
    print(node);
    lsort(&node, sup, NULL);
    print(node);
    lsort(&node, sub, NULL);
    print(node);
    return 0;
}

二つの順位定義関数supとsubを定義している。
supは第一引数の文字列が文字コード順で上位の場合に、subは逆に下位の場合に真を返す。
実行すると、

[peach]->[apple]->[strawberry]->[orange]->[banana]
[apple]->[banana]->[orange]->[peach]->[strawberry]
[strawberry]->[peach]->[orange]->[banana]->[apple]

期待通り、supで文字コード順に並び、subでその逆順に並んだ。