dictADT

[pelufoo]

buenas noches, perdon por la hora pero estuve intentando en completar el ejecicio visto hoy y queria saber si era eficiente mas que nada en la funcion eliminarRec. En esa funcion hice que devuelva una nueva lista, nose si esta bien eso o hay una manera mas eficiente sin tener que recorrer la lista entera. Despues tambien en la funcion hecha hoy en clase la de agregar un word nose si me falto copiarlo o no pero en le funcion generica no la recursiva se aumento el size pero no la dimension en el nodo que contiene las listas y la dimension. Dejando eso de lado el test me pasa y me da ok, pero mi duda surgia mas en la eficiencia.Muchas gracias y perdon!

mi CDT:

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "dict.h"
#define MAX ('z' - 'a' + 1)
#define IDX(s) (tolower(*s) - 'a')
#define BLOCK 20
#define validLetter(s) (tolower(s) >= 'a' && tolower(s) <= 'z')

typedef struct node{
    char * word;
    char * def;
    size_t Wlength; //the lenght of the word 
    size_t Dlength; //length of the definition of the word
    struct node * tail;
}node;

// structure that points towards a list of words that starts with the same letter
typedef struct words{
    struct node * first;
    size_t dim; //amount of words in that letter

}Twords;

typedef struct dictCDT{
    struct words alphabet[MAX];
    size_t size;
}dictCDT;

char * copyStr(char * deff, size_t * len, const char * newDeff){
    int i = 0;
    for(; newDeff[i]; i++, (*len)++){
        if(*len % BLOCK == 0){
            deff = realloc(deff, (*len+BLOCK+1) * sizeof(char));
        }
        deff[*len] = newDeff[i];
    }
    deff[*len] = '\0';
    return deff;
}

node * findWordRec(node * l, const char * word, const char * deff, int * flag){
    int c; 
    if(l == NULL || (c = strcmp(word, l->word)) < 0){
        node * new = malloc(sizeof(node));
        size_t len = 0;
        new->def = copyStr(NULL, &len, deff);
        new->Dlength = len;
        new->Wlength = strlen(word) + 1;
        new->word = strcpy(malloc(new->Wlength + 1), word);
        new->tail = l;
        *flag = 1;
        return new;
    }
    if(c==0){
        l->def = copyStr(l->def, &l->Dlength, deff);
        return l;
    }
    l->tail = findWordRec(l->tail, word, deff, flag);
    return l;
}

dictADT newDict(void){
    return calloc(1, sizeof(dictCDT));
}

/* Recibe una palabra y una definición. Si la palabra existe, agrega la nueva
   definición a la  ya existente.
   Si la palabra no existe en el diccionario, la agrega junto con su definición
*/
void addDefinition(dictADT dict, const char * word, const char * deff){
    size_t idx = IDX(word);
    int flag = 0;
    dict->alphabet[idx].first = findWordRec(dict->alphabet[idx].first, word, deff, &flag);
    dict->alphabet[idx].dim += flag;
    dict->size += flag;

}

char * findAndCopyWord(node * l,const char * s){
    if(l == NULL){
        return NULL;
    }
    if(strcmp(l->word, s) == 0){
        char * copy = malloc(l->Dlength + 1);
        strcpy(copy, l->def);
        return copy;
    }
    return findAndCopyWord(l->tail, s);
}

/* Retorna una copia de la definición o NULL si no existe la palabra */
char * getDeff(const dictADT dict, const char * word){
    size_t idx = IDX(word);
    char * copy = findAndCopyWord(dict->alphabet[idx].first, word);
    return copy;
}

char **copyAllWordsRec(node * l,size_t dim, char **vec, size_t index){
    if(dim == 0){
        return vec;
    }
    vec[index] = malloc(strlen(l->word)+1);
    strcpy(vec[index],l->word);
    return copyAllWordsRec(l->tail, dim-1, vec, index+1);

}

/* Retorna un vector ordenado con la copia de todas las palabras que
   comienzan con una letra.
   Si no hay palabras que empiecen con la letra retorna NULL y *dim en cero
*/
char ** wordsBeginWith(const dictADT dict, char letter, size_t * dim){
    if(dict == NULL || !validLetter(letter)){
        *dim = 0;
        return NULL;
    }
    *dim = dict->alphabet[tolower(letter) - 'a'].dim;
    if(*dim == 0){
        return NULL;
    }
    char ** copy = malloc((*dim) * sizeof(char *));
    return copyAllWordsRec(dict->alphabet[tolower(letter) - 'a'].first, *dim, copy, 0);
}

/* Retorna un vector ordenado con la copia de todas las palabras del diccionario
   Si no hay palabras retorna NULL y *dim en cero
*/
char ** words(const dictADT dict, size_t * dim){
    *dim = 0;
    for(int i = 0; i < MAX; i++){
        *dim += dict->alphabet[i].dim;
    }
    if(*dim == 0){
        return NULL;
    }
    char ** allWords = malloc(*dim * sizeof(char *));
    size_t index = 0;
    for(int i = 0; i < MAX; i++){
        if(dict->alphabet[i].dim > 0){
            allWords = copyAllWordsRec(dict->alphabet[i].first, dict->alphabet[i].dim, allWords, index);
            index+= dict->alphabet[i].dim;
        }
    }
    return allWords;
}

node * removeRec(node * l,const char * s){
    if(l == NULL){
        return l;
    }
    if(strcmp(l->word, s) == 0){
        node * aux = l->tail;
        free(l->def);
        free(l->word);
        free(l);
        return aux;
    }
    l->tail = removeRec(l->tail, s);
    return l;
}

/* Remueve la palabra del diccionario. Si no existe no hace nada */
void removeWord(dictADT dict, const char * word){
    int idx = IDX(word);
    dict->alphabet[idx].first = removeRec(dict->alphabet[idx].first, word);
}
// TAREA

void freeRec(node * l){
    if(l == NULL){
        return;
    }
    node * aux = l->tail;
    free(l->def);
    free(l->word);
    free(l);
    freeRec(aux);
}

/* Libera todos los recursos utilizados por el TAD */
void freeDict(dictADT dict){
    for(int i = 0; i < MAX; i++){
        freeRec(dict->alphabet[i].first);
    }
    free(dict);
}

[marcelogarberoglio]

Las palabras están ordenadas, entonces si encontrás una palabra mayor a la que estás buscando tenés que frenar, no seguir invocando recursivamente