¿Qué son los algoritmos y las estructuras de datos?
Un algoritmo es una serie de instrucciones claras para resolver problemas, es decir, puede obtener el resultado requerido en un tiempo limitado para ciertas entradas estandarizadas. Si un algoritmo es defectuoso o inapropiado para un problema, ejecutarlo no resolverá el problema. Diferentes algoritmos pueden utilizar diferente tiempo, espacio o eficiencia para completar la misma tarea. La calidad de un algoritmo se puede medir por su complejidad espacial y temporal.
Los algoritmos pueden entenderse como pasos completos de resolución de problemas que constan de operaciones básicas y secuencias de operaciones prescritas. O puede considerarse como una secuencia de cálculo limitada y exacta diseñada de acuerdo con los requisitos, y dichos pasos y secuencias pueden resolver un tipo de problema.
Un algoritmo debe tener las siguientes cinco características importantes:
1. Finitud: un algoritmo debe garantizar que finaliza después de ejecutar un número finito de pasos
; 2. Exactitud: Cada paso del algoritmo debe tener una definición exacta;
3. Entrada: Un algoritmo tiene 0 o más entradas para describir la situación inicial del objeto de operación. al algoritmo Él mismo determina las condiciones iniciales
4. Salida: Un algoritmo tiene una o más salidas para reflejar los resultados del procesamiento de los datos de entrada. Un algoritmo sin resultados no tiene sentido;
5. Viabilidad: en principio, el algoritmo puede ejecutarse con precisión y puede ser completado por personas que utilicen lápiz y papel para realizar un número limitado de operaciones.
El informático Nicklaus Wirth escribió una vez un famoso libro "Estructura de datos Diez algoritmos = programas", que muestra el estado de los algoritmos en el mundo de la informática y las aplicaciones informáticas.
La estructura de datos es la forma en que una computadora almacena y organiza los datos. Una estructura de datos se refiere a una colección de elementos de datos que tienen una o más relaciones específicas entre sí. A menudo, las estructuras de datos cuidadosamente seleccionadas pueden conducir a una mayor eficiencia operativa o de almacenamiento. Las estructuras de datos suelen estar relacionadas con algoritmos de recuperación y técnicas de indexación eficientes.
Generalmente se cree que una estructura de datos está organizada por elementos de datos de acuerdo con ciertas conexiones lógicas. La descripción de la relación lógica entre los elementos de datos se denomina estructura lógica de los datos y debe almacenarse en la computadora, y la estructura de almacenamiento de los datos es la forma de implementación de la estructura de datos y su representación en la computadora; Cuando se habla de una estructura de datos, también debemos discutir que las operaciones realizadas en este tipo de datos son significativas.
En el diseño de muchos tipos de programas, la elección de las estructuras de datos es una consideración de diseño fundamental. La experiencia de construcción de muchos sistemas a gran escala muestra que la dificultad de la implementación del sistema y la calidad de la construcción del sistema dependen seriamente de si se selecciona la estructura de datos óptima. Muchas veces, una vez determinada la estructura de datos, el algoritmo es fácil de conseguir. A veces las cosas funcionan al revés y elegimos una estructura de datos que se ajuste a un algoritmo específico. En cualquier caso, es muy importante elegir la estructura de datos adecuada.
Una vez seleccionada la estructura de datos, también se determina el algoritmo. Los datos, no los algoritmos, son el factor clave en la construcción del sistema. Esta idea ha llevado a la aparición de muchos métodos de diseño de software y lenguajes de programación, y los lenguajes de programación orientados a objetos son uno de ellos.
En informática, la estructura de datos es una disciplina que estudia los objetos operativos de la computadora (elementos de datos) y las relaciones y operaciones entre ellos en problemas de programación no numérica, y asegura que a través de estos la nueva estructura obtenida después la operación sigue siendo el tipo de estructura original.
"Estructura de datos" como curso independiente no se creó en el extranjero hasta 1968. En 1968, el profesor estadounidense Don O. Knut creó el sistema original de estructura de datos. El primer volumen de "Técnicas de programación informática" escrito por él, "Algoritmos básicos", fue el primer libro que explicó sistemáticamente la estructura lógica y la estructura de almacenamiento de los datos. y escritos sobre sus operaciones. "Estructura de datos" es un curso básico profesional integral en informática. La estructura de datos es un curso básico entre matemáticas, hardware y software de computadora. El contenido del curso de estructura de datos no es solo la base de la programación general (especialmente la programación no numérica), sino también una base importante para el diseño e implementación de compiladores, sistemas operativos, sistemas de bases de datos y otros programas del sistema.
La informática es una ciencia que estudia el uso de los ordenadores para representar y procesar información.
Esto implica dos cuestiones:
Representación de la información
Procesamiento de la información
La representación y agrupación de la información están directamente relacionadas con la eficiencia del programa que procesa la información. Con la popularización de las computadoras, la cantidad de información ha aumentado y el alcance de la información se ha ampliado, lo que hace que muchos programas de sistema y programas de aplicación sean de gran escala y de estructura compleja. Por lo tanto, para escribir un "buen" programa, es necesario analizar las características de los objetos a procesar y las relaciones entre los objetos. Este es el tema que se estudiará en el curso de estructura de datos. Como todos sabemos, los programas informáticos procesan información. En la mayoría de los casos, esta información no está desorganizada. A menudo existen relaciones estructurales importantes entre la información (datos). Este es el contenido de la estructura de datos. La estructura de los datos afecta directamente la selección y eficiencia del algoritmo.
Cuando una computadora resuelve un problema específico, generalmente necesita seguir los siguientes pasos: primero, debe abstraer un modelo matemático apropiado del problema específico y luego diseñar un algoritmo (Algoritmo) para resolver el problema matemático. modelo, y finalmente prográmelo, pruébelo, modifíquelo hasta obtener la solución final. La esencia de buscar un modelo matemático es analizar el problema, extraer los objetos de operación, descubrir las relaciones entre estos objetos de operación y luego describirlos en lenguaje matemático. Los algoritmos informáticos están estrechamente relacionados con la estructura de los datos. Todos los algoritmos dependen de estructuras de datos específicas. Las estructuras de datos están directamente relacionadas con la selección y la eficiencia de los algoritmos. La operación la completa la computadora, lo que requiere el diseño de los correspondientes algoritmos de inserción, eliminación y modificación. En otras palabras, la estructura de datos también debe proporcionar algoritmos para diversas operaciones definidas por cada tipo de estructura.
Datos es una representación simbólica de cosas objetivas. En informática, se refiere al término general para todos los símbolos que pueden ingresarse en la computadora y procesarse mediante el programa de computadora.
Un elemento de datos es la unidad básica de datos y suele considerarse como un todo en los programas informáticos. Un elemento de datos consta de varios elementos de datos. Un elemento de datos es la unidad de datos indivisible más pequeña. Hay dos tipos de elementos de datos: un tipo son elementos de datos atómicos indivisibles, como: entero "5", carácter "N", etc., el otro tipo son elementos de datos compuestos de múltiples cantidades, cada uno de los cuales se denomina datos A; artículo. Por ejemplo, un elemento de datos que describe la información de un estudiante puede consistir en los siguientes seis elementos de datos. La fecha de nacimiento puede estar compuesta por tres elementos de datos: "año", "mes" y "día", luego la "fecha de nacimiento" se denomina elemento combinado y otros elementos de datos indivisibles son elementos atómicos.
Una palabra clave se refiere a un elemento de datos que identifica uno o más elementos de datos. Si puede desempeñar una función de identificación única, se denomina palabra clave "primaria"; de lo contrario, se denomina palabra clave "secundaria".
Un objeto de datos es una colección de elementos de datos con las mismas propiedades y es un subconjunto de datos. Los objetos de datos pueden ser finitos o infinitos.
El procesamiento de datos se refiere al proceso operativo de buscar, insertar, eliminar, fusionar, ordenar, realizar estadísticas y realizar cálculos simples sobre datos. Al principio, las computadoras se utilizaban principalmente para cálculos científicos y de ingeniería. Después de la década de 1980, las computadoras se utilizaban principalmente para el procesamiento de datos. Según estadísticas relevantes, la proporción de tiempo que se utilizan las computadoras para el procesamiento de datos ahora alcanza más del 80%. Con el paso del tiempo y la mayor popularización de las aplicaciones informáticas, la proporción de tiempo que se utilizan las computadoras para el procesamiento de datos definitivamente aumentará. más.
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 entre elementos de datos 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 la estructura de datos en la computadora se llama 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.
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. 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, clasificación de actualización, etc.