Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <cstdlib>
- using namespace std;
- struct dnode {
- int data;
- dnode *prev;
- dnode *next;
- dnode *child;
- };
- //Overwriting input and output stream.
- class Flatten {
- dnode* theNode=NULL;
- dnode* flattened=NULL;
- int listLength =0 ;
- public:
- //Constructor
- Flatten() {
- theNode = new dnode();
- theNode->data = 5;
- theNode->prev = NULL;
- dnode *n33 = new dnode();
- n33->data = 33;
- n33->prev = theNode;
- theNode->next = n33;
- dnode *n17 = new dnode();
- n17->data = 17;
- n17->prev = n33;
- n33->next = n17;
- dnode *n2 = new dnode();
- n2->data = 2;
- n2->prev=n17;
- n17->next = n2;
- dnode *n1 = new dnode();
- n1->data = 1;
- n1->prev= n2;
- n2->next = n1;
- n1->next = NULL;
- //second row
- dnode *n6 = new dnode();
- n6->data = 6;
- n6->prev = NULL;
- dnode *n25 = new dnode();
- n25->data = 25;
- n25->prev = n6;
- n6->next = n25;
- dnode *n60 = new dnode();
- n60->data = 60;
- n60->prev = n25;
- n25->next = n60;
- dnode *n20 = new dnode();
- n20->data = 20;
- n20->prev = n60;
- n60->next= n20;
- dnode *n7 = new dnode();
- n7->data = 7;
- n7->prev = n20;
- n20->next = n7;
- n7->next = NULL;
- //thrid row
- dnode *n8 = new dnode();
- n8->data = 8;
- n8->prev = NULL;
- n8->next = NULL;
- dnode *n9 = new dnode();
- n9->data = 9;
- n9->prev = n8;
- n9->next = NULL;
- dnode *n12 = new dnode();
- n12->data = 12;
- n12->prev = n9;
- dnode *n50 = new dnode();
- n50->data = 50;
- n50->prev = n12;
- n12->next = n50;
- n50->next = NULL;
- //Fourth Row
- dnode *n70 = new dnode();
- n70->data = 70;
- n70->prev = NULL;
- n70->next = NULL;
- dnode *n21 = new dnode();
- n21->data = 21;
- n21->prev = n70;
- dnode *n3 = new dnode();
- n3->data = 3;
- n3->prev = n21;
- n21->next = n3;
- n3->next = NULL;
- //Connecting children and parents
- theNode->child = n6;
- n2->child = n20;
- n25->child = n8;
- n60->child = n9;
- n20->child = n12;
- n9->child = n70;
- n12->child = n21;
- }
- dnode* wrapper(){
- dnode *flatFuturePrev = NULL;
- return flatten1(theNode, &flatFuturePrev);
- }
- dnode* flatten1(dnode* theNode, dnode** flatFuturePrev){
- while(theNode){
- if(theNode->child == NULL){
- if(flattened==NULL){
- flattened = new dnode();
- flattened->data = theNode->data;
- flattened->child = NULL;
- flattened->prev = NULL;
- *flatFuturePrev=flattened;
- }else{
- dnode *newNode = new dnode();
- newNode->data = theNode->data;
- newNode->prev = flattened;
- newNode->child = NULL;
- newNode->next=NULL;
- (*flatFuturePrev)->next=newNode;
- *flatFuturePrev = (*flatFuturePrev)->next;
- }
- }else{
- if(flattened==NULL) {
- flattened = new dnode();
- flattened->data = theNode->data;
- flattened->child = NULL;
- flattened->prev = NULL;
- *flatFuturePrev = flattened;
- flatten1(theNode->child, flatFuturePrev);
- }else{
- dnode *newNode = new dnode();
- newNode->data = theNode->data;
- newNode->prev = flattened;
- newNode->child = NULL;
- newNode->next=NULL;
- (*flatFuturePrev)->next=newNode;
- *flatFuturePrev = (*flatFuturePrev)->next;
- flatten1(theNode->child, flatFuturePrev);
- }
- }
- theNode = theNode->next;
- }
- return flattened;
- }
- void display(dnode* theNode) {
- dnode *initalNode = (dnode *) malloc(sizeof(dnode));
- initalNode->next = theNode;
- dnode *lastNode = initalNode;
- do {
- lastNode = lastNode->next;
- cout << "data is " << lastNode->data << endl;
- } while (lastNode->next != NULL);
- }
- };
- int main() {
- dnode *head = new dnode();
- head->data = 1;
- head->prev = NULL;
- head->child = NULL;
- dnode *n2 = new dnode();
- n2->data = 2;
- n2->prev = head;
- head->next = n2;
- n2->child = NULL;
- dnode *n3 = new dnode();
- n3->prev = n2;
- n3->data = 3;
- n2->next= n3;
- n3->child = NULL;
- n3->next = NULL;
- //second row
- dnode *n4 = new dnode();
- n4->data = 4;
- n4->prev = NULL;
- n4->child = NULL;
- dnode *n5 = new dnode();
- n5->data = 5;
- n5->prev = n4;
- n4->next = n5;
- n5->child = NULL;
- n5->next = NULL;
- n2->child = n4;
- Flatten *ll = new Flatten();
- try{
- int start=clock();
- cout << "Approach 1: Flattening... " << endl;
- dnode* flattened = ll->wrapper();
- ll->display(flattened);
- int stop=clock();
- cout << "calculated time of operation is " << stop-start << endl;
- }catch (const char *e){
- cout << "Exception Occured! " << e << endl << endl;
- }
- //Returns with no error.
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement