Ej8 Guia 11.

[romamati]

//Me indica que en la funcion addRec me quedan memory leaks y no entiendo donde me faltaria hacer un free.

include

include

include "ej8ADT.h"

typedef struct node { elemType e; struct node * tail; }Tnode;

typedef Tnode * TList;//Puntero a struct

typedef struct setCDT { compare cmp; size_t size;//Cantidad de nodos de la lista TList first;//Puntero al primer nodo de la lista }setCDT;

//Crea un nuevo stack setADT newSet(compare cmp) { setADT set = calloc(1, sizeof(*set)); set->cmp = cmp; return set; }

static TList addRec(TList l, elemType e, int flag, compare cmp) { int c; if(l == NULL || (c = cmp(l->e, e)) > 0) //En cualquiera de estos casos tengo que adherir al elemento { TList aux = malloc(sizeof(aux)); aux->e = e; aux->tail = l;//Pues lo estoy metiendo antes del elemento actual de la lista *flag = 1;//Indico que pude meter al elemento return aux; //Retorno a la direccion de la lista con las modificaciones a donde la llamen }

if(c < 0)
{
    l->tail = addRec(l->tail, e, flag, cmp);
    return l;
}

//Si llega aca es porque c = 0 y por ende el elemento ya esta en la lista asi que simplemente la retorno tal cual esta
return l;

}

//Adhiere un elemento al set y retorna 1 si lo pudo meter o cero sino int addElement(setADT set, elemType e) { int flag = 0; set->first = addRec(set->first, e, &flag, set->cmp); set->size+=flag; return flag; }

static int ContainsRec(TList l, elemType e, compare cmp) { int c; if(l == NULL || (c= cmp(l->e, e))>0) //En cualquiera de estos casos ya sabemos que el elemento no esta { return 0; }

if(c < 0) 
{
    return ContainsRec(l->tail, e, cmp);//Avanzo pues el elemento podria aparecer despues en mi lista
}

//Si llega aca es porque c = 0 y por ende lo encontro
return 1;

}

//Se fija si el elemento pertenece al set int setContains(setADT set, elemType e) { return ContainsRec(set->first, e, set->cmp); }

static TList unionRec(TList l1, TList l2, size_t * size) { if(l1 == NULL && l2 == NULL) { return NULL; }

if(l2 == NULL || (l1!= NULL && l1->e < l2->e))//En cualquiera de estos casos voy a incorporar al elemento de l1 a la union
{
    TList aux = malloc(sizeof(*aux));
    (*size)++;
    aux->e = l1->e; 
    aux->tail = unionRec(l1->tail, l2, size);//Avanzo solo en l1 pues podrian haber mas elementos que sean menores al actual de l2
    return aux;//Retorno la lista modificada a donde sea que la llamen
}

if(l1 == NULL || (l2!= NULL && l2->e < l1->e)) //En cualquiera de estos casos tengo que agregar al elemento de l2
{
    TList aux = malloc(sizeof(*aux));
    (*size)++;
    aux->e = l2->e;
    aux->tail = unionRec(l1, l2->tail, size);//Avanzo solo en l2
    return aux;
}

//Si llega aca es porque el elemento de l1 es igual al elemento de l2 y por ende agrego al elemento y avanzo en ambas listas
TList aux = malloc(sizeof(*aux));
(*size)++;
aux->e = l1->e;
aux->tail = unionRec(l1->tail, l2->tail, size);
return aux;

}

//Crea un set de rta con la union de los dos sets que recibe como parametro setADT unionSet(setADT s1, setADT s2) { setADT rta = newSet(s1->cmp); size_t size = 0; rta->first = unionRec(s1->first, s2->first, &size); rta->size = size; return rta; }

static void freeSetRec(TList l) { if(l == NULL) { return; }

freeSetRec(l->tail);//Hago que llegue al final
free(l);//Libero cada nodo de la lista
return;

} //Libera toda la memoria del set void freeSet(setADT set) { freeSetRec(set->first); free(set);//Libero al set en si return; }

static TList intersectRec(TList l1, TList l2, size_t * size) { if(l1 == NULL || l2 == NULL)//Si alguna de las listas es vacia no hay nada que hacer pues no hay nada en la interseccion { return NULL; }

TList rta;
if(l1->e == l2->e) //Solo en este caso vamos a agregar al elemento
{
    rta = malloc(sizeof(*rta));
    (*size)++;//Contabilizo al elemento que agrego
    rta->e = l1->e;
    rta->tail = intersectRec(l1->tail, l2->tail, size);
    return rta;
}

if(l1->e < l2->e)
{
    return intersectRec(l1->tail, l2, size);
}

//Si llega aca es porque l1->e > l2->e y por ende solo avanzo en l2
return intersectRec(l1, l2->tail, size);

}

//crea un set de rta con la interseccion de s1 y s2 y lo retorna setADT intersectionSet(setADT s1, setADT s2) { setADT rta = newSet(s1->cmp); size_t size = 0; rta->first = intersectRec(s1->first, s2->first, &size); rta->size = size; //Asigno el tamaño de la rta return rta; }

static TList diffRec(TList l1, TList l2, size_t * size) { if(l1 == NULL) { return NULL; }

TList rta;
if(l2 == NULL || l1->e < l2->e)//En cualquiera de estos casos ya se que el elemento de l1 no aparece en l2
{
    rta = malloc(sizeof(*rta));
    (*size)++;
    rta->e = l1->e;
    rta->tail = diffRec(l1->tail, l2, size);//Avanzo solo en l1 pues podrian quedar mas elementos que sean menores que el actual de l2
    return rta;
}

if(l2->e < l1->e) //Entonces el elemento de l1 podria aparcer despues en l2 y por ello avanzo solo en l2
{
    return diffRec(l1, l2->tail, size);
}

//Si llega aca es porque l1->e = l2->e y entonces simplemente avanzo en ambas listas
return diffRec(l1->tail, l2->tail, size);

}

//Crea un set de rta con todos los elementos de s1 que no estan en s2 setADT diffSet(setADT s1, setADT s2) { setADT rta = newSet(s1->cmp); size_t size = 0; rta->first = diffRec(s1->first, s2->first, &size); rta->size = size; return rta; }

static TList deleteElementRec(TList l, elemType e, int *flag) { if(l == NULL)//Si la lisat es vacia no hay nada que eliminar y retorna NULL { return NULL; }

if(l->e == e)//Entonces elimino
{
    TList aux = l->tail;//Me guardo la direccion del siguiente
    free(l); //Elimino al nodo
    (*flag) = 1;//Disminuyo el size
    return aux;//Retorno la lista modificada a donde se que la llamen
}

//Si llega aca es porque l->e != e y por ende simplemente avanzo en mi lista
l = deleteElementRec(l->tail, e, flag);
return l;

}

//Elimina un elemento del set y retorna la direccion del set modificado. Si no lo puede eliminar pues no esta retorna NULL setADT deleteElement(setADT s, elemType e) { int flag = 0; s->first = deleteElementRec(s->first, e, &flag); s->size-=flag;//Si lo elimino disinuyo el size en 1 return s; }

//Indica si el set que recibe por parametro posee o no posee elementos(si esta vacio retorna 1 y sino 0) int isEmptySet(setADT s1) { return s1->first == NULL; }

//Indica la cantidad de elementos que posee el set size_t sizeSet(setADT s) { return s->size; }

[marcelogarberoglio]

No puedo correrlo con nuestro testeo, hay algunas diferencias, por ejemplo el tipo que devuelve deleteElement. Subí el .h y el man que usaste para probarlo.

[romamati]

Ahh oka! DeleteElement tiene que ser void (ahi lo modifique).

El .h seria este:

ifndef EJ8ADT_H

define EJ8ADT_H

include

typedef struct setCDT setADT; //Siempre tengo que aclarar que es struct aca!!! typedef char elemType; typedef int (*compare)(elemType e1, elemType e2);//Puntero a funcion que compara elementos genericos

//Crea un nuevo stack setADT newSet(compare cmp);

//Adhiere un elemento al set y retorna 1 si lo pudo meter o cero sino int addElement(setADT set, elemType e);

//Se fija si el elemento pertenece al set int setContains(setADT set, elemType e);

//Crea un set de rta con la union de los dos sets que recibe como parametro setADT unionSet(setADT s1, setADT s2);

//Libera toda la memoria del set void freeSet(setADT set);

//crea un set de rta con la interseccion de s1 y s2 y lo retorna setADT intersectionSet(setADT s1, setADT s2);

//Crea un set de rta con todos los elementos de s1 que no estan en s2 setADT diffSet(setADT s1, setADT s2);

//Elimina un elemento del set y retorna la direccion del set modificado. Si no lo puede eliminar pues no esta retorna NULL setADT deleteElement(setADT s, elemType e);

//Indica si el set que recibe por parametro posee o no posee elementos(si esta vacio retorna 1 y sino 0) int isEmptySet(setADT s1);

//Indica la cantidad de elementos que posee el set size_t sizeSet(setADT s);

endif //EJ8ADT_H

[romamati]

Y el Test que estoy corriendo seria este:

include

include

include

include "ej8ADT.h"

//Defino esta funcion porque sino no me toma al strcmp como tipo de funcion a la que apunte compare. int strcmp1(elemType t, elemType s) { int i = 0; while( (t[i] && s[i]) && t[i] - s[i] == 0 ) { i++; } //si saliste porque ambos llegaron a su final entonces son iguales y retorna cero //si saliste porque t llego a su fin pero s no entonces retorna negativo //sino es porque s llego a su fin y t no y por ende retorna positivo

return t[i]-s[i];

}

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

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

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

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

deleteElement( set1, "carlos" );
ans = intersectionSet(set1, set2);
assert( isEmptySet(ans) );

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

// test con conjuntos de un elemento
set1 = newSet(strcmp1);
set2 = newSet(strcmp1);
ok = addElement( set1, "amelia" );
ok = addElement( set2, "amelia" );
ans = intersectionSet( set1, set2 );
assert( setContains(ans, "amelia") == 1 );
assert(sizeSet(ans)==1);
freeSet(ans);

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

// Diferencia de un conjunto con un solo elemento
freeSet(set2);
set2 = newSet(strcmp1);
ans = diffSet( set1, set2 );
assert(sizeSet(ans)==1);

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

puts("OK!");

}

[marcelogarberoglio]

El problema está en el delete, en realidad hay dos problemas

1) Acá hay que usar la función de comparación. if(l->e == e)//Entonces elimino

2) Está mal la llamada, si borrás el tercero perdés también los dos anteriores

l = deleteElementRec(l->tail, e, flag);

al igual que en el add debe ser

l->tail = deleteElementRec(l->tail, e, flag);

por eso los leaks, porque perdías referencia a los anteriores y nunca se liberaban

[romamati]

Ahh perfecto! Muchas gracias.