C言語アルゴリズム-連結リスト



リストデータ構造について

リストとは

リストとは、多数のデータ要素を一定の形式に従って並べて扱うデータ構造です。

リスト構造は複数のデータを一覧表のように関連付けてまとめて扱いたい場合に用います。


線形リストと連結リストの違い

線形リスト(linear list)とは、要素が順序付けされたリストデータ構造のことです。例えば、配列は代表的な線形リストと言えます。なお、C言語における線形リストは、同じ要素のデータをメモリアドレス順に並べたものを指すと考えることができます。


連結リスト(linked list)とは、要素を何らかの方法でつなぎ合わせた(連結した)データ構造です。連結リストでは、配列のように各要素を連続的なメモリアドレスに並べることをしません。各要素は、メモリアドレス上に飛び飛びの位置に置かれており、それぞれをポインタで「連結(リンク)」します。

なお、単にリストといった場合、通常は連結リストのことを指します。


リストの種類


セル (cell)とは

セルとは、リスト構造においてデータを格納する入れ物のことです。ノードと呼ばれることもあります。

C言語でリストを作成する場合、たいてい構造体を利用します。構造体メンバのnextは次のセルへのポインタです。

struct cell {
    struct cell *prev;
    struct cell *next;
    int key;
    data_t data;
};

C言語による連結リスト構造のサンプルプログラム

最も単純化した単方向連結リストです。新規セルを最後尾に追加する構造としています。

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

/* セルの定義 */
struct cell{
    struct cell *next;
    int data;
};
typedef struct cell cell_t;

/*!
 * @brief       新規セルを生成する。
 * @param[in]   data  データ
 * @return      新規セルのアドレスを返す。失敗の場合はNULLを返す。
 */
cell_t *
list_alloc(int data)
{
    cell_t *new = NULL;

    new = (cell_t *)malloc(sizeof(cell_t));
    if(new == NULL){
        fprintf(stderr, "ERROR: list_alloc(): %s\n", strerror(errno));
        return(NULL);
    }

    new->next = NULL;
    new->data = data;

    return(new);
}

/*!
 * @brief      リスト末尾に新規セルを追加する
 * @param[in]  header  リストの先頭要素
 * @param[in]  data  データ
 */
int
list_add(cell_t *header, int data)
{
    cell_t *next = NULL;
    cell_t *prev = header;

    /* セルを生成する */
    next = list_alloc(data);
    if(next == NULL) return(-1);

    /* 末尾にセルを追加する */
    while(prev->next != NULL){
        prev = prev->next;
    }
    prev->next = next;

    return(0);
}

/*!
 * @brief      リストの要素を全て解放する
 * @param[in]  header  リストの先頭要素
 */
void
list_free(cell_t *header)
{
    cell_t *temp = header;
    cell_t *swap = NULL;

    while(temp != NULL){
        swap = temp->next;
        free(temp);
        temp = swap;
    }
}

/*!
 * @brief      リストの要素を一覧表示する
 * @param[in]  header  リストの先頭要素
 */
static void
list_print(cell_t *header)
{
    cell_t *p = header;

    printf("list{ ");
    while(p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("}\n");
}

int
main(void)
{
    int cnt = 0;

    /* 先頭セルを用意する */
    cell_t *header = list_alloc(0);
    if(header == NULL) return(-1);

    /* 要素を追加する */
    for(cnt = 1; cnt < 10; cnt++){
        list_add(header, cnt);
    }
    list_print(header);

    /* リストを解放する */
    list_free(header);

    return(0);
}



関連ページ



スポンサード リンク