Top datastrukturer og algoritmer i Java, som du har brug for at vide

Hvis jeg skulle vælge det vigtigste emne inden for softwareudvikling, ville det være datastrukturer og algoritmer. Du kan tænke på det som det grundlæggende værktøj, der er tilgængeligt for enhver computerprogrammerer. Under programmering bruger vi datastrukturer at gemme og organisere data og algoritmer at manipulere dataene i disse strukturer. Denne artikel indeholder en detaljeret gennemgang af alle de almindelige datastrukturer og algoritmer i for at give læserne mulighed for at blive veludstyrede.

Nedenfor er de emner, der diskuteres i denne artikel:

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

Datastrukturer i Java

En datastruktur er en måde at lagre og organisere data på en computer, så de kan bruges effektivt. Det giver et middel til effektivt at administrere store mængder data. Og effektive datastrukturer er nøglen til at designe effektive algoritmer.

Idenne artikel 'Datastrukturer og algoritmer i Java' vil vi dække grundlæggende datastrukturer såsom:

• Lineære datastrukturer
  • Tilknyttet liste
  • Stakke
  • Køer

• Hierarkiske datastrukturer
  • Binære træer
  • Dynger
  • Hash-borde

Lad os se på hver af dem.

Lineære datastrukturer i Java

Lineære datastrukturer i er dem, hvis elementer er sekventielle og ordnet på en måde, så: der er kun en første element og har kun en næste element , der er kun en sidste element og har kun en forrige element , mens alle andre elementer har en Næste og en Tidligere element.

Arrays

An array er en lineær datastrukturrepræsenterer en gruppe af lignende elementer, der er adgang til med indeks. Størrelsen på en matrix skal angives, før data lagres. Nedenfor er en række egenskaber:

• Hvert element i en matrix er af samme datatype og har samme størrelse
• Elementerne i arrayet lagres ved sammenhængende hukommelsessteder, hvor det første element starter ved det mindste hukommelsessted
• Elementer i arrayet kan fås tilfældigt
• Arraydatastrukturen er ikke helt dynamisk

For eksempel , vil vi måske have et videospil for at holde styr på de ti bedste scores for det spil. I stedet for at bruge ti forskellige variabler til denne opgave kunne vi bruge et enkelt navn til hele gruppen og bruge indeksnumre til at henvise til de høje score i den gruppe.

Tilknyttet liste

TIL er en lineær datastruktur med indsamling af flere noder, hvor each-element gemmer sine egne data og en markør til placeringen af ​​det næste element. Det sidste link i en sammenkædet liste peger på null, hvilket indikerer slutningen af ​​kæden. Et element i en sammenkædet liste kaldes a knude . Den første knude kaldes hoved .Den sidste knude kaldesdet hale .

Typer af sammenkædet liste

Enkeltkædet liste (ensrettet)

Dobbeltkoblet liste (tovejs)

Cirkulær sammenkædet liste

Her er et simpelt eksempel: Forestil dig en sammenkædet liste som en kæde af papirclips, der er knyttet sammen. Du kan nemt tilføje en anden papirclips til toppen eller bunden. Det er endda hurtigt at indsætte en i midten. Alt du skal gøre er at bare frakoble kæden i midten, tilføje den nye papirclips og derefter tilslutte den anden halvdel igen. En sammenkædet liste er ens.

Stakke

Stak, en abstrakt datastruktur, er en samling af genstande der indsættes og fjernes i henhold til last-in-first-out (LIFO) princip. Objekter kan indsættes i en stak til enhver tid, men kun det senest indsatte (dvs. 'sidste') objekt kan fjernes når som helst.Nedenfor vises egenskaber for en stak:

• Det er en ordret liste, hvorindsættelse og sletning kan kun udføres i den ene ende, der kaldes top
• Rekursiv datastruktur med en markør til dets øverste element
• Følger last-in-first-out (LIFO) princip
• Understøtter to mest grundlæggende metoder
  • push (e): Indsæt element e øverst på stakken
  • pop (): Fjern og returner det øverste element på stakken

Praktiske eksempler på stakken inkluderer, når du vender et ord,for at kontrollere rigtigheden af parentesersekvens,implementering af tilbage-funktionalitet i browsere og mange flere.

Køer

er også en anden type abstrakt datastruktur. I modsætning til en stak er køen en samling objekter, der indsættes og fjernes i henhold til first-in-first-out (FIFO) princip. Det vil sige, at elementer kan indsættes når som helst, men kun det element, der har været længst i køen, kan fjernes når som helst.Nedenfor vises egenskaber for en kø:

• Ofte kaldet først ind først ud liste
• Understøtter to mest grundlæggende metoder
  • enqueue (e): Indsæt element e ved bag- af køen
  • dequeue (): Fjern og returner elementet fra foran af køen

Køer bruges iasynkron overførsel af data mellem to processer, CPU-planlægning, Diskplanlægning og andre situationer, hvor ressourcer deles mellem flere brugere og serveres efter først til mølle-serverbasis. Derefter i denne artikel 'Datastrukturer og algoritmer i Java' har vi hierarkiske datastrukturer.

Hierarkiske datastrukturer i Java

Binært træ

Binært træ er enhierarkiske træ datastrukturer, hvor hver knude har højst to børn , der kaldes venstre barn og rigtige barn . Hvert binært træ har følgende grupper af noder:

• Root Node: Det er den øverste knude og ofte omtalt som hovedknudenfordi alle andre noder kan nås fra roden
• Left Sub-Tree, som også er et binært træ
• Right Sub-Tree, som også er et binært træ

Nedenfor er egenskaberne af et binært træ:

• Et binært træ kan krydses på to måder:
  • Dybde første gennemgang : I rækkefølge (venstre-rod-højre), forudbestilling (rod-venstre-højre) og efterbestilling (venstre-højre-rod)
  • Bredde første gennemgang : Gennemgang af niveauordre
• Tidskompleksitet af trægennemgang: O (n)
• Det maksimale antal noder på niveau 'l' = 2^l-1.

Anvendelser af binære træer inkluderer:

• Anvendes i mange søgeapplikationer, hvor data konstant kommer ind / ud
• Som en arbejdsgang til sammensætning af digitale billeder til visuelle effekter
• Anvendes i næsten alle routere med høj båndbredde til opbevaring af routerborde
• Bruges også til trådløst netværk og hukommelsesallokering
• Anvendes i komprimeringsalgoritmer og mange flere

Binær bunke

Binary Heap er en kompletbinært træ, som svarer på bunkeegenskaben. Enkelt sagt deter en variation af et binært træ med følgende egenskaber:

• Heap er et komplet binært træ: Et træ siges at være komplet, hvis alle dets niveauer, undtagen muligvis det dybeste, er komplette. Thans ejendom Binary Heap gør det velegnet til opbevaring i et .
• Følger bunkeejendom: En binær bunke er enten en Min-bunke eller a Max-Heap .
  • Min binær bunke: Feller hver knude i en bunke, knudens værdi er mindre end eller lig med børnenes værdier
  • Maks. Binær bunke: Feller hver node i en bunke, er nodens værdi større end eller lig med børnenes værdier

Populære anvendelser af binær bunke inkludererimplementering af effektive prioritetskøer, effektivt at finde de k mindste (eller største) elementer i en matrix og mange flere.

Hash-borde

Forestil dig, at du har en objekt og du vil tildele en nøgle til den for at gøre søgning meget let. For at gemme dette nøgle / værdipar kan du bruge et simpelt array som en datastruktur, hvor nøgler (heltal) kan bruges direkte som et indeks til at gemme dataværdier. I tilfælde hvor nøglerne er for store og ikke kan bruges direkte som et indeks, anvendes en teknik kaldet hashing.

I hashing konverteres de store nøgler til små nøgler ved hjælp af hash-funktioner . Værdierne gemmes derefter i en datastruktur, der kaldestil hash-bord. En hash-tabel er en datastruktur, der implementerer en ordbog ADT, en struktur, der kan kortlægge unikke nøgler til værdier.

Generelt har en hash-tabel to hovedkomponenter:

1. Bucket Array: En bucket-array til en hash-tabel er en array A i størrelse N, hvor hver celle i A betragtes som en 'bucket', det vil sige en samling nøgleværdipar. Heltallet N definerer arrayets kapacitet.
2. Hash-funktion: Det er en hvilken som helst funktion, der kortlægger hver nøgle k på vores kort til et heltal i området [0, N & minus 1], hvor N er kapaciteten i bucket-arrayet til denne tabel.

Når vi lægger objekter i en hashtable, er det muligt, at forskellige objekter kan have den samme hashcode. Dette kaldes en kollision . For at håndtere kollision er der teknikker som kæde og åben adressering.

Så dette er nogle grundlæggende og hyppigst anvendte datastrukturer i Java. Nu hvor du er opmærksom på hver af disse, kan du begynde at implementere dem i din . Med dette har vi afsluttet den første del af 'denne' Datastrukturer og algoritmer i Java 'artikel. I den næste del skal vi lære omgrundlæggende algoritmer og hvordan man bruger dem i praktiske anvendelser såsom sortering og søgning, opdeling og erobring, grådige algoritmer, dynamisk programmering.

Algoritmer i Java

Historisk anvendt som et værktøj til løsning af komplekse matematiske beregninger, er algoritmer dybt forbundet med datalogi og især med datastrukturer. En algoritme er en sekvens af instruktioner, der beskriver en måde at løse et specifikt problem på i en begrænset periode. De er repræsenteret på to måder:

• Flowcharts - Det er envisuel repræsentation af en algoritmes kontrolflow
• Pseudokode - Deter en tekstlig repræsentation af en algoritme, der tilnærmer sig den endelige kildekode

Bemærk: Algoritmens ydeevne måles ud fra tidskompleksitet og rumkompleksitet. For det meste afhænger kompleksiteten af ​​enhver algoritme af problemet og af selve algoritmen.

Lad os undersøge de to hovedkategorier af algoritmer i Java, som er:

• Sortering af algoritmer i Java
• Søger algoritmer i Java

Sortering af algoritmer i Java

Sorteringsalgoritmer er algoritmer, der placerer elementer på en liste i en bestemt rækkefølge. De mest anvendte ordrer er numerisk rækkefølge og leksikografisk rækkefølge. I denne 'Datastrukturer og algoritmer'-artikel kan vi udforske et par sorteringsalgoritmer.

Boblesortering i Java

Boblesortering, ofte kaldet synkende sortering, er den enkleste sorteringsalgoritme. Det går flere gange gennem listen, der skal sorteres, sammenligner hvert par tilstødende elementer og bytter dem, hvis de er i den forkerte rækkefølge.Boblesortering får sit navn, fordi den filtrerer elementerne ud til toppen af ​​arrayet, som bobler der flyder på vandet.

Her erpseudokode, der repræsenterer boblesorteringsalgoritme (stigende sorteringskontekst).

a [] er en matrix af størrelse N begynder BubbleSort (a []) erklærer heltal i, j for i = 0 til N - 1 for j = 0 til N - i - 1 hvis a [j]> a [j + 1 ] skift derefter en [j], en [j + 1] ende, hvis slut for at returnere en ende BubbleSort

Denne kode ordrer et endimensionelt array af N-dataelementer i stigende rækkefølge. En ydre sløjfe får N-1 til at passere over arrayet. Hvert pas bruger en indre sløjfe til at udveksle dataelementer, så det næste mindste dataelement 'bobler' mod begyndelsen af ​​arrayet. Men problemet er, at algoritmen har brug for en hel pas uden at bytte for at vide, at listen er sorteret.

Kompleksitet i værste og gennemsnitlige tilfælde: O (n * n). Det værste tilfælde opstår, når en matrix er omvendt sorteret.

Bedste sagstidskompleksitet: På). Bedste tilfælde opstår, når en matrix allerede er sorteret.

Valg Sorter i Java

Valgssortering er en kombination af både søgning og sortering. Algoritmen sorterer et array ved gentagne gange at finde minimumselementet (i betragtning af stigende rækkefølge) fra den usorterede del og placere det i en korrekt position i arrayet.

Her er pseudokode, der repræsenterer selektions sorteringsalgoritme (stigende sorteringskontekst).

a [] er en matrix af størrelse N begynder SelectionSort (a []) for i = 0 til n - 1 / * indstil det aktuelle element som minimum * / min = i / * find minimumselementet * / for j = i + 1 til n hvis liste [j]
Som du kan forstå af koden, er antallet af gange, sorteringen passerer gennem arrayet, et mindre end antallet af elementer i arrayet. Den indre sløjfe finder den næste mindste værdi, og den ydre sløjfe placerer den værdi på sin rette placering. Selektionssortering skaber aldrig mere end O (n) swaps og kan være nyttigt, når hukommelseskrivningen er en dyr handling.
 Tidskompleksitet: På2) da der er to indlejrede løkker.
 Hjælpeplads: Eller (1).
 Indsættelse Sorter i Java 
Insertion Sort er en simpel sorteringsalgoritme, som gentages gennem listen ved at forbruge et inputelement ad gangen og bygger det endelige sorterede array. Det er meget simpelt og mere effektivt på mindre datasæt. Det er stabil og på stedet sorteringsteknik.
Her er pseudokode, der repræsenterer Insertion Sort Algorithm (stigende sorteringskontekst).
a [] er en matrix af størrelse N begynder InsertionSort (a []) for i = 1 til N-nøgle = a [i] j = i - 1 mens (j> = 0 og en [j]> -tast 0 a [j + 1] = x [j] j = j - 1 ende, mens en [j + 1] = nøgleende til slut InsertionSort
Som du kan forstå fra koden, indsættelses sorteringsalgoritmenfjerner et element fra inputdataene, finder den placering, det hører til i den sorterede liste og indsætter det der. Det gentages, indtil ingen inputelementer forbliver usorterede.
 Bedste tilfælde: Det bedste tilfælde er, når input er en matrix, der allerede er sorteret. I dette tilfælde har indsættelsessortering en lineær løbetid (dvs. & Theta (n)).
dyb kloning og lav kloning i java
 Værste tilfælde:  Den enkleste worst case input er en matrix sorteret i omvendt rækkefølge.
 QuickSort i Java 
Quicksort-algoritme er en hurtig, rekursiv, ikke-stabil sorteringsalgoritme, der fungerer efter opdelings- og erobringsprincippet. Det vælger et element som pivot og partitionerer det givne array omkring den valgte pivot.
 Trin til implementering Hurtig sortering:  
 
Vælg et passende 'drejepunkt'.
Opdel listerne i to listerbaseret på dette drejelement. Hvert element, der er mindre end pivotelementet, placeres i venstre liste, og hvert element, der er større, placeres på den højre liste. Hvis et element er lig med pivotelementet, kan det gå på en hvilken som helst liste. Dette kaldes partitionsoperationen.
Sorter hver af de mindre lister rekursivt. 
Her er pseudokode, der repræsenterer Quicksort-algoritme.
QuickSort (A som array, lav som int, høj som int) {if (lav
I ovenstående pseudokode, skillevæg() funktion udfører partition og Quicksort () funktion kalder gentagne gange på partitionsfunktion for hver genererede mindre liste. Kompleksiteten af ​​quicksort i gennemsnit er & Theta (n log (n)) og i værste fald er & Theta (n2).
 Flet sortering i Java 
Mergesort er en hurtig, rekursiv, stabil sorteringsalgoritme, som også fungerer efter opdelings- og erobringsprincippet. Svarende til quicksort deler flettsortering listen over elementer i to lister. Disse lister sorteres uafhængigt og kombineres derefter. Under kombinationen af ​​listerne indsættes (eller flettes) elementerne på det rigtige sted på listen.
Her er pseudokode, der repræsenterer flettsorteringsalgoritme.
procedure 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 = fusionssort (l1) l2 = fusionssort (l2) returfletning (l1, l2) slutprocedureprocedure fletning (a som array, b som array) var c som array, mens (a og b har elementer) hvis ( a [0]> b [0]) tilføj b [0] til slutningen af ​​c fjern b [0] fra b ellers tilføj en [0] til slutningen af ​​c fjern a [0] fra en ende, hvis slut, mens mens (a har elementer) tilføj a [0] til slutningen af ​​c fjern a [0] fra en ende, mens (b har elementer) tilføj b [0] til slutningen af ​​c fjern b [0] fra b-ende mens retur c afslut proceduren
 fusionsort () funktion opdeler listen i to, opkald fusionsort () på disse lister separat og derefter kombinere dem ved at sende dem som parametre for at flette () -funktionen.Algoritmen har en kompleksitet af O (n log (n)) og har en bred vifte af applikationer.
 Heap Sort i Java 
Heapsort er en sammenligningsbaseret sorteringsalgoritmeBinær bunke datastruktur. Du kan tænke på det som forbedret version f valgsort, hvorden deler sin input i en sorteret og en usorteret region, og den krymper iterativt den usorterede region ved at udtrække det største element og flytte det til det sorterede område.
 Trin til implementering af Quicksort (i stigende rækkefølge): 
Byg en maksimal bunke med sorteringsarrayet
På dette punktt, den største vare er gemt i roden af ​​bunken. Udskift det med det sidste element i bunken, og reducer størrelsen på bunken med 1. Til sidst skal du heapify træets rod
Gentag ovenstående trin, indtil dyngens størrelse er større end 1
Her er pseudokode, der repræsenterer 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) ende for slut for heapify (a som array, n som int, i som int) største = i // Initialiser størst som root int l eft = 2 * i + 1 // venstre = 2 * i + 1 int højre = 2 * i + 2 // højre = 2 * i + 2 hvis (venstre a [største]) største = venstre hvis (højre a [største]) største = højre hvis (største! = I) swap ( a [i], A [største]) Heapify (a, n, største) ende heapify
Bortset fra disse er der andre sorteringsalgoritmer, som ikke er så kendte, f.eks. Introsort, Counting Sort osv. Når vi går videre til det næste sæt algoritmer i denne artikel om 'Datastrukturer og algoritmer', lad os undersøge søgningsalgoritmer.
 Søger algoritmer i Java 
Søgning er en af ​​de mest almindelige og ofte udførte handlinger i almindelige forretningsapplikationer. Søgealgoritmer er algoritmer til at finde et element med specificerede egenskaber blandt en samling af varer. Lad os udforske to af de mest anvendte søgealgoritmer.
 Lineær søgealgoritme i Java 
Lineær søgning eller sekventiel søgning er den enkleste søgealgoritme. Det involverer sekventiel søgning efter et element i den givne datastruktur, indtil enten elementet findes, eller slutningen af ​​strukturen er nået. Hvis elementet findes, returneres varens placering, ellers returnerer algoritmen NULL.
Her er pseudokode, der repræsenterer lineær søgning i Java:
procedure lineærsøgning (a [], værdi) for i = 0 til n-1, hvis en [i] = værdi skal udskrives 'Fundet' returnere i slutning, hvis udskrivning 'Ikke fundet' ende til slut lineær_søgning
Det er enbrute-force algoritme.Selvom det bestemt er det enkleste, er det bestemt ikke det mest almindelige på grund af dets ineffektivitet. Tidskompleksitet for lineær søgning er PÅ) .
 Binær søgealgoritme i Java 
Binær søgning, også kendt som logaritmisk søgning, er en søgealgoritme, der finder placeringen af ​​en målværdi inden for et allerede sorteret array. Det opdeler inputindsamlingen i lige store halvdele, og varen sammenlignes med det midterste element på listen. Hvis elementet findes, slutter søgningen der. Ellers fortsætter vi med at lede efter elementet ved at opdele og vælge den passende partition af arrayet, baseret på om målelementet er mindre eller større end det midterste element.
Her er pseudokode, der repræsenterer binær søgning i Java:
Procedure binær_søg efter en sorteret matrix n størrelse af matrix x værdi, der skal søges lowerBound = 1 upperBound = n, mens x ikke findes, hvis upperBound
Søgningen afsluttes, når upperBound (vores markør) går forbi lowerBound (sidste element), hvilket betyder, at vi har søgt i hele arrayet, og elementet ikke er til stede.Det er de mest anvendte søgealgoritmer primært på grund af dets hurtige søgetid. Tidskompleksiteten af ​​den binære søgning er PÅ) hvilket er en markant forbedring af PÅ) tidskompleksitet ved lineær søgning.
Dette bringer os til slutningen af ​​denne artikel 'Datastrukturer og algoritmer i Java'. Jeg har dækket et af de mest grundlæggende og vigtige emner i Java.Håber du er klar med alt, hvad der er delt med dig i denne artikel.
  Sørg for at øve så meget som muligt, og vend din oplevelse tilbage.   
 Tjek    af Edureka, et pålideligt online læringsfirma med et netværk på mere end 250.000 tilfredse elever spredt over hele kloden. Vi er her for at hjælpe dig med hvert trin på din rejse, for at blive et udover dette java-interviewspørgsmål, kommer vi med en læseplan, der er designet til studerende og fagfolk, der ønsker at være Java-udvikler. 
 Har du et spørgsmål til os? Nævn det i kommentarfeltet i denne 'Datastrukturer og algoritmer i Java'  artikel, og vi vender tilbage til dig hurtigst muligt.