Czas najwyższy na kolejny post z serii o strukturach danych. Tym razem bardzo prosta do zaimplementowania struktura – słownik.
Słownik składa się z danych połączonych w pary: klucz i wartość. Klucza używamy aby znaleźć przypisaną do niego wartość. Jak łatwo się domyślić klucze mają unikatowe wartości – nie mogą się powtarzać. Dobrym przykładem (i często przytaczanym), ilustrującym tę strukturę to książka adresowa. Imię i nazwisko to klucz, po którym szukamy w książce adresowej wartości czyli adresu.
Jeśli to wszystko brzmi znajomo, nie dziw się. Słownik to struktura bardzo zbliżona do JavaScriptowej notacja literału obiektu. Ja jednak do mojej implementacji słownika, dodam kilka dodatkowych funkcji, których w JavaScripcie nie ma.
Należy jednak pamiętać, że w tej serii postów chodzi nie tyle o stworzenie przydatnego kodu, co o poznanie i zrozumienie zasady działania klasycznych struktury danych. Ok, skoro to jest już jasne, przejdę do implementacji klasy Dictionary.
Struktury danych w JavaScripcie – Słownik. Implementacja
Oprócz pola, które będzie przechowywało dane klasa Dictionary zawierać będzie też następujące metody:
- add – ta metoda dodaje nowy element do słownika.
- remove – jak łatwo się domyślić po nazwie, metoda służąca do usuwania elementu.
- has – dzięki tej metodzie, można sprawdzić czy dany klucz istnieje w słowniku.
- get – ta metoda zwraca wartość pod konkretnym kluczem.
- clear – ta metoda usuwa wszystkie elementy słownika.
- size – ta metoda zwraca ilość elementów w słowniku.
- keys – metoda, która zwraca tablicę wszystkich kluczy elementów słownika.
- values – metoda, która zwraca tablicę wszystkich wartości elementów słownika.
- viewAll – ta metoda wypisuje w konsoli całą zawartość słownika.
A oto kod:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
var Dictionary = function(){ this.data = {}; this.add = function(key, value){ this.data[key] = value; }; this.remove = function(key) { delete this.data[key]; }; this.has = function(key){ return key in this.data; }; this.get = function(key) { return this.has(key) ? this.data[key] : undefined; }; this.clear = function() { for (var key in this.data) { delete this.data[key]; } }; this.size = function() { var n = 0; for (var key in this.data) { n++; } return n; }; this.keys = function() { var keys = []; for (var key in this.data) { keys.push(key); } return keys; }; this.values = function(){ var values = []; for (var key in this.data) { if (this.has(key)) { values.push(this.data[key]); } } return values; }; this.viewAll = function() { for (var key in this.data) { console.log(key + " -> " + this.data[key]); } }; } |
Tak jak pisałem, nie jest to skomplikowana klasa. Na początku do pola data przypisuję pusty obiekt. To on będzie przechowywał wszystkie elementy dodawane do słownika. Następnie definuję funkcje klasy.
Metody add oraz remove wykorzystują podstawowe właściwości JSowych obiektów. Dodaję nowy element do obiektu data używając zapisu tablicy asocjacyjnej. Nowe dane przekazywane są jako argumenty metodzie add. Usuwanie elementów odbywa się za pomocą operatora delete. Usuwa on z obiektu pole i metodę, której nazwa podana jest po nim.
Metoda has przyjmuje jeden argument i sprawdza czy istnieje on w słowniku. Korzysta w tym celu z operatora in. Operator ten zwraca true, jeżeli wymieniony przed nim klucz zawarty jest w wymienionym po operatorze obiekcie. W innym wypadku zwracane jest false. Ten mechanizm wykorzystuje następna metoda get. Za pomocą has sprawdza czy podany klucz jest w słowniku, jeżeli tak zwraca przypisaną do niego wartość, w innym wypadku zwracane jest undefined.
Metoda clear korzysta z pętli for in. Pętla ta służy do iterowania po polach obiektu zdefiniowanego po operatorze in. Dla każdego pola zwraca nazwę aktualnego klucza w zmiennej zdefiniowanej przed operatorem in. Dzięki tej pętli oraz z pomocą operatora delete usuwam wszystkie pola z obiektu zawierającego elementy słownika.
Kolejna metoda, size, również korzysta z pętli for in. Tym razem jednak nie zmienia nic w polach obiektu słownika a jedynie liczy każdy obieg. Na końcu zwraca liczbę obiegów, będącą zarazem liczbą elementów zawartych w słowniku.
Metody keys oraz values zwracają tablicę z odpowiednimi informacjami pobranymi z elementów słownika. Do tego również wykorzystuję pętle for in. W pętli zbieram klucze / wartości, dodaję je do tablicy, po czym zwracam tablicę.
Ostatnia metoda to viewAll. Tutaj również wykorzystana zostaje pętla for in. Tym razem każdy obieg pętli wypisuje w konsoli klucz oraz wartość danego elementu.
Tak jak pisałem, jest to dość prosta struktura danych. Jednak bardzo fajnie ilustruje, że można bardzo w efektywny sposób przechowywać dane, nie korzystając z listy/tablicy.
na koniec warto jeszcze przetestować klasę słownika. Przykładowe testy mogą wyglądać tak:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
var dict = new Dictionary(); console.log(dict.has("maja")); dict.add("maja","pies"); console.log(dict.has("maja")); console.log(dict.get("maja")); dict.remove("maja"); console.log(dict.has("maja")); dict.add("maja","pies"); dict.add("milus","pies"); dict.add("greebo","kot"); dict.add("przylepa","kot"); dict.viewAll(); console.log(dict.keys()); console.log(dict.values()); console.log(dict.size()); dict.clear(); dict.viewAll(); console.log(dict.size()); console.log(dict.get("dzeki")) |
Sprawdź w konsoli czy wszystko działa. Wygląda na to, że wszystko śmiga jak należy. Gratulacje, implementacja słownika w JavaScripcie udana 🙂
Jeżeli masz jakieś pytania odnośnie słownika, lub którejś z poprzednio opisanych struktur danych, może śmiało je zadać w komentarzach poniżej. Oczywiście świetnym miejscem na kontakt ze mną jest też moja strona na facebooku. Zachęcam przy okazji do polubienia jej, dzięki temu będziesz na bieżąco ze wszystkimi nowościami, które pojawiają się na blogu 🙂