SHARE
TWEET

Untitled

a guest Nov 12th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. class Elem //komorka listy
  6. {
  7. private:
  8.     int v; //key, data
  9.     Elem* next_elem;
  10.     Elem* prev_elem;
  11.  
  12. public:
  13.     Elem();             //tworzy pusty element
  14.     Elem(int x);            //tworzy element przechowujący x
  15.     int value();            //zwraca wartość
  16.     void setValue(int v);       //ustawia wartość v
  17.     Elem* next();           //zwraca następny element
  18.     Elem* prev();           //zwraca poprzednielement
  19.     void setNext(Elem* p);      //ustawia p jako następny element
  20.     void setPrev(Elem* p);      //ustawia p jako poprzedni element
  21. };
  22.  
  23. Elem::Elem()
  24. {
  25.     next_elem = NULL;
  26.     prev_elem = NULL;
  27.     v = 0; //zeby byla jakas wartosc
  28. }
  29.  
  30. Elem::Elem(int x)
  31. {
  32.     next_elem = NULL;
  33.     prev_elem = NULL;
  34.     v = x;
  35. }
  36.  
  37. int Elem::value()
  38. {
  39.     return v;
  40. }
  41.  
  42. void Elem::setValue(int v)
  43. {
  44.     this->v = v; //stary v staje sie nowym v, element, do ktorego sie teraz konkretnie odwoluje
  45. }
  46.  
  47. Elem* Elem::next()
  48. {
  49.     return next_elem;
  50. }
  51.  
  52. Elem* Elem::prev()
  53. {
  54.     return prev_elem;
  55. }
  56.  
  57. void Elem::setNext(Elem* p)
  58. {
  59.     next_elem = p;
  60. }
  61.  
  62. void Elem::setPrev(Elem* p)
  63. {
  64.     prev_elem = p;
  65. }
  66.  
  67. class SortedDLList //lista
  68. {
  69. private:
  70.     Elem* head;         //wskaźnik na pierwszy element list
  71.     Elem* tail;         //wskaźnik na ostatni element list
  72.     int list_size;          //długość listy, czyli inaczej liczba elementow listy
  73.  
  74. public:
  75.     SortedDLList();             //tworzy pustą listę
  76.     bool empty();               //zwraca prawdę jeśli lista pusta, fałsz w przeciwnym przypadku
  77.     int size();             //zwraca wielkość listy (liczbę elementów w liście)
  78.     Elem* first();              //zwraca pozycję pierwszego elementu
  79.     Elem* last();               //zwraca pozycję ostatniego elementu
  80.     Elem* next(Elem* p);            //zwraca pozycję elementu następnego za p
  81.     Elem* prev(Elem* p);            //zwraca pozycję elementu poprzedniego przed p
  82.     int retrieve(Elem* p);          //zwraca element z pozycji p
  83.     Elem* locate(int x);            //zwrac pozycję pierwszego wystąpienia elementu x, -1 jeśli x nie występuje
  84.     void insert(int x);             //wstawia x z zachowniem porządku
  85.     void del(int x);                //usuwa pierwsze wystąpienie element x    
  86.     void delALLx(int x);             //usuwa wszystkie wystapienia elementu x
  87.     void clear();               //usuwa całą listę
  88.     friend ostream& operator<<(ostream& out, SortedDLList& l); //wypisuje elementu listy   
  89. };
  90.  
  91. SortedDLList::SortedDLList()
  92. {
  93.     head = tail = NULL;
  94.     list_size = 0;
  95. }
  96.  
  97. bool SortedDLList::empty()
  98. {
  99.     if (list_size == 0)
  100.     {
  101.         return true;
  102.     }
  103.     else
  104.     {
  105.         return false;
  106.     }
  107. }
  108.  
  109. int SortedDLList::size()
  110. {
  111.     return list_size;
  112. }
  113.  
  114. Elem* SortedDLList::first()
  115. {
  116.     return head;
  117. }
  118.  
  119. Elem* SortedDLList::last()
  120. {
  121.     return tail;
  122. }
  123.  
  124. Elem* SortedDLList::next(Elem* p)
  125. {
  126.     if (empty())
  127.     {
  128.         return NULL;
  129.     }
  130.     if (head == tail)
  131.     {
  132.         return NULL;
  133.     }
  134.     if (p == tail)
  135.     {
  136.         return NULL;
  137.     }
  138.     return p->next();
  139. }
  140.  
  141. Elem* SortedDLList::prev(Elem* p)
  142. {
  143.     if (empty())
  144.     {
  145.         return NULL;
  146.     }
  147.     if (head == tail)
  148.     {
  149.         return NULL;
  150.     }
  151.     if (p == head)
  152.     {
  153.         return NULL;
  154.     }
  155.     return p->prev();
  156. }
  157.  
  158. int SortedDLList::retrieve(Elem* p)
  159. {
  160.     if (empty())
  161.     {
  162.         return NULL;
  163.     }
  164.     else
  165.     {
  166.         return p->value();
  167.     }
  168. }
  169.  
  170. Elem* SortedDLList::locate(int x)
  171. {
  172.     if (empty())
  173.     {
  174.         return NULL;
  175.     }
  176.     Elem* p = head;
  177.     while (p->value() != x)
  178.     {
  179.         if (p == tail)
  180.             return NULL;
  181.         p = p->next();
  182.     }
  183.     return p;
  184. }
  185.  
  186. void SortedDLList::insert(int x)
  187. {
  188.     if (empty())
  189.     {
  190.         head = new Elem(x); //wywolujemy drugi konstruktor, tworzymy nowy pierwszy element
  191.         tail = head;
  192.         head->setNext(NULL);
  193.         head->setPrev(NULL);
  194.         list_size++;
  195.     }
  196.     else
  197.     {
  198.         if (head->value() >= x) //tworze nowy element przed dotychczasowa head
  199.         {
  200.             Elem* p = new Elem;
  201.             p->setValue(x);
  202.             p->setPrev(NULL);
  203.             head->setPrev(p);
  204.             p->setNext(head);
  205.             head = p;
  206.             list_size++;
  207.         }
  208.         else
  209.         {
  210.             if (head == tail) //nowy element jest wiekszy od head, czyli tworze nowy tail, bo lista jest jednoelementowa
  211.             {
  212.                 tail = new Elem(x);
  213.                 head->setNext(tail);
  214.                 tail->setPrev(head);
  215.                 tail->setNext(NULL);
  216.                 list_size++;
  217.                 return;
  218.             }
  219.             Elem* p = head;
  220.             while (p != tail)
  221.             {
  222.                 if (p->next()->value() >= x) //wstawiam nowy element pomiedzy head i tail
  223.                 {
  224.                     Elem* newElem = new Elem(x);
  225.                     p->next()->setPrev(newElem);
  226.                     newElem->setNext(p->next());
  227.                     p->setNext(newElem);
  228.                     newElem->setPrev(p);
  229.                     list_size++;
  230.                     return;
  231.  
  232.                 }
  233.                 p = p->next();
  234.             }
  235.             //wstawiam nowy element za tail
  236.             Elem* new_elem = new Elem(x);
  237.             new_elem->setPrev(tail);
  238.             tail->setNext(new_elem);
  239.             new_elem->setNext(NULL);
  240.             tail = new_elem;
  241.             list_size++;
  242.         }
  243.     }
  244. }
  245.  
  246. void SortedDLList::del(int x)
  247. {
  248.     Elem* p = locate(x);
  249.     if (p == NULL) //elementu nie ma w liscie lub lista jest pusta
  250.     {
  251.         return;
  252.     }
  253.     else if (p == head) //poszukiwany element jest head
  254.     {
  255.         head = head->next();
  256.         delete p;
  257.         list_size--;
  258.     }
  259.     else if (p != tail) //poszukiwany element jest pomiedzy head a tail
  260.     {
  261.         p->prev()->setNext(p->next());
  262.         p->next()->setPrev(p->prev());
  263.         delete p;
  264.         list_size--;
  265.     }
  266.     else //poszukiwany element jest tail
  267.     {
  268.         tail = tail->prev();
  269.         delete p;
  270.         list_size--;
  271.     }
  272. }
  273.  
  274. void SortedDLList::delALLx(int x)
  275. {
  276.     if (empty())
  277.     {
  278.         return;
  279.     }
  280.     else
  281.     {
  282.         Elem* p = locate(x);
  283.         while (p != NULL)
  284.         {
  285.             p = locate(x);
  286.             if (p == NULL)
  287.                 break;
  288.             if (p->prev() != NULL)
  289.             {
  290.                 p->prev()->setNext(p->next());
  291.                 p->next()->setPrev(p->prev());
  292.                 delete p;
  293.                 list_size--;
  294.             }
  295.             else
  296.             {
  297.                 head->next()->setPrev(NULL);
  298.                 head = head->next();
  299.                 delete p;
  300.                 list_size--;
  301.             }
  302.         }
  303.     }
  304. }
  305.  
  306. void SortedDLList::clear()
  307. {
  308.     if (empty())
  309.     {
  310.         return;
  311.     }
  312.     else
  313.     {
  314.         while (head != NULL)
  315.         {
  316.             Elem* p = head;
  317.             head->next()->setPrev(NULL);
  318.             head = head->next();
  319.             delete p;
  320.             list_size = 0;
  321.         }
  322.     }
  323. }
  324.  
  325. ostream& operator<<(ostream& out, SortedDLList& l)
  326. {
  327.     if (l.empty())
  328.     {
  329.         return out;
  330.     }
  331.     Elem* temp = l.head;
  332.  
  333.  
  334.     while (temp != NULL)
  335.     {
  336.         out << temp->value() << " ";
  337.         temp = temp->next();
  338.     }
  339.     return out;
  340. }
  341.  
  342. int main()
  343. {
  344.     SortedDLList lista;
  345.     lista.insert(2);
  346.     lista.insert(5);
  347.     lista.insert(5);
  348.     lista.insert(8);
  349.     lista.insert(1);
  350.     lista.insert(1);
  351.     lista.insert(9);
  352.     cout << lista << endl;
  353.  
  354.     /**blad jest w insert na pewno**/
  355.     /**juz nie ma, ale brakowalo linii 238 :)**/
  356.  
  357.     lista.delALLx(1);
  358.     cout << lista << endl;
  359.     return 0;
  360. }
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