第15章の5　自己参照構造体

C言語の自己参照構造体とは、自分と同じ型の構造体へのポインタをメンバーとして含む構造体のことです。これにより、構造体同士を連結してリスト構造（連結リスト、木構造など）を作成することができます。

1. 自己参照構造体とは

自己参照構造体は、次に示す例のように、メンバに自分自身と同じ型の構造体をポインタで宣言しています。

// 自己参照構造体
struct list {
    char name[20];
    struct list *next;    // 自分自身と同じ型の構造体をポインタで宣言
};

この自己参照構造体は一般にリスト処理で用いられます。

2. リスト処理

今まで複数のデータをまとめて扱うときには配列を用いて処理をしてきました。

配列は連続するデータを一括して処理しているうちはいいのですが、途中にデータを挿入したり削除をするときに、それ以降のデータを前後にずらす必要があります。 数少ないデータでしたら、前後にデータをずらしても左程時間はかかりません。

しかし、大量のデータや頻繁にデータの追加や削除が行われるシステムでは、それは大変な無駄なのです。 そのような場合に、リスト構造を使ってデータを処理します。

(1) リスト構造の例

リスト構造ではデータは物理的に連続に並んでいる必要はありません。 ポインタを使って、次のデータ部を参照することにより、連続した処理を可能にします。

(2) リストへのデータの挿入

データを追加するときには、ポインタをつなぎ換え、新しいデータ部を指すようにします。

(3)リストからのデータの削除

データを削除する場合には、不要になったデータはそのままにし、次のデータ部にポインタをつなぎ換えるようにします。

3. 自己参照構造体を使ったリスト処理

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

struct list {
    int key;             // キー
    char name[20];       // 名前
    struct list *next;   // 次のデータへのポインタ
};

struct list *add_list(int key, char *name, struct list *head);
void show_list(struct list *p);
void free_list(struct list *p);

int main(void)
{
    struct list *head;   // 先頭ポインタ
    char name[20];
    int key = 0;

    head = NULL;         // 先頭ポインタにNULLを設定

    printf("キーと名前（MAX:19文字）を入力（終了:数値以外を入力）\n");
    // scanf が 2 つの値（%d %s）を読み込めなくなったら終了
    while (scanf("%d %19s", &key, name) == 2) {
        // リストにデータを登録
        head = add_list(key, name, head);
    }

    // リストの表示
    show_list(head);

    // リストの開放
    free_list(head);

    return 0;
}

// リストにデータを登録
struct list *add_list(int key, char *name, struct list *head)
{
    struct list *p;

    // 記憶領域の確保
    if ((p = (struct list *)malloc(sizeof(struct list))) == NULL) {
        printf("malloc error\n");
        exit(EXIT_FAILURE);
    }

    // リストにデータを登録
    p->key = key;
    strcpy(p->name, name);

    // ポインタのつなぎ換え
    p->next = head;  // 今までの先頭ポインタを次ポインタに
    head = p;        // 新たな領域を先頭ポインタに

    return head;
}

// リストの表示
void show_list(struct list *p)
{
    while (p != NULL) {  // 次ポインタがNULLまで処理
        printf("%3d %s\n", p->key, p->name);
        p = p->next;
    }
}

// リストの開放
void free_list(struct list *p)
{
    struct list *p2;

    while (p != NULL) {    // 次ポインタがNULLまで処理
        p2 = p->next;
        free(p);
        p = p2;
    }
}

(1) サンプルプログラムの解説

add_list関数 の流れ

1. まず先頭ポインタ head に NULL を設定

   

2. malloc で確保したエリアにデータ1 を格納し、head にデータ1 のアドレスを設定 head に格納されていた NULL は次ポインタへ

   

3. malloc で確保したエリアにデータ2 を格納し、head にデータ2 のアドレスを設定

   head に格納されていたデータ1 のアドレスは次ポインタへ

   

show_list関数 と free_list関数 の流れ

1. まず head のアドレスを main より受け取る

   

2. 次ポインタを次々につなぎ換えながらNULL（リスト終了）まで処理を行う。このとき、free_list では、ポインタをfreeする前に次ポインタを退避しておく。

   

〇 演習問題

「自己参照構造体を使ったリスト処理」で用いたプログラムを次のように修正しなさい。

キーと名前の他に、処理コードを入力させ、処理コードに従って次の処理を行うようにする。

1. 処理コード：１
   キーボードから入力したキーと名前を、新規のデータとしてリストに追加する。このとき、リストのデータはキーで降順に並ぶように登録すること。
2. 処理コード：２
   キーボードから入力したキーと同一キーのデータをリストから削除する。
3. 処理コード：３
   入力処理を終了し、リストの中身を表示する。

解答例

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

#define  ADD 1
#define  DEL 2
#define  END 3

struct list {
    int key;            // キー
    char name[20];      // 名前
    struct list *next;  // 次のデータへのポインタ
};

struct list *add_list(int key, char *str, struct list *head);
struct list *del_list(int key, struct list *head);
void show_list(struct list *p);
int in_dt(int *key, char *name);
void free_list(struct list *p);

int main(void)
{
    struct list *head;   // 先頭ポインタ
    char name[20];
    int code, key;

    head = NULL;         // 先頭ポインタにNULLを設定

    while(1) {
        // コード、キー、名前の入力
        code = in_dt(&key, name);
        if (code == END)
            // 処理終了
            break;
        else if (code == ADD)
            // リストにデータを登録
            head = add_list(key, name, head);
        else if (code == DEL)
            // リストからデータを削除
            head = del_list(key, head);
        else
            // コード入力エラー
            printf("コードの入力エラーです。再入力してください\n");
    }
    // リストの表示
    show_list(head);
    
    // リストの開放
    free_list(head);

    return 0;
}

// リストにデータを登録
struct list *add_list(int key, char *str, struct list *head)
{
    struct list *p, *new_p;

    // 新規リストにデータを登録
    if ((new_p = (struct list *)malloc(sizeof(struct list))) == NULL) {
        printf("malloc error\n");
        exit(EXIT_FAILURE );
    }
    new_p->key = key;
    strcpy(new_p->name, str);

    // キーが最大のとき
    if (head == NULL || key > head->key) {
        // ポインタのつなぎ換え
        new_p->next = head;
        return new_p;
    }

    // キーのサーチ
    for (p = head;  p->next != NULL; p = p->next)
        if (key > p->next->key) break;

    // ポインタのつなぎ換え
    new_p->next = p->next;
    p->next = new_p;
    return head;
}

// リストからデータを削除
struct list *del_list(int key, struct list *head)
{
    struct list *p, *old_p;

    p = old_p = head;

    // キーのサーチ
    while (p != NULL) {
        if (key == p->key) {
            // キーが一致したら
            if (p == head)
                head = p->next;
            else 
                old_p->next = p->next;
            free(p);
            return head;
        }
        old_p = p;
        p = p->next;
    }
    // キーが見つからない
    printf( "キー%dが見つかりません\n", key );
    return head;
}

// リストの表示
void show_list( struct list *p )
{
    printf("\nリストのひょうじ\n");
    while (p != NULL) { // 次ポインタがNULLまで処理
        printf("%3d %s\n", p->key, p->name);
        p = p->next;
    }
}

// コード、キー、名前の入力
int in_dt(int *key, char *name)
{
    int code;

    printf("次の処理コードを選択しなさい\n");
    printf("%d:リストの追加 %d:リストの削除 %d:処理終了\n", ADD, DEL, END);
    scanf("%d", &code );

    if (code == ADD) {
        printf("KEYを入力\n");
        scanf("%d", key);
        printf("名前を入力（MAX:19文字 )\n");
        scanf("%19s", name);
    }
    else if (code == DEL) {
        printf("KEYを入力\n");
        scanf("%d", key);
    }

    // 処理コードの返却
    return code;
}

// リストの開放
void free_list(struct list *p)
{
    struct list *p2;

    while (p != NULL) {     // 次ポインタがNULLまで処理
        p2 = p->next;
        free(p);
        p = p2;
    }
}