単連結リストの整列 #9 代り映えしないが

ヘッダで宣言したインタフェイスを実装する。
基本的にtest_node.cの各関数に沿った形になっている。
list_t型はtest_node.cにおけるダミー要素にあたるheadメンバーを管理する。
このダミー要素や実データを収納する要素はこれまでと同様にnode_t型である。

list.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct tag_node node_t;
struct tag_node {
    node_t *next;
    int val;
};

struct tag_list {
    node_t head;
};

static node_t *node_new(int val)
{
    node_t *p = malloc(sizeof(node_t));
    if (p != NULL) {
        p->next = NULL;
        p->val = val;
    }
    return p;
}

static void node_swap(node_t *current)
{
    node_t *p, *q;
    if (current == NULL || (p = current->next) == NULL || (q = p->next) == NULL) return;
    current->next = q;
    p->next = q->next;
    q->next = p;
}

list_t list_new(void)
{
    list_t p = malloc(sizeof(struct tag_list));
    if (p != NULL) p->head.next = NULL;
    return p;
}

void list_dispose(list_t list)
{
    node_t *p;
    if (list == NULL) return;
    p = list->head.next;
    while (p != NULL) {
        node_t *q = p->next;
        free(p);
        p = q;
    }
    free(list);
}

int list_add(list_t list, int val)
{
    node_t *p, *q;
    if (list == NULL || (q = node_new(val)) == NULL) return 0;
    for (p = &list->head; p->next != NULL; p = p->next) ;
    p->next = q;
    return 1;
}

void list_print(list_t list)
{
    node_t *p;
    if (list == NULL) return;
    for (p = list->head.next; p != NULL; p = p->next) {
        printf(p->next == NULL ? "%d\n" : "%d ", p->val);
    }
}

void list_sort(list_t list)
{
    node_t *p, *q;
    if (list == NULL || list->head.next == NULL || list->head.next->next == NULL) return;
    for (q = NULL; q != list->head.next->next; q = p->next) {
        for (p = &list->head; p->next->next != q; p = p->next) {
            if (p->next->val > p->next->next->val) node_swap(p);
        }
    }
}

前回示した使い方例のプログラムを動かすと、

$ ./test_list
179 380 824 328 439 383 919 463 177 140 249 345 693 568 943 987 601 422 915 471
140 177 179 249 328 345 380 383 422 439 463 471 568 601 693 824 915 919 943 987