Najlepšie dátové štruktúry a algoritmy v jazyku Java, ktoré potrebujete vedieť

Keby som si mal vybrať jednu najdôležitejšiu tému vo vývoji softvéru, boli by to dátové štruktúry a algoritmy. Môžete to považovať za základný nástroj, ktorý má k dispozícii každý počítačový programátor. Pri programovaní používame dátové štruktúry - ukladať a organizovať údaje a - algoritmy manipulovať s údajmi v týchto štruktúrach. Tento článok obsahuje podrobný prehľad všetkých bežných dátových štruktúr a algoritmov v systéme Windows umožniť čitateľom byť dobre vybavení.

Ďalej sú uvedené témy diskutované v tomto článku:

• Dátové štruktúry v Jave
  • Lineárne dátové štruktúry
  • Hierarchické dátové štruktúry
• Algoritmy v Jave
  • Algoritmy triedenia
  • Hľadanie algoritmov

Dátové štruktúry v Jave

Dátová štruktúra je spôsob ukladania a organizovania údajov v počítači, aby sa dali efektívne využívať. Poskytuje prostriedky na efektívnu správu veľkého množstva údajov. A efektívne dátové štruktúry sú kľúčom k navrhovaniu efektívnych algoritmov.

Vv tomto článku „Dátové štruktúry a algoritmy v Jave“ sa budeme zaoberať základnými dátovými štruktúrami, ako sú:

• Lineárne dátové štruktúry
  • Prepojený zoznam
  • Stohy
  • Fronty

• Hierarchické dátové štruktúry
  • Binárne stromy
  • Haldy
  • Hašovacie tabuľky

Pozrime sa na každú z nich.

Lineárne dátové štruktúry v Jave

Lineárne dátové štruktúry v sú tie, ktorých prvky sú postupné a usporiadané tak, aby: bol iba jeden prvý prvok a má iba jednu nasledujúci prvok , je tu iba jeden posledný prvok a má iba jednu predchádzajúci prvok , zatiaľ čo všetky ostatné prvky majú a Ďalšie a a predchádzajúce prvok.

Polia

An pole je lineárna dátová štruktúrapredstavujúci skupinu podobných prvkov, ku ktorým má prístup index. Pred uložením údajov je potrebné uviesť veľkosť poľa. Nižšie sú uvedené vlastnosti poľa:

• Každý prvok v poli je rovnakého dátového typu a má rovnakú veľkosť
• Prvky poľa sú uložené na súvislých pamäťových miestach, pričom prvý prvok začína na najmenšom pamäťovom mieste
• K prvkom poľa je možné náhodne získať prístup
• Štruktúra dát poľa nie je úplne dynamická

spracovanie výnimiek v Oracle uloženej procedúre

Napríklad , možno by sme chceli, aby videohra sledovala desať najlepších skóre v tejto hre. Skôr ako použiť desať rôznych premenné pre túto úlohu by sme mohli použiť jediný názov pre celú skupinu a pomocou indexových čísel odkazovať na najvyššie skóre v tejto skupine.

Prepojený zoznam

TO je lineárna dátová štruktúra so zbierkou viacerých uzlov, kde naprprvok ach ukladá svoje vlastné údaje a ukazovateľ na umiestnenie nasledujúceho prvku. Posledný odkaz v prepojenom zozname ukazuje na nulu, čo znamená koniec reťazca. Prvok v prepojenom zozname sa nazýva a uzol . Prvý uzol sa nazýva hlava .Posledný uzol sa voláthe chvost .

Typy prepojeného zoznamu

Singly Linked List (Uni-Directional)

Dvojnásobne prepojený zoznam (obojsmerný)

Kruhový prepojený zoznam

Tu je jednoduchý príklad: Predstavte si prepojený zoznam ako reťaz kancelárskych sponiek, ktoré sú navzájom spojené. Môžete ľahko pridať ďalšiu sponku na papier zhora alebo zdola. Je dokonca rýchle vložiť jeden do stredu. Musíte len odpojiť reťaz v strede, pridať novú kancelársku sponku a potom znova pripojiť druhú polovicu. Prepojený zoznam je podobný.

Stohy

Stoh, abstraktná dátová štruktúra, je kolekcia predmety ktoré sa vkladajú a vyberajú podľa Last-in-First-Out (LIFO) princíp. Objekty je možné vložiť do stohu kedykoľvek, ale kedykoľvek je možné odstrániť iba naposledy vložený (tj. „Posledný“) objekt.Nižšie sú uvedené vlastnosti zásobníka:

• Je to objednávkový zoznam, v ktoromvkladanie a mazanie je možné vykonávať iba na jednom konci, ktorý sa nazýva hore
• Rekurzívna dátová štruktúra s ukazovateľom na jej horný prvok
• Nasleduje Last-in-First-Out (LIFO) princíp
• Podporuje dve najzákladnejšie metódy
  • push (e): Vložte prvok e do hornej časti stohu
  • pop (): Odstráni a vráti horný prvok zo zásobníka

Medzi praktické príklady skupiny patrí aj obrátenie slova,skontrolovať správnosť zátvorkypostupnosť,implementácia funkcií späť do prehľadávačov a mnohých ďalších.

Fronty

sú tiež ďalším typom abstraktnej dátovej štruktúry. Na rozdiel od stohu je frontom kolekcia objektov, ktoré sa vkladajú a odoberajú podľa prvý-prvý-prvý-von (FIFO) princíp. To znamená, že prvky je možné vložiť kedykoľvek, ale kedykoľvek je možné odstrániť iba prvok, ktorý bol vo fronte najdlhšie.Nižšie sú uvedené vlastnosti frontu:

• Často sa označuje ako prvý dnu prvý von zoznam
• Podporuje dve najzákladnejšie metódy
  • radenie (e): Vložte prvok e na vzadu frontu
  • dequeue (): Odstráni a vráti prvok z spredu frontu

Fronty sa používajú vasynchrónny prenos údajov medzi dvoma procesmi, plánovaním procesora, plánovaním diskov a inými situáciami, keď sú zdroje zdieľané medzi viacerými používateľmi a sú poskytované serverom „kto prv príde“. Ďalej v tomto článku „Dátové štruktúry a algoritmy v Jave“ máme hierarchické dátové štruktúry.

Hierarchické dátové štruktúry v Jave

Binárny strom

Binárny strom je ahierarchické stromové dátové štruktúry, v ktorých každý uzol má najviac dve deti , ktoré sa označujú ako ľavé dieťa a správne dieťa . Každý binárny strom má nasledujúce skupiny uzlov:

• Root Node: Je to najvyšší uzol a často sa označuje ako hlavný uzolpretože na všetky ostatné uzly sa dá dostať z koreňa
• Ľavý pod strom, ktorý je tiež binárnym stromom
• Pravý pod strom, ktorý je tiež binárnym stromom

Ďalej sú uvedené vlastnosti binárneho stromu:

• Binárny strom je možné prechádzať dvoma spôsobmi:
  • Hĺbka prvého prechodu : V poradí (zľava-root-vpravo), predobjednávka (root-zľava-doprava) a postorder (zľava-doprava-root)
  • Šírka prvého prechodu : Prechod na úrovni objednávky
• Časová zložitosť prechodu stromov: O (n)
• Maximálny počet uzlov na úrovni ‘l’ = 2^l-1.

Medzi aplikácie binárnych stromov patria:

• Používa sa v mnohých vyhľadávacích aplikáciách, kde údaje neustále vstupujú / odchádzajú
• Ako pracovný tok na skladanie digitálnych obrázkov pre vizuálne efekty
• Používa sa takmer v každom routeri s vysokou šírkou pásma na ukladanie tabuliek routerov
• Používa sa tiež pri bezdrôtových sieťach a prideľovaní pamäte
• Používa sa v kompresných algoritmoch a v mnohých ďalších

Binárna halda

Binary Heap je kompletnýbinárny strom, ktorá odpovedá na vlastnosť haldy. Jednoducho povedanéje variácia binárneho stromu s nasledujúcimi vlastnosťami:

• Heap je kompletný binárny strom: O strome sa hovorí, že je úplný, ak sú všetky jeho úrovne, okrem najhlbších, pravdepodobne úplné. Tvďaka jeho majetku Binary Heap je vhodné byť uskladnený v .
• Nasleduje vlastnosť haldy: Binárna halda je buď a Hromada min alebo a Max. Halda .
  • Min. Binárna halda: Falebo každý uzol v halde, hodnota uzla je menší alebo rovný hodnoty detí
  • Max. Binárna halda: Falebo každý uzol v halde, hodnota uzla je väčší alebo rovný hodnoty detí

Medzi populárne aplikácie binárnej haldy patriaimplementácia efektívnych frontov priorít, efektívne hľadanie k najmenších (alebo najväčších) prvkov v poli a mnoho ďalších.

Hašovacie tabuľky

Predstavte si, že máte objekt a chcete mu priradiť kľúč, aby bolo vyhľadávanie veľmi jednoduché. Na uloženie tohto páru kľúč / hodnota môžete použiť jednoduché pole, ako je dátová štruktúra, kde sa kľúče (celé čísla) dajú použiť priamo ako index na ukladanie dátových hodnôt. Avšak v prípadoch, keď sú kľúče príliš veľké a nemožno ich použiť priamo ako index, použije sa technika nazývaná hašovanie.

Pri hašovaní sa veľké klávesy prevádzajú na malé pomocou hašovacie funkcie . Hodnoty sa potom uložia do dátovej štruktúry s názvomdo hašovací stôl. Hašovacia tabuľka je dátová štruktúra, ktorá implementuje slovník ADT, štruktúru, ktorá dokáže namapovať jedinečné kľúče na hodnoty.

Všeobecne má hash tabuľka dve hlavné zložky:

1. Pole vedra: Pole vedierka pre hashovaciu tabuľku je pole A o veľkosti N, kde sa každá bunka A považuje za „vedro“, to znamená zbierku párov kľúč - hodnota. Celé číslo N definuje kapacitu poľa.
2. Funkcia hash: Je to akákoľvek funkcia, ktorá mapuje každý kľúč k na našej mape na celé číslo v rozsahu [0, N a mínus 1], kde N je kapacita vedierkového poľa pre túto tabuľku.

Keď dávame objekty do hashtable, je možné, že rôzne objekty môžu mať rovnaký hashcode. Toto sa nazýva a Zrážka . Na riešenie kolízií existujú techniky ako reťazenie a otvorené adresovanie.

Toto je niekoľko základných a najčastejšie používaných dátových štruktúr v Jave. Teraz, keď ste si vedomí každého z nich, môžete ich začať implementovať vo svojom . Týmto sme dokončili prvú časť ‘tohto článku‘ Dátové štruktúry a algoritmy v Jave ’. V ďalšej časti sa budeme učiť ozákladné algoritmy a ako ich používať v praktických aplikáciách ako je triedenie a hľadanie, delenie a dobývanie, chamtivé algoritmy, dynamické programovanie.

Algoritmy v Jave

Historicky používané ako nástroj na riešenie zložitých matematických výpočtov sú algoritmy úzko spojené s počítačovou vedou a predovšetkým s dátovými štruktúrami. Algoritmus je postupnosť pokynov, ktorá popisuje spôsob riešenia konkrétneho problému v konečnom časovom období. Sú zastúpené dvoma spôsobmi:

• Vývojové diagramy - Je tovizuálne znázornenie toku riadenia algoritmu
• Pseudokód - Toje textová reprezentácia algoritmu, ktorý sa približuje konečnému zdrojovému kódu

Poznámka: Výkonnosť algoritmu sa meria na základe časovej a priestorovej zložitosti. Zložitosť ľubovoľného algoritmu väčšinou závisí od problému a od samotného algoritmu.

Pozrime sa na dve hlavné kategórie algoritmov v Jave, ktorými sú:

• Triedenie algoritmov v Jave
• Vyhľadávanie algoritmov v jazyku Java

Triedenie algoritmov v Jave

Algoritmy triedenia sú algoritmy, ktoré zaraďujú prvky zoznamu do určitého poradia. Najbežnejšie používané poradia sú číselné poradie a lexikografické poradie. V tomto článku „Dátové štruktúry a algoritmy“ sa dozvieme niekoľko algoritmov triedenia.

Bublinové triedenie v Jave

Bubble Sort, často označovaný ako potápanie, je najjednoduchší algoritmus triedenia. Opakovane prechádza zoznamom, ktorý sa má triediť, porovnáva každú dvojicu susedných prvkov a zamieňa ich, ak sú v nesprávnom poradí.Názov Bublinové triedenie dostal svoje meno, pretože filtruje prvky navrchu poľa, napríklad bubliny, ktoré plávajú na vode.

Tu jepseudokód predstavujúci Algoritmus triedenia bublín (vzostupný kontext triedenia).

a [] je pole veľkosti N begin BubbleSort (a []) deklaruje celé číslo i, j pre i = 0 až N - 1 pre j = 0 až N - i - 1, ak a [j]> a [j + 1 ] potom vymeňte [j], [j + 1] koniec, ak koniec za návrat, koniec BubbleSort

Tento kód objednáva jednorozmerné pole N dátových položiek do vzostupného poradia. Vonkajšia slučka vedie N-1 cez pole. Každý prechod používa vnútornú slučku na výmenu dátových položiek, takže nasledujúca najmenšia dátová položka „bublinkuje“ smerom na začiatok poľa. Problém však je, že algoritmus potrebuje jeden celý prechod bez akejkoľvek výmeny, aby vedel, že je zoznam zoradený.

Najhoršia a priemerná časová zložitosť prípadu: O (n * n). Najhorší prípad nastane, keď je pole spätne zoradené.

Najlepšia časová náročnosť prípadu: O (n). Najlepší prípad nastane, keď je pole už zoradené.

Výber Zoradiť v jazyku Java

Triedenie podľa výberu je kombináciou vyhľadávania aj triedenia. Algoritmus zoradí pole tak, že opakovane nájde minimálny prvok (vzhľadom na vzostupné poradie) z netriedenej časti a umiestni ho na správne miesto v poli.

Tu je pseudokód predstavujúci algoritmus výberu zoradenia (vzostupný kontext triedenia).

a [] je pole veľkosti N begin SelectionSort (a []) pre i = 0 až n - 1 / * nastavte aktuálny prvok ako minimálny * / min = i / * nájdite minimálny prvok * / pre j = i + 1 to n if list [j]
Ako môžete pochopiť z kódu, počet prechodov poľa poľom je o jeden menší ako počet položiek v poli. Vnútorná slučka nájde nasledujúcu najmenšiu hodnotu a vonkajšia slučka umiestni túto hodnotu na svoje správne miesto. Výberové triedenie nikdy neurobí viac ako O (n) swapov a môže byť užitočné, keď je zápis do pamäte nákladná operácia.
 Časová zložitosť: O (n2), pretože existujú dve vnorené slučky.
 Pomocný priestor: Alebo (1).
 Vkladanie Triedenie v Jave 
Insertion Sort je jednoduchý algoritmus triedenia, ktorý prechádza zoznamom tak, že spotrebuje jeden vstupný prvok naraz a vytvorí konečné zoradené pole. Je to veľmi jednoduché a efektívnejšie pri menších súboroch údajov. Je to stabilná technika miestneho triedenia.
Tu je pseudokód predstavujúci algoritmus triedenia vloženia (vzostupný kontext triedenia).
a [] je pole veľkosti N begin InsertionSort (a []) pre i = 1 až N kľúč = a [i] j = i - 1 while (j> = 0 a a [j]> kľúč0 a [j + 1] = x [j] j = j - 1 koniec, zatiaľ čo [j + 1] = kľúčový koniec pre koniec InsertionSort
Ako ste pochopili z kódu, algoritmus triedenia vkladaniaodstráni jeden prvok zo vstupných údajov, vyhľadá miesto, kam patrí, v zoradenom zozname a vloží ho tam. Opakuje sa, kým žiadne vstupné prvky nezostanú nezoradené.
 Najlepší prípad: Najlepší prípad je, keď je vstupom pole, ktoré je už zoradené. V tomto prípade má triedenie vloženia lineárny čas chodu (t.j. & Theta (n)).
 V najhoršom prípade:  Najjednoduchším vstupom v najhoršom prípade je pole zoradené v opačnom poradí.
 QuickSort v Jave 
Algoritmus Quicksort je rýchly, rekurzívny a nestabilný algoritmus triedenia, ktorý funguje na princípe rozdelenia a dobytia. Vyberie prvok ako čap a rozdelí dané pole okolo tohto vybratého čapu.
 Kroky na implementáciu rýchleho triedenia:  
 
Vyberte vhodný „otočný bod“.
Zoznamy rozdeľte na dva zoznamyna základe tohto otočného prvku. Každý prvok, ktorý je menší ako otočný prvok, sa umiestni do ľavého zoznamu a každý väčší prvok sa umiestni do pravého zoznamu. Ak sa prvok rovná pivotnému prvku, môže ísť do ľubovoľného zoznamu. Toto sa nazýva operácia oddielu.
Rekurzívne triedte každý z menších zoznamov. 
Tu je pseudokód predstavujúci algoritmus Quicksort.
QuickSort (pole ako, nízke ako int, vysoké ako int) {if (nízke
Vo vyššie uvedenom pseudokóde oddiel () funkcia vykonáva činnosť oddielu a Quicksort () funkcia opakovane volá funkciu oddielu pre každý menší vygenerovaný zoznam. Zložitosť quicksortu je v priemernom prípade & Theta (n log (n)) a v najhoršom prípade & Theta (n2).
 Zlúčiť zoradenie v Jave 
Mergesort je rýchly, rekurzívny a stabilný algoritmus triedenia, ktorý funguje aj na princípe rozdelenia a dobytia. Podobne ako v prípade quicksortu, aj pri zlúčení sa zoznam prvkov rozdelí na dva zoznamy. Tieto zoznamy sú zoradené nezávisle a potom spojené. Počas kombinácie zoznamov sa prvky vkladajú (alebo spájajú) na správne miesto v zozname.
Tu je pseudokód predstavujúci algoritmus zlúčenia a roztriedenia.
postup MergeSort (a ako pole), ak (n == 1) vráti var l1 ako pole = a [0] ... a [n / 2] var l2 ako pole = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) vrátiť zlúčenie (l1, l2) ukončiť procedúru procedúry zlúčiť (a ako pole, b ako pole) var c ako pole while (a a b majú prvky) if ( a [0]> b [0]) pridať b [0] na koniec c odstrániť b [0] z b else pridať a [0] na koniec c odstrániť a [0] z konca, ak koniec while while (a má prvky) pridáva [0] na koniec c odstraňuje a [0] z konca while (b má prvky) pridáva b [0] na koniec c odstraňuje b [0] z b konca pri návrate c ukončiť postup
 mergesort () funkcia rozdelí zoznam na dva, hovory mergesort () na týchto zoznamoch osobitne a potom ich skombinuje tak, že ich odošle ako parametre do funkcie merge ().Algoritmus má zložitosť O (n log (n)) a má širokú škálu aplikácií.
 Hromadné triedenie v Jave 
Heapsort je porovnávací algoritmus založený na porovnaníBinárna halda dátová štruktúra. Môžete to považovať za vylepšenú verziu f triedenia, kderozdelí svoj vstup na zoradený a netriedený región a iteratívne zmenší netriedený región extrakciou najväčšieho prvku a jeho presunutím do zoradeného regiónu.
 Kroky na implementáciu Quicksortu (v rastúcom poradí): 
čo je tlmočník v jave
Vytvorte maximálnu hromadu pomocou triediaceho poľa
Pri tomto poinet, najväčšia položka je uložená v koreni haldy. Nahraďte ju poslednou položkou haldy a zmenšite veľkosť haldy o 1. Nakoniec heapifikujte koreň stromu
Vyššie uvedené kroky opakujte, kým veľkosť haldy nebude väčšia ako 1
Tu je pseudokód predstavujúci algoritmus triedenia haldy.
Heapsort (a ako pole) pre (i = n / 2 - 1) na i> = 0 heapify (a, n, i) pre i = n-1 na 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) larger = i // Inicializovať najväčší ako root int l eft = 2 * i + 1 // left = 2 * i + 1 int vpravo = 2 * i + 2 // doprava = 2 * i + 2 if (zľava [najväčší]) najväčší = zľava if (pravý a [najväčší]) najväčší = pravý if (najväčší! = I) swap ( a [i], A [najväčší]) Heapify (a, n, najväčší) koniec heapify
Okrem nich existujú aj ďalšie algoritmy triedenia, ktoré nie sú až také známe, ako napríklad Introsort, počítanie zoradenia atď. Prejdime na ďalšiu skupinu algoritmov v tomto článku „Dátové štruktúry a algoritmy“ a poďme preskúmať vyhľadávacie algoritmy.
 Vyhľadávanie algoritmov v jazyku Java 
Vyhľadávanie je jednou z najbežnejších a často vykonávaných akcií v bežných obchodných aplikáciách. Vyhľadávacie algoritmy sú algoritmy na vyhľadanie položky so špecifikovanými vlastnosťami v zbierke položiek. Pozrime sa na dva z najčastejšie používaných vyhľadávacích algoritmov.
 Algoritmus lineárneho vyhľadávania v Jave 
Najjednoduchším vyhľadávacím algoritmom je lineárne alebo sekvenčné vyhľadávanie. Zahŕňa postupné hľadanie prvku v danej dátovej štruktúre, kým sa element nenájde alebo sa nedosiahne koniec štruktúry. Ak sa prvok nájde, vráti sa umiestnenie položky, inak algoritmus vráti hodnotu NULL.
Tu je pseudokód predstavujúci lineárne vyhľadávanie v Jave:
postup linear_search (a [], hodnota) pre i = 0 až n-1, ak a [i] = hodnota, potom vytlačiť 'Nájdené' vráti i koniec, ak vypíše 'Nenašiel sa' koniec konca
Je toalgoritmus hrubej sily.Aj keď je to určite najjednoduchšie, určite nie je najbežnejšie kvôli jeho neefektívnosti. Časová zložitosť lineárneho vyhľadávania je O (N) .
 Algoritmus binárneho vyhľadávania v jazyku Java 
Binárne vyhľadávanie, tiež známe ako logaritmické vyhľadávanie, je vyhľadávací algoritmus, ktorý vyhľadáva pozíciu cieľovej hodnoty v už zoradenom poli. Rozdelí kolekciu vstupov na rovnaké polovice a položka sa porovná so stredným prvkom zoznamu. Ak je prvok nájdený, hľadanie tu končí. V opačnom prípade pokračujeme v hľadaní prvku rozdelením a výberom príslušného oddielu poľa na základe toho, či je cieľový prvok menší alebo väčší ako stredný prvok.
Tu je pseudokód predstavujúci binárne vyhľadávanie v Jave:
Procedúra binary_search zoradené pole n veľkosť poľa x hodnota, ktorá sa má prehľadať lowerBound = 1 upperBound = n zatiaľ čo x sa nenájde, ak upperBound
Vyhľadávanie sa ukončí, keď horná hranica (náš ukazovateľ) prejde okolo dolnej hranice (posledný prvok), čo znamená, že sme prehľadali celé pole a prvok nie je prítomný.Je to najbežnejšie používaný vyhľadávací algoritmus predovšetkým kvôli rýchlej dobe hľadania. Časová zložitosť binárneho vyhľadávania je O (N) čo je výrazné zlepšenie oproti O (N) časová zložitosť lineárneho vyhľadávania.
Týmto sa dostávame na koniec tohto článku „Dátové štruktúry a algoritmy v Jave“. Prebral som jednu z najzákladnejších a najdôležitejších tém Javy.Dúfam, že máte jasno vo všetkom, čo bolo s vami zdieľané v tomto článku.
  Určite cvičte čo najviac a obráťte sa na svoje skúsenosti.   
 Pozrite sa na    autor: Edureka, dôveryhodná online vzdelávacia spoločnosť so sieťou viac ako 250 000 spokojných študentov rozmiestnených po celom svete. Sme tu, aby sme vám pomohli na každom kroku na vašej ceste. Okrem otázok týkajúcich sa tohto rozhovoru pre jazyk java vymyslíme učebný plán určený pre študentov a profesionálov, ktorí sa chcú stať vývojármi Java. 
 Máte na nás otázku? Uveďte to v sekcii komentárov v tejto časti „Dátové štruktúry a algoritmy v Jave“.  článok a my sa vám ozveme čo najskôr.