MeehoweCK

Untitled

Oct 24th, 2020
428
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // main.cpp
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include "lista.hpp"
  6.  
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     Lista<int> lista;
  12.  
  13.     for(unsigned i = 0; i < 20; ++i)
  14.         lista.dodaj_porzadkowo(rand());
  15.     lista.wypisz();
  16.  
  17.     return 0;
  18. }
  19.  
  20. // lista.hpp
  21. #include <iostream>
  22.  
  23. using namespace std;
  24.  
  25. template <class T>
  26. struct element_listy
  27. {
  28.     T wartosc;
  29.     element_listy* next;
  30.     element_listy* prev;
  31. };
  32.  
  33. template <class T>
  34. class Lista
  35. {
  36.     element_listy<T>* head;
  37.     element_listy<T>* last;
  38.     unsigned rozmiar;
  39. public:
  40.     Lista();
  41.     ~Lista();
  42.     unsigned size() const
  43.     {
  44.         return rozmiar;
  45.     }
  46.     void dodaj_na_koniec(T);
  47.     void dodaj_na_poczatek(T);
  48.     void clear();
  49.     int szukaj(T);
  50.     void usun_element(unsigned);
  51.     void usun_pierwszy();
  52.     void usun_ostatni();
  53.     void wypisz();
  54.     void szukaj_i_usun(T);
  55.     bool zmien_wartosc(T, unsigned);
  56.     bool dodaj_na_pozycje(T, unsigned);
  57.     void dodaj_porzadkowo(T);
  58. };
  59.  
  60. template <class T>
  61. Lista<T>::Lista() : head(nullptr), rozmiar(0) {}
  62.  
  63. template <class T>
  64. Lista<T>::~Lista()
  65. {
  66.     element_listy<T>* temp;
  67.     element_listy<T>* pretemp=nullptr;
  68.  
  69.     while (head)
  70.     {
  71.         temp = head;
  72.  
  73.         // przechodzimy na koniec listy:
  74.         while (temp->next)
  75.         {
  76.             pretemp = temp;
  77.             temp = temp->next;
  78.         }
  79.         delete temp;
  80.         pretemp->next = nullptr;
  81.  
  82.         if (pretemp == head)     // zostaje ostatni element
  83.         {
  84.             delete head;
  85.             head = nullptr;
  86.             cout << "Usunieto element\n";
  87.         }
  88.         cout << "Usunieto element\n";
  89.     }
  90.     cout << "Koniec destruktora\n";
  91. }
  92.  
  93. template <class T>
  94. void Lista<T>::dodaj_na_koniec(T value)
  95. {
  96.     element_listy<T>* nowy = new element_listy<T>;
  97.     nowy->wartosc = value;
  98.     nowy->next = nullptr;
  99.  
  100.     // pierwszy element listy:
  101.     if (head == nullptr)
  102.     {
  103.         head = nowy;
  104.         head->prev = nullptr;
  105.         last = head;
  106.         cout << "dodano wartosc " << head->wartosc << endl;
  107.     }
  108.  
  109.     else
  110.     {
  111.         element_listy<T>* temp = head;
  112.         while (temp->next)
  113.             temp = temp->next;
  114.  
  115.         nowy->prev = temp;
  116.         temp->next = nowy;
  117.         cout << "dodano wartosc " << temp->next->wartosc << endl;
  118.         last = nowy;
  119.     }
  120.  
  121.     ++rozmiar;
  122. }
  123.  
  124. template <class T>
  125. void Lista<T>::clear()
  126. {
  127.     element_listy<T>* temp;
  128.     element_listy<T>* pretemp = nullptr;;
  129.  
  130.     while (head)
  131.     {
  132.         temp = head;
  133.  
  134.         // przechodzimy na koniec listy:
  135.         while (temp->next)
  136.         {
  137.             pretemp = temp;
  138.             temp = temp->next;
  139.         }
  140.         delete temp;
  141.         pretemp->next = nullptr;
  142.  
  143.         if (pretemp == head)     // zostaje ostatni element
  144.         {
  145.             delete head;
  146.             head = nullptr;
  147.         }
  148.     }
  149.     rozmiar = 0;
  150. }
  151.  
  152. template <class T>
  153. int Lista<T>::szukaj(T value)
  154. {
  155.  
  156.     if (head->wartosc == value)
  157.         return 0;
  158.  
  159.     element_listy<T>* temp = head->next;
  160.  
  161.     if (temp)
  162.         for (int i = 1; i < rozmiar; ++i)
  163.         {
  164.             if (temp->wartosc == value)
  165.                 return i;
  166.             temp = temp->next;
  167.         }
  168.     else
  169.     {
  170.         return -1;
  171.     }
  172. }
  173.  
  174. template <class T>
  175. void Lista<T>::usun_element(unsigned nr)
  176. {
  177.     if (nr == 0)
  178.     {
  179.         element_listy<T>* temp = head->next;
  180.         delete head;
  181.         head = temp;
  182.         --rozmiar;
  183.  
  184.     }
  185.  
  186.     // kasowanie ostatniego
  187.     else if (nr == rozmiar - 1)
  188.     {
  189.         element_listy<T>* kasowany = head;
  190.         for (unsigned i = 0; i < nr; ++i)
  191.             kasowany = kasowany->next;
  192.  
  193.         element_listy<T>* temp_prev = kasowany->prev;
  194.  
  195.  
  196.         temp_prev->next = nullptr;          // zmiana
  197.  
  198.  
  199.         delete kasowany;
  200.         --rozmiar;
  201.     }
  202.     else
  203.     {
  204.         element_listy<T>* kasowany = head;
  205.         for (unsigned i = 0; i < nr; ++i)
  206.             kasowany = kasowany->next;
  207.  
  208.         element_listy<T>* temp_next = kasowany->next;
  209.         element_listy<T>* temp_prev = kasowany->prev;
  210.  
  211.         temp_prev->next = temp_next;
  212.         temp_next->prev = temp_prev;
  213.  
  214.         delete kasowany;
  215.         --rozmiar;
  216.     }
  217. }
  218.  
  219.  
  220. template<class T>
  221. void Lista<T>::usun_pierwszy()
  222. {
  223.     usun_element(0);
  224. }
  225.  
  226. template<class T>
  227. void Lista<T>::usun_ostatni()
  228. {
  229.     usun_element(rozmiar - 1);
  230. }
  231.  
  232.  
  233. template <class T>
  234. void Lista<T>::wypisz()
  235. {
  236.     cout << "Rozmiar listy: " << rozmiar << endl;
  237.     cout << "Adresy komorek i dane:\n";
  238.  
  239.     element_listy<T>* temp = head;
  240.  
  241.     for (unsigned i = 0; i < rozmiar; ++i)
  242.     {
  243.         cout << '\t' << i << ": " << temp << '\t' << temp->wartosc;
  244.         if(i > 0)
  245.             cout << '\t' << "poprzedni: " << temp->prev;
  246.         cout << endl;
  247.         temp = temp->next;
  248.     }
  249. }
  250.  
  251. template <class T>
  252. void Lista<T>::szukaj_i_usun(T value)
  253. {
  254.     int x = szukaj(value);
  255.     usun_element(x);
  256. }
  257.  
  258. template <class T>
  259. bool Lista<T>::zmien_wartosc(T value, unsigned nr)
  260. {
  261.     if(nr >= rozmiar)
  262.         return false;
  263.  
  264.     if(nr == 0)
  265.     {
  266.         head->wartosc = value;
  267.         return true;
  268.     }
  269.  
  270.     element_listy<T>* temp = head;
  271.     for(unsigned i = 0; i < nr; ++i)
  272.         temp = temp->next;
  273.  
  274.     temp->wartosc = value;
  275.     return true;
  276. }
  277.  
  278. template <class T>
  279. void Lista<T>::dodaj_na_poczatek(T value)
  280. {
  281.     if(rozmiar == 0)
  282.     {
  283.         dodaj_na_koniec(value);
  284.         return;
  285.     }
  286.  
  287.     element_listy<T>* nowy = new element_listy<T>;
  288.     nowy->wartosc = value;
  289.  
  290.     element_listy<T>* temp = head;
  291.     head = nowy;
  292.     head->prev = nullptr;
  293.     head->next = temp;
  294.     head->next->prev = head;
  295.  
  296.     ++rozmiar;
  297. }
  298.  
  299. template <class T>
  300. bool Lista<T>::dodaj_na_pozycje(T value, unsigned nr)
  301. {
  302.     if(nr > rozmiar) return false;
  303.     if(nr == rozmiar)
  304.     {
  305.         dodaj_na_koniec(value);
  306.         return true;
  307.     }
  308.  
  309.     if(nr == 0)
  310.     {
  311.         dodaj_na_poczatek(value);
  312.         return true;
  313.     }
  314.  
  315.     element_listy<T>* temp = head;
  316.  
  317.     for(unsigned i = 0; i < nr; ++i)
  318.         temp = temp->next;
  319.  
  320.     element_listy<T>* temp_prev = temp->prev;
  321.     element_listy<T>* temp_next = temp;
  322.  
  323.  
  324.     element_listy<T>* nowy = new element_listy<T>;
  325.     nowy->wartosc = value;
  326.     nowy->next = temp_next;
  327.     nowy->prev = temp_prev;
  328.  
  329.     temp_prev->next = nowy;
  330.     temp_next->prev = nowy;
  331.     ++rozmiar;
  332.     return true;
  333. }
  334.  
  335. template <class T>
  336. int abs(T a, T b)
  337. {
  338.     if(a >= b)
  339.         return a - b;
  340.     return b - a;
  341. }
  342.  
  343. template <class T>
  344. void Lista<T>::dodaj_porzadkowo(T value)
  345. {
  346.     if(rozmiar == 0)
  347.     {
  348.         dodaj_na_koniec(value);
  349.         return;
  350.     }
  351.  
  352.     unsigned pozycja = 0;
  353.     T porownanie = head->wartosc;
  354.     T best_value = abs(value, head->wartosc);
  355.  
  356.     element_listy<T>* temp = head->next;
  357.  
  358.     for(unsigned i = 1; i < rozmiar; ++i)
  359.     {
  360.         if(abs(value, temp->wartosc) < best_value)
  361.         {
  362.             best_value = abs(value, temp->wartosc);
  363.             porownanie = temp->wartosc;
  364.             pozycja = i;
  365.         }
  366.         temp = temp->next;
  367.     }
  368.  
  369.     if(value <= porownanie)
  370.         dodaj_na_pozycje(value, pozycja);
  371.     else
  372.         dodaj_na_pozycje(value, pozycja + 1);
  373. }
  374.  
RAW Paste Data