Structuri și algoritmi de date de top în Java pe care trebuie să le cunoașteți

Dacă ar trebui să aleg cel mai important subiect în dezvoltarea software-ului, ar fi structurile de date și algoritmii. Vă puteți gândi la acesta ca la instrumentul fundamental disponibil pentru fiecare programator de calculator. În timp ce programăm, folosim structuri de date să stocheze și să organizeze date și algoritmi pentru a manipula datele din aceste structuri. Acest articol conține o revizuire detaliată a tuturor structurilor și algoritmilor de date obișnuiți în pentru a permite cititorilor să devină bine echipați.

Mai jos sunt enumerate subiectele discutate în acest articol:

• Structuri de date în Java
  • Structuri de date liniare
  • Structuri ierarhice de date
• Algoritmi în Java
  • Algoritmi de sortare
  • Căutarea algoritmilor

Structuri de date în Java

O structură de date este un mod de stocare și organizare a datelor într-un computer, astfel încât să poată fi utilizate în mod eficient. Oferă un mijloc de gestionare eficientă a unor cantități mari de date. Iar structurile de date eficiente sunt esențiale pentru proiectarea algoritmilor eficienți.

Înacest articol „Structuri de date și algoritmi în Java”, vom acoperi structuri de date de bază, cum ar fi:

• Structuri de date liniare
  • Listă legată
  • Stive
  • Cozi

• Structuri ierarhice de date
  • Copaci binari
  • Grămezi
  • Hash Tables

Să verificăm fiecare dintre ele.

Structuri de date liniare în Java

Structuri de date liniare în sunt acelea ale căror elemente sunt secvențiale și ordonate într-un fel astfel încât: există doar unul primul element și are doar unul elementul următor , există doar unul ultimul element și are doar unul elementul anterior , în timp ce toate celelalte elemente au un Următorul și a anterior element.

Matrice

Un matrice este o structură de date liniarăreprezentând un grup de elemente similare, accesate prin index. Dimensiunea unei matrice trebuie furnizată înainte de stocarea datelor. Mai jos sunt enumerate proprietățile unui tablou:

• Fiecare element dintr-o matrice are același tip de date și are aceeași dimensiune
• Elementele matricei sunt stocate în locații de memorie alăturate, primul element pornind de la cea mai mică locație de memorie
• Elementele matricei pot fi accesate aleatoriu
• Structura datelor matrice nu este complet dinamică

De exemplu , s-ar putea să ne dorim ca un joc video să țină evidența primelor zece scoruri pentru acel joc. Decât să folosiți zece diferite variabile pentru această sarcină, am putea folosi un singur nume pentru întregul grup și putem folosi numere index pentru a ne referi la scorurile mari din acel grup.

Listă legată

LA este o structură de date liniară cu colecția de noduri multiple, unde eelementul ach stochează propriile date și un pointer către locația elementului următor. Ultima verigă dintr-o listă legată indică nul, indicând sfârșitul lanțului. Un element dintr-o listă legată se numește a nodul . Primul nod se numește cap .Se numește ultimul nod coadă .

Tipuri de liste legate

Listă legată individual (unidirecțională)

Lista dublă legată (bidirecțională)

Listă circulară legată

Iată un exemplu simplu: Imaginați-vă o listă legată ca un lanț de agrafe care sunt legate între ele. Puteți adăuga cu ușurință o altă agrafă în partea de sus sau de jos. Este chiar rapid să introduceți unul în mijloc. Tot ce trebuie să faceți este să deconectați lanțul de la mijloc, să adăugați noua agrafă, apoi să reconectați cealaltă jumătate. O listă legată este similară.

Stive

Grămadă, o structură de date abstractă, este o colecție de obiecte care sunt inserate și eliminate în conformitate cu ultimul intrat primul (LIFO) principiu. Obiectele pot fi inserate într-o stivă în orice moment, dar numai cel mai recent obiect inserat (adică „ultimul”) poate fi eliminat în orice moment.Enumerate mai jos sunt proprietățile unei stive:

• Este o listă ordonată în careinserarea și ștergerea pot fi efectuate numai la un capăt numit top
• Structură de date recursive cu un indicator către elementul său superior
• Urmărește ultimul intrat primul (LIFO) principiu
• Sprijină două dintre cele mai fundamentale metode
  • push (e): Introduceți elementul e, în partea de sus a stivei
  • pop (): Scoateți și returnați elementul de sus de pe stivă

Exemplele practice ale stivei includ atunci când se inversează un cuvânt,pentru a verifica corectitudinea parantezesecvenţă,implementarea funcționalității back în browsere și multe altele.

Cozi

sunt, de asemenea, un alt tip de structură abstractă a datelor. Spre deosebire de o stivă, coada este o colecție de obiecte care sunt inserate și eliminate în conformitate cu first-in-first-out (FIFO) principiu. Adică, elementele pot fi inserate în orice moment al timpului, dar numai elementul care a fost cel mai mult timp în coadă poate fi eliminat în orice moment.Mai jos sunt enumerate proprietățile unei cozi:

salariul dezvoltatorilor Java în India

• Adesea denumit primul-în-primul-ieșit listă
• Sprijină două dintre cele mai fundamentale metode
  • enqueue (e): Introduceți elementul e, la spate a cozii
  • dequeue (): Scoateți și returnați elementul din față a cozii

Cozile sunt utilizate întransfer asincron de date între două procese, programarea procesorului, programarea discurilor și alte situații în care resursele sunt partajate între mai mulți utilizatori și servite pe baza primul venit primul server. În continuare, în acest articol „Structuri de date și algoritmi în Java”, avem structuri de date ierarhizate.

Structuri de date ierarhice în Java

Arborele binar

Arborele binar este unstructuri de date arborescente ierarhice în care fiecare nod are cel mult doi copii , care sunt denumite copil lăsat si copil drept . Fiecare arbore binar are următoarele grupuri de noduri:

• Nodul rădăcină: este cel mai de sus nod și adesea denumit nodul principaldeoarece toate celelalte noduri pot fi atinse de la rădăcină
• Sub-Arborele din stânga, care este și un arbore binar
• Sub-arborele drept, care este și un arbore binar

Mai jos sunt enumerate proprietățile unui arbore binar:

• Un arbore binar poate fi parcurs în două moduri:
  • Adâncimea întâi traversare : În ordine (stânga-rădăcină-dreapta), precomandă (rădăcină-stânga-dreapta) și postordine (stânga-dreapta-rădăcină)
  • Lățimea Primului Traversal : Transversarea ordinii de nivel
• Complexitatea în timp a traversării copacilor: O (n)
• Numărul maxim de noduri la nivelul ‘l’ = 2^l-1.

Aplicațiile arborilor binari includ:

• Folosit în multe aplicații de căutare în care datele intră / ies în mod constant
• Ca flux de lucru pentru compunerea imaginilor digitale pentru efecte vizuale
• Utilizat în aproape fiecare router cu lățime de bandă mare pentru stocarea meselor routerului
• De asemenea, este utilizat în rețelele wireless și în alocarea memoriei
• Folosit în algoritmi de compresie și multe altele

Heap binar

Binary Heap este completcopac binar, care răspunde la proprietatea heap. În termeni simplieste o variație a unui arbore binar cu următoarele proprietăți:

• Heap este un arbore binar complet: Se spune că un copac este complet dacă toate nivelurile sale, cu excepția celor mai profunde, sunt complete. Tproprietatea sa de Binary Heap îl face adecvat pentru a fi stocat într-un .
• Urmărește proprietatea heap: O grămadă binară este fie un Min-Heap sau a Max-Heap .
  • Greutate binară minimă: Fsau fiecare nod dintr-o grămadă, valoarea nodului este mai mic sau egal cu valorile copiilor
  • Heap maxim binar: Fsau fiecare nod dintr-o grămadă, valoarea nodului este mai mare sau egal cu valorile copiilor

Aplicațiile populare ale heap-ului binar includimplementarea cozilor de prioritate eficiente, găsirea eficientă a celor mai mici (sau mai mari) elemente dintr-o matrice și multe altele.

Hash Tables

Imaginați-vă că aveți un obiect și doriți să îi atribuiți o cheie pentru a facilita căutarea. Pentru a stoca acea pereche cheie / valoare, puteți utiliza o matrice simplă, cum ar fi o structură de date, unde cheile (numere întregi) pot fi utilizate direct ca index pentru a stoca valorile datelor. Cu toate acestea, în cazurile în care tastele sunt prea mari și nu pot fi utilizate direct ca index, se folosește o tehnică numită hashing.

În hashing, tastele mari sunt convertite în taste mici folosind funcții hash . Valorile sunt apoi stocate într-o structură de date numităla masa de hash. Un tabel hash este o structură de date care implementează un dicționar ADT, o structură care poate asocia cheile unice la valori.

În general, un tabel hash are două componente majore:

1. Matrice de cupe: O matrice de găleată pentru o tabelă hash este o matrice A de dimensiunea N, unde fiecare celulă din A este considerată o „găleată”, adică o colecție de perechi cheie-valoare. Numărul întreg N definește capacitatea tabloului.
2. Funcția Hash: Este orice funcție care mapează fiecare tastă k din harta noastră la un număr întreg din intervalul [0, N & minus 1], unde N este capacitatea matricei de cupe pentru acest tabel.

Când punem obiecte într-un hashtable, este posibil ca diferite obiecte să aibă același cod hash. Aceasta se numește a coliziune . Pentru a face față coliziunii, există tehnici precum înlănțuirea și adresarea deschisă.

Deci, acestea sunt câteva structuri de date de bază și cele mai frecvent utilizate în Java. Acum, că sunteți conștienți de fiecare dintre acestea, puteți începe să le implementați în . Cu aceasta, am finalizat prima parte a acestui articol „Structuri de date și algoritmi în Java”. În partea următoare, vom învăța desprealgoritmi de bază și modul de utilizare a acestora în aplicații practice, cum ar fi sortarea și căutarea, divizarea și cucerirea, algoritmii lacomi, programarea dinamică.

Algoritmi în Java

Utilizate istoric ca instrument pentru rezolvarea unor calcule matematice complexe, algoritmii sunt profund conectați cu informatica și, în special, cu structurile de date. Un algoritm este o succesiune de instrucțiuni care descrie o modalitate de rezolvare a unei probleme specifice într-o perioadă de timp finită. Ele sunt reprezentate în două moduri:

• Diagramele de flux - Este unreprezentarea vizuală a fluxului de control al unui algoritm
• Pseudo cod - Aceastaeste o reprezentare textuală a unui algoritm care aproximează codul sursă final

Notă: Performanța algoritmului este măsurată pe baza complexității timpului și a complexității spațiului. În cea mai mare parte, complexitatea oricărui algoritm depinde de problemă și de algoritmul în sine.

Să explorăm cele două mari categorii de algoritmi din Java, care sunt:

• Sortarea algoritmilor în Java
• Căutarea algoritmilor în Java

Sortarea algoritmilor în Java

Algoritmii de sortare sunt algoritmi care pun elementele unei liste într-o anumită ordine. Cele mai utilizate ordine sunt ordinea numerică și ordinea lexicografică. În acest articol „Structuri de date și algoritmi”, puteți explora câțiva algoritmi de sortare.

cum se folosește atomul pentru python

Sortare cu bule în Java

Sortarea cu bule, denumită adesea sortare cu scufundare, este cel mai simplu algoritm de sortare. Parcurge în mod repetat lista care urmează a fi sortată, compară fiecare pereche de elemente adiacente și le schimbă dacă sunt în ordinea greșită.Sortarea cu bule își primește numele deoarece filtrează elementele în partea de sus a matricei, precum bule care plutesc pe apă.

Iatăpseudocod care reprezintă algoritmul de sortare a bulelor (context de sortare crescător).

a [] este o matrice de dimensiunea N începe BubbleSort (a []) declară numărul întreg i, j pentru i = 0 la N - 1 pentru j = 0 la N - i - 1 dacă a [j]> a [j + 1 ] apoi schimbați un [j], un [j + 1] end if end pentru returnarea unui sfârșit BubbleSort

Acest cod comandă o matrice unidimensională de N elemente de date în ordine crescătoare. O buclă exterioară face ca N-1 să treacă peste matrice. Fiecare trecere folosește o buclă interioară pentru a face schimb de elemente de date, astfel încât cel mai mic element de date următor să „bulele” spre începutul matricei. Dar problema este că algoritmul are nevoie de o singură trecere fără niciun swap pentru a ști că lista este sortată.

Cea mai proastă și medie complexitate a cazului: O (n * n). Cel mai rău caz apare atunci când o matrice este sortată invers.

Cel mai bun complex timp de caz: Pe). Cel mai bun caz apare atunci când o matrice este deja sortată.

Selecție Sortare în Java

Sortarea selecției este o combinație atât de căutare, cât și de sortare. Algoritmul sortează o matrice găsind în mod repetat elementul minim (luând în considerare ordinea crescătoare) din partea nesortată și plasându-l într-o poziție corectă în matrice.

Iată pseudocodul care reprezintă algoritmul de sortare a selecției (context de sortare crescător).

a [] este o matrice de dimensiunea N begin SelectionSort (a []) pentru i = 0 la n - 1 / * setați elementul curent ca minim * / min = i / * găsiți elementul minim * / pentru j = i + 1 la n dacă lista [j]
După cum puteți înțelege din cod, numărul de ori în care sortarea trece prin matrice este cu unul mai mic decât numărul de articole din matrice. Bucla interioară găsește următoarea cea mai mică valoare, iar bucla exterioară plasează această valoare în locația corectă. Sortarea selecției nu face niciodată mai mult de swap-uri O (n) și poate fi utilă atunci când scrierea în memorie este o operațiune costisitoare.
 Complexitatea timpului: Pe2) deoarece există două bucle imbricate.
 Spațiu auxiliar: Sau (1).
 Inserare Sortare în Java 
Insertion Sort este un algoritm simplu de sortare care iterează prin listă consumând câte un element de intrare pe rând și construiește matricea sortată finală. Este foarte simplu și mai eficient pentru seturi de date mai mici. Este o tehnică de sortare stabilă și în loc.
Iată pseudocodul care reprezintă Algoritmul de sortare a inserției (context de sortare crescător).
a [] este o matrice de dimensiunea N begin InsertionSort (a []) pentru i = 1 la N cheie = a [i] j = i - 1 în timp ce (j> = 0 și a [j]> cheie0 a [j + 1] = x [j] j = j - 1 capăt în timp ce a [j + 1] = capăt cheie pentru capăt InsertionSort
După cum puteți înțelege din cod, algoritmul de sortare a inserțieielimină un element din datele de intrare, găsește locația care îi aparține în lista sortată și îl introduce acolo. Se repetă până când niciun element de intrare nu rămâne nesortat.
 Cel mai bun caz: Cel mai bun caz este atunci când intrarea este o matrice care este deja sortată. În acest caz, sortarea prin inserție are un timp de rulare liniar (adică, & Theta (n)).
 Cel mai rău caz:  Cea mai simplă intrare în cel mai rău caz este o matrice sortată în ordine inversă.
 QuickSort în Java 
Algoritmul Quicksort este un algoritm de sortare rapid, recursiv, nestabil, care funcționează conform principiului divizării și cuceririi. Acesta alege un element ca pivot și partiționează matricea dată în jurul acelui pivot ales.
 Pași pentru implementarea sortării rapide:  
 
Alegeți un „punct de pivot” adecvat.
Împărțiți listele în două listepe baza acestui element pivot. Fiecare element care este mai mic decât elementul pivot este plasat în lista din stânga și fiecare element care este mai mare este plasat în lista din dreapta. Dacă un element este egal cu elementul pivot, atunci acesta poate intra în orice listă. Aceasta se numește operația de partiție.
Sortați recursiv fiecare dintre listele mai mici. 
Iată pseudocodul care reprezintă algoritmul Quicksort.
QuickSort (A ca matrice, scăzut ca int, înalt ca int) {if (scăzut
În pseudocodul de mai sus, partiție () funcția efectuează operația de partiție și Sortare rapida() funcția apelează în mod repetat funcția de partiție pentru fiecare listă mai mică generată. Complexitatea rapidului rapid în cazul mediu este & Theta (n log (n)) și în cel mai rău caz este & Theta (n2).
 Merge Sort in Java 
Mergesort este un algoritm de sortare rapid, recursiv, stabil, care funcționează și după principiul divizării și cuceririi. Similar cu quicksort, sortarea prin îmbinare împarte lista elementelor în două liste. Aceste liste sunt sortate independent și apoi combinate. În timpul combinării listelor, elementele sunt inserate (sau îmbinate) la locul potrivit din listă.
Iată pseudocodul care reprezintă algoritmul Merge Sort.
procedure MergeSort (a as array) if (n == 1) return a var l1 as array = a [0] ... a [n / 2] var l2 as array = a [n / 2 + 1] ... a [n] l1 = mergesort (l1) l2 = mergesort (l2) return merge (l1, l2) end procedure procedure merge (a ca matrice, b ca matrice) var c ca matrice în timp ce (a și b au elemente) dacă ( a [0]> b [0]) adăugați b [0] la sfârșitul lui c eliminați b [0] din b altceva adăugați un [0] la sfârșitul lui c eliminați un [0] dintr-un capăt dacă se termină în timp ce (a are elemente) adăugați un [0] la sfârșitul lui c eliminați un [0] dintr-un capăt în timp ce în timp ce (b are elemente) adăugați b [0] la sfârșitul lui c eliminați b [0] din capătul b în timp ce reveniți c procedura de încheiere
 mergesort () funcția împarte lista în două, apeluri mergesort () pe aceste liste separat și apoi le combină trimițându-le ca parametri pentru funcția merge ().Algoritmul are o complexitate de O (n log (n)) și are o gamă largă de aplicații.
 Sortare în grămadă în Java 
Heapsort este un algoritm de sortare bazat pe comparațieStructură de date Binary Heap. Vă puteți gândi la aceasta ca la o versiune îmbunătățită pentru sortarea selecției, undeîși împarte intrarea într-o regiune sortată și o regiune nesortată și micșorează iterativ regiunea nesortată extragând cel mai mare element și mutându-l în regiunea sortată.
 Pași pentru implementarea Quicksort (în ordine crescătoare): 
Construiți un heap maxim cu matricea de sortare
La acest punctt, cel mai mare articol este stocat la rădăcina heap-ului. Înlocuiți-l cu ultimul element al heap-ului și reduceți dimensiunea heap-ului cu 1. În cele din urmă, heapify rădăcina arborelui
Repetați pașii de mai sus până când dimensiunea heap-ului este mai mare de 1
Iată pseudocodul care reprezintă algoritmul Heap Sort.
Heapsort (a ca matrice) pentru (i = n / 2 - 1) la i> = 0 heapify (a, n, i) pentru i = n-1 la 0 swap (a [0], a [i]) heapify (a, i, 0) end for end for heapify (a as array, n as int, i as int) largest = i // Inițializați cea mai mare ca rădăcină int l eft = 2 * i + 1 // left = 2 * i + 1 int dreapta = 2 * i + 2 // dreapta = 2 * i + 2 if (stânga a [cea mai mare]) cea mai mare = stânga dacă (dreapta a [cea mai mare]) cea mai mare = dreapta dacă (cea mai mare! = I) swap ( a [i], A [cel mai mare]) Heapify (a, n, cel mai mare) sfârșit heapify
În afară de acestea, există și alți algoritmi de sortare care nu sunt atât de cunoscuți, cum ar fi, Introsort, Counting Sort, etc. Trecând la următorul set de algoritmi din acest articol „Structuri de date și algoritmi”, să explorăm algoritmi de căutare.
 Căutarea algoritmilor în Java 
Căutarea este una dintre acțiunile cele mai frecvente și frecvent efectuate în aplicațiile obișnuite de afaceri. Algoritmii de căutare sunt algoritmi pentru găsirea unui articol cu ​​proprietăți specificate într-o colecție de articole. Să explorăm doi dintre cei mai utilizați algoritmi de căutare.
 Algoritm de căutare liniară în Java 
Căutarea liniară sau căutarea secvențială este cel mai simplu algoritm de căutare. Aceasta implică căutarea secvențială a unui element în structura de date dată până când elementul este găsit sau se ajunge la sfârșitul structurii. Dacă elementul este găsit, atunci locația elementului este returnată altfel algoritmul returnează NULL.
Iată pseudocodul care reprezintă căutarea liniară în Java:
procedure linear_search (a [], value) for i = 0 to n-1 if a [i] = value then print 'Found' return i end if print 'Not found' end for end linear_search
Este unalgoritm de forță brută.Deși este cu siguranță cel mai simplu, cu siguranță nu este cel mai comun, datorită ineficienței sale. Complexitatea în timp a căutării liniare este PE) .
 Algoritm de căutare binară în Java 
Căutarea binară, cunoscută și sub numele de căutare logaritmică, este un algoritm de căutare care găsește poziția unei valori țintă într-o matrice deja sortată. Împarte colecția de intrare în jumătăți egale și elementul este comparat cu elementul de mijloc al listei. Dacă elementul este găsit, căutarea se termină acolo. Altfel, continuăm să căutăm elementul împărțind și selectând partiția corespunzătoare a matricei, în funcție de dacă elementul țintă este mai mic sau mai mare decât elementul din mijloc.
Iată pseudocodul care reprezintă Binary Search în Java:
Procedură binary_search o matrice sortată n dimensiune a matricei x valoare care trebuie căutată lowerBound = 1 upperBound = n în timp ce x nu se găsește dacă upperBound
Căutarea se termină atunci când upperBound (indicatorul nostru) trece de lowerBound (ultimul element), ceea ce înseamnă că am căutat întreaga matrice și elementul nu este prezent.Este cel mai frecvent utilizat algoritm de căutare, în principal datorită timpului său rapid de căutare. Complexitatea în timp a căutării binare este PE) ceea ce reprezintă o îmbunătățire marcată a PE) complexitatea în timp a Căutării Liniare.
seria Fibonacci c ++
Acest lucru ne aduce la sfârșitul acestui articol „Structuri de date și algoritmi în Java”. Am acoperit unul dintre cele mai importante și importante subiecte Java.Sper că ești clar cu tot ce ți-a fost împărtășit în acest articol.
  Asigurați-vă că exersați cât mai mult posibil și reveniți la experiență.   
 Verificați    de Edureka, o companie de învățare online de încredere, cu o rețea de peste 250.000 de elevi mulțumiți răspândiți pe tot globul. Suntem aici pentru a vă ajuta cu fiecare pas din călătoria dvs., pentru a deveni o afară de întrebările de interviuri java, venim cu un curriculum care este conceput pentru studenți și profesioniști care doresc să fie un dezvoltator Java. 
 Ai o întrebare pentru noi? Vă rugăm să o menționați în secțiunea de comentarii a acestui „Structuri de date și algoritmi în Java”  articol și vă vom răspunde cât mai curând posibil.