Tassos

Code error

Nov 7th, 2015
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.02 KB | None | 0 0
  1. /**
  2.  * ΤΕΙ ΗΠΕΙΡΟΥ
  3.  * ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΕ
  4.  * ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ
  5.  * 2015-2016
  6.  * ΓΚΟΓΚΟΣ ΧΡΗΣΤΟΣ
  7.  *
  8.  * Αρχικός κώδικας : http://pastebin.com/REK6nTAJ
  9.  */
  10.  
  11. #include <iostream>
  12. #include <string>
  13. #include <random>
  14. #include <algorithm>
  15. #include <list>
  16. #include <chrono>
  17.  
  18. using namespace std;
  19. using namespace chrono;
  20.  
  21. mt19937 mt;
  22. uniform_int_distribution<int> uni1(0, 5000);
  23. uniform_int_distribution<int> uni2(0, 25);
  24.  
  25.  
  26. // Δομή "πελάτης" :
  27. struct customer
  28. {
  29.     string name;
  30.     int balance;
  31.  
  32.     bool operator<(customer other) // Δημιουργία συνάρτησης σύγκρισης του αντικειμένου
  33.     {
  34.         return name < other.name;
  35.     }
  36. };
  37.  
  38.  
  39. string generate_random_name(int k)
  40. {
  41.     string name { }; // Δημιουργία ενός *αρχικά* κενού String ονόματος. ( String name = ""; )
  42.  
  43.     string letters_en("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); // Εδώ βάζει όλα τα γράμματα της αλφαβήτου από τα οποία θα διαλέγει 1 κάθε φορά.
  44.  
  45.     for (int j = 0; j < k; j++)
  46.     {
  47.         // Δημιουργία ενός τυχαίου *χαρακτήρα* :
  48.         char c { letters_en[uni2(mt)] }; // Ίδιο με :  char c = letters_en[ uni2(mt) ]; - Εδώ διαλέγει ένα από τα 25 γράμματα του string.
  49.         name += c; // Προσθήκη του νέου χαρακτήρα στο String του ονόματος
  50.     }
  51.  
  52.     return name;
  53. }
  54.  
  55.  
  56.  
  57.  
  58.  
  59. /**
  60.  * ######################################################################
  61.  * ΣΤΑΤΙΚΗ ΑΝΑΠΑΡΑΣΤΑΣΗ ΓΡΑΜΜΙΚΗΣ ΛΙΣΤΑΣ (ΑΡΧΗ)
  62.  * ######################################################################
  63.  */
  64.  
  65. const int MAX = 50000;
  66.  
  67. template<class T>
  68. struct static_list
  69. {
  70.     T elements[MAX];
  71.     int size = 0;
  72. };
  73.  
  74.  
  75.  
  76. // επιστροφή του στοιχείου που βρίσκεται στη θέση i
  77. template<class T>
  78. T access(static_list<T>& static_list, int i)
  79. {
  80.     if (i < 0 || i >= static_list.size)
  81.         throw -1;
  82.     else
  83.         return static_list.elements[i];
  84. }
  85.  
  86.  
  87.  
  88. // προσθήκη στοιχείου στο τέλος της λίστας
  89. template<class T>
  90. void push_back(static_list<T>& static_list, T x)
  91. {
  92.     if (static_list.size == MAX)
  93.         return;
  94.  
  95.     static_list.elements[static_list.size] = x;
  96.     static_list.size++;
  97. }
  98.  
  99.  
  100.  
  101.  
  102. // προσθήκη στοιχείου στη θέση i, ολίσθηση δεξιά των υπόλοιπων στοιχείων
  103. template<class T>
  104. void insert(static_list<T>& static_list, int i, T x)
  105. {
  106.     if (static_list.size == MAX)
  107.         return;
  108.  
  109.     if (i < 0 || i >= static_list.size)
  110.         return;
  111.  
  112.     for (int k = static_list.size; k > i; k--)
  113.     {
  114.         static_list.elements[k] = static_list.elements[k - 1];
  115.     }
  116.  
  117.     static_list.elements[i] = x;
  118.     static_list.size++;
  119. }
  120.  
  121.  
  122.  
  123.  
  124. // διαγραφή στοιχείου στη θέση i, αριστερή ολίσθηση των υπόλοιπων στοιχείων
  125. template<class T>
  126. void delete_item(static_list<T>& static_list, int i)
  127. {
  128.     if (i < 0 || i >= static_list.size)
  129.         return;
  130.  
  131.     for (int k = i; k < static_list.size; k++)
  132.     {
  133.         static_list.elements[k] = static_list.elements[k + 1];
  134.     }
  135.  
  136.     static_list.size--;
  137. }
  138.  
  139.  
  140.  
  141. // δημιουργία δεδομένων στατικής λίστας
  142. void generate_data_static_list(static_list<customer>& static_list, int N)
  143. {
  144.  
  145.     for (int i = 0; i < N; i++)
  146.     {
  147.         customer c;
  148.         c.name = generate_random_name(10);
  149.         c.balance = uni1(mt);
  150.         push_back(static_list, c);
  151.     }
  152.  
  153. }
  154.  
  155.  
  156.  
  157. // εκτύπωση στατικής λίστας
  158. void print_customers_static_list(static_list<customer>& static_list, int k)
  159. {
  160.     for (int i = 0; i < k; i++)
  161.     {
  162.         customer cu = access(static_list, i);
  163.         cout << cu.name << " - " << cu.balance << endl;
  164.     }
  165.  
  166.     cout << "SIZE " << static_list.size << endl;
  167.  
  168. }
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175. void total_balance_static_list(static_list<customer>& static_list, char c)
  176. {
  177.     // ερώτημα 1α
  178. }
  179.  
  180. void add_extra_customers_static_list(static_list<customer>& static_list, char c)
  181. {
  182.     // ερώτημα 1β
  183. }
  184.  
  185.  
  186.  
  187.  
  188. void remove_customers_static_list(static_list<customer>& static_list, char c)
  189. {
  190.     int i = 0;
  191.  
  192.     while (i < static_list.size)
  193.     {
  194.         customer cu = access(static_list, i);
  195.  
  196.         if (cu.name.at(0) == c)
  197.             delete_item(static_list, i);
  198.         else
  199.             i++;
  200.     }
  201.  
  202. }
  203.  
  204.  
  205. void test_static_list()
  206. {
  207.     mt = *(new mt19937(1940));
  208.  
  209.     cout << "Testing static list" << endl;
  210.     cout << "########################################################" << endl;
  211.  
  212.     high_resolution_clock::time_point t1 = high_resolution_clock::now();
  213.     struct static_list<customer> static_list;
  214.  
  215.     generate_data_static_list(static_list, 40000);
  216.  
  217.     high_resolution_clock::time_point t2 = high_resolution_clock::now();
  218.     print_customers_static_list(static_list, 20);
  219.  
  220.     auto duration = duration_cast<microseconds>( t2 - t1 ).count();
  221.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  222.  
  223.  
  224.  
  225.     t1 = high_resolution_clock::now();
  226.     total_balance_static_list(static_list, 'A');
  227.     t2 = high_resolution_clock::now();
  228.  
  229.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  230.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  231.  
  232.  
  233.  
  234.     t1 = high_resolution_clock::now();
  235.     add_extra_customers_static_list(static_list, 'A');
  236.     t2 = high_resolution_clock::now();
  237.  
  238.     print_customers_static_list(static_list, 20);
  239.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  240.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  241.  
  242.     t1 = high_resolution_clock::now();
  243.     remove_customers_static_list(static_list, 'B');
  244.     t2 = high_resolution_clock::now();
  245.  
  246.     print_customers_static_list(static_list, 20);
  247.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  248.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  249.  
  250.  
  251.     cout << "########################################################" << endl;
  252. }
  253.  
  254.  
  255. /**
  256.  * ######################################################################
  257.  * ΓΡΑΜΜΙΚΗ ΛΙΣΤΑ (ΤΕΛΟΣ)
  258.  * ######################################################################
  259.  */
  260.  
  261.  
  262.  
  263.  
  264.  
  265. /**
  266.  * ######################################################################
  267.  * ΣΥΝΔΕΔΕΜΕΝΗ ΛΙΣΤΑ (ΑΡΧΗ)
  268.  * ######################################################################
  269.  */
  270.  
  271. template<class T>
  272. struct node
  273. {
  274.     T data;
  275.     struct node<T>* next = NULL;
  276. };
  277.  
  278.  
  279. template<class T>
  280. struct linked_list
  281. {
  282.     struct node<T>* head = NULL;
  283.     int size = 0;
  284. };
  285.  
  286.  
  287. // επιστροφή του στοιχείου που βρίσκεται στη θέση i
  288. template<class T>
  289. struct node<T>* access(linked_list<T>& linked_list, int i)
  290. {
  291.     if (i < 0 || i >= linked_list.size)
  292.         return NULL;
  293.  
  294.     struct node<T>* current = linked_list.head;
  295.  
  296.     for (int k = 0; k < i; k++)
  297.     {
  298.         current = current->next;
  299.     }
  300.  
  301.     return current;
  302. }
  303.  
  304.  
  305.  
  306. // προσθήκη στοιχείου στο τέλος της λίστας
  307. template<class T>
  308. void push_back(linked_list<T>& linked_list, T x)
  309. {
  310.     struct node<T>* new_node, *current;
  311.  
  312.     new_node = new node<T>();
  313.     new_node->data = x;
  314.     new_node->next = NULL;
  315.     current = linked_list.head;
  316.  
  317.     if (current == NULL)
  318.     {
  319.         linked_list.head = new_node;
  320.         linked_list.size++;
  321.     }
  322.  
  323.     else
  324.     {
  325.         while (current->next != NULL)
  326.         {
  327.             current = current->next;
  328.         }
  329.  
  330.         current->next = new_node;
  331.         linked_list.size++;
  332.     }
  333.  
  334.  
  335. }
  336.  
  337.  
  338.  
  339. void print_customers_linked_list(linked_list<customer>& linked_list, int k)
  340. {
  341.     for (int i = 0; i < k; i++)
  342.     {
  343.         struct node<customer>* node = access(linked_list, i);
  344.         customer cu = node->data;
  345.         cout << cu.name << " - " << cu.balance << endl;
  346.     }
  347.  
  348.     cout << "SIZE " << linked_list.size << endl;
  349. }
  350.  
  351.  
  352.  
  353.  
  354.  
  355. void generate_data_linked_list(linked_list<customer>& linked_list, int N)
  356. {
  357.     for (int i = 0; i < N; i++)
  358.     {
  359.         customer c;
  360.         c.name = generate_random_name(10);
  361.         c.balance = uni1(mt);
  362.         push_back(linked_list, c);
  363.     }
  364.  
  365. }
  366.  
  367.  
  368.  
  369. void total_balance_linked_list(linked_list<customer>& linked_list, char c)
  370. {
  371.     struct node<customer>* ptr;
  372.     ptr = linked_list.head;
  373.     int i = 0;
  374.     int sum = 0;
  375.  
  376.     while (ptr != NULL)
  377.     {
  378.         customer cu = ptr->data;
  379.         if (cu.name.at(0) == c)
  380.             sum += cu.balance;
  381.         ptr = ptr->next;
  382.         i++;
  383.     }
  384.  
  385.     cout << "Total balance for customers having name starting with character  " << c << " is " << sum << endl;
  386.  
  387. }
  388.  
  389.  
  390.  
  391.  
  392. void add_extra_customers_linked_list(linked_list<customer>& linked_list, char c)
  393. {
  394.     struct node<customer>* ptr;
  395.     ptr = linked_list.head;
  396.  
  397.     while (ptr != NULL)
  398.     {
  399.         customer cu = ptr->data;
  400.  
  401.         if (cu.name.at(0) == c)
  402.         {
  403.             customer ncu;
  404.             ncu.name = cu.name;
  405.             reverse(ncu.name.begin(), ncu.name.end());
  406.             ncu.balance = cu.balance;
  407.  
  408.             struct node<customer>* new_node = new node<customer>();
  409.             new_node->data = ncu;
  410.             new_node->next = ptr->next;
  411.             ptr->next = new_node;
  412.             linked_list.size++;
  413.             ptr = new_node->next;
  414.         }
  415.  
  416.         else
  417.             ptr = ptr->next;
  418.     }
  419.  
  420.  
  421. }
  422.  
  423.  
  424.  
  425.  
  426. void remove_customers_linked_list(linked_list<customer>& linked_list, char c)
  427. {
  428.     // ερώτημα 2
  429. }
  430.  
  431.  
  432.  
  433.  
  434. void test_linked_list()
  435. {
  436.     mt = *(new mt19937(1940));
  437.  
  438.     cout << "Testing linked list" << endl;
  439.     cout << "########################################################" << endl;
  440.  
  441.     struct linked_list<customer> linked_list;
  442.     high_resolution_clock::time_point t1 = high_resolution_clock::now();
  443.     generate_data_linked_list(linked_list, 40000);
  444.     high_resolution_clock::time_point t2 = high_resolution_clock::now();
  445.     print_customers_linked_list(linked_list, 20);
  446.     auto duration = duration_cast<microseconds>( t2 - t1 ).count();
  447.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  448.  
  449.  
  450.     t1 = high_resolution_clock::now();
  451.     total_balance_linked_list(linked_list, 'A');
  452.     t2 = high_resolution_clock::now();
  453.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  454.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  455.  
  456.  
  457.     t1 = high_resolution_clock::now();
  458.     add_extra_customers_linked_list(linked_list, 'A');
  459.     t2 = high_resolution_clock::now();
  460.     print_customers_linked_list(linked_list, 20);
  461.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  462.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  463.  
  464.     t1 = high_resolution_clock::now();
  465.     remove_customers_linked_list(linked_list, 'B');
  466.     t2 = high_resolution_clock::now();
  467.     print_customers_linked_list(linked_list, 20);
  468.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  469.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  470.  
  471.  
  472.     cout << "########################################################" << endl;
  473. }
  474.  
  475. /**
  476.  * ######################################################################
  477.  * ΣΥΝΔΕΔΕΜΕΝΗ ΛΙΣΤΑ (ΤΕΛΟΣ)
  478.  * ######################################################################
  479.  */
  480.  
  481.  
  482.  
  483.  
  484.  
  485. /**
  486.  * ######################################################################
  487.  * ΛΙΣΤΑ STL (ΑΡΧΗ)
  488.  * ######################################################################
  489.  */
  490.  
  491.  
  492. void generate_data_stl_list(list<customer>& stl_list, int N)
  493. {
  494.     for (int i = 0; i < N; i++)
  495.     {
  496.         customer c;
  497.         c.name = generate_random_name(10);
  498.         c.balance = uni1(mt);
  499.         stl_list.push_back(c);
  500.     }
  501.  
  502. }
  503.  
  504. void print_customers_stl_list(list<customer>& stl_list, int k)
  505. {
  506.  
  507.     list<customer>::iterator i;
  508.     int c = 0;
  509.  
  510.     for (i = stl_list.begin(); c < k && i != stl_list.end(); i++)
  511.     {
  512.         customer cu = *i;
  513.         cout << cu.name << " - " << cu.balance << endl;
  514.         c++;
  515.     }
  516.  
  517.     cout << "SIZE " << stl_list.size() << endl;
  518.  
  519. }
  520.  
  521. void total_balance_stl_list(list<customer>& stl_list, char c)
  522. {
  523.     list<customer>::iterator i;
  524.     int sum = 0;
  525.  
  526.     for (i = stl_list.begin(); i != stl_list.end(); i++)
  527.     {
  528.         customer cu = *i;
  529.         if (cu.name.at(0) == c)
  530.             sum += cu.balance;
  531.     }
  532.  
  533.     cout << "Total balance for customers having name starting with character  " << c << " is " << sum << endl;
  534. }
  535.  
  536.  
  537.  
  538.  
  539. void add_extra_customers_stl_list(list<customer>& stl_list, char c)
  540. {
  541.     // ερώτημα 3
  542. }
  543.  
  544.  
  545.  
  546. void remove_customers_stl_list(list<customer>& stl_list, char c)
  547. {
  548.     list<customer>::iterator i = stl_list.begin();
  549.  
  550.     while (i != stl_list.end())
  551.     {
  552.         customer cu = *i;
  553.  
  554.         if (cu.name.at(0) == c)
  555.         {
  556.             i = stl_list.erase(i);
  557.         }
  558.  
  559.         else
  560.             i++;
  561.     }
  562.  
  563. }
  564.  
  565.  
  566.  
  567. void test_stl_list()
  568. {
  569.     // STL ΛΙΣΤΑ
  570.     mt = *(new mt19937(1940));
  571.     cout << "Testing stl list" << endl;
  572.     cout << "########################################################" << endl;
  573.  
  574.     high_resolution_clock::time_point t1 = high_resolution_clock::now();
  575.     list<customer> stl_list;
  576.     generate_data_stl_list(stl_list, 40000);
  577.     high_resolution_clock::time_point t2 = high_resolution_clock::now();
  578.     print_customers_stl_list(stl_list, 20);
  579.     auto duration = duration_cast<microseconds>( t2 - t1 ).count();
  580.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  581.  
  582.  
  583.     t1 = high_resolution_clock::now();
  584.     total_balance_stl_list(stl_list, 'A');
  585.     t2 = high_resolution_clock::now();
  586.     duration = duration_cast<microseconds>( t2 - t1 ).count();
  587.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  588.  
  589.     t1 = high_resolution_clock::now();
  590.     add_extra_customers_stl_list(stl_list, 'A');
  591.     t2 = high_resolution_clock::now();
  592.     print_customers_stl_list(stl_list, 20);
  593.     duration = duration_cast<microseconds>(t2 - t1).count();
  594.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  595.  
  596.     t1 = high_resolution_clock::now();
  597.     remove_customers_stl_list(stl_list, 'B');
  598.     t2 = high_resolution_clock::now();
  599.     print_customers_stl_list(stl_list, 20);
  600.     duration = duration_cast<microseconds>(t2 - t1).count();
  601.     cout << "Time elapsed: " << duration << "microseconds" << endl;
  602.  
  603.     cout << "########################################################" << endl;
  604.  
  605. }
  606.  
  607. /**
  608.  * ######################################################################
  609.  * ΛΙΣΤΑ STL (ΤΕΛΟΣ)
  610.  * ######################################################################
  611.  */
  612.  
  613.  
  614.  
  615.  
  616.  
  617. int main(int argc, char **argv)
  618. {
  619.     test_static_list();
  620.     test_linked_list();
  621.     test_stl_list();
  622. }
Advertisement
Add Comment
Please, Sign In to add comment