Parimad Java struktuuri andmekonstruktsioonid ja algoritmid, mida peate teadma

Kui peaksin valima tarkvaraarenduses kõige olulisema teema, oleksid need andmestruktuurid ja algoritmid. Võite mõelda sellest kui põhilisest tööriistast, mis on saadaval kõigile arvutiprogrammeerijatele. Programmeerimise ajal kasutame andmestruktuurid andmete salvestamiseks ja korrastamiseks ning algoritmid nende struktuuride andmetega manipuleerida. See artikkel sisaldab üksikasjalikku ülevaadet kõigist tavalistest andmestruktuuridest ja algoritmidest et lugejad saaksid end hästi varustada.

Allpool on loetletud selles artiklis käsitletud teemad:

• Andmestruktuurid Java-s
  • Lineaarsed andmestruktuurid
  • Hierarhilised andmestruktuurid
• Algoritmid Java-s
  • Algoritmide sorteerimine
  • Algoritmide otsimine

Andmestruktuurid Java-s

Andmestruktuur on viis andmete salvestamiseks ja korrastamiseks arvutis, et neid saaks tõhusalt kasutada. See pakub vahendit suurte andmemahtude tõhusaks haldamiseks. Ja tõhusad andmestruktuurid on tõhusate algoritmide kujundamisel võtmetähtsusega.

SisseSelles artiklis „Andmekonstruktsioonid ja algoritmid Java-s” käsitleme selliseid põhilisi andmestruktuure nagu:

• Lineaarsed andmestruktuurid
  • Lingitud loend
  • Virnad
  • Järjekorrad

• Hierarhilised andmestruktuurid
  • Binaarpuud
  • Hunnikud
  • Hash tabelid

Vaatame neid kõiki.

Lineaarsed andmekonstruktsioonid Java-s

Lineaarsed andmestruktuurid on need, mille elemendid on järjestikused ja järjestatud nii, et: on ainult üks esimene element ja tal on ainult üks järgmine element , on ainult üks viimane element ja tal on ainult üks eelmine element , samas kui kõigil teistel elementidel on a järgmine ja a eelmine element.

Massiivid

An massiiv on lineaarne andmestruktuurmis esindab sarnaste elementide rühma, millele pääseb ligi indeksite kaupa. Enne andmete salvestamist tuleb esitada massiivi suurus. Allpool on loetletud massiivi omadused:

pl sql õpetus algajatele koos näidetega

• Iga massiivi element on sama tüüpi andmetega ja sama suur
• Massiivi elemendid salvestatakse külgnevatesse mälupaikadesse, kusjuures esimene element algab kõige väiksemast mälukohast
• Massiivi elementidele pääseb juhuslikult juurde
• Massiiviandmete struktuur ei ole täielikult dünaamiline

Näiteks , võime soovida, et videomäng jälgiks selle mängu kümmet parimat tulemust. Selle asemel, et kasutada kümmet erinevat muutujad selle ülesande jaoks võiksime kasutada kogu grupi jaoks ühte nime ja kasutada indeksi numbreid, et viidata selle grupi rekorditele.

Lingitud loend

TO on lineaarne andmestruktuur mitme sõlme kogumisega, kus each-element salvestab enda andmed ja kursori järgmise elemendi asukohale. Lingitud loendi viimane link osutab nullile, näidates ahela lõppu. Lingitud loendi elementi nimetatakse a sõlm . Esimest sõlme nimetatakse pea .Viimast sõlme kutsutakse saba .

Lingitud loendi tüübid

Üksikult lingitud loend (ühesuunaline)

Kahekordse lingiga loend (kahesuunaline)

Ringkirjaga seotud loend

Siin on lihtne näide: Kujutage ette lingitud loendit nagu kirjaklambrite kett, mis on omavahel ühendatud. Saate hõlpsalt lisada teise kirjaklambri üla- või alaosa. Selle keskele sisestamine on isegi kiire. Kõik, mida peate tegema, on lihtsalt keskel kett lahti ühendada, lisada uus kirjaklamber ja seejärel teine ​​pool uuesti ühendada. Lingitud loend on sarnane.

Virnad

Virna, abstraktne andmestruktuur on objektid mis on sisestatud ja eemaldatud vastavalt last-in-first-out (LIFO) põhimõttel. Objektid saab virnasse lisada igal ajahetkel, kuid ainult viimati sisestatud (st “viimase”) objekti saab igal ajal eemaldada.Allpool on loetletud virna omadused:

• See on orderd loend, millessisestamist ja kustutamist saab teha ainult ühes otsas, mida nimetatakse üles
• Rekursiivne andmestruktuur koos kursoriga selle ülemisele elemendile
• Järgib last-in-first-out (LIFO) põhimõttel
• Toetab kahte kõige põhilisemat meetodit
  • push (e): sisestage element e virna ülaossa
  • pop (): Eemaldage ja tagastage virna pealmine element

Virna praktilised näited hõlmavad sõna tagasikäiku,faili õigsuse kontrollimiseks sulgudesjärjestusbrauserites tagasi funktsionaalsuse juurutamine ja palju muud.

Järjekorrad

on ka teist tüüpi abstraktsed andmestruktuurid. Erinevalt virnast on järjekord objektide kogum, mis lisatakse ja eemaldatakse vastavalt esimene-esimesena-välja (FIFO) põhimõttel. See tähendab, et elemente saab sisestada igal ajahetkel, kuid igal ajal saab eemaldada ainult selle elemendi, mis on kõige kauem järjekorras olnud.Allpool on loetletud järjekorra omadused:

• Sageli nimetatakse seda esimene-esimene-välja nimekiri
• Toetab kahte kõige põhilisemat meetodit
  • enqueue (e): sisestage element e tagumine järjekorrast
  • dequeue (): eemaldage element elemendist ja tagastage see ees järjekorrast

Järjekordi kasutatakseasünkroonne andmete edastamine kahe protsessi vahel, protsessori ajastamine, ketta ajastamine ja muud olukorrad, kus ressursse jagatakse mitme kasutaja vahel ja neid serveeritakse esmalt serveris. Selle artikli „Andmekonstruktsioonid ja algoritmid Java-s” järgmisena on meil hierarhilised andmestruktuurid.

Hierarhilised andmestruktuurid Java-s

Binaarne puu

Binaarne puu on ahierarhilised puuandmete struktuurid, milles igas sõlmes on maksimaalselt kaks last , millele viidatakse kui vasak laps ja õige laps . Igal binaarpuul on järgmised sõlmede rühmad:

• Juuresõlm: see on kõige ülemine sõlm, mida sageli nimetatakse põhisõlmekssest kõigi teiste sõlmedeni pääseb juurest
• Vasak alampuu, mis on ka binaarne puu
• Parem alampuu, mis on ka binaarne puu

Allpool on loetletud kahendpuu omadused:

• Binaarse puu saab läbida kahel viisil:
  • Esimene sügavus : Järjekorras (vasak-parem-parem), eeltellimus (vasak-parem-parem) ja postitellimus (vasak-parem-juur)
  • Laiuse esimene läbimine : Taseme järjekorra läbimine
• Puu läbimise ajaline keerukus: O (n)
• Maksimaalne sõlmede arv tasemel ’l’ = 2^l-1.

Binaarpuude rakendused hõlmavad järgmist:

• Kasutatakse paljudes otsingurakendustes, kuhu andmed pidevalt sisenevad / väljuvad
• Digitaalsete piltide komponeerimise visuaalsete efektide töövooks
• Kasutatakse peaaegu igas suure ribalaiusega ruuteris ruuterilaudade salvestamiseks
• Kasutatakse ka traadita võrgus ja mälu jaotamisel
• Kasutatakse tihendusalgoritmides ja palju muud

Binaarne hunnik

Binaarhunnik on täielikbinaarne puu, mis vastab kuhja omadusele. Lihtsamalt öeldeson binaarse puu variatsioon, millel on järgmised omadused:

• Hunnik on täielik binaarne puu: Puu kohta öeldakse, et see on täielik, kui kõik selle astmed, välja arvatud võimalik, et kõige sügavamad, on täielikud. Ttema binaarhunniku omadus muudab selle sobivaks salvestamiseks .
• Järgib kuhja vara: Binaarhunnik on kas a Min-Heap või a Max-Heap .
  • Min binaarne hunnik: Fvõi iga kuhja sõlme, on sõlme väärtus väiksem või võrdne laste väärtused
  • Max kahendkuhi: Fvõi iga kuhja sõlme, on sõlme väärtus suurem või võrdne laste väärtused

Binaarse hunniku populaarsed rakendused hõlmavad järgmisttõhusate prioriteedijärjekordade rakendamine, massiivi k väikseima (või suurima) elemendi efektiivne leidmine ja palju muud.

Hash tabelid

Kujutage ette, et teil on objekt ja soovite sellele määrata võtme, et otsimine oleks väga lihtne. Selle võtme / väärtuse paari salvestamiseks võite kasutada lihtsat massiivi nagu andmestruktuur, kus võtmeid (täisarvu) saab kasutada otse indeksina andmete väärtuste salvestamiseks. Juhtudel, kui võtmed on liiga suured ja neid ei saa otseselt indeksina kasutada, kasutatakse räsimiseks kutsutavat tehnikat.

Räsimisel muudetakse suured klahvid väikeste klahvide abil räsifunktsioonid . Seejärel salvestatakse väärtused andmestruktuuri nimegakuni räsitabel. Räsitabel on andmestruktuur, mis rakendab sõnastikku ADT, struktuuri, mis suudab unikaalsed võtmed väärtusteni kaardistada.

Üldiselt on räsitabelil kaks peamist komponenti:

1. Ämber massiiv: Räsitabeli ämbermassiiv on N-suurusega massiiv A, kus A iga lahtrit peetakse “ämbriks”, see tähendab võtme-väärtuse paaride kogumiks. Täisarv N määrab massiivi mahu.
2. Räsi funktsioon: See on mis tahes funktsioon, mis kaardistab meie kaardi iga võtme k täisarvuni vahemikus [0, N ja miinus 1], kus N on selle tabeli ämbermassiivi maht.

Kui paneme objektid räsitabelisse, on võimalik, et erinevatel objektidel võib olla sama räsikood. Seda nimetatakse a kokkupõrge . Kokkupõrkega toimetulemiseks on olemas sellised võtted nagu aheldamine ja avatud pöördumine.

Need on mõned Java põhilised ja kõige sagedamini kasutatavad andmestruktuurid. Nüüd, kui olete neist kõigist teadlik, võite hakata neid oma rakenduses rakendama . Sellega oleme lõpetanud selle artikli ‘Jaava andmestruktuurid ja algoritmid’ esimese osa. Järgmises osas läheme õppimapõhialgoritmid ja kuidas neid kasutada praktilistes rakendustes nagu sortimine ja otsimine, jagamine ja vallutamine, ahned algoritmid, dünaamiline programmeerimine.

Algoritmid Java-s

Ajalooliselt keerukate matemaatiliste arvutuste lahendamise vahendina on algoritmid tihedalt seotud arvutiteaduse ja eriti andmestruktuuridega. Algoritm on käskude jada, mis kirjeldab konkreetse probleemi lahendamist piiratud aja jooksul. Neid on esindatud kahel viisil:

• Voodiagrammid - See onalgoritmi juhtimisvoo visuaalne esitus
• Pseudokood - Seeon algoritmi tekstiline esitus, mis ühtlustab lõpliku lähtekoodi

Märge: Algoritmi jõudlust mõõdetakse aja keerukuse ja ruumi keerukuse põhjal. Enamasti sõltub mis tahes algoritmi keerukus probleemist ja algoritmist endast.

Uurime Java Java kahte peamist algoritmide kategooriat, milleks on:

• Algoritmide sorteerimine Java-s
• Algoritmide otsimine Javas

Algoritmide sorteerimine Java-s

Sorteerimisalgoritmid on algoritmid, mis panevad loendi elemendid kindlas järjekorras. Enamkasutatavad järjestused on arvuline ja leksikograafiline järjekord. Selles artiklis „Andmekonstruktsioonid ja algoritmid” saate uurida mõnda sorteerimisalgoritmi.

Mullide sortimine Java-s

Mullide sorteerimine, mida sageli nimetatakse vajuvaks sortimiseks, on lihtsaim sorteerimisalgoritm. See sirvib loendit korduvalt, võrdleb iga külgneva elemendi paari ja vahetab need omavahel, kui need on vales järjekorras.Mullisort saab oma nime, kuna see filtreerib elemendid massiivi tippu, nagu mullil, mis hõljuvad vees.

Siin onmullisorteerimise algoritmi tähistav pseudokood (kasvav sortimiskontekst).

a [] on massiivi suurus N algab BubbleSort (a []) deklareerib täisarvu i, j i = 0 kuni N - 1 j = 0 kuni N - i - 1 korral, kui a [j]> a [j + 1 ], siis vaheta lõppu [j], lõppu [j + 1], et tagastada lõpp BubbleSort

See kood tellib N-andmeühiku ühemõõtmelise massiivi kasvavas järjekorras. Väline silmus muudab N-1 massiivi läbimiseks. Iga läbipääs kasutab andmeüksuste vahetamiseks sisemist silmust, nii et järgmine väikseim andmeüksus 'mullib' massiivi alguse suunas. Kuid probleem on selles, et algoritm vajab ühte tervet läbimist ilma vahetuseta, et teada, et loend on sorteeritud.

Halvima ja keskmise juhtumi keerukus: O (n * n). Halvimal juhul juhtub massiiv vastupidises sorteerimises.

Parima juhtumi aja keerukus: Peal). Parim juhtum on siis, kui massiiv on juba sorteeritud.

Valik Sorteeri Java-s

Valikute sortimine on nii otsimise kui ka sortimise kombinatsioon. Algoritm sorteerib massiivi, leides sorteerimata osast korduvalt minimaalse elemendi (arvestades kasvavat järjestust) ja asetades selle massiivi õigesse kohta.

Siin on valiku sortimise algoritmi esindav pseudokood (kasvav sortimiskontekst).

a [] on massiivi suurus algus SelectionSort (a []) i = 0 kuni n - 1 / * määrake praegune element minimaalseks * / min = i / * leidke minimaalne element * / jaoks j = i + 1 n-ni, kui loend [j]
Nagu koodist aru saate, on sortimise massiivi läbimise arv üks vähem kui massiivi üksuste arv. Sisemine silmus leiab järgmise väikseima väärtuse ja välimine silmus asetab selle väärtuse õigesse asukohta. Valiku sortimine ei tee kunagi rohkem kui O (n) vahetusi ja see võib olla kasulik, kui mälu kirjutamine on kulukas operatsioon.
 Aja keerukus: Peal2), kuna pesastatud silmuseid on kaks.
 Abiruum: Või (1).
 Lisamine Sorteeri Java-s 
Insertion Sort on lihtne sorteerimisalgoritm, mis kordab loendi läbi ühe sisendelemendi korraga tarbides ja ehitab lõpliku sorteeritud massiivi. See on väiksemate andmekogumite puhul väga lihtne ja tõhusam. See on stabiilne ja kohapeal sorteerimistehnika.
Siin on pseudokood, mis tähistab sisestamise sorteerimise algoritmi (kasvav sortimiskontekst).
a [] on massiivi suurus N, algab InsertionSort (a []) i = 1 kuni N-klahvi jaoks = a [i] j = i - 1, samas kui (j> = 0 ja a [j]> võti0 a [j + 1] = x [j] j = j - 1 ots, samal ajal kui [j + 1] = võtme lõpp InsertSort
Nagu koodist aru saate, sisestamise sortimise algoritmeemaldab sisendandmetest ühe elemendi, leiab sorditud loendist asukoha, kuhu see kuulub, ja sisestab selle sinna. See kordub seni, kuni ükski sisendelement jääb sortimata.
 Parim juhtum: Parim juhtum on see, kui sisendiks on juba sorteeritud massiiv. Sel juhul on sisestamise sortimisel lineaarne jooksuaeg (st & teeta (n)).
 Halvimal juhul:  Lihtsaim halvima juhtumi sisend on vastupidises järjekorras sorteeritud massiiv.
 QuickSort Java-s 
Quicksorti algoritm on kiire, rekursiivne, mittestabiilne sortimisalgoritm, mis töötab jagamise ja vallutamise põhimõttel. See valib pivoti elemendi ja jaotab antud massiivi valitud pivoti ümber.
 Kiire sortimise juurutamise sammud:  
 
Valige sobiv pöördepunkt.
Jagage loendid kahte loendissepõhineb sellel pöördelemendil. Kõik liigendelemendist väiksemad elemendid paigutatakse vasakpoolsesse loendisse ja kõik suuremad elemendid paremasse loendisse. Kui element on võrdne pöördelemendiga, võib see minna mis tahes loendisse. Seda nimetatakse sektsiooni toiminguks.
Sortige kõik väiksemad loendid rekursiivselt. 
Siin on Quicksorti algoritmi tähistav pseudokood.
QuickSort (A massiivina, madal kui int, kõrge kui int) {if (madal
Ülaltoodud pseudokoodis partitsioon () funktsioon teostab partitsiooni operatsiooni ja Quicksort () funktsioon kutsub korduvalt iga genereeritud loendi jaoks partitsioonifunktsiooni. Kiirsordi keerukus on keskmisel juhul & Theta (n log (n)) ja halvimal juhul & Theta (n2).
 Ühenda sortimine Java-s 
Mergesort on kiire, rekursiivne, stabiilne sortimisalgoritm, mis töötab ka jagamise ja vallutamise põhimõttel. Sarnaselt kiirsortiga jagab sortide sortimine elementide loendi kaheks loendiks. Need loendid sorteeritakse iseseisvalt ja seejärel ühendatakse. Loendite kombineerimise käigus lisatakse (või liidetakse) elemendid loendi õigesse kohta.
Siin on pseudokood, mis tähistab ühendamise algoritmi.
protseduur MergeSort (a massiivina), kui (n == 1) tagastab massiivi var l1 = a [0] ... a [n / 2] var l2 massiivina = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) protseduuri lõpetamine protseduuri liitmine (a massiivina, b massiivina) var c massiivina, samas kui (a ja b-l on elemente), kui ( a [0]> b [0]) lisage b [0] c-i lõppu eemaldage b [0] b-st. lisage a [0] c lõppu eemaldage a [0] otsast, kui lõpp on (a-l on elemente) lisage c lõppu [0], eemaldage otsast [0], samal ajal kui (b-l on elemente), lisage b [0] c-i lõppu, eemaldage b [0] b-otsast, naastes c protseduuri lõpetamine
 mergesort () funktsioon jagab loendi kaheks kõneks mergesort () nendes loendites eraldi ja seejärel ühendab need, saates need parameetriteks funktsiooni ühendamiseks ().Algoritmil on keerukus O (n log (n)) ja sellel on lai valik rakendusi.
 Hunniku sortimine Java-s 
Heapsort on võrdluspõhine sortimisalgoritmBinaarhunniku andmestruktuur. Võite seda mõelda kui täiustatud versiooni f valiku sortimist, kussee jagab sisendi sorteeritud ja sorteerimata piirkonnaks ning vähendab sorteerimata piirkonda iteratiivselt, eraldades suurima elemendi ja viies selle sorteeritud piirkonda.
 Quicksorti juurutamise sammud (kasvavas järjekorras): 
Ehitage sorteerimismassiividega maksimaalne hunnik
Selle poini juurest, suurim element salvestatakse kuhja juure. Asendage see kuhi viimase elemendiga ja vähendage kuhja suurust 1 võrra. Lõpuks kuhjata puu juur
Korrake ülaltoodud samme, kuni kuhja suurus on suurem kui 1
Siin on hunniku sortimise algoritmi tähistav pseudokood.
Heapsort (massiivina) (i = n / 2 - 1) kuni i> = 0 heapify (a, n, i) i = n-1 kuni 0 vahel vahetada (a [0], a [i]) heapify (a, i, 0) lõpu ots heapify jaoks (a massiivina, n kui int, i kui int) suurim = i // Initialize suurim juurena int l eft = 2 * i + 1 // vasak = 2 * i + 1 int parem = 2 * i + 2 // parem = 2 * i + 2 kui (vasakul [kõige suurem]) suurim = vasak, kui (paremal [kõige suurem]) suurim = parem, kui (suurim! = I) vahetada ( a [i], A [suurim]) Heapify (a, n, suurim) ots kuhjub
Peale nende on ka teisi sorteerimisalgoritme, mis pole nii tuntud, näiteks Introsort, Loendamissorteerimine jne. Selle artikli „Andmekonstruktsioonid ja algoritmid” järgmise algoritmide komplekti juurde liikumisel uurime algoritmide otsimist.
 Algoritmide otsimine Javas 
Otsimine on tavalistes ärirakendustes üks levinumaid ja sagedasemaid toiminguid. Otsingu algoritmid on algoritmid määratud omadustega üksuse leidmiseks üksuste kogu hulgast. Uurime kahte kõige sagedamini kasutatavat otsingualgoritmi.
 Java sirgjooneline otsingu algoritm 
Lineaarne otsing või järjestikune otsing on lihtsaim otsimisalgoritm. See hõlmab antud andmestruktuuris elemendi järjestikust otsimist kuni elemendi leidmiseni või struktuuri lõpuni jõudmiseni. Kui element leitakse, tagastatakse üksuse asukoht, vastasel juhul tagastab algoritm NULL.
Siin on Java sirgjoonelist otsingut tähistav pseudokood:
protseduur linear_search (a [], väärtus) i = 0 kuni n-1 jaoks, kui [i] = väärtus, siis printige 'Leitud', tagastan i lõpu, kui printida 'Ei leitud' lõppu otseliinile_otsing
See ontoore jõu algoritm.Ehkki see on kindlasti kõige lihtsam, pole see oma ebaefektiivsuse tõttu kindlasti kõige levinum. Lineaarotsingu ajaline keerukus on PEAL) .
 Binaarotsingu algoritm Java-s 
Binaarotsing, tuntud ka kui logaritmiline otsing, on otsingu algoritm, mis leiab sihtväärtuse positsiooni juba sorteeritud massiivist. See jagab sisendkogumi võrdseks pooleks ja üksust võrreldakse loendi keskmise elemendiga. Kui element leitakse, lõpeb otsing sellega. Muidu jätkame elemendi otsimist, jagades ja valides massiivi sobiva partitsiooni, lähtudes sellest, kas sihtelement on väiksem või suurem kui keskmine element.
Siin on Java binaarset otsingut tähistav pseudokood:
Protseduur binaarne_otsing sorteeritud massiivi n massiivi x otsitava väärtuse väärtus
Otsing lõpeb, kui upperBound (meie kursor) läheb mööda lowerBound (viimane element), mis tähendab, et oleme otsinud kogu massiivi ja elementi pole.See on kõige sagedamini kasutatavad otsingualgoritmid peamiselt tänu kiirele otsimisajale. Binaarotsingu ajaline keerukus on PEAL) mis on märgatav edasiminek PEAL) Lineaarotsingu ajaline keerukus.
Sellega jõuame selle artikli „Java andmestruktuurid ja algoritmid” lõppu. Olen käsitlenud Java ühte kõige põhilisemat ja olulisemat teemat.Loodan, et teil on selge kõigega, mida selles artiklis teiega jagatud on.
  Harjutage kindlasti nii palju kui võimalik ja pöörake oma kogemused tagasi.   
 Vaadake    autor Edureka, usaldusväärne veebiõppeettevõte, mille võrgustik koosneb enam kui 250 000 rahulolevast õppijast ja mis levib üle kogu maailma. Oleme siin, et aidata teil igal sammul teie teekonnal, et saada lisaks sellele Java-intervjuu küsimustele välja, pakume välja õppekava, mis on mõeldud õpilastele ja spetsialistidele, kes soovivad olla Java-arendajad. 
 Kas teil on meile küsimus? Palun mainige seda selle jaotise „Java struktuuride ja algoritmide” kommentaaride jaotises  artikkel ja me pöördume teie poole niipea kui võimalik.