ในปัญหานี้ เราได้รับรายการเชื่อมโยงหลายระดับ งานของเราคือการสร้างโปรแกรมเพื่อเรียบรายการเชื่อมโยงหลายระดับ
การดำเนินการแบนจะดำเนินการในลักษณะที่โหนดระดับแรกจะเกิดขึ้นก่อนในรายการที่เชื่อมโยง จากนั้นโหนดระดับที่สองจะเกิดขึ้น
รายการที่เชื่อมโยงหลายระดับ เป็นโครงสร้างข้อมูลแบบหลายมิติ ซึ่งทุกโหนดของรายการที่เชื่อมโยงมีตัวชี้ลิงก์สองตัว ตัวหนึ่งเป็นลิงก์ไปยังโหนดถัดไป และอีกตัวหนึ่งไปยังรายการย่อยที่มีโหนดอย่างน้อยหนึ่งโหนด ตัวชี้ลูกนี้อาจหรือไม่ชี้ไปที่โหนดรายการอื่น
ตัวอย่าง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
ผลผลิต
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้อัลกอริธึมลำดับระดับการข้ามผ่าน เราจะข้ามผ่านรายการที่เชื่อมโยงโดยเริ่มจากโหนดแรกและข้ามผ่านโหนดทั้งหมดในระดับเดียวกัน หากมีตัวชี้ชายน์สำหรับโหนด ให้ย้ายไปยังจุดสิ้นสุดของรายการที่เชื่อมโยงปัจจุบันโดยใช้ส่วนท้าย จากนั้นดำเนินการข้ามผ่านแบบเดียวกันซ้ำๆ สำหรับแต่ละโหนดย่อยของรายการที่เชื่อมโยง โปรแกรมด้านล่างจะอธิบายตรรกะให้ละเอียดยิ่งขึ้น
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The flattened Linked List is 1 9 8 4 6 7 3 2 5
