daily pastebin goal
34%
SHARE
TWEET

Untitled

a guest Dec 11th, 2017 46 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdlib>
  2. #include <iostream>
  3. using namespace std;
  4. template <class T>
  5. class ListElement;
  6. template <class T>
  7. class LinkedList;
  8. template <class T>
  9.  
  10. class List
  11. {
  12.  protected:
  13.      int count;
  14.  public:
  15.     List (){count=0;};
  16.     ~List (){};
  17.     //List operator = (List const&);
  18.     bool IsEmpty (){ return count==0;} ;
  19.     virtual T  First ()=0 ;
  20.     virtual T Last ()=0;
  21.     virtual  void Prepend (T &)=0;
  22.     virtual  void Append (T &)=0;
  23.     virtual  void Extract (T&)=0;
  24.     virtual void Purge ()=0;
  25.     virtual void InsertAfter (T&, T &){};
  26.     virtual void InsertBefore (T&, T &){};
  27. };
  28.  
  29. template <class T>
  30. class ListElement {
  31.     T datum;
  32.     ListElement<T>* next;
  33.     ListElement (T&, ListElement<T>*);
  34. public:
  35.     T Datum ();
  36.     ListElement<T>* Next ();
  37.     friend class LinkedList<T>;
  38. };
  39.  
  40. template <class T>
  41. class LinkedList:public List<T>{
  42.     ListElement<T>* head;
  43.     ListElement<T>* tail;
  44. public:
  45.     LinkedList ();
  46.     ~LinkedList ();
  47.     LinkedList<T> operator = (LinkedList<T>&);
  48.     ListElement<T> * Head () ;
  49.     ListElement<T> * Tail () ;
  50.     T  First () ;
  51.     T Last () ;
  52.     void Prepend (T &);
  53.     void Append (T &);
  54.     void Extract (T&);
  55.     void Purge ();
  56.     void InsertAfter (ListElement<T> *, T &);
  57.     void InsertBefore (ListElement<T> *, T &);
  58.     void InsertAfterItem (T, T&);
  59.     void InsertBeforeItem (T&, T&);
  60. };
  61.  
  62. template <class T>
  63. ListElement<T>::ListElement(T& _datum, ListElement<T>* _next)
  64. {
  65.     datum = _datum;
  66.     next = _next;
  67. }
  68.  
  69. template <class T>
  70. T ListElement<T>::Datum ()
  71.     { return datum; }
  72. template <class T>
  73. ListElement<T>* ListElement<T>::Next ()
  74.     { return next; }
  75. template <class T>
  76. LinkedList<T>::LinkedList()
  77. {
  78.  head = tail = NULL;
  79. }
  80.  
  81. template <class T>
  82. void LinkedList<T>::Purge()
  83. {
  84.  ListElement<T>* tmp = head;
  85.  if (tail!=NULL) tail->next = NULL;
  86.  while (head!=NULL)
  87.  {  tmp = head;
  88.     head = head->next;
  89.     delete tmp;
  90.  }
  91.   this->count = 0;
  92.  tail = NULL;
  93. }
  94.  
  95. template <class T>
  96. LinkedList<T>::~LinkedList()
  97. {
  98.  Purge();
  99. }
  100.  
  101. template <class T>
  102. LinkedList<T> LinkedList<T>::operator = (LinkedList<T>& linkedList)
  103. {
  104.     if (&linkedList != this)
  105.     {
  106.     Purge ();
  107.     ListElement<T>* ptr;
  108.     for (ptr = linkedList.head; ptr != tail; ptr = ptr->next)
  109.         Append (ptr->datum);
  110.     }
  111.     if (tail!=head)
  112.         Append(tail->datum);
  113.     return *this;
  114. }
  115.  
  116. template <class T>
  117. ListElement<T> * LinkedList<T>::Head ()
  118.     { return head; }
  119. template <class T>
  120. ListElement<T> * LinkedList<T>::Tail ()
  121.     { return tail; }
  122. template <class T>
  123. T LinkedList<T>::First ()
  124. {
  125.     if (head == NULL)
  126.        cout<<"lista Vazia";//throw domain_error ("list is empty");
  127.     return head->datum;
  128. }
  129.  
  130. template <class T>
  131. T LinkedList<T>::Last ()
  132. {
  133.     if (tail == NULL)
  134.        cout<<"Lista Vazia";//throw domain_error ("list is empty");
  135.     return tail->datum;
  136. }
  137.  
  138. template <class T>
  139. void LinkedList<T>::Prepend (T& item)
  140. {
  141.     ListElement<T>* tmp = new ListElement<T> (item, head);
  142.     if (head == NULL)
  143.         tail = tmp;
  144.     head = tmp;
  145.     this->count++;
  146. }
  147.  
  148. template <class T>
  149. void LinkedList<T>::Append (T &item)
  150. {
  151.      ListElement<T>* tmp=new ListElement<T> (item, head);
  152.      if (head==NULL)
  153.          head = tail = tmp;
  154.      tail->next = tmp;
  155.      tail = tmp;
  156.      this->count++;
  157. }
  158.  
  159. template <class T>
  160. void LinkedList<T>::Extract (T& item)
  161. {
  162.  ListElement<T>* ptr = head;
  163.  ListElement<T>* prevPtr = NULL;
  164.  if (!this->IsEmpty())
  165.  {
  166.     do
  167.     {
  168.         prevPtr = ptr;
  169.         ptr = ptr->next;
  170.     }while (ptr != head && ptr->datum != item);
  171.     if ((ptr == head) && (ptr->datum!=item))
  172.          cout<<"\n item não encountrado";
  173.     else
  174.     {
  175.       if (ptr == head && ptr==tail)
  176.           head=tail=NULL;
  177.       else if (ptr == head)
  178.                head = tail->next = ptr->next;
  179.            else
  180.                prevPtr->next = ptr->next;
  181.       if (ptr == tail)
  182.       {
  183.           tail = prevPtr;
  184.           tail->next = head;
  185.       }
  186.       delete ptr;
  187.       this->count--;
  188.     }
  189.   }
  190.   else cout<<"\n Lista vazia\n";
  191. }
  192.  
  193. template <class T>
  194. void LinkedList<T>::InsertAfter (ListElement<T> *ptr, T & item)
  195. {
  196.     if (ptr!=NULL){
  197.          ListElement<T>* tmp =new ListElement<T> (item, ptr->next);
  198.          ptr->next = tmp;
  199.          if (tail == ptr)
  200.              tail = tmp;
  201.     }
  202.     else if (head == NULL)
  203.     { head=tail=new ListElement<T> (item, NULL);
  204.       tail->next=head;
  205.     }
  206. }
  207.  
  208. template <class T>
  209. void LinkedList<T>::InsertBefore (ListElement<T> *ptr, T& item)
  210. {
  211.     if (ptr != NULL)
  212.     {
  213.         ListElement<T>* tmp = new ListElement<T> (item, ptr);
  214.         if (head == ptr)
  215.             head = tmp;
  216.         else
  217.         {
  218.             ListElement<T>* prevPtr = head;
  219.             while (prevPtr->next != head && prevPtr->next != ptr)
  220.                    prevPtr = prevPtr->next;
  221.             if (prevPtr->next == head)
  222.             {       cout<<"\n Posição inválida";//throw invalid_argument
  223. ("invalid position");
  224.                     delete tmp;
  225.             }
  226.             else prevPtr->next = tmp;
  227.         }
  228.     }
  229.     else if (head == NULL)
  230.     { head=tail=new ListElement<T> (item, NULL);
  231.       tail->next=head;
  232.     }
  233. }
  234.  
  235. template <class T>
  236. void LinkedList<T>::InsertAfterItem (T item, T& _dado){ //item -> item a ser procurado, dado -> dado que quer colocar depois do item
  237.  
  238.    ListElement<T>* ptr = head;
  239.    if (!this->IsEmpty())
  240.    {
  241.       do
  242.       {
  243.           ptr = ptr->next;
  244.       }while (ptr != head && ptr->datum != item);
  245.       if ((ptr == head) && (ptr->datum!=item))
  246.            cout<<"\n item não encountrado";
  247.       else
  248.         InsertAfter(ptr,_dado);
  249.     }
  250.     else cout<<"\n Lista vazia\n";
  251. };
  252.  
  253. template <class T>
  254. void LinkedList<T>::InsertBeforeItem (T& item, T &dado){}
  255.  
  256.  
  257. int main(int argc, char *argv[])
  258. {
  259.     LinkedList<int> lista;
  260.     int a=3;
  261.     lista.Append(a);
  262.     lista.Append(++a);
  263.     lista.Append(++a);
  264.     lista.Append(++a);
  265.     int b=4;
  266.     lista.Extract(b);
  267.     lista.Append(++a);
  268.     lista.Append(++a);
  269.     cout<<"\n"<<lista.First();
  270.     cout<<"\n"<<lista.Last();
  271.     lista.InsertAfterItem(8,++a);
  272.     cout<<"\n"<<lista.Last();
  273.     system("PAUSE");
  274.     return EXIT_SUCCESS;
  275.  
  276. }
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