SHARE
TWEET

Untitled

a guest Sep 13th, 2017 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdlib>
  4.  
  5. using namespace std;
  6.  
  7. struct dnode {
  8.     int data;
  9.     dnode *prev;
  10.     dnode *next;
  11.     dnode *child;
  12. };
  13.  
  14. //Overwriting input and output stream.
  15. class Flatten {
  16.     dnode* theNode=NULL;
  17.     dnode* flattened=NULL;
  18.     int listLength =0 ;
  19. public:
  20.     //Constructor
  21.     Flatten() {
  22.         theNode = new dnode();
  23.         theNode->data = 5;
  24.         theNode->prev = NULL;
  25.  
  26.         dnode *n33 = new dnode();
  27.         n33->data = 33;
  28.         n33->prev = theNode;
  29.         theNode->next = n33;
  30.  
  31.         dnode *n17 = new dnode();
  32.         n17->data = 17;
  33.         n17->prev = n33;
  34.         n33->next = n17;
  35.  
  36.         dnode *n2 = new dnode();
  37.         n2->data = 2;
  38.         n2->prev=n17;
  39.         n17->next = n2;
  40.  
  41.         dnode *n1 = new dnode();
  42.         n1->data = 1;
  43.         n1->prev= n2;
  44.         n2->next = n1;
  45.         n1->next = NULL;
  46.  
  47.  
  48.         //second row
  49.         dnode *n6 = new dnode();
  50.         n6->data = 6;
  51.         n6->prev = NULL;
  52.  
  53.         dnode *n25 = new dnode();
  54.         n25->data = 25;
  55.         n25->prev = n6;
  56.         n6->next = n25;
  57.  
  58.         dnode *n60 = new dnode();
  59.         n60->data = 60;
  60.         n60->prev = n25;
  61.         n25->next = n60;
  62.  
  63.         dnode *n20 = new dnode();
  64.         n20->data = 20;
  65.         n20->prev = n60;
  66.         n60->next= n20;
  67.  
  68.         dnode *n7 = new dnode();
  69.         n7->data = 7;
  70.         n7->prev = n20;
  71.         n20->next = n7;
  72.         n7->next = NULL;
  73.  
  74.  
  75.         //thrid row
  76.         dnode *n8 = new dnode();
  77.         n8->data = 8;
  78.         n8->prev = NULL;
  79.         n8->next = NULL;
  80.  
  81.         dnode *n9 = new dnode();
  82.         n9->data = 9;
  83.         n9->prev = n8;
  84.         n9->next = NULL;
  85.  
  86.         dnode *n12 = new dnode();
  87.         n12->data = 12;
  88.         n12->prev = n9;
  89.  
  90.  
  91.         dnode *n50 = new dnode();
  92.         n50->data = 50;
  93.         n50->prev = n12;
  94.         n12->next = n50;
  95.         n50->next = NULL;
  96.  
  97.         //Fourth Row
  98.         dnode *n70 = new dnode();
  99.         n70->data = 70;
  100.         n70->prev = NULL;
  101.         n70->next = NULL;
  102.  
  103.         dnode *n21 = new dnode();
  104.         n21->data = 21;
  105.         n21->prev = n70;
  106.  
  107.  
  108.         dnode *n3 = new dnode();
  109.         n3->data = 3;
  110.         n3->prev = n21;
  111.         n21->next = n3;
  112.         n3->next = NULL;
  113.  
  114.  
  115.         //Connecting children and parents
  116.         theNode->child = n6;
  117.         n2->child = n20;
  118.         n25->child = n8;
  119.         n60->child = n9;
  120.         n20->child = n12;
  121.         n9->child = n70;
  122.         n12->child = n21;
  123.     }
  124.  
  125.     dnode* wrapper(){
  126.         dnode *flatFuturePrev = NULL;
  127.         return flatten1(theNode, &flatFuturePrev);
  128.     }
  129.  
  130.     dnode* flatten1(dnode* theNode, dnode** flatFuturePrev){
  131.         while(theNode){
  132.             if(theNode->child == NULL){
  133.                 if(flattened==NULL){
  134.                     flattened = new dnode();
  135.                     flattened->data = theNode->data;
  136.                     flattened->child = NULL;
  137.                     flattened->prev = NULL;
  138.                     *flatFuturePrev=flattened;
  139.                 }else{
  140.                     dnode *newNode = new dnode();
  141.                     newNode->data = theNode->data;
  142.                     newNode->prev = flattened;
  143.                     newNode->child = NULL;
  144.                     newNode->next=NULL;
  145.                     (*flatFuturePrev)->next=newNode;
  146.                     *flatFuturePrev = (*flatFuturePrev)->next;
  147.                 }
  148.             }else{
  149.                 if(flattened==NULL) {
  150.                     flattened = new dnode();
  151.                     flattened->data = theNode->data;
  152.                     flattened->child = NULL;
  153.                     flattened->prev = NULL;
  154.                     *flatFuturePrev = flattened;
  155.                     flatten1(theNode->child, flatFuturePrev);
  156.                 }else{
  157.                     dnode *newNode = new dnode();
  158.                     newNode->data = theNode->data;
  159.                     newNode->prev = flattened;
  160.                     newNode->child = NULL;
  161.                     newNode->next=NULL;
  162.                     (*flatFuturePrev)->next=newNode;
  163.                     *flatFuturePrev = (*flatFuturePrev)->next;
  164.                     flatten1(theNode->child, flatFuturePrev);
  165.                 }
  166.             }
  167.             theNode = theNode->next;
  168.         }
  169.         return flattened;
  170.     }
  171.  
  172.     void display(dnode* theNode) {
  173.         dnode *initalNode = (dnode *) malloc(sizeof(dnode));
  174.         initalNode->next = theNode;
  175.         dnode *lastNode = initalNode;
  176.         do {
  177.             lastNode = lastNode->next;
  178.             cout << "data is " << lastNode->data << endl;
  179.         } while (lastNode->next != NULL);
  180.     }
  181. };
  182.  
  183. int main() {
  184.     dnode *head = new dnode();
  185.     head->data = 1;
  186.     head->prev = NULL;
  187.     head->child = NULL;
  188.  
  189.     dnode *n2 = new dnode();
  190.     n2->data = 2;
  191.     n2->prev = head;
  192.     head->next = n2;
  193.     n2->child = NULL;
  194.  
  195.     dnode *n3 = new dnode();
  196.     n3->prev = n2;
  197.     n3->data = 3;
  198.     n2->next= n3;
  199.     n3->child = NULL;
  200.     n3->next = NULL;
  201.  
  202.  
  203.     //second row
  204.     dnode *n4 = new dnode();
  205.     n4->data = 4;
  206.     n4->prev = NULL;
  207.     n4->child = NULL;
  208.  
  209.     dnode *n5 = new dnode();
  210.     n5->data = 5;
  211.     n5->prev = n4;
  212.     n4->next = n5;
  213.     n5->child = NULL;
  214.     n5->next = NULL;
  215.  
  216.     n2->child = n4;
  217.     Flatten *ll = new Flatten();
  218.     try{
  219.         int start=clock();
  220.         cout << "Approach 1: Flattening... " << endl;
  221.         dnode* flattened = ll->wrapper();
  222.         ll->display(flattened);
  223.         int stop=clock();
  224.         cout << "calculated time of operation is " << stop-start << endl;
  225.     }catch (const char *e){
  226.         cout << "Exception Occured! " << e << endl << endl;
  227.     }
  228.  
  229.     //Returns with no error.
  230.     return 0;
  231. }
RAW Paste Data
Pastebin PRO Autumn Special!
Get 40% OFF on Pastebin PRO accounts!
Top