A Java legfontosabb adatstruktúrái és algoritmusai, amelyeket tudnia kell

Ha a szoftverfejlesztésben az egyetlen legfontosabb témát kellene választanom, akkor az adatstruktúrák és algoritmusok lennének. Úgy gondolhat rá, mint minden számítógépes programozó számára elérhető alapvető eszközre. Programozás közben használjuk adatszerkezetek - adatok tárolására és rendszerezésére, és algoritmusok manipulálni az adatokat azokban a struktúrákban. Ez a cikk az összes általános adatszerkezet és algoritmus részletes áttekintését tartalmazza hogy az olvasók jól felszereltek legyenek.

Az alábbiakban felsoroljuk a cikkben tárgyalt témákat:

mi a különbség a c ++ és a java között

• Adatszerkezetek Java-ban
  • Lineáris adatszerkezetek
  • Hierarchikus adatszerkezetek
• Algoritmusok Java-ban
  • Algoritmusok rendezése
  • Algoritmusok keresése

Adatszerkezetek Java-ban

Az adatstruktúra az adatok számítógépen történő tárolásának és rendszerezésének egyik módja annak hatékony felhasználása érdekében. Lehetőséget nyújt nagy mennyiségű adat hatékony kezelésére. A hatékony adatstruktúrák pedig kulcsfontosságúak a hatékony algoritmusok tervezéséhez.

Ban benebben az „Adatszerkezetek és algoritmusok a Java-ban” cikkben olyan alapvető adatszerkezetekre térünk ki, mint például:

• Lineáris adatszerkezetek
  • Összekapcsolt lista
  • Verem
  • Sorok

• Hierarchikus adatszerkezetek
  • Bináris fák
  • Halmok
  • Hash Tables

Nézzük meg mindegyiket.

Lineáris adatszerkezetek a Java-ban

Lineáris adatszerkezetek azok, amelyek elemei egymást követik, és úgy vannak rendezve, hogy: csak egy van első elem és csak egy van következő elem , csak egy van utolsó elem és csak egy van előző elem , míg az összes többi elemnek van egy következő és a előző elem.

Tömbök

An sor egy lineáris adatszerkezethasonló elemek csoportját képviseli, index alapján érhető el. Az adatok tárolása előtt meg kell adni egy tömb méretét. Az alábbiakban felsoroljuk egy tömb tulajdonságait:

• A tömb minden eleme azonos adattípusú és azonos méretű
• A tömb elemeit egybefüggő memóriahelyeken tárolják, és az első elem a legkisebb memóriahelyen kezdődik
• A tömb elemeihez véletlenszerűen lehet hozzáférni
• A tömb adatstruktúrája nem teljesen dinamikus

Például , érdemes lehet egy videojáték követni az adott játék tíz legjobb eredményét. Ahelyett, hogy tíz különbözőt használna változók Ehhez a feladathoz egyetlen nevet használhatunk a teljes csoporthoz, és indexszámokkal hivatkozhatunk az adott csoport magas pontszámaira.

Összekapcsolt lista

NAK NEK egy lineáris adatstruktúra több csomópont gyűjtésével, ahol plAz ach elem tárolja a saját adatait és egy mutatót a következő elem helyére. A csatolt lista utolsó linkje nullára mutat, jelezve a lánc végét. A csatolt listák egyik elemét a-nak nevezzük csomópont . Az első csomópont a fej .Az utolsó csomópontot hívjuk megaz farok .

A kapcsolt lista típusai

Egyszerűen összekapcsolt lista (egyirányú)

Kétszer összekapcsolt lista (kétirányú)

Kör alakú összekapcsolt lista

Íme egy egyszerű példa: Képzeljen el egy összekapcsolt listát, például egy összekapcsolt gemkapocsláncot. Könnyedén hozzáadhat egy újabb gemkapcsot a tetejére vagy az aljára. Még gyorsan is be lehet illeszteni egyet a közepébe. Csak annyit kell tennie, hogy csak leválasztja a láncot a közepén, hozzáadja az új gemkapcsot, majd csatlakoztassa újra a másik felét. A linkelt lista hasonló.

Verem

Kazal, egy absztrakt adatszerkezet, az tárgyakat amelyeket a szerint illesztenek be és távolítanak el last-in-first-out (LIFO) elv. Az objektumokat bármikor be lehet illeszteni a verembe, de bármikor csak a legutóbb beillesztett (vagyis „utolsó”) objektumot lehet eltávolítani.Az alábbiakban felsoroljuk a verem tulajdonságait:

• Ez egy orderd lista, amelybena beillesztés és a törlés csak az egyik végén hajtható végre tetejére
• Rekurzív adatstruktúra, mutatóval a legfelső elemére
• Követi a last-in-first-out (LIFO) elv
• Két alapvető módszert támogat
  • nyomja (e): Helyezze be az e elemet a verem tetejére
  • pop (): Távolítsa el és helyezze vissza a verem legfelső elemét

A verem gyakorlati példái közé tartozik a szó megfordítása,ellenőrzésének helyességét zárójelbensorrend,a hátsó funkcionalitás megvalósítása a böngészőkben és még sok másban.

Sorok

az elvont adatszerkezet másik típusa. A veremtől eltérően a sor objektumok gyűjteménye, amelyeket a first-in-first-out (FIFO) elv. Vagyis elemeket bármikor be lehet illeszteni, de csak azt az elemet lehet bármikor eltávolítani, amelyik a leghosszabb ideig állt a sorban.Az alábbiakban felsoroljuk a sor tulajdonságait:

• Gyakran nevezik first-in-first-out lista
• Két alapvető módszert támogat
  • enqueue (e): Helyezze be az e elemet a hátulsó a sorból
  • dequeue (): Távolítsa el és adja vissza az elemet a elülső a sorból

Sorokat használnak aaszinkron adatátvitel két folyamat között, a CPU ütemezése, a Lemezütemezés és más olyan helyzetek, amikor az erőforrásokat több felhasználó osztja meg, és az elsőbbségi kiszolgáló alapján szolgáltatják ki. Ezután az „Adatszerkezetek és algoritmusok a Java-ban” cikkben hierarchikus adatstruktúrákkal rendelkezünk.

Hierarchikus adatszerkezetek a Java-ban

Bináris fa

A bináris fa egyhierarchikus fa adatszerkezetek, amelyekben mindegyik csomópontnak legfeljebb két gyermeke van , amelyekre a bal gyermek és a helyes gyerek . Minden bináris fának a következő csomópontcsoportok vannak:

• Gyökércsomópont: Ez a legfelső csomópont, és gyakran nevezik fő csomópontnakmert az összes többi csomópont a gyökérből érhető el
• Bal alfa, amely szintén bináris fa
• Jobb alfa, amely szintén bináris fa

Az alábbiakban felsoroljuk a bináris fa tulajdonságait:

• A bináris fát kétféleképpen lehet bejárni:
  • Mélység első bejárása : Sorrendben (bal-jobb-jobb-jobb), előrendelés (gyökér-bal-jobb-jobb) és postarend (bal-jobb-jobb-gyökér)
  • Szélesség első bejárása : Szintű sorrend bejárása
• A fák bejárásának időbeli összetettsége: O (n)
• A csomópontok maximális száma az „l” = 2 szinten^l-1.

A bináris fák alkalmazásai a következők:

• Számos keresési alkalmazásban használják, ahol az adatok folyamatosan beérkeznek / távoznak
• A digitális képek vizuális effektusok összeállításának munkafolyamataként
• Szinte minden nagy sávszélességű útválasztóban használják routertáblák tárolására
• Vezeték nélküli hálózatban és memóriaallokációban is használják
• Tömörítési algoritmusokban és még sok másban használják

Bináris kupac

A bináris kupac teljesbináris fa, amely válaszol a kupac tulajdonságra. Egyszerűbben fogalmazvaegy bináris fa változata a következő tulajdonságokkal:

• A halom egy teljes bináris fa: Egy fáról azt mondják, hogy teljes, ha minden szintje, kivéve a legmélyebbet, teljes. Ta bináris halom tulajdonsága alkalmassá teszi egy .
• Halom tulajdonságát követi: A bináris halom vagy a Min-Heap vagy a Max-Heap .
  • Min bináris halom: Fvagy minden kupacban lévő csomópont, a csomópont értéke kisebb vagy egyenlő a gyermekek értékei
  • Max bináris halom: Fvagy egy halom minden csomópontjánál a csomópont értéke nagyobb vagy egyenlő a gyermekek értékei

A bináris kupac népszerű alkalmazásai a következők:hatékony prioritási várólisták megvalósítása, a k legkisebb (vagy legnagyobb) elem hatékony megtalálása egy tömbben és még sok más.

Hash Tables

Képzelje el, hogy van egy tárgy és hozzá akar rendelni egy kulcsot a keresés megkönnyítéséhez. A kulcs / érték pár tárolásához használhat egy egyszerű tömböt, például egy adatstruktúrát, ahol a kulcsokat (egész számokat) közvetlenül indexként lehet felhasználni az adatértékek tárolásához. Azokban az esetekben azonban, amikor a kulcsok túl nagyok, és nem használhatók közvetlenül indexként, a kivonatolásnak nevezett technikát alkalmazzák.

A kivonatoláskor a nagy kulcsokat a használatával kis kulcsokká alakítják hash funkciók . Az értékeket ezután egy ún. Adatstruktúrában tároljuknak nek hash asztal. A hash tábla olyan adatstruktúra, amely megvalósítja az ADT szótárat, egy olyan struktúrát, amely egyedi kulcsokat képes leképezni az értékekre.

Általában egy hash-tábla két fő összetevőből áll:

1. Vödör tömb: A hash tábla vázlattömbje N méretű A tömb, ahol A minden celláját „vödörnek”, azaz kulcs-érték párok gyűjteményének tekintik. Az N egész szám határozza meg a tömb kapacitását.
2. Hash funkció: Bármely függvény leképezi a térképünk minden egyes k kulcsát a [0, N és mínusz 1] tartományba eső egész számra, ahol N a táblázat tömbtömbjének kapacitása.

Ha objektumokat rakunk hashtable-be, akkor lehetséges, hogy a különböző objektumoknak ugyanaz a hashcode. Ezt hívják a ütközés . Az ütközés kezelésére léteznek olyan technikák, mint a láncolás és a nyílt címzés.

Tehát ezek néhány alapvető és leggyakrabban használt adatstruktúra a Java-ban. Most, hogy ezek mindegyikével tisztában van, elkezdheti ezeket megvalósítani a sajátjában . Ezzel befejeztük ’ennek a’ Adatszerkezetek és algoritmusok a Java-ban ’cikk első részét. A következő részben megismerkedünkaz alapvető algoritmusok és azok gyakorlati alkalmazásában való felhasználása, például válogatás és keresés, osztás és meghódítás, kapzsi algoritmusok, dinamikus programozás.

Algoritmusok Java-ban

A bonyolult matematikai számítások megoldásának eszközeként használt algoritmusok története szorosan kapcsolódik a számítástechnikához és különösen az adatstruktúrákhoz. Egy algoritmus az utasítások sorozata, amely leírja egy adott probléma megoldását véges idő alatt. Kétféle módon vannak képviselve:

• Folyamatábra - Ez egyegy algoritmus vezérlési folyamatának vizuális ábrázolása
• Álkód - Aztegy olyan algoritmus szöveges ábrázolása, amely közelíti a végső forráskódot

Jegyzet: Az algoritmus teljesítményét az idő és a tér összetettsége alapján mérik. Leginkább bármely algoritmus összetettsége a problémától és magától az algoritmustól függ.

Fedezzük fel a Java algoritmusainak két fő kategóriáját, amelyek:

• Algoritmusok rendezése Java-ban
• Algoritmusok keresése Java-ban

Algoritmusok rendezése Java-ban

A rendezési algoritmusok olyan algoritmusok, amelyek egy lista elemeit egy bizonyos sorrendbe teszik. A leggyakrabban használt sorrendek a numerikus sorrend és a lexikográfiai sorrend. Ebben az „Adatszerkezetek és algoritmusok” cikkben feltárhatunk néhány rendezési algoritmust.

Bubble Sort Java-ban

A Bubble Sort, amelyet gyakran süllyedő rendezésnek neveznek, a legegyszerűbb rendezési algoritmus. Ismételten végigméri a rendezendő listát, összehasonlítja a szomszédos elemek egyes párjait és felcseréli őket, ha rossz sorrendben vannak.A buborékfajta azért kapta a nevét, mert kiszűri az elemeket a tömb tetejére, mint a vízen lebegő buborékok.

Itt vana Bubble Sort algoritmust ábrázoló álkód (növekvő rendezési kontextus).

a [] egy N méretű tömb, a BubbleSort (a []) deklarálja az i egész számot, j = i = 0 - N - 1, ha j = 0 - N - i - 1, ha a [j]> a [j + 1 ], majd cseréljen egy [j], egy [j + 1] véget, ha véget, és adja vissza a BubbleSort végét

Ez a kód N adatelem egydimenziós tömbjét növekvő sorrendbe rendezi. Egy külső hurok révén az N-1 áthalad a tömbön. Minden lépés egy belső hurkot használ az adatelemek cseréjére, így a következő legkisebb adatelem a tömb eleje felé „buborékzik”. De a probléma az, hogy az algoritmusnak egyetlen egész lépésre van szüksége minden csere nélkül, hogy tudja, hogy a lista rendezve van.

A legrosszabb és átlagos eset-összetettség: O (n * n). A legrosszabb eset akkor fordul elő, ha egy tömböt fordított sorrendbe rendeznek.

Legjobb eset komplexitás: Tovább). A legjobb eset akkor következik be, amikor egy tömb már rendezve van.

Válogatás Rendezés Java-ban

A kijelölés rendezése a keresés és a rendezés kombinációja. Az algoritmus úgy rendezi a tömböt, hogy többször megtalálja a minimális elemet (figyelembe véve a növekvő sorrendet) a nem rendezett részből, és megfelelő helyre teszi a tömbben.

Itt található a Selection Sort Algorithm (növekvő rendezési kontextus) ábrázoló álkód.

a [] egy N méretű tömb, kezdődik SelectionSort (a []) i = 0-tól n-ig - 1 / * állítsa az aktuális elemet minimumra * / min = i / * keresse meg a minimális elemet * / j = i + 1 esetén n-ig, ha a [j] lista
Mint a kódból meg lehet érteni, a rendezés tömbön való áthaladásának száma eggyel kevesebb, mint a tömbben lévő elemek száma. A belső hurok megtalálja a következő legkisebb értéket, a külső hurok pedig ezt az értéket a megfelelő helyre helyezi. A választási rendezés soha nem végez többet O (n) csere mellett, és hasznos lehet, ha a memóriaírás költséges művelet.
 Idő összetettsége: Tovább2), mivel két beágyazott hurok van.
 Kiegészítő tér: Vagy (1).
 Beszúrás Rendezés Java-ban 
Az Insertion Sort egy egyszerű rendezési algoritmus, amely végigvezet a listán egy-egy beviteli elem felhasználásával, és felépíti a végső rendezett tömböt. Nagyon egyszerű és hatékonyabb kisebb adathalmazok esetén. Stabil és hely szerinti válogatási technika.
Itt található a beszúrás rendezési algoritmust ábrázoló álkód (növekvő rendezési kontextus).
a [] egy N méretű tömb, kezdődik az InsertionSort (a []) i = 1-től N-ig = a [i] j = i - 1, míg (j> = 0 és a [j]> billentyű0 a [j + 1] = x [j] j = j - 1 vég, míg a [j + 1] = kulcs vége az InsertionSort végéhez
Amint a kódból meg lehet érteni, a beszúrás rendezési algoritmuseltávolít egy elemet a bemeneti adatokból, megtalálja a helyet, amelyhez tartozik a rendezett listán, és beszúrja oda. Addig ismétel, amíg egyetlen bemeneti elem sem marad rendezetlen.
 Legjobb eset: A legjobb eset az, amikor a bemenet egy már rendezett tömb. Ebben az esetben a beillesztés rendezésének lineáris futási ideje van (azaz & Theta (n)).
 Legrosszabb esetben:  A legegyszerűbb legrosszabb eset egy fordított sorrendbe rendezett tömb.
 QuickSort Java-ban 
A Quicksort algoritmus egy gyors, rekurzív, nem stabil rendezési algoritmus, amely az osztás és meghódítás elv alapján működik. Kiválaszt egy elemet pivotként és felosztja az adott tömböt a kiválasztott pivot köré.
 A gyors rendezés megvalósításának lépései:  
 
Válasszon megfelelő „forgópontot”.
Ossza fel a listákat két listáraezen pivot elem alapján. Minden elem, amely kisebb, mint a forgó elem, a bal listába kerül, és minden nagyobb elem a jobb oldali listába kerül. Ha egy elem egyenlő a pivot elemmel, akkor bármelyik listában szerepelhet. Ezt partíciós műveletnek nevezzük.
Rekurzívan rendezze a kisebb listákat. 
Itt van a Quicksort algoritmust ábrázoló álkód.
QuickSort (A mint tömb, alacsony mint int, magas, mint int) {if (alacsony
A fenti álkódban partíció () funkció végrehajtja a partíció működését és Quicksort () function ismételten meghívja a partíciós függvényeket minden kisebb generált listához. A quicksort összetettsége átlagos esetben a & Theta (n log (n)), legrosszabb esetben pedig a & Theta (n2).
 Egyesítés rendezés Java-ban 
A Mergesort egy gyors, rekurzív, stabil rendezési algoritmus, amely az osztás és meghódítás elvével is működik. A quardsorthoz hasonlóan az egyesítés rendezése két listára osztja az elemek listáját. Ezeket a listákat egymástól függetlenül rendezzük, majd egyesítjük. A listák kombinálása során az elemeket a lista megfelelő helyre illesztik (vagy egyesítik).
Íme a Merge Sort algoritmust ábrázoló álkód.
egyesítés rendezési kód c ++
eljárás MergeSort (a mint tömb), ha (n == 1) egy var l1 értéket ad vissza tömbként = a [0] ... a [n / 2] var l2 tömbként = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end eljárás eljárás egyesítés (a mint tömb, b mint tömb) var c tömb, míg (a és b elemekkel rendelkezik), ha ( a [0]> b [0]) adj b [0] -t a c végéhez távolítsd el b [0] a b-ből, vagy adj hozzá egy [0] -t a c végéhez távolítsd el a [0] -t a végéről, ha vége (a-nak vannak elemei) adjon hozzá egy [0] -t a c végéhez, távolítson el egy [0] -t a végétől, míg (b-nek vannak elemei) adjon hozzá b [0] -t c végéhez, távolítsa el b [0] -ot c az eljárás befejezése
 mergesort () függvény felosztja a listát két hívásra mergesort () ezeken a listákon külön-külön, majd egyesíti őket paraméterek küldésével az egyesítés () függvényhez.Az algoritmus bonyolult O-val (n log (n)), és sokféle alkalmazási lehetőséggel rendelkezik.
 Halom rendezés Java-ban 
A Heapsort egy összehasonlításon alapuló rendezési algoritmusBináris kupac adatstruktúra. Elképzelhető, hogy az f változat továbbfejlesztett válogatása, hola bemenetet rendezett és nem rendezett régióra osztja, és a nem rendezett régiót iteratív módon zsugorítja a legnagyobb elem kivonásával és azt a rendezett régióba helyezve.
 A Quicksort megvalósításának lépései (növekvő sorrendben): 
Készítsen egy maximális kupacot a rendező tömb segítségével
Ennél a poénnált, a legnagyobb elemet a halom gyökerében tárolják. Cserélje ki a kupac utolsó elemére, és csökkentse a kupac méretét 1-gyel. Végül halmozza fel a fa gyökerét
Ismételje meg a fenti lépéseket, amíg a kupac mérete nagyobb lesz, mint 1
Itt van a halom rendezési algoritmust ábrázoló álkód.
Heapsort (a tömb) az (i = n / 2 - 1) - i> = 0 heapify (a, n, i) helyett i = n-1 - 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a mint tömb, n mint int, i mint int) legnagyobb = i // A legnagyobb inicializálása gyökérként int l eft = 2 * i + 1 // bal = 2 * i + 1 int jobb = 2 * i + 2 // jobb = 2 * i + 2 ha (balra egy [legnagyobb]) legnagyobb = balra, ha (jobbra egy [legnagyobb]) legnagyobb = jobbra, ha (legnagyobb! = I) csere ( a [i], A [legnagyobb]) Heapify (a, n, legnagyobb) vég halmozódik fel
Ezeken kívül vannak más, nem annyira ismert rendezési algoritmusok, mint például Introsort, Counting Sort stb. Továbblépve a következő algoritmuskészletre ebben az „Adatszerkezetek és algoritmusok” cikkben, vizsgáljuk meg a kereső algoritmusokat.
 Algoritmusok keresése Java-ban 
A keresés a szokásos üzleti alkalmazások egyik leggyakoribb és leggyakrabban végrehajtott művelete. A keresési algoritmusok olyan algoritmusok, amelyek segítségével meghatározott tulajdonságokkal rendelkező elemet lehet megtalálni az elemek gyűjteménye között. Fedezzük fel a két leggyakrabban használt keresési algoritmust.
 Lineáris keresési algoritmus a Java-ban 
A lineáris keresés vagy a szekvenciális keresés a legegyszerűbb keresési algoritmus. Ez magában foglalja az elem adatainak egymás utáni keresését az adott adatstruktúrában mindaddig, amíg az elemet meg nem találják, vagy el nem érik a szerkezet végét. Ha az elem megtalálható, akkor az elem helyét visszaadja, különben az algoritmus NULL értéket ad vissza.
Itt van a Java-lineáris keresést ábrázoló álkód:
eljárás linear_search (a [], érték) az i = 0-tól n-1-ig, ha egy [i] = érték, akkor a 'Talált' visszatérés i véget nyomtatja, ha a 'Nem található' véget a lineáris_keresés végére nyomtatja
Ez egynyers erő algoritmus.Bár minden bizonnyal a legegyszerűbb, a hatékonyságának köszönhetően egészen biztosan nem a leggyakoribb. A lineáris keresés időbeli összetettsége TOVÁBB) .
 Bináris keresési algoritmus a Java-ban 
A bináris keresés, más néven logaritmikus keresés, olyan keresési algoritmus, amely megtalálja a célérték pozícióját egy már rendezett tömbben. A bemeneti gyűjteményt egyenlő felekre osztja, és az elemet összehasonlítja a lista középső elemével. Ha az elem megtalálható, a keresés ott ér véget. Egyébként folytatjuk az elem keresését a tömb megfelelő partíciójának felosztásával és kiválasztásával, annak alapján, hogy a cél elem kisebb vagy nagyobb, mint a középső elem.
Itt van a Java bináris keresést ábrázoló álkód:
Binary_search egy rendezett tömb n keresése az x tömb mérete keresendő alsóBound = 1 upperBound = n, míg x nem található, ha upperBound
A keresés akkor fejeződik be, amikor a upperBound (a mutatónk) elmegy az alsóBound (utolsó elem) mellett, ami azt jelenti, hogy a teljes tömböt kerestük, és az elem nincs jelen.Ez a leggyakrabban használt keresési algoritmus, elsősorban gyors keresési idejének köszönhetően. A bináris keresés időbeli összetettsége TOVÁBB) ami markáns javulás a TOVÁBB) a lineáris keresés időbeli összetettsége.
Ezzel eljutottunk az „Adatszerkezetek és algoritmusok a Java-ban” cikk végéhez. Kitértem a Java egyik legalapvetőbb és legfontosabb témájára.Remélem, tisztában van mindazzal, amit megosztott veled ebben a cikkben.
  Győződjön meg arról, hogy a lehető legtöbbet gyakorolja, és állítsa vissza a tapasztalatait.   
 Nézze meg a    az Edureka, egy megbízható online tanulási vállalat, amelynek több mint 250 000 elégedett tanulóval rendelkező hálózata elterjedt az egész világon. Azért vagyunk itt, hogy segítséget nyújthassunk utazásának minden lépésében, hogy e java interjúk kérdései mellett a tanévre váltsunk, előállítunk egy tananyagot, amelyet azoknak a hallgatóknak és szakembereknek tervezünk, akik Java fejlesztők szeretnének lenni. 
 Van egy kérdésünk? Kérjük, említse meg a „Java adatstruktúrák és algoritmusok” megjegyzés szakaszában  cikket, és a lehető leghamarabb kapcsolatba lépünk Önnel.