Tạo danh sách liên kết từ ma trận 2D (Phương pháp tiếp cận lặp lại) trong C ++

Giả sử chúng ta có một ma trận, chúng ta phải chuyển nó thành danh sách liên kết 2d bằng cách sử dụng phương pháp lặp lại. Danh sách sẽ có con trỏ bên phải và con trỏ xuống.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• real_head:=NULL

• Xác định head_arr mảng có kích thước:m.

• để khởi tạo i:=0, khi i

  • head_arr [i]:=NULL

  • để khởi tạo j:=0, khi j

    • p:=nút cây mới với mat giá trị [i, j]

    • nếu real_head là null, thì -

      • real_head:=p

    • nếu head_arr [i] là null, thì -

      • head_arr [i]:=p

    • Nếu không

      • quyền của right_ptr:=p

    • right_ptr:=p

• để khởi tạo i:=0, khi tôi

  • p:=head_arr [i], q =head_arr [i + 1]

  • while (p và q đều không rỗng), do -

    • xuống của p:=q

    • p:=right of p

    • q:=bên phải của q

• trả về real_head

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

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

Đầu ra

10 20 30
40 50 60
70 80 90