În postarea mea anterioară, am discutat despre ce sunt „algoritmii” pe scurt. Acum, putem vorbi despre ce sunt structurile de date, cum se leagă acestea cu algoritmi și să obținem o scurtă prezentare a diferitelor structuri de date pe care le veți întâlni.

O structură de date preia date și le organizează, le gestionează sau le stochează într-un format astfel încât să poată fi accesate și modificate cu ușurință. Efectuarea unor operațiuni specifice include accesarea, modificarea sau chiar ștergerea datelor respective.

Deci, mai jos este o definiție foarte simplă a structurilor de date și a algoritmilor și modul în care acestea sunt legate între ele:

  • Ostructură de date se referă la organizarea și gestionarea eficientă a datelor, astfel încât să putem efectua operațiuni specifice în mod eficient. Unalgoritm este o procedură pas cu pas care trebuie urmată pentru a ajunge la rezultatul dorit.
  • Pașii algoritmului folosesc una sau mai multe structuri de date pentru a rezolva o problemă.

Grozav, acum că avem o înțelegere de bază a celor două elemente diferite, dar înrudite, mai jos este o listă de structuri de date comune pe care le veți întâlni pentru a aborda acești algoritmi atât de distractive!

În primul rând, să înțelegem că există diferite tipuri de structuri de date care sunt potrivite pentru diferite tipuri de aplicații și sunt clasificate în linii mari ca date liniare și neliniare.

Structura de date liniarăa are elemente de date aranjate secvenţial și fiecare element membru este conectat la elementul său anterior și următor. Parcurgerea unei structuri de date sau iterarea peste structura de date, ceea ce înseamnă „vizitarea” sau „atingerea” fiecărui element al structurii, este secvențială. Aceste structuri de date sunt ușor de implementat deoarece memoria computerului este, de asemenea, secvențială. Exemple de structuri de date liniare sunt tablourile, lista legată, stiva și coada.

Structurile Date neliniare nu sunt aranjate secvenţial sau liniar. Fiecare element poate avea mai multe căi pentru a se conecta la alte elemente. Nu puteți repeta sau traversa toate elementele într-o singură rulare. Structurile de date neliniare nu sunt ușor de implementat, dar sunt mai eficiente în utilizarea memoriei computerului. Exemple de structuri de date neliniare includ arbori și grafice.

Să explorăm pe scurt diferitele structuri de date:

Matrice

  • O matrice este cel mai simplu tip de structură de date care conține elemente de același tip de date (întreg, float, șir etc.)
  • Este un tip de date liniar
  • Datele stocate în fiecare poziție a unui tablou primesc o valoare pozitivă numită index.
  • Valoarea indexului începe cu 0 pentru primul element dintr-o matrice.

Să presupunem că avem prețurile pentru 6 elemente de băcănie și poziția lor de index. Putem stoca toate numerele întregi într-o matrice.

Acest tablou poate fi scris ca atare:

const arr = [10, 5, 23, 8, 12, 7]

Lista conectată

  • O listă legată este un tip de structură de date constând din noduri și fiecare nod „știe” adresa următorului nod. Un bun exemplu în acest sens ar fi conectarea punctelor pentru a crea o imagine. Știți să legați punctele pentru că sunt numerotate.
  • O listă legată este o colecție secvențială de elemente. Elementul este stocat sub formă de noduri care constau din două informații cheie - valoarea datelor în sine și un pointer / next care face referire la următorul nod din listă.
  • Datele stocate într-o listă legată pot fi de orice formă, șiruri, numere sau caractere.
  • Listele legate nu sunt grozave pentru a obține acces direct la un element precum o matrice, dar sunt cu adevărat eficiente pentru inserarea și ștergerea elementelor din cauza modului în care elementele lor sunt stocate în memorie.
  • Există două tipuri de liste legate — olistă legată individualîn care fiecare nod are un indicator către următorul nod din listă. Există, de asemenea, listă dublu legată în care fiecare nod are un pointer către următorul nod și un al doilea pointer al nodului anterior.

Principalele proprietăți ale structurii de date a unei liste legate sunt:
- dimensiunea: numărul de elemente din lista legată
- head: primul element din lista legată
- coada: ultimul element în lista legată

  • Primul nod (conținând 2) se numește Head Node deoarece nu există niciun nod care să indice el.
  • Nodul 2 stochează adresa nodului care conține 4 și așa mai departe.
  • Nodul de coadă indică null, ceea ce indică sfârșitul listei.

Unele aplicații practice ale listei legate includ:

  • Imaginile sunt legate între ele, astfel încât un software de imagine utilizează o listă legată pentru a vizualiza imaginile anterioare și următoare.
  • Playerele muzicale folosesc, de asemenea, o listă conexă pentru a comuta între muzică și adesea este folosită o listă conexă circulară.

Dacă doriți să vă aprofundați mai mult în listele legate, consultați aceste resurse grozave:

NoobCoder — Lista legată în JavaScript pentru începători
Beiatrix — Liste legate | Structuri de date în JavaScript

Tabel Hash

  • Structură de date care vă permite să creați o listă de perechi cheie-valoare. Apoi, puteți prelua o anumită valoare utilizând cheia pentru acea valoare.
  • Tabelul hash este o structură de date care utilizează hashing pentru a implementa matrice asociative sau mapări ale perechilor valori cheie
  • O funcție hash sau hashing preia un șir, îl convertește într-un fel de număr întreg sau într-un șir de litere și numere și apoi remapează acel număr întreg într-un index.
  • Un tabel hash începe cu mai multe substituenți numite găleți care vor păstra conținut. Pentru a adăuga orice pereche de valori cheie la tabelul hash, luați o cheie și o treceți prin funcția hash care scoate un număr care corespunde unui index într-o matrice în care vom stoca valoarea

Dacă doriți mai multe informații despre tabelele hash. Resursa de mai jos aprofundează subiectul:

„ComputerScience — Tabele Hash și funcții Hash”

Stiva

  • O stivă este o structură de date care ajută la organizarea datelor într-o anumită ordine și urmează principiul „ultimul intrat, primul ieșit” (LIFO). Aceasta înseamnă că ultimul element introdus în stiva este primul care trebuie eliminat.
  • Gândiți-vă la teanc ca la o grămadă de cărți în care puteți lua doar elementul de sus din teanc pentru a elimina cărțile din el și puteți adăuga o carte nouă doar în partea de sus. Acest tip de accesare a datelor se numește „ultimul intrat, primul ieșit”.

Coadă

  • O structură de date liniară care urmează principiul „primul intrat, primul ieşit” (FIFO). Elementul introdus primul este primul care trebuie îndepărtat.
  • Exemple comune de coadă sunt rândurile de oameni care așteaptă un serviciu sau să recupereze ceva. Prima persoană din rând este servită prima, în timp ce persoana care este ultima pe linie este servită ultima.

Grafic

  • O structură de date neliniară care constă dintr-un set finit de vârfuri (sau noduri) și un set de muchii care conectează o pereche de noduri
  • Graficele sunt folosite pentru a reprezenta rețele, cum ar fi căile dintr-un oraș sau o rețea de telefonie. Ele sunt folosite și în rețelele sociale Facebook și LinkedIn.

  • În diagrama de mai sus:
    Varfuri = {A, B, C, D, E}
    Muchii = {AB, BE, ED, DC, CA, AD, BD}

Copac

  • O structură de date ierarhică neliniară care constă din noduri conectate prin muchii. Fiecare nod conține o valoare sau date și poate avea sau nu un copil de nod.
  • Exemple de organizare ierarhică este un arbore genealogic, în HTML - Document Object Model (DOM) funcționează ca un arbore.

Acolo aveți o prezentare generală de bază a diferitelor tipuri de structuri de date pe care le puteți utiliza în algoritmii dvs. pentru a rezolva diverse probleme! În continuare, vom aborda complexitatea timpului și spațiului.