Estructura de datos

Particular way of storing and organizing data in a computer

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 generalmente se elige para el 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 diferentes tipos de estructuras de datos se adaptan a diferentes 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 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 formal y lenguajes de programación enfatizan las estructuras de datos, en lugar de los algoritmos, como 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 memoria secundaria . ^[8]

Implementación

Las estructuras de datos se pueden implementar utilizando una variedad de técnicas y lenguajes de programación, pero todos 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. Así, 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 vinculados se basan en almacenar 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 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 ellos y las propiedades matemáticas de esas operaciones (incluido su costo de espacio y tiempo). ^[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 sobre tipos de datos primitivos más simples . Ejemplos bien conocidos son: ^[12]

• Una matriz es una cantidad de elementos en un orden específico, generalmente todos del mismo tipo (según el idioma, es posible forzar que todos los elementos individuales sean 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 tener una longitud fija o cambiar de tamaño.
• Una lista vinculada (también llamada simplemente lista ) es una colección lineal de elementos de datos de cualquier tipo, llamados nodos, donde cada nodo tiene un valor 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, 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 agregados . Un registro es un valor que contiene otros valores, generalmente en números y secuencias fijos y generalmente indexados por nombres. Los elementos de los registros suelen denominarse campos o miembros . En el contexto de la programación orientada a objetos , los registros se conocen como estructuras de datos antiguas para distinguirlos de los objetos. ^[13]
• Las tablas hash , también conocidas como mapas hash, son estructuras de datos que proporcionan una recuperación rápida de valores basados ​​en claves. Utilizan una función hash para asignar claves a índices en una matriz, lo que permite un acceso en tiempo constante en el caso promedio. Las tablas hash se utilizan comúnmente en diccionarios, cachés e indexación de bases de datos. Sin embargo, pueden ocurrir colisiones de hash, lo que puede afectar su rendimiento. Se emplean técnicas como el encadenamiento y el direccionamiento abierto para manejar las colisiones.
• Los gráficos son colecciones de nodos conectados por aristas, que representan relaciones entre entidades. Los gráficos se pueden utilizar para modelar redes sociales, redes informáticas y redes de transporte, entre otras cosas. Consisten en vértices (nodos) y aristas (conexiones entre nodos). Los gráficos pueden ser dirigidos o no dirigidos y pueden tener ciclos o ser acíclicos. Los algoritmos de recorrido de gráficos incluyen búsqueda en amplitud y búsqueda en profundidad.
• Las pilas y colas son tipos de datos abstractos que se pueden implementar mediante matrices o listas vinculadas. Una pila tiene dos operaciones principales: empujar (agrega un elemento a la parte superior de la pila) y pop (elimina el elemento superior de la pila), que siguen el principio Último en entrar, primero en salir (LIFO). Las colas tienen dos operaciones principales: poner en cola (agrega un elemento al final de la cola) y quitar de la cola (elimina un elemento del frente de la cola) que siguen el principio de primero en entrar, primero en salir (FIFO).
• Los árboles representan una organización jerárquica de elementos. Un árbol consta de nodos conectados por aristas, siendo un nodo la raíz y todos los demás nodos formando subárboles. Los árboles se utilizan ampliamente en diversos algoritmos y escenarios de almacenamiento de datos. Los árboles binarios (particularmente los montones ), los árboles AVL y los árboles B son algunos tipos populares de árboles. Permiten una búsqueda, clasificación y representación jerárquica de datos eficiente y óptima.
• Un trie , también conocido como árbol de prefijos, es una estructura de datos de árbol especializada que se utiliza para la recuperación eficiente de cadenas. Intenta almacenar caracteres de una cadena como nodos, donde cada borde representa un carácter. Son particularmente útiles en escenarios de procesamiento de texto como autocompletar, revisión ortográfica e implementaciones de diccionario. Los intentos permiten búsquedas rápidas y operaciones basadas en prefijos en cadenas.

Ayuda de idioma

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 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 diferentes programas reutilicen las implementaciones de estructuras de datos. Los lenguajes modernos suelen venir con bibliotecas estándar que implementan las estructuras de datos más comunes. Algunos ejemplos son la biblioteca de plantillas estándar de C++ , Java Collections Framework y Microsoft .NET Framework .

Los lenguajes modernos también generalmente soportan 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 concurrentes que permiten que múltiples subprocesos informáticos accedan a una única instancia concreta de una estructura de datos simultáneamente. ^[dieciséis]

Ver también

• Tipo de datos abstractos
• 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 y sencilla
• Queap
• Estructura de datos sucinta
• Árbol (estructura de datos)

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. Negro, Paul E. (15 de diciembre de 2004). "estructura de datos". En Pieterse, Vreda; Negro, 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, Pedro; 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 - Algoritmos y estructuras de datos CS3 . Archivado desde el original el 10 de febrero de 2023 . Consultado el 15 de febrero de 2023 .
6. Gavin Powell (2006). "Capítulo 8: Creación de modelos de bases de datos de rápido rendimiento". Comenzando el diseño de bases de datos . Publicación Wrox . 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 27 de abril de 2021 . Consultado el 14 de junio de 2018 .
8. "Cuando los datos son demasiado grandes para caber en la memoria principal". Universidad de Indiana Bloomington - Estructuras de datos (C343/A594) . 2014. Archivado desde el original el 10 de abril de 2018.
9. Vaisnavi, Gunjal; Shraddha, Gavane; Yogeshwari, Joshi (21 de junio de 2021). "Documento de encuesta sobre el reconocimiento detallado de expresiones faciales mediante el 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", Manual de geometría computacional , Ámsterdam: Holanda Septentrional, págs. 725–764, ISBN 978-0-444-82537-7, recuperado 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". Fundación de Software Libre . 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 1 de abril de 2011.

Bibliografía

• 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 

Otras lecturas

• 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

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