Vrhunske strukture podataka i algoritmi u Javi koje trebate znati



Ovaj blog o strukturama podataka i algoritmima na Javi pomoći će vam da razumijete sve glavne strukture podataka i algoritme na Javi.

Kad bih morao odabrati jedinu najvažniju temu u razvoju softvera, to bi bile strukture podataka i algoritmi. Možete ga smatrati temeljnim alatom dostupan svakom računalnom programeru. Tijekom programiranja koristimo strukture podataka za pohranu i organiziranje podataka i algoritmi za manipulaciju podacima u tim strukturama. Ovaj članak sadrži detaljan pregled svih uobičajenih struktura podataka i algoritama u kako bi se čitateljima omogućilo da se dobro opreme.

U nastavku su navedene teme o kojima se raspravlja u ovom članku:





Strukture podataka u Javi

Struktura podataka način je spremanja i organiziranja podataka u računalu kako bi se mogli učinkovito koristiti. Pruža sredstvo za učinkovito upravljanje velikim količinama podataka. A učinkovite strukture podataka ključne su za dizajniranje učinkovitih algoritama.

Uovaj članak 'Strukture podataka i algoritmi u Javi' pokrivat ćemo osnovne strukture podataka kao što su:



Provjerimo svakog od njih.

Linearne podatkovne strukture u Javi

Linearne strukture podataka u su oni čiji su elementi sekvencijalni i poredani na način da: postoji samo jedan prvi element i ima samo jedan sljedeći element , postoji samo jedan posljednji element i ima samo jedan prethodni element , dok svi ostali elementi imaju a Sljedeći i a prethodni element.

Nizovi

An niz je linearna struktura podatakapredstavlja skupinu sličnih elemenata kojima se pristupa indeksom. Prije spremanja podataka mora se navesti veličina polja. Dolje su navedena svojstva niza:



  • Svaki je element u nizu iste vrste podataka i iste je veličine
  • Elementi niza pohranjuju se na susjedna memorijska mjesta, a prvi element počinje na najmanjem memorijskom mjestu
  • Elementima niza može se slučajno pristupiti
  • Struktura podataka niza nije potpuno dinamična

Nizovi - Edureka

Na primjer , možda bismo željeli da video igra prati deset najboljih rezultata za tu igru. Umjesto da koristite deset različitih varijable za ovaj zadatak mogli bismo upotrijebiti jedno ime za cijelu skupinu i koristiti indeksne brojeve za pozivanje na visoke ocjene u toj skupini.

Povezani popis

DO je linearna struktura podataka sa skupom više čvorova, gdje je eelement ach pohranjuje vlastite podatke i pokazivač na mjesto sljedećeg elementa. Posljednja karika na povezanom popisu pokazuje nulu, što označava kraj lanca. Element na povezanom popisu naziva se a čvor . Prvi čvor naziva se glava .Poziva se zadnji čvor rep .

Vrste povezanih popisa

Popis s jednom vezom (jednosmjerni)

Popis dvostruko povezanih (dvosmjerni)

Kružno povezani popis

Evo jednostavnog primjera: Zamislite povezani popis poput lanca spajalica povezanih zajedno. Možete jednostavno dodati još jednu spajalicu na vrh ili na dno. Čak je i brzo umetnuti jedan u sredinu. Sve što morate učiniti je samo odspojiti lanac u sredini, dodati novu spajalicu, a zatim ponovno spojiti drugu polovicu. Povezani popis sličan je.

Stogovi

Stog, apstraktna struktura podataka, zbirka je predmeta koji se umeću i uklanjaju prema zadnji-u-prvom-izašao (LIFO) načelo. Objekti se mogu umetnuti u stog u bilo kojem trenutku, ali u bilo kojem trenutku može se ukloniti samo posljednji umetnuti (tj. 'Zadnji') objekt.Dolje su navedena svojstva stoga:

  • To je poredani popis u kojemumetanje i brisanje može se izvesti samo na jednom kraju koji se naziva vrh
  • Rekurzivna struktura podataka s pokazivačem na gornji element
  • Slijedi zadnji-u-prvom-izašao (LIFO) načelo
  • Podržava dvije najvažnije metode
    • push (e): Umetnite element e, na vrh snopa
    • pop (): Uklonite i vratite gornji element na hrpi

Praktični primjeri stoga uključuju preokretanje riječi,provjeriti ispravnost zagradeslijed,implementiranje back funkcionalnosti u preglednike i mnoge druge.

Redovi

su također druga vrsta apstraktne strukture podataka. Za razliku od stoga, red je zbirka objekata koji se ubacuju i uklanjaju prema prvi u prvom izlazu (FIFO) načelo. Odnosno, elementi se mogu umetnuti u bilo kojem trenutku, ali u bilo kojem trenutku može se ukloniti samo element koji je najdulje bio u redu čekanja.Dolje su navedena svojstva reda:

implementirati red prioriteta c ++
  • Često se naziva i prvi u prvom popis
  • Podržava dvije najvažnije metode
    • enqueue (e): Umetnite element e, na straga reda
    • dequeue (): Uklonite i vratite element iz ispred reda

Redovi se koriste uasinkroni prijenos podataka između dva procesa, zakazivanje CPU-a, zakazivanje diska i druge situacije u kojima se resursi dijele između više korisnika i poslužuju po principu 'prvi dođe prvi.' Sljedeće u ovom članku 'Strukture podataka i algoritmi u Javi' imamo hijerarhijske strukture podataka.

Hijerarhijske strukture podataka u Javi

Binarno stablo

Binarno stablo jehijerarhijske strukture podataka stabla u kojima svaki čvor ima najviše dvoje djece , koji se nazivaju lijevo dijete i pravo dijete . Svako binarno stablo ima sljedeće skupine čvorova:

  • Korijenski čvor: To je najviši čvor i često se naziva glavnim čvoromjer se do svih ostalih čvorova može doći iz korijena
  • Lijevo podstablo, koje je ujedno i binarno stablo
  • Desno podstablo, koje je ujedno i binarno stablo

Dolje su navedena svojstva binarnog stabla:

  • Binarno stablo može se preći na dva načina:
    • Dubina Prvo prelazak : Redoslijed (lijevo-korijen-desno), predbilježba (korijen-lijevo-desno) i redoslijed (lijevo-desno-korijen)
    • Širina prvo prelazak : Prelazak redoslijeda razine
  • Složenost vremenskog presijecanja stabla: O (n)
  • Maksimalni broj čvorova na razini 'l' = 2l-1.

Primjene binarnih stabala uključuju:

  • Koristi se u mnogim aplikacijama za pretraživanje u kojima podaci neprestano ulaze / izlaze
  • Kao tijek rada za komponiranje digitalnih slika za vizualne efekte
  • Koristi se u gotovo svakom usmjerivaču s velikom širinom pojasa za spremanje stolova usmjerivača
  • Također se koristi u bežičnom umrežavanju i dodjeli memorije
  • Koristi se u algoritmima kompresije i mnogim drugim

Binarna hrpa

Binarna hrpa je cjelovitabinarno stablo, koji odgovara svojstvu gomile. Jednostavno rečenoje varijacija binarnog stabla sa sljedećim svojstvima:

  • Heap je kompletno binarno stablo: Za drvo se kaže da je cjelovito ako su sve njegove razine, osim vjerojatno najdublje, cjelovite. Tnjegovo svojstvo Binary Heap čini ga pogodnim za pohranu u .
  • Slijedi svojstvo hrpe: Binarna hrpa je ili Min-hrpa ili a Max-Heap .
    • Min binarna hrpa: Fili svaki čvor u hrpi, vrijednost čvora je manje ili jednako vrijednosti djece
    • Maksimalna binarna hrpa: Fili svaki čvor u hrpi, vrijednost čvora je veći ili jednak vrijednosti djece

Popularne primjene binarne hrpe uključujuimplementiranje učinkovitih redova prioriteta, učinkovito pronalaženje k najmanjih (ili najvećih) elemenata u nizu i još mnogo toga.

Hash tablice

Zamislite da imate objekt a želite mu dodijeliti ključ kako biste pretraživanje učinili vrlo jednostavnom. Za spremanje tog para ključ / vrijednost možete upotrijebiti jednostavan niz poput strukture podataka gdje se ključevi (cijeli brojevi) mogu izravno koristiti kao indeks za pohranu vrijednosti podataka. Međutim, u slučajevima kada su tipke prevelike i ne mogu se izravno koristiti kao indeks, koristi se tehnika koja se naziva raspršivanje.

U raspršivanju se veliki ključevi pretvaraju u male ključeve pomoću hash funkcije . Vrijednosti se zatim spremaju u strukturu podataka koja se nazivado hash tablica. Hash tablica je struktura podataka koja implementira rječnik ADT, strukturu koja može preslikati jedinstvene ključeve u vrijednosti.

Općenito, hash tablica ima dvije glavne komponente:

  1. Niz kanta: Polje segmenta za hash tablicu je niz A veličine N, gdje se svaka ćelija A smatra 'sefom', odnosno skupom parova ključ / vrijednost. Cijeli broj N definira kapacitet polja.
  2. Funkcija raspršivanja: Bilo koja je funkcija koja preslikava svaki ključ k na našoj karti na cijeli broj u rasponu [0, N i minus 1], gdje je N kapacitet segmenta polja za ovu tablicu.

Kada stavimo objekte u hashtable, moguće je da različiti objekti mogu imati isti hashcode. To se naziva a sudar . Za rješavanje sudara postoje tehnike poput lančanog i otvorenog adresiranja.

Ovo su neke osnovne i najčešće korištene podatkovne strukture u Javi. Sad kad ste svjesni svakog od ovih, možete ih početi implementirati u svoj . Ovim smo dovršili prvi dio članka 'ovaj' Strukture podataka i algoritmi u Javi '. U sljedećem ćemo dijelu učiti o tomeosnovni algoritmi i kako ih koristiti u praktičnim primjenama poput sortiranja i pretraživanja, podijeli i osvoji, pohlepni algoritmi, dinamičko programiranje.

Algoritmi u Javi

Povijesno korišteni kao alat za rješavanje složenih matematičkih proračuna, algoritmi su duboko povezani s informatikom, a posebno sa strukturama podataka. Algoritam je slijed uputa koji opisuju način rješavanja određenog problema u ograničenom vremenskom razdoblju. Predstavljeni su na dva načina:

  • Dijagrami toka - To jevizualni prikaz toka upravljanja algoritma
  • Pseudokod - Toje tekstualni prikaz algoritma koji aproksimira konačni izvorni kod

Bilješka: Učinak algoritma mjeri se na temelju vremenske složenosti i složenosti prostora. Složenost bilo kojeg algoritma uglavnom ovisi o problemu i o samom algoritmu.

Istražimo dvije glavne kategorije algoritama u Javi, a to su:

Algoritmi sortiranja u Javi

Algoritmi za sortiranje algoritmi su koji stavljaju elemente popisa u određeni redoslijed. Najčešće korišteni redoslijed je numerički poredak i leksikografski poredak. U ovom članku 'Strukture podataka i algoritmi' istražujemo nekoliko algoritama za sortiranje.

Razvrstavanje mjehurića na Javi

Sortiranje mjehurića, koje se često naziva sortiranjem koje tone, najjednostavniji je algoritam sortiranja. Uzastopno korača kroz popis radi razvrstavanja, uspoređuje svaki par susjednih elemenata i zamjenjuje ih ako su u pogrešnom redoslijedu.Ime mjehurića dobiva jer filtrira elemente na vrhu niza, poput mjehurića koji plutaju po vodi.

Evopseudokod koji predstavlja algoritam sortiranja mjehurića (rastući kontekst sortiranja).

a [] je niz veličine N begin BubbleSort (a []) deklarira cijeli broj i, j za i = 0 do N - 1 za j = 0 do N - i - 1 ako je a [j]> a [j + 1 ] zatim zamijenite [j], [j + 1] kraj ako kraj za povratak kraj BubbleSort

Ovaj kod naređuje jednodimenzionalni niz od N podataka u uzlaznom redoslijedu. Vanjska petlja čini da N-1 prolazi preko niza. Svaki prolaz koristi unutarnju petlju za razmjenu stavki podataka tako da se sljedeća najmanja podatkovna stavka 'oblači' prema početku niza. Ali problem je što algoritam treba jednu cijelu prolaznicu bez ikakve zamjene da bi znao da je popis sortiran.

Najgora i prosječna složenost slučaja: O (n * n). Najgori slučaj se događa kada je niz obrnuto sortiran.

Složenost najboljeg slučaja: Na). Najbolji slučaj događa se kada je niz već sortiran.

Sortiranje odabira na Javi

Sortiranje po odabiru kombinacija je pretraživanja i sortiranja. Algoritam sortira niz ponavljajući pronalaženje minimalnog elementa (uzimajući u obzir uzlazni poredak) iz nerazvrstanog dijela i stavljajući ga na odgovarajuće mjesto u nizu.

niz objekata u Java primjeru programa

Evo pseudokoda koji predstavlja algoritam sortiranja odabira (rastući kontekst sortiranja).

a [] je niz veličine N begin SelectionSort (a []) za i = 0 do n - 1 / * postavi trenutni element kao minimum * / min = i / * pronađi minimalni element * / za j = i + 1 do n ako popis [j]

Kao što možete shvatiti iz koda, broj puta prolaska sortiranja kroz niz je jedan manji od broja stavki u nizu. Unutarnja petlja pronalazi sljedeću najmanju vrijednost, a vanjska petlja postavlja tu vrijednost na njeno pravilno mjesto. Sortiranje odabira nikad ne vrši više od O (n) zamjena i može biti korisno kada je upisivanje u memoriju skupa operacija.

Složenost vremena: Na2) jer postoje dvije ugniježđene petlje.

Pomoćni prostor: Ili (1).

Sortiranje umetanja na Javi

Sortiranje umetanja jednostavan je algoritam za sortiranje koji se kreće kroz popis trošeći po jedan ulazni element istovremeno i gradi konačni sortirani niz. Vrlo je jednostavan i učinkovitiji na manjim skupovima podataka. To je stabilna tehnika sortiranja na mjestu.

Evo pseudokoda koji predstavlja algoritam sortiranja umetanja (rastući kontekst sortiranja).

a [] je niz veličine N begin InsertionSort (a []) za i = 1 do N ključ = a [i] j = i - 1 dok (j> = 0 i a [j]> tipka0 a [j + 1] = x [j] j = j - 1 kraj dok je [j + 1] = ključni kraj za kraj InsertionSort

Kao što možete shvatiti iz koda, algoritam sortiranja umetanjauklanja jedan element iz ulaznih podataka, pronalazi mjesto koje mu pripada unutar sortiranog popisa i tamo ga ubacuje. Ponavlja se sve dok nijedan ulazni element ne ostane nesortiran.

Najbolji slučaj: Najbolji je slučaj kada je ulaz niz koji je već sortiran. U ovom slučaju sortiranje umetanja ima linearno vrijeme izvođenja (tj. & Theta (n)).

Najgori slučaj: Najjednostavniji unos u najgorem slučaju je niz sortiran obrnutim redoslijedom.

QuickSort u Javi

Quicksort algoritam je brzi, rekurzivni, nestabilni algoritam sortiranja koji djeluje po principu podijeli i osvoji. Odabire element kao stožer i razdvaja zadani niz oko tog izabranog pivota.

Koraci za implementaciju brzog sortiranja:

  1. Odaberite prikladnu 'točku okretanja'.
  2. Podijelite popise na dva popisana temelju ovog stožnog elementa. Svaki element koji je manji od pivot elementa stavlja se na lijevi popis, a svaki veći element stavlja se na desni popis. Ako je element jednak zaokretnom elementu, tada može ići na bilo koji popis. To se naziva operacija particije.
  3. Rekurzivno sortiranje svakog od manjih popisa.

Evo pseudokoda koji predstavlja algoritam Quicksort.

QuickSort (A kao niz, nisko kao int, visoko kao int) {if (nisko

U gornjem pseudokodu, particija () funkcija izvodi operaciju particije i Brzi sortiraj () funkcija više puta poziva particijsku funkciju za svaki manji generirani popis. Složenost brzog sortiranja u prosječnom je slučaju & Theta (n log (n)), a u najgorem slučaju & Theta (n2).

Spajanje sortiranja na Javi

Mergesort je brz, rekurzivan, stabilan algoritam sortiranja koji također radi po principu podijeli i osvoji. Slično brzom sortiranju, sortiranje spajanjem dijeli popis elemenata na dva popisa. Ti se popisi neovisno sortiraju, a zatim kombiniraju. Tijekom kombinacije popisa elementi se ubacuju (ili spajaju) na pravom mjestu popisa.

Evo pseudokoda koji predstavlja algoritam sortiranja stapanja.

postupak MergeSort (a kao niz) ako (n == 1) vrati var l1 kao niz = a [0] ... a [n / 2] var l2 kao niz = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) postupak završetka postupka spajanje (a kao niz, b kao niz) var c kao niz dok (a i b imaju elemente) if ( a [0]> b [0]) dodaj b [0] na kraj c ukloni b [0] iz b ostalo dodaj a [0] na kraj c ukloni [0] s kraja ako završi dok while (a ima elemente) dodajte a [0] na kraj c uklonite a [0] s kraja dok dok (b ima elemente) dodajte b [0] na kraj c uklonite b [0] s b kraja dok se vraća c završni postupak

mergesort () funkcija dijeli popis na dva poziva mergesort () na tim popisima odvojeno, a zatim ih kombinira tako što ih šalje kao parametre u funkciju merge ().Algoritam ima složenost O (n log (n)) i ima širok spektar primjena.

Razvrstavanje hrpe na Javi

Heapsort je algoritam sortiranja zasnovan na usporedbiStruktura podataka binarne hrpe. Možete to smatrati poboljšanom verzijom odabira, gdjedijeli svoj ulaz na razvrstano i nesortirano područje, a iterativno smanjuje nesortirano izvlačenjem najvećeg elementa i premještanjem na razvrstano područje.

Koraci za implementaciju Quicksort-a (u sve većem redoslijedu):

  1. Izgradite maksimalnu hrpu s nizom za sortiranje
  2. Na ovom mjestut, najveći je predmet pohranjen u korijenu hrpe. Zamijenite ga zadnjim dijelom hrpe i smanjite veličinu hrpe za 1. Napokon, pojačajte korijen stabla
  3. Ponavljajte gornje korake dok veličina hrpe ne bude veća od 1

Evo pseudokoda koji predstavlja algoritam sortiranja hrpe.

Heapsort (a kao niz) za (i = n / 2 - 1) do i> = 0 heapify (a, n, i) za i = n-1 do 0 swap (a [0], a [i]) heapify (a, i, 0) kraj za kraj za gomilanje (a kao niz, n kao int, i kao int) najveći = i // Inicijaliziraj najveći kao korijen int l eft = 2 * i + 1 // lijevo = 2 * i + 1 int desno = 2 * i + 2 // desno = 2 * i + 2 ako (lijevo [najveći]) najveći = lijevo ako (desno [najveći]) najveći = desno ako (najveći! = I) zamijeni ( a [i], A [najveći]) Heapify (a, n, najveći) kraj heapify

Osim njih, postoje i drugi algoritmi za sortiranje koji nisu toliko poznati, poput Introsort, Counting Sort itd. Prijelazeći na sljedeći skup algoritama u ovom članku 'Strukture podataka i algoritmi', istražimo algoritme pretraživanja.

Pretraživanje algoritama na Javi

Pretraživanje je jedna od najčešćih i najčešće izvođenih radnji u redovnim poslovnim aplikacijama. Algoritmi pretraživanja algoritmi su za pronalaženje predmeta s određenim svojstvima među zbirkom predmeta. Istražimo dva najčešće korištena algoritma pretraživanja.

Algoritam linearnog pretraživanja na Javi

Linearno pretraživanje ili sekvencijalno pretraživanje najjednostavniji je algoritam pretraživanja. Uključuje sekvencijalno traženje elementa u datoj strukturi podataka sve dok se ne pronađe element ili ne postigne kraj strukture. Ako je element pronađen, vraća se mjesto stavke, u suprotnom algoritam vraća NULL.

Evo pseudokoda koji predstavlja Linearno pretraživanje na Javi:

postupak linearno_traženje (a [], vrijednost) za i = 0 do n-1 ako je [i] = vrijednost tada ispis 'Pronađeno' vrati i završi ako ispis 'Nije pronađeno' završi za kraj linearno_traženje

To jealgoritam grube sile.Iako je sigurno najjednostavnije, definitivno nije najčešće zbog svoje neučinkovitosti. Složenost vremena linearnog pretraživanja je NA) .

Binarni algoritam pretraživanja na Javi

Binarno pretraživanje, poznato i kao logaritamsko pretraživanje, algoritam je pretraživanja koji pronalazi položaj ciljne vrijednosti unutar već razvrstanog niza. Zbirku unosa dijeli na jednake polovice i stavka se uspoređuje sa srednjim elementom popisa. Ako je element pronađen, pretraživanje tamo završava. Inače, nastavljamo tražiti element dijeljenjem i odabirom odgovarajuće particije niza na temelju toga je li ciljni element manji ili veći od srednjeg elementa.

Evo pseudokoda koji predstavlja binarno pretraživanje na Javi:

Procedura binary_search sortirani niz n veličina polja x vrijednost za pretragu lowerBound = 1 upperBound = n dok x nije pronađen ako upperBound

Pretraživanje se završava kad gornja granica (naš pokazivač) prolazi prošlost donje granice (posljednji element), što znači da smo pretražili cijeli niz, a element nije prisutan.To su najčešće korišteni algoritmi pretraživanja prvenstveno zbog svog brzog vremena pretraživanja. Vremenska složenost binarnog pretraživanja je NA) što je značajno poboljšanje na NA) vremenska složenost Linearnog pretraživanja.

google podaci znanstvenik pitanja za intervju

To nas dovodi do kraja ovog članka „Strukture podataka i algoritmi u Javi“. Obradio sam jednu od najvažnijih i najvažnijih tema Jave.Nadam se da vam je jasno sve što je s vama podijeljeno u ovom članku.

Obavezno vježbajte što je više moguće i vratite svoje iskustvo.

Pogledajte Edureka, pouzdane tvrtke za internetsko učenje s mrežom od više od 250 000 zadovoljnih učenika raširenih širom svijeta. Ovdje smo da vam pomognemo u svakom koraku na putovanju, jer osim što postajete pitanja za ovaj intervju za javu, donosimo kurikulum koji je dizajniran za studente i profesionalce koji žele biti programer za Javu.

Imate pitanje za nas? Molimo navedite ga u odjeljku za komentare ovog 'Strukture podataka i algoritmi u Javi' članka i javit ćemo vam se u najkraćem mogućem roku.