C言語033 リスト構造 : プログラミング指南

今回は C# や Z80 アセンブラでの活用方法を解説しているリスト構造です。前回、動的メモリ確保を解説しましたので、ようやく C言語でもリスト構造を解説できる下地が出来ました。それでは早速説明していきましょう。
--
いきなりここに飛んで来ちゃった人は、よろしければ下記からご覧ください。
C言語基礎講座インデックス

基本構造

リスト構造に関しては既に過去2度にわたり解説しています。

原理の細かい説明は、上記のリンク先でご確認ください。簡単に言うと、確保したメモリをポインタアドレスを繋げていく事で管理する手法です。次のポインタが NULL になったらリストは終了となります。

今回は画面に星をランダムに表示したり消したりするサンプルで説明していきます。まずは構造体を定義します。


/// <summary>
/// 星の構造体
/// </summary>
struct _SStar
{
    struct _SStar* pNext;   // 次のポインタ
    int PosX;               // X座標
    int PosY;               // Y座標
    int Color;              // 色番号 1-7
};
typedef struct _SStar SStar;

pNext メンバ変数がリストを繋げるポインタとなります。グローバル変数として、リストの先頭を用意します。


/// <summary>
/// 星管理リスト
/// </summary>
SStar* g_pStar = NULL;

g_pStar に動的に確保した星の構造体変数を繋げていきます。

リストに追加する

今回は複雑なことはしませんので、ダイレクトに AddStar() という関数を作ってしまいます。この関数は一度呼ばれる度に、g_pStar に新たに星をひとつ、画面枠内の座標範囲で追加します。座標に関しては重なりチェックはしていませんので、途中で消えてしまう事があります。そのため、追加の度に全て書き直すようにしてみました。

まずは全ての星の表示です。リストを追いかけていくだけです。


/// <summary>
/// 星を全て再表示する
/// </summary>
void PrintStar()
{
    for (SStar* ptr = g_pStar; ptr; ptr = ptr->pNext)
    {
        printf(LOCATE, ptr->PosY, ptr->PosX);
        printf("\x1b[3%dm*", ptr->Color);
    }
}

次に星の追加です。色は 1-7、XY座標はそれぞれ 1-80, 1-25 という範囲でランダムに生成することにしました。


/// <summary>
/// リストに星を追加
/// </summary>
bool AddStar()
{
    SStar* star = (SStar*)malloc(sizeof(SStar));
    if (!star) return false;
    star->Color = (rand() % 7) + 1;
    star->PosX = (rand() % 80) + 1;
    star->PosY = (rand() % 25) + 1;

    // 新規追加対象を先頭に追加
    star->pNext = g_pStar;
    g_pStar = star;

    // 新規表示対象を表示
    PrintStar();
    return true;
}

ポイントとしては、動的にメモリ確保した構造体変数の pNext に現在のリスト先頭ポインタを代入している点です。これで新規に確保した変数の次が、今までの先頭になりましたので、新規に確保した変数を新しい先頭ポインタとして g_pStar に代入するだけで、リストが繋がっています。後方にぶら下げる（追加する）よりも簡単です。

【Amazon】
Western Digital ウエスタンデジタル WD BLACK M.2 SSD 内蔵ヒートシンク搭載 2TB NVMe PCIe Gen4 x4 (読取り最大 7300MB/s 書込み最大 6600MB/s) WDS200T2XHE-EC SN850X 【国内正規取扱代理店】

WESTERN DIGITAL

2022-09-09

※ M.2 SSD Gen4 2TB で2万円とちょっと。ここまで来ると、PCにHDDを選択する気にならないですね。

Western Digital ウエスタンデジタル WD BLACK M.2 SSD ヒートシンク搭載 2TB NVMe PCIe Gen4x4 ( 読取り最大 7300MB/s 書込み最大 6600MB/s ) PS5 ゲーミング PC メーカー保証5年 WDS200T2XHE SN850X 【国内正規取扱代理店】

【楽天】
Western Digital ウエスタンデジタル WD BLACK M.2 SSD ヒートシンク搭載 2TB NVMe PCIe Gen4x4 ( 読取り最大 7300MB/s 書込み最大 6600MB/s ) PS5 ゲーミング PC メーカー保証5年 WDS200T2XHE SN850X 【国内正規取扱代理店】

リストから削除する

削除する場合ですが、新規に追加しているのが先頭なので、先頭から削除してしまうと他の星が全く変化しません。そこで最後尾の星を削除することにします。考え方としては最後尾は pNext が NULL の構造体変数なので、そこまで追いかけていき、その一つ手前が最終とします。そして、最終位置の変数は free 関数により OS に返却します。


/// <summary>
/// リストから最後のデータを削除
/// </summary>
void RemoveStar()
{
    // リストがなければ終了
    SStar* ptr = g_pStar;
    if (!ptr) return;

    // 最後尾のデータまで移動
    SStar* prev = NULL;
    while (ptr->pNext)
    {
        prev = ptr;
        ptr = ptr->pNext;
    }

    // リストを繋ぎ変える
    if (prev)
    {
        prev->pNext = ptr->pNext;
    }
    else
    {
        g_pStar = ptr->pNext;
    }

    // 対象を削除
    printf(LOCATE, ptr->PosY, ptr->PosX);
    printf(" ");
    free(ptr);
}

リストの繋ぎ変えの部分ですが、実は ptr->pNext は常に NULL なので、ここは定数として NULL の代入でも全く問題ないのですが、任意の位置の削除にも対応できるように、ptr->pNext の値（つまりは次に繋がるポインタ）を代入するようにしています。

動作テスト

これでリスト構造の動作テストは実装できましたので、実際に動作させるためのメイン処理を作成します。


/// <summary>
/// メイン関数
/// </summary>
/// <returns>終了コード</returns>
int main(void)
{
    const int max = 50;

    // 最初に全て星を配置する
    srand((unsigned)time(NULL));
    for (int i = 0; i < max; ++i)
    {
        AddStar();
    }

    // [Esc]が押されるまで星の削除と追加を繰り返す
    while (true)
    {
        if (_kbhit() && _getch() == 0x1b) break;
        RemoveStar();
        AddStar();
        Sleep(20);
    }

    // 登録されている全ての星の削除する
    while (g_pStar)
    {
        RemoveStar();
    }

    printf(ATBCLEAR);
    printf(SCRCLEAR);
    printf(LOCATE, 1, 1);
    return EXIT_SUCCESS;
}

星の最大数を max 定数で定義しておきました。これで max を変更すれば好きなだけ星を出すことが出来ます（限界はあります）。最初に全てドンッと定義してから、20ms毎に一つずつ星が変化していきます。

ループで [Esc]キーが押されたかの判定をしています。このキーが押されたら、ループを終了します。リストに登録されている全ての構造体変数メモリを free で OS に返却します。その後画面を初期化して終了です。

これが C言語でリスト構造を実装する基本となります。この例だと、毎回メモリの確保と開放という処理が走りますので、メモリの断片化が起きるかもしれませんし、また、実行速度的にもあまり好ましいとは思えません。そこで次回は、自分でメモリを管理する手法について解説します。