Monthly Archive kwiecień 2020

Rzucanie i przechwytywanie wyjątków w Javie

W poprzedniej części wpisu na temat wyjątków w Javie przyjrzeliśmy się klasom, które odpowiadają za wyjątki oraz błędy w Javie. Poznaliśmy wiele przykładów gotowych klas oraz podział na wyjątki kontrolowane oraz niekontrolowane. Jednakże sama znajomość klas nie wystarczy i należy poznać techniki rzucania oraz obsługi wyjątków. W tym celu użyjemy słów kluczowych throws, try oraz catch.
Wyjątki kontrolowane to wszystkie klasy z gałęzi Exception, które nie dziedziczą po RuntimeException. To właśnie one będą przedmiotem zainteresowania w dzisiejszej lekcji.

Read More

Wyjątki w Javie

W jednym z poprzednich wpisów omówiliśmy operacje wyjścia-wyjścia, które były obsługiwane przez klasę Scanner. Jedną z jej cech jest możliwość wprowadzania danych przez użytkownika przy pomocy klawiatury. Gdybyśmy wyobrazili sobie idealnego użytkownika, to z pewnością zawsze podawałby dane zgodne z oczekiwaniami programisty. Nikt nie jest nieomylny i zawsze ktoś może popełnić błąd (w tym sam twórca np. próbując dostać się do elementu „spoza tablicy”). Sprzymierzeńcem okazuje się jeden z filarów Javy czyli niezawodność.

Read More

Kolekcje Javy – Interfejs Map

Przechodzimy do ostatniego typu kolekcji, który będzie omawiać czyli interfejs Map. Mapy to obiekty, które przechowują dane w postaci dwójki klucz-wartość. To najważniejsza zmiana w stosunku do poprzednio przedstawionych kolekcji. Klucz jest swego rodzaju identyfikatorem i to na jego podstawie zwracana jest wartość. Artykuł jest częścią wpisów o kolekcjach w Javie.

Read More

Kolekcje Javy – Interfejs Set

Kolekcje implementujące interfejs Set posiadają cechę wyróżniającą ją od innych poznanych wcześniej kolekcji – elementy nie mogą się powtarzać. Dodatkowo użytkownik nie ma wpływu na pozycję przy dodawaniu elementów, jednak konkretna implementacja może porządkować zbiory. Dozwolona jest wartość null, jednakże tylko raz.

W stosunku do sekwencyjnego przeszukiwania listy wykorzystanie interfejsu Set może okazać się bardziej wydajne. Artykuł jest częścią wpisów o kolekcjach w Javie.

Read More

Implementacja drzewa BST w Javie

Przykładowa implementacja drzewa poszukiwań binarnych (BST) w Javie

Nasza implementacja drzewa BST składa się z dwóch klas.

  • Wezel – jest klasą wewnętrzną. Reprezentuje pojedynczy węzeł w drzewie. Przechowywanym kluczem jest wartość int.
  • Drzewo – zawiera algorytmy dodawania, usuwania, wyświetlania elementów, odnajdywania poprzednika i następnika węzła oraz przechowuje korzeń. Jest klasą zewnętrzną.

Drzewa BST są ważną strukturą danych. Pozwalają o wiele skrócić czas wyszukiwania elementów, co jest szczególnie zauważalne przy dużych zbiorach. Oczywiście zakładając, że drzewo jest zrównoważone – w przeciwnym wypadku liczba operacji może wzrosnąć do poziomu zwykłej listy. Dużo lepszą wydajność zapewnią drzewa AVL lub drzewa czerwono-czarne. Te struktury poprzez rotacje potrafią zapewnić zrównoważenie poziomu obu poddrzew korzenia. Aby jednak je poznać warto najpierw poznać dokładnie drzewa BST, gdyż ta wiedza jest niezbędna, aby potem stosować dodatkowe zasady umieszczania węzłów.

Teoretyczna część znajduje się w naszym artykule odnośnie drzew BST. Tutaj skupimy się na praktycznej implementacji podanych tam algorytmów.

Klasa Drzewo

Wewnętrzna klasa Wezel

Klasa Wezel przechowuje informację o dwóch potomkach, o rodzicu oraz klucz. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Drzewo, gdyż i tak nie wykorzystamy jej nigdzie indziej.

Pola

Obiekt klasy Wezel zawiera trzy referencje:

  • do lewego potomka,
  • do prawego potomka,
  • oraz do rodzica.

Dodatkowym polem jest przechowywana wartość czyli zmienna key.

Konstruktor

Inicjuje dane – referencje do innych węzłów na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Drzewo

Obiekt klasy Drzewo przechowuje referencję do korzenia (ang. root). Zawiera również niezbędne algorytmy, takie jak:

  • dodawanie elementów do drzewa,
  • usuwanie elementów z drzewa,
  • szukanie elementu o konkretnej wartości,
  • znalezienie największej wartości w drzewie,
  • znalezienie najmniejszej wartości w drzewie,
  • wskazanie następnika węzła,
  • wskazanie poprzednika węzła.

Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

System zbierania nieużytków (ang. Garbage collector)

W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Wystarczy odłączyć usuwany obiekt od struktury drzewa.