UNIDAD 1 Introducci n a las estructuras de datos

UNIDAD 1: Introducción a las estructuras de datos.

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.
Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobreellos. Las operaciones básicas son:
Alta, adicionar un nuevo valor a la estructura.
Baja, borrar un valor de la estructura.
Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).
Otras operaciones que se pueden realizar son:
Ordenamiento, de los elementos pertenecientes a laestructura.
Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.


1.1 Tipos de datos abstractos (TDA)

Un TDA es un tipo de dato definido por el programador que se puede manipular de un modo similar a los tipos de datos definidos por el sistema.
• Está formado por un conjunto válido de elementos y un número de operaciones primitivas que se puedenrealizar sobre ellos.
Para la especificación de un tipo abstracto de datos en lenguaje natural (especificación informal) hemos de seguir el siguiente esquema:
TIPO DE DATOS Nombre del tipo (Lista de operaciones)
VALORES: Descripción de los posibles valores
OPERACIONES: Descripción de cada operación
Primero indicaremos el nombre del TAD y citaremos todas las operaciones definidas.En el apartado valores describiremos los posibles valores de los datos de este tipo, pero lo haremos desde un punto de vista abstracto, sin pensar en la posible realización concreta. Finalmente en el apartado operaciones haremos una descripción de cada una de las operaciones definidas sobre el TAD.

Como ya se mencionó, los Lenguajes de Programación Orientados a Objetos son lenguajes formados pordiferentes métodos o funciones y que son llamados en el orden en que el programa lo requiere, o el usuario lo desea. La abstracción de datos consiste en ocultar las características de un objeto y obviarlas, de manera que solamente utilizamos el nombre del objeto en nuestro programa. Esto es similar a una situación de la vida cotidiana. Cuando yo digo la palabra “perro”, usted no necesita que yo lediga lo que hace el perro. Usted ya sabe la forma que tiene un perro y también sabe que los perros ladran. De manera que yo abstraigo todas las características de todos los perros en un solo término, al cual llamo “perro”. A esto se le llama ‘Abstracción’ y es un concepto muy útil en la programación, ya que un usuario no necesita mencionar todas las características y funciones de un objeto cadavez que éste se utiliza, sino que son declaradas por separado en el programa y simplemente se utiliza el término abstracto (“perro”) para mencionarlo.
En el ejemplo anterior, “perro” es un Tipo de Dato Abstracto y todo el proceso de definirlo, implementarlo y mencionarlo es a lo que llamamos Abstracción de Datos.

Los tipos abstractos de datos básicos se clasifican habitualmente, atendiendo a suestructura, en lineales y no lineales.
TAD LINEALES
1.- LISTAS
Esta forma de almacenar elementos consiste en colocarlos en una lista lineal que tiene un enlace por cada elemente para determinar cual es el elemento siguiente. Las listas se utilizan habitualmente para guardar elementos del mismo tipo y se caracterizan porque pueden contener un número indeterminado de elementos y porque siguen un ordenexplícito. La lista de cero elementos se denomina lista vacía.
2.- COLAS
En el contexto de la programación, una cola es una lista en la que los elementos se insertan por un extremo (llamado fondo) y se suprimen por el otro (llamado frente). En esta estructura de datos el primer elemento que entra es el primero en salir. Es un tipo de dato muy común tanto dentro de la informática como en la vida...