【C言語】mallocとreallocで作る可変長配列 ― 図書館システムの実装例で解説

問題概要

図書館でのさまざまな操作を記録・照会する図書館管理システムを構築することになったとしましょう。ここで、次の3つのコマンドを実装するよう求められています。

• コマンド1：棚xにyページの本を挿入したことを記録する。
• コマンド2：棚xにあるy番目の本のページ数を出力する。
• コマンド3：棚xにある本の総冊数を出力する。

コマンドは「{コマンド種別, x, y}」という形式の2次元配列として与えられ、yの値がない場合は0がデフォルト値として使われます。そして、与えられたコマンドの実行結果を出力します。

入出力の例

たとえば、棚の数が4、クエリの数が4、入力配列が{{1, 3, 23}, {1, 4, 128}, {2, 3, 0}, {3, 4, 0}}である場合、出力は次のようになります。

23
1

この結果は、次のように解釈できます。

• クエリ1（{1, 3, 23}）：棚3に23ページの本を挿入する。
• クエリ2（{1, 4, 128}）：棚4に128ページの本を挿入する。
• クエリ3（{2, 3, 0}）：棚3の0番目（先頭）の本のページ数を出力する → 23
• クエリ4（{3, 4, 0}）：棚4の本の冊数を出力する → 1

解決のためのアルゴリズム

この問題は、次の手順で解決できます。

1. サイズsの整数配列bを新しく確保する。これは各棚の本の冊数を保持します。
2. サイズsのポインタ配列pを新しく確保する。これは各棚のページ数を格納する可変長配列へのポインタを保持します。
3. iを0からs未満まで1ずつ増やしながら、b[i]を0で初期化し、p[i]に新しい配列を割り当てる。
4. loopCountを0からq未満まで1ずつ増やしながら、以下を繰り返す。
   • qtypeにq_array[loopCount][0]の値を代入する。
   • qtypeが1の場合：xとyにq_array[loopCount][1]、q_array[loopCount][2]を代入し、b[x]を1増やした後、p[x]をrealloc()でb[x]個分のint型サイズに拡張して、p[x][b[x] - 1]にyを代入する。
   • qtypeが2の場合：xとyを同様に取得し、p[x][y]の値を出力する。
   • それ以外の場合：xを取得し、b[x]の値を出力する。
5. bがNULLでなければ、free()でそのメモリを解放する。
6. iを0からs未満まで1ずつ増やしながら、p[i]がNULLでなければそのメモリを解放する。
7. pがNULLでなければ、そのメモリを解放する。

C言語による実装例

理解を深めるために、以下の実装例を見てみましょう。

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

void solve(int s, int q, int q_array[][3])
{
    int* b;
    int** p;
    b = (int*)malloc(sizeof(int)*s);
    p = (int**)malloc(sizeof(int*)*s);
    for(int i = 0; i < s; i++)
    {
        b[i] = 0;
        p[i] = (int*)malloc(sizeof(int));
    }
    int loopCount;
    for(loopCount = 0; loopCount < q; loopCount++)
    {
        int qtype;
        qtype = q_array[loopCount][0];
        if (qtype == 1)
        {
            int x, y;
            x = q_array[loopCount][1];
            y = q_array[loopCount][2];
            b[x] += 1;
            p[x] = realloc(p[x], b[x]*sizeof(int));
            p[x][b[x] - 1] = y;
        }
        else if (qtype == 2)
        {
            int x, y;
            x = q_array[loopCount][1];
            y = q_array[loopCount][2];
            printf("%d\n", p[x][y]);
        }
        else
        {
            int x;
            x = q_array[loopCount][1];
            printf("%d\n", b[x]);
        }
    }
    if (b)
        free(b);
    for (int i = 0; i < s; i++)
        if (p[i])
            free(p[i]);
    if (p)
        free(p);
}
int main() {
    int input_arr[][3] = {{1, 3, 23}, {1, 4, 128}, {2, 3, 0}, {3, 4, 0}};
    solve(4, 4, input_arr);
}

入力

int input_arr[][3] = {{1, 3, 23}, {1, 4, 128}, {2, 3, 0}, {3, 4, 0}};
solve(4, 4, input_arr);

出力

23
1

ポイント解説：mallocとreallocによる可変長配列

このプログラムの核心は、標準ライブラリのmalloc()とrealloc()を使った動的メモリ管理にあります。

• malloc()：必要な初期メモリをヒープ領域から確保します。ここでは棚の数sに応じて、冊数カウンタ用の配列bと、ページ数配列へのポインタ配列pを確保しています。
• realloc()：既に確保済みのメモリブロックのサイズを変更します。本を1冊追加するたびにp[x]の領域を1要素分拡張することで、最大冊数を事前に決めなくても可変長配列として扱えます。
• free()：使い終わったメモリは必ず解放します。これによりメモリリークを防ぎます。

なお、本を追加するたびに毎回realloc()を呼び出す方式はシンプルですが、再確保が頻発するとパフォーマンスが低下する可能性があります。実務では容量を倍々に増やすなど、再確保の回数を抑える工夫をするのが一般的です。