stringtranslate.com

Estructura de datos

Una estructura de datos conocida como tabla hash .

En informática , una estructura de datos es un formato de organización y almacenamiento de datos que generalmente se elige para un acceso eficiente a los datos. [1] [2] [3] Más precisamente, una estructura de datos es una colección de valores de datos, las relaciones entre ellos y las funciones u operaciones que se pueden aplicar a los datos, [4] es decir, es una estructura algebraica sobre datos .

Uso

Las estructuras de datos sirven como base para los tipos de datos abstractos (ADT). El ADT define la forma lógica del tipo de datos. La estructura de datos implementa la forma física del tipo de datos . [5]

Los distintos tipos de estructuras de datos son adecuados para distintos tipos de aplicaciones y algunas están altamente especializadas para tareas específicas. Por ejemplo, las bases de datos relacionales suelen utilizar índices de árbol B para la recuperación de datos, [6] mientras que las implementaciones de compiladores suelen utilizar tablas hash para buscar identificadores . [7]

Las estructuras de datos proporcionan un medio para gestionar grandes cantidades de datos de manera eficiente para usos tales como bases de datos de gran tamaño y servicios de indexación de Internet. Por lo general, las estructuras de datos eficientes son clave para diseñar algoritmos eficientes . Algunos métodos de diseño formal y lenguajes de programación enfatizan las estructuras de datos, en lugar de los algoritmos, como el factor organizador clave en el diseño de software. Las estructuras de datos se pueden utilizar para organizar el almacenamiento y la recuperación de información almacenada tanto en la memoria principal como en la memoria secundaria . [8]

Implementación

Las estructuras de datos se pueden implementar utilizando una variedad de lenguajes y técnicas de programación, pero todas comparten el objetivo común de organizar y almacenar datos de manera eficiente. [9] Las estructuras de datos generalmente se basan en la capacidad de una computadora para buscar y almacenar datos en cualquier lugar de su memoria, especificado por un puntero ( una cadena de bits que representa una dirección de memoria , que puede almacenarse en la memoria y manipularse mediante el programa). Por lo tanto, las estructuras de datos de matriz y registro se basan en el cálculo de las direcciones de los elementos de datos con operaciones aritméticas , mientras que las estructuras de datos vinculadas se basan en el almacenamiento de direcciones de elementos de datos dentro de la propia estructura. Este enfoque de la estructuración de datos tiene profundas implicaciones para la eficiencia y la escalabilidad de los algoritmos. Por ejemplo, la asignación de memoria contigua en matrices facilita el acceso rápido y las operaciones de modificación, lo que conduce a un rendimiento optimizado en escenarios de procesamiento de datos secuenciales. [10]

La implementación de una estructura de datos generalmente requiere escribir un conjunto de procedimientos que crean y manipulan instancias de esa estructura. La eficiencia de una estructura de datos no se puede analizar por separado de esas operaciones. Esta observación motiva el concepto teórico de un tipo de datos abstracto , una estructura de datos que se define indirectamente por las operaciones que se pueden realizar en ella y las propiedades matemáticas de esas operaciones (incluido su costo espacial y temporal). [11]

Ejemplos

La jerarquía de tipos estándar del lenguaje de programación Python 3 .

Existen numerosos tipos de estructuras de datos, generalmente construidas a partir de tipos de datos primitivos más simples . Algunos ejemplos conocidos son: [12]

Un trie , o árbol de prefijos, es un tipo especial de árbol que se utiliza para recuperar cadenas de manera eficiente. En un trie, cada nodo representa un carácter de una cadena y los bordes entre los nodos representan los caracteres que los conectan. Esta estructura es especialmente útil para tareas como autocompletar, revisar la ortografía y crear diccionarios. Los tries permiten realizar búsquedas y operaciones rápidas basadas en prefijos de cadenas.

Soporte de idiomas

La mayoría de los lenguajes ensambladores y algunos lenguajes de bajo nivel , como BCPL (Basic Combined Programming Language), carecen de soporte integrado para estructuras de datos. Por otro lado, muchos lenguajes de programación de alto nivel y algunos lenguajes ensambladores de nivel superior, como MASM , tienen una sintaxis especial u otro soporte integrado para ciertas estructuras de datos, como registros y matrices. Por ejemplo, los lenguajes C (un descendiente directo de BCPL) y Pascal admiten estructuras y registros, respectivamente, además de vectores ( matrices unidimensionales ) y matrices multidimensionales. [14] [15]

La mayoría de los lenguajes de programación cuentan con algún tipo de mecanismo de biblioteca que permite que las implementaciones de estructuras de datos se reutilicen en diferentes programas. Los lenguajes modernos suelen contar con bibliotecas estándar que implementan las estructuras de datos más comunes. Algunos ejemplos son la biblioteca de plantillas estándar de C++ , el marco de colecciones de Java y el marco .NET de Microsoft .

Los lenguajes modernos también suelen admitir la programación modular , es decir, la separación entre la interfaz de un módulo de biblioteca y su implementación. Algunos proporcionan tipos de datos opacos que permiten a los clientes ocultar detalles de implementación. Los lenguajes de programación orientados a objetos , como C++ , Java y Smalltalk , suelen utilizar clases para este propósito.

Muchas estructuras de datos conocidas tienen versiones concurrentes que permiten que múltiples subprocesos computacionales accedan a una única instancia concreta de una estructura de datos simultáneamente. [16]

Véase también

Referencias

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introducción a los algoritmos, tercera edición (3ª ed.). La prensa del MIT. ISBN 978-0262033848.
  2. ^ Black, Paul E. (15 de diciembre de 2004). «data structure». En Pieterse, Vreda; Black, Paul E. (eds.). Dictionary of Algorithms and Data Structures [en línea] . Instituto Nacional de Estándares y Tecnología . Consultado el 6 de noviembre de 2018 .
  3. ^ "Estructura de datos". Enciclopedia Británica . 17 de abril de 2017. Consultado el 6 de noviembre de 2018 .
  4. ^ Wegner, Peter; Reilly, Edwin D. (29 de agosto de 2003). Enciclopedia de informática. Chichester, Reino Unido: John Wiley and Sons. págs. 507–512. ISBN 978-0470864128.
  5. ^ "Tipos de datos abstractos". Virginia Tech - CS3 Estructuras de datos y algoritmos . Archivado desde el original el 2023-02-10 . Consultado el 2023-02-15 .
  6. ^ Gavin Powell (2006). "Capítulo 8: Creación de modelos de bases de datos de rápido rendimiento". Diseño de bases de datos básico . Wrox Publishing . ISBN 978-0-7645-7490-0. Archivado desde el original el 18 de agosto de 2007.{{cite book}}: CS1 maint: unfit URL (link)
  7. ^ "1.5 Aplicaciones de una tabla hash". Universidad de Regina - Laboratorio CS210: Tabla hash . Archivado desde el original el 2021-04-27 . Consultado el 2018-06-14 .
  8. ^ "Cuando los datos son demasiado grandes para caber en la memoria principal". Universidad de Indiana en Bloomington - Estructuras de datos (C343/A594) . 2014. Archivado desde el original el 10 de abril de 2018.
  9. ^ Vaishnavi, Gunjal; Shraddha, Gavane; Yogeshwari, Joshi (21 de junio de 2021). "Artículo de investigación sobre reconocimiento de expresiones faciales de grano fino mediante aprendizaje automático" (PDF) . Revista internacional de aplicaciones informáticas . 183 (11): 47–49. doi :10.5120/ijca2021921427.
  10. ^ Nievergelt, Jürg; Widmayer, Peter (1 de enero de 2000), Sack, J. -R.; Urrutia, J. (eds.), "Capítulo 17 - Estructuras de datos espaciales: conceptos y opciones de diseño", Handbook of Computational Geometry , Ámsterdam: Holanda Septentrional, págs. 725–764, ISBN 978-0-444-82537-7, consultado el 12 de noviembre de 2023
  11. ^ Dubey, RC (2014). Biotecnología avanzada: para estudiantes de licenciatura y maestría en biotecnología y otras ciencias biológicas . Nueva Delhi: S Chand. ISBN 978-81-219-4290-4.OCLC 883695533  .
  12. ^ Seymour, Lipschutz (2014). Estructuras de datos (Primera edición revisada). Nueva Delhi, India: McGraw Hill Education. ISBN 9781259029967.OCLC 927793728  .
  13. ^ Walter E. Brown (29 de septiembre de 1999). «Nota sobre el lenguaje C++: tipos de POD». Laboratorio Nacional del Acelerador Fermi . Archivado desde el original el 3 de diciembre de 2016. Consultado el 6 de diciembre de 2016 .
  14. ^ "El manual GNU C". Free Software Foundation . Consultado el 15 de octubre de 2014 .
  15. ^ Van Canneyt, Michaël (septiembre de 2017). "Free Pascal: Guía de referencia". Pascal libre.
  16. ^ Mark Moir y Nir Shavit. "Estructuras de datos concurrentes" (PDF) . cs.tau.ac.il . Archivado desde el original (PDF) el 2011-04-01.

Bibliografía

Lectura adicional

Enlaces externos