【C++】再帰を使って2次元マトリックスから2Dリンクリストを作成する方法

行列(マトリックス)が与えられたとき、再帰的なアプローチを用いて、それを2Dリンクリストへ変換する方法を解説します。

ここで作成するリストの各ノードは、right(右方向)ポインタとdown(下方向)ポインタの2つのポインタを持ちます。rightポインタは同じ行の次の要素を、downポインタは同じ列の一つ下の行の要素を指します。

問題の概要

例えば、次のような3×3の行列が入力として与えられたとします。

この場合、出力は次のようになります。各要素がノードとなり、横方向はrightポインタ、縦方向はdownポインタによって連結された、格子状のデータ構造が生成されます。

解決手順

この問題は、以下の手順で解くことができます。

• 関数 make_2d_list() を定義します。引数として、行列 mat、現在の位置 i・j、行数 m、列数 n を受け取ります。

• i または j が行列の境界外にある場合は、NULL を返します。(これが再帰の終了条件となります)

• mat[i][j] の値を持つ新しいノード temp を作成します。

• temp のrightポインタに、make_2d_list(mat, i, j + 1, m, n) の戻り値を設定します。(同じ行の右隣の要素への連結)

• temp のdownポインタに、make_2d_list(mat, i + 1, j, m, n) の戻り値を設定します。(同じ列の下の要素への連結)

• temp を返します。

C++による実装例

それでは、実際のC++コードを見て、動作をより深く理解していきましょう。

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
    public:
    int data;
    TreeNode *right, *down;
    TreeNode(int d){
        data = d;
        right = down = NULL;
    }
};
void show_2d_list(TreeNode* head) {
    TreeNode *right_ptr, *down_ptr = head;
    while (down_ptr) {
        right_ptr = down_ptr;
        while (right_ptr) {
            cout << right_ptr->data << " ";
            right_ptr = right_ptr->right;
        }
        cout << endl;
        down_ptr = down_ptr->down;
    }
}
TreeNode* make_2d_list(int mat[][3], int i, int j, int m, int n) {
    if (i > n - 1 || j > m - 1)
        return NULL;
    TreeNode* temp = new TreeNode(mat[i][j]);
    temp->right = make_2d_list(mat, i, j + 1, m, n);
    temp->down = make_2d_list(mat, i + 1, j, m, n);
    return temp;
}
int main() {
    int m = 3, n = 3;
    int mat[][3] = {
        { 10, 20, 30 },
        { 40, 50, 60 },
        { 70, 80, 90 } };
    TreeNode* head = make_2d_list(mat, 0, 0, m, n);
    show_2d_list(head);
}

このコードでは、まずデータと2つのポインタ(right・down)を持つ TreeNode クラスを定義しています。show_2d_list() 関数は、生成された2Dリンクリストを先頭ノードから行単位で出力するための補助関数です。main() 関数内では、左上の要素 (0, 0) を起点として make_2d_list() を呼び出すことで、行列全体が再帰的にリンクされていきます。

入力

{ { 10, 20, 30 },
{ 40, 50, 60 },
{ 70, 80, 90 } }

出力

10 20 30
40 50 60
70 80 90

まとめ

このアルゴリズムでは、各ノードに対して右方向と下方向の再帰呼び出しを行うことで、行列全体を一度の走査で2Dリンクリストへ変換できます。時間計算量はノードの総数分となるため O(m×n)、空間計算量も生成するノード数に比例して O(m×n) となります。画像データやスプレッドシートのように、二次元的な構造をそのまま連結リストで表現したい場合に役立つテクニックです。