Monografías Plus »

Abstracciones de las Estructuras de Datos



Monografias.com
Abstracciones, tipos y mecanismos. MECANISMOS DE ABSTRACCIÓN Abstracción por especificación: Sólo necesitamos conocer qué va a hacer el procedimiento y no cómo funciona. (Encapsulación y ocultación de implement.) Abstracción por parametrización: Un algoritmo, un tipo, o una variable se definen en base a unos parámetros.(Genericidad)
Monografias.com
Abstracciones, tipos y mecanismos. TIPOS DE ABSTRACCIONES Abstraccionesfuncionales Abstracciones de datos Abstraccionesde iteradores Rutinas, funciones, procedimientos Tipos Abstractos deDatos (TAD) Iteradores
Monografias.com
TIPO ABSTRACTO DE DATOS: TIPO DE DATOS: ESTRUCTURA DE DATOS: Dominio abstracto de valores junto con las operaciones aplicables sobre el mismo. Conjunto de valores que puede tomar una variable, un parámetro o una expresión. Disposición en memoria de los datos necesarios para almacenar valores de un tipo.
Monografias.com
Ejemplos TAD: Enteros Tipo de datos: Tipo integer de Pascal, o tipo int de C Estructura de datos: Representación mediante enteros de 16 bits, 32 bits, listas de dígitos (enteros largos), etc.
Monografias.com
La evolución de los lenguajes de programación tiende a introducir cada vez más abstracciones. Lenguajes de bajo nivel (Basic, Fortran, Ensamblador, …) Lenguajes estructurados (Pascal, C,Modula, ADA, …) Lenguajes orientados a objetos (Smalltalk, C++, Java, Eiffel, …)
Monografias.com
La evolución de los lenguajes de programación tiende a introducir cada vez más abstracciones. Soporte de TAD: Lenguajes estructurados (tipos definidos por el usuario): Los datos y las operaciones van aparte. Lenguajes orientados a objetos (clases): Los datos y las operaciones constituyen una unidad.
Monografias.com
Pascal ObjectPascal type Pila = register tope: integer; datos: array [1..10] of integer; end; proc push (i: integer; var p:Pila); proc pop (var p: Pila); func top (p: Pila): integer; type Pila = class private: tope: integer; datos: array [1..10] of integer; public: proc push (i: integer); proc pop; func top: integer; end;
Monografias.com
Pascal ObjectPascal var p1, p2: Pila; i: integer; begin push(10, p1); push(20, p1); pop(p1); i:= top(p1); p1.tope:= 243; i:= top(p1); … var p1, p2: Pila; i: integer; begin p1.push(10); p1.push(20); p1.pop; i:= p1.top; p1.tope:= 243; i:= p1.top; … Error de compilación: “tope” es privado
Monografias.com
Especificaciones: Tipos de notaciones Notaciones informales. Notaciones formales. Algebraicas (o axiomáticas). Operacionales (o constructivas).
Monografias.com
Especificaciones informales. Notación Operación (ent : ; : , ..., sal ) Requiere: Establece restricciones de uso. Modifica: Identifica los datos de entrada que se modifican (si existe alguno). Calcula: Descripción textual del comportamiento de la operación. Abstracciones funcionales.
Monografias.com
Ejemplo 1: Eliminar la repetición en los elementos de un array. Operación QuitarDuplic (ent a: array [entero]) Modifica: a Calcula: Quita los elementos repetidos de a. El límite inferior del array no varía, pero sí lo puede hacer el superior. Ejemplo 2: Buscar un elemento en un array de enteros. Operación Buscar (ent a: array [entero]; x: entero; sal i: entero) Requiere: a debe estar ordenado de forma ascendente. Calcula: Si x está en a, entonces i debe contener el valor del índice de x tal que a[i] = x. Si x no está en a, entonces i = sup+1, donde sup es el índice superior del array a.
Monografias.com
Generalización: una operación está definida independiente-mente de cual sea el tipo de sus parámetros. Ejemplo 3: Eliminar la repetición en los elementos de un array. Operación QuitarDuplic [T: tipo](ent a: array [T]) Requiere: T debe tener una operación de comparación IgualQue(ent T, T; sal booleano). Modifica: a Calcula: Quita los elementos repetidos de a. El límite inferior del array no varía, pero sí lo puede hacer el superior. Ejemplo 4: Buscar un elemento en un array de enteros. Operación Buscar [T: tipo](ent a: array [T]; x: T; sal i: entero) Requiere: T debe tener dos operación de comparación MenorQue(ent T, T; sal bool), Igual(ent T, T; sal bool). a debe estar ordenado de forma ascendente. Calcula: Si x está en a, entonces i debe contener ...
Monografias.com
Ejemplo de especificación informal de funciones:
Monografias.com
Abstracciones de datos. Notación TAD es Descripción Descripción textual del tipo Operaciones Especificación informal de las operaciones de la lista anterior Fin .