Najboljše podatkovne strukture in algoritmi v Javi, ki jih morate vedeti

Če bi moral izbrati eno najpomembnejših tem pri razvoju programske opreme, bi to bile podatkovne strukture in algoritmi. Lahko ga smatrate za temeljno orodje, ki je na voljo vsakemu računalniškemu programerju. Med programiranjem uporabljamo podatkovne strukture za shranjevanje in razvrščanje podatkov in algoritmi za obdelavo podatkov v teh strukturah. Ta članek vsebuje podroben pregled vseh običajnih podatkovnih struktur in algoritmov v bralcem omogočiti, da se dobro opremijo.

Spodaj so navedene teme, obravnavane v tem članku:

• Podatkovne strukture v Javi
  • Linearne podatkovne strukture
  • Hierarhične podatkovne strukture
• Algoritmi v Javi
  • Algoritmi za razvrščanje
  • Iskanje algoritmov

Podatkovne strukture v Javi

Podatkovna struktura je način shranjevanja in organiziranja podatkov v računalniku, da jih je mogoče učinkovito uporabljati. Omogoča učinkovito upravljanje velikih količin podatkov. In učinkovite podatkovne strukture so ključne za načrtovanje učinkovitih algoritmov.

Vv tem članku 'Podatkovne strukture in algoritmi v Javi' bomo zajeli osnovne podatkovne strukture, kot so:

• Linearne podatkovne strukture
  • Povezani seznam
  • Skladi
  • Čakalne vrste

• Hierarhične podatkovne strukture
  • Binarna drevesa
  • Kupe
  • Hash tabele

Oglejmo si vsakega od njih.

Linearne podatkovne strukture v Javi

Linearne podatkovne strukture v so tisti, katerih elementi so zaporedni in urejeni tako, da: obstaja samo en prvi element in ima samo enega naslednji element , je samo ena zadnji element in ima samo enega prejšnji element , medtem ko imajo vsi drugi elementi a Naslednji in a prejšnji element.

Polja

An matriko je linearna podatkovna strukturapredstavlja skupino podobnih elementov, do katerih dostopa indeks. Pred shranjevanjem podatkov je treba navesti velikost matrike. Spodaj so navedene lastnosti matrike:

• Vsak element v matriki je istega podatkovnega tipa in ima enako velikost
• Elementi matrike so shranjeni na sosednjih pomnilniških mestih, pri čemer se prvi element začne na najmanjši pomnilniški lokaciji
• Do elementov polja je mogoče naključno dostopati
• Struktura podatkov matrike ni popolnoma dinamična

Na primer , morda želimo, da video igra spremlja najboljših deset rezultatov za to igro. Namesto da bi uporabili deset različnih spremenljivke za to nalogo bi lahko uporabili eno ime za celotno skupino in uporabili indeksne številke za sklicevanje na najvišje ocene v tej skupini.

Povezani seznam

TO je linearna podatkovna struktura z zbiranjem več vozlišč, kjer je nprelement ach shrani lastne podatke in kazalec na lokacijo naslednjega elementa. Zadnja povezava na povezanem seznamu kaže na nič, kar pomeni konec verige. Element na povezanem seznamu se imenuje a vozlišče . Prvo vozlišče se imenuje glavo .Pokliče se zadnje vozlišče rep .

Vrste povezanega seznama

Enolično povezan seznam (enosmerni)

Dvojno povezan seznam (dvosmerni)

Krožno povezan seznam

Tu je preprost primer: Predstavljajte si povezan seznam, kot je veriga sponk, ki so povezane med seboj. Zgoraj ali spodaj lahko preprosto dodate še eno sponko. Hitro je celo vstaviti eno na sredino. Vse, kar morate storiti, je, da samo odklopite verigo na sredini, dodate novo sponko in nato ponovno povežete drugo polovico. Povezani seznam je podoben.

Skladi

Stack, abstraktna podatkovna struktura, je zbirka predmetov ki se vstavijo in odstranijo v skladu z zadnji v prvem izhodu (LIFO) načelo. Predmete lahko kadar koli vstavite v sklad, lahko pa jih kadar koli odstranite le nazadnje vstavljeni (torej 'zadnji') predmet.Spodaj so navedene lastnosti sklada:

• Gre za urejeni seznam, v kateremvstavljanje in brisanje se lahko izvede samo na enem koncu, ki se imenuje vrh
• Struktura rekurzivnih podatkov s kazalcem na zgornji element
• Sledi zadnji v prvem izhodu (LIFO) načelo
• Podpira dve najbolj temeljni metodi
  • push (e): Vstavite element e na vrh sklada
  • pop (): Odstranite in vrnite zgornji element na kupu

Praktični primeri sklada vključujejo obračanje besede,preveriti pravilnost oklepajizaporedje,izvajanje povratnih funkcij v brskalnikih in še veliko več.

Čakalne vrste

so tudi druga vrsta abstraktne podatkovne strukture. Za razliko od sklada je čakalna vrsta zbirka predmetov, ki se vstavijo in odstranijo v skladu z prvi v prvem ven (FIFO) načelo. To pomeni, da je mogoče elemente vstaviti kadar koli, vendar je mogoče kadar koli odstraniti le tisti element, ki je bil v čakalni vrsti najdlje.Spodaj so navedene lastnosti čakalne vrste:

• Pogosto se imenuje prvi v prvem seznam
• Podpira dve najbolj temeljni metodi
  • enqueue (e): Vstavite element e, v zadaj čakalne vrste
  • dequeue (): Odstrani in vrni element iz spredaj čakalne vrste

Čakalne vrste so uporabljene vasinhroni prenos podatkov med dvema procesoma, razporejanje procesorja, razporejanje diskov in druge situacije, ko se viri delijo med več uporabnikov in se strežejo po sistemu »kdor prvi pride prvi«. Naslednje v tem članku 'Podatkovne strukture in algoritmi v Javi' imamo hierarhične podatkovne strukture.

Hierarhične podatkovne strukture v Javi

Binarno drevo

Binarno drevo jehierarhične drevesne podatkovne strukture, v katerih vsako vozlišče ima največ dva otroka , ki se imenujejo levi otrok in pravi otrok . Vsako binarno drevo ima naslednje skupine vozlišč:

• Koreninsko vozlišče: je najvišje vozlišče in se pogosto imenuje glavno vozliščeker je vsa druga vozlišča mogoče doseči iz korena
• Levo poddrevo, ki je tudi binarno drevo
• Desno poddrevo, ki je tudi binarno drevo

Spodaj so navedene lastnosti binarnega drevesa:

kako globoko kopirati v javi -

• Binarno drevo je mogoče prehoditi na dva načina:
  • Globina prvo prečkanje : Po vrstnem redu (levo-koren-desno), prednaročilo (koren-levo-desno) in po naročilu (levo-desno-koren)
  • Širina prva prečka : Prehod vrstnega reda
• Zapletenost prečkanja dreves: O (n)
• Največje število vozlišč na ravni „l“ = 2^l-1.

Aplikacije binarnih dreves vključujejo:

• Uporablja se v številnih iskalnih aplikacijah, kjer podatki nenehno vstopajo / odhajajo
• Kot potek dela za sestavljanje digitalnih slik za vizualne učinke
• Uporablja se v skoraj vseh usmerjevalnikih z visoko pasovno širino za shranjevanje tabel usmerjevalnikov
• Uporablja se tudi pri brezžičnem mreženju in dodeljevanju pomnilnika
• Uporablja se v algoritmih stiskanja in mnogih drugih

Binarni kup

Binarni kup je popolnbinarno drevo, ki odgovarja na lastnost kopice. Preprosto povedanoje različica binarnega drevesa z naslednjimi lastnostmi:

• Heap je popolno binarno drevo: Drevo naj bi bilo popolno, če so vse njegove ravni, razen morda najgloblje, popolne. Tnjegova lastnost Binary Heap omogoča, da je primerna za shranjevanje v .
• Sledi lastnosti kopice: Binarni kup je bodisi a Min-kup ali a Max-Heap .
  • Min binarni kup: Fali vsako vozlišče na kopici, vrednost vozlišča je manjši ali enak vrednote otrok
  • Največja binarna kopica: Fali vsako vozlišče na kopici, je vrednost vozlišča večja ali enaka vrednote otrok

Med priljubljene aplikacije binarne kopice spadajoizvajanje učinkovitih prioritetnih čakalnih vrst, učinkovito iskanje k najmanjših (ali največjih) elementov v polju in še veliko več.

Hash tabele

Predstavljajte si, da imate predmet in mu želite dodeliti ključ, da bo iskanje zelo enostavno. Če želite shraniti ta par ključ / vrednost, lahko uporabite preprosto matriko, kot je podatkovna struktura, kjer lahko ključe (cela števila) uporabite neposredno kot indeks za shranjevanje podatkovnih vrednosti. Kadar pa so tipke prevelike in jih ni mogoče uporabiti neposredno kot indeks, se uporablja tehnika, imenovana zgoščevanje.

Pri razpršitvi se velike tipke z uporabo pretvorijo v majhne hash funkcije . Nato se vrednosti shranijo v imenovano podatkovno strukturodo hash tabela. Hash tabela je podatkovna struktura, ki izvaja slovar ADT, strukturo, ki lahko preslika edinstvene ključe v vrednosti.

Na splošno ima hash tabela dve glavni komponenti:

1. Polje vedra: Polje vedra za razpršilno tabelo je polje A velikosti N, kjer je vsaka celica A mišljena kot »vedro«, to je zbirka parov ključ / vrednost. Celo število N definira zmogljivost polja.
2. Funkcija razpršitve: Katera koli funkcija preslika vsak ključ k na našem zemljevidu na celo število v obsegu [0, N in minus 1], kjer je N zmogljivost vedra polja za to tabelo.

Ko predmete damo v razpršilno tablico, je možno, da imajo različni predmeti isto hashcode. To se imenuje trčenje . Za spopadanje s trkom obstajajo tehnike, kot sta veriženje in odprto naslavljanje.

To je nekaj osnovnih in najpogosteje uporabljenih podatkovnih struktur v Javi. Zdaj, ko ste seznanjeni z vsakim od njih, jih lahko začnete izvajati v svojem . S tem smo zaključili prvi del tega članka „Strukture podatkov in algoritmi v Javi“. V naslednjem delu bomo izvedeli več o temosnovni algoritmi in kako jih uporabiti v praktičnih aplikacijah, kot so razvrščanje in iskanje, razdeli in osvoji, pohlepni algoritmi, dinamično programiranje.

Algoritmi v Javi

V preteklosti so se uporabljali kot orodje za reševanje zapletenih matematičnih izračunov, algoritmi pa so globoko povezani z računalništvom in zlasti s podatkovnimi strukturami. Algoritem je zaporedje navodil, ki opisuje način reševanja določenega problema v končnem časovnem obdobju. Zastopani so na dva načina:

• Diagrami poteka - Jevizualni prikaz krmilnega toka algoritma
• Psevkodo - Jaje besedilna predstavitev algoritma, ki približuje končno izvorno kodo

Opomba: Učinkovitost algoritma se meri na podlagi časovne zapletenosti in zapletenosti prostora. Zapletenost katerega koli algoritma je večinoma odvisna od problema in samega algoritma.

Oglejmo si dve glavni kategoriji algoritmov v Javi, ki sta:

• Razvrščanje algoritmov v Javi
• Iskanje algoritmov v Javi

Razvrščanje algoritmov v Javi

Algoritmi za razvrščanje so algoritmi, ki dajo elemente seznama v določen vrstni red. Najpogosteje uporabljena naročila so številčni in leksikografski vrstni red. V tem članku „Podatkovne strukture in algoritmi“ si oglejte nekaj algoritmov za razvrščanje.

Razvrsti mehurčke v Javi

Razvrstitev mehurčkov, ki jo pogosto imenujemo tudi potapljanje, je najpreprostejši algoritem razvrščanja. Večkrat prečka seznam, ki ga je treba razvrstiti, primerja vsak par sosednjih elementov in jih zamenja, če so v napačnem vrstnem redu.Razvrstitev mehurčkov dobi svoje ime, ker filtrira elemente na vrhu polja, kot so mehurčki, ki plavajo po vodi.

Tukaj jepsevdokoda, ki predstavlja algoritem razvrščanja mehurčkov (naraščajoči kontekst razvrščanja).

a [] je niz velikosti N začne BubbleSort (a []) razglasi celo število i, j za i = 0 do N - 1 za j = 0 do N - i - 1, če je [j]> a [j + 1 ] nato zamenjajte [j], [j + 1] konec, če je konec, za vrnitev konca BubbleSort

Ta koda naroči enodimenzionalno matriko N podatkovnih elementov v naraščajočem vrstnem redu. Zunanja zanka omogoča prehod N-1 preko polja. Vsak prehod uporablja notranjo zanko za izmenjavo podatkovnih postavk, tako da se naslednji najmanjši podatkovni element 'zavihti' proti začetku polja. Toda težava je v tem, da algoritem potrebuje en celoten prehod brez zamenjave, da ve, da je seznam razvrščen.

Najslabša in povprečna časovna zapletenost: O (n * n). Najslabši primer se zgodi, ko je polje obratno razvrščeno.

Najboljša časovna zapletenost: O (n). Najboljši primer je, če je polje že razvrščeno.

Razvrščanje izbora v Javi

Izbirno razvrščanje je kombinacija iskanja in razvrščanja. Algoritem razvrsti matriko tako, da večkrat poišče najmanjši element (upoštevajoč naraščajoči vrstni red) iz nesortiranega dela in ga postavi na pravilen položaj v matriki.

Tu je psevdokoda, ki predstavlja algoritem razvrščanja po izboru (naraščajoči kontekst razvrščanja).

a [] je niz velikosti N začni SelectionSort (a []) za i = 0 do n - 1 / * nastavi trenutni element kot najmanjši * / min = i / * poišči najmanjši element * / za j = i + 1 do n, če je seznam [j]
Kot lahko razberete iz kode, je število prehodov vrstice skozi matriko za eno manj kot število elementov v matriki. Notranja zanka poišče naslednjo najmanjšo vrednost, zunanja zanka pa jo postavi na njeno pravilno mesto. Izbirno razvrščanje nikoli ne opravi več kot zamenjav O (n) in je lahko koristno, če je zapisovanje v pomnilnik drago.
 Zapletenost časa: O (št2.), saj obstajata dve ugnezdeni zanki.
 Pomožni prostor: Ali (1).
 Razvrstitev vstavka v Javi 
Razvrstitev vstavljanja je preprost algoritem za razvrščanje, ki pregleduje seznam tako, da porabi en vhodni element hkrati in gradi končno razvrščeno polje. Je zelo preprost in učinkovitejši pri manjših naborih podatkov. Je stabilna tehnika sortiranja na mestu.
Tu je psevdokoda, ki predstavlja algoritem za razvrščanje po vstavitvi (naraščajoči kontekst razvrščanja).
a [] je niz velikosti N begin InsertionSort (a []) za i = 1 do N ključ = a [i] j = i - 1, medtem ko (j> = 0 in a [j]> key0 a [j + 1] = x [j] j = j - 1 konec, medtem ko je [j + 1] = ključni konec za konec InsertionSort
Kot lahko razberete iz kode, algoritem za razvrščanje vstavljanjaodstrani en element iz vhodnih podatkov, poišče mesto, ki mu pripada, na razvrščenem seznamu in ga vanj vstavi. Ponavlja se, dokler noben vhodni element ne ostane nesortiran.
 Najboljši primer: Najboljši primer je, če je vnos matrika, ki je že razvrščena. V tem primeru ima vrsta vstavljanja linearni čas delovanja (tj. & Theta (n)).
 V najslabšem primeru:  Najpreprostejši vnos v najslabšem primeru je polje, razvrščeno v obratnem vrstnem redu.
 QuickSort v Javi 
Quicksort algoritem je hiter, rekurziven, nestabilen algoritem razvrščanja, ki deluje po principu deli in vladaj. Izbere element kot vrtišče in razdeli dano matriko okoli tega izbranega vrtišča.
 Koraki za izvedbo hitrega razvrščanja:  
 
Izberite primerno 'vrtilno točko'.
Sezname razdelite na dva seznamatemelji na tem vrtilnem elementu. Vsak element, ki je manjši od vrtilnega elementa, se uvrsti na levi seznam, vsak večji element pa na desni seznam. Če je element enak vrtilnemu elementu, je lahko na katerem koli seznamu. To se imenuje operacija particije.
Rekurzivno razvrstite vsak manjši seznam. 
Tu je psevdokoda, ki predstavlja algoritem Quicksort.
QuickSort (A kot matrika, nizka kot int, visoka kot int) {if (nizka
V zgornji psevdokodi je particija () funkcija izvaja operacijo particije in Quicksort () funkcija večkrat pokliče particijsko funkcijo za vsak manjši ustvarjeni seznam. Zapletenost hitrega sortiranja je v povprečnem primeru & Theta (n log (n)), v najslabšem primeru pa & Theta (n2).
 Združi razvrstitev v Javi 
Mergesort je hiter, rekurziven, stabilen algoritem za razvrščanje, ki deluje tudi po principu deli in vladaj. Podobno kot hitro sortiranje tudi združevanje razvrsti seznam elementov na dva seznama. Ti seznami so razvrščeni neodvisno in nato združeni. Med kombinacijo seznamov se elementi vstavijo (ali združijo) na pravem mestu na seznamu.
Tu je psevdokoda, ki predstavlja algoritem za sortiranje spajanja.
postopek MergeSort (a kot matrika), če (n == 1) vrne var l1 kot matriko = a [0] ... a [n / 2] var l2 kot matriko = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) vrni spajanje (l1, l2) postopek zaključka postopka spajanje (a kot matrika, b kot matrika) var c kot matrika, medtem ko (a in b imata elemente), če ( a [0]> b [0]) dodajte b [0] na konec c odstranite b [0] iz b sicer dodajte a [0] na konec c odstranite [0] s konca, če konec, medtem ko (a ima elemente) dodajte a [0] na konec c, odstranite a [0] s konca, medtem ko (b ima elemente) dodajte b [0] na konec c, odstranite b [0] s konca b, medtem ko se vrnete c končni postopek
 mergesort () funkcija razdeli seznam na dva klica mergesort () na teh seznamih ločeno in jih nato kombinira tako, da jih pošlje kot parametre v funkcijo merge ().Algoritem ima zapletenost O (n log (n)) in ima širok spekter aplikacij.
 Razvrščanje kopice v Javi 
Heapsort je algoritem za razvrščanje na podlagi primerjaveStruktura podatkov binarne kopice. Lahko si omislite to kot izboljšano različico f sort sort, kjerazdeli svoj vnos na razvrščeno in nesortirano območje, nesortirano regijo pa iterativno skrči tako, da izvleče največji element in ga premakne v razvrščeno območje.
 Koraki za izvajanje Quicksort (v naraščajočem vrstnem redu): 
Z matriko za razvrščanje zgradite največ kup
Na tej točkit, največji element je shranjen v korenu kupa. Zamenjajte ga z zadnjim elementom kopice in zmanjšajte velikost kopice za 1. Na koncu z gnoji koren drevesa
Ponavljajte zgornje korake, dokler velikost kupa ni večja od 1
Tu je psevdokoda, ki predstavlja algoritem razvrščanja kopij.
Heapsort (a kot matrika) za (i = n / 2 - 1) do i> = 0 heapify (a, n, i) za i = n-1 do 0 zamenjava (a [0], a [i]) heapify (a, i, 0) konec za konec za heapify (a kot matrika, n kot int, i kot int) največji = i // Inicializiraj največji kot korenski int l eft = 2 * i + 1 // levi = 2 * i + 1 int desno = 2 * i + 2 // desno = 2 * i + 2 če (levo [največje]) največje = levo če (desno [največje]) največje = desno če (največje! = I) swap ( a [i], A [največji]) Heapify (a, n, največji) end heapify
Poleg teh obstajajo tudi drugi algoritmi za razvrščanje, ki niso tako dobro znani, na primer Introsort, Counting Sort itd. Če nadaljujemo z naslednjim naborom algoritmov v tem članku 'Podatkovne strukture in algoritmi', raziščimo algoritme iskanja.
 Iskanje algoritmov v Javi 
Iskanje je eno najpogostejših in najpogosteje izvedenih dejanj v običajnih poslovnih aplikacijah. Iskalni algoritmi so algoritmi za iskanje predmeta z določenimi lastnostmi med zbirko elementov. Oglejmo si dva najpogosteje uporabljena algoritma za iskanje.
 Algoritem linearnega iskanja v Javi 
Linearno iskanje ali zaporedno iskanje je najpreprostejši algoritem iskanja. Vključuje zaporedno iskanje elementa v dani podatkovni strukturi, dokler ne najdemo elementa ali ne dosežemo konca strukture. Če je element najden, se vrne lokacija elementa, sicer algoritem vrne NULL.
Tu je psevdokoda, ki predstavlja Linearno iskanje v Javi:
postopek linearno iskanje (a [], vrednost) za i = 0 do n-1, če je [i] = vrednost nato natisni 'Najdeno' vrne i konec, če je tiskanje 'Ni najdeno' konec za konec linearno_search
Jealgoritem surove sile.Čeprav je zagotovo najpreprostejši, vsekakor ni najbolj pogost zaradi svoje neučinkovitosti. Časovna zapletenost linearnega iskanja je O (N) .
 Binarni algoritem iskanja v Javi 
Binarno iskanje, znano tudi kot logaritemsko iskanje, je iskalni algoritem, ki najde položaj ciljne vrednosti v že razvrščeni matriki. Zbirko vhodnih podatkov razdeli na enake polovice, postavka pa se primerja s srednjim elementom seznama. Če je element najden, se iskanje tam konča. V nasprotnem primeru še naprej iščemo element z delitvijo in izbiro ustrezne particije polja, glede na to, ali je ciljni element manjši ali večji od srednjega elementa.
Tu je psevdokoda, ki predstavlja binarno iskanje v Javi:
Postopek binary_search razvrščeno polje n Velikost polja x Vrednost x iskati lowerBound = 1 upperBound = n, medtem ko x ni mogoče najti, če upperBound
Iskanje se konča, ko zgornja meja (naš kazalec) preide spodnjo mejo (zadnji element), kar pomeni, da smo iskali celotno matriko in element ni prisoten.Gre za najpogosteje uporabljene algoritme iskanja, predvsem zaradi hitrega časa iskanja. Časovna zapletenost binarnega iskanja je O (N) kar je izrazit napredek na O (N) časovna zapletenost linearnega iskanja.
S tem smo na koncu tega članka »Podatkovne strukture in algoritmi v Javi«. Obdelal sem eno najbolj temeljnih in najpomembnejših tem Java.Upam, da vam je jasno vse, kar je bilo v tem članku delljeno z vami.
  Poskrbite, da boste čim več vadili in si povrnili izkušnje.   
 Oglejte si    Edureka, zaupanja vredno podjetje za spletno učenje z mrežo več kot 250.000 zadovoljnih učencev, ki se širijo po vsem svetu. Tu smo, da vam pomagamo pri vsakem koraku na poti, saj smo poleg tega vprašanja za java intervjuji pripravili učni načrt, ki je zasnovan za študente in strokovnjake, ki želijo biti razvijalec Java. 
 Imate vprašanje za nas? Prosimo, omenite ga v oddelku za komentarje tega 'Podatkovne strukture in algoritmi v Javi'  članek in se vam bomo javili v najkrajšem možnem času.