Next Sec.: 木構造リスト（tree structured list） Upper Sec.: 動的データ構造 Prev. Sec.: Cにおけるポインタの表現

線形リスト

線形リスト（linear list）


ポインタによって線形に結合されたデータ構造

例：スタック（stack），待ち行列（queue），etc.

例)リストの生成（先頭挿入）

#include <stdio.h>

struct node {
        int    data;
        struct node *next;
};

void main(void)
{
        int n;
        struct node *HEAD = NULL;
        struct node *P;

        if(scanf("%d", &n) > 0) {
                while(n > 0) {
                        P = (struct node *)malloc(sizeof(struct node));
                        P->data = n;
                        P->next = HEAD;
                        HEAD = P;
                        n--;
                }
         }
}

例) リストの生成（中間挿入）

ランダムに入力されるデータを昇順にソートしたリストの生成

#include <stdio.h>

struct node {
        int data;
        struct node *next;
};

void main(void)
{
        int n;
        node *HEAD, *TAIL, *P, *Q;

        TAIL = (struct node *)malloc(sizeof(struct node));
        TAIL->next = NULL;
        HEAD = TAIL;

        while(scanf("%d" &n) != EOF) {
                TAIL->data = n;        /* 番兵のセット */

                P = HEAD;
                while(n > P->data)
                        P = P->next;

                Q = (struct node*)malloc(sizeof(struct node));
                *Q = *P;
                P->data = n;
                Q->next = Q;
                if (Q->next == NULL) TAIL = Q;
        }
}

22 < X < 51