From Wikipedia, the free encyclopedia
En programació, una estructura de dades és una forma d'organitzar un conjunt de dades elementals amb l'objectiu de facilitar la seva manipulació, i per aconseguir un accés eficient a les dades que conté.[1][2][3] De forma més precisa, una estructura de dades és una col·lecció de valors de dades, les relacions entre elles i les funcions o operacions que es poden aplicar a aquestes dades,[4] és a dir, és una estructura algebraica sobre dades.
Una dada elemental és la mínima informació que es té en un sistema, i una estructura de dades defineix l'organització i interrelació d'aquests i un conjunt d'operacions que es poden realitzar sobre ells. Les operacions bàsiques són:
Altres operacions que es poden realitzar són:
Cada estructura ofereix avantatges i desavantatges en relació a la simplicitat i eficiència per a la realització de cada operació. D'aquesta forma, l'elecció de l'estructura de dades apropiada per a cada problema depèn de factors com la freqüència i l'ordre que es realitza cada operació sobre les dades.
Les estructures de dades serveixen de base per als tipus de dades abstractes (ADT, de l'anglès abstract data types). L'ADT defineix la forma lògica del tipus de dades. L'estructura de dades implementa la forma física del tipus de dades.[5]
Els diferents tipus d'estructures de dades s'adapten a diferents tipus d'aplicacions, i algunes estan altament especialitzades per a tasques específiques. Per exemple, les bases de dades relacionals utilitzen habitualment índexs d'arbre B per a la recuperació de dades,[6] mentre que les implementacions del compilador solen utilitzar taules hash per buscar identificadors.[7]
Les estructures de dades proporcionen un mitjà per gestionar grans quantitats de dades de manera eficient per a usos com grans bases de dades i serveis d'indexació d'Internet. Normalment, les estructures de dades eficients són clau per dissenyar algorismes eficients. Alguns mètodes de disseny formals i llenguatges de programació emfatitzen les estructures de dades, més que els algorismes, com el factor organitzador clau en el disseny de programari. Les estructures de dades es poden utilitzar per organitzar l'emmagatzematge i la recuperació de la informació emmagatzemada tant a la memòria principal com a la memòria secundària.[8]
Les estructures de dades es poden implementar mitjançant una gran varietat de llenguatges i tècniques de programació, però totes comparteixen l'objectiu comú d'organitzar i emmagatzemar dades de la manera més eficient possible.[9] Les estructures de dades es basen generalment en la capacitat d'un ordinador per obtenir i emmagatzemar dades en qualsevol lloc de la seva memòria, especificada per un punter: una cadena de bits, que representa una adreça de memòria, que pot ser emmagatzemada a la memòria i manipulada pel programa. Així, les estructures de dades de vector o matriu i registre es basen a calcular les adreces dels elements de dades amb operacions aritmètiques, mentre que les estructures de dades enllaçades es basen a emmagatzemar adreces d'elements de dades dins de la pròpia estructura. Aquest enfocament de l'estructuració de dades té implicacions profundes per a l'eficiència i escalabilitat dels algorismes. Per exemple, l'assignació de memòria contigua en matrius facilita l'accés ràpid i les operacions de modificació, donant lloc a un rendiment optimitzat en escenaris de processament de dades seqüencials.[10]
La implementació d'una estructura de dades normalment requereix escriure un conjunt de procediments que creïn i manipulin instàncies d'aquesta estructura. L'eficiència d'una estructura de dades no es pot analitzar per separat d'aquestes operacions. Aquesta observació motiva el concepte teòric d'un tipus de dades abstracte, una estructura de dades que es defineix indirectament per les operacions que s'hi poden realitzar i les propietats matemàtiques d'aquestes operacions (incloent-hi el seu cost d'espai i de temps).[11]
La majoria dels llenguatges assemblador i alguns llenguatges de baix nivell, com ara el BCPL (Llenguatge de programació combinat bàsic, de l'anglès: Basic Combined Programming Language), no tenen suport integrat per a les estructures de dades. D'altra banda, molts llenguatges de programació d'alt nivell i alguns llenguatges d'assemblador de nivell superior, com MASM, tenen una sintaxi especial o un altre suport integrat per a determinades estructures de dades, com ara registres i matrius. Per exemple, els llenguatges C (un descendent directe de BCPL) i Pascal admeten estructures i registres, respectivament, a més de vectors (matrius unidimensionals) i matrius multidimensionals.[12][13]
La majoria dels llenguatges de programació inclouen algun tipus de mecanisme de biblioteca que permet que les implementacions d'estructura de dades siguin reutilitzades per diferents programes. Els llenguatges moderns solen venir amb biblioteques estàndard que implementen les estructures de dades més comunes. Alguns exemples són la biblioteca de plantilles estàndard de C++, el marc de col·leccions de Java i el Microsoft .NET Framework .
Els llenguatges moderns també admeten generalment la programació modular, la separació entre la interfície d'un mòdul de biblioteca i la seva implementació. Alguns proporcionen tipus de dades opacs que permeten als clients amagar els detalls d'implementació. Els llenguatges de programació orientats a objectes, com ara C++, Java i Smalltalk, solen utilitzar classes per a aquest propòsit.
Moltes estructures de dades conegudes tenen versions concurrents que permeten que diversos fils informàtics accedeixin a una única instància concreta d'una estructura de dades simultàniament.[14]
Hi ha nombrosos tipus d'estructures de dades, generalment construïdes sobre tipus de dades primitives més simples. Alguns exemples coneguts són: [15]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
