fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6.      ________
  7.     |  Data  |
  8.     |________|
  9.     | *next  |
  10.     |________|
  11. */
  12.  
  13. struct Data
  14. {
  15.     int data;
  16.     Data *next;
  17.  
  18.     Data(int);                  //  Data(int val)
  19.     ~Data();
  20.     void print();
  21. };
  22. //  konstruktor
  23. Data :: Data(int val)
  24. {
  25.     data = val;
  26.     next = NULL;
  27.     //  Ponizej jest rysunek jak wyglada lista
  28.     //  - element i wskaznik na kolejny element
  29.     //  - na koncu wskaznik na pusty element
  30. }
  31.  
  32. Data :: ~Data()
  33. {
  34.     cout << "Deleted ";
  35.     print();
  36.     cout << endl;
  37. }
  38.  
  39. void Data :: print()
  40. {
  41.     cout << " (" << data << ") ";
  42. }
  43.  
  44. /*
  45.          ________      ________      ________          ________      ________
  46.         |  Data  |  ->|  Data  |  ->|  Data  |        |  Data  |  ->|  NULL  |
  47.   List: |________| /  |________| /  |________|   ...  |________| /  |________|
  48.         | *next  |/   | *next  |/   | *next  |        | *next  |/   |        |
  49.         |________|    |________|    |________|        |________|    |________|
  50.           first         ->next        ->next     ...    ->next        ->next
  51.                                         ^
  52.                                         |
  53.                                 first->next->next
  54. */
  55.  
  56. struct List
  57. {
  58.     //  pierwszy element listy
  59.     Data *first;
  60.  
  61.     List();
  62.     List(int);                  //  List(int val)
  63.     ~List();
  64.     void push(int);             //  push(int val)
  65.     int pop();
  66.     void replace(int, int);     //  replace(int pos, int val)
  67.     void insert(int, int);      //  insert(int pos, int val);
  68.     void erase(int);            //  erase(int pos);
  69.     void print();
  70.     int size();
  71.     void sort();
  72. };
  73.  
  74. //  konstruktor tworzy pierwszy blok jako pusty
  75. List :: List()
  76. {
  77.     first = NULL;
  78. }
  79.  
  80. //  konstruktor tworzy pierwszy element
  81. //  kontruktor elementu tworzy wskaznik na kolejny pusty blok
  82. List :: List(int val)
  83. {
  84.     first = new Data(val);
  85. }
  86.  
  87. //  destruktor usuwa wszystkie elementy z listy
  88. List :: ~List()
  89. {
  90.     Data *temp = first;
  91.     /*  Windows:
  92.     Data *next = first->next; */
  93.  
  94.     //  chodzimy po liscie
  95.     //  Linux:
  96.     while (temp)
  97.     /*  Windows:
  98.     while (temp->next) */
  99.     {
  100.         //  usuwamy obecny
  101.         delete temp;
  102.         //  temp wskazuje na nastepny
  103.         //  Linux:
  104.         temp = temp->next;
  105.         /*  Windows:
  106.         temp = next;
  107.         next = next->next; */
  108.     }
  109.  
  110.     //  pozostanie nam ostatni element do usuniecia
  111.     delete temp;
  112. }
  113.  
  114. //  wstawiamy nowy element na koncu listy,
  115. //  pusty blok staje sie nowym elementem
  116. void List :: push(int val)
  117. {
  118.     //  tworzy nowy element
  119.     Data *data = new Data(val);
  120.  
  121.     if (first == NULL)
  122.     {
  123.         /*
  124.             Gdy lista nie zawiera elementow
  125.                  ________
  126.                 |  NULL  |
  127.           List: |________|
  128.                 |        |
  129.                 |________|
  130.                  push(val)
  131.             Wstawiamy elment jako pierwszy
  132.                  ________      ________
  133.                 |  Data  |  ->| NULL   |
  134.           List: |__(val)_| /  |________|
  135.                 | *next  |/   |        |
  136.                 |________|    |________|
  137.         */
  138.  
  139.         first = data;
  140.     }
  141.     else
  142.     {
  143.         /*
  144.             Gdy lista zawiera elementy, obchodzimy ja do konca i tam
  145.             wstawiamy nowy element
  146.                  ________      ________      ________
  147.                 |  Data  |  ->|  Data  |  ->|  NULL  |
  148.           List: |________| /  |________| /  |________|
  149.                 | *next  |/   | *next  |/   |        |
  150.                 |________|    |________|    |________|
  151.                                              push(val)
  152.             Wstawiamy element na koniec
  153.                  ________      ________      ________      ________
  154.                 |  Data  |  ->|  Data  |  ->|  Data  |  ->|  NULL  |
  155.           List: |________| /  |________| /  |__(val)_| /  |________|
  156.                 | *next  |/   | *next  |/   | *next  |/   |        |
  157.                 |________|    |________|    |________|    |________|
  158.         */
  159.         //  zaczynamy od pierwszego elementu
  160.         Data *temp = first;
  161.  
  162.         //  chodzimy po liscie tak dlugo, az aktualny element
  163.         //  nie wskazuje na pusty blok
  164.         while (temp->next)
  165.         {
  166.             temp = temp->next;
  167.         }
  168.  
  169.         //  jak znajdzie taki blok to go uzupelnia
  170.         temp->next = data;
  171.         temp->next->next = NULL;
  172.     }
  173. }
  174.  
  175. //  Sciaga ostatni element z listy zastepujac go pustym blokiem
  176. int List :: pop()
  177. {
  178.     /*
  179.              ________      ________      ________      ________
  180.             |  Data  |  ->|  Data  |  ->|  Data  |  ->|  NULL  |
  181.       List: |________| /  |________| /  |__(val)_| /  |________|
  182.             | *next  |/   | *next  |/   | *next  |/   |        |
  183.             |________|    |________|    |________|    |________|
  184.                                            pop()
  185.         Sciagamy ostatni
  186.              ________      ________      ________
  187.             |  Data  |  ->|  Data  |  ->|  NULL  |
  188.       List: |________| /  |________| /  |________|
  189.             | *next  |/   | *next  |/   |        |
  190.             |________|    |________|    |________|
  191.     */
  192.     int ret_val;
  193.  
  194.     if (first == NULL)
  195.     {
  196.         //  Jezeli lista pusta to error
  197.         cout << "Empty list! Cannot pop." << endl;
  198.         ret_val = 0;
  199.     }
  200.     else if (!first->next)
  201.     {
  202.         //  Jezeli lista 1-elementowa to usuwamy i zerujemy
  203.         ret_val = first->data;
  204.         delete first->next;
  205.  
  206.         first = NULL;
  207.     }
  208.     else
  209.     {
  210.         //  Jezeli lista >1-elementowa
  211.         //  poprzednik ostatniego
  212.         Data *prev = first;
  213.         //  ostatni
  214.         Data *data = first->next;
  215.  
  216.         //  chodzimy po liscie tak dlugo, az ostatni element
  217.         //  nie wskazuje na pusty blok
  218.         while (data->next)
  219.         {
  220.             prev = prev->next;
  221.             data = data->next;
  222.         }
  223.  
  224.         //  zwracamy dane z ostatniego
  225.         ret_val = data->data;
  226.         //  usuwamy ostatni
  227.         delete data;
  228.         //  poprzednik wskazuje na pusty blok
  229.         prev->next = NULL;
  230.     }
  231.  
  232.     return ret_val;
  233. }
  234.  
  235. void List :: replace(int pos, int val)
  236. {
  237.     if (pos < 1 or pos > size())
  238.     {
  239.         cout << "Index out of range!" << endl;
  240.         return;
  241.     }
  242.     else
  243.     {
  244.         int i = 1;
  245.  
  246.         Data *temp = first;
  247.  
  248.         while (i != pos)
  249.         {
  250.             i++;
  251.             temp = temp->next;
  252.         }
  253.  
  254.         temp->data = val;
  255.     }
  256. }
  257.  
  258. void List :: insert(int pos, int val)
  259. {
  260.     //  nowy element
  261.     Data *data = new Data(val);
  262.     if (pos < 1)
  263.     {
  264.         cout << "Index out of range!" << endl;
  265.         return;
  266.     }
  267.     else if(!first)
  268.     {
  269.         //  gdy lista pusta wstawiamy nowy element jako pierwszy
  270.         first = data;
  271.     }
  272.     else
  273.     {
  274.         int i = 1;
  275.  
  276.         if (!first)
  277.         {
  278.             //  Jezeli lista pusta
  279.             first = data;
  280.         }
  281.         else
  282.         {
  283.             //  Jezeli lista zawiera elementy
  284.             //  poprzednik
  285.             Data *prev = first;
  286.             //  nastepnik
  287.             Data *next = first->next;
  288.  
  289.             if (pos == 1)
  290.             {
  291.                 first = data;
  292.                 data->next = prev;
  293.             }
  294.             else
  295.             {
  296.                 while (i != pos)
  297.                 {
  298.                     i++;
  299.                     prev = prev->next;
  300.                     next = next->next;
  301.                 }
  302.  
  303.                 //  poprzednik wskazuje na nowy element
  304.                 prev->next = data;
  305.                 //  nowy element wskazuje na nastepnik;
  306.                 data->next = next;
  307.             }
  308.         }
  309.     }
  310. }
  311.  
  312. void List :: erase(int pos)
  313. {
  314.     if (pos < 1 or pos > size())
  315.     {
  316.         cout << "Index out of range!" << endl;
  317.         return;
  318.     }
  319.     else
  320.     {
  321.         int i = 1;
  322.         Data *temp = first;
  323.  
  324.         if (pos == 1)
  325.         {
  326.             //  Jezeli usuwamy pierwszy element
  327.             delete first;
  328.             //  pierwszy staje sie nastepnym
  329.             first = temp->next;
  330.         }
  331.         else
  332.         {
  333.             //  chodzimy po liscie
  334.             while (temp)
  335.             {
  336.                 if ((i + 1) == pos)
  337.                 {
  338.                     //  Jezeli kolejny ma byc usuniety
  339.                     //  zapisujemy sobie kolejny po usuwanym
  340.                     Data *temp2 = temp->next->next;
  341.  
  342.                     //  usuwamy
  343.                     delete temp->next;
  344.                     //  obecny wskazuje na kolejny po usuwanym
  345.                     temp->next = temp2;
  346.  
  347.                     break;
  348.                 }
  349.  
  350.                 temp = temp->next;
  351.                 i++;
  352.             }
  353.         }
  354.     }
  355. }
  356.  
  357. void List :: print()
  358. {
  359.     cout << "HEAD";
  360.  
  361.     Data *temp = first;
  362.  
  363.     while (temp)
  364.     {
  365.         cout << "->";
  366.         temp->print();
  367.         temp = temp->next;
  368.     }
  369.  
  370.     cout << endl;
  371. }
  372.  
  373. int List :: size()
  374. {
  375.     int size = 0;
  376.  
  377.     Data *temp = first;
  378.  
  379.     while (temp)
  380.     {
  381.         size++;
  382.         temp = temp->next;
  383.     }
  384.  
  385.     return size;
  386. }
  387.  
  388. void List :: sort()
  389. {
  390.     if (!first or !first->next)
  391.     {
  392.         return;
  393.     }
  394.     else
  395.     {
  396.         Data *prev = first;
  397.         for (int i = 0; i < size(); i++)
  398.         {
  399.             Data *next = prev->next;
  400.             int temp;
  401.  
  402.             for (int j = i; j < size() - 1; j++)
  403.             {
  404.                 if (prev->data > next->data)
  405.                 {
  406.                     temp = prev->data;
  407.                     prev->data = next->data;
  408.                     next->data = temp;
  409.                 }
  410.  
  411.                 next = next->next;
  412.             }
  413.  
  414.             prev = prev->next;
  415.         }
  416.     }
  417. }
  418.  
  419. int main()
  420. {
  421.     List *lista = new List();
  422.  
  423.     lista->print();
  424.  
  425.     lista->insert(1, -5);
  426.     lista->print();
  427.  
  428.     lista->push(-1);
  429.     lista->push(2);
  430.     lista->push(-2);
  431.     lista->print();
  432.  
  433.     lista->sort();
  434.     lista->print();
  435.  
  436.     lista->pop();
  437.     lista->print();
  438.  
  439.     lista->replace(0, 4);
  440.     lista->replace(1, 4);
  441.     lista->print();
  442.  
  443.     lista->insert(1, 6);
  444.     lista->print();
  445.  
  446.     lista->erase(6);
  447.     lista->erase(3);
  448.     lista->print();
  449.  
  450.     delete lista;
  451.  
  452.     return 0;
  453. }
  454.  
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
HEAD
HEAD-> (-5) 
HEAD-> (-5) -> (-1) -> (2) -> (-2) 
HEAD-> (-5) -> (-2) -> (-1) -> (2) 
Deleted  (2) 
HEAD-> (-5) -> (-2) -> (-1) 
Index out of range!
HEAD-> (4) -> (-2) -> (-1) 
HEAD-> (6) -> (4) -> (-2) -> (-1) 
Index out of range!
Deleted  (-2) 
HEAD-> (6) -> (4) -> (-1) 
Deleted  (6) 
Deleted  (4) 
Deleted  (-1)
https://ideone.com/ceBRte
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!