Advertisement
Guest User

List reverse and testing

a guest
Jan 16th, 2019
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.76 KB | None | 0 0
  1. //Файл My_list.h
  2.  
  3. #pragma once
  4.  
  5. using std::cout; using std::endl;
  6.  
  7. template<typename Item>
  8. class My_list
  9. {
  10.     struct Node//Структура для узла списка.
  11.     {
  12.         Item item; //Содержимое узла.
  13.         Node* next = nullptr;//Указатель на следующий узел.
  14.  
  15.         Node(const Item & it) { item = it; }
  16.         ~Node() {/* cout << "Node deleted.\n";*/ }
  17.     };
  18.  
  19.     Node* front = nullptr;//Указатель на голову списка.
  20.  
  21. public:
  22.  
  23.     My_list() { cout << "Empty My_list created.\n"; }//Создание пустого списка
  24.     ~My_list();
  25.    
  26.     void insert(const Item & it);//Добавить элемент в список со стороны головы.
  27.     void show()const;//Вывести все эл-ты в консоль.
  28.     void reverse();//Изменение порядка элементов на обратный.
  29. };
  30.  
  31. //Деструктор последовательно освобождает память, выделенную для всех узлов.
  32. template<typename Item>
  33. inline My_list<Item>::~My_list()
  34. {
  35.     if (front != nullptr)
  36.     {
  37.         while (front->next != nullptr)
  38.         {
  39.             Node* temp = front;
  40.             front = front->next;
  41.             delete temp;
  42.         }
  43.         delete front;
  44.     }
  45.     cout << "My list deleted.\n";
  46. }
  47.  
  48. //Добавить элемент в список со стороны головы.
  49. template<typename Item>
  50. inline void My_list<Item>::insert(const Item & it)
  51. {
  52.     Node* temp = new Node(it);
  53.     temp->next = front;
  54.     front = temp;
  55. }
  56.  
  57. //Вывести все эл-ты в консоль.
  58. template<typename Item>
  59. inline void My_list<Item>::show() const
  60. {
  61.     if (front != nullptr)
  62.     {
  63.         Node* temp = front;
  64.         while (temp->next != nullptr)
  65.         {
  66.             cout << temp->item << ' ';
  67.             temp = temp->next;
  68.         }
  69.         cout << temp->item << endl;
  70.     }
  71.     else
  72.     {
  73.         cout << "The list is empty!\n";
  74.     }
  75. }
  76.  
  77. //Изменение порядка элементов на обратный.
  78. template<typename Item>
  79. inline void My_list<Item>::reverse()
  80. {
  81.     if (front != nullptr)//Если список не пустой.
  82.     {
  83.         if (front->next != nullptr)//Размер больше 1;
  84.         {
  85.             Node* old_front = front;//Указатель на голову при прямом порядке списка ("старая голова"). По окончанию реверса станет последним эл-том.
  86.             Node* current = old_front->next;//Указатель на эл-т, следующий за старой головой. Этот эл-т будет "перемещаться".
  87.  
  88.             while (current != nullptr)//Пока не достигнут конец списка.
  89.             {
  90.                 old_front->next = current->next;//Старая голова теперь связана с эл-том за текущим, который теперь можно перемещать.
  91.                 current->next = front;//Текущий связывается с новой головой,
  92.                 front = current;//и сам становится ею.
  93.                 current = old_front->next;//Текущим становится эл-т, стоявший ранее следующим в списке.
  94.             }
  95.         }
  96.         else
  97.         {
  98.             cout << "List size is 1.\n";
  99.             return;
  100.         }
  101.     }
  102.     else
  103.     {
  104.         cout << "The list is empty!\n";
  105.     }
  106. }
  107.  
  108.  
  109.  
  110. //Файл List reverse.cpp
  111.  
  112. #include <iostream>
  113. #include <forward_list>
  114. #include <ctime>
  115. #include "My_list.h"
  116.  
  117. using std::cin;
  118.  
  119. int main()
  120. {
  121.     My_list<int> li;
  122.    
  123.     //Заполняем для демонстрации.
  124.     for (size_t i = 0; i < 11; i++)
  125.     {
  126.         li.insert(i);
  127.     }
  128.     li.show();
  129.  
  130.     li.reverse();//Разворачиваем.
  131.     li.show();
  132.  
  133.     My_list<int> li2;
  134.     std::forward_list<int> f_list;//Стандартный односвязный список для сравнения.
  135.  
  136.     cout << "Enter list size: ";
  137.     int size;
  138.     while (!(cin >> size))
  139.     {
  140.         cout << "Only digits!\n";
  141.         cin.clear();
  142.         cin.ignore(1000, '\n');
  143.     }
  144.  
  145.     //Заполняем оба списка.
  146.     clock_t fill_start = clock();
  147.     for (size_t i = 0; i < size; i++)
  148.     {
  149.         li2.insert(i);
  150.         f_list.emplace_front(i);
  151.     }
  152.     clock_t fill_end = clock();
  153.     cout<<"Filling lists time is "<< (double)(fill_end - fill_start) / CLOCKS_PER_SEC << " seconds.\n";
  154.  
  155.     //Разворачиваем наш список и замеряем время, на это потраченное.
  156.     clock_t my_start = clock();
  157.     li2.reverse();
  158.     clock_t my_end = clock();
  159.     cout << "My_list reversing time is " << (double)(my_end - my_start) / CLOCKS_PER_SEC << " seconds.\n";
  160.  
  161.     ////Аналогично для стандартного списка.
  162.     clock_t std_start = clock();
  163.     f_list.reverse();
  164.     clock_t std_end = clock();
  165.     cout << "Std forward_list reversing time is " << (double)(std_end - std_start) / CLOCKS_PER_SEC << " seconds.\n";
  166.  
  167.     return 0;
  168. }
  169.  
  170. 16.01.2019
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement