Estructura de datos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de febrero de 2020; las comprobaciones requieren 6 ediciones .

Una estructura de datos es una  unidad de software que le permite almacenar y procesar el mismo tipo y/o datos relacionados lógicamente . Para agregar, buscar, cambiar y eliminar datos, la estructura de datos proporciona un determinado conjunto de funciones que componen su interfaz.

El término "estructura de datos" puede tener varios significados cercanos, pero sin embargo diferentes [1] :

• tipo de datos abstractos ;
• Implementación de algún tipo de dato abstracto;
• Una instancia de un tipo de datos, como una lista específica ;
• En el contexto de la programación funcional: una unidad única ( ing.  identidad única ), que se conserva durante los cambios. Se le conoce informalmente como una estructura de datos única, a pesar de la posible existencia de diferentes versiones.

Las estructuras de datos se forman utilizando tipos de datos , referencias y operaciones sobre ellos en el lenguaje de programación elegido .

Diferentes tipos de estructuras de datos se adaptan a diferentes aplicaciones; algunos de ellos tienen una especialización estrecha para ciertas tareas. Por ejemplo, los árboles B suelen ser adecuados para crear bases de datos , mientras que las tablas hash se usan de forma ubicua para crear varios tipos de diccionarios, por ejemplo, para asignar nombres de dominio a direcciones de Internet de computadoras .

En el desarrollo de software, la complejidad de la implementación y la calidad del trabajo de los programas dependen significativamente de la correcta elección de las estructuras de datos. Esta comprensión dio lugar a métodos formales de desarrollo y lenguajes de programación que pusieron estructuras de datos, no algoritmos, al frente de la arquitectura de software. La mayoría de estos lenguajes cuentan con algún tipo de modularidad que permite reutilizar estructuras de datos de forma segura en distintas aplicaciones. Los lenguajes orientados a objetos como Java , C# y C++ son ejemplos de este enfoque.

Muchas estructuras de datos clásicas se proporcionan en las bibliotecas estándar de los lenguajes de programación o se integran directamente en los lenguajes de programación. Por ejemplo, la estructura de datos de la tabla hash está integrada en los lenguajes de programación Lua , Perl , Python , Ruby , Tcl y otros La biblioteca de plantillas estándar (STL) de C ++ se usa ampliamente.

Los bloques de construcción fundamentales para la mayoría de las estructuras de datos son matrices , registros ( structen C y Pascal ), uniones discriminadas ( recorden C) y referencias . Por ejemplo, se puede construir una lista doblemente enlazada usando entradas y enlaces, donde cada entrada (nodo) almacenará datos y enlaces a los nodos "izquierdo" y "derecho".union

Comparación de estructuras de datos en programación funcional e imperativa

Diseñar estructuras de datos para lenguajes funcionales es más difícil que para lenguajes imperativos por al menos dos razones [1] :

1. Casi todas las estructuras de datos hacen un uso intensivo de la asignación , que no se usa en un estilo puramente funcional;
2. Las estructuras de datos funcionales son más flexibles y, por lo tanto, mientras que en la programación imperativa la versión anterior se pierde simplemente reemplazándola por una nueva, en la programación funcional continúa existiendo automáticamente. En otras palabras, en programación imperativa (si no se toman medidas especiales que pueden complicar seriamente el programa), las estructuras de datos son efímeras ( inglés  ephemeral ), y en programas funcionales suelen ser constantes ( inglés  persistente ).

Notas

1. ↑ 12 Okasaki , 1998 , págs. 3-4.

Literatura

• Alfred W. Aho, John Hopcroft , Jeffrey D. Ullman. Estructuras de datos y algoritmos = Estructuras de datos y algoritmos. - M. : Williams , 2000. - 384 p. — ISBN 0-201-00023-7 .
• Michael Main, Walter Savitch. Estructuras de datos y otros objetos usando C++. - 2ª ed. - M. : Williams , 2002. - 832 p. — ISBN 0-201-70297-5 .
• Chris Okasaki. Estructuras de datos puramente funcionales. - Prensa de la Universidad de Cambridge, 1998. - 232 p. - ISBN 978-0521663502 .

Enlaces

• Estructuras de datos y hash

Estructuras de datos
Liza	formación lista enlazada simple lista doblemente enlazada lista de pases
Árboles	árbol B Árbol de búsqueda binario árbol AVL árbol rojo-negro montón
cuenta	Gráfico dirigido Gráfico Acíclico Dirigido Diagrama de decisión binaria Hipergrafo
Otro	Tabla de picadillo Pila

Tipos de datos
Ininterpretable	Un poco Picar Byte qubit Tratar Rasgo Palabra
Numérico	Entero punto fijo punto flotante Racional Complejo Largo intervalo
Texto	Simbólico Cuerda
Referencia	Dirección Enlace Puntero Envoltura
Compuesto	Tipo de dato algebraico ( genérico ) Clase Tipo-producto ( Escribir tupla estructura ) Un objeto Consolidación ( etiquetado ) Par ordenado
resumen	formación Lista Giro Pila Matriz asociativa (pantalla, mapa ) Un montón de multiconjunto Escribe Grafico
Otro	Lógico Más bajo Más alto Polimórfico Funcional enumerable Recopilación Excepción Género ( Metaclase ) Monada Semáforo Caudal vacío
Temas relacionados	tipo de datos abstractos tipo primitivo Estructura de datos Genérico variable de tipo Interfaz Constructor (OOP) Constructor (FP) constructor de tipos Tipo de fundición Prototipo sistema de tipos