¿Cuáles son las dos operaciones básicas de la pila y cuáles son sus significados?

Término ampliamente utilizado en los campos de la ciencia y la tecnología de las máquinas. Se utiliza para reflejar la estructura interna de un dato, es decir, de qué componentes está compuesto un dato, cómo está compuesto y qué estructura tiene. Las estructuras de datos se dividen en estructuras de datos lógicas y estructuras de datos físicas. La estructura de datos lógica refleja la relación lógica entre los datos de los componentes, mientras que la estructura de datos físicos refleja la disposición de almacenamiento de los datos de los componentes dentro de la computadora. La estructura de datos es la forma en que existen los datos. Una estructura de datos es una forma de organizar la información. Su propósito es mejorar la eficiencia de un algoritmo. Generalmente corresponde a un conjunto de algoritmos mediante los cuales se pueden realizar ciertas operaciones sobre los datos en la estructura de datos.

¿Cuál es el principal estudio de la estructura de datos?

La estructura de datos como materia estudia principalmente diversas estructuras lógicas y estructuras de almacenamiento de datos, así como diversas operaciones sobre los datos. Por tanto, existen principalmente tres aspectos: la estructura lógica de los datos; la estructura de almacenamiento físico de los datos y la operación (o algoritmo) de los datos; Por lo general, 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 físico de los datos.

¿Qué es una estructura de datos? ¿Qué son las estructuras lógicas y físicas?

Los datos se refieren a una colección de elementos que consta de un conjunto limitado de símbolos (por ejemplo, "0" y "1", con sus propias estructuras, operaciones y semántica correspondiente). Una estructura es una colección de relaciones entre elementos. En términos generales, una estructura de datos DS se puede expresar como una tupla:

DS=(D, S), //es decir, estructura-datos=(parte-datos, parte-estructura-lógica) Aquí D es un conjunto de elementos de datos (o "nodos", que también pueden contener "elementos de datos" o "campos de datos"), y S es un conjunto de relaciones definidas en D (u otros conjuntos), S =, llamado es el sistema lógico estructura de los elementos. Hay cuatro tipos básicos de estructuras lógicas: estructura de conjunto, estructura lineal, estructura de árbol y estructura de red. Las tablas y los árboles son las dos estructuras de datos eficientes más utilizadas y se pueden diseñar e implementar muchos algoritmos eficientes utilizando estas dos estructuras de datos. Las tablas son estructuras lineales (relaciones de orden total), los árboles (orden parcial o relaciones jerárquicas) y los gráficos (órdenes débiles/locales) son estructuras no lineales.

La estructura física de la estructura de datos se refiere a la imagen de almacenamiento de la estructura lógica. La estructura física P de la estructura de datos DS corresponde a un mapeo de los elementos de datos de DS al área de almacenamiento M (que mantiene la estructura lógica S):

(PD, S) -- gt; Modelo de memoria: una memoria M es una serie de unidades de almacenamiento de tamaño fijo. Cada unidad U tiene una dirección única A (U), que está codificada continuamente. Cada unidad U tiene una unidad sucesora única U'=succ(U). Hay cuatro modelos básicos de mapeo de P: mapeo secuencial, vinculado, indexado y hash.

Por lo tanto, podemos obtener al menos 4×4 posibles estructuras de datos físicos:

secuenciales (conjuntos)

listas enlazadas

indexadas árboles

gráficos hash

(No todas las combinaciones posibles son razonables)

Operaciones sobre la estructura de datos DS: Todas las operaciones definidas en el DS La estructura lógica y física del DS debe mantenerse al cambiar elementos de datos (nodos) o los campos de los nodos.

Operaciones básicas en DS: Cualquier otra operación avanzada en DS se puede implementar utilizando estas operaciones básicas. Es mejor pensar en el DS y todas sus operaciones básicas como un todo: llámelo módulo.

Podemos abstraer aún más este módulo en un tipo de datos (donde la estructura de almacenamiento de DS se representa como un miembro privado y las operaciones básicas se representan como métodos públicos), llamado ADT. Como ADT, las pilas y las colas son tipos especiales de tablas que tienen un subconjunto de operaciones de la tabla. Las operaciones avanzadas para DAT se pueden diseñar como algoritmos (no encapsulados), utilizando operaciones básicas para procesar DS.

DS bueno y malo: Si un DS se puede transformar en un DS lineal (como una tabla lineal) mediante alguna "regla lineal", se llama DS bueno. Un buen DS suele corresponder a un buen algoritmo (eficiente). Esto está determinado por la potencia de cálculo de la computadora, porque la computadora esencialmente solo puede acceder a unidades de memoria lógicamente continuas, por lo que las estructuras sin linealización son lógicamente no computables. Por ejemplo, cuando se opera en un gráfico, para acceder a todos los nodos del gráfico, se deben visitar todos los nodos en un orden determinado (para formar un orden parcial) y la estructura no lineal inherente del gráfico se debe convertir en una estructura lineal en de alguna manera para operar en la imagen.

Los árboles son buenos DS: tienen reglas de linealización muy simples y eficientes, por lo que se pueden diseñar muchos algoritmos muy eficientes utilizando árboles. La implementación y el uso de árboles son simples, pero pueden resolver una gran cantidad de problemas complejos especiales. Por lo tanto, los árboles son la estructura de datos más importante y útil en la programación práctica. La estructura del árbol es inherentemente recursiva: cada nodo hoja puede ser reemplazado por un subárbol y viceversa. De hecho, cada estructura recursiva se puede transformar en (o equivalente a) una estructura de árbol.

Abstracción del lenguaje de máquina al lenguaje de alto nivel

Sabemos que un algoritmo se define como una secuencia de operaciones. Todas las operaciones en esta secuencia de operaciones se definen en un tipo específico de modelo de datos y están dirigidas a resolver un tipo específico de problema. Esta secuencia de operaciones debe tener las siguientes cuatro características. Finitud, es decir, el número de elementos en la secuencia es limitado y cada elemento de operación se puede completar en un tiempo limitado, es decir, cada operación de la secuencia tiene una definición clara y no puede haber ninguna entrada; elementos de operación, pero debe haber un término de operación de salida, es decir, para cualquier entrada legal dada, se puede obtener la salida correcta correspondiente; Estas características se pueden utilizar para determinar si una determinada secuencia de operaciones puede denominarse algoritmo. Sin embargo, nuestro problema actual no es juzgar si una determinada secuencia de operaciones puede llamarse algoritmo, sino revisar cómo utilizamos el lenguaje de programación para expresar una secuencia de operaciones que ya es un algoritmo.

La expresión del programa de un algoritmo es, en última instancia, la expresión del programa de los elementos del algoritmo, porque una vez que un programa expresa claramente cada elemento del algoritmo, la expresión del programa de todo el algoritmo no será un problema.

Un algoritmo como secuencia de operaciones tiene tres elementos. Datos que son el operando y el resultado de varias operaciones en la secuencia de operaciones; varias operaciones en la secuencia de operaciones transfieren el control en la secuencia de operaciones; Estos tres elementos se denominan datos, operación y control respectivamente en ese orden. Dado que los algoritmos surgen uno tras otro y están en constante cambio, los datos de los objetos sobre los que actúan las operaciones y los datos de los resultados obtenidos son numerosos, demasiado numerosos para enumerarlos. Los más simples y básicos incluyen datos booleanos, datos de caracteres, datos de números enteros y reales, etc.; los un poco más complejos incluyen vectores, matrices, registros y otros datos; los más complejos también incluyen conjuntos, árboles y gráficos; como sonidos, gráficos, imágenes y otros datos. Además, debido a que los algoritmos surgen sin cesar y cambian constantemente, los tipos de operaciones son diversos y coloridos. Las más básicas y elementales incluyen operaciones de asignación, operaciones aritméticas, operaciones lógicas y operaciones relacionales, etc.; las un poco más complejas incluyen expresiones aritméticas y expresiones lógicas, etc.; las más complejas incluyen cálculos de valores de funciones, operaciones vectoriales, matrices; operaciones, operaciones de conjuntos y operaciones sobre tablas, pilas, colas, árboles y gráficos, etc.: Además, puede haber combinación y anidamiento de las operaciones enumeradas anteriormente. En cuanto a la transferencia de control, es relativamente sencillo. En los cálculos en serie, solo existen varios tipos: secuencia, rama, bucle, recursividad y transferencia incondicional.

Repasemos qué proceso ha pasado la expresión del programa de los tres elementos anteriores del algoritmo desde la llegada de las computadoras.

El lenguaje de programación más antiguo es el lenguaje de máquina, que es un conjunto de instrucciones en una computadora específica. En ese momento, todos los algoritmos que se ejecutaban en una computadora tenían que expresarse directamente en lenguaje de máquina para que la computadora los aceptara. La secuencia de operaciones del algoritmo, incluidos los operandos y los resultados de las operaciones, debe convertirse en una secuencia de instrucciones. Cada instrucción aparece en forma de codificación (código de instrucción y código de dirección). Los algoritmos expresados ​​en lenguaje algorítmico son muy diferentes entre sí. Para las personas que no han recibido una formación especial en programación, un programa es como un "libro celestial", incomprensible y de lectura extremadamente pobre.

Utilizar el lenguaje de máquina para expresar las operaciones, datos y control de algoritmos es muy complicado y trivial porque las instrucciones proporcionadas por el lenguaje de máquina son demasiado elementales y primitivas. El lenguaje de máquina solo acepta operaciones aritméticas, operaciones lógicas bit a bit y operaciones de comparación de números. Para operaciones un poco más complejas, se deben descomponer una por una hasta llegar a la operación más elemental antes de poder reemplazarla con la instrucción correspondiente. Los únicos tres tipos de datos que pueden expresarse directamente mediante lenguaje de máquina son bits, bytes y palabras. Incluso los datos más simples del algoritmo, como valores booleanos, caracteres, números enteros y números reales, deben asignarse uno por uno en bits, bytes y palabras

, y sus unidades de almacenamiento deben asignarse una por uno. La expresión de datos estructurados en algoritmos es mucho más problemática. Las instrucciones de transferencia de control proporcionadas por el lenguaje de máquina son solo las más básicas, como transferencia incondicional, transferencia condicional, ingreso a subrutina y regreso de subrutina. Usarlos para construir bucles, formar ramas y llamar a funciones y procedimientos requiere mucha preparación previa y muchas habilidades. Expresar algoritmos directamente en lenguaje de máquina tiene muchas desventajas.

Una gran cantidad de detalles complicados y triviales limitan a los programadores, haciéndoles imposible tener más tiempo y energía para dedicarse al trabajo creativo y realizar tareas que son más importantes para ellos. Como garantizar la corrección y eficiencia del programa. Los programadores no sólo deben controlar la situación general de la programación, sino también profundizar en cada parte hasta los detalles de implementación. Incluso los programadores con inteligencia superior a menudo se concentran en una cosa y pasan por alto la otra y cometen errores frecuentes. Como resultado, los programas que compilan son deficientes. Fiabilidad y largos ciclos de desarrollo. Dado que la forma de pensar y expresar la programación en lenguaje de máquina es muy diferente de los hábitos de las personas, sólo los programadores que hayan pasado por un largo período de formación profesional pueden ser competentes, lo que hace que la programación sea de alto nivel. Debido a que su forma escrita es todo un código "secreto", tiene poca legibilidad y es inconveniente para la comunicación y la cooperación. Debido a que depende en gran medida de la computadora específica, tiene poca portabilidad y reutilización. Estas deficiencias provocaron que las aplicaciones informáticas de aquella época no se promocionaran rápidamente.

La forma de superar las deficiencias anteriores radica en la abstracción de los lenguajes de programación para acercarlos lo más posible a los lenguajes algorítmicos. Con este fin, lo primero que la gente nota es la legibilidad y la portabilidad, ya que se mejoran con relativa facilidad mediante la abstracción. Como resultado, pronto apareció el lenguaje ensamblador. La abstracción del lenguaje de máquina por parte de este lenguaje se manifiesta primero en la simbolización de cada instrucción del lenguaje de máquina: el código de instrucción se reemplaza por un símbolo de memoria y el código de dirección se reemplaza por una dirección simbólica, de modo que su significado aparece en el símbolo y ya no está. escondido en él. En la codificación, las personas pueden leer el "texto" y obtener el significado. En segundo lugar, este lenguaje está libre de las limitaciones de computadoras específicas y puede ejecutarse en computadoras con diferentes conjuntos de instrucciones, siempre que la computadora esté equipada con un programa ensamblador en lenguaje ensamblador. Este es sin duda un paso hacia el lenguaje de máquina acercándose al lenguaje algorítmico. Sin embargo, todavía está demasiado lejos del lenguaje de algoritmos, por lo que los programadores no pueden liberarse de las complicadas y triviales cuestiones de descomponer los datos, las operaciones y el control del algoritmo en instrucciones que puedan expresarse directamente en ensamblador. A mediados de la década de 1950, aparecieron lenguajes de programación de alto nivel como Fortran, Algol60 y más tarde PL/l, Pascal, etc., y la expresión del programa de algoritmos dio un gran salto.

Es cierto que el algoritmo debe en última instancia expresarse como lenguaje de máquina en una computadora específica para poder ejecutarse en esa computadora y obtener los resultados requeridos. Sin embargo, la práctica del lenguaje ensamblador ha inspirado a la gente a que expresarlo en lenguaje de máquina no tiene por qué hacerse en un solo paso. Se puede hacer en dos pasos o se puede construir un puente para cruzar el río. Es decir, primero se expresa en un lenguaje intermediario y luego se convierte a lenguaje de máquina.

Como lenguaje intermediario, el lenguaje ensamblador no ha logrado un gran éxito porque todavía está demasiado lejos de ser un lenguaje algorítmico. Esto guía a las personas a diseñar un lenguaje estándar que sea lo más cercano posible al lenguaje de algoritmos, es decir, el llamado lenguaje de alto nivel, para que los programadores puedan usarlo para expresar algoritmos de manera conveniente y luego usar la "traducción" de del lenguaje estándar de alto nivel al lenguaje de máquina estándar. Finalmente, el algoritmo se expresa en lenguaje de máquina. Además, dado que tanto los lenguajes de alto nivel como los lenguajes de máquina son normativos, la "traducción" aquí puede ser completada mecánicamente por una computadora, al igual que el lenguaje ensamblador se traduce al lenguaje de máquina, siempre que la computadora esté equipada con un compilador. Los dos pasos anteriores, el primer paso lo completa el programador y el último paso lo puede completar el compilador. Luego de especificar qué debe hacer cada uno de ellos, estos dos pasos son completamente independientes. Lo que cada uno de ellos debería hacer es irrelevante para el otro. Todo lo que hay que hacer en el primer paso es expresar correctamente el algoritmo dado en un lenguaje de alto nivel y generar un programa de lenguaje de alto nivel. Todo lo que hay que hacer en el último paso es traducir el lenguaje de alto nivel; programa obtenido en el primer paso en un programa en lenguaje de máquina. En cuanto a cómo los programadores expresan algoritmos en lenguajes de alto nivel y cómo los compiladores traducen algoritmos expresados ​​en lenguajes de alto nivel en algoritmos expresados ​​en lenguaje de máquina, obviamente son irrelevantes.

La forma de pensar antes mencionada que aborda el complejo proceso de expresión final desde el lenguaje algorítmico al lenguaje de máquina es una abstracción. La aparición del lenguaje ensamblador y los lenguajes de alto nivel son ejemplos de esta abstracción. En comparación con el lenguaje ensamblador, el gran éxito del lenguaje de alto nivel es que introduce muchos conceptos y herramientas cercanos al lenguaje algorítmico en la expresión de datos, operación y control, lo que mejora en gran medida la capacidad de expresar algoritmos de manera abstracta. En términos de operaciones, los lenguajes de alto nivel como Pascal no solo permiten que las cuatro operaciones aritméticas, operaciones lógicas, operaciones relacionales, expresiones aritméticas y expresiones lógicas de los lenguajes algorítmicos se utilicen intactas, sino que también introducen poderosas funciones y herramientas de procedimiento y permiten las definidas por el usuario. La importancia de esta herramienta no es sólo que reduce los segmentos de texto repetitivos del programa, sino también que refleja los dos niveles de abstracción del programa.

A nivel de llamada de función y procedimiento, a la gente sólo le importa lo que puede hacer, no cómo lo hace. Sólo cuando se definen funciones y procedimientos la gente da detalles de cómo hacerlo. Los lectores que han utilizado lenguajes de alto nivel saben que una vez que los nombres, parámetros y funciones de las funciones y procedimientos están claramente especificados, llamarlos en el programa es completamente independiente de describirlos al principio del programa. Puede modificar o incluso reemplazar cuerpos de funciones y cuerpos de procedimientos sin afectar la forma en que se llaman. Si los nombres de funciones y procedimientos se consideran nombres de operaciones, y los parámetros se consideran objetos de operaciones o resultados de operaciones, entonces

las llamadas a funciones y procedimientos no son diferentes de las referencias a operaciones elementales. . Cualquier operación compleja en un lenguaje algorítmico se puede expresar de forma natural mediante funciones y procedimientos y su composición o anidamiento.

En términos de datos, los lenguajes de alto nivel como Pascal introducen el concepto de tipos de datos, que clasifican todos los datos. Cada dato (incluidas las expresiones) o cada variable de datos pertenece a una determinada categoría. Este tipo de datos se llama tipo de datos. Por tanto, un tipo de datos es una descripción genérica de un dato o variable de datos que indica la totalidad de valores que puede tomar el dato o variable de datos. Para datos no estructurados, los lenguajes de alto nivel como Pascal no solo proporcionan tipos de datos básicos estándar: tipos booleanos, de caracteres, enteros y reales, sino que también proporcionan clases de enumeración, tipos de sublímites y tipos de puntero definibles por el usuario. El uso de estos tipos (excepto los punteros) se ajusta a los hábitos de las personas en los lenguajes algorítmicos. Para datos estructurados, los lenguajes de alto nivel como Pascal proporcionan cuatro tipos de datos estructurales estándar: matrices, registros, colecciones restringidas y archivos. Entre ellos, las matrices son la abstracción de vectores y matrices en registros informáticos científicos; los conjuntos restringidos son la abstracción de conjuntos potenciales que son lo suficientemente pequeños en matemáticas, los archivos son datos de almacenamiento externo, como los discos. abstracción.

Las personas pueden utilizar los tipos de datos básicos proporcionados (incluidos los estándar y personalizados) para construir datos estructurados de acuerdo con las reglas de construcción de matrices, registros, colecciones restringidas y archivos.

Además, también permite a los usuarios utilizar tipos de datos estructurales estándar para construir datos estructurales más complejos y de mayor nivel mediante combinación o anidamiento. Esto hace que los tipos de datos en lenguajes de alto nivel sean significativamente jerárquicos. La jerarquía de tipos de datos en lenguajes de alto nivel es infinita, por lo que pueden usarse para expresar datos en cualquier nivel complejo en lenguajes algorítmicos. En términos de control, los lenguajes de alto nivel como Pascal proporcionan seis formas de expresar la transferencia de control de algoritmos.

(1) El control de secuencia predeterminado ";".

(2) Control condicional (ramificación): "si la expresión (verdadera) entonces S1 si no S2;".

(3) Control de selección (caso):

"Expresión de caso de

Valor 1: S1

Valor 2: S2

...

Valor n: Sn

end"

(4) Control de bucle:

" mientras que la expresión (verdadera) haga S;" o

"repita S hasta que la expresión (verdadera);" o

"para el nombre de la variable: = valor inicial hasta/baja hasta el valor final haga S ;"

(5) Llamadas a funciones y procedimientos, incluidas llamadas a funciones recursivas y procedimientos recursivos.

(6) Transferencia incondicional de goto.

Estas seis expresiones no solo cubren todos los requisitos de expresión de control en lenguajes algorítmicos, sino que ya no son tan primitivos, engorrosos y oscuros como el lenguaje de máquina o el lenguaje ensamblador, sino como se ve arriba, que es casi lo mismo que la expresión del lenguaje natural. Los principales beneficios que aporta la abstracción del lenguaje de programación del lenguaje de máquina al lenguaje de alto nivel son: El lenguaje de alto nivel está cerca del lenguaje de algoritmos, es fácil de aprender y dominar, y el personal técnico y de ingeniería común puede ser competente como programadores con solo una pocas semanas de capacitación en lenguaje de alto nivel Proporciona a los programadores un entorno y herramientas de programación estructurados, lo que hace que los programas diseñados sean legibles, mantenibles y confiables. Los lenguajes de alto nivel están lejos de los lenguajes de máquina y tienen poco que hacer; con hardware de computadora específico, por lo que el programa escrito tiene buena portabilidad y alta tasa de reutilización, porque los asuntos complicados y triviales se entregan al compilador, el grado de automatización es alto, el ciclo de desarrollo es corto y el programador y los programadores; se sienten aliviados y pueden concentrar su tiempo y energía en participar en el trabajo creativo que es más importante para ellos para mejorar la calidad del programa.

Estructura de datos, tipo de datos y tipo de datos abstractos

Estructura de datos, tipo de datos y tipo de datos abstractos, estos tres términos son literalmente diferentes pero similares, lo que refleja sus diferentes significados. Ambos tienen diferencias. y conexiones.

Estructura de datos es un término muy utilizado en todos los campos de la informática y la tecnología. Se utiliza para reflejar la estructura interna de un dato, es decir, de qué componentes está compuesto un dato, cómo está compuesto y qué estructura tiene. Las estructuras de datos se dividen en estructuras de datos lógicas y estructuras de datos físicas. La estructura de datos lógica refleja la relación lógica entre los datos de los componentes y la estructura de datos físicos refleja la disposición de almacenamiento de los datos de los componentes en la computadora. La estructura de datos es la forma en que existen los datos.

Los datos se clasifican según la estructura de datos y los datos con la misma estructura de datos pertenecen a la misma categoría. Todos los datos del mismo tipo se denominan tipo de datos. En los lenguajes de programación de alto nivel, los tipos de datos se utilizan para describir la pertenencia de un dato en la clasificación de datos. Es una propiedad de los datos. Este atributo limita el rango de cambios en estos datos. Para solucionar el problema, los lenguajes de alto nivel definen una serie de tipos de datos según el tipo de estructura de datos. Diferentes lenguajes de alto nivel definen diferentes tipos de datos. Los tipos de tipos de datos definidos por el lenguaje Pascal.

Entre ellos, los tipos de datos simples corresponden a estructuras de datos simples; los tipos de datos construidos corresponden a estructuras de datos complejas; en las estructuras de datos complejas, los datos componentes en sí pueden tener estructuras de datos complejas. permitir el anidamiento compuesto; el tipo de puntero corresponde a la relación entre los datos de los componentes en la estructura de datos. Es un tipo de datos simple en la superficie, pero en realidad apunta a datos de componentes complejos, es decir, datos en el tipo de datos construidos. No se incluyen aquí. Los tipos de datos simples no se clasifican en tipos de datos estructurados, sino que se clasifican como una categoría separada.

La estructura de datos refleja la estructura interna de los datos. A menudo se describe con un diagrama de estructura: cada componente de los datos se considera como un nodo y se representa mediante un cuadro o círculo. está representado por líneas de flechas entre los nodos correspondientes. Si los datos del componente tienen su propia estructura, las estructuras están anidadas. Anidar aquí también permite el anidamiento recursivo.

Debido a la introducción de datos de puntero, es posible construir varias estructuras de datos complejas. Según la relación entre los datos componentes en la estructura de datos, la estructura de datos se puede dividir en lineal y no lineal. En las estructuras de datos no lineales, existen niveles y redes. Dado que los tipos de datos se dividen según las estructuras de datos, un tipo de estructura de datos corresponde a un tipo de datos. Los tipos de datos también se pueden dividir en estructuras lineales y no lineales, jerárquicas y similares a redes según la estructura presentada por los datos en el tipo. Para una variable de datos, la especificación de tipo en un lenguaje de alto nivel debe ser el tipo de datos correspondiente a la estructura de datos de la variable leída. Las estructuras de datos más utilizadas son las estructuras de matrices y las estructuras de registros. Las características de la estructura de la matriz son:

El número de datos del componente es fijo y la relación lógica entre ellos se refleja en el número de serie de los datos del componente (o el subíndice de la matriz). Estos datos de componentes están ordenados uno por uno según la secuencia de números de serie. Los datos de cada componente tienen la misma estructura (puede ser una estructura simple o una estructura compleja) y, por lo tanto, pertenecen al mismo tipo de datos (en consecuencia, un tipo de datos simple o un tipo de datos construido). Este mismo tipo de datos se denomina tipo base. Todos los datos de los componentes están organizados secuencialmente en una unidad de memoria continua. En resumen, una estructura de matriz es una estructura lineal y uniforme a cuyos datos componentes se puede acceder de forma aleatoria.

Debido a que esta estructura tiene estas buenas características, es la más utilizada por las personas. En lenguajes de alto nivel, el tipo de datos correspondiente a la estructura de matriz es el tipo de matriz, es decir, la variable de datos de la estructura de matriz debe describirse como matriz [i] de T0, donde i es el tipo de subíndice de la matriz o estructura, y T0 es el tipo de estructura base. La estructura de registro es otra estructura de datos comúnmente utilizada. Sus características son: al igual que la estructura de matriz, el número de datos de los componentes es fijo. Pero no existe un orden natural entre los datos que los componen: están en pie de igualdad. Cada dato componente se denomina campo y se le asigna un nombre de dominio. Diferentes dominios tienen diferentes nombres de dominio. Diferentes campos permiten diferentes estructuras y, por tanto, diferentes tipos de datos. Al igual que las estructuras de matriz, se puede acceder a ellas de forma aleatoria, pero el acceso depende del nombre de dominio. El tipo de datos correspondiente a la estructura de registro en lenguajes de alto nivel es el tipo de registro. Las variables que registran los datos de una estructura deben declararse como tipo de registro.

El significado de los tipos de datos abstractos se ha descrito específicamente en el párrafo anterior. Puede entenderse como una abstracción adicional de los tipos de datos. Es decir, el tipo de datos y las operaciones sobre el tipo de datos se agrupan y encapsulan. El propósito de introducir tipos de datos abstractos es separar la representación de tipos de datos y la implementación de operaciones sobre tipos de datos de las referencias de estos tipos de datos y operaciones en el programa, haciéndolos independientes entre sí. Para la descripción de un tipo de datos abstracto, además de describir su estructura de datos, también debe describir las operaciones (procedimientos o funciones) definidas en él. Los procedimientos y funciones definidos en un tipo de datos abstractos se basan en la estructura de datos que deben tener los datos del tipo de datos abstractos.

Diseño genérico y estructuras de datos y algoritmos

A continuación me gustaría hablar sobre la última promoción del modelo de programación genérico para estructuras de datos y algoritmos. El pensamiento genérico ha transformado las estructuras de datos en <. /p>

Las ideas básicas de los algoritmos de construcción se han abstraído a un nivel sin precedentes. Ahora existen muchos lenguajes de programación que admiten el diseño genérico, como

ADA, C, y se dice. que en JAVA El diseño genérico también será totalmente compatible con la próxima versión y C#.

Primero hablemos de la idea básica del diseño genérico: la programación genérica (programación genérica, denominada directamente GP en lo sucesivo) es una idea de programación completamente nueva, que es similar a la programación conocida. Conceptos de OO, OB y ​​PO. La diferencia en las ideas de programación es que GP tiene un mayor grado de abstracción. Los componentes diseñados en base a GP tienen un bajo grado de acoplamiento y no tienen relación de herencia, por lo que la interactividad y escalabilidad entre componentes. alto. Todos sabemos que cualquier algoritmo opera en una estructura de datos específica. El ejemplo más simple es que la condición de implementación más fundamental del algoritmo de clasificación rápida es que los objetos ordenados se almacenen en una matriz.

, porque la clasificación rápida. utiliza las características de almacenamiento aleatorio de las matrices, es decir, puede intercambiar objetos distantes dentro de una unidad de tiempo, no solo dos objetos adyacentes, y si se usa una tabla conjunta para almacenar objetos, porque en la tabla conjunta El tiempo para obtener el objeto es lineal , es decir, O[n], lo que hará que la clasificación rápida pierda sus características rápidas. En otras palabras, cuando diseñamos un algoritmo, siempre consideramos primero la estructura de datos de su aplicación, como la búsqueda de matrices, la búsqueda de tablas conjuntas, la búsqueda de árboles y la búsqueda de gráficos. Su núcleo es la búsqueda, pero debido a la estructura de datos. usado Diferente

tendrá muchas manifestaciones diferentes. Una relación tan estrecha entre estructuras de datos y algoritmos siempre ha sido nuestra comprensión previa. La idea fundamental del diseño genérico es separar el algoritmo de la estructura de datos sobre la que actúa, es decir, cuando diseñamos el algoritmo, no consideramos en qué tipo de estructura de datos actuará el algoritmo que diseñamos. El estado ideal del diseño genérico es que un algoritmo de búsqueda pueda operar en varias estructuras de datos, como matrices, tablas vinculadas, árboles, gráficos, etc., y convertirse en un algoritmo genérico universal. ¿No es tentador este ideal?

La programación genérica aporta flexibilidad y abstracción sin precedentes sin pérdida de eficiencia. A diferencia de OO, GP no requiere que llames a funciones a través de capas adicionales de indirección: te permite escribir algoritmos completamente generales que están estandarizados y son reutilizables. tan eficiente como los algoritmos diseñados para estructuras de datos específicas. Todos sabemos que las estructuras de datos se pueden representar mediante tipos definidos por el usuario en C, y la tecnología de plantilla en C usa tipos como parámetros. Entonces puedo imaginar que la tecnología de plantilla se puede usar para implementar la idea de GP con la que comenzamos, es decir, una función de plantilla puede pasar varios tipos en el trabajo, y estos tipos pueden ser varias estructuras de datos que definimos.

Los algoritmos genéricos se abstraen de tipos específicos y estructuras de datos específicas, haciéndolos adaptables a un tipo lo más general posible. El algoritmo en sí es solo para darse cuenta de la esencia lógica que el algoritmo necesita expresar y no ser. Interferido por detalles de implementación de varias estructuras de datos. Esto significa que un algoritmo genérico en realidad consta de dos partes. 1. Instrucciones reales utilizadas para describir la lógica esencial del algoritmo; 2. Un conjunto de requisitos que especifican correctamente las propiedades que deben satisfacer sus tipos de parámetros. A estas alturas creo que mucha gente ya está confundida. Jaja, no importa. Después de todo, GP es una idea de programación con un alto grado de abstracción. Su núcleo es que las condiciones abstractas se convierten en el núcleo del proceso de programación, reemplazando así la posición central de los tipos en OO. Lo que consideramos es que los tipos se convierten en el manto de condiciones abstractas, por lo que llamamos a este tipo de pensamiento programático pensamiento genérico: tipos generalizadores.