[Algoritmi]

[giacomovicinanza]

Salve a tutti. Sto riscontrando alcuni problemi con questo esercizio. Non riesco a risolvere gli errori che si presentano. Qualcuno potrebbe aiutarmi dandomi alcuni suggerimenti? Ringrazio chi mi aiuterà

Nel link che ho postato ci sono le Struct necessiare
https://onlinegdb.com/_2YtSxup1

In allegato ci sono anche gli errori

/* 
 *  Una biblioteca deve riorganizzare alcuni elenchi di libri tra cui elenco1 
 * (un BST), elenco2 (una HT) ed elenco3 (una lista).
 * In ciascuna struttura un libro e' rappresentato da
 * un codice ISBN numerico (campo chiave) e da un titolo. 
 * 
 * Si dovra' realizzare un programma che individui tutti i libri presenti in 
 * entrambi gli elenchi, li stampi in ordine crescente di ISBN (completare nella
 * funzione main) e che sostituisca in elenco2
 * il codice ISBN di un libro in base al titolo.
 * Infine, da elenco3 verranno rimossi tutti i libri con ISBN pari e anche l'elemento
 * con ISBN piu' piccolo.
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 * 
 * 1) BSTHTdupList(bst, ht, list): funzione RICORSIVA che copia in list (lista 
 *    ordinata) tutti i libri che sono presenti contemporaneamente sia in bst che 
 *    in ht (fa fede il codice ISBN).
 * 
 * 2) HTchangeKey(ht, value, newKey): funzione ITERATIVA che sostituisce in ht
 *    la chiave associata a value con la nuova chiave newKey.
 *    Se value non e' presente in ht allora non fa nulla.
 *    Se value compare piu' di una volta in ht allora alle fine ci sara' una sola
 *    coppia (newKey, value). Se newKey e' gia' presente in ht allora il vecchio valore
 *    viene rimosso e poi viene inserito il nuovo valore.
 *
 * 3) listDeleteEven(list): funzione RICORSIVA che elimina da list tutti i 
 *    libri con ISBN pari. Restituisce la lista aggiornata.
 *
 * 4) deleteMinList(list): funzione che elimina il libro con ISBN piu' basso.
 */

#include <stdio.h>
#include <string.h>
#include "THT.h"
#include "TBST.h"
#include "TArray.h"
#include "TList.h"

TList BSTHTdupList(TBST bst, THT *ht, TList list) {
    //CASO BASE: l'albero è vuoto, niente da aggiungere
    if(bst != NULL) {
        //DIVIDE E COMBINA: aggiungo il sotto-albero sinistro (elementi minori)
        list = BSTHTdupList(bst->left, ht, list);
        bst->left = BSTHTdupList(bst->left, ht, list);
        //Aggiungo l'elemento
        list = listInsert(list, bst->info);
        //Aggiungo il sotto-albero destro (elementi maggiori)
        list = BSTHTdupList(bst->right, ht, list);
        bst->right = BSTHTdupList(bst->right, ht, list); 
    }
    return list;
}

void HTchangeKey(THT* ht, TValue value, TKey newKey) {
     TList list = listCreate();
        TNode* node = nodeCreate(list->info);
    if (list == NULL)
        return;
        for (int i = 0; i < ht->n_bucket; i++)
        for (TNode *node = ht->bucket[i]; node != NULL; node = node->link)
                if (HTsearch(ht, list->info.key) == NULL)
                HTinsert(ht, list->info.value, list->info.key);
                list = listInsert(list,node->info);

}

TList listDeleteEven(TList list) {
        /* Caso Base */
    if(list == NULL) {
        return list;
    }
    
    /* Divide et Impera */
    TList tail = listDeleteEven(list->link);
    
    if(listDeleteEven(list->info))
    list->link = tail;
    else {
        nodeDestroy(list);
        list = tail;
    }
    /* Combina */
    return list;
}

TList deleteMinList(TList list) {
    TNode* curr = list;
    TNode* prev;
    
    /* Ricerca degli elementi da cancellare */
    while(curr != NULL) {
        if(infoGreater(curr->info, min) && infoLess(curr->info, max)) {
            prev = curr;
            list = listDelete(list, curr->info);
            curr = prev->link;
        } else curr = curr->link;
    }
    return list;

}

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Le mille e una notte"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Orgoglio e pregiudizio"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Finzioni"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Delitto e castigo"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Il processo"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Madame Bovary"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "L'amore ai tempi del colera"});
    elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Il vecchio e il mare"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Anna Karenina"});

    THT* elenco2 = HTcreate(5);
    HTinsert(elenco2, 3357, (TValue) {"Il rosso e il nero"});
    HTinsert(elenco2, 7675, (TValue) {"Alla ricerca del tempo perduto"});
    HTinsert(elenco2, 4222, (TValue) {"Moby-Dick"});
    HTinsert(elenco2, 1445, (TValue) {"Il processo"});
    HTinsert(elenco2, 3233, (TValue) {"Pippi Calzelunghe"});
    HTinsert(elenco2, 3321, (TValue) {"L'uomo senza qualita'"});
    HTinsert(elenco2, 1111, (TValue) {"Anna Karenina"});
    HTinsert(elenco2, 9090, (TValue) {"Le metamorfosi"});
    HTinsert(elenco2, 3432, (TValue) {"Finzioni"});

    printf("Libri in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nLibri in elenco2 (HT):\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    printf("\nCopio in elenco3 (lista) i libri contenuti sia in elenco1 che elenco2.");
    elenco3 = BSTHTdupList (elenco1, elenco2, elenco3);
    printf("\nLibri in elenco3 in ordine crescente di ISBN:\n");
    
    /* Completare con la chiamata a funzione corretta */
    listPrint(elenco3);

    TValue titolo = (TValue) {"Il processo"};
    TKey nuovoISBN = 1000;
    printf("\nCambio in elenco2 (HT) il codice di '%s' in %d", titolo.titolo, nuovoISBN);
    HTchangeKey(elenco2, titolo, nuovoISBN);
    printf("\nLibri in elenco2 dopo la modifica:\n");
    HTprint(elenco2);

    elenco3 = listDeleteEven(elenco3);
    printf("\nStudenti in elenco3 (Lista)\n(dopo aver rimosso gli ISBN pari)\n");
    listPrint(elenco3);
    
    elenco3 = deleteMinList(elenco3);
    printf("\nLibri in elenco3 (Lista)\n(tutti quelli di elenco3 tranne ISBN piu' basso)\n");
    listPrint(elenco3);

    BSTdestroy(elenco1);
    HTdestroy(elenco2);
    listDestroy(elenco3);
    return 0;
}

[vict85]

Le strutture sono fornite dal professore? Sembra che la hash table sia fatta per memorizzare dati diversi. Nota che un ISBN di un libro è un numero di 13 cifre. Quindi il valore massimo è \(10^{14}-1\) che non può essere salvato in un intero (con segno) a 32 bit. Devi per forza utilizzare un intero (meglio senza segno) a 64 bit. Ti suggerisco di usare il typedef uint64_t fornito nella libreria standard . Non vi è comunque alcun posto per il titolo (si tratta probabilmente di una libreria per un problema diverso).

Nota che listCreate crea un puntatore a NULL, quindi fare link->info dopo averlo chiamato fa crashare il programma.

Le funzioni che hai implementato nel main non fatto quello che viene richiesto, quindi per correggerti il codice dovrei mettermi a riscrivere le tue funzioni e, probabilmente, anche quelle fornite dal professore (che non mi paiono di gran qualità). Non mi sembra il caso.

Comincia a mettere a posto le strutture.

[giacomovicinanza]

https://onlinegdb.com/-Z8uhkELV_ Ho aggiornato il codice

/* 
 *  Una biblioteca deve riorganizzare alcuni elenchi di libri tra cui elenco1 
 * (un BST), elenco2 (una HT) ed elenco3 (una lista).
 * In ciascuna struttura un libro e' rappresentato da
 * un codice ISBN numerico (campo chiave) e da un titolo. 
 * 
 * Si dovra' realizzare un programma che individui tutti i libri presenti in 
 * entrambi gli elenchi, li stampi in ordine crescente di ISBN (completare nella
 * funzione main) e che sostituisca in elenco2
 * il codice ISBN di un libro in base al titolo.
 * Infine, da elenco3 verranno rimossi tutti i libri con ISBN pari e anche l'elemento
 * con ISBN piu' piccolo.
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 * 
 * 1) BSTHTdupList(bst, ht, list): funzione RICORSIVA che copia in list (lista 
 *    ordinata) tutti i libri che sono presenti contemporaneamente sia in bst che 
 *    in ht (fa fede il codice ISBN).
 * 
 * 2) HTchangeKey(ht, value, newKey): funzione ITERATIVA che sostituisce in ht
 *    la chiave associata a value con la nuova chiave newKey.
 *    Se value non e' presente in ht allora non fa nulla.
 *    Se value compare piu' di una volta in ht allora alle fine ci sara' una sola
 *    coppia (newKey, value). Se newKey e' gia' presente in ht allora il vecchio valore
 *    viene rimosso e poi viene inserito il nuovo valore.
 *
 * 3) listDeleteEven(list): funzione RICORSIVA che elimina da list tutti i 
 *    libri con ISBN pari. Restituisce la lista aggiornata.
 *
 * 4) deleteMinList(list): funzione che elimina il libro con ISBN piu' basso.
 */

#include <stdio.h>
#include <string.h>
#include "THT.h"
#include "TBST.h"
#include "TArray.h"
#include "TList.h"

TList BSTHTdupList(TBST bst, THT *ht, TList list) {
    //CASO BASE: l'albero è vuoto, niente da aggiungere
    if(bst != NULL) {
        //DIVIDE E COMBINA: aggiungo il sotto-albero sinistro (elementi minori)
        list = BSTHTdupList(bst->left, ht, list);
        bst->left = BSTHTdupList(bst->left, ht, list);
        //Aggiungo l'elemento
        list = listInsert(list, bst->info);
        //Aggiungo il sotto-albero destro (elementi maggiori)
        list = BSTHTdupList(bst->right, ht, list);
        bst->right = BSTHTdupList(bst->right, ht, list); 
    }
    return list;
}

void HTchangeKey(THT* ht, TValue value, TKey newKey) {
     TList list = listCreate();
        TNode* node = nodeCreate(list->info);
    if (list == NULL)
        return;
        for (int i = 0; i < ht->n_bucket; i++)
        for (TNode *node = ht->bucket[i]; node != NULL; node = node->link)
                if (HTsearch(ht, list->info.key) == NULL)
                HTinsert(ht, list->info.key, list->info.value);
                list = listInsert(list,node->info);

}

TList listDeleteEven(TList list) {
        /* Caso Base */
    if(list == NULL) {
        return list;
    }
    
    /* Divide et Impera */
    TList tail = listDeleteEven(list->link);
    
    if(listDeleteEven(list->link))
    list->link = tail;
    else {
        nodeDestroy(list);
        list = tail;
    }
    /* Combina */
    return list;
}

TList deleteMinList(TList list) {
    TNode* curr = list;
    TNode* prev;
    TInfo min, max;
    
    /* Ricerca degli elementi da cancellare */
    while(curr != NULL) {
        if(infoGreater(curr->info, min) && infoLess(curr->info, max)) {
            prev = curr;
            list = listDelete(list, curr->info);
            curr = prev->link;
        } else curr = curr->link;
    }
    return list;

}

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Le mille e una notte"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Orgoglio e pregiudizio"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Finzioni"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Delitto e castigo"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Il processo"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Madame Bovary"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "L'amore ai tempi del colera"});
    elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Il vecchio e il mare"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Anna Karenina"});

    THT* elenco2 = HTcreate(5);
    HTinsert(elenco2, 3357, (TValue) {"Il rosso e il nero"});
    HTinsert(elenco2, 7675, (TValue) {"Alla ricerca del tempo perduto"});
    HTinsert(elenco2, 4222, (TValue) {"Moby-Dick"});
    HTinsert(elenco2, 1445, (TValue) {"Il processo"});
    HTinsert(elenco2, 3233, (TValue) {"Pippi Calzelunghe"});
    HTinsert(elenco2, 3321, (TValue) {"L'uomo senza qualita'"});
    HTinsert(elenco2, 1111, (TValue) {"Anna Karenina"});
    HTinsert(elenco2, 9090, (TValue) {"Le metamorfosi"});
    HTinsert(elenco2, 3432, (TValue) {"Finzioni"});

    printf("Libri in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nLibri in elenco2 (HT):\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    printf("\nCopio in elenco3 (lista) i libri contenuti sia in elenco1 che elenco2.");
    elenco3 = BSTHTdupList (elenco1, elenco2, elenco3);
    printf("\nLibri in elenco3 in ordine crescente di ISBN:\n");
    
    /* Completare con la chiamata a funzione corretta */
    listPrint(elenco3);

    TValue titolo = (TValue) {"Il processo"};
    TKey nuovoISBN = 1000;
    printf("\nCambio in elenco2 (HT) il codice di '%s' in %d", titolo, nuovoISBN);
    HTchangeKey(elenco2, titolo, nuovoISBN);
    printf("\nLibri in elenco2 dopo la modifica:\n");
    HTprint(elenco2);

    elenco3 = listDeleteEven(elenco3);
    printf("\nStudenti in elenco3 (Lista)\n(dopo aver rimosso gli ISBN pari)\n");
    listPrint(elenco3);
    
    elenco3 = deleteMinList(elenco3);
    printf("\nLibri in elenco3 (Lista)\n(tutti quelli di elenco3 tranne ISBN piu' basso)\n");
    listPrint(elenco3);

    BSTdestroy(elenco1);
    HTdestroy(elenco2);
    listDestroy(elenco3);
    return 0;
}

[giacomovicinanza]

"vict85":Le strutture sono fornite dal professore? Sembra che la hash table sia fatta per memorizzare dati diversi. Nota che un ISBN di un libro è un numero di 13 cifre. Quindi il valore massimo è \(10^{14}-1\) che non può essere salvato in un intero (con segno) a 32 bit. Devi per forza utilizzare un intero (meglio senza segno) a 64 bit. Ti suggerisco di usare il typedef uint64_t fornito nella libreria standard . Non vi è comunque alcun posto per il titolo (si tratta probabilmente di una libreria per un problema diverso).

Nota che listCreate crea un puntatore a NULL, quindi fare link->info dopo averlo chiamato fa crashare il programma.

Le funzioni che hai implementato nel main non fatto quello che viene richiesto, quindi per correggerti il codice dovrei mettermi a riscrivere le tue funzioni e, probabilmente, anche quelle fornite dal professore (che non mi paiono di gran qualità). Non mi sembra il caso.

Comincia a mettere a posto le strutture.

E' stato tutto fornito dal professore, l'esercizio richiede di implementare le funzioni e di completare con la chiamata a funzione corretta

[vict85]

Al di là dell'ISBN che tanto lui non ha messo come vero ISBN, direi che devi fare questa modifica in TInfo.h:
Convertire

typedef struct { 
    char nome[20]; 
    char cognome[20]; 
} TValue;

in

typedef struct { 
    char titolo[40]; 
} TValue;

O puoi anche tenere 20, ma immagino i titoli siano più lunghi dei nomi e cognomi.

Devi anche cambiare infoPrint, altrimenti non compila.

Riguardo a BSTHTdupList conviene prima fare la parte destra e poi la sinistra perché almeno inserisci i nuovi elementi all'inizio invece che alla fine della lista. Insomma così:

TList BSTHTdupList(TBST bst, THT *ht, TList list)
{
    //CASO BASE: l'albero è vuoto, niente da aggiungere
    if (bst == NULL)
    {
        return list;
    }

    list = BSTHTdupList(bst->right, ht, list);

    TValue *found = HTsearch(ht, bst->info.key);
    if (found != NULL)
    {
        list = listInsert(list, bst->info); // verra' inserito all'inizio
    }

    return BSTHTdupList(bst->left, ht, list);
}

Mancava totalmente la ricerca dell'elemento in ht. Fare destra -> centro -> sinistra è per ottimizzare gli inserimenti supponendo che sinistra < centro < destra.

Per quanto riguarda HTchangeKey, io farei così:
[list=1][*:3eb1em25] elimina tutte le occorrenze di value in ht e contale[/*:m:3eb1em25]
[*:3eb1em25] se il numero di eliminazioni è 0, allora ritorni[/*:m:3eb1em25]
[*:3eb1em25] elimina l'elemento associato a newKey se presente[/*:m:3eb1em25]
[*:3eb1em25] aggiungi (newKey, value).[/*:m:3eb1em25][/list:o:3eb1em25]
Il tutto non può essere fatto con le funzioni fornite dal professore (tranne eliminare l'elemento associato a newKey). Sinceramente la libreria che ha scritto il professore è poco adatta ai problemi che vuole risolvere.

In listDeleteEven(list) non capisco cosa tu voglia fare. Insomma io farei così:
[list=1][*:3eb1em25] Se list è nulla, ritorna NULL[/*:m:3eb1em25]
[*:3eb1em25] Se il key è pari, allora ritorna listDeleteEven(list->link). Insomma elimini la testa.[/*:m:3eb1em25]
[*:3eb1em25] Nel restante di casi, list->link = listDeleteEven(list->link);[/*:m:3eb1em25]
[*:3eb1em25]Infine ritorni list[/*:m:3eb1em25][/list:o:3eb1em25]

[giacomovicinanza]

Grazie mille mi metto subito al lavoro Consigli preziosi

[giacomovicinanza]

https://onlinegdb.com/U6cdSa1zZ Ho riscritto le funzioni come me le hai consigliate ma ancora non funzionano :/