Najlepsze struktury danych i algorytmy w Javie, które musisz znać

Gdybym miał wybrać najważniejszy temat w tworzeniu oprogramowania, byłyby to struktury danych i algorytmy. Można o nim myśleć jako o podstawowym narzędziu dostępnym dla każdego programisty. Podczas programowania używamy struktury danych do przechowywania i organizowania danych oraz algorytmy manipulować danymi w tych strukturach. Ten artykuł zawiera szczegółowy przegląd wszystkich typowych struktur danych i algorytmów w aby czytelnicy byli dobrze wyposażeni.

Poniżej wymienione są tematy omówione w tym artykule:

• Struktury danych w Javie
  • Liniowe struktury danych
  • Hierarchiczne struktury danych
• Algorytmy w Javie
  • Algorytmy sortowania
  • Wyszukiwanie algorytmów

Struktury danych w Javie

Struktura danych to sposób przechowywania i organizowania danych w komputerze w celu ich efektywnego wykorzystania. Umożliwia efektywne zarządzanie dużymi ilościami danych. Wydajne struktury danych są kluczem do projektowania wydajnych algorytmów.

Ww tym artykule „Struktury danych i algorytmy w Javie” zajmiemy się podstawowymi strukturami danych, takimi jak:

• Liniowe struktury danych
  • Połączona lista
  • Półki na książki
  • Kolejki

• Hierarchiczne struktury danych
  • Drzewa binarne
  • Stosy
  • Hash Tables

Sprawdźmy każdy z nich.

Liniowe struktury danych w Javie

Liniowe struktury danych w to takie, których elementy są sekwencyjne i uporządkowane w taki sposób, że: jest tylko jeden pierwszy element i ma tylko jeden następny element , Tam jest tylko jeden ostatni element i ma tylko jeden poprzedni element , podczas gdy wszystkie inne elementy mają rozszerzenie Kolejny i a poprzedni element.

Tablice

Na szyk to liniowa struktura danychreprezentująca grupę podobnych elementów, do których można uzyskać dostęp za pomocą indeksu. Przed zapisaniem danych należy podać rozmiar tablicy. Poniżej wymienione są właściwości tablicy:

• Każdy element w tablicy ma ten sam typ danych i ten sam rozmiar
• Elementy tablicy są przechowywane w sąsiednich lokalizacjach pamięci, przy czym pierwszy element zaczyna się w najmniejszej lokalizacji pamięci
• Dostęp do elementów tablicy można uzyskać losowo
• Struktura danych tablicy nie jest całkowicie dynamiczna

Na przykład , możemy chcieć, aby gra wideo śledziła dziesięć najlepszych wyników w tej grze. Zamiast używać dziesięciu różnych zmienne w tym zadaniu moglibyśmy użyć jednej nazwy dla całej grupy i użyć numerów indeksowych do odniesienia się do najlepszych wyników w tej grupie.

Połączona lista

DO to liniowa struktura danych ze zbiorem wielu węzłów, gdzie eKażdy element przechowuje własne dane i wskaźnik do lokalizacji następnego elementu. Ostatnie łącze na liście połączonej wskazuje na wartość null, wskazując koniec łańcucha. Element na połączonej liście nosi nazwę węzeł . Pierwszy węzeł nosi nazwę głowa .Nazywa się ostatni węzełthe ogon .

mongodb tworzy użytkownika dla bazy danych

Typy list połączonych

Lista pojedynczo połączona (jednokierunkowa)

Lista podwójnie połączona (dwukierunkowa)

Lista połączona cyklicznie

Oto prosty przykład: Wyobraź sobie połączoną listę, jak łańcuch spinaczy, które są ze sobą połączone. Możesz łatwo dodać kolejny spinacz na górze lub na dole. Można nawet szybko wstawić jedną pośrodku. Wszystko, co musisz zrobić, to po prostu odłączyć łańcuch na środku, dodać nowy spinacz, a następnie ponownie podłączyć drugą połowę. Lista połączona jest podobna.

Półki na książki

Stos, abstrakcyjna struktura danych, to zbiór plików obiekty które są wkładane i wyjmowane zgodnie z ostatnie weszło, pierwsze wyszło (LIFO) zasada. Obiekty można wstawiać do stosu w dowolnym momencie, ale tylko ostatnio wstawiony (czyli „ostatni”) obiekt można usunąć w dowolnym momencie.Poniżej wymienione są właściwości stosu:

• Jest to uporządkowana lista, w którejwstawianie i usuwanie można wykonać tylko na jednym końcu, który jest nazywany Top
• Rekurencyjna struktura danych ze wskaźnikiem do jej górnego elementu
• Postępuje zgodnie z ostatnie weszło, pierwsze wyszło (LIFO) zasada
• Obsługuje dwie najbardziej podstawowe metody
  • push (e): Włożyć element e na szczyt stosu
  • pop (): Usuń i zwróć górny element na stosie

Praktyczne przykłady stosu obejmują odwracanie słowa,aby sprawdzić poprawność zdanie wtrąconesekwencja,wdrażanie funkcji z powrotem w przeglądarkach i wielu innych.

Kolejki

to także inny rodzaj abstrakcyjnej struktury danych. W przeciwieństwie do stosu kolejka jest zbiorem obiektów, które są wstawiane i usuwane zgodnie z pierwszy na wejściu, pierwszy na wyjściu (FIFO) zasada. Oznacza to, że elementy można wstawić w dowolnym momencie, ale w dowolnym momencie można usunąć tylko ten element, który był w kolejce najdłużej.Poniżej wymienione są właściwości kolejki:

• Często określane jako pierwszy na wejściu, pierwszy na wyjściu lista
• Obsługuje dwie najbardziej podstawowe metody
  • enqueue (e): Wstaw element e na tylny kolejki
  • dequeue (): Usuń i zwróć element z z przodu kolejki

Kolejki są używane wasynchroniczny transfer danych między dwoma procesami, planowanie procesora, planowanie dysków i inne sytuacje, w których zasoby są współdzielone przez wielu użytkowników i obsługiwane na zasadzie „kto pierwszy, ten pierwszy”. Następnie w tym artykule „Struktury danych i algorytmy w Javie” mamy hierarchiczne struktury danych.

Hierarchiczne struktury danych w Javie

Drzewo binarne

Drzewo binarne to plikhierarchiczne drzewiaste struktury danych, w których każdy węzeł ma co najwyżej dwoje dzieci , które są określane jako lewe dziecko i właściwe dziecko . Każde drzewo binarne ma następujące grupy węzłów:

• Węzeł główny: jest to najwyższy węzeł i często nazywany jest węzłem głównymponieważ wszystkie inne węzły są dostępne z poziomu katalogu głównego
• Left Sub-Tree, które jest również drzewem binarnym
• Prawe drzewo podrzędne, które jest również drzewem binarnym

Poniżej wymienione są właściwości drzewa binarnego:

• Po drzewie binarnym można przejść na dwa sposoby:
  • Głębokie pierwsze przejście : W kolejności (od lewej do prawej strony), przedsprzedaż (od początku do lewej z prawej) i po kolejności (od lewej do prawej strony)
  • Pierwsze przejście szerokości : Przechodzenie po kolejności poziomów
• Złożoność czasowa przemierzania drzewa: O (n)
• Maksymalna liczba węzłów na poziomie „l” = 2^l-1.

Zastosowania drzew binarnych obejmują:

• Używany w wielu wyszukiwarkach, w których dane są stale wprowadzane / wychodzące
• Jako przepływ pracy do komponowania obrazów cyfrowych w celu uzyskania efektów wizualnych
• Używany w prawie każdym routerze o dużej przepustowości do przechowywania tablic routerów
• Używany również w sieciach bezprzewodowych i alokacji pamięci
• Używany w algorytmach kompresji i wielu innych

Binary Heap

Binary Heap jest kompletnadrzewo binarne, która odpowiada na właściwość sterty. Mówiąc prosto, tojest odmianą drzewa binarnego o następujących właściwościach:

• Heap to kompletne drzewo binarne: Mówi się, że drzewo jest kompletne, jeśli wszystkie jego poziomy, z wyjątkiem być może najgłębszego, są kompletne. Tjego własność Binary Heap sprawia, że ​​nadaje się do przechowywania w pliku .
• Następuje po właściwości sterty: Sterta binarna to plik Min-Heap lub a Max-Heap .
  • Min sterta binarna: F.lub każdy węzeł w stercie, wartość węzła to mniejsze lub równe wartości dzieci
  • Maksymalna sterta binarna: F.lub każdy węzeł w stercie, wartość węzła to większy lub równy wartości dzieci

Popularne zastosowania stosu binarnego obejmująimplementowanie wydajnych kolejek priorytetów, efektywne znajdowanie k najmniejszych (lub największych) elementów w tablicy i wiele innych.

Hash Tables

Wyobraź sobie, że masz plik obiekt i chcesz przypisać do niego klucz, aby wyszukiwanie było bardzo łatwe. Aby zapisać tę parę klucz / wartość, możesz użyć prostej tablicy, takiej jak struktura danych, w której klucze (liczby całkowite) mogą być używane bezpośrednio jako indeks do przechowywania wartości danych. Jednak w przypadkach, gdy klucze są zbyt duże i nie można ich użyć bezpośrednio jako indeksu, używana jest technika zwana haszowaniem.

Podczas haszowania duże klucze są przekształcane w małe klucze przy użyciu funkcje skrótu . Wartości są następnie przechowywane w strukturze danych o nazwiedo tabela skrótów. Tablica skrótów to struktura danych, która implementuje słownik ADT, strukturę, która może odwzorowywać unikalne klucze na wartości.

Ogólnie rzecz biorąc, tabela skrótów ma dwa główne składniki:

1. Tablica wiader: Tablica zasobnikowa dla tabeli skrótów to tablica A o rozmiarze N, w której każda komórka A jest traktowana jako „zasobnik”, czyli zbiór par klucz-wartość. Liczba całkowita N określa pojemność tablicy.
2. Funkcja skrótu: Jest to dowolna funkcja, która odwzorowuje każdy klucz k w naszej mapie na liczbę całkowitą z zakresu [0, N i minus 1], gdzie N jest pojemnością tablicy kubełkowej dla tej tabeli.

Kiedy umieszczamy obiekty w tablicy hashy, możliwe jest, że różne obiekty mogą mieć ten sam hashcode. Nazywa się to kolizja . Aby poradzić sobie z kolizjami, istnieją techniki, takie jak tworzenie łańcuchów i adresowanie otwarte.

Oto kilka podstawowych i najczęściej używanych struktur danych w Javie. Teraz, gdy wiesz o każdym z nich, możesz zacząć wdrażać je w swoim . Tym samym zakończyliśmy pierwszą część „tego artykułu„ Struktury danych i algorytmy w języku Java ”. W następnej części dowiemy się o tympodstawowe algorytmy i sposoby ich wykorzystania w praktycznych zastosowaniach, takich jak sortowanie i wyszukiwanie, dzielenie i zdobywanie, algorytmy zachłanne, programowanie dynamiczne.

Algorytmy w Javie

Historycznie używane jako narzędzie do rozwiązywania złożonych obliczeń matematycznych, algorytmy są głęboko związane z informatyką, w szczególności ze strukturami danych. Algorytm to sekwencja instrukcji opisująca sposób rozwiązania określonego problemu w skończonym okresie czasu. Są reprezentowane na dwa sposoby:

• Schematy blokowe - To jestwizualna reprezentacja przepływu sterowania algorytmem
• Pseudo kod - Tojest tekstową reprezentacją algorytmu, który aproksymuje ostateczny kod źródłowy

Uwaga: Wydajność algorytmu mierzy się na podstawie złożoności czasowej i przestrzennej. Przeważnie złożoność każdego algorytmu zależy od problemu i samego algorytmu.

Przyjrzyjmy się dwóm głównym kategoriom algorytmów w Javie, którymi są:

• Sortowanie algorytmów w Javie
• Wyszukiwanie algorytmów w Javie

Sortowanie algorytmów w Javie

Algorytmy sortowania to algorytmy, które układają elementy listy w określonej kolejności. Najczęściej używanymi porządkami są porządek numeryczny i porządek leksykograficzny. W tym artykule „Struktury danych i algorytmy” przyjrzyjmy się kilku algorytmom sortowania.

Sortowanie bąbelkowe w Javie

Sortowanie bąbelkowe, często nazywane sortowaniem tonącym, jest najprostszym algorytmem sortowania. Wielokrotnie przechodzi przez listę do posortowania, porównuje każdą parę sąsiednich elementów i zamienia je, jeśli są w złej kolejności.Sortowanie bąbelkowe ma swoją nazwę, ponieważ filtruje elementy na szczyt tablicy, podobnie jak bąbelki unoszące się na wodzie.

Otopseudokod reprezentujący algorytm sortowania bąbelkowego (kontekst sortowania rosnącego).

a [] jest tablicą o rozmiarze N begin BubbleSort (a []) deklaruje liczbę całkowitą i, j dla i = 0 do N - 1 dla j = 0 do N - i - 1, jeśli a [j]> a [j + 1 ], a następnie zamień a [j], a [j + 1] end if end if end, aby zwrócić koniec BubbleSort

Ten kod porządkuje jednowymiarową tablicę N elementów danych w porządku rosnącym. Zewnętrzna pętla sprawia, że ​​N-1 przechodzi przez tablicę. Każdy przebieg wykorzystuje wewnętrzną pętlę do wymiany elementów danych w taki sposób, że następny najmniejszy element danych „bąbelkuje” w kierunku początku tablicy. Ale problem polega na tym, że algorytm potrzebuje jednego całego przebiegu bez żadnej zamiany, aby wiedzieć, że lista jest posortowana.

Najgorsza i średnia złożoność przypadków: O (n * n). Najgorszy przypadek występuje, gdy tablica jest posortowana odwrotnie.

Najlepsza złożoność czasowa przypadku: Na). Najlepszy przypadek ma miejsce, gdy tablica jest już posortowana.

Sortowanie przez wybór w Javie

Sortowanie przez wybór jest połączeniem wyszukiwania i sortowania. Algorytm sortuje tablicę, wielokrotnie znajdując minimalny element (biorąc pod uwagę kolejność rosnącą) z nieposortowanej części i umieszczając go we właściwej pozycji w tablicy.

co oznacza append w java

Oto pseudokod reprezentujący algorytm sortowania przez wybór (rosnący kontekst sortowania).

a [] to tablica o rozmiarze N begin SelectionSort (a []) dla i = 0 do n - 1 / * ustaw bieżący element jako minimum * / min = i / * znajdź element minimum * / dla j = i + 1 do n jeśli lista [j]
Jak widać z kodu, liczba przejść sortowania przez tablicę jest o jeden mniejsza niż liczba elementów w tablicy. Pętla wewnętrzna znajduje następną najmniejszą wartość, a pętla zewnętrzna umieszcza tę wartość w odpowiednim miejscu. Sortowanie przez wybór nigdy nie powoduje wymiany więcej niż O (n) i może być przydatne, gdy zapis do pamięci jest kosztowną operacją.
 Złożoność czasowa: Na2), ponieważ istnieją dwie zagnieżdżone pętle.
 Przestrzeń pomocnicza: Lub (1).
 Sortowanie przez wstawianie w Javie 
Sortowanie przez wstawianie to prosty algorytm sortowania, który iteruje po liście, zużywając jeden element wejściowy naraz i buduje ostateczną posortowaną tablicę. Jest to bardzo proste i skuteczniejsze w przypadku mniejszych zestawów danych. Jest to stabilna technika sortowania na miejscu.
Oto pseudokod reprezentujący algorytm sortowania przez wstawianie (rosnący kontekst sortowania).
a [] to tablica o rozmiarze N begin InsertionSort (a []) dla i = 1 do N key = a [i] j = i - 1 while (j> = 0 and a [j]> key0 a [j + 1] = x [j] j = j - 1 koniec, podczas gdy a [j + 1] = koniec klucza dla końca InsertionSort
Jak widać z kodu, algorytm sortowania przez wstawianieusuwa jeden element z danych wejściowych, znajduje jego położenie w posortowanej liście i wstawia go tam. Powtarza się, dopóki żadne elementy wejściowe nie pozostaną nieposortowane.
 Najlepszy przypadek: W najlepszym przypadku jest to tablica, która jest już posortowana. W tym przypadku sortowanie przez wstawianie ma liniowy czas trwania (tj. & Theta (n)).
 Najgorszy przypadek:  Najprostszym wejściem najgorszego przypadku jest tablica posortowana w odwrotnej kolejności.
 QuickSort w Javie 
Algorytm Quicksort to szybki, rekurencyjny, niestabilny algorytm sortowania, który działa na zasadzie dziel i rządź. Wybiera element jako pivot i dzieli daną tablicę wokół tego wybranego pivota.
 Kroki do wdrożenia szybkiego sortowania:  
 
Wybierz odpowiedni „punkt obrotu”.
Podziel listy na dwie listyna podstawie tego elementu obrotowego. Każdy element, który jest mniejszy od elementu obrotowego, jest umieszczany na lewej liście, a każdy większy element jest umieszczany na prawej liście. Jeśli element jest równy elementowi przestawnemu, może znaleźć się na dowolnej liście. Nazywa się to operacją partycji.
Sortuj rekurencyjnie każdą z mniejszych list. 
Oto pseudokod reprezentujący algorytm szybkiego sortowania.
QuickSort (A as array, low as int, high as int) {if (low
W powyższym pseudokodzie przegroda() funkcja wykonuje operacje na partycji i Szybkie sortowanie() funkcja wielokrotnie wywołuje funkcję partycji dla każdej generowanej mniejszej listy. Złożoność szybkiego sortowania w przeciętnym przypadku to & Theta (n log (n)), aw najgorszym to & Theta (n2).
 Sortuj przez scalanie w Javie 
Mergesort to szybki, rekurencyjny, stabilny algorytm sortowania, który działa również na zasadzie dziel i zwyciężaj. Podobnie jak quicksort, sortowanie przez scalanie dzieli listę elementów na dwie listy. Listy te są sortowane niezależnie, a następnie łączone. Podczas łączenia list elementy są wstawiane (lub łączone) w odpowiednich miejscach listy.
Oto pseudokod reprezentujący algorytm sortowania przez scalanie.
procedura MergeSort (a as array) if (n == 1) zwraca var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... ( a [0]> b [0]) dodaj b [0] do końca c usuń b [0] z b w przeciwnym razie dodaj a [0] do końca c usuń a [0] z końca, jeśli koniec podczas gdy (a ma elementy) dodaj a [0] na końcu c usuń a [0] z końca, podczas gdy (b ma elementy) dodaj b [0] do końca c usuń b [0] z końca b podczas powrotu c zakończyć procedurę
 scalesort () funkcja dzieli listę na dwie, wywołania scalesort () na tych listach oddzielnie, a następnie łączy je, wysyłając jako parametry do funkcji merge ().Algorytm ma złożoność O (n log (n)) i ma szeroki zakres zastosowań.
 Sortowanie na stosie w Javie 
Heapsort to algorytm sortowania oparty na porównaniuStruktura danych binarnej sterty. Możesz o tym myśleć jako o ulepszonej wersji sortowania selekcji, gdziedzieli dane wejściowe na posortowany i nieposortowany region, a następnie iteracyjnie zmniejsza nieposortowany region, wyodrębniając największy element i przenosząc go do posortowanego regionu.
 Kroki do wdrożenia Quicksort (w kolejności rosnącej): 
Zbuduj maksymalną stertę za pomocą tablicy sortującej
W tym miejscut, największy element jest przechowywany w katalogu głównym sterty. Zastąp go ostatnim elementem sterty i zmniejsz rozmiar sterty o 1. Na koniec ułóż na stosie korzeń drzewa
Powtarzaj powyższe kroki, aż rozmiar sterty będzie większy niż 1
Oto pseudokod reprezentujący algorytm sortowania sterty.
Heapsort (a as array) for (i = n / 2 - 1) to i> = 0 heapify (a, n, i) for i = n-1 to 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int )hest = i // Inicjalizacja największego jako root int l eft = 2 * i + 1 // left = 2 * i + 1 int w prawo = 2 * i + 2 // w prawo = 2 * i + 2 if (lewo a [największy]) największy = lewy if (prawy a [największy]) największy = prawy if (największy! = I) swap ( a [i], A [największy]) heapify (a, n, największy) koniec heapify
Oprócz tego istnieją inne algorytmy sortowania, które nie są tak dobrze znane, takie jak Introsort, Sortowanie zliczania itp. Przechodząc do następnego zestawu algorytmów w tym artykule „Struktury danych i algorytmy”, przyjrzyjmy się algorytmom wyszukiwania.
 Wyszukiwanie algorytmów w Javie 
Wyszukiwanie jest jedną z najczęściej wykonywanych czynności w zwykłych aplikacjach biznesowych. Algorytmy wyszukiwania to algorytmy służące do znajdowania elementu o określonych właściwościach w kolekcji elementów. Przyjrzyjmy się dwóm najczęściej używanym algorytmom wyszukiwania.
 Liniowy algorytm wyszukiwania w Javie 
Wyszukiwanie liniowe lub sekwencyjne to najprostszy algorytm wyszukiwania. Polega na sekwencyjnym wyszukiwaniu elementu w danej strukturze danych, aż do znalezienia elementu lub osiągnięcia końca struktury. Jeśli element zostanie znaleziony, zwracana jest lokalizacja elementu, w przeciwnym razie algorytm zwraca NULL.
Oto pseudokod reprezentujący wyszukiwanie liniowe w Javie:
procedura linear_search (a [], value) for i = 0 do n-1 if a [i] = value then print 'Found' return i end if print 'Not found' end for end linear_search
To jestalgorytm brutalnej siły.Chociaż z pewnością jest najprostszy, z pewnością nie jest najczęstszy ze względu na jego nieefektywność. Złożoność czasowa wyszukiwania liniowego wynosi NA) .
 Algorytm wyszukiwania binarnego w Javie 
Wyszukiwanie binarne, znane również jako wyszukiwanie logarytmiczne, to algorytm wyszukiwania, który znajduje pozycję wartości docelowej w już posortowanej tablicy. Dzieli zbiór wejściowy na równe połówki, a element jest porównywany ze środkowym elementem listy. Jeśli element zostanie znaleziony, wyszukiwanie kończy się na tym. W przeciwnym razie kontynuujemy wyszukiwanie elementu, dzieląc i wybierając odpowiednią partycję tablicy, w oparciu o to, czy element docelowy jest mniejszy, czy większy niż element środkowy.
Oto pseudokod reprezentujący wyszukiwanie binarne w Javie:
Procedura binary_search a posortowana tablica n rozmiar tablicy x wartość do przeszukania lowerBound = 1 upperBound = n, podczas gdy x nie znaleziono, jeśli upperBound
Wyszukiwanie kończy się, gdy upperBound (nasz wskaźnik) minie lowerBound (ostatni element), co oznacza, że ​​przeszukaliśmy całą tablicę i element nie jest obecny.Jest to najczęściej używany algorytm wyszukiwania przede wszystkim ze względu na krótki czas wyszukiwania. Złożoność czasowa wyszukiwania binarnego wynosi NA) co jest wyraźnym ulepszeniem NA) złożoność czasowa wyszukiwania liniowego.
To prowadzi nas do końca artykułu „Struktury danych i algorytmy w Javie”. Omówiłem jeden z najbardziej podstawowych i najważniejszych tematów języka Java.Mam nadzieję, że wszystko, co zostało Ci udostępnione w tym artykule, jest dla Ciebie jasne.
  Upewnij się, że ćwiczysz jak najwięcej i cofnij swoje doświadczenie.   
 Sprawdź    autorstwa Edureka, zaufanej firmy zajmującej się edukacją online, z siecią ponad 250 000 zadowolonych uczniów rozsianych po całym świecie. Jesteśmy tutaj, aby pomóc Ci na każdym etapie Twojej podróży, aby zostać oprócz tych pytań do wywiadu Java, opracowaliśmy program nauczania przeznaczony dla studentów i profesjonalistów, którzy chcą zostać programistą Java. 
 Masz do nas pytanie? Proszę wspomnieć o tym w sekcji komentarzy w niniejszym „Strukturach danych i algorytmach w Javie”  artykuł, a my skontaktujemy się z Tobą tak szybko, jak to możliwe.