Programación 2: Guión Práctica 3

 

PRÁCTICA 3

TIPO ABSTRACTO DE DATOS IMPLEMENTADOS EN LENGUAJE DE PROGRAMACIÓN C

1. Introducción

Esta práctica introduce el concepto de Tipo Abstracto de Dato para que el estudiante pueda comprender, construir y utilizar esta poderosa herramienta de programación.

Antes de entrar en los detalles de los TADs entendamos antes algunos conceptos básicos. Con la aparición de los lenguajes de programación en los años 60 se definieron los tipos de datos para adicionar un mayor nivel de expresividad a los programas. La mayoría de los lenguajes de programación incluyen tipos de datos predefinidos que pueden ser utilizados por el programador para realizar distintas actividades dentro del desarrollo de un programa, por ejemplo, enteros, punto flotantes, caracteres, etc.

• Dato: En el computador un dato siempre se resume a un conjunto de bits. Un conjunto de reglas sobre esos bits forman un tipo de dato. Por ejemplo: un dato de tipo entero o tipo caracter.
• Valor:Es un elemento perteneciente a un conjunto. Este conjunto representa un tipo de dato y todos sus elementos (valores) deben tener las mismas propiedades.El conjunto define las operaciones que se pueden aplicar a sus valores. Por ejemplo: El valor 2 es un elemento del conjunto siguiente:N = { 1, 2, 3 …… }
• Tipo de Dato:Es la agrupación de un conjunto de valores sobre el cual se puede realizar unconjunto de operaciones. Ejemplo, El tipo de dato fecha podría estar representado por los atributos DIA, MES y AÑO, siendo los tres de tipo entero. Las operaciones aplicables sobre el tipo de dato fecha podrían ser:
  • Mostrar fecha
  • Incrementar día, mes o año
  • Intervalo entre dos fechas

Tipo Abstracto de Dato: un TAD es un conjunto de valores sobre los cuales se aplica un conjunto dado de operaciones que cumplen determinadas propiedades.

En la Wikipedia aparece la siguiente definición: Un tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo.

Los TDA se caracterizan por:

• Definen un tipo de dato e incluye la descripción de todo el comportamiento asociado al dato.
• No están asociados a ninguna implementación.
• El implementar un TAD supone la traducción de las especificaciones del TAD en las sintaxis de un lenguaje de programación en particular.

En realidad, los TAD ya existe en los lenguajes de programación estructurados bajo la forma de los tipos predefinidos, que se pueden considerar como tipos abstractos de datos sencillos.

Si consideramos por ejemplo el tipo de datos de los enteros que ofrece el lenguaje C podemos definirlo determinando los siguientes elementos:

• Cuáles son sus valores: los números enteros dentro del intérvalo [minint, maxint];
• Cuáles son sus operaciones: la suma, la resta, el producto, y el cociente y el resto de la división
• Cuáles son las propiedades que cumplen estas operaciones: hay varias; por ejemplo:
  a+b = b+a,
  a*0 = 0,
  etcétera

2. Trabajo Práctico

En esta sección el estudiante será guiado en la confección de un TAD. Se tomará como ejemplo el TAD. Al mismo tiempo se le mostrará al estudiante como organizar el código fuente de tal manera de cumplir con un estilo de programación estándar para desarrollos de dimensión considerable.

Definición del TAD Cola

EL TAD Cola modela una secuencia de elementos en la que la operación de agregar se realiza por un extremo y la operación de extracción por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Operaciones básicas

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, agregar, push): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar, pop): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

2.1. Realización en Lenguaje de programación C

En está parte del curso sólo se han dado los conceptos básicos, más adelante set tocaran los temas de Programación Paramétrica y Programación Orientada a Objetos, así que está realización se implementará una cola de números enteros. El código del TAD será organizado en tres archivos y su respectivo Makefile:

• cola.h: Archivo cabecera contentivo de las estructuras de datos, variables globales y prototipos de las funciones
• cola.c: Archivo contentivo de la implantación de las funciones del TAD.
• principal.c: Archivo con la función principal (main) donde se harán algunas pruebas del TAD.

Instrucciones:

1. Revisar los programas fuentes, compilar, y ejecutar paso a paso usando el depurador DDD.
2. Usar el comando Display del depurador para observar los cambios en la cola.
3. Usar el comando valgrind para verificar el manejo de la memoria:
   • valgrind –leak-check=full ./principal.exe
4. Agregar las siguientes operaciones:
   1. Unir dos colas en una nueva cola.
   2. Decir si un elemento dado está en una cola.
   3. Eliminar el i-esimo elemento de una cola.

Nota: Las operaciones agregadas deben ser revisadas con la ayuda de las utilidades valgrind y ddd.

Nota de la Práctica 3  para el semestre A-2017: El TDA a usar será el TDA Día de la semana.

Descripción: los valores posible de un día de la semana son Lunes, Martes, Miércoles, Jueves, Viernes, Sábado y Domingo.

Además de las operaciones básicas se debe implementar la aritmética de días de la semana, por ejemplo,  si una instancia de la realización  de esta Clase tiene valor de Lunes y se le suma 1, el nuevo valor debe ser Martes, y si a Lunes se le resta 2 el nuevo valor será Sábado.