Untitled
#include <iostream> #include <string> using namespace std; template <typename T> struct Node { struct Node<T>* prev = nullptr; T data; struct Node<T>* next = nullptr; }; template <typename T, typename Y> struct LinkedList { struct Node<T>* head = nullptr; struct Node<T>* tail = nullptr; int size = 0; void pushBack(T data) { // tworzenie węzła Node<T>* n = new Node<T>(); n->data = data; n->prev = tail; // jeśli nie został wcześniej dodany żaden element if (tail != nullptr) { tail->next = n; } else { head = n; } tail = n; // zwiększenie informacji o ilości elementów znajdujących się w liście size++; } bool isEmpty() { if (head == nullptr) return true; return false; } Node<T>* search(string key) { Node<T>* n = head; while (n != nullptr) { if (n->data.key == key) return n; n = n->next; } return nullptr; } bool searchAndDelete(string key) { Node<T>* n = search(key); if (n == nullptr) return false; else { if (n == head) { if (n->next != nullptr) { head = n->next; head->prev = nullptr; } else { head = tail = nullptr; } } else if (n == tail) { tail = n->prev; tail->next = nullptr; } else { n->next->prev = n->prev; n->prev->next = n->next; } delete n; size--; return true; } } void clear() { Node<T>* n = head; Node<T>* lastFound = nullptr; if (head == nullptr) { return; } while (true) { lastFound = n; n = n->next; if (n == nullptr) break; delete n->prev; size--; } delete lastFound; // ustawienie tail i head na nullptr head = tail = nullptr; } string str(string(*func)(Y)) { string s = ""; Node<T>* n = head; while (n != nullptr) { s += n->data.key + " -> " + func(n->data.data) + "; \n"; if (n->next != nullptr) s += "\t\t "; n = n->next; } return s; } int getSize() { return size; } Node<T>* get(int i) { Node<T>* n = head; for (int j = 0; j < i; j++) { n = n->next; } return n; } }; // dotąd dosłownie mamy po prostu liste z dowiązaniami (1 zadanie) template <typename T> struct Item { string key; T data; }; // para klucz data, czyli to co bedzie dodawane pozniej do node'a, który jest w liście która jest w tablicy // jakby nie mialy byc same inty w mainie // struct simple_object { // string surname; // int age; // }; // string so_str(simple_object so) { // return so.surname + ' ' + to_string(so.age); // } template <typename T> struct HashTable { int size = 0; int capacity = 10; // tworzenie tablicy list LinkedList<Item<T>, T>* array = new LinkedList<Item<T>, T>[capacity]; //item<T> to para klucz, a samo t to data ta ktora jest juz w itemie przy okazji wczesniej (jest to po to zeby moc zwrocic latwiej po prostu samo data a nie caly item ) //T* array = new T[capacity]; // po prostu troche zmieniona tablica dynamiczna // F) int hash_func(string key) { int q = key.length(); long long hash = 0; for (int i = 0; i < q; i++) { hash += key[i] * pow(31, (q - 1 - i)); } hash = abs(hash % capacity); // hash zmienia sie w zaleznosci od rozmiaru tablicy return hash; } // po prostu dosłownie podpunkt 8 z instrukcji przepisany // G) void rehash() { int old_capacity = capacity; capacity *= 2; // powiekszam capacity 2x LinkedList<Item<T>, T>* tmp_array = new LinkedList<Item<T>, T>[capacity]; // znowu tworze tablice list tylko 2x wieksza for (int i = 0; i < old_capacity; i++) { // jade po wszystkich elementach (indeksach) - vertcial tablicy a pod kazdym elementem jest lista if (!array[i].isEmpty()) { for (int j = 0; j < array[i].getSize(); j++) { // tutaj jade po wszystkich elementach (horyzontalnie) listy ktora jest pod danym indeksem w tablicy Node<Item<T>>* n = array[i].get(j); // wyciągam element string key = n->data.key; // wyciągam kllucz elementu i dalej jak w insercie int hash = hash_func(key); // to samo co w insercie, czyli znajduje miejsce w funkcji hash dla powiekszonej tablicy tmp_array[hash].pushBack(n->data); // i wrzucam tam ta date po prostu (bardzo podobnie jak w insert) } } // znajdzie miejsce dla nowych data no bo capacity jest 2x większe } delete array; // zwalniam stara tablice array = tmp_array; // przypisuje nowa } // A) void insert(string key, T data) { Item<T>* is = search(key); // szukam czy istnieje juz w tablicy hashujacej taki sam klucz if (is != nullptr) { is->data = data; // jesli istnieje to podmieniam data na nową data } else { Item<T> it = Item<T>{ key, data }; // w przeciwnym tworze nowy item int hash = hash_func(key); // wrzucam "hash z klucza" zeby wiedziec w ktorym miejscu wrzucic array[hash].pushBack(it); // w miejscu w ktore zwrocila funkcja hash istnieje lista i dodaje po prostu do tej listy size++; } if (capacity * 0.75 < size) { rehash(); // jesli size przekroczy 75% capacity (jest zapelniona w 75%) to wywolujemy rehash } } // B) Item<T>* search(string key) { int hash = hash_func(key); // uzywamy funkcji hash zeby sprawdzic pod jakim indeksem moglby byc dany element o danym kluczu (jezeli by istniał) Node<Item<T>>* n = array[hash].search(key); // szukamy w liscie czy istnieje pod danym indeksem tablicy if (n != nullptr) // jesli rozne od nullptr return &n->data; // zwracamy date else return nullptr; // a jesli wyszedl nullptr no to nullptr XD } // C) bool remove(string key) { int hash = hash_func(key); // uzywamy funkcji hash zeby sprawdzic pod jakim indeksem moglby byc dany element o danym kluczu (jezeli by istniał) bool flag = array[hash].searchAndDelete(key); //funckja znowu z tablicy searchanddelete (albo zwroci prawde albo nieprawde w zaleznosci czy istnieje element czy nie) if (flag == 1) // jesli istnial to zmniejszamy rozmiar wszystkich elementów size--; return flag; } // D) void clear() { for (int i = 0; i < capacity; i++) { array[i].clear(); // czyscze kazda liste pod kazdym indeksem (array[i] to jest cala nasza lista jakas) } delete[] array; // zwolnienie pamieci tablicy, czyli pustych list bo te zostaly juz wczesniej wyczyszczone size = 0; capacity = 10; array = new LinkedList<Item<T>, T>[capacity]; // tworzymy nowa tablice list } // PODPUNKT 9 // string stats() { // statystyki // int min_list_size = array[0].getSize(); // int max_list_size = array[0].getSize(); // int nonempty_lists = 0; // default values // int item_counter = 0; // for (int i = 0; i < capacity; i++) { // jade po calej tej XD tablicy // if (!array[i].isEmpty()) // sprawdzam jesli lista nie jest pusta // { // nonempty_lists++; // int current_list_size = array[i].getSize(); // sprawdzamy size listy // item_counter += current_list_size; // if (current_list_size > max_list_size) // sprawdzamy czy wiekszy niz maksymalny // max_list_size = current_list_size; // jesli byl to przypisujemy do maksymalnego // else if (current_list_size < max_list_size) //sprawdzamy czy wiekszy niz minimalnu // min_list_size = current_list_size; // jesli byl to przypisujemy do minimalnego // } // } // printowanie wszystkiego /*float average_list_size = item_counter / static_cast<float>(capacity); return "Stats:\n\tlist min size: " + to_string(min_list_size) + "\n\tlist max size: " + to_string(max_list_size) + "\n\tnonempty lists: " + to_string(nonempty_lists) + "\n\taverage list size: " + to_string(average_list_size) + '\n'; }*/ // E) // i tutaj do postaci stringa zeby sobie wyprintowac ten tego tablice string str(string(*func)(T), int x = 0) { // domyslnie argument x = 0 wiec jesli by nic nie wpisal to bedzie cala lista jesli by wpisal 5 to 5 elementow string s = "Hash table: \n\tCurrent size: " + to_string(size) + "\n\tMax size: " + to_string(capacity) + "\n\tTable:\n\t{\n"; if (x < 1) x = capacity; for (int i = 0; i < x; i++) { if (!array[i].isEmpty()) { s += "\t\t" + to_string(i) + ": " + array[i].str(func); // to samo co wczesniej przy statystykach wiec do str dodaje } } s += "\t}\n"; return s; } }; // tworzenie randomowych kluczy o dlugosci 6 (dokladnie z zadania wziete on chcial zeby taka funkcja byla) string randKey(int j) { string s = ""; for (int i = 0; i < j; i++) s += static_cast<char>(rand() % (127 + 1 - 32) + 32); // od 32 do 127 symbole ASCII wybiera do kluczy return s; } int main() { srand(time(NULL)); const int MAX_ORDER = 7; HashTable<int>* ht = new HashTable<int>(); for (int o = 1; o <= MAX_ORDER; o++) { const int n = pow(10, o); clock_t t1 = clock(); for (int i = 0; i < n; i++) ht->insert(randKey(6), i); // tutaj tam i sram 6 znakowe klucze, jesli chcialby nie same inty tylko na szablonach to odkomentowuje simple object i so str clock_t t2 = clock(); // i daje zamiast i np {"kddfvd", "deffdedf", 21} cout << ht->str(to_string, 5); cout << "\nCzas dodawania: " << (double)(t2 - t1) / CLOCKS_PER_SEC; const int m = pow(10, 4); int hits = 0; t1 = clock(); for (int i = 0; i < m; i++) { Item<int>* it = ht->search(randKey(6)); if (it != nullptr) hits++; } t2 = clock(); cout << "\nCzas wyszukiwania: " << (double)(t2 - t1) / CLOCKS_PER_SEC << "\n"; //cout << ht->stats(); DO PODPUNKTU 9 -> PRZY SPRAWDZANIU WYWALIĆ, W RAZIE CZEGO DODAĆ ht->clear(); } delete ht; } // hash table with chaining jak bym szukał filmików
Leave a Comment