Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * ΤΕΙ ΗΠΕΙΡΟΥ
- * ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΕ
- * ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ
- * 2015-2016
- * ΓΚΟΓΚΟΣ ΧΡΗΣΤΟΣ
- *
- * Αρχικός κώδικας : http://pastebin.com/REK6nTAJ
- */
- #include <iostream>
- #include <string>
- #include <random>
- #include <algorithm>
- #include <list>
- #include <chrono>
- using namespace std;
- using namespace chrono;
- mt19937 mt;
- uniform_int_distribution<int> uni1(0, 5000);
- uniform_int_distribution<int> uni2(0, 25);
- // Δομή "πελάτης" :
- struct customer
- {
- string name;
- int balance;
- bool operator<(customer other) // Δημιουργία συνάρτησης σύγκρισης του αντικειμένου
- {
- return name < other.name;
- }
- };
- string generate_random_name(int k)
- {
- string name { }; // Δημιουργία ενός *αρχικά* κενού String ονόματος. ( String name = ""; )
- string letters_en("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); // Εδώ βάζει όλα τα γράμματα της αλφαβήτου από τα οποία θα διαλέγει 1 κάθε φορά.
- for (int j = 0; j < k; j++)
- {
- // Δημιουργία ενός τυχαίου *χαρακτήρα* :
- char c { letters_en[uni2(mt)] }; // Ίδιο με : char c = letters_en[ uni2(mt) ]; - Εδώ διαλέγει ένα από τα 25 γράμματα του string.
- name += c; // Προσθήκη του νέου χαρακτήρα στο String του ονόματος
- }
- return name;
- }
- /**
- * ######################################################################
- * ΣΤΑΤΙΚΗ ΑΝΑΠΑΡΑΣΤΑΣΗ ΓΡΑΜΜΙΚΗΣ ΛΙΣΤΑΣ (ΑΡΧΗ)
- * ######################################################################
- */
- const int MAX = 50000;
- template<class T>
- struct static_list
- {
- T elements[MAX];
- int size = 0;
- };
- // επιστροφή του στοιχείου που βρίσκεται στη θέση i
- template<class T>
- T access(static_list<T>& static_list, int i)
- {
- if (i < 0 || i >= static_list.size)
- throw -1;
- else
- return static_list.elements[i];
- }
- // προσθήκη στοιχείου στο τέλος της λίστας
- template<class T>
- void push_back(static_list<T>& static_list, T x)
- {
- if (static_list.size == MAX)
- return;
- static_list.elements[static_list.size] = x;
- static_list.size++;
- }
- // προσθήκη στοιχείου στη θέση i, ολίσθηση δεξιά των υπόλοιπων στοιχείων
- template<class T>
- void insert(static_list<T>& static_list, int i, T x)
- {
- if (static_list.size == MAX)
- return;
- if (i < 0 || i >= static_list.size)
- return;
- for (int k = static_list.size; k > i; k--)
- {
- static_list.elements[k] = static_list.elements[k - 1];
- }
- static_list.elements[i] = x;
- static_list.size++;
- }
- // διαγραφή στοιχείου στη θέση i, αριστερή ολίσθηση των υπόλοιπων στοιχείων
- template<class T>
- void delete_item(static_list<T>& static_list, int i)
- {
- if (i < 0 || i >= static_list.size)
- return;
- for (int k = i; k < static_list.size; k++)
- {
- static_list.elements[k] = static_list.elements[k + 1];
- }
- static_list.size--;
- }
- // δημιουργία δεδομένων στατικής λίστας
- void generate_data_static_list(static_list<customer>& static_list, int N)
- {
- for (int i = 0; i < N; i++)
- {
- customer c;
- c.name = generate_random_name(10);
- c.balance = uni1(mt);
- push_back(static_list, c);
- }
- }
- // εκτύπωση στατικής λίστας
- void print_customers_static_list(static_list<customer>& static_list, int k)
- {
- for (int i = 0; i < k; i++)
- {
- customer cu = access(static_list, i);
- cout << cu.name << " - " << cu.balance << endl;
- }
- cout << "SIZE " << static_list.size << endl;
- }
- void total_balance_static_list(static_list<customer>& static_list, char c)
- {
- // ερώτημα 1α
- }
- void add_extra_customers_static_list(static_list<customer>& static_list, char c)
- {
- // ερώτημα 1β
- }
- void remove_customers_static_list(static_list<customer>& static_list, char c)
- {
- int i = 0;
- while (i < static_list.size)
- {
- customer cu = access(static_list, i);
- if (cu.name.at(0) == c)
- delete_item(static_list, i);
- else
- i++;
- }
- }
- void test_static_list()
- {
- mt = *(new mt19937(1940));
- cout << "Testing static list" << endl;
- cout << "########################################################" << endl;
- high_resolution_clock::time_point t1 = high_resolution_clock::now();
- struct static_list<customer> static_list;
- generate_data_static_list(static_list, 40000);
- high_resolution_clock::time_point t2 = high_resolution_clock::now();
- print_customers_static_list(static_list, 20);
- auto duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- total_balance_static_list(static_list, 'A');
- t2 = high_resolution_clock::now();
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- add_extra_customers_static_list(static_list, 'A');
- t2 = high_resolution_clock::now();
- print_customers_static_list(static_list, 20);
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- remove_customers_static_list(static_list, 'B');
- t2 = high_resolution_clock::now();
- print_customers_static_list(static_list, 20);
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- cout << "########################################################" << endl;
- }
- /**
- * ######################################################################
- * ΓΡΑΜΜΙΚΗ ΛΙΣΤΑ (ΤΕΛΟΣ)
- * ######################################################################
- */
- /**
- * ######################################################################
- * ΣΥΝΔΕΔΕΜΕΝΗ ΛΙΣΤΑ (ΑΡΧΗ)
- * ######################################################################
- */
- template<class T>
- struct node
- {
- T data;
- struct node<T>* next = NULL;
- };
- template<class T>
- struct linked_list
- {
- struct node<T>* head = NULL;
- int size = 0;
- };
- // επιστροφή του στοιχείου που βρίσκεται στη θέση i
- template<class T>
- struct node<T>* access(linked_list<T>& linked_list, int i)
- {
- if (i < 0 || i >= linked_list.size)
- return NULL;
- struct node<T>* current = linked_list.head;
- for (int k = 0; k < i; k++)
- {
- current = current->next;
- }
- return current;
- }
- // προσθήκη στοιχείου στο τέλος της λίστας
- template<class T>
- void push_back(linked_list<T>& linked_list, T x)
- {
- struct node<T>* new_node, *current;
- new_node = new node<T>();
- new_node->data = x;
- new_node->next = NULL;
- current = linked_list.head;
- if (current == NULL)
- {
- linked_list.head = new_node;
- linked_list.size++;
- }
- else
- {
- while (current->next != NULL)
- {
- current = current->next;
- }
- current->next = new_node;
- linked_list.size++;
- }
- }
- void print_customers_linked_list(linked_list<customer>& linked_list, int k)
- {
- for (int i = 0; i < k; i++)
- {
- struct node<customer>* node = access(linked_list, i);
- customer cu = node->data;
- cout << cu.name << " - " << cu.balance << endl;
- }
- cout << "SIZE " << linked_list.size << endl;
- }
- void generate_data_linked_list(linked_list<customer>& linked_list, int N)
- {
- for (int i = 0; i < N; i++)
- {
- customer c;
- c.name = generate_random_name(10);
- c.balance = uni1(mt);
- push_back(linked_list, c);
- }
- }
- void total_balance_linked_list(linked_list<customer>& linked_list, char c)
- {
- struct node<customer>* ptr;
- ptr = linked_list.head;
- int i = 0;
- int sum = 0;
- while (ptr != NULL)
- {
- customer cu = ptr->data;
- if (cu.name.at(0) == c)
- sum += cu.balance;
- ptr = ptr->next;
- i++;
- }
- cout << "Total balance for customers having name starting with character " << c << " is " << sum << endl;
- }
- void add_extra_customers_linked_list(linked_list<customer>& linked_list, char c)
- {
- struct node<customer>* ptr;
- ptr = linked_list.head;
- while (ptr != NULL)
- {
- customer cu = ptr->data;
- if (cu.name.at(0) == c)
- {
- customer ncu;
- ncu.name = cu.name;
- reverse(ncu.name.begin(), ncu.name.end());
- ncu.balance = cu.balance;
- struct node<customer>* new_node = new node<customer>();
- new_node->data = ncu;
- new_node->next = ptr->next;
- ptr->next = new_node;
- linked_list.size++;
- ptr = new_node->next;
- }
- else
- ptr = ptr->next;
- }
- }
- void remove_customers_linked_list(linked_list<customer>& linked_list, char c)
- {
- // ερώτημα 2
- }
- void test_linked_list()
- {
- mt = *(new mt19937(1940));
- cout << "Testing linked list" << endl;
- cout << "########################################################" << endl;
- struct linked_list<customer> linked_list;
- high_resolution_clock::time_point t1 = high_resolution_clock::now();
- generate_data_linked_list(linked_list, 40000);
- high_resolution_clock::time_point t2 = high_resolution_clock::now();
- print_customers_linked_list(linked_list, 20);
- auto duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- total_balance_linked_list(linked_list, 'A');
- t2 = high_resolution_clock::now();
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- add_extra_customers_linked_list(linked_list, 'A');
- t2 = high_resolution_clock::now();
- print_customers_linked_list(linked_list, 20);
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- remove_customers_linked_list(linked_list, 'B');
- t2 = high_resolution_clock::now();
- print_customers_linked_list(linked_list, 20);
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- cout << "########################################################" << endl;
- }
- /**
- * ######################################################################
- * ΣΥΝΔΕΔΕΜΕΝΗ ΛΙΣΤΑ (ΤΕΛΟΣ)
- * ######################################################################
- */
- /**
- * ######################################################################
- * ΛΙΣΤΑ STL (ΑΡΧΗ)
- * ######################################################################
- */
- void generate_data_stl_list(list<customer>& stl_list, int N)
- {
- for (int i = 0; i < N; i++)
- {
- customer c;
- c.name = generate_random_name(10);
- c.balance = uni1(mt);
- stl_list.push_back(c);
- }
- }
- void print_customers_stl_list(list<customer>& stl_list, int k)
- {
- list<customer>::iterator i;
- int c = 0;
- for (i = stl_list.begin(); c < k && i != stl_list.end(); i++)
- {
- customer cu = *i;
- cout << cu.name << " - " << cu.balance << endl;
- c++;
- }
- cout << "SIZE " << stl_list.size() << endl;
- }
- void total_balance_stl_list(list<customer>& stl_list, char c)
- {
- list<customer>::iterator i;
- int sum = 0;
- for (i = stl_list.begin(); i != stl_list.end(); i++)
- {
- customer cu = *i;
- if (cu.name.at(0) == c)
- sum += cu.balance;
- }
- cout << "Total balance for customers having name starting with character " << c << " is " << sum << endl;
- }
- void add_extra_customers_stl_list(list<customer>& stl_list, char c)
- {
- // ερώτημα 3
- }
- void remove_customers_stl_list(list<customer>& stl_list, char c)
- {
- list<customer>::iterator i = stl_list.begin();
- while (i != stl_list.end())
- {
- customer cu = *i;
- if (cu.name.at(0) == c)
- {
- i = stl_list.erase(i);
- }
- else
- i++;
- }
- }
- void test_stl_list()
- {
- // STL ΛΙΣΤΑ
- mt = *(new mt19937(1940));
- cout << "Testing stl list" << endl;
- cout << "########################################################" << endl;
- high_resolution_clock::time_point t1 = high_resolution_clock::now();
- list<customer> stl_list;
- generate_data_stl_list(stl_list, 40000);
- high_resolution_clock::time_point t2 = high_resolution_clock::now();
- print_customers_stl_list(stl_list, 20);
- auto duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- total_balance_stl_list(stl_list, 'A');
- t2 = high_resolution_clock::now();
- duration = duration_cast<microseconds>( t2 - t1 ).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- add_extra_customers_stl_list(stl_list, 'A');
- t2 = high_resolution_clock::now();
- print_customers_stl_list(stl_list, 20);
- duration = duration_cast<microseconds>(t2 - t1).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- t1 = high_resolution_clock::now();
- remove_customers_stl_list(stl_list, 'B');
- t2 = high_resolution_clock::now();
- print_customers_stl_list(stl_list, 20);
- duration = duration_cast<microseconds>(t2 - t1).count();
- cout << "Time elapsed: " << duration << "microseconds" << endl;
- cout << "########################################################" << endl;
- }
- /**
- * ######################################################################
- * ΛΙΣΤΑ STL (ΤΕΛΟΣ)
- * ######################################################################
- */
- int main(int argc, char **argv)
- {
- test_static_list();
- test_linked_list();
- test_stl_list();
- }
Advertisement
Add Comment
Please, Sign In to add comment