Topp datastrukturer og algoritmer i Java som du trenger å vite

Hvis jeg måtte velge det viktigste temaet innen programvareutvikling, ville det være datastrukturer og algoritmer. Du kan tenke på det som det grunnleggende verktøyet som er tilgjengelig for alle dataprogrammerere. Mens vi programmerer, bruker vi datastrukturer å lagre og organisere data, og algoritmer å manipulere dataene i disse strukturene. Denne artikkelen inneholder en detaljert gjennomgang av alle vanlige datastrukturer og algoritmer i for å la leserne bli godt rustet.

Nedenfor er temaene diskutert i denne artikkelen:

• Datastrukturer i Java
  • Lineære datastrukturer
  • Hierarkiske datastrukturer
• Algoritmer i Java
  • Sorteringsalgoritmer
  • Søker algoritmer

Datastrukturer i Java

En datastruktur er en måte å lagre og organisere data på en datamaskin slik at den kan brukes effektivt. Det gir et middel til å administrere store datamengder effektivt. Og effektive datastrukturer er nøkkelen til å designe effektive algoritmer.

Idenne ‘Datastrukturer og algoritmer i Java’-artikkelen, skal vi dekke grunnleggende datastrukturer som:

• Lineære datastrukturer
  • Koblet liste
  • Stabler
  • Køer

• Hierarkiske datastrukturer
  • Binære trær
  • Dynger
  • Hash-bord

La oss sjekke ut hver av dem.

Lineære datastrukturer i Java

Lineære datastrukturer i er de hvis elementer er sekvensielle og ordnet på en måte slik at: det er bare en første elementet og har bare en neste element , det er bare en siste element og har bare en forrige element , mens alle andre elementer har en neste og en tidligere element.

Arrays

An array er en lineær datastruktursom representerer en gruppe av lignende elementer, tilgjengelig via indeks. Størrelsen på en matrise må oppgis før du lagrer data. Nedenfor er egenskaper for en matrise:

• Hvert element i en matrise er av samme datatype og har samme størrelse
• Elementer i matrisen lagres på sammenhengende minneplasser med det første elementet begynner på det minste minneplassering
• Du kan få tilfeldig tilgang til elementer i matrisen
• Arraydatastrukturen er ikke helt dynamisk

For eksempel , vil vi kanskje ha et videospill for å holde oversikt over de ti beste poengene for det spillet. Snarere enn å bruke ti forskjellige variabler for denne oppgaven kan vi bruke et enkelt navn for hele gruppen og bruke indeksnummer for å referere til høye poengsummer i den gruppen.

Koblet liste

TIL er en lineær datastruktur med samling av flere noder, der each element lagrer sine egne data og en peker til plasseringen av neste element. Den siste lenken i en koblet liste peker mot null, noe som indikerer slutten på kjeden. Et element i en koblet liste kalles a node . Den første noden kalles hode .Den siste noden heterde hale .

Typer koblet liste

Enkelinket liste (ensrettet)

Dobbeltkoblet liste (toveis)

Sirkulær koblet liste

Her er et enkelt eksempel: Se for deg en koblet liste som en kjede av binders som er koblet sammen. Du kan enkelt legge til en annen binders øverst eller nederst. Det er til og med raskt å sette inn en i midten. Alt du trenger å gjøre er å bare koble fra kjedet i midten, legge til den nye binders og deretter koble den andre halvdelen til igjen. En koblet liste er lik.

Stabler

Stable, en abstrakt datastruktur, er en samling av gjenstander som settes inn og fjernes i henhold til last-in-first-out (LIFO) prinsipp. Objekter kan settes inn i en bunke når som helst, men bare det sist innsatte (det vil si 'siste') objektet kan fjernes når som helst.Oppført nedenfor er egenskaper for en stabel:

• Det er en ordreliste derinnsetting og sletting kan bare utføres i den ene enden som kalles topp
• Rekursiv datastruktur med en peker til toppelementet
• Følger last-in-first-out (LIFO) prinsipp
• Støtter to mest grunnleggende metoder
  • trykk (e): Sett inn element e, til toppen av bunken
  • pop (): Fjern og legg tilbake toppelementet på bunken

Praktiske eksempler på stabelen inkluderer når du snur et ord,for å sjekke korrektheten av parentessekvens,implementere tilbake funksjonalitet i nettlesere og mange flere.

Køer

er også en annen type abstrakt datastruktur. I motsetning til en stabel er køen en samling objekter som settes inn og fjernes i henhold til først inn først ut (FIFO) prinsipp. Det vil si at elementer kan settes inn når som helst, men bare elementet som har stått lengst i køen kan fjernes når som helst.Oppført nedenfor er egenskaper for en kø:

• Ofte referert til som først inn først ut liste
• Støtter to mest grunnleggende metoder
  • enqueue (e): Sett inn element e, ved bak av køen
  • dequeue (): Fjern og returner elementet fra front av køen

Kø brukes iasynkron overføring av data mellom to prosesser, CPU-planlegging, Diskplanlegging og andre situasjoner der ressurser deles mellom flere brukere og serveres på førstemann til mølla-basis. Neste opp i denne ‘Datastrukturer og algoritmer i Java’-artikkelen har vi hierarkiske datastrukturer.

Hierarkiske datastrukturer i Java

Binært tre

Binary Tree er enhierarkiske tredatastrukturer der hver node har høyst to barn , som er referert til som venstre barn og riktig barn . Hvert binært tre har følgende grupper av noder:

• Rotnode: Det er den øverste noden og ofte referert til som hovednodenfordi alle andre noder kan nås fra roten
• Left Sub-Tree, som også er et binært tre
• Right Sub-Tree, som også er et binært tre

Oppført nedenfor er egenskapene til et binært tre:

• Et binært tre kan krysses på to måter:
  • Dybde første gjennomgang : I rekkefølge (venstre-rot-høyre), forhåndsbestilling (rot-venstre-høyre) og etterbestilling (venstre-høyre-rot)
  • Bredde første gjennomgang : Gjennomgang av nivåordre
• Tidskompleksitet av tregjennomgang: O (n)
• Maksimalt antall noder på nivå ‘l’ = 2^l-1.

Anvendelser av binære trær inkluderer:

• Brukes i mange søkeapplikasjoner der data stadig kommer inn / ut
• Som en arbeidsflyt for sammensetting av digitale bilder for visuelle effekter
• Brukes i nesten alle rutere med høy båndbredde for lagring av rutetabeller
• Brukes også i trådløst nettverk og minnetildeling
• Brukes i komprimeringsalgoritmer og mange flere

Binær haug

Binary Heap er en komplettbinært tre, som svarer på haugegenskapen. Enkelt sagt deter en variant av et binært tre med følgende egenskaper:

• Heap er et komplett binært tre: Et tre sies å være komplett hvis alle nivåene, bortsett fra muligens det dypeste, er fullstendige. Thans eiendom av Binary Heap gjør det egnet å bli lagret i et .
• Følger haugeiendom: En binær haug er enten en Min-haug eller a Max-Heap .
  • Min binær dyng: Feller hver node i en haug, er nodens verdi mindre enn eller lik verdiene til barna
  • Maks binær haug: Feller hver node i en haug, er nodens verdi større enn eller lik verdiene til barna

Populære applikasjoner av binær heap inkludererimplementere effektive prioritetskøer, effektivt finne de k minste (eller største) elementene i en matrise og mange flere.

Hash-bord

Tenk deg at du har en gjenstand og du vil tilordne en nøkkel til den for å gjøre det veldig enkelt å søke. For å lagre det nøkkel- / verdiparet kan du bruke en enkel matrise som en datastruktur der nøkler (heltall) kan brukes direkte som en indeks for å lagre dataverdier. I tilfeller der nøklene er for store og ikke kan brukes direkte som en indeks, brukes imidlertid en teknikk som kalles hashing.

hva betyr tostring i java

I hashing blir de store tastene konvertert til små nøkler ved hjelp av hash-funksjoner . Verdiene lagres deretter i en datastruktur som kallestil hasjbord. En hash-tabell er en datastruktur som implementerer en ordbok-ADT, en struktur som kan kartlegge unike nøkler til verdier.

Generelt har et hasjbord to hovedkomponenter:

1. Bucket Array: En bøtteoppstilling for en hash-tabell er en matrise A i størrelse N, der hver celle i A blir tenkt på som en 'bøtte', det vil si en samling nøkkelverdipar. Heltallet N definerer matrisens kapasitet.
2. Hash-funksjon: Det er en hvilken som helst funksjon som kartlegger hver tast k i vårt kart til et helt tall i området [0, N & minus 1], der N er kapasiteten til bøtteoppstillingen for denne tabellen.

Når vi legger objekter i en hashtable, er det mulig at forskjellige objekter kan ha samme hashkode. Dette kalles a kollisjon . For å håndtere kollisjon er det teknikker som lenking og åpen adressering.

Så dette er noen grunnleggende og mest brukte datastrukturer i Java. Nå som du er klar over hver av disse, kan du begynne å implementere dem i din . Med dette har vi fullført den første delen av ’denne‘ Datastrukturer og algoritmer i Java’-artikkelen. I neste del skal vi lære omgrunnleggende algoritmer og hvordan du bruker dem i praktiske applikasjoner som sortering og søk, dele og erobre, grådige algoritmer, dynamisk programmering.

Algoritmer i Java

Historisk brukt som et verktøy for å løse komplekse matematiske beregninger, er algoritmer dypt forbundet med datavitenskap, og spesielt med datastrukturer. En algoritme er en sekvens av instruksjoner som beskriver en måte å løse et bestemt problem på i en begrenset periode. De er representert på to måter:

• Flytskjemaer - Det er envisuell fremstilling av en algoritmes kontrollflyt
• Pseudokode - Dener en tekstlig fremstilling av en algoritme som tilnærmer seg den endelige kildekoden

Merk: Utførelsen av algoritmen måles basert på tidskompleksitet og romkompleksitet. For det meste er kompleksiteten til en hvilken som helst algoritme avhengig av problemet og av selve algoritmen.

La oss utforske de to hovedkategoriene av algoritmer i Java, som er:

• Sortering av algoritmer i Java
• Søker algoritmer i Java

Sortering av algoritmer i Java

Sorteringsalgoritmer er algoritmer som setter elementer i en liste i en bestemt rekkefølge. De mest brukte ordrene er numerisk rekkefølge og leksikografisk rekkefølge. I denne artikkelen ‘Datastrukturer og algoritmer’ kan vi utforske noen få sorteringsalgoritmer.

Boblesortering i Java

Bubblesortering, ofte referert til som synkende sortering, er den enkleste sorteringsalgoritmen. Den går flere ganger gjennom listen som skal sorteres, sammenligner hvert par tilstøtende elementer og bytter dem hvis de er i feil rekkefølge.Boblesorter får navnet sitt fordi det filtrerer ut elementene til toppen av matrisen, som bobler som flyter på vann.

Her erpseudokode som representerer boblesorteringsalgoritme (stigende sorteringssammenheng).

a [] er en matrise av størrelse N begynn BubbleSort (a []) erklærer heltall i, j for i = 0 til N - 1 for j = 0 til N - i - 1 hvis a [j]> a [j + 1 ] bytt deretter en [j], en [j + 1] ende hvis slutt for å returnere en slutt BubbleSort

Denne koden bestiller et endimensjonalt utvalg av N-dataelementer i stigende rekkefølge. En ytre sløyfe gjør at N-1 passerer over matrisen. Hvert pass bruker en indre sløyfe for å utveksle dataelementer slik at det neste minste dataelementet 'bobler' mot begynnelsen av matrisen. Men problemet er at algoritmen trenger ett helt pass uten bytte for å vite at listen er sortert.

Kompleksitet i verste og gjennomsnittlige tilfelle: O (n * n). Det verste tilfellet oppstår når en matrisesorteres omvendt.

Beste sakstidskompleksitet: På). Beste tilfelle oppstår når en matrise allerede er sortert.

Valg Sorter i Java

Valgsortering er en kombinasjon av både søk og sortering. Algoritmen sorterer en matrise ved gjentatte ganger å finne minimumselementet (vurderer stigende rekkefølge) fra den usorterte delen og sette den på en riktig posisjon i matrisen.

Her er pseudokode som representerer seleksjonsalgoritme (stigende sorteringskontekst).

a [] er en matrise av størrelse N begynner SelectionSort (a []) for i = 0 til n - 1 / * sett gjeldende element som minimum * / min = i / * finn minimumselementet * / for j = i + 1 til n hvis liste [j]
Som du kan forstå fra koden, er antallet ganger sorten går gjennom matrisen ett mindre enn antall elementer i matrisen. Den indre sløyfen finner den neste minste verdien, og den ytre sløyfen plasserer den verdien på riktig plassering. Valgsortering gjør aldri mer enn O (n) -bytter og kan være nyttig når minneskrivingen er en kostbar operasjon.
 Tidskompleksitet: På2) da det er to nestede løkker.
 Hjelpeplass: Eller (1).
 Innsetting Sorter i Java 
Innsettingssortering er en enkel sorteringsalgoritme som går gjennom listen ved å konsumere ett inngangselement om gangen og bygge den endelige sorterte matrisen. Det er veldig enkelt og mer effektivt på mindre datasett. Det er stabil og på plass sorteringsteknikk.
Her er pseudokode som representerer algoritme for innsettingssortering (stigende sorteringssammenheng).
a [] er en matrise av størrelse N begynner InsertionSort (a []) for i = 1 til N-tast = a [i] j = i - 1 mens (j> = 0 og en [j]> tast 0 a [j + 1] = x [j] j = j - 1 slutt mens en [j + 1] = nøkkelende for slutt InsertionSort
Som du kan forstå fra koden, innsettingssorteringsalgoritmenfjerner ett element fra inngangsdataene, finner stedet det tilhører i den sorterte listen og setter det inn der. Den gjentas til ingen inngangselementer forblir usorterte.
 Beste tilfelle: Det beste tilfellet er når input er en matrise som allerede er sortert. I dette tilfellet har innsettingssortering en lineær kjøretid (dvs. & Theta (n)).
 Verste tilfelle:  Den enkleste worst case-inndata er en matrise sortert i omvendt rekkefølge.
 QuickSort i Java 
Quicksort-algoritme er en rask, rekursiv, ikke-stabil sorteringsalgoritme som fungerer etter delings- og erobringsprinsippet. Den plukker et element som pivot og partisjonerer den gitte matrisen rundt den plukkede pivoten.
 Fremgangsmåte for å implementere Rask sortering:  
 
Velg et passende “pivot point”.
Del listene i to listerbasert på dette dreieelementet. Hvert element som er mindre enn pivotelementet plasseres i venstre liste, og hvert element som er større plasseres i høyre liste. Hvis et element er lik pivotelementet, kan det gå i hvilken som helst liste. Dette kalles partisjonsoperasjonen.
Sorter hver av de mindre listene rekursivt. 
Her er pseudokode som representerer Quicksort-algoritme.
QuickSort (A som matrise, lav som int, høy som int) {hvis (lav
I ovennevnte pseudokode, skillevegg() funksjon utfører partisjonsoperasjon og Quicksort () funksjon kaller gjentatte ganger partisjonsfunksjon for hver genererte liste. Kompleksiteten til quicksort i gjennomsnitt er & Theta (n log (n)) og i verste fall er & Theta (n2).
 Slå sammen Sorter i Java 
Mergesort er en rask, rekursiv, stabil sorteringsalgoritme som også fungerer etter delings- og erobringsprinsippet. I likhet med kviksort, deler mergesorter listen over elementer i to lister. Disse listene sorteres uavhengig og deretter kombineres. Under kombinasjonen av listene settes elementene inn (eller slås sammen) på riktig sted i listen.
Her er pseudokode som representerer Merge Sort Algorithm.
prosedyre MergeSort (a som array) hvis (n == 1) returnerer en var l1 som array = a [0] ... a [n / 2] var l2 som array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) sluttprosedyre prosedyre flette (a som array, b som array) var c som array mens (a og b har elementer) hvis ( a [0]> b [0]) legg til b [0] til slutten av c fjerne b [0] fra b ellers legge til [0] til slutten av c fjerne a [0] fra en ende hvis slutt mens mens (a har elementer) legg til [0] til slutten av c fjern a [0] fra en ende mens mens (b har elementer) legg til b [0] til slutten av c fjerne b [0] fra b-enden mens retur avslutte prosedyren
 sammenslåing () funksjon deler listen i to, samtaler sammenslåing () på disse listene hver for seg og kombinerer dem ved å sende dem som parametere for å slå sammen () -funksjonen.Algoritmen har en kompleksitet på O (n log (n)) og har et bredt spekter av applikasjoner.
 Haugsortering i Java 
Heapsort er en sammenligningsbasert sorteringsalgoritmeBinary Heap datastruktur. Du kan tenke på det som forbedret versjon f utvalgssort, hvorden deler sine innspill i en sortert og en usortert region, og den krymper iterativt den usorterte regionen ved å trekke ut det største elementet og flytte det til det sorterte området.
 Fremgangsmåte for å implementere Quicksort (i økende rekkefølge): 
Bygg en maks haug med sorteringsmatrisen
På dette punktett, er den største gjenstanden lagret ved roten til dyngen. Erstatt den med den siste gjenstanden av haugen og reduser størrelsen på haugen med 1. Til slutt, heapify roten til treet
Gjenta trinnene ovenfor til haugens størrelse er større enn 1
Her er pseudokode som representerer Heap Sort Algorithm.
Heapsort (a som array) for (i = n / 2 - 1) til i> = 0 heapify (a, n, i) for i = n-1 til 0 swap (a [0], a [i]) heapify (a, i, 0) slutt for slutt for heapify (a som array, n som int, i som int) størst = i // Initialiser størst som root int l eft = 2 * i + 1 // left = 2 * i + 1 int høyre = 2 * i + 2 // høyre = 2 * i + 2 hvis (venstre a [største]) største = venstre hvis (høyre a [største]) største = høyre hvis (største! = I) bytte ( a [i], A [største]) Heapify (a, n, største) end heapify
Bortsett fra disse, er det andre sorteringsalgoritmer som ikke er så kjente, for eksempel Introsort, Counting Sort osv. Når vi går videre til neste sett med algoritmer i denne ‘Data Structures and Algorithms’ artikkelen, la oss utforske søkealgoritmer.
 Søker algoritmer i Java 
Søking er en av de vanligste og ofte utførte handlingene i vanlige forretningsapplikasjoner. Søkealgoritmer er algoritmer for å finne et element med spesifiserte egenskaper blant en samling av elementer. La oss utforske to av de mest brukte søkealgoritmene.
 Lineær søkealgoritme i Java 
Lineært søk eller sekvensielt søk er den enkleste søkealgoritmen. Det innebærer sekvensiell søking etter et element i den gitte datastrukturen til enten elementet er funnet eller slutten av strukturen er nådd. Hvis elementet blir funnet, returneres varens beliggenhet, ellers returnerer algoritmen NULL.
Her er pseudokode som representerer Lineær søk i Java:
prosedyre linear_search (a [], verdi) for i = 0 til n-1 hvis en [i] = verdi, skriv ut 'Fant' return i end if print 'Not found' end for end linear_search
Det er enbrute-force algoritme.Selv om det absolutt er det enkleste, er det absolutt ikke det vanligste på grunn av dets ineffektivitet. Tidskompleksitet for lineært søk er PÅ) .
 Binær søkealgoritme i Java 
Binært søk, også kjent som logaritmisk søk, er en søkealgoritme som finner posisjonen til en målverdi i en allerede sortert matrise. Den deler inngangssamlingen i like halvdeler, og varen sammenlignes med det midterste elementet på listen. Hvis elementet blir funnet, slutter søket der. Ellers fortsetter vi å lete etter elementet ved å dele og velge riktig partisjon av matrisen, basert på om målelementet er mindre eller større enn det midterste elementet.
Her er pseudokode som representerer Binary Search i Java:
Fremgangsmåte binær_søk en sortert matrise n størrelse på matrise x verdi som skal søkes underBound = 1 upperBound = n mens x ikke blir funnet hvis upperBound
Søket avsluttes når upperBound (pekeren vår) går forbi lowerBound (siste element), noe som betyr at vi har søkt i hele matrisen og elementet ikke er til stede.Det er de mest brukte søkealgoritmene, hovedsakelig på grunn av den raske søketiden. Tidskompleksiteten til det binære søket er PÅ) som er en markant forbedring av PÅ) tidskompleksitet av Linear Search.
Dette bringer oss til slutten av denne ‘Datastrukturer og algoritmer i Java’-artikkelen. Jeg har dekket et av de mest grunnleggende og viktige temaene i Java.Håper du er tydelig med alt som har blitt delt med deg i denne artikkelen.
  Forsikre deg om at du trener så mye som mulig og tilbakestiller opplevelsen.   
 Sjekk ut    av Edureka, et pålitelig online læringsfirma med et nettverk av mer enn 250 000 fornøyde elever spredt over hele verden. Vi er her for å hjelpe deg med hvert trinn på reisen, for å bli en foruten dette java-intervjuspørsmålene, kommer vi med en læreplan som er designet for studenter og fagpersoner som ønsker å være Java-utvikler. 
hvordan du installerer php på Windows 10
 Har du et spørsmål til oss? Vennligst nevn det i kommentarfeltet i denne ‘Datastrukturer og algoritmer i Java’  artikkel, og vi kommer tilbake til deg så snart som mulig.