Vés al contingut

Estructura de dades

De la Viquipèdia, l'enciclopèdia lliure
Una estructura de dades coneguda com a taula hash.

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:

  • Alta, addicionar un nou valor a l'estructura.
  • Baixa, esborrar un valor de l'estructura.
  • Recerca, trobar un determinat valor en l'estructura per a realitzar una operació amb aquest valor, en forma seqüencial o binari (sempre que les dades estiguen ordenats).

Altres operacions que es poden realitzar són:

  • Ordenament, dels elements pertanyents a l'estructura.
  • Aparellament, donades dues estructures originar una nova ordenada i que continga a les apariades.

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.

Ús

[modifica]

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]

Implementació

[modifica]

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]

Suport dels llenguatges de programació

[modifica]

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]

Estructures de dades: exemples

[modifica]
La jerarquia de tipus estàndard del llenguatge de programació Python 3.

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]

  • Una matriu és una sèrie d'elements en un ordre específic, normalment tots del mateix tipus (segons el llenguatge, els elements individuals poden ser forçats a ser del mateix tipus, o poden ser de gairebé qualsevol tipus). S'accedeix als elements mitjançant un índex sencer per especificar quin element és necessari. Les implementacions típiques assignen paraules de memòria contigües per als elements de les matrius (però això no sempre és una necessitat). Les matrius poden ser de longitud fixa o redimensionables.
  • Una llista enllaçada (també anomenada llista) és una col·lecció lineal d'elements de dades de qualsevol tipus, anomenats nodes, on cada node té un valor i apunta al següent node de la llista enllaçada. El principal avantatge d'una llista enllaçada sobre una matriu és que els valors sempre es poden inserir i eliminar de manera eficient sense reubicar la resta de la llista. Algunes altres operacions, com ara l'accés aleatori a un element determinat, són, però, més lentes a les llistes que a les matrius.
  • Un registre (també anomenat tuple o struct) és una estructura de dades agregades . Un registre és un valor que conté altres valors, normalment en nombre i seqüència fixes i normalment indexats per noms. Els elements dels registres solen anomenar-se camps o membres . En el context de la programació orientada a objectes, els registres es coneixen com a estructures de dades antigues per distingir-los dels objectes.[16]
  • Les taules hash, també conegudes com a mapes hash, són estructures de dades que proporcionen una ràpida recuperació de valors basats en claus. Utilitzen una funció hash per assignar claus a índexs d'una matriu, permetent l'accés en temps constant en el cas mitjà. Les taules hash s'utilitzen habitualment en diccionaris, memòria cau i indexació de bases de dades. Tanmateix, es poden produir col·lisions de hash, que poden afectar el seu rendiment. S'utilitzen tècniques com l'encadenament i l'adreçament obert per gestionar les col·lisions.
  • Els gràfics són col·leccions de nodes connectats per arestes, que representen relacions entre entitats. Els gràfics es poden utilitzar per modelar xarxes socials, xarxes informàtiques i xarxes de transport, entre altres coses. Consten de vèrtexs (nodes) i arestes (connexions entre nodes). Els gràfics poden ser dirigits o no, i poden tenir cicles o ser acíclics. Els algorismes de recorregut de gràfics inclouen la cerca en amplitud i la cerca en profunditat.
  • Les piles i les cues són tipus de dades abstractes que es poden implementar mitjançant matrius o llistes enllaçades. Una pila té dues operacions principals: push (afegeix un element a la part superior de la pila) i pop (elimina l'element superior de la pila), que segueixen el principi Last In, First Out (LIFO). Les cues tenen dues operacions principals: posar en cua (afegeix un element a la part posterior de la cua) i treure un element de la part davantera de la cua) que segueixen el principi FIFO (First In, First Out).
  • Els arbres representen una organització jeràrquica dels elements. Un arbre consta de nodes connectats per vores, un node és l'arrel i tots els altres nodes formen subarbres. Els arbres s'utilitzen àmpliament en diversos algorismes i escenaris d'emmagatzematge de dades. Els arbres binaris (especialment els munts ), els arbres AVL i els arbres B són alguns tipus d'arbres populars. Permeten la cerca, l'ordenació i la representació jeràrquica de dades eficients i òptimes.
  • Un trie, també conegut com a arbre de prefix, és una estructura de dades d'arbre especialitzada que s'utilitza per a la recuperació eficient de cadenes. Intenta emmagatzemar caràcters d'una cadena com a nodes, amb cada aresta que representa un caràcter. Són especialment útils en escenaris de processament de text com l'autocompletar, la correcció ortogràfica i les implementacions de diccionari. Els intents permeten la cerca ràpida i les operacions basades en prefixos a les cadenes.

Llistat d'estructures de dades

[modifica]

Referències

[modifica]
  1. ↑ Cormen, Thomas H. Introduction to Algorithms, Third Edition. 3rd. The MIT Press, 2009. ISBN 978-0262033848. 
  2. ↑ Black, Paul E. «data structure». A: Pieterse. Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology, 15 December 2004. 
  3. ↑ , 17 April 2017. 
  4. ↑ Wegner, Peter. Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons, 2003-08-29, p. 507–512. ISBN 978-0470864128. 
  5. ↑ «Abstract Data Types». Virginia Tech - CS3 Data Structures & Algorithms. Arxivat de l'original el 2023-02-10. [Consulta: 15 febrer 2023].
  6. ↑ Gavin Powell. «Chapter 8: Building Fast-Performing Database Models». A: Beginning Database Design. Wrox Publishing, 2006. ISBN 978-0-7645-7490-0. 
  7. ↑ «1.5 Applications of a Hash Table». University of Regina - CS210 Lab: Hash Table. Arxivat de l'original el 2021-04-27. [Consulta: 14 juny 2018].
  8. ↑ «When data is too big to fit into the main memory». Indiana University Bloomington - Data Structures (C343/A594). Arxivat de l'original el 2018-04-10.
  9. ↑ Vaishnavi, Gunjal; Shraddha, Gavane; Yogeshwari, Joshi International Journal of Computer Applications, 183, 11, 21-06-2021, pàg. 47–49. DOI: 10.5120/ijca2021921427.
  10. ↑ , ISBN 978-0-444-82537-7, <https://www.sciencedirect.com/science/article/pii/B9780444825377500188>. Consulta: 12 novembre 2023
  11. ↑ Dubey, R. C.. Advanced biotechnology : For B Sc and M Sc students of biotechnology and other biological sciences.. New Delhi: S Chand, 2014. ISBN 978-81-219-4290-4. OCLC 883695533. 
  12. ↑ «The GNU C Manual». Free Software Foundation. [Consulta: 15 octubre 2014].
  13. ↑ Van Canneyt, Michaël. «Free Pascal: Reference Guide». Free Pascal, 01-09-2017.
  14. ↑ Mark Moir and Nir Shavit. «Concurrent Data Structures». cs.tau.ac.il. Arxivat de l'original el 2011-04-01.
  15. ↑ Seymour, Lipschutz. Data structures. Revised first. New Delhi, India: McGraw Hill Education, 2014. ISBN 9781259029967. OCLC 927793728. 
  16. ↑ Walter E. Brown. «C++ Language Note: POD Types». Fermi National Accelerator Laboratory, 29-09-1999. Arxivat de l'original el 2016-12-03. [Consulta: 6 desembre 2016].

Bibliografia

[modifica]

Enllaços externs

[modifica]
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Estructura de dades
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Estructura_de_dades&oldid=34374582»