Estructura de datos en c++, datos abstractos

Capítulo 4: Tipos de Datos Abstractos.
1.1 Introducción
Proceso de Programación: Fase de modelación: se expresan ciertos aspectos de un problema a través de un modelo formal. En esta etapa, la solución del problema será un algoritmo expresado de manera muy informal. Fase TDA: Aplicando refinamientos por pasos llegamos a un programa en pseudolenguaje . Se crean los tipos de datos abstractos paracada tipo de datos (a excepción de los datos de tipo elemental). La solución al problema será un algoritmo en pseudolenguaje definido sobre tipos de datos abstractos y sus operaciones. Fase Estructuras de datos: Para cada tipo de datos abstracto se elija una representación y se reemplace por sentencias en C. El resultado será un programa ejecutable

Modelo Matemático algoritmo Informal

TDAsalgoritmo pseudolenguaje

Estructuras de datos Programa en C

1.2 Concepto de TDA
Introducción al concepto de TDA Comparación Procedimiento-TDA: • Los procedimientos generalizan el concepto de operador. Evitan al programador limitarse a los operadores incorporados en un lenguaje de programación. El programador es libre de definir sus propios operadores y aplicarlos a operandos que no tienenpor qué ser de tipo fundamental. Ej. : multiplicación de matrices. • Pueden utilizarse para encapsular partes de un algoritmo, localizando en una sección de un programa todas las sentencias que incumben a un aspecto del programa en concreto. Un ejemplo de encapsulación es el uso de un procedimiento para leer todas las entradas y verificar su validez. Definición TDA: Es un modelo matemático con unaserie de operaciones definidas sobre ese modelo. Un ejemplo de TDA son los conjuntos de números enteros con las operaciones de unión, intersección y diferencia. Las operaciones de un TDA pueden tener como operandos no solo los del TDA que se define, sino también otros tipos de operandos, como enteros o de otros TDA, y el resultado de una operación puede no ser un caso de ese TDA.

2

Laspropiedades de generalización y encapsulación, igualmente aplicables a los tipos de datos abstractos:

son

• Los TDA son generalizaciones de los tipos de datos primitivos (enteros, caracteres,...), al igual que los procedimientos son generalizaciones de operaciones primitivas (suma, resta,...). • Un TDA encapsula cierto tipo de datos pues es posible localizar la definición del tipo y todas susoperaciones en una sección del programa. De esta forma, si se desea cambiar la forma de implementar un TDA, se sabe hacia dónde dirigirse. Una vez definido un TDA, éste se puede utilizar como si fuese un tipo de dato primitivo, sin preocuparse por cual sea su implementación. Metodología para la definición de un TDA • Definir el dominio del TDA en donde tomará valores una entidad que pertenezca almodelo matemático del TDA. • Definir los efectos que producen en el dominio del TDA cada una de las operaciones definidas. Especificando sintácticamente las operaciones, indicando las reglas que hay que seguir para hacer referencia a una operación. Especificando semánticamente para conocer que significado o consecuencia tiene cada operación.
3

Dominio de un TDA Formas para describir el dominiode un TDA: • Si el dominio es finito y pequeño, éste puede ser enumerado. Por ejemplo, el dominio del tipo booleano es {true, false}. • Se puede hacer referencia a un dominio conocido de objetos matemáticos. Por ejemplo, el conjunto de los números negativos. • Se puede definir constructivamente. Enumerando unos cuantos miembros básicos del dominio y proporcionando reglas para generar o construirlos miembros restantes a partir de los enumerados. Ejemplo. Dominio de las cadenas de caracteres : 1. Cualquier letra es una cadena. 2. Cualquier cadena seguida de una letra es una cadena. Este tipo de definiciones se llama también definiciones recursivas, ya que hacen referencia a los elementos del dominio definido para crear nuevos elementos. Especificación sintáctica de un TDA Consiste en...