Structură de date

Structuri de date de bază

Array

Cel mai simplu tip de structură de date este o matrice liniară. Cunoscută și sub denumirea de matrice unidimensională. Un array conține mai multe valori de același tip (Integer, Floats, String, etc.). Accesarea elementelor din cadrul unui array este foarte rapidă. În mod normal, un array are o dimensiune fixă. După ce dimensiunea tabloului este definită la început, este posibil să nu fie posibilă creșterea dimensiunii tabloului fără a crea un nou tablou mai mare și a copia toate valorile în noul tablou. În informatică, o structură de date de tip array sau, pur și simplu, un array este o structură de date care constă într-o colecție de elemente (valori sau variabile), fiecare dintre acestea fiind identificat prin cel puțin un index sau o cheie de array. Un array este stocat astfel încât poziția fiecărui element să poată fi calculată printr-o formulă matematică din tupla de indici a acestuia.

De exemplu, o matrice de 10 variabile întregi, cu indicii de la 0 la 9, poate fi stocată sub forma a 10 cuvinte la adresele de memorie 2000, 2004, 2008, 2036, astfel încât elementul cu indicele i să aibă adresa 2000 + 4 × i.

Deoarece conceptul matematic al unei matrice poate fi reprezentat ca o grilă bidimensională, matricele bidimensionale sunt uneori numite și matrice. În unele cazuri, termenul "vector" este utilizat în informatică pentru a se referi la o matrice, deși echivalentul matematic mai corect este reprezentat de tuple și nu de vectori. Tabelele sunt adesea folosite pentru a implementa tabele, în special tabele de căutare; cuvântul tabel este uneori folosit ca sinonim al cuvântului matrice.

Array-urile se numără printre cele mai vechi și mai importante structuri de date și sunt utilizate în aproape toate programele. De asemenea, acestea pot fi utilizate pentru a implementa multe alte structuri de date, cum ar fi listele și șirurile de caractere. Ele exploatează în mod eficient logica de adresare a computerelor. În majoritatea computerelor moderne și în multe dispozitive de stocare externă, memoria este o matrice unidimensională de cuvinte, ai căror indici sunt adresele acestora. Procesoarele, în special procesoarele vectoriale, sunt adesea optimizate pentru operațiile cu matrice.

Array-urile sunt utile deoarece indicii elementelor pot fi calculați în timpul execuției. Printre altele, această caracteristică permite ca o singură instrucțiune iterativă să proceseze un număr arbitrar de elemente ale unui array. Din acest motiv, se cere ca elementele unei structuri de date de tip array să aibă aceeași dimensiune și să utilizeze aceeași reprezentare a datelor. Setul de tușe de indici validați și adresele elementelor (și, prin urmare, formula de adresare a elementelor) sunt de obicei, dar nu întotdeauna, fixate în timp ce matricea este utilizată.

Termenul array este adesea utilizat pentru a desemna tipul de date array, un tip de tip de date oferit de majoritatea limbajelor de programare de nivel înalt, care constă într-o colecție de valori sau variabile care pot fi selectate prin unul sau mai mulți indici calculați în timpul execuției. Tipurile de matrice sunt adesea implementate prin structuri de matrice; cu toate acestea, în unele limbaje, ele pot fi implementate prin tabele hash, liste legate, arbori de căutare sau alte structuri de date.

Listă legată

O structură de date legate este un set de informații/date legate între ele prin referințe. Datele sunt adesea numite noduri. Referințele sunt adesea numite legături sau pointeri. De aici încolo, cuvintele nod și pointer vor fi folosite pentru aceste concepte.

În structurile de date legate, pointerii sunt doar dereferențiați sau comparați pentru egalitate. Astfel, structurile de date legate sunt diferite de array-uri, care necesită adăugarea și scăderea indicatorilor.

Listele legate, arborii de căutare și arborii de expresie sunt toate structuri de date legate. Acestea sunt, de asemenea, importante în algoritmi precum sortarea topologică și găsirea uniunii de seturi.

Stivă

O stivă este o structură de date de bază care poate fi gândită logic ca o structură liniară reprezentată de o stivă fizică reală sau de o grămadă, o structură în care inserarea și ștergerea elementelor are loc la un capăt numit partea superioară a stivei. Conceptul de bază poate fi ilustrat gândindu-vă la setul dumneavoastră de date ca la o stivă de farfurii sau cărți, în care puteți lua doar elementul de sus din stivă pentru a elimina lucruri din ea. Această structură este utilizată în întreaga programare.

Implementarea de bază a unei stive se mai numește și structura "Last In First Out"; cu toate acestea, există diferite variante de implementare a stivei.

În principiu, există trei operații care pot fi efectuate pe stive. Acestea sunt:

• inserarea ("împingerea") unui element într-o stivă
• ștergerea ("popping") unui element din stivă
• afișarea conținutului elementului superior al stivei ("peeking")

Coadă de așteptare

O coadă de așteptare este un tip de date abstract sau o structură de date liniară, în care primul element este introdus de la un capăt (coada), iar ștergerea unui element existent are loc de la celălalt capăt (capul). O coadă de așteptare este o structură de tip "primul intrat, primul ieșit". "First In First Out" înseamnă că elementele introduse primele în coadă vor ieși primele, iar elementele introduse ultimele vor ieși ultimele. Un exemplu de coadă sunt cozile de oameni care așteaptă. Prima persoană din coadă iese prima, iar ultima persoană din coadă iese ultima.

Procesul de adăugare a unui element la o coadă se numește "enqueuing", iar procesul de eliminare a unui element dintr-o coadă se numește "dequeuing".

Grafic

Un graf este un tip de date abstracte care este destinat să implementeze conceptele de graf și hipergraf din matematică.

O structură de date grafice constă într-un set finit (și eventual mutabil) de perechi ordonate, numite muchii sau arce, de anumite entități numite noduri sau vârfuri. La fel ca în matematică, se spune că o muchie (x,y) indică sau merge de la x la y. Nodurile pot face parte din structura grafului sau pot fi entități externe reprezentate prin indici sau referințe de numere întregi. O structură de date grafice poate, de asemenea, să asocieze fiecărei muchii o anumită valoare, cum ar fi o etichetă simbolică sau un atribut numeric.

Copac

Arborele este una dintre cele mai puternice structuri de date avansate. Apare adesea în subiecte avansate, cum ar fi inteligența artificială (AI) și designul. În mod surprinzător, arborele este important într-o aplicație mult mai elementară - păstrarea unui index eficient.

Atunci când se utilizează un arbore, există o mare probabilitate să se utilizeze un index. Cel mai simplu tip de index este o listă ordonată de câmpuri cheie. În mod normal, un arbore are o structură definită. În cazul unui arbore binar, puteți utiliza o căutare binară pentru a localiza orice element fără a fi nevoie să vă uitați la fiecare element.

Tipul de date arbore este un tip de graf, ceea ce înseamnă că mulți algoritmi creați pentru a traversa un graf funcționează și cu un arbore, însă algoritmii pot fi foarte asemănători și trebuie să aibă un nod de pornire dedicat, adică nodul care nu are alte noduri care să facă legătura cu el.

Problema cu o listă ordonată simplă apare atunci când începeți să adăugați elemente noi și trebuie să păstrați lista ordonată - acest lucru poate fi realizat în mod rezonabil de eficient, dar necesită unele modificări. În plus, un index liniar nu este ușor de partajat, deoarece întregul index trebuie "blocat" atunci când un utilizator îl editează, în timp ce o "ramură" a unui arbore poate fi blocată, lăsând celelalte ramuri editabile de către alți utilizatori (deoarece nu pot fi afectate).

Tabel Hash

Un tabel hash este o matrice în care fiecare index indică o listă legată pe baza unei valori hash. O valoare hash este o valoare determinată de o funcție hash. O funcție hash determină o valoare unică pe baza datelor pe care le stochează. Acest lucru permite accesul la date în timp constant, deoarece calculatorul știe întotdeauna unde să caute.

Fiecare nod indică un alt nod.