Hatena::Groupcprogramming

Going My C Way このページをアンテナに追加 RSSフィード

2011年07月19日(火)

連結リストを扱うマクロ

15:33 | 連結リストを扱うマクロ - Going My C Way を含むブックマーク はてなブックマーク - 連結リストを扱うマクロ - Going My C Way 連結リストを扱うマクロ - Going My C Way のブックマークコメント

双方向循環連結リストを扱うマクロ集です。

制約として、データは以下のような構造体である必要があります。

struct xxxxx {
  struct xxxxx *next;  /* next という名前の「次へ」の自己参照ポインタ */
  struct xxxxx *prev;  /* prev という名前の「前へ」の自己参照ポインタ */

        :
};

循環連結リストはヘッドというダミーのデータを持ちます。

空のリストはヘッドのみのリストです。

最後のデータの「次の」データはヘッドです。

またヘッドの「前の」データは最後のデータになります。

  [head]                       # データがない空のリスト
  [head] -> [data1]            # データが 1つのリスト
  [head] -> [data1] -> [data2] # データが 2つのリスト

llist.h

#ifndef INCLUDED_LLIST_H
#define INCLUDED_LLIST_H

#define llist_init(l_)  ((l_)->next = (l_)->prev = (l_))

#define llist_next(l_)  ((l_)->next)
#define llist_prev(l_)  ((l_)->prev)

#define llist_ins_next(l_, x_)  (\
    (x_)->next       = (l_)->next   ,\
    (x_)->prev       = (l_)         ,\
    (l_)->next->prev = (x_)         ,\
    (l_)->next       = (x_)         )

#define llist_ins_prev(l_, x_)  (\
    (x_)->prev       = (l_)->prev   ,\
    (x_)->next       = (l_)         ,\
    (l_)->prev->next = (x_)         ,\
    (l_)->prev       = (x_)         )

#define llist_del_next(l_)                      (\
    (l_)->next->next->prev  = (l_)              ,\
    (l_)->next              = (l_)->next->next  )

#define llist_del_prev(l_)                      (\
    (l_)->prev->prev->next  = (l_)              ,\
    (l_)->prev              = (l_)->prev->prev  )

#define llist_del(l_)               (\
    (l_)->prev->next = (l_)->next   ,\
    (l_)->next->prev = (l_)->prev   )

#endif /* !INCLUDED_LLIST_H */

使用例。(try-llist.c)

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

typedef struct station_t {
    struct station_t *next;
    struct station_t *prev;

    char *name;
} STATION_t;

int main(void)
{
    STATION_t stations[10], *station;

    STATION_t *chuo_line    = &stations[0]; /* ヘッド */
    STATION_t *shinjuku     = &stations[1];
    STATION_t *nakano       = &stations[2];
    STATION_t *mitaka       = &stations[3];

    shinjuku->name  = "Shinjuku";
    nakano->name    = "Nakano";
    mitaka->name    = "Mitaka";

    /*
        リストの初期化とデータの挿入
    */
    llist_init(chuo_line);
    llist_ins_next(chuo_line,   shinjuku);
    llist_ins_next(shinjuku,    nakano);
    llist_ins_next(nakano,      mitaka);

    /*
        リストの全データの表示
    */
    puts("-----");
    for (station = llist_next(chuo_line);
            station != chuo_line; station = llist_next(station)) {
        puts(station->name);
    }

    /*
        データ nakano を削除してみる
    */
    puts("-----");
    llist_del(nakano);

    for (station = llist_next(chuo_line);
            station != chuo_line; station = llist_next(station)) {
        puts(station->name);
    }

    return EXIT_SUCCESS;
}

実行結果。

$ ./try-llist 
-----
Shinjuku
Nakano
Mitaka
-----
Shinjuku
Mitaka