Embedded Files
Problem
Start with a standard doubly-linked list. Now imagine that in addition to next and previous pointers, each element has a child pointer, which may or may not point to a separate doubly-linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure
Flatten the list so that all the nodes appear in a single-level, doubly-linked list. You are given the head and tail of the first level of the list.
Unflatten the list. Restore the data structure to its original condition before it was passed to FlattenList.
Solution
#include <iostream>
using namespace std;
typedef struct doubly_linked_node{
int data;
struct doubly_linked_node *prev;
struct doubly_linked_node *next;
struct doubly_linked_node *child;
}DLNode;
DLNode* create_node(int data)
{
DLNode *p = new DLNode;
if(p != NULL){
p->data = data;
p->prev = NULL;
p->next = NULL;
p->child = NULL;
}
return p;
}
DLNode *add_child(DLNode* node, int data)
{
DLNode *p = create_node(data);
node->child = p;
return p;
}
DLNode *add_node(DLNode** head, int data)
{
DLNode *p = create_node(data);
if(*head == NULL){
*head = p;
return p;
}
DLNode *p1 = *head;
while(p1->next != NULL){
p1 = p1->next;
}
p1->next = p;
p->prev = p1;
return p;
}
void print_flatten_list(DLNode *head){
DLNode *p = head;
while(p){
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
DLNode * flatten_list(DLNode *head)
{
DLNode *p, *phead, *phead1, *ptail, *ptail1, *pchild;
p = head;
while(p->next){
p = p->next;
}
phead = head;
ptail = p;
while(phead->next != NULL){
if(phead->child != NULL){
ptail->next = phead->child;
phead->child->prev = ptail;
while(ptail->next != NULL){
ptail = ptail->next;
}
}
phead = phead->next;
}
return head;
}
DLNode* deflatten_list(DLNode *head)
{
DLNode *p, *p1;
p = head;
while(p != NULL){
if(p->child != NULL){
p1 = p->child;
if(p1->prev != NULL){
p1->prev->next = NULL;
p1->prev = NULL;
}
deflatten_list(p1);
}
p = p->next;
}
return head;
}
void print_deflatten_list(DLNode *head)
{
DLNode *p = head;
while(p != NULL){
cout << p->data << " ";
if(p->child != NULL){
cout << endl;
print_deflatten_list(p->child);
}
p = p->next;
}
cout << endl;
}
int main(int argc, char* argv[])
{
DLNode *head = NULL, *head1, *tail, *tail1, *child;
tail = add_node(&head, 1);
head1 = add_child(head, 6);
tail1 = add_node(&head1, 7);
add_child(tail1, 11);
tail1 = add_node(&head1, 8);
child = add_child(tail1, 12);
add_child(child, 15);
tail = add_node(&head, 2);
tail = add_node(&head, 3);
tail = add_node(&head, 4);
add_node(&head, 5);
head1 = add_child(tail, 9);
add_node(&head1, 10);
child = add_child(head1, 13);
add_node(&child, 14);
child = add_child(child, 16);
add_node(&child, 17);
cout << "before flatten " << endl;
print_deflatten_list(head);
cout << "after flatten" << endl;
flatten_list(head);
print_flatten_list(head);
cout << "after deflatten " << endl;
deflatten_list(head);
print_deflatten_list(head);
return 0;
}
Output
before flatten
1
6 7
11
8
12
15
2 3 4
9
13
16 17
14
10
5
after flatten
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
after deflatten
1
6 7
11
8
12
15
2 3 4
9
13
16 17
14
10
5
Page updated
Google Sites
Report abuse