Nejlepší datové struktury a algoritmy v Javě, které potřebujete vědět

Kdybych měl vybrat nejdůležitější téma vývoje softwaru, byly by to datové struktury a algoritmy. Můžete si to představit jako základní nástroj, který má každý počítačový programátor k dispozici. Při programování používáme datové struktury ukládat a organizovat data a algoritmy manipulovat s daty v těchto strukturách. Tento článek obsahuje podrobný přehled všech běžných datových struktur a algoritmů v umožnit čtenářům být dobře vybaveni.

Níže jsou uvedena témata diskutovaná v tomto článku:

• Datové struktury v Javě
  • Lineární datové struktury
  • Hierarchické datové struktury
• Algoritmy v Javě
  • Algoritmy řazení
  • Prohledávání algoritmů

Datové struktury v Javě

Datová struktura je způsob ukládání a organizace dat v počítači, aby bylo možné je efektivně využívat. Poskytuje prostředky pro efektivní správu velkého množství dat. A efektivní datové struktury jsou klíčem k navrhování efektivních algoritmů.

vv tomto článku „Datové struktury a algoritmy v Javě“ se budeme zabývat základními datovými strukturami, jako jsou:

• Lineární datové struktury
  • Spojový seznam
  • Hromádky
  • Fronty

• Hierarchické datové struktury
  • Binární stromy
  • Hromady
  • Hash tabulky

Podívejme se na každého z nich.

Lineární datové struktury v Javě

Lineární datové struktury v systému Windows jsou ty, jejichž prvky jsou sekvenční a uspořádané tak, že: existuje pouze jeden první prvek a má jen jednu další prvek , je jen jeden poslední prvek a má jen jednu předchozí prvek , zatímco všechny ostatní prvky mají a další a a předchozí živel.

Pole

An pole je lineární datová strukturapředstavující skupinu podobných prvků, přístupných indexem. Před uložením dat musí být uvedena velikost pole. Níže jsou uvedeny vlastnosti pole:

• Každý prvek v poli je stejného datového typu a má stejnou velikost
• Prvky pole jsou uloženy na souvislých paměťových místech, přičemž první prvek začíná na nejmenším paměťovém místě
• K prvkům pole lze přistupovat náhodně
• Struktura dat pole není zcela dynamická

rozdíl mezi xml a html

Například , můžeme chtít, aby videohra sledovala první desítky skóre této hry. Spíše než použít deset různých proměnné pro tento úkol bychom mohli použít jednotný název pro celou skupinu a pomocí indexových čísel odkazovat na nejvyšší skóre v této skupině.

Spojový seznam

NA je lineární datová struktura se shromažďováním více uzlů, kde eprvek ach ukládá svá vlastní data a ukazatel na umístění dalšího prvku. Poslední odkaz v propojeném seznamu ukazuje na null, což označuje konec řetězce. Prvek v propojeném seznamu se nazývá a uzel . První uzel se nazývá hlava .Poslední uzel je volánthe ocas .

Typy propojeného seznamu

Singly Linked List (Uni-Directional)

Doubly Linked List (Bi-Directional)

Kruhový propojený seznam

Zde je jednoduchý příklad: Představte si propojený seznam jako řetězec kancelářských sponek, které jsou spojeny dohromady. Nahoře nebo dole můžete snadno přidat další kancelářskou sponku. Je dokonce rychlé vložit jeden do středu. Jediné, co musíte udělat, je jednoduše odpojit řetěz uprostřed, přidat novou kancelářskou sponku a znovu připojit druhou polovinu. Propojený seznam je podobný.

Hromádky

Zásobník, abstraktní datová struktura, je sbírka předměty které se vkládají a odebírají podle last-in-first-out (LIFO) zásada. Objekty lze do zásobníku vložit kdykoli, ale kdykoli lze odebrat pouze naposledy vložený (tj. „Poslední“) objekt.Níže jsou uvedeny vlastnosti zásobníku:

• Je to objednávkový seznam, ve kterémvkládání a mazání lze provádět pouze na jednom konci, který se nazývá horní
• Rekurzivní datová struktura s ukazatelem na její horní prvek
• Následuje last-in-first-out (LIFO) zásada
• Podporuje dvě nejzákladnější metody
  • push (e): Vložte prvek e do horní části stohu
  • pop (): Odebere a vrátí horní prvek ze zásobníku

Mezi praktické příklady zásobníku patří při obrácení slova,zkontrolovat správnost závorkysekvence,implementace funkcí zpět do prohlížečů a mnoha dalších.

Fronty

jsou také dalším typem abstraktní datové struktury. Na rozdíl od zásobníku je fronta kolekce objektů, které se vkládají a odebírají podle first-in-first-out (FIFO) zásada. To znamená, že prvky lze vložit kdykoli, ale kdykoli lze odebrat pouze prvek, který byl ve frontě nejdelší.Níže jsou uvedeny vlastnosti fronty:

• Často se označuje jako first-in-first-out seznam
• Podporuje dvě nejzákladnější metody
  • enqueue (e): Vložte prvek e na zadní fronty
  • dequeue (): Odebrání a vrácení prvku z přední fronty

Fronty se používají vasynchronní přenos dat mezi dvěma procesy, plánování CPU, plánování disku a další situace, kdy jsou prostředky sdíleny mezi více uživateli a jsou poskytovány na serveru „kdo dřív přijde“. Dále v tomto článku „Datové struktury a algoritmy v Javě“ máme hierarchické datové struktury.

Hierarchické datové struktury v Javě

Binární strom

Binární strom je ahierarchické stromové datové struktury, ve kterých každý uzel má nejvýše dvě děti , které se označují jako levé dítě a správné dítě . Každý binární strom má následující skupiny uzlů:

• Root Node: Je to nejvyšší uzel a často se označuje jako hlavní uzelprotože na všechny ostatní uzly se lze dostat z kořenového adresáře
• Left Sub-Tree, což je také binární strom
• Right Sub-Tree, což je také binární strom

Níže jsou uvedeny vlastnosti binárního stromu:

• Binární strom lze procházet dvěma způsoby:
  • Procházení hloubky : In-order (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)
  • Šířka prvního průchodu : Traverz úrovně objednávky
• Časová složitost křížení stromu: O (n)
• Maximální počet uzlů na úrovni „l“ = 2^l-1.

Mezi aplikace binárních stromů patří:

• Používá se v mnoha vyhledávacích aplikacích, kde data neustále vstupují / odcházejí
• Jako pracovní postup pro skládání digitálních obrázků pro vizuální efekty
• Používá se téměř v každém routeru s velkou šířkou pásma pro ukládání tabulek routerů
• Používá se také při bezdrátových sítích a přidělování paměti
• Používá se v kompresních algoritmech a mnoha dalších

Binární halda

Binární halda je kompletníbinární strom, který odpovídá na vlastnost haldy. Jednoduše řečenoje variace binárního stromu s následujícími vlastnostmi:

• Halda je kompletní binární strom: O stromu se říká, že je úplný, pokud jsou úplné všechny jeho úrovně, kromě nejhlubších. Tdíky jeho vlastnosti Binary Heap je vhodné být uložen v .
• Následuje vlastnost haldy: Binární halda je buď a Min. Hromada nebo a Max. Hromada .
  • Min. Binární halda: Fnebo každý uzel v haldě, hodnota uzlu je menší nebo rovno hodnoty dětí
  • Max. Binární halda: Fnebo každý uzel v haldě, hodnota uzlu je větší nebo rovno hodnoty dětí

Mezi oblíbené aplikace binární haldy patříimplementace efektivních prioritních front, efektivní vyhledání k nejmenších (nebo největších) prvků v poli a mnoho dalších.

Hash tabulky

Představte si, že máte objekt a chcete mu přiřadit klíč, aby bylo hledání velmi snadné. Chcete-li uložit tento pár klíč / hodnota, můžete použít jednoduché pole, jako je datová struktura, kde lze klíče (celá čísla) použít přímo jako index k ukládání datových hodnot. V případech, kdy jsou klíče příliš velké a nelze je použít přímo jako index, se však používá technika zvaná hashování.

Při hašování se velké klávesy převádějí na malé pomocí hashovací funkce . Hodnoty se poté uloží do datové struktury s názvemna hash tabulka. Hašovací tabulka je datová struktura, která implementuje slovník ADT, strukturu, která dokáže namapovat jedinečné klíče na hodnoty.

Obecně má hash tabulka dvě hlavní komponenty:

1. Pole lopaty: Pole kbelíku pro hashovací tabulku je pole A o velikosti N, kde je každá buňka A považována za „kbelík“, tj. Soubor párů klíč – hodnota. Celé číslo N definuje kapacitu pole.
2. Funkce hash: Je to jakákoli funkce, která mapuje každý klíč k na naší mapě na celé číslo v rozsahu [0, N a minus 1], kde N je kapacita pole kbelíku pro tuto tabulku.

Když vložíme objekty do hashtable, je možné, že různé objekty mohou mít stejný hashcode. Tomu se říká a srážka . Pro řešení kolize existují techniky, jako je řetězení a otevřené adresování.

Jedná se o některé základní a nejčastěji používané datové struktury v Javě. Nyní, když jste si vědomi každého z nich, můžete je začít implementovat do svého . Tím jsme dokončili první část tohoto článku „Datové struktury a algoritmy v Javě“. V další části se dozvíme něco ozákladní algoritmy a jejich použití v praktických aplikacích, jako je třídění a vyhledávání, dělení a dobývání, chamtivé algoritmy, dynamické programování.

Algoritmy v Javě

Historicky používané jako nástroj pro řešení složitých matematických výpočtů jsou algoritmy hluboce spojeny s informatikou a zejména s datovými strukturami. Algoritmus je posloupnost pokynů, která popisuje způsob řešení konkrétního problému v konečném časovém období. Jsou zastoupeny dvěma způsoby:

• Vývojové diagramy - Je tovizuální reprezentace toku řízení algoritmu
• Pseudo kód - Toje textová reprezentace algoritmu, který přibližuje konečný zdrojový kód

Poznámka: Výkonnost algoritmu se měří na základě časové a prostorové složitosti. Složitost jakéhokoli algoritmu většinou závisí na problému a na samotném algoritmu.

Pojďme prozkoumat dvě hlavní kategorie algoritmů v Javě, kterými jsou:

• Třídění algoritmů v Javě
• Hledání algoritmů v Javě

Třídění algoritmů v Javě

Algoritmy řazení jsou algoritmy, které dávají prvky seznamu v určitém pořadí. Nejčastěji používané objednávky jsou číselné pořadí a lexikografické pořadí. V tomto článku „Datové struktury a algoritmy“ prozkoumáme několik třídicích algoritmů.

Bubble Sort v Javě

Bubble Sort, často označovaný jako potopení, je nejjednodušší algoritmus třídění. Opakovaně prochází seznam, který má být seřazen, porovnává každou dvojici sousedních prvků a zaměňuje je, pokud jsou ve špatném pořadí.Název Bubble sort dostává své jméno, protože filtruje prvky do horní části pole, jako jsou bubliny, které se vznášejí na vodě.

Tady jepseudokód představující Algoritmus řazení bublin (vzestupný kontext řazení).

a [] je pole velikosti N začátek BubbleSort (a []) deklaruje celé číslo i, j pro i = 0 až N - 1 pro j = 0 až N - i - 1, pokud a [j]> a [j + 1 ] poté vyměňte [j], [j + 1] konec, pokud konec za návrat, konec BubbleSort

Tento kód objednává jednorozměrné pole N datových položek do vzestupného pořadí. Vnější smyčka umožňuje průchod N-1 přes pole. Každý průchod používá vnitřní smyčku k výměně datových položek tak, že další nejmenší datová položka „bublá“ směrem k začátku pole. Problém však je, že algoritmus potřebuje jeden celý průchod bez jakéhokoli swapu, aby věděl, že je seznam seřazen.

Nejhorší a průměrná časová složitost případu: O (n * n). Nejhorší případ nastane, když je pole obráceně tříděno.

Nejlepší časová složitost případu: Na). Nejlepší případ nastane, když je pole již seřazené.

Výběr Seřadit v Javě

Třídění podle výběru je kombinací vyhledávání i třídění. Algoritmus třídí pole opakovaným nalezením minimálního prvku (s ohledem na vzestupné pořadí) z netříděné části a jeho umístěním do správné polohy v poli.

Zde je pseudokód představující algoritmus výběru řazení (vzestupný kontext řazení).

a [] je pole velikosti N začátek SelectionSort (a []) pro i = 0 až n - 1 / * nastavit aktuální prvek jako minimum * / min = i / * najít minimální prvek * / pro j = i + 1 to n if list [j]
Jak můžete pochopit z kódu, počet procházení pole maticí je o jeden menší než počet položek v matici. Vnitřní smyčka najde další nejmenší hodnotu a vnější smyčka umístí tuto hodnotu na správné místo. Selection selection never makes more than O (n) swaps and can be useful when the memory write is a costly operation.
 Časová složitost: Na2), protože existují dvě vnořené smyčky.
 Pomocný prostor: Nebo (1).
 Vložení třídění v Javě 
Insertion Sort je jednoduchý třídicí algoritmus, který iteruje seznamem tím, že spotřebovává jeden vstupní prvek najednou a vytváří konečné seřazené pole. Je to velmi jednoduché a efektivnější na menších souborech dat. Je to stabilní a na místě používaná technika třídění.
Zde je pseudokód představující algoritmus řazení řazení (vzestupný kontext řazení).
a [] je pole velikosti N begin InsertionSort (a []) pro i = 1 až N klíč = a [i] j = i - 1 while (j> = 0 a a [j]> klíč0 a [j + 1] = x [j] j = j - 1 konec, zatímco [j + 1] = klíčový konec pro konec InsertionSort
Jak můžete pochopit z kódu, algoritmus třídění vkládáníodebere jeden prvek ze vstupních dat, vyhledá místo, kam patří, v seřazeném seznamu a vloží jej tam. Opakuje se, dokud žádné vstupní prvky nezůstanou netříděné.
 Nejlepší případ: Nejlepším případem je, když je vstup pole, které je již tříděno. V tomto případě má třídění vložení lineární dobu chodu (tj. & Theta (n)).
 Nejhorší případ:  Nejjednodušším vstupem v nejhorším případě je pole seřazené v opačném pořadí.
 QuickSort v Javě 
Algoritmus Quicksort je rychlý, rekurzivní, nestabilní algoritmus řazení, který funguje na principu rozděl a panuj. Vybírá prvek jako pivot a rozděluje dané pole kolem tohoto vybraného pivot.
 Kroky k implementaci rychlého řazení:  
 
Vyberte vhodný „otočný bod“.
Rozdělte seznamy na dva seznamyna základě tohoto otočného prvku. Každý prvek, který je menší než otočný prvek, je umístěn v levém seznamu a každý prvek, který je větší, je umístěn v pravém seznamu. Pokud se prvek rovná prvku pivot, může jít do libovolného seznamu. Tomu se říká operace oddílu.
Rekurzivně seřaďte každý z menších seznamů. 
Tady je pseudokód představující algoritmus Quicksort.
QuickSort (A jako pole, nízké jako int, vysoké jako int) {if (nízké
Ve výše uvedeném pseudokódu rozdělit() funkce provádí činnost oddílu a Quicksort () funkce opakovaně volá funkci oddílu pro každý generovaný menší seznam. Složitost quicksortu je v průměrném případě & Theta (n log (n)) a v nejhorším případě & Theta (n2).
 Sloučit řazení v Javě 
Mergesort je rychlý, rekurzivní a stabilní algoritmus třídění, který funguje také na principu rozděl a panuj. Podobně jako quicksort rozděluje sloučení seznam prvků do dvou seznamů. Tyto seznamy jsou tříděny samostatně a poté kombinovány. Během kombinace seznamů jsou prvky vloženy (nebo sloučeny) na správném místě v seznamu.
Zde je pseudokód představující algoritmus sloučení řazení.
postup MergeSort (jako pole), pokud (n == 1) vrátí var l1 jako pole = a [0] ... a [n / 2] var l2 jako pole = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) návratové sloučení (l1, l2) ukončení procedury procedury sloučení (a jako pole, b jako pole) var c jako pole while (a a b mají prvky) if ( a [0]> b [0]) přidat b [0] na konec c odebrat b [0] z b else přidat a [0] na konec c odstranit a [0] z konce, pokud end while while (a má prvky) přidá [0] na konec c odebere a [0] z konce while (b má prvky) přidá b [0] na konec c odebere b [0] z b konce při návratu c ukončete postup
 Sloučit třídění() funkce rozdělí seznam na dva, volání Sloučit třídění() na těchto seznamech samostatně a poté je zkombinuje odesláním jako parametrů do funkce merge ().Algoritmus má složitost O (n log (n)) a má širokou škálu aplikací.
 Hromadit řazení v Javě 
Heapsort je třídicí algoritmus založený na srovnáníBinární halda datová struktura. Můžete si to představit jako vylepšenou verzi pro výběr výběru, kderozdělí svůj vstup na tříděnou a netříděnou oblast a iterativně zmenší netříděnou oblast extrahováním největšího prvku a přesunutím do seřazené oblasti.
 Kroky k implementaci Quicksort (ve vzestupném pořadí): 
co je kuchař a loutka
Vytvořte maximální hromadu pomocí třídicího pole
V tuto chvílit, největší položka je uložena v kořenovém adresáři haldy. Nahraďte ji poslední položkou haldy a zmenšete velikost haldy o 1. Nakonec heapify kořen stromu
Výše uvedené kroky opakujte, dokud nebude halda větší než 1
Zde je pseudokód představující algoritmus třídění haldy.
Heapsort (a jako pole) pro (i = n / 2 - 1) na i> = 0 heapify (a, n, i) pro 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 // Inicializovat největší jako root int l eft = 2 * i + 1 // left = 2 * i + 1 int vpravo = 2 * i + 2 // vpravo = 2 * i + 2 if (vlevo [největší]) největší = vlevo if (vpravo a [největší]) největší = vpravo if (největší! = I) vyměnit ( a [i], A [největší]) Heapify (a, n, největší) konec heapify
Kromě toho existují i ​​jiné algoritmy řazení, které nejsou tak dobře známé, například Introsort, počítání řazení atd. Přejdeme k další sadě algoritmů v tomto článku „Datové struktury a algoritmy“, pojďme prozkoumat vyhledávací algoritmy.
 Hledání algoritmů v Javě 
Hledání je jednou z nejběžnějších a nejčastěji prováděných akcí v běžných podnikových aplikacích. Vyhledávací algoritmy jsou algoritmy pro vyhledání položky se zadanými vlastnostmi v kolekci položek. Prozkoumejme dva z nejčastěji používaných vyhledávacích algoritmů.
 Algoritmus lineárního vyhledávání v Javě 
Lineární vyhledávání nebo sekvenční vyhledávání je nejjednodušší vyhledávací algoritmus. Zahrnuje postupné vyhledávání prvku v dané datové struktuře, dokud není prvek nalezen nebo je dosaženo konce struktury. Pokud je prvek nalezen, je vráceno umístění položky, jinak algoritmus vrátí NULL.
Zde je pseudokód představující lineární vyhledávání v Javě:
postup linear_search (a [], hodnota) pro i = 0 až n-1, pokud a [i] = hodnota, pak vytisknout 'Nalezeno' vrátit i konec, pokud vytisknout 'Nenalezeno' konec pro konec linear_search
Je toalgoritmus hrubé síly.I když je to určitě nejjednodušší, rozhodně to není nejběžnější, kvůli jeho neúčinnosti. Časová složitost lineárního vyhledávání je NA) .
 Algoritmus binárního vyhledávání v Javě 
Binární vyhledávání, také známé jako logaritmické vyhledávání, je vyhledávací algoritmus, který najde pozici cílové hodnoty v již seřazeném poli. Rozdělí vstupní kolekci na stejné poloviny a položka se porovná se středním prvkem seznamu. Pokud je prvek nalezen, hledání zde končí. Jinak pokračujeme v hledání prvku rozdělením a výběrem příslušného oddílu pole na základě toho, zda je cílový prvek menší nebo větší než prostřední prvek.
Zde je pseudokód představující binární vyhledávání v Javě:
Procedura binary_search a seřazené pole n velikost pole x hodnota, která má být prohledána lowerBound = 1 upperBound = n zatímco x nebyl nalezen, pokud upperBound
Hledání končí, když upperBound (náš ukazatel) přejde lowerBound (poslední prvek), což znamená, že jsme prohledali celé pole a prvek není přítomen.Jedná se o nejčastěji používané vyhledávací algoritmy především kvůli jeho rychlému vyhledávacímu času. Časová složitost binárního vyhledávání je NA) což je výrazné zlepšení oproti NA) časová složitost lineárního vyhledávání.
Tím se dostáváme na konec tohoto článku „Datové struktury a algoritmy v Javě“. Probral jsem jedno z nejzásadnějších a nejdůležitějších témat Javy.Doufám, že máte jasno se vším, co bylo s vámi v tomto článku sdíleno.
  Ujistěte se, že cvičíte co nejvíce a vraťte své zkušenosti.   
 Podívejte se na    Edureka, důvěryhodná online vzdělávací společnost se sítí více než 250 000 spokojených studentů po celém světě. Jsme tu, abychom vám pomohli s každým krokem na vaší cestě, abychom se kromě otázek týkajících se tohoto rozhovoru pro javu stali i učebním plánem, který je určen pro studenty a profesionály, kteří chtějí být vývojářem Java. 
 Máte na nás dotaz? Uveďte to prosím v sekci komentářů v této „Datové struktuře a algoritmech v Javě“  článku a my se vám ozveme co nejdříve.