programación estructurada




Programación Estructurada y Estructura de Datos


Ingeniería En Telemática










Tipos de datos abstractos
Abstracción: Operación mediante la cual la inteligencia llega a formar conocimiento conceptual común a un conjunto de entidades, separando de ellos los datos contingentes e individualespara atender a lo que los constituye esencialmente. Es decir, aislar mentalmente o considerar por separado las cualidades de un objeto.

Tipo de Datos Abstracto (TDA): Es un tipo de datos definido de forma única mediante un tipo y un conjunto dado de operaciones definidas sobre el tipo. Normalmente existe más de un TDA para resolver un problema concreto. La elección de uno u otro dependerá dealgunas características del problema a resolver (disponibilidad de memoria, velocidad de resolución, etc.). Ello implica que cada implementación de un TDA presentará un coste diferente. El coste de un TDA no viene determinado por un sólo factor. En primer lugar se deberá analizar el almacenamiento requerido por los datos y la cantidad de ellos que serán manejados. El segundo aspecto a considerarserá el coste de las operaciones básicas. En el caso de los árboles, por ejemplo, serán los costes de las operaciones de inserción, búsqueda y eliminación. Para calcular el coste de esas operaciones deberán emplearse técnicas de análisis de algoritmos.

Por tanto, el diseño de un TDA (debido al proceso de abstracción) deberá realizarse siguiendo tres pasos fundamentales:

1. Análisis de datos yoperaciones.
2. Elección del Tipo de datos Abstracto.
3. Elección de la Implementación.

Las siguientes definiciones precisan los TDA compuestos básicos.
Conjunto: Colección de elementos tratados con las operaciones unión, intersección, y diferencia de conjuntos.

Arreglo: Colección homogénea de longitud fija tal que cada una de sus componentes pueden ser accedidas individualmente medianteuno (unidimensional) o varios (multidimensional) índices, que serán de tipo ordinal y que indican la posición de la componente dentro de la colección.

Registro: Tipo de datos heterogéneo compuesto por un número fijo de componentes denominadas campos a las que se accede mediante un selector de campo (.).

Matriz: Tiene como tipo el conjunto de matrices definido por las matemáticas y losoperadores asociados a las mismas: obtener elementos, asignar elementos, sumar, restar, negar, producto escala, producto matricial, determinante, inversa y transporte.

Lista o secuencia: Colección homogénea de datos, ordenados según su posición en ella, tal que cada elemento tiene un predecesor (excepto el primero) y un sucesor (excepto el último) y sus operadores asociados son: Insertar, Localizar,Recuperar, Suprimir (elemento p), Suprimir dato (todas las apariciones de x), Anula (vacía lista), Primero (Fin), Imprimir.

En general, el término 'lista' se usa cuando el TDA se implementa sobre memoria principal, mientras que 'secuencia' suele reservarse para implementaciones en memoria secundaria. Como puede observarse, desde el punto de vista lógico, la lista es una estructura de datosdinámica, ya que su tamaño vendrá determinado por el número de elementos a contener. Una lista puede ser implementada de diversas formas. Con los TDA que se han visto hasta ahora se haría mediante arreglos. Así, la lista, que es dinámica, independientemente de su implementación, se realiza mediante una implementación estática. Sin embargo también es posible implementarla dinámicamente mediantepunteros.

LISTA:
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL. En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la...