Advertisement
Guest User

Untitled

a guest
Sep 13th, 2017
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.51 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement