データ構造:リスト:単方向連結リスト #1 [C]

データ構造「リスト」の中で、もっともシンプルな「単方向連結リスト」です。

リストを型定義し、リストを操作する基本的な手続きを記述します。

リスト構造体とリスト型定義を宣言

適宜、リストの要素のデータ型を変更してください。

typedef struct LIST {
    /* データ型 */
    int data;
    struct LIST *next;
} LIST;

リストを作成

    LIST *list = NULL;

リストの先頭に要素を追加

適宜、メモリの動的割り当てに失敗したときのエラー処理をしてください。また、データ型にあわせたデータを格納してください。

    LIST *e = (LIST *)malloc(sizeof(LIST));
    if (!e) {
        /* エラー処理 */
        fprintf(stderr, "%s:%d: cannot allocate memory", __FILE__, __LINE__);
        exit(EXIT_FAILURE);
    }
    /* データ */
    e->data = 0;
    e->next = NULL;

    if (list)
        e->next = list;
    list = e;

リストの末尾に要素を追加

適宜、メモリの動的割り当てに失敗したときのエラー処理をしてください。また、データ型にあわせたデータを格納してください。

    LIST *e = (LIST *)malloc(sizeof(LIST));
    if (!e) {
        /* エラー処理 */
        fprintf(stderr, "%s:%d: cannot allocate memory", __FILE__, __LINE__);
        exit(EXIT_FAILURE);
    }
    /* データ */
    e->data = 0;
    e->next = NULL;

    if (list) {
        LIST *p;
        for (p = list; p->next; p = p->next)
            ;
        p->next = e;
    }
    else {
        list = e;
    }

リストの先頭の要素を削除

    if (list) {
        LIST *p = list;
        list = list->next;
        free(p);
    }

リストの末尾の要素を削除

    if (list) {
        LIST *p;
        if (list->next) {
            LIST *q;
            for (q = list; q->next->next; q = q->next)
                ;
            p = q->next;
            q->next = NULL;
        }
        else {
            p = list;
            list = p->next;
        }
        free(p);
    }

リストの要素を反復

適宜、要素の処理を変更してください。

    LIST *p;
    for (p = list; p; p = p->next)
        /* 要素の処理 */
        printf("%d ", p->data);

サンプルコード

list1-1.c

About TSUCHIDA Takuya

生まれ変わったら黒猫になりたいシステムアーキテクトです。僕への連絡は右下の MessageLeaf からお願いします。
This entry was posted in Data Structure and tagged , , , . Bookmark the permalink.