listADT

[JuaniRaggio]

Hola buenas tardes, hice esta solucion y me paso el test. Queria saber si esta bien La consigna decia lo siguiente: Se desea implementar un TAD para listas de elementos no repetidos, que permita recorrerla con dos criterios: en forma ascendente o por el orden de inserción de los elementos. El .h:

typedef struct listCDT * listADT;

typedef int elemType;   // Tipo de elemento a insertar, por defecto int

/* Retorna una lista vacía.
*/
listADT newList(int (*compare) (elemType e1, elemType e2));

/* Agrega un elemento. Si ya estaba no lo agrega */
void add(listADT list, elemType elem);

/* Elimina un elemento. */
// void remove(listADT list, elemType elem);

/* Resetea el iterador que recorre la lista en el orden de inserción */
void toBegin(listADT list);

/* Retorna 1 si hay un elemento siguiente en el iterador que
** recorre la lista en el orden de inserción. Sino retorna 0 */
int hasNext(listADT list);

/* Retorna el elemento siguiente del iterador que recorre la lista en el orden de inserción. 
** Si no hay un elemento siguiente o no se invocó a toBegin aborta la ejecución.
*/
elemType next(listADT list);

/* Resetea el iterador que recorre la lista en forma ascendente */
void toBeginAsc(listADT list);

/* Retorna 1 si hay un elemento siguiente en el iterador que
** recorre la lista en forma ascendente. Sino retorna 0 */
int hasNextAsc(listADT list);

/* Retorna el elemento siguiente del iterador que recorre la lista en forma ascendente. 
** Si no hay un elemento siguiente o no se invocó a toBeginAsc aborta la ejecución.
*/
elemType nextAsc(listADT list);

/* Libera la memoria reservada por la lista */
void freeListPrime(listADT list);

Mi .c

#include "listADT.h"
#include <stdlib.h>
#include <assert.h>

// Si bien puede parecer mas complicado, al tener una sola lista, basta con
// borrar el nodo una sola vez, no es necesario tener que primero buscar si
// esta el elemento en la lista ascendente y luego volver a buscarlo en la
// lista de insercion => Va a ser mas corto el problema que tenemos que
// resolver, basta con borrar el nodo que encontremos y mantener los punteros
// anteriores
struct node {
  elemType value;
  struct node * prevInsert;
  struct node * nextInsert;
  struct node * prevIncreasing;
  struct node * nextIncreasing;
};

typedef struct node * header;

typedef int (*fCompare)(elemType, elemType);

struct listCDT {
  header firstInc; // Es el primero de la lista ascendente
  header firstAdded;
  header lastAdded; // Es el ultimo agregado
  header iteratorAdded;
  header iteratorInc;
  fCompare cmp;
};

listADT newList(int (*compare) (elemType e1, elemType e2)) {
  listADT new = malloc(sizeof(*new));
  new->firstInc = NULL;
  new->firstAdded = NULL;
  new->lastAdded = NULL;
  new->iteratorAdded = NULL;
  new->iteratorInc = NULL;
  new->cmp = compare;
  return new;
}

header addListRec(header list, header * lastAdded, fCompare cmp, elemType toAdd) {
  int comparison, isNull = list == NULL;
  if (isNull || (comparison = cmp(list->value, toAdd)) > 0) {
      header new = malloc(sizeof(*new));
      new->value = toAdd;
      new->nextIncreasing = list;
      new->prevInsert = *lastAdded;
      if (*lastAdded != NULL) (*lastAdded)->nextInsert = new;
      *lastAdded = new;
      // Como no hay mas despues, el siguiente va a ser NULL
      new->nextInsert = NULL;
      new->prevIncreasing = isNull ? NULL:list->prevIncreasing;
      if (!isNull) list->prevIncreasing = new;
      return new;
   } else if (comparison < 0) {
      list->nextIncreasing = addListRec(list->nextIncreasing, lastAdded, cmp, toAdd);
   }
   return list; 
}

void add(listADT list, elemType elem) {
  int modifyFirst = list->firstAdded == NULL;
  list->firstInc = addListRec(list->firstInc, &list->lastAdded, list->cmp, elem);
  if (modifyFirst) list->firstAdded = list->firstInc;
}

void toBegin(listADT list) {
  list->iteratorAdded = list->firstAdded;
}

int hasNext(listADT list) {
  return list->iteratorAdded != NULL;
}

elemType next(listADT list) {
  assert(list->iteratorAdded != NULL);
  elemType retValue = list->iteratorAdded->value;
  list->iteratorAdded = list->iteratorAdded->nextInsert;
  return retValue;
}

void toBeginAsc(listADT list) {
  list->iteratorInc = list->firstInc;
}

int hasNextAsc(listADT list) {
  return list->iteratorInc != NULL;
}

elemType nextAsc(listADT list) {
  assert(list->iteratorInc != NULL);
  elemType retValue = list->iteratorInc->value;
  list->iteratorInc = list->iteratorInc->nextIncreasing;
  return retValue;
}

void freeListRec(header list) {
  if (list == NULL)
    return;
  freeListRec(list->nextIncreasing);
  free(list);
}

void freeListPrime(listADT list) {
  freeListRec(list->firstInc);
  free(list);
}

[marcelogarberoglio]

Creo que no es el listADT sino el ejercicio 14 del TP 11. Como no se pedía función para remover no es necesario que tengas puntero al anterior Salvo eso, está bien También se podía resolver con dos listas: una en forma ordenada y otra donde se inserta directamente al final