২D ম্যাট্রিক্স থেকে লিঙ্কড লিস্ট তৈরি করা C++-তে (ইটারেটিভ পদ্ধতি)

সমস্যা বিবরণ

একটি ২D ম্যাট্রিক্স দেওয়া আছে। আমাদের এটি একটি ২D লিঙ্কড লিস্টে রূপান্তর করতে হবে ইটারেটিভ (লুপ-ভিত্তিক) পদ্ধতিতে। প্রতিটি নোডের right এবং down পয়েন্টার থাকবে।

ইটারেটিভ অ্যালগরিদম

1. real_head = NULL এবং সাইজ m-এর একটি অ্যারে head_arr সংজ্ঞায়িত করুন।
2. প্রতিটি সারি i (০ থেকে m-1) এর জন্য:
   • head_arr[i] = NULL।
   • প্রতিটি কলাম j (০ থেকে n-1) এর জন্য:
     • mat[i][j] মান দিয়ে নতুন নোড p তৈরি করুন।
     • যদি real_head খালি হয়, তবে real_head = p।
     • যদি head_arr[i] খালি হয়, তবে head_arr[i] = p (সারির প্রথম নোড)।
     • অন্যথায়, right_ptr->right = p (পূর্বের নোডের সাথে লিঙ্ক)।
     • right_ptr = p আপডেট করুন।
3. সকল সারি তৈরি হলে, প্রতিটি সারির নোডগুলকে নিচের সারির সাথে লিঙ্ক করুন:
   • i = 0 থেকে m-2 পর্যন্ত:
     • p = head_arr[i], q = head_arr[i+1]।
     • যখন p এবং q দুটোই NULL না হয়:
       • p->down = q।
       • p = p->right, q = q->right।
4. real_head রিটার্ন করুন।

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 m, int n) {
    TreeNode* real_head = NULL;
    TreeNode* head_arr[m];
    TreeNode *right_ptr, *p;

    for (int i = 0; i < m; i++) {
        head_arr[i] = NULL;
        for (int j = 0; j < n; j++) {
            p = new TreeNode(mat[i][j]);
            if (!real_head) real_head = p;
            if (!head_arr[i]) head_arr[i] = p;
            else right_ptr->right = p;
            right_ptr = p;
        }
    }

    for (int i = 0; i < m - 1; i++) {
        TreeNode *p = head_arr[i], *q = head_arr[i + 1];
        while (p && q) {
            p->down = q;
            p = p->right;
            q = q->right;
        }
    }
    return real_head;
}

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, m, n);
    show_2d_list(head);
    return 0;
}

আউটপুট

10 20 30
40 50 60
70 80 90