De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Una estructura de datos conocida como tabla hash .

En informática , una estructura de datos es un formato de organización, gestión y almacenamiento de datos que permite un acceso y una modificación eficientes. [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]

Uso [ editar ]

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 diferentes tipos de estructuras de datos se adaptan a diferentes tipos de aplicaciones y algunas son 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 administrar grandes cantidades de datos de manera eficiente para usos como grandes bases de datos 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 formales y lenguajes de programación enfatizan las estructuras de datos, en lugar de los algoritmos, como el factor organizativo 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 secundaria. [8]

Implementación [ editar ]

Las estructuras de datos generalmente se basan en la capacidad de una computadora para buscar y almacenar datos en cualquier lugar de su memoria, especificada por un puntero, una cadena de bits, que representa una dirección de memoria , que se puede almacenar en la memoria y manipular por el programa. Por tanto, las estructuras de datos de matriz y registro se basan en calcular las direcciones de elementos de datos con operaciones aritméticas , mientras que las estructuras de datos vinculadas se basan en almacenar direcciones de elementos de datos dentro de la propia estructura.

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 él, y las propiedades matemáticas de esas operaciones (incluido su costo de espacio y tiempo). [9]

Ejemplos [ editar ]

Existen numerosos tipos de estructuras de datos, generalmente construidas sobre tipos de datos primitivos más simples : [10]

  • Una matriz es un número de elementos en un orden específico, generalmente todos del mismo tipo (dependiendo del idioma, los elementos individuales pueden ser forzados a ser del mismo tipo o pueden ser de casi cualquier tipo). Se accede a los elementos mediante un índice entero para especificar qué elemento se requiere. Las implementaciones típicas asignan palabras de memoria contiguas para los elementos de las matrices (pero esto no siempre es una necesidad). Las matrices pueden ser de longitud fija o de tamaño variable.
  • Una lista vinculada (también llamada lista ) es una colección lineal de elementos de datos de cualquier tipo, denominados nodos, donde cada nodo tiene un valor en sí mismo y apunta al siguiente nodo de la lista vinculada. La principal ventaja de una lista vinculada sobre una matriz es que los valores siempre se pueden insertar y eliminar de manera eficiente sin reubicar el resto de la lista. Sin embargo, algunas otras operaciones, como el acceso aleatorio a un determinado elemento, son más lentas en las listas que en las matrices.
  • Un registro (también llamado tupla o estructura ) es una estructura de datos agregada . Un registro es un valor que contiene otros valores, típicamente en un número fijo y secuencia y típicamente indexados por nombres. Los elementos de los registros suelen denominarse campos o miembros .
  • Una unión es una estructura de datos que especifica cuál de varios tipos primitivos permitidos puede almacenarse en sus instancias, por ejemplo, float o entero largo . Contraste con un registro , que podría definirse para contener un número flotante y un número entero; mientras que en una unión, solo hay un valor a la vez. Se asigna suficiente espacio para contener el tipo de datos de miembro más amplio.
  • Una unión etiquetada (también denominada variante , registro de variante , unión discriminada o unión disjunta ) contiene un campo adicional que indica su tipo actual, para mejorar la seguridad del tipo.
  • Un objeto es una estructura de datos que contiene campos de datos, como lo hace un registro, así como varios métodos que operan en el contenido de los datos. Un objeto es una instancia en memoria de una clase de una taxonomía. En el contexto de la programación orientada a objetos , los registros se conocen como estructuras de datos antiguas simples para distinguirlos de los objetos. [11]

Además, los gráficos y los árboles binarios son otras estructuras de datos de uso común.

Soporte de idiomas [ editar ]

La mayoría de los lenguajes ensambladores y algunos lenguajes de bajo nivel , como BCPL (lenguaje de programación combinado básico), carecen de soporte integrado para estructuras de datos. Por otro lado, muchos lenguajes de programación de alto nivel y algunos lenguajes ensambladores de alto nivel, 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. [12] [13]

La mayoría de los lenguajes de programación cuentan con algún tipo de mecanismo de biblioteca que permite que diferentes programas reutilicen las implementaciones de la estructura de datos. Los lenguajes modernos generalmente vienen 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 de Microsoft .NET .

Los lenguajes modernos también suelen admitir la programación modular , 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 simultáneas que permiten que múltiples subprocesos informáticos accedan a una única instancia concreta de una estructura de datos simultáneamente. [14]

Ver también [ editar ]

  • Tipo de datos abstracto
  • Estructura de datos concurrentes
  • Modelo de datos
  • Dinamización
  • Estructura de datos vinculados
  • Lista de estructuras de datos
  • Estructura de datos persistente
  • Estructura de datos antigua simple
  • Estructura de datos sucinta

Referencias [ editar ]

  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). "estructura de datos" . En Pieterse, Vreda; Black, Paul E. (eds.). Diccionario de algoritmos y estructuras de datos [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 Ciencias de la Computación . Chichester, Reino Unido: John Wiley and Sons. págs. 507–512. ISBN 978-0470864128.
  5. ^ "Tipos de datos abstractos" . Virginia Tech - Estructuras de datos y algoritmos de CS3 .
  6. ^ Gavin Powell (2006). "Capítulo 8: Creación de modelos de base de datos de rendimiento rápido" . Diseño de base de datos inicial . Publicación Wrox . ISBN 978-0-7645-7490-0.
  7. ^ "1.5 Aplicaciones de una tabla hash" . Universidad de Regina - Laboratorio CS210: Tabla hash .
  8. ^ "Cuando los datos son demasiado grandes para caber en la memoria principal" . homes.sice.indiana.edu .
  9. ^ Dubey, RC (2014). Biotecnología avanzada: para estudiantes B Sc y M Sc de biotecnología y otras ciencias biológicas . Nueva Delhi: S Chand. ISBN 978-81-219-4290-4. OCLC  883695533 .
  10. ^ Seymour, Lipschutz (2014). Estructuras de datos (revisada primera ed.). Nueva Delhi, India: McGraw Hill Education. ISBN 9781259029967. OCLC  927793728 .
  11. ^ Walter E. Brown (29 de septiembre de 1999). "Nota de lenguaje C ++: tipos de POD" . Laboratorio del Acelerador Nacional Fermi . Archivado desde el original el 3 de diciembre de 2016 . Consultado el 6 de diciembre de 2016 .
  12. ^ "El manual de GNU C" . Fundación de Software Libre . Consultado el 15 de octubre de 2014 .
  13. ^ Van Canneyt, Michaël (septiembre de 2017). "Free Pascal: Guía de referencia" . Pascal libre.
  14. ^ Mark Moir y Nir Shavit. "Estructuras de datos concurrentes" (PDF) . cs.tau.ac.il .

Bibliografía [ editar ]

  • Peter Brass, Estructuras de datos avanzadas , Cambridge University Press , 2008, ISBN 978-0521880374 
  • Donald Knuth , El arte de la programación informática , vol. 1. Addison-Wesley , tercera edición, 1997, ISBN 978-0201896831 
  • Dinesh Mehta y Sartaj Sahni , Manual de estructuras y aplicaciones de datos , Chapman y Hall / CRC Press , 2004, ISBN 1584884355 
  • Niklaus Wirth , Algoritmos y estructuras de datos , Prentice Hall , 1985, ISBN 978-0130220059 

Lectura adicional [ editar ]

  • Alfred Aho , John Hopcroft y Jeffrey Ullman , Estructuras de datos y algoritmos , Addison-Wesley, 1983, ISBN 0-201-00023-7 
  • GH Gonnet y R. Baeza-Yates , Manual de algoritmos y estructuras de datos - en Pascal y C , segunda edición, Addison-Wesley, 1991, ISBN 0-201-41607-7 
  • Ellis Horowitz y Sartaj Sahni, Fundamentos de estructuras de datos en Pascal , Computer Science Press , 1984, ISBN 0-914894-94-3 

Enlaces externos [ editar ]

  • Descripciones del Diccionario de algoritmos y estructuras de datos
  • Curso de estructuras de datos
  • Un examen de las estructuras de datos desde la perspectiva de .NET
  • Schaffer, C.Estructuras de datos y análisis de algoritmos