TP11_EJ8

[SrMathew]

Buenas tardes profe,

Le queria consultar este ejercicio que hice con Lautaro Bonseñor enfocandolo en forma de vectores y queriamos consultar si respeta el estilo y la eficiencia ya que la solución propuesta utiliza listas. Optamos por esta forma porque pensamos que las funciones serían más sencillas y la consigna indicaba que los elemntos no estan en orden.

Adjunto primero el codigo de conjuntoCDT.c y luego adjunto main.c (test propuesto por la catedra) ya que cambiamos el nombre de las funciones, el mismo responde con "OK!" e incluso con el flag de -sanitize=address

Desde ya muchas gracias por su tiempo

#include <stdlib.h>
#include <stdio.h>
#include "conjuntoADT.h"

#define BLOQUE 10

typedef struct conjuntoCDT{
    compare funcion;
    elemType * vec; 
    char * exists;
    size_t size; // espacio
    size_t dim; // usados
} conjuntoCDT;

conjuntoADT newConjunto( int (*funcion)(elemType a1, elemType a2) ){
    conjuntoADT new = calloc(1, sizeof(conjuntoCDT));
    new->funcion = funcion;
    return new;
}

// esta funcion devuelve -1 si no lo encontro o la posicion en que esta
static int existsInConjunto( conjuntoADT conjunto, elemType elem ){
    if (conjunto->size != 0){
        for (size_t i = 0; i < conjunto->dim; i++){
            if ( conjunto->funcion(conjunto->vec[i],elem) == 0 && conjunto->exists[i] == 1 ){ // existe
                return i;
            }
        }
    }
    return -1;
}

int addToConjunto( conjuntoADT conjunto, elemType elem ){
    // elem ya puede existir
    // si no existe meto al final y agrego un exist y aumento el size
    if ( existsInConjunto(conjunto, elem) == -1 ){
        if ( conjunto->dim == conjunto->size ){
            conjunto->vec = realloc(conjunto->vec, (conjunto->size + BLOQUE) * sizeof(elemType));
            conjunto->exists = realloc(conjunto->exists, (conjunto->size + BLOQUE));
            conjunto->size += BLOQUE;
            for (int i = conjunto->size - BLOQUE; i < conjunto->size; i++)
            {
                conjunto->exists[i]=0;
            }

        }
        conjunto->exists[conjunto->dim] = 1;
        conjunto->vec[conjunto->dim]=elem;
        conjunto->dim++;
        return 1;
    }
    return 0;
}

void deleteFromConjunto(conjuntoADT conjunto, elemType elem){
    int pos = existsInConjunto(conjunto, elem);
    if ( pos != -1 ){
        conjunto->exists[pos] = 0;
        conjunto->dim--;
    }
    return;
}

conjuntoADT unionConjuntos (conjuntoADT conjunto1, conjuntoADT conjunto2 ){
    conjuntoADT new = newConjunto(conjunto1->funcion);
    for (int j = 0; j < conjunto1->size; j++)
    {
        if ( conjunto1->exists[j] == 1 ){
            addToConjunto(new, conjunto1->vec[j]);
        }
    }

    for ( int i = 0; i < conjunto2->size; i++){
        if ( conjunto2->exists[i] == 1){
            addToConjunto(new, conjunto2->vec[i]);
        }
    }
    return new;
}

conjuntoADT interseccionConjuntos (conjuntoADT conjunto1, conjuntoADT conjunto2 ){
    conjuntoADT new = newConjunto(conjunto2->funcion); // set1 = {"amelia", "belen", "carlos"}
    int i;
    for ( i = 0; i < conjunto1->dim; i++){
        if ( conjunto1->exists[i]==1 && existsInConjunto(conjunto2,conjunto1->vec[i])!=-1 ){
            addToConjunto(new, conjunto1->vec[i]);
        }
    }
    printf("inter de miami:\n");
    return new; // carlos
}

conjuntoADT diferenciaConjuntos (conjuntoADT conjunto1, conjuntoADT conjunto2 ){
    conjuntoADT new = newConjunto(conjunto1->funcion);
    for (int j = 0; j < conjunto1->size; j++)
    {
        if ( conjunto1->exists[j] == 1 ){
            addToConjunto(new, conjunto1->vec[j]);
        }
    }
    int i;
    for ( i = 0; i < conjunto2->dim; i++){
        if ( conjunto1->exists[i] && existsInConjunto(conjunto2,conjunto1->vec[i])!=-1 ){
            deleteFromConjunto(new, conjunto1->vec[i]);
        }
    }
    return new;
}

int setContains(conjuntoADT conjunto1, elemType elem){
    if (existsInConjunto(conjunto1,elem) != -1){
        return 1;
    }
    return 0;
}

int sizeSet(conjuntoADT conjunto){
    return conjunto->dim;
}

int isEmptySet(conjuntoADT conjunto){
    return conjunto->dim == 0;
}

void freeSet(conjuntoADT conjunto){
    free(conjunto->vec); 
    free(conjunto->exists);
    free(conjunto);
    return;
}

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include "conjuntoADT.h" 

/* Utilizamos char * como elemType y strcmp como compare */
int main(void) {
    conjuntoADT set1 = newConjunto(strcmp);
    conjuntoADT set2 = newConjunto(strcmp);
    conjuntoADT ans;
    int ok;
    ok = addToConjunto( set1, "amelia" );
    assert( ok && setContains( set1, "amelia" ) );
    ok = addToConjunto( set1, "amelia" );
    assert( ok == 0 );
    addToConjunto( set1, "belen" );
    addToConjunto( set1, "carlos" ); // set1 = {"amelia", "belen", "carlos"}
    addToConjunto( set2, "carlos" );
    addToConjunto( set2, "daniel" );
    addToConjunto( set2, "emilia" ); // set2 = {"carlos", "daniel", "emilia"}

    ans = unionConjuntos( set1, set2 ); 
    assert( setContains(ans, "amelia") && setContains(ans, "daniel"));
    freeSet(ans);

    ans = interseccionConjuntos( set1, set2 );
    assert( setContains(ans, "carlos"));
    assert( setContains(ans, "amelia") == 0);
    freeSet(ans);

    ans = diferenciaConjuntos( set1, set2 );
    assert( setContains(ans, "amelia") && setContains(ans, "carlos") == 0 );
    freeSet(ans);

    deleteFromConjunto( set1, "carlos" );
    ans = interseccionConjuntos(set1, set2);
    assert( isEmptySet(ans) );

    freeSet(set1);
    freeSet(set2);
    freeSet(ans);

    // test con conjuntos de un elemento
    set1 = newConjunto(strcmp);
    set2 = newConjunto(strcmp);
    ok = addToConjunto( set1, "amelia" );
    ok = addToConjunto( set2, "amelia" );
    ans = interseccionConjuntos( set1, set2 );
    assert( setContains(ans, "amelia") == 1 );
    assert(sizeSet(ans)==1);
    freeSet(ans);

    ans = unionConjuntos( set1, set2 );
    assert( setContains(ans, "amelia") == 1 );
    assert(sizeSet(ans)==1);
    freeSet(ans);

    // Diferencia de un conjunto con un solo elemento
    freeSet(set2);
    set2 = newConjunto(strcmp);
    ans = diferenciaConjuntos( set1, set2 );
    assert(sizeSet(ans)==1);

    freeSet(ans);
    freeSet(set1);
    freeSet(set2);

    puts("OK!");
}

[marcelogarberoglio]

No es una buena idea usar vectores para este TAD ya que hace que las funciones para unión, intersección y resta sean muy ineficientes. Para que estas funciones no sean muy ineficientes es necesario que los elementos estén ordenados, entonces conviene usar listas, ya sea que se implementen dentro del TAD o se use el TAD de listas.