Làm phẳng danh sách liên kết đa cấp trong C ++

Trong bài toán này, chúng tôi được cung cấp một danh sách liên kết đa cấp. Nhiệm vụ của chúng ta là tạo chương trình apro để làm phẳng danh sách liên kết đa cấp.

Hoạt động làm phẳng được thực hiện theo cách mà các nút cấp một sẽ xuất hiện đầu tiên trong danh sách được liên kết và sau đó các nút cấp hai sẽ xuất hiện.

Danh sách được liên kết đa cấp là một cấu trúc dữ liệu đa chiều, trong đó mỗi nút của danh sách liên kết có hai con trỏ liên kết, một con trỏ liên kết đến nút tiếp theo và một con trỏ tới danh sách con có một hoặc nhiều nút. Con trỏ con này có thể trỏ đến các nút danh sách khác hoặc không.

Ví dụ

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào

Đầu ra

1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là sử dụng loại thuật toán duyệt theo thứ tự cấp độ. Chúng tôi sẽ duyệt qua danh sách được liên kết bắt đầu từ nút đầu tiên và duyệt qua tất cả các nút ở cùng một cấp. Nếu bất kỳ con trỏ con nào là đại diện cho một nút, hãy di chuyển nó đến cuối danh sách được liên kết hiện tại bằng cách sử dụng con trỏ đuôi. Sau đó, thực hiện đệ quy cùng một lần duyệt cho mỗi nút con của danh sách được liên kết. Chương trình dưới đây sẽ giải thích logic tốt hơn.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#include <bits/stdc++.h>
using namespace std;

#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))

class Node{
   public:
   int data;
   Node *next;
   Node *child;
};
Node *createList(int *arr, int n){
   Node *head = NULL;
   Node *p;
   int i;
   for (i = 0; i < n; ++i){
      if (head == NULL)
         head = p = new Node();
      else{
         p->next = new Node();
         p = p->next;
      }
      p->data = arr[i];
      p->next = p->child = NULL;
   }
   return head;
}
Node *createList(void){
   int arr1[] = {1, 9, 8, 4, 6};
   int arr2[] = {7, 3, 2};
   int arr3[] = {5};
   Node *head1 = createList(arr1, (sizeof(arr1)/sizeof(arr1[0])));
   Node *head2 = createList(arr2, (sizeof(arr2)/sizeof(arr2[0])));
   Node *head3 = createList(arr3, (sizeof(arr3)/sizeof(arr3[0])));
   head1->child = head2;
   head1->next->child = head3;
   return head1;
}
void flattenLinkedList(Node *head){
   if (head == NULL)
   return;
   Node *tmp;
   Node *tail = head;
   while (tail->next != NULL)
   tail = tail->next;
   Node *cur = head;
   while (cur != tail){
      if (cur->child){
         tail->next = cur->child;
         tmp = cur->child;
         while (tmp->next)
         tmp = tmp->next;
         tail = tmp;
      }
      cur = cur->next;
   }
}
int main(void){
   Node *head = NULL;
   head = createList();
   flattenLinkedList(head);
   cout<<"The flattened Linked List is ";
   while (head != NULL){
      cout << head->data << " ";
      head = head->next;
   }
   return 0;
}

Đầu ra

The flattened Linked List is 1 9 8 4 6 7 3 2 5