Structură de date

De la Wikipedia, enciclopedia liberă

Un arbore binar este un tip simplu de structură de date.

În informatică, o structură de date este o metodă de stocare a informaţiilor într-un calculator în aşa fel încât ele să poată fi folosite în mod eficient. Deseori o alegere bine făcută a structurii de date va permite şi implementarea unui algoritm eficient. Structura de date aleasă este derivată de multe ori dintr-un tip de dată abstract. O structură de date bine concepută permite efectuarea unei varietăţi de operaţii de bază, utilizând puţine resurse (ca de exemplu memoria necesară şi timpul de execuţie). Structurile de date se implementează utilizând tipuri de date, referinţe şi operaţii asupra acestora, toate facilitate de către un limbaj de programare.

Există tipuri de structuri de date care sunt foarte specializate pe anumite sarcini/aplicaţii. De exemplu, în special arborii B sunt foarte potriviţi pentru implementarea bazelor de date, în timp ce tabelele de rutare se folosesc îndeosebi pentru interconectarea elementelor din reţelele de calculatoare.

În designul multor tipuri de programe, alegerea structurii de date este principalul obiectiv al specificaţiilor de implementare. Experienţa în construirea sistemelor informatice mari a arătat că dificultatea implementării, precum şi calitatea şi performanţa produsului final depind în mare măsură de alegerea structurilor de date. După ce au fost alese tipurile de structui de date, algoritmii ce vor trebui utilizaţi devin de multe ori aproape evidenţi. Câteodată însă situaţia este mai complicată; atunci structurile de date sunt alese pe baza necesităţilor sarcinilor cheie.

Pentru multe metode formale de design şi limbaje de programare factorul organizatoric cheie sunt structurile de date, şi nu algoritmii. Majoritatea limbajelor dispun de un modul sistem anume, care permite reutilizarea structurilor de date şi pentru alte aplicaţii, prin ascunderea detaliilor de implementare, sigure şi verificate, în spatele unor interfeţe controlate. Limbajele de programare orientate pe obiecte cum ar fi C++ şi Java, de exemplu, utilizează în acest scop aşa-numitele clase.

Din cauză că structurile de date au o importanţă atât de mare, multe dintre ele sunt incluse în bibliotecile standard ale multor limbaje de programare şi medii de dezvoltare, cum ar fi Standard Template Library pentru C++, şi Java Collections Framework.

Elementele fundamentale pentru construirea structurilor de date sunt vectorii, înregistrările, structurile de tip union, şi referinţele. De exemplu, referinţa invalidabilă, o referinţă ce poate conţine valoarea null (zero), este o combinaţie de referinţe şi structuri de tip "uniune", iar cel mai simplu model de structură de date înlănţuite, lista simplu înlănţuită, este construită din înregistrări şi referinţe invalidabile.

Structurile de date reprezintă implementări ale unor interfeţe: o structură de date poate fi văzută ca o interfaţă între două funcţii sau ca o implementare a metodelor de accesare a depozitului care este organizat în concordanţă cu tipul de dată asociat.