Tema 1 - Tipos Abstractos de Datos (TAD)

Nota

Los estudiantes deben convercerse de que la programación no un arte misterioso, sino una disciplina ingenieril…

… la abstracción y la especificación deben ser piezas clave para conseguir una programación efectiva.

• Barbara Liskov: Profesora en el Massachusetts Institute of Technology (MIT); Medalla John von Neumann, 2004; Premio Turing, 2008; Computer Pioneer Award de la IEEE Computer Society, 2018.

• John Guttag: Profesor en el Massachusetts Institute of Technology (MIT).

¿Qué es la abstracción?

1. tr. Separar por medio de una operación intelectual un rasgo o una cualidad de algo para analizarlos aisladamente o considerarlos en su pura esencia o noción.

2. intr. Hacer caso omiso de algo, o dejarlo a un lado.

Consejo

Si la definición de la RAE te ha dejado igual que como estabas. No te preocupes.

La abstracción, entendiéndola como su primera acepción es fundamental tanto en la programación como en cualquier disciplina intelectual.

Gracias al pensamiento abstracto el avance tecnológico/científico humano no parece tener límite.

Un ejemplo sencillo, un conductor no necesita conocer el complicado mecanismo que permite a su coche cambiar las marchas (ni siquiera que son las marchas) del motor. Lo único que debe entender es una implementación (abstracción) “sencilla” como es el embrague y la palanca de cambios y como interactuar con ella.

En el ámbito de la programación la abstracción es constante. Cuando programamos en C, no necesitamos conocer como ha sido implementada la función printf(), solo debemos conocer como interactuar con ella, el formato que acepta que puede o no leer, etc.

Nota

Sí te pica la curiosidad, la función printf() tiene más de 700 líneas de código, si quieres curiosear una de sus implementaciones. Enlace a “printf.c” de coreutils

En este tema nos centraremos en los TADs los Tipos Abstractos de Datos, un tipo de abstracción común y que en el futuro nos resultará muy util.

Definición de Tipo Abstracto de Datos

Nota

Un tipo abstracto de datos es aquel definido por el programador que puede ser manipulado de forma similar a los definidos por el sistema.

Al igual que estos últimos, un tipo abstracto de datos corresponde a un conjunto de valores lícitos y de * operaciones* asociadas a los mismos, operaciones que se definen mediante una especificación que es independiente de la implementación de esos datos.

John Guttag (1974)

A la hora de definir un TAD, debemos seguir unas pautas formales, para obtener la abstracción que facilita el desarrollo a otros/as programadores/as como nosotros/as.

Cargando diagrama...

Código diagrama

flowchart TB
    Diseño[Diseño TAD]

    subgraph Programador[Programador del tipo]
        subgraph Usuario
            Especificación
            Valores
            Operaciones["Operaciones (Sintaxis y Semática)"]
        end
        Implementación
        Representación[Representación del tipo]
        ImpOperaciones[Implementación de las Operaciones]
    end

    Diseño --> Especificación & Implementación
    Especificación -..-> Implementación
    Especificación --> Valores & Operaciones
    Implementación --> Representación & ImpOperaciones

Especificación de un TAD

Nombre_de_operación (tipo_de_argumento) -> tipo_de_resultado

TAD	Nombre_del_tipo
VALORES	valores que pueden tomar los datos del tipo
OPERACIONES	nombre de las operaciones que los manipulan
Objetivo	Descripción de la operación
Entrada	Descripción los datos de entrada
Salida	Que se espera como retorno en invocación
Precondiciones	Que condiciones se esperan de los datos de entrada
Poscondiciones	Que efectos laterales puede tener invocar la función (Que modifica, que añade, etc)

Podemos clasificarlas en:

• Constructoras: Devuelven el TAD
  • Generadoras: Solo ellas pueden generar el TAD
  • Modificadoras: El resto
• Observadoras / Acceso: No devuelve un TAD
• Destructoras: Devuelven el TAD

Ejemplo de especificación de un TAD: Rational

Vamos a crear un TAD para los números racionales, es decir, un par de números enteros: Numerador y denominador

Constructoras Generadoras

• Objetivo: Crea un número racional.

  Entrada: Numerador del nuevo racional y denominador del nuevo racional.

  Precondición: Denominador distinto de 0.

  Salida: El número racional creado.

Constructoras Modificadoras

• Objetivo: Calcula la suma de dos números racionales.

  Entrada: Números racionales a sumar.

  Salida: Un nuevo racional suma de los números a la entrada.

Observadoras

• Objetivo: Obtiene el numerador de un número racional.

  Entrada: Número racional del que obtener el numerador.

  Salida: Numerador del número a la entrada.

• Objetivo: Obtiene el denominador de un número racional.

  Entrada: Número racional del que obtener el denominador.

  Salida: Denominador del número a la entrada.

Rational TAD: El código

Implementación

main.c

// SPDX-FileCopyrightText: Facultade de Informática de A Coruña
//
// SPDX-License-Identifier: CC-BY-4.0

#include <stdio.h>

//#include "rational_struct.h"
//#include "rational_pointer.h"

int main() {
    Rational r1, r2, r3, r4, s;

    r1 = createRational(2, 3);
    r2 = createRational(5, 7);

    r3 = createRational(7, 3);
    r4 = createRational(5, 4);

    s = sum(r1, r2);
    printf("The sum is %d/ %d\n", numerator(s), denominator(s));
    s = sum(r3, r4);
    printf("The sum is %d/ %d\n", numerator(s), denominator(s));
}

rational_pointer.c

// SPDX-FileCopyrightText: Facultade de Informática de A Coruña
//
// SPDX-License-Identifier: CC-BY-4.0

#include <stdlib.h>
#include "rational_pointer.h"

// Operación para crear un racional
Rational createRational(int n, int d) {
    Rational temp;

    temp = malloc(sizeof(*temp));
    temp->num = n;
    temp->den = d;
    return temp;
}

// Operación que retorna el numerador de un racional
int numerator(Rational r) {
    return r->num;
}

// Operación que retorna el denominador de un racional
int denominator(Rational r) {
    return r->den;
}

// Operación que retorna la suma de dos racionales
Rational sum(Rational r1, Rational r2) {
    Rational s;

    s = malloc(sizeof(*s));
    s->num = r1->num * r2->den + r2->num * r1->den;
    s->den = r1->den * r2->den;
    return s;
}

rational_pointer.h

// SPDX-FileCopyrightText: Facultade de Informática de A Coruña
//
// SPDX-License-Identifier: CC-BY-4.0

#ifndef TAD_Rational_RATIONAL_POINTER_H
#define TAD_Rational_RATIONAL_POINTER_H

typedef struct Data *Rational;
struct Data {
    int num;
    int den;
};

Rational createRational(int n, int d);

int numerator(Rational r);

int denominator(Rational r);

Rational sum(Rational r1, Rational r2);

#endif // TAD_Rational_RATIONAL_POINTER_H

rational_struct.c

// SPDX-FileCopyrightText: Facultade de Informática de A Coruña
//
// SPDX-License-Identifier: CC-BY-4.0

#include "rational_struct.h"

// Operación para crear un racional
Rational createRational(int n, int d) {
    Rational temp;
    temp.num = n;
    temp.den = d;
    return temp;
}

// Operación que retorna el numerador de un racional
int numerator(Rational r) {
    return r.num;
}

// Operación que retorna el denominador de un racional
int denominator(Rational r) {
    return r.den;
}

// Operación que retorna la suma de dos racionales
Rational sum(Rational r1, Rational r2) {
    Rational s;

    s.num = r1.num * r2.den + r2.num * r1.den;
    s.den = r1.den * r2.den;
    return s;
}

rational_struct.h

// SPDX-FileCopyrightText: Facultade de Informática de A Coruña
//
// SPDX-License-Identifier: CC-BY-4.0

#ifndef TAD_Rational_RATIONAL_STRUCT_H
#define TAD_Rational_RATIONAL_STRUCT_H

typedef struct Data Rational;
struct Data {
    int num;
    int den;
};

Rational createRational(int n, int d);

int numerator(Rational r);

int denominator(Rational r);

Rational sum(Rational r1, Rational r2);

#endif // TAD_Rational_RATIONAL_STRUCT_H

CMakeLists.txt

# SPDX-FileCopyrightText: Facultade de Informática de A Coruña
#
# SPDX-License-Identifier: CC-BY-4.0

cmake_minimum_required(VERSION 3.22)
project(TAD_Rational)

set(CMAKE_C_STANDARD 99)

add_executable(Rational_struct main.c
        rational_struct.c
        rational_struct.h)
add_executable(Rational_pointer main.c
        rational_pointer.c
        rational_pointer.h)

Pablo Portas López © 2025 licensed under CC BY 4.0