¿Cuáles son las clasificaciones de las estructuras de datos?

La estructura de datos se refiere a la relación entre elementos de datos en la misma clase de elementos de datos. Las estructuras de datos son, respectivamente, estructura lógica, estructura de almacenamiento (estructura física) y operaciones de datos. La estructura lógica de los datos es una descripción de la relación entre los datos. A veces, la estructura lógica se denomina simplemente estructura de datos. Una estructura lógica se define formalmente como (K, R) (o (D, S)), donde K es un conjunto finito de elementos de datos y R es un conjunto finito de relaciones en K. La relación de los elementos de datos entre sí se llama estructura. Hay cuatro tipos básicos de estructuras: conjuntos, estructuras lineales, estructuras de árbol y estructuras de gráficos (estructuras de red). Las estructuras de árbol y las estructuras de gráficos se denominan colectivamente estructuras no lineales. Los elementos de datos en la estructura de la colección no tienen otra relación excepto que pertenecen al mismo tipo. Existe una relación de uno a uno entre elementos en una estructura lineal, una relación de uno a muchos entre elementos en una estructura de árbol y una relación de muchos a muchos entre elementos en una estructura gráfica. Cada nodo en la estructura del gráfico puede tener cualquier número de nodos predecesores y nodos posteriores. La representación (imagen) de una estructura de datos en una computadora se denomina estructura física (almacenamiento) de los datos. Incluye la representación de elementos de datos y la representación de relaciones. Existen dos métodos diferentes de representación de la relación entre elementos de datos: mapeo secuencial y mapeo no secuencial, y así se obtienen dos estructuras de almacenamiento diferentes: estructura de almacenamiento secuencial y estructura de almacenamiento en cadena. Método de almacenamiento secuencial: almacena nodos lógicamente adyacentes en unidades de almacenamiento físicamente adyacentes. La relación lógica entre nodos se refleja en la relación de adyacencia de las unidades de almacenamiento. La representación de almacenamiento resultante se denomina estructura de almacenamiento secuencial. La estructura de almacenamiento secuencial es el método de representación de almacenamiento más básico, generalmente implementado con la ayuda de matrices en lenguajes de programación. Método de almacenamiento de enlaces: no requiere que los nodos lógicamente adyacentes también sean físicamente adyacentes. La relación lógica entre nodos está representada por campos de puntero adicionales. La representación de almacenamiento resultante se denomina estructura de almacenamiento encadenada. La estructura de almacenamiento encadenada generalmente se implementa con la ayuda de tipos de puntero en los lenguajes de programación. Método de almacenamiento de índice: además de establecer la información del nodo de almacenamiento, también se establece una tabla de índice adicional para identificar la dirección del nodo. Método de almacenamiento hash: la dirección de almacenamiento del nodo se calcula directamente en función de la palabra clave del nodo. En la estructura de datos, la estructura de datos se puede dividir lógicamente en estructura lineal y estructura no lineal (estructura lógica: relación lógica entre elementos de datos). La estructura de almacenamiento secuencial de una estructura lineal es una estructura de almacenamiento de acceso aleatorio, y la estructura de almacenamiento vinculada de una lista lineal es una estructura de almacenamiento de acceso secuencial. Si una tabla lineal está representada por almacenamiento en cadena, las direcciones de la unidad de almacenamiento entre todos los nodos pueden ser continuas o discontinuas. La estructura lógica no tiene nada que ver con la forma, el contenido, la posición relativa o el número de nodos contenidos en el propio elemento de datos. Edite este párrafo Estructura de datos y algoritmo El diseño del algoritmo depende de la estructura (lógica) de los datos y la implementación del algoritmo depende de la estructura de almacenamiento utilizada. La estructura de almacenamiento de datos es esencialmente la realización de su estructura lógica en la memoria de la computadora. Para reflejar de manera integral la estructura lógica de un dato, su imagen en la memoria incluye dos aspectos, a saber, la información entre los elementos de datos y la relación entre los elementos de datos. entre. Las diferentes estructuras de datos tienen sus operaciones correspondientes. Las operaciones de datos son algoritmos de operación definidos en la estructura lógica de los datos, como recuperación, inserción, eliminación, actualización y clasificación. Las operaciones de datos son un aspecto importante de las estructuras de datos. La discusión de cualquier estructura de datos es inseparable de la discusión de las operaciones de datos sobre la estructura y sus algoritmos de implementación. La forma de la estructura de datos se define como: la estructura de datos es una tupla: Estructura de datos = (D, S) donde: D es un conjunto finito de elementos de datos y S es un conjunto finito de relaciones en D. La estructura de datos es diferente del tipo de datos y del objeto de datos. No solo describe el objeto de datos del tipo de datos, sino que también describe la relación entre los elementos del objeto de datos. Un tipo de datos es una colección de valores y un conjunto de operaciones definidas en este conjunto de valores. Los tipos de datos se pueden dividir en dos categorías: tipos atómicos y tipos estructurales. Por un lado, en los lenguajes de programación cada dato pertenece a un determinado tipo de datos. Los tipos especifican explícita o implícitamente el rango de valores de los datos, cómo se almacenan y las operaciones permitidas. Se puede considerar que los tipos de datos son estructuras de datos que se han implementado en programación. Por otro lado, durante el proceso de programación, cuando es necesario introducir una nueva estructura de datos, la estructura de almacenamiento de datos siempre se describe con la ayuda de los tipos de datos proporcionados por el lenguaje de programación. La unidad de datos más pequeña representada en una computadora es un bit de un número binario, llamado bit.

Usamos una cadena de bits formada por una combinación de varios bits para representar un elemento de datos. Esta cadena de bits generalmente se denomina elemento o nodo. Cuando un elemento de datos consta de varios elementos de datos, la cadena de subbits correspondiente a cada elemento de datos en la cadena de bits se denomina campo de datos. Los elementos o nodos pueden verse como la imagen de elementos de datos en la computadora. Un marco de sistema de software debe basarse en datos, no en operaciones. Un módulo de software que contenga tipos de datos abstractos debe contener tres partes: definición, representación e implementación. Para cada estructura de datos, debe haber un conjunto de operaciones estrechamente relacionadas con ella. Si el tipo y número de operaciones son diferentes, incluso si la estructura lógica es la misma, la estructura de datos puede desempeñar diferentes funciones. Diferentes estructuras de datos tienen diferentes conjuntos de operaciones, pero las siguientes operaciones son indispensables: 1. Generación de la estructura; 2. Destrucción de la estructura; 3. Búsqueda de elementos de datos que cumplan con las condiciones especificadas en la estructura; el elemento de estructura; 5. Eliminar los elementos de datos existentes en la estructura; 6. Recorrer. Tipo de datos abstractos: un modelo matemático y un conjunto de operaciones definidas en el modelo. Un tipo de datos abstracto es en realidad la definición de esta estructura de datos. Porque define una estructura lógica de datos y un conjunto de algoritmos sobre esta estructura. Los tipos de datos abstractos se pueden representar mediante el siguiente triplete: (D, S, P). D es un objeto de datos, S es un conjunto de relaciones en D y P es un conjunto de operaciones básicas en D. La definición de ADT es: nombre del tipo de datos abstractos ADT {Objeto de datos: (conjunto de elementos de datos) Relación de datos: (combinación de tuplas de relaciones de datos) Operaciones básicas: (lista de funciones operativas) } Nombre del tipo de datos abstractos ADT; Dos características importantes: cuando la abstracción de datos utiliza ADT para describir las entidades procesadas por el programa, el énfasis está en sus características esenciales, las funciones que puede completar y su interfaz con usuarios externos (es decir, la forma en que el mundo exterior lo usa). . La encapsulación de datos separa las características externas de una entidad de sus detalles de implementación interna y oculta sus detalles de implementación interna a los usuarios externos. Los datos son portadores de información que las computadoras pueden reconocer, almacenar y procesar. Es la materia prima que procesan los programas informáticos, y las aplicaciones procesan todo tipo de datos. En informática, el objeto del procesamiento informático son los llamados datos. Pueden ser datos numéricos o no numéricos. Los datos numéricos son algunos números enteros, números reales o números complejos, que se utilizan principalmente en cálculos de ingeniería, cálculos científicos y procesamiento comercial. Los datos no numéricos incluyen caracteres, texto, gráficos, imágenes, voces, etc. El elemento de datos es la unidad básica de datos. En diferentes condiciones, los elementos de datos también pueden denominarse elementos, nodos, vértices, registros, etc. Por ejemplo, un registro en la tabla de información del estudiante en el sistema de recuperación de información del estudiante se llama elemento de datos. A veces, un elemento de datos puede estar compuesto por varios elementos de datos (Elemento de datos). Por ejemplo, cada elemento de datos en la tabla de información del estudiante en el sistema de gestión del estado del estudiante es un registro del estudiante. Incluye elementos de datos como número de estudiante, nombre, sexo, lugar de origen, fecha de nacimiento y calificaciones. Estos elementos de datos se pueden dividir en dos tipos: uno se llama elementos elementales, como el sexo de los estudiantes, el lugar de origen, etc. Estos elementos de datos son las unidades más pequeñas que no se pueden dividir durante el procesamiento de datos y el otro se llama elementos combinados. como las calificaciones de los estudiantes. Se puede subdividir en términos más pequeños como matemáticas, física, química, etc. Normalmente, se accede y procesa cada registro de estudiante como una unidad básica al resolver problemas de aplicación práctica. Un objeto de datos (Objeto de datos) o una clase de elemento de datos (Clase de elemento de datos) es una colección de elementos de datos con las mismas propiedades. En un problema específico, todos los elementos de datos tienen las mismas propiedades (los valores de los elementos no son necesariamente iguales), pertenecen al mismo objeto de datos (clase de elemento de datos) y el elemento de datos es una instancia de la clase de elemento de datos. Por ejemplo, en la red de tráfico del sistema de aviso de tráfico, todos los vértices son una clase de elemento de datos. El vértice A y el vértice B representan cada uno una ciudad y son dos instancias de la clase de elemento de datos. y b. La estructura de datos se refiere a una colección de elementos de datos que tienen una o más relaciones entre sí. En cualquier problema, los elementos de datos no están aislados. Existen relaciones de un tipo u otro entre ellos. Esta relación entre elementos de datos se llama estructura. Según las diferentes características de las relaciones entre elementos de datos, suelen existir los siguientes cuatro tipos básicos de estructuras: ⑴ Estructura de conjunto. La relación entre los elementos de datos de esta estructura es "pertenecer al mismo conjunto". ⑵Estructura lineal.

Existe una relación uno a uno entre los elementos de datos de esta estructura. ⑶Estructura de árbol. Existe una relación de uno a muchos entre los elementos de datos de esta estructura. ⑷Estructura gráfica. Existe una relación de muchos a muchos entre los elementos de datos de esta estructura, también llamada estructura de red. A partir del concepto de estructura de datos presentado anteriormente, podemos saber que una estructura de datos tiene dos elementos. Uno es una colección de elementos de datos y el otro es una colección de relaciones. Formalmente, una estructura de datos suele representarse mediante una tupla. La forma de la estructura de datos se define como: la estructura de datos es una tupla Estructura_Datos = (D, R) donde D es un conjunto finito de elementos de datos y R es un conjunto finito de relaciones en D. La característica de la estructura lineal es que existe una relación lineal entre los elementos de datos y los elementos de datos están "organizados uno tras otro". Los tipos de elementos de datos en una tabla lineal son los mismos, o una tabla lineal es una estructura lineal compuesta por elementos de datos del mismo tipo. Hay muchos ejemplos de tablas lineales en problemas prácticos. Por ejemplo, la tabla de información del estado del estudiante es una tabla lineal: el tipo de elementos de datos en la tabla es tipo de estudiante también es una tabla lineal: el tipo de datos; Los elementos de la tabla son el tipo de carácter, etc. Las tablas lineales son las estructuras lineales más simples, básicas y más utilizadas. Una tabla lineal es una secuencia finita de n (n>=0) elementos de datos con el mismo tipo de datos, generalmente registrados como: (a1, a2,… ai-1, ai, ai+1,…an) donde n es el longitud de la tabla, cuando n = 0, se denomina lista vacía. Tiene dos métodos de almacenamiento: almacenamiento secuencial y almacenamiento en cadena. Sus principales operaciones básicas son la inserción, eliminación y recuperación.