Index

C++の壺・リスト篇

　C++の基本テクニックのTipsです。リスト篇では、自己参照構造体とリスト構造の基礎知識を扱っています。また、双方向リストの簡単なサンプルを紹介しています。

[INDEX]	・リスト構造	::　自己参照構造体 / リスト構造 / 双方向リスト
	・データの追加と挿入	::　データの追加 / データの挿入 / データのクリア
	・データの削除	::　データの削除 / データ数の取得

sasaraan programming

Exposition

●リスト構造

　自己参照構造体とは、みずからの構造体へのポインタをメンバにもつ構造体です。また、同じ自己参照構造体を次々と連結させて、配列のようにするのがリスト構造です。自己参照構造体は、前のデータや後ろのデータのアドレスを格納しておくので、リスト構造では、データの挿入や削除の際、これらのアドレスを書き換えるだけで済み、以降のデータを移動させる必要がなくなります。さらに、データの個数を気にせず、容易にデータを増減させることができます。

// 自己参照構造体
struct xdata {
　　char name[64];
　　xdata* prev;　　// 前のデータへのポインタ
　　xdata* next;　　// 次のデータへのポインタ
};

　下図は、リスト構造のひとつである双方向リストの例です。各データには、前のデータと後ろのデータのアドレスを格納できるようになっており、順番にデータにアクセスすることができます。これを、前のみ (prev) 、あるいは後ろのみ (next) に限ったものは単方向リストと呼ばれます。双方向リスト

　この例では、先頭のデータの prev メンバに NULL を入れることによって先頭データであることを表しています。逆に、末尾のデータには next メンバに NULL を入れるようにしています。先頭データの prev メンバに末尾データのアドレスを、末尾データの next メンバに先頭データのアドレスを入れると、無限チェーンとなります。
単方向リストとチェーンリスト

●データの追加と挿入

　多くの双方向リストでは、コーディングや管理が容易になることから、先頭データを固定することが多いようです。下記サンプルでもダミーのデータ (base) を用意して先頭データ (pList) に設定しています。今回の例では、ダミーデータは実データとしては使用していませんが、データの挿入や削除で位置が移動したり削除されたりすることはありません。
　データの追加は、このダミーデータの後ろに行います。add 関数では、データの末尾にポインタを移動し、データを追加しています。また、挿入 (insert 関数) は、指定位置（先頭からの位置）にデータを挿入するようにしています。いずれも、前後のデータがあれば、それらの prev / next メンバの値を再設定し、連結の付け替えを行う必要があります。

　また、先頭データの prev メンバを NULL に、末尾データの next メンバを NULL に設定することで、先頭と末尾のデータを明確にしています。下例の main 関数では、データを四つ追加して、さらに三番目の位置にデータを挿入しています。これらのデータは、削除の際にメモリを解放できるように new 演算子を使って動的に作成しています。この時、new 演算子で作成したオブジェクトは delete 演算子で削除する必要がありますので注意が必要です。

// データの追加と挿入
#include <stdio.h>     // printf
#include <string.h>    // strcpy
#include <conio.h>    // getch

// 構造体
struct xdata {
    char name[64];
    xdata* prev;
    xdata* next;
};

// 関数プロトタイプ
xdata* add(xdata*, char*);        // 追加
xdata* insert(xdata*, int, char*); // 挿入
void clear(xdata*);        // クリア（全消去）

// main 関数
void main() {
    xdata base = {"", NULL, NULL}; // ダミー 
    xdata* pList = &base; // 先頭位置（固定）
    xdata* pCur = NULL;  // 現在位置（変動）

    // データの追加
    add(pList, "Renoir");
    add(pList, "Matisse");
    add(pList, "Picasso");
    add(pList, "Chagall");

    // データの挿入
    insert(pList, 3, "Monet");

    // データの表示
    pCur = pList;
    while (pCur->next) {
        pCur = pCur->next;
        printf ("%s\n", pCur->name);
    }

    // データの並び : 
    // 0.ダミー...1.Renoir...2.Mattice...
    // 3.Monet...4.Picasso...5.Chagall

    // データのクリア
    clear(pList);
    if (getch()) return;
}

// データを末尾に追加
xdata* add(xdata* list, char* name) {
    // ポインタを末尾に移動
    while (list->next) list = list->next;

    // データの付け替え
    xdata* data = new xdata;
    list->next = data;
    data->prev = list;
    data->next = NULL;
    strcpy(data->name, name);

    return data;  // 新データのアドレスを返す
}

// データを途中に挿入
xdata* insert(xdata* list, int n, char* name) {
    // 0以下は1（ダミーの位置=0を回避）
    if (n <= 0) n = 1;

    // ポインタを挿入位置に移動
    while (n--) {
        if (!list->next) return NULL;
        list = list->next;
    }

    // データの付け替え
    xdata* data = new xdata;
    (list->prev)->next = data;
    data->prev = list->prev;
    data->next = list;
    list->prev = data;
    strcpy(data->name, name);

    return data;  // 新データのアドレスを返す
}

// データを全消去（最初のダミーは残る）
void clear(xdata* list) {
    xdata* curr = list->next;
    while (curr) {
        xdata* next = curr->next; 
        delete curr;
        curr = next;
    }
    list->next = NULL;
}

●データの削除

　データのクリア (clear, 前節) や削除 (cut) では、先頭のダミーデータを削除しないようにする必要があります。この時、削除するデータの前後のデータの有無を調べ、存在すれば、prev / next メンバを再設定して連結を付け替えなければなりません。

... （略） ...
bool cut(xdata*, int);    // 削除
int getlen(xdata*);      // データ数
... （略） ...

// main 関数
void main() {
    xdata base = {"", NULL, NULL};
    xdata* pList = &base;

    // データの追加と挿入	
    add(pList, "Renoir");
    add(pList, "Matisse");
    add(pList, "Picasso");
    add(pList, "Chagall");
    insert(pList, 3, "Monet");

    // データ数の表示 = 5
    printf("データ数 : %d\n", getlen(pList));

    // データの削除（3番目="Monet"）
    cut(pList, 3);

    // データ数の表示 = 4
    printf("データ数 : %d\n", getlen(pList));

    // データのクリア
    clear(pList);

    // データ数の表示 = 0
    printf("データ数 : %d\n", getlen(pList));
    if (getch()) return;
}

// データの削除（ダミー=0は削除しない）
bool cut(xdata* list, int n) {
    // 0以下は処理を中止
    if (n <= 0) return false;

    // 削除位置までポインタを進める
    while (n--) {
        if (!list->next) return false;
        list = list->next;
    }

    // データの付け替え
    if (list->prev) {
        (list->prev)->next = list->next;
    } 
    if (list->next) {
        (list->next)->prev = list->prev;
    }

    // データの削除
    delete list;
    return true;  // 削除後はtrueを返す
}

// データ数の取得（ダミーは数えない）
int getlen(xdata* list) {
    int n = 0;
    while (list->next) {
        list = list->next;
        n++;
    }
    return n;
}