Tema 1 - Tipos Abstractos de Datos (TAD)

¿Qué es la abstracción?

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.
intr. Hacer caso omiso de algo, o dejarlo a un lado.

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.

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

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

// 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));
}

// 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;
}

// 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

// 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;
}

// 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

# 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)