SHARE
TWEET

Untitled

Amr1998 Apr 18th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<vector>
  3. using namespace std;
  4. //vector<int>c;
  5. vector<int>u;
  6.  
  7. struct DNode
  8. {
  9.     int info;
  10.     DNode *prev,*next;
  11.     DNode(int el,DNode *n=0,DNode *p=0)
  12.     {
  13.         next=n;
  14.         prev=p;
  15.         info=el;
  16.     }
  17. };
  18.  
  19.  
  20. class doublelinked
  21. {
  22. public:
  23.     DNode *head,*tail;
  24.  
  25.     doublelinked()
  26.     {
  27.         head=tail=0;
  28.     }
  29.     void addtohead(const int &el);
  30.     void addtotail(const int &el);
  31.     int  deletefromhead();
  32.     int   deletefromtail();
  33.     int    findel(const int & el);
  34.     int    firsel();
  35.     void cleardata();
  36.     int size();
  37. };
  38. int doublelinked::size()
  39. {
  40.     int counter=0;
  41.     DNode *tmp=head;
  42.     for(tmp=head; tmp!=0; tmp=tmp->next)
  43.     {
  44.         counter++;
  45.     }
  46.  
  47.     return counter;
  48. }
  49. void doublelinked::addtohead(const int &el)
  50. {
  51.     if(head == 0)
  52.     {
  53.         head=tail=new DNode(el);
  54.     }
  55.     else
  56.     {
  57.         head=new DNode(el,head,0);
  58.         head->next->prev=head;
  59.     }
  60. }
  61. void doublelinked::addtotail(const int &el)
  62. {
  63.     if(head==0)
  64.     {
  65.         head=tail=new DNode(el);
  66.     }
  67.     else
  68.     {
  69.         tail=new DNode(el,0,tail);
  70.         tail->prev->next=tail;
  71.     }
  72. }
  73. int doublelinked::deletefromhead()
  74. {
  75.     int el=head->info;
  76.     if(head==tail)
  77.     {
  78.         delete head;
  79.         head=tail=0;
  80.     }
  81.     else
  82.     {
  83.         head=head->next;
  84.         delete head->prev;
  85.         head->prev=0;
  86.     }
  87.     return el;
  88. }
  89. int doublelinked::deletefromtail()
  90. {
  91.     int el=tail->info;
  92.     if(head==tail)
  93.     {
  94.         delete tail;
  95.         head=tail=0;
  96.     }
  97.     else
  98.     {
  99.         tail=tail->prev;
  100.         delete tail->next;
  101.         tail->next=0;
  102.     }
  103. }
  104. int doublelinked::findel(const int & el)
  105. {
  106.     DNode *tmp;
  107.     for(tmp=head; tmp!=0&&(tmp->info!=el); tmp=tmp->next)
  108.         if(tmp==0)
  109.         {
  110.             return 0;
  111.         }
  112.         else
  113.             return el;
  114. }
  115. int doublelinked::firsel()
  116. {
  117.     return head->info;
  118. }
  119. void doublelinked::cleardata()
  120. {
  121.     for(DNode *tmp; head!=0;)
  122.     {
  123.         tmp=head;
  124.         head=head->next;
  125.         delete tmp;
  126.     }
  127. }
  128.  
  129. void intersection(doublelinked &a,doublelinked &b)  //complexity o(n^3)
  130. {
  131.     //vector<int>c;
  132.     doublelinked *c;
  133.     c=new doublelinked();
  134.  
  135.     if((a.head==0)||(b.head==0))
  136.     {
  137.         cout<<"there is no intersection"<<endl;
  138.     }
  139.     else
  140.     {
  141.         DNode*tmp=a.head;
  142.         DNode*current=b.head;
  143.         for(tmp=a.head; tmp!=0; tmp=tmp->next)
  144.         {
  145.             for(current=b.head; current!=0; current=current->next)
  146.             {
  147.                 if(tmp->info==current->info)
  148.                 {
  149.                     bool flag = false;
  150.                     for(int i : c)
  151.                     {
  152.                         if(i==tmp->info)
  153.                             flag =true;
  154.                     }
  155.                     if (flag==false)
  156.                         //   c.push_back(tmp->info);
  157.                         c->addtohead(tmp->info);
  158.  
  159.                 }
  160.             }
  161.         }
  162.         /*for(int i=0;i<c.size();i++){
  163.             cout<<c[i]<<endl;
  164.         }*/
  165.         for (Node*tmp =c->head; tmp != 0; tmp = tmp->next)
  166.         {
  167.             cout << tmp->info << " ";
  168.             cout << endl;
  169.         }
  170.     }
  171. }
  172.  
  173. /*void uniondouble(doublelinked &a,doublelinked &b){ // complexity o(n^2)
  174. DNode*tmp=a.head;
  175. DNode*current=b.head;
  176. vector<int>u;
  177. for(tmp=a.head;tmp!=0;tmp=tmp->next){
  178.  
  179.             bool flag = false;
  180.             for(int i : u) {
  181.                 if(i==tmp->info)
  182.                     flag =true;
  183.             }
  184.             if (flag==false)
  185.                         u.push_back(tmp->info);
  186.  
  187.  
  188. }
  189.     for(current=b.head;current!=0;current=current->next){
  190.  
  191.             bool flag = false;
  192.             for(int i : u) {
  193.                 if(i==current->info)
  194.                     flag =true;
  195.             }
  196.             if (flag==false)
  197.                         u.push_back(current->info);
  198.  
  199.           }
  200.     for(int i=0;i<u.size();i++){
  201.     cout<<u[i]<<endl;
  202. }
  203.  
  204. }*/
  205. int main()
  206. {
  207.     doublelinked a,b,p;
  208.     a.addtohead(45);
  209.     a.addtohead(45);
  210.     a.addtohead(78);
  211.     b.addtohead(45);
  212.     b.addtotail(78);
  213.     b.addtotail(80);
  214.     intersection(a,b);
  215.     return 0;
  216. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top