Estructura de datos

Estructura de datos

En programación de computadoras, un estructura de datos es un formato predefinido para almacenar, acceder y procesar de manera eficiente datos en un programa de computadora . Algunas estructuras de datos son una lenguaje de programación componente incorporado, y otros pueden requerir la inclusión de una biblioteca o módulo antes de que se pueda utilizar la estructura.

La decisión de qué estructuras de datos usar y cómo se usan es uno de los pasos más importantes en el diseño y la escritura de un programa de computadora.



Consejo

Los malos programadores se preocupan por el código. Los buenos programadores se preocupan por las estructuras de datos y sus relaciones ”. - Linus Torvalds

cómo exportar Word para sobresalir

Estructuras de datos primitivas

Los siguientes son estructuras de datos primitivas , también conocido como tipos de datos . Cada una de las siguientes primitivas puede contener un solo valor , como 1, 3.14 o la letra minúscula a.

Nombre Descripción Valores de ejemplo
Booleano Un tipo de datos booleano puede representar uno de los dos únicos valores posibles: verdadero o falso, almacenado internamente como '1' o '0'. Lleva el nombre del matemático George Boole, cuyo sistema de operaciones lógicas es la base de todo binario ordenadores. Verdadero, falso, 1, 0
Personaje Un carácter representa un único elemento visual o alfanumérico. símbolo . Internamente, se representa como un número. Dependiendo del tipo de codificación de caracteres, un carácter puede almacenarse en un solo byte (ocho bits ) o varios bytes (por ejemplo, 16 bits para UTF-16 Unicode ). Cuando se conectan varios caracteres en secuencia, como la palabra 'manzana' o la frase 'Me gustaría una manzana', forman una cadena. A, a, 5,?,
Entero Un número entero que cae dentro de ciertos límites numéricos. Los límites dependen del lenguaje de programación y, a veces, de la arquitectura del UPC . Los números enteros pueden tener signo (positivo o negativo) o sin signo (restringido a valores positivos únicamente). El valor máximo de un 32 bits entero con signo es 2147483647 (2 x 1031- 1) y el valor mínimo es -2147483648 (-2 x 1031). 1, 123, -2147483648
Punto flotante Un número de punto flotante puede representar números con un componente fraccionario: números con dígitos después de un punto decimal. El punto decimal puede 'flotar', lo que significa que puede aparecer en cualquier posición del número. Internamente, un flotador es similar a notación cientifica (por ejemplo, 1618033 x 10-6= 1,618033), con un exponente almacenado (en este caso, -6) que representa la posición del punto decimal. Los números de coma flotante están firmados; pueden almacenar valores positivos o negativos. 1.567001, 0.356000, -5000.01
Punto flotante de doble precisión Un punto flotante de doble precisión utiliza el doble de bytes que un flotante estándar, lo que proporciona aproximadamente el doble de precisión. 3.00000012384632, -351691.581045892
Puntero, también llamado referencia, identificador o descriptor Un puntero es un valor especial que se refiere ('apunta') a una ubicación de memoria donde un objeto de datos (por ejemplo, una estructura de datos o un función ) está almacenado. Los punteros son una característica poderosa de algunos lenguajes de bajo nivel , pero son peligrosos si se implementan incorrectamente y pueden causar errores graves o vulnerabilidades de software. Algunos idiomas no admiten punteros. Otros lenguajes lo hacen, pero requieren que el puntero se 'escriba'; el programador debe explícitamente declare el tipo de datos al que apunta. Acceder a un valor por su puntero se llama desreferenciar . 0xffe2ba6c, 0xffe2ac5b
Punto fijo Un valor numérico con un número entero y un componente fraccionario, similar a un número de punto flotante, pero con un nivel de precisión preestablecido. Por ejemplo, los valores monetarios generalmente se pueden representar en un formato de punto fijo que siempre tiene dos dígitos después del punto decimal, por ejemplo, 5,00 o 123,45. La mayoría de los lenguajes de programación no admiten de forma nativa un tipo de datos de punto fijo, porque el punto flotante es más flexible. Los lenguajes con tipos de datos de punto fijo incluyen Ada y COBOL. 1.2, 400.00, -9.874

Estructuras de datos compuestas

Estructuras de datos compuestas puede contener múltiples elementos . Estos elementos suelen ser valores de un tipo de datos primitivo, como un número entero o un carácter. Algunas estructuras compuestas están restringidas a un solo tipo de datos, mientras que otras permiten una combinación de tipos de datos. Algunos pueden contener estructuras de datos como elementos.



Cada una de las siguientes estructuras compuestas tiene sus propios beneficios y casos de uso.

cómo determinar qué versión de Windows tengo

Estructuras de datos lineales

A estructura de datos lineal es una estructura de datos compuesta cuyos elementos están ordenados en una secuencia lógica. En estas estructuras, a cada elemento le sigue exactamente otro elemento, a menos que sea el último.

Nombre Descripción
Formación Una matriz es una secuencia de elementos, generalmente de un solo tipo de datos. Se puede acceder a cada elemento mediante un número de índice que representa su posición en la matriz.

Por lo general, la indexación de matrices es de base cero : si la matriz contiene norte elementos, el primer elemento tiene índice 0, el segundo tiene índice 1 y el último tiene índice norte -1. Por ejemplo, considere una matriz llamadabonificacionesque contiene los valores[2, 3, 5, 7, 11]. El primer elemento,bonificaciones [0], es el valor2. El último elemento,bonificaciones [4], es el valor11. La largo de esta matriz (el número de elementos que contiene) es 5.

A matriz estática no puede cambiar de tamaño una vez que se declara y se asigna su memoria. A matriz dinámica puede aumentar o disminuir su longitud según sea necesario.

Una LUT (tabla de búsqueda) es una matriz que contiene valores precalculados para acelerar el cálculo. Por ejemplo, una LUT puede contener raíces cuadradas de números de uso frecuente. Cuando se necesita la raíz cuadrada de un número en un cálculo, el valor se 'busca' en la matriz, en lugar de calcularse, conservando los ciclos de la CPU.

A matriz multidimensional contiene matrices de longitud fija como elementos. Por ejemplo,[[1, 2], [3, 4], [5, 6]]es una matriz bidimensional. Contiene tres elementos, cada uno de los cuales es una matriz. Se puede acceder a los valores proporcionando dos números de índice, uno para cada matriz. En este ejemplo, el valor en el índice[0][0]es1. En el índice[0][1]es el valor2. En el índice[1][0]es el valor3. El último valor, en el índice[2][1], es6.

Una matriz es un objeto matemático que se puede implementar como una matriz multidimensional.
Matriz asociativa Un matriz asociativa , también llamado diccionario , mapa , o tabla de símbolos , es una estructura de datos que contiene pares de llaves y valores . Cada clave debe ser única (no debe aparecer más de una vez en la estructura). Cada clave está asociada con un valor, que no necesita ser único; varias claves pueden tener valores idénticos.

Los lenguajes de alto nivel a menudo tienen tipos de datos integrados para trabajar con matrices asociativas, comodictarclase en Python. Una matriz asociativa puede implementarse como una matriz unidimensional o bidimensional estándar, si el programador diseña el esquema adecuado para indexar y asociar claves y valores de manera adecuada. También se puede implementar como una tabla hash, un árbol de búsqueda binaria, etc.

JSON es una estructura de datos ampliamente utilizada para asociar claves y valores, diseñada por Douglas Crockford para JavaScript aplicaciones. JSON es esencialmente una matriz asociativa donde los valores también pueden ser matrices asociativas.
Lista Una lista es una secuencia de elementos. En su forma más simple, una lista se puede implementar como una matriz. Sin embargo, el término 'lista' generalmente se refiere a un lista enlazada con cada elemento de la lista (llamado 'nodo') que contiene punteros a uno o más elementos de la lista. A diferencia de una matriz, en una lista vinculada, los elementos secuenciales no se organizan secuencialmente en la memoria física.

en un lista enlazada individualmente , cada elemento contiene un puntero al siguiente elemento de la lista.

en un lista doblemente enlazada , cada elemento tiene dos punteros: un puntero al siguiente elemento y un puntero al anterior.

en un lista de enlaces múltiples , se pueden incluir más de dos punteros en un nodo. Cada uno de estos punteros puede tener un propósito especial, definido por el programador, para atravesar elementos en una secuencia arbitraria. Por ejemplo, un nodo puede tener un puntero para el siguiente nodo por orden alfabético, otro puntero para el siguiente nodo por orden cronológico, etc. Aunque una lista de enlaces múltiples se puede atravesar linealmente, su enlace múltiple puede permitir un cruce no lineal de los datos. estructura.

en un lista enlazada circular , el último nodo apunta al primero, lo que permite un recorrido infinito de la lista. En otras palabras, el siguiente nodo después del último es el primero.

En general, las listas enlazadas son más flexibles que las matrices. Por ejemplo, la inserción de un elemento de matriz puede requerir que todo o parte de la matriz se vuelva a escribir en la memoria, comenzando en la ubicación de la inserción. Por el contrario, insertar un nodo en una lista vinculada requiere que se cree solo un nodo y que los punteros de los nodos adyacentes se actualicen con la ubicación del nuevo nodo. La compensación es que las listas vinculadas requieren más recursos del sistema. Por ejemplo, las listas vinculadas requieren GC (recolección de basura) manual o automática, para 'limpiar' (hacer disponible) la memoria que ya no está en uso después de que los nodos se eliminan de la lista.
Cola Una cola es una colección secuencial donde los elementos se agregan al final de la cola y se eliminan desde el principio. Es una estructura de datos FIFO ('primero en entrar, primero en salir'). Se implementa de manera más eficiente con una lista doblemente vinculada. Una cola también se puede implementar como una lista enlazada individualmente o una matriz dinámica, si se mantienen dos punteros adicionales, apuntando al primer y último elemento. Agregar un elemento a una cola se llama hacer cola , y eliminar un elemento de una cola se llama dequeueing.
Apilar Una pila es una colección secuencial de elementos donde solo se puede modificar el último elemento (en la 'parte superior' de la pila). Se puede 'empujar' un nuevo elemento a la pila, en cuyo caso, se convierte en el último elemento de la pila, y la longitud de la pila aumenta en 1. El último elemento se puede 'sacar' de la pila, donde se devuelve como un value y se elimina de la pila, lo que reduce la longitud de la pila en 1. A veces, también se proporciona una operación de 'mirar', lo que permite leer el último elemento sin eliminarlo. Una pila es una estructura de datos LIFO ('último en entrar, primero en salir'): el último elemento agregado es siempre el siguiente elemento eliminado. Por lo general, una pila se puede implementar como una matriz o una lista vinculada, con un puntero separado al elemento superior de la pila.
Cuerda Una cadena contiene una secuencia de caracteres. En algunos idiomas, una cadena es una matriz de caracteres que termina con un carácter nulo. Por ejemplo, la palabra 'esperanza' podría estar representada por la matriz['h', 'o', 'p', 'e', ​​' 0']. En otros lenguajes, como Python, las cadenas se implementan como clase , con asociado métodos para procesar, acceder y manipular los caracteres de la cadena.
Tupla Una tupla es una lista secuencial de elementos. Suele implementarse como un inmutable objeto que permite tipos de datos mixtos. Para identificar su tamaño, puede denominarse ' norte -tupla, es decir, tres tuplas, seis tuplas, etc., donde norte es el número de elementos que contiene.

Estructuras de árboles

Un árbol es una estructura compuesta cuyos elementos están ordenados en una jerarquía de padres e hijos, similar a las ramas de un árbol. Los elementos se denominan nodos. Un árbol contiene un solo nodo raíz , que no tiene padres. El recorrido generalmente ocurre solo en una dirección, desde el nodo hasta uno de sus hijos (llamados 'descendientes'). Luego, el recorrido continúa de forma recursiva, a uno de los hijos de ese nodo, hasta que se alcanza el nodo deseado. Si un nodo no tiene hijos, se llama nodo hoja .



Si un árbol es equilibrado , todas sus ramas tienen la misma 'profundidad': todos los nodos hoja están a la misma distancia del nodo raíz. Si un árbol es desequilibrado , no hay ninguna restricción sobre la duración de una rama en relación con las demás. Los árboles desequilibrados son más simples de implementar, pero pueden ser menos eficientes en el peor de los casos.

Nombre Descripción
Árbol de sintaxis abstracta Un AST ( árbol de sintaxis abstracta ) estructura los elementos de un programa de computadora en una jerarquía de árbol. La estructura del árbol representa naturalmente algunos elementos del sintaxis de un lenguaje informático, como el alcance léxico y declaraciones condicionales . Un AST tiene muchos usos en informática, como convertir automáticamente un programa de un idioma a otro.
Árbol binario En un árbol binario, cada nodo tiene cero, uno o dos hijos. Según algunas definiciones, los nodos de árbol binario deben tener exactamente dos hijos o ninguno. Un ejemplo de uso de árbol binario es una comparación numérica, donde el recorrido del árbol se basa en comparar dos hijos y elegir el valor mayor o menor.
Árbol B Árboles B son estructuras de árbol en las que los nodos pueden tener más de dos hijos y están organizados de acuerdo con sus valores ordenados. Los árboles B se autoequilibran, se organizan de acuerdo con un conjunto de reglas dado que aseguran que las operaciones fundamentales ocurran en tiempo logarítmico. En otras palabras, el número de pasos necesarios para completar una operación, en el peor de los casos, nunca es mayor que el logaritmo del número total de elementos del árbol. Esta propiedad hace que los árboles B sean ideales para el acceso rápido al almacenamiento masivo de datos, como sistemas de archivos y bases de datos .
Árbol BSP A Árbol BSP contiene datos utilizados en particionamiento del espacio binario , donde un espacio geométrico se divide recursiva y lógicamente. Los árboles BSP se utilizan con frecuencia en 3D gráficos para optimizar la representación de objetos en el espacio. Por ejemplo, un espacio se puede dividir para que los objetos parcialmente ocultos por otros objetos no se rendericen por completo o no se rendericen en absoluto, lo que aumenta el rendimiento.
Montón A montón es un árbol que satisface la 'propiedad del montón'. en un montón máximo , para cualquier nodo C , Si PAG es un nodo padre de C , luego el valor (clave) de PAG es mayor o igual a C . en un min montón , El valor de PAG es menor o igual que el valor de C .

Los montones se utilizan comúnmente como cola de prioridad , donde el elemento de mayor o menor prioridad se almacena en la raíz del árbol.

Los montones binarios (con un máximo de dos nodos para cualquier padre) son la estructura de datos fundamental del tipo de pila algoritmo .
Árbol Merkle A Árbol Merkle o árbol de hachís es una estructura de árbol con cada nodo padre contiene un hash criptográfico de sus hijos, y los nodos hoja contienen un hash criptográfico de un bloque de datos. Son útiles para verificar la autenticidad de los datos. Por ejemplo, se utilizan en los sistemas de archivos IPFS, Btrfs y ZFS para verificar que los datos no se hayan dañado en el disco. También se utilizan en los protocolos de criptomonedas de bitcoin y Ethereum para proteger contra inconsistencias maliciosas o incidentales en la cadena de bloques. Otros sistemas que utilizan árboles Merkle incluyen Git y Mercurial sistemas de control de versiones y el sistema de base de datos NoSQL Apache Cassandra. Llevan el nombre de su inventor, Ralph Merkle.
Árbol R Árboles R son estructuras de árbol optimizadas para ciertas operaciones espaciales en los datos. Por ejemplo, pueden almacenar ubicaciones geográficas y encontrar ubicaciones de manera eficiente dentro de un cierto radio, en función de la distancia de sus carreteras de conexión. La 'R' significa rectángulo, en referencia al hecho de que los elementos se agrupan de acuerdo con sus rectángulos delimitadores mínimos dentro de un espacio geométrico.

Estructuras hash

En informática, un función hash es una función que produce un número de longitud fija, a menudo representado en hexadecimal, que se puede calcular a partir de un conjunto dado de datos de entrada. Independientemente del tamaño de la entrada, siempre que la entrada no haya cambiado, siempre produce el mismo número hexadecimal de longitud fija. Este tipo de funciones tienen usos importantes en informática, porque pueden validar o indexar datos, incluso a escala masiva.

Los siguientes son ejemplos de estructuras de datos diseñadas para almacenar los resultados de las funciones hash, muchos de los cuales son casos especiales de estructuras descritas en las secciones anteriores.

cómo abrir un archivo .csv
Nombre Descripción
Filtro de floración A Filtro de floración es una estructura de datos probabilística propuesta por primera vez por el científico Burton Howard Bloom en el MIT en 1970 . Las propiedades matemáticas de la estructura permiten que un programa determine rápidamente si un elemento posiblemente o ciertamente no pertenecen a un conjunto mayor de elementos. Bloom ideó la estructura para abordar los problemas en los campos crecientes de AI , ML y Big Data. Usando estructuras tradicionales como tablas hash, las consultas deterministas en grandes conjuntos de datos no serían factibles, excediendo una cantidad práctica de espacio en disco y memoria central. Sin embargo, utilizando un filtro Bloom, se pueden obtener resultados con un alto grado de probabilidad con una fracción de acceso a la memoria y al disco. La estructura se puede ajustar de acuerdo con los recursos disponibles, proporcionando enormes ganancias de eficiencia con una pérdida insignificante de precisión.
Tabla de picadillo A tabla de picadillo o mapa hash es un tipo de matriz asociativa donde las claves son los hash calculados de sus valores. Por ejemplo, el contenido de los archivos se puede utilizar para crear una clave de longitud fija, por ejemplo, un número hexadecimal con un número constante de dígitos. El algoritmo asegura que esta clave es casi seguro único. Por lo general, existe una pequeña probabilidad de una 'colisión' en la tabla; diferentes entradas tienen una pequeña posibilidad de producir claves idénticas. La posibilidad de colisión suele ser insignificante y se considera una compensación aceptable por un alto rendimiento.

Las tablas hash son una buena forma de indexar grandes conjuntos de datos, proporcionando tiempos de búsqueda que son independientes del tamaño de la tabla.
Hash rodante A hash rodante es una tabla hash cuya función hash 'recorre' un conjunto de entrada, calculando hash de forma progresiva para una ventana móvil de los datos de entrada. Es útil para procesar datos que se ingresan en un flujo constante, como los datos transferidos a través de una red. Por ejemplo, rsync utiliza un hash rodante para proteger contra la corrupción de datos durante las transferencias de archivos de red. El hash rodante también es útil en el procesamiento de transmisiones. En el procesamiento de flujos, los cálculos se realizan progresivamente en conjuntos de datos demasiado grandes para almacenarlos todos a la vez en un solo dispositivo.
Trie A intentar (también se pronuncia como 'árbol' o 'prueba') es una estructura de árbol ordenada que almacena matrices asociativas. Tiene propiedades especiales que lo hacen eficiente en términos de espacio para ciertas operaciones de búsqueda. En un intento, la clave de un nodo no se almacena literalmente. En cambio, la clave está definida por la posición del nodo en el árbol. Las claves de todos los descendientes de un nodo determinado comparten un prefijo común, como los primeros caracteres de una cadena, asociados con el nodo principal. Los intentos son ideales para determinadas funciones de búsqueda, como las que se utilizan en NLP (procesamiento del lenguaje natural).

La estructura de datos fue descrita por primera vez por el científico informático René de la Briandais en 1959, y el término 'trie' fue acuñado por Edward Fredkin en 1961. Fredkin derivó el término de la palabra 'recuperación' y lo pronunció como 'árbol'.

Estructuras de grafos

Un gráfico es una estructura de datos que organiza los datos de acuerdo con las relaciones de sus elementos en un espacio geométrico. Los elementos suelen ser vértices (puntos en el gráfico) y aristas (las conexiones entre vértices).

Si los vértices de un gráfico se pueden atravesar en una sola dirección (A → B, pero no B → A), se denomina gráfico dirigido . Si los vértices se pueden atravesar en cualquier dirección, se llama gráfico no dirigido . Si es posible atravesar aristas y regresar al vértice inicial, se llama gráfico cíclico . Si tal recorrido no es posible, se llama un gráfico acíclico .

Los siguientes son ejemplos de estructuras de datos que se utilizan para almacenar y procesar gráficos de manera eficiente.

Nombre Descripción
Lista de adyacencia Un lista de adyacencia es una colección de listas desordenadas, cada una de las cuales describe los vecinos de un vértice en un gráfico. Puede implementarse utilizando otras estructuras de datos, como una tabla hash donde los valores son matrices de vértices adyacentes. En otras implementaciones, los vértices y los bordes se almacenan cada uno como objetos conectados por punteros, similar a una lista de enlaces múltiples. Una lista de adyacencia puede calcular todos los vecinos de un vértice en tiempo constante, proporcional al grado del vértice (la dimensionalidad del gráfico). Sin embargo, es ineficaz para determinar si existe una arista entre dos vértices dados.
Matriz de adyacencia En un matriz de adyacencia , una matriz multidimensional usa valores booleanos (que requieren solo un bit) correspondientes a la conectividad de los vértices, que están indexados a las filas y columnas de la matriz. En esta estructura, enumerar los vecinos de un vértice lleva mucho más tiempo calcular, proporcional al número total de vértices. Además, la estructura requiere más almacenamiento, creciendo exponencialmente con el número total de vértices. Sin embargo, determinar si existe un borde entre dos vértices es significativamente más rápido que con una lista de adyacencia.
Pila con estructura de gráficos A pila estructurada en gráficos es una estructura de datos cuyas operaciones se correlacionan con una pila tradicional (un LIFO cuyos valores pueden ser empujados o desplegados), pero la conexión de elementos de un gráfico acíclico. Tiene usos importantes en PNL, específicamente para analizar gramáticas ambiguas o no deterministas, como las que usan los humanos.
Hypergraph en un hipergrafo , una arista puede unir cualquier número de vértices. Estos bordes especiales, llamados hiperextensiones , generalmente comparten cardinalidad (todos están conectados al mismo número de nodos). en un a -Hipergrafo uniforme, todos los hipergrafos estn conectados a a nodos. Por ejemplo, un 'hipergráfico uniforme de 2' es lo mismo que un gráfico tradicional; en un hipergrafo de 6 uniformes, cada hiperraja se conecta a 6 nodos. Los hipergráficos tienen una definición especial de aciclicidad, con reglas especiales para lo que constituye el cruce de nodos en un ciclo.

Las propiedades matemáticas de los hipergráficos han ganado atención con la llegada del aprendizaje automático (ML), en aplicaciones como los sistemas de recomendación y el aprendizaje semi-supervisado.
Gráfico de escena A gráfico de escena es una estructura utilizada en algunos editores de gráficos vectoriales, software de modelado 3D y juegos de computadora. Puede modelar de manera eficiente una relación compleja de objetos que están relacionados espacialmente, lo que representa una jerarquía de modificaciones secuenciales. Por ejemplo, cuando se aplican varios efectos de geometría a un objeto de modelado 3D, cada modificación secuencial se basa en los resultados de los cambios anteriores. Una esfera puede crearse como un objeto NURBS, modificarse mediante un enrejado delimitador y luego convertirse a geometría de estructura alámbrica para que sus vértices individuales puedan transformarse. Estas modificaciones se pueden almacenar en un gráfico de escena, por lo que el resultado final de todas las transformaciones se puede animar o renderizar de manera eficiente como objetos individuales. La modificación de un solo paso en la cadena de modificación no destruiría las transformaciones que ocurren más adelante en la secuencia.