Implementación de un TDA en C

Interfaz vs Implementacion

Para separar la interfaz del TDA, es decir aquellas funciones y tipos que el programador "usuario" utilizará, de los detalles de implementación, vamos a utilizar los archivos headers de C. Es decir, los .h.

    • Interfaz: declarada en el archivo .h
    • Implementación: declarada en el .c

Y el programa de prueba o cliente deberá símplemente incluir el .h

#include "lista.h"

Definiendo la interfaz

Dentro del .h vamos a definir:

    • Los tipos: typedef y structs
    • Los "prototipos" de las funciones (es decir, las firmas, pero no la implementación de las funciones).

Ahora, existe un "truco" que se utiliza en estos casos, porque, por un lado necesitamos exponer un tipo de dato (es decir un typedef y un struct), pero por otro lado, no podemos definir la representación interna de los structs, es decir, qué miembros o datos tendrá y de qué tipo.

Para esto:

    • En el .h
    • Se define un "struct" vacío
    • Se define un "typedef" de puntero al struct
    • Todas las funciones van a hacer referencia al tipo "typedef"
    • Luego el .c va a definir un nuevo struct con el mismo nombre que el definido en el .h de esta forma se va a "sobrescribir" el original vacío por el nuevo que sí tendrá los datos.

Ejemplo de .h

struct ListaStruct;
typedef struct ListaStruct* Lista;
// funciones

Y el .c

struct ListaStruct {
    int longitud;
    int* vector;
};

Como vemos ambos structs se llaman iguales. Solo que el segundo tiene realmente datos, cuando el primero está vacío. Como los usuarios del TDA compilan contra el .h, solo verían el struct vacío.

Ejemplo de TDA - Fracciones

Veamos un ejemplo donde queremos modelar los números racionales es decir los que se expresan como el cociente de dos números como 1/4, 2/3, etc.

Definiendo la interfaz (fraccion.h)

Entonces primero definimos en un fraccion.h los tipos

struct FraccionStruct;
typedef struct FraccionStruct* Fraccion;

Acá vemos que el struct está vacío, porque luego lo vamos a definir en la implementación.

Y las operaciones que vamos a exponer:

Fraccion crear(int n, int d);
int numerador(Fraccion x);
int denominador(Fraccion x);
Fraccion sumar(Fraccion x, Fraccion y);
Fraccion restar(Fraccion x, Fraccion y);
Fraccion multiplicar(Fraccion x, Fraccion y);
Fraccion dividir(Fraccion x, Fraccion y);
int iguales(Fraccion x, Fraccion y);
Fraccion simplificar(Fraccion fraccion);
void imprimir(Fraccion x);

Ejemplo de Uso

Sin importarnos los detalles de cómo se va a implementar esto, ya estaríamos en condiciones de hacer una aplicación de ejemplo que use estas fracciones. Por ejemplo:

#include <stdio.h>
#include <stdlib.h>
#include "fraccion.h"
int main(void) {
    Fraccion dosQuintos = crear(2, 5);
    imprimir(dosQuintos);
    Fraccion suma = sumar(dosQuintos, crear(2,5));
    imprimir(suma);
    Fraccion sumaSimplificada = simplificar(suma);
    imprimir(sumaSimplificada);
    return EXIT_SUCCESS;
}

Implementación (fraccion.c)

Y por otro lado podemos hacer una implementación redefiniendo el struct e implementando las funciones.

#include <stdlib.h>
#include <stdio.h>
#include "fraccion.h"
struct FraccionStruct {
    int numerador;
    int denominador;
};
Fraccion crear(int n, int d) {
    struct FraccionStruct* fraccion = malloc(sizeof(struct FraccionStruct));
    fraccion->numerador = n;
    fraccion->denominador = d;
    return fraccion;
}
int numerador(Fraccion x) {
    return x->numerador;
}
int denominador(Fraccion x) {
    return x->denominador;
}
Fraccion sumar(Fraccion x, Fraccion y) {
    int numerador = x->numerador * y->denominador + x->denominador * y->numerador;
    int denominador = x->denominador * y->denominador;
    return crear(numerador, denominador);
}
Fraccion restar(Fraccion x, Fraccion y) {
    int numerador = x->numerador * y->denominador - x->denominador * y->numerador;
    int denominador = x->denominador * y->denominador;
    return crear(numerador, denominador);
}
Fraccion multiplicar(Fraccion x, Fraccion y) {
    int numerador = x->numerador * y->numerador;
    int denominador = x->denominador * y->denominador;
    return crear(numerador, denominador);
}
Fraccion dividir(Fraccion x, Fraccion y) {
    int numerador = x->numerador * y->denominador;
    int denominador = x->denominador * y->numerador;
    return crear(numerador, denominador);
}
int iguales(Fraccion x, Fraccion y) {
    return x->numerador * y->denominador == x->denominador * y->numerador;
}
int maximoComunDenominador(int mayor, int menor) {
    if (menor == 0) {
        return mayor;
    }
    if (menor > mayor) {
        return maximoComunDenominador(menor, mayor);
    }
    int resto = mayor % menor;
    return maximoComunDenominador(menor, resto);
}
Fraccion simplificar(Fraccion fraccion) {
    int mcd = maximoComunDenominador(fraccion->numerador, fraccion->denominador);
    int numerador = fraccion->numerador / mcd;
    int denominador = fraccion->denominador / mcd;
    return crear(numerador, denominador);
}
void imprimir(Fraccion x) {
    printf("%d/%d\n", x->numerador, x->denominador);   
}

Si ejecutamos ahora el ejemplo va a imprimir:

2/5
20/25
4/5