Algoritmi e strutture dati

[giacomovicinanza]

Salve a tutti. Sto riscontrando alcuni problemi con questo esericizio. In particolare con la funzione void listPrintReverse_exemption(TList list) ed i due warning che ho postato. Qualcuno potrebbe aiutarmi? Grazie mille


Qui c'è l'esercizio con le strutture apposite
https://onlinegdb.com/uYGAjyTQo

/*
 * Una struttura ospedaliera deve riorganizzare alcuni elenchi di pazienti 
 * tra cui elenco1 (un Binary Search Tree) ed elenco2 (una Hash Table).
 * In ciascuna struttura, un paziente
 * e' rappresentato da un ID (campo chiave di tipo TKey, ossia un intero),
 * dal nome e dal cognome (di tipo TValue, ossia due stringhe).
 * In tutte le strutture coinvolte, i pazienti con esenzione dal ticket
 * vengono indicati con uno 0 finale nel loro ID.
 * 
 * Si dovra' realizzare un programma che sposti tutti i pazienti con esenzione
 * (ID la cui ultima cifra sia 0) da elenco2 ad elenco1, rimuovendo gli
 * eventuali duplicati in conseguenza del travaso. Inoltre, si dovranno copiare in elenco3
 * (una lista ordinata) tutti i pazienti di elenco1, eseguendo anche una stampa
 * dei soli pazienti con esenzione considerando gli ID in ordine decrescente.
 * Bisogna, infine, rimuovere da elenco1 il paziente con ID piu' alto.
 *
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 *    
 * 1) HTtoBST_exemption(ht, bst): funzione ITERATIVA che copia da ht a bst tutti
 *    i pazienti con ID la cui ultima cifra sia 0, rimuovendoli da ht.
 *    Nel caso in cui un paziente di ht gia' esiste in bst,
 *    esso non verra' duplicato (ma verra' comunque rimosso da ht).
 * 2) BSTtoList(bst, list): funzione RICORSIVA che copia da bst a list tutti
 *    i pazienti di bst in ordine crescente di ID.
 * 3) listPrintReverse_exemption(list): funzione RICORSIVA che stampa gli elementi di 
 *    list in ordine inverso (in termini di ID).
 * 4) BSTremoveLast(bst): funzione RICORSIVA che rimuove da bst l'ultimo 
 *    elemento in ordine di ID (ossia il paziente con l'ID piu' alto). 
 *    Restituisce il bst aggiornato.
 * 
 */

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

TBST HTtoBST_exemption(THT* ht, TBST bst) {
    for(int i = 0; i < ht->n_bucket; i++)
    for(TNode *node = ht->bucket[i]; node != NULL; node = node->link)
    if(HTtoBST_exemption(ht, bst->info.key)){
        if(BSTsearch(bst, node->info) == NULL)
        bst = BSTinsert(bst, node->info);
        HTdelete(ht, node->info.key);
    }
    
    return bst;
}

TList BSTtoList(TBST bst, TList list) {
    // Caso base: l'albero è vuoto, niente da aggiungere
    if(bst != NULL){
        //Divide e combina: aggiungo il sotto-albero sinistro (elementi minori)
        list = BSTtoList(bst->left, list);
        
        // Aggiungo l'elemento
        list = listInsert(list, bst->info);
        
        // Aggiungo il sotto-albero destro (elementi maggiori)
        list = BSTtoList(bst->right, list);
        
        return list;
    }

}

void listPrintReverse_exemption(TList list) {
    // Caso base
    if(list == NULL)
    return;
    
    // Divide et Impera
    listPrintReverse_exemption(list->link);
    printf("%d\n",list->info);

}

TBST BSTremoveLast(TBST bst) {
    TInfo min, max;
    
    // Caso base
    if(bst == NULL)
    return 0;
    
    // Divide et Impera (+ combina)
    if(!infoGreater(min, bst->info))
    BSTprint(bst->left);
    if (!infoGreater(min, bst->info) && !infoLess(max, bst->info))
        infoPrint(bst->info);
    if (!infoLess(max, bst->info))
        BSTprint(bst->right);
        
    bst = BSTdelete(bst, bst->info);
    
    return bst;
}

/* Logica applicativa */

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1320, "Mario", "Rossi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2370, "Antonio", "Bianchi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Lucia", "Verdi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Camilla", "Neri"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4443, "Aldo", "Giallini"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4230, "Carlo", "Aranci"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "Maria", "Scarlatti"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2644, "Luigi", "Turchesi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1110, "Giovanni", "Argento"});

    THT *elenco2 = HTcreate(3);
    HTinsert(elenco2, 3351, (TValue) {"Nicola", "Grigetti"});
    HTinsert(elenco2, 7675, (TValue) {"Costanza", "Violetti"});
    HTinsert(elenco2, 4260, (TValue) {"Filippa", "Azzurri"});
    HTinsert(elenco2, 4443, (TValue) {"Aldo", "Giallini"});
    HTinsert(elenco2, 3233, (TValue) {"Anna", "Indaco"});
    HTinsert(elenco2, 6320, (TValue) {"Luigi", "Rosi"});
    HTinsert(elenco2, 1110, (TValue) {"Giovanni", "Argento"});
    HTinsert(elenco2, 5430, (TValue) {"Lucio", "Rossetti"});
    HTinsert(elenco2, 1238, (TValue) {"Maria", "Scarlatti"});
    HTinsert(elenco2, 3450, (TValue) {"Biagio", "Verdini"});

    printf("Pazienti in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nPazienti in elenco2 (HT):\n");
    HTprint(elenco2);

    elenco1 = HTtoBST_exemption(elenco2, elenco1);

    printf("\nPazienti in elenco1 (BST) dopo lo spostamento:\n");
    BSTprint(elenco1);
    printf("\nPazienti in elenco2 (HT) dopo lo spostamento:\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    printf("\nRiverso in elenco3 i pazienti di elenco1...");
    printf("\nPazienti in elenco3 (Lista):\n");
    elenco3 = BSTtoList(elenco1, elenco3);
    listPrint(elenco3);
    
    printf("\nPazienti con esenzione presenti in elenco3 (Lista)\n(in ordine decrescente)\n");
    listPrintReverse_exemption(elenco3);
    
    printf("\nPazienti in elenco1 (BST dopo aver rimosso l'elemento con ID massimo):\n");
    elenco1 = BSTremoveLast(elenco1);
    BSTprint(elenco1);
    

    BSTdestroy(elenco1);
    HTdestroy(elenco2);
    listDestroy(elenco3);

    return 0;
}

[Quinzio]

Il primo warning e' perche' hai questa funzione
TBST HTtoBST_exemption(THT* ht, TBST bst)
che chiami in questo modo
HTtoBST_exemption(ht, bst->info.key)

Quindi passi "key" che e' un oggetto TKey, che alla fine e' un intero, ma la funzione accetta un TBST che e' alla fine un puntatore.
Quindi il compilatore ti sta gentilmente dicendo che stai usando un intero dove ci si aspetta un puntatore e questo potrebbe nascondere un grave errore, come in effetti e' nel tuo caso.
Cio' non e' sempre un errore. Ad esempio nei software che sviluppo io, per i microprocessori, molte volte e' lecito passare un intero dove serve un puntatore a patto che uno sappia cosa sta facendo e perche', e lo faccia in modo "garbato" e esplicito.

Il secondo warning e' perche' nella printf e' specificato %d, quindi un intero, ma alla printf viene passata una struttura e quindi il compilatore non sa cosa fare.
Altri linguaggi, come ad es. Python, possono gestire le stampe in modo piu' intelligente e se chiedi di stampare una struttura, sotto c'e' un algoritmo che lo fa in modo leggibile.
In C no. In C devi occuparti tu della stampa della tua struttura.

[vict85]

Penso sia almeno un mese che lavori con queste librerie, ma il tuo problema è a priori. Fai errori base dell'uso del C e non riesci a capire quel che ti dice il compilatore. Secondo me dovresti prendere un manuale e ripassarti bene i capitoli su puntatori e funzioni. E magari risolverti qualche problema elementare (per esempio su LeetCode o CodeWars, DMOJ potrebbe essere troppo complesso).

[giacomovicinanza]

Per il primo quesito ho aggiunto una funzione di supporto.

Int Func(TKey num){
     if(num%10==0)
        return 1;
     else
        return 0;
 }

TBST HTtoBST_exemption(THT* ht, TBST bst) {
    for(int i = 0; i < ht->n_bucket; i++)
    for(TNode *node = ht->bucket[i]; node != NULL; node = node->link)
    if(Func(node->info.key) == 1){
        if(BSTsearch(bst, node->info) == NULL)
        bst = BSTinsert(bst, node->info);
        HTdelete(ht, node->info.key);
    }
    
    return bst;
}

Mentre per la stampa della lista in ordine decrescente non funziona

  // Caso base
    if (list == NULL || list->link == NULL)
        return;
        
    // Divide et Impera
    TNode *first = list;
    list = listPrintReverse_exemption(list->link);
    (first->link)->link = first;
    first->link = NULL;

[apatriarca]

Riguardo alla funzione di supporto:
1. L'espressione [tt]num % 10 == 0[/tt] restituisce già [tt]1[/tt] (o [tt]true[/tt]) quando l'espressione è vera e [tt]0[/tt] (o [tt]false[/tt]) altrimenti. La struttura di controllo [tt]if[/tt] è quindi completamente ridondante.
2. Stai chiaramente facendo uso di una versione di C che supporta i commenti del C++ e nella stessa versione è stato introdotto il tipo [tt]_Bool[/tt] (o [tt]bool[/tt] se viene incluso [tt]stdbool.h[/tt]) che è maggiormente adatto a rappresentare un valore booleano.
3. Il nome della funzione dovrebbe essere rappresentativo di quello che fa e quindi [tt]Func[/tt] è un pessimo nome.
4. La tua funzione di supporto restituisce un valore booleano ed è quindi totalmente ridondante confrontare tale valore con [tt]1[/tt] quando utilizzi tale funzione in [tt]HTtoBST_exemption[/tt].
5. Sinceramente non mi sembra particolarmente utile l'idea di creare una funzione di supporto in questo caso.

La funzione avrebbe insomma dovuto essere:

bool LastDigitIsZero(TKey num) {
    return num % 10 == 0;
}

TBST HTtoBST_exemption(THT* ht, TBST bst) {
    for(int i = 0; i < ht->n_bucket; i++)
    for(TNode *node = ht->bucket[i]; node != NULL; node = node->link)
    if(Func(node->info.key)){
        if(BSTsearch(bst, node->info) == NULL)
        bst = BSTinsert(bst, node->info);
        HTdelete(ht, node->info.key);
    }
   
    return bst;
}

[apatriarca]

Per quanto riguarda la stampa non credo che il caso base sia corretto. Dovrebbe eliminare solo il caso in cui la lista sia NULL. Inoltre non vedo la stampa della lista, solo la chiamata ricorsiva..

[giacomovicinanza]

In questa maniera?

void listPrintReverse_exemption(TList list) {
    // Caso base
    if(list == NULL)
    return;
    
    // Divide et Impera
    listPrintReverse_exemption(list->link);
    printf("%d\n", list->info.key);

}

[giacomovicinanza]

"apatriarca":Riguardo alla funzione di supporto:
1. L'espressione [tt]num % 10 == 0[/tt] restituisce già [tt]1[/tt] (o [tt]true[/tt]) quando l'espressione è vera e [tt]0[/tt] (o [tt]false[/tt]) altrimenti. La struttura di controllo [tt]if[/tt] è quindi completamente ridondante.
2. Stai chiaramente facendo uso di una versione di C che supporta i commenti del C++ e nella stessa versione è stato introdotto il tipo [tt]_Bool[/tt] (o [tt]bool[/tt] se viene incluso [tt]stdbool.h[/tt]) che è maggiormente adatto a rappresentare un valore booleano.
3. Il nome della funzione dovrebbe essere rappresentativo di quello che fa e quindi [tt]Func[/tt] è un pessimo nome.
4. La tua funzione di supporto restituisce un valore booleano ed è quindi totalmente ridondante confrontare tale valore con [tt]1[/tt] quando utilizzi tale funzione in [tt]HTtoBST_exemption[/tt].
5. Sinceramente non mi sembra particolarmente utile l'idea di creare una funzione di supporto in questo caso.

La funzione avrebbe insomma dovuto essere:

bool LastDigitIsZero(TKey num) {
    return num % 10 == 0;
}

TBST HTtoBST_exemption(THT* ht, TBST bst) {
    for(int i = 0; i < ht->n_bucket; i++)
    for(TNode *node = ht->bucket[i]; node != NULL; node = node->link)
    if(Func(node->info.key)){
        if(BSTsearch(bst, node->info) == NULL)
        bst = BSTinsert(bst, node->info);
        HTdelete(ht, node->info.key);
    }
   
    return bst;
}

Capito grazie mille

[giacomovicinanza]

    // Caso base
    if (list == NULL)
        return;
       
    // Divide et Impera
    TNode *first = list;
    (first->link)->link = first;
    first->link = NULL;
    listPrintReverse_exemption(list->link);
    printf("%d\n", list->info.key);

}

Continuo ad avere problemi con questa funzione

[apatriarca]

In realtà il tuo codice è più complesso del necessario. Se la lista è vuota non c'è nulla da stampare (caso base) mentre se c'è almeno un nodo nella lista chiamiamo la funzione sul resto della lista in modo da stampare tutti gli elementi successivi e concludiamo stampando il valore in quel nodo. Insomma è sufficiente la seguente funzione che avevi postato qualche post fa:

void listPrintReverse_exemption(TList list) {
    if (list == NULL)
        return;
   
    listPrintReverse_exemption(list->link);
    printf("%d\n", list->info.key);
}

Che problemi hai incontrato con questa funzione?

[giacomovicinanza]

"apatriarca":In realtà il tuo codice è più complesso del necessario. Se la lista è vuota non c'è nulla da stampare (caso base) mentre se c'è almeno un nodo nella lista chiamiamo la funzione sul resto della lista in modo da stampare tutti gli elementi successivi e concludiamo stampando il valore in quel nodo. Insomma è sufficiente la seguente funzione che avevi postato qualche post fa:

void listPrintReverse_exemption(TList list) {
    if (list == NULL)
        return;
   
    listPrintReverse_exemption(list->link);
    printf("%d\n", list->info.key);
}

Che problemi hai incontrato con questa funzione?

Continua a non stampare l'elenco Forse sarà un problema del compilatore?

[apatriarca]

Sei sicuro che la lista non sia vuota? Non viene stampato alcun paziente neanche nella parte precedente dove stai stampando la lista in ordine crescente.

[giacomovicinanza]

Però da come si evince dalla traccia "Inoltre, si dovranno copiare in elenco3 (una lista ordinata) tutti i pazienti di elenco1" dovrebbe essere "popolata"

[vict85]

Il codice per HTtoBST_exemption è più colplicato di così: tu stai iterando su una lista da cui stai cancellando valori! Di fatto dopo HTdelete non dovresti più usare node.

In BSTtoList hai sbagliato la posizione del return, strano che tu non abbia ricevuto uno warning a riguardo.

BSTremoveLast era proprio implementato sbagliato.

Puoi vedere la mia soluzione qui:

TBST
HTtoBST_exemption(THT *ht, TBST bst)
{
    for (int i = 0; i < ht->n_bucket; i++)
    {
        while (ht->bucket[i] && ht->bucket[i]->info.key % 10 == 0)
        {
            TNode *temp   = ht->bucket[i];
            ht->bucket[i] = ht->bucket[i]->link;
            if (BSTsearch(bst, temp->info) == NULL)
            {
                BSTinsert(bst, temp->info);
            }
            nodeDestroy(temp);
        }

        if (ht->bucket[i] == NULL)
        {
            continue;
        }

        TNode *prev = ht->bucket[i];
        TNode *node = prev->link;

        while (node != NULL)
        {
            if (node->info.key % 10 != 0)
            {
                node = node->link;
                prev = prev->link;
                continue;
            }

            TNode *temp = node;
            node        = node->link;
            prev->link  = node;
            if (BSTsearch(bst, temp->info) == NULL)
            {
                BSTinsert(bst, temp->info);
            }
            nodeDestroy(temp);
        }
    }

    return bst;
}

TList
BSTtoList(TBST bst, TList list)
{
    // Caso base: l'albero è vuoto, niente da aggiungere
    if (bst != NULL)
    {
        // Divide e combina: aggiungo il sotto-albero sinistro (elementi minori)
        list = BSTtoList(bst->left, list);

        // Aggiungo l'elemento
        list = listInsert(list, bst->info);

        // Aggiungo il sotto-albero destro (elementi maggiori)
        list = BSTtoList(bst->right, list);
    }
    return list;
}

void listPrintReverse_exemption(TList list) {
    // Caso base
    if(list == NULL)
    return;
    
    // Divide et Impera
    listPrintReverse_exemption(list->link);
    printf("%d\n",list->info.key);

}

TBST BSTremoveLast(TBST bst) {
    // Caso base
    if(bst == NULL)
    {
        return bst;
    }
    
    if( bst->right == NULL )
    {
        return bst->left;
    }
    
    bst->right = BSTremoveLast( bst->right );
    
    return bst;
}

Prova a vedere se capisci il perché l'ho fatto così e le differenze con le tue versioni.

[giacomovicinanza]

Si mi è tutto chiaro grazie mille per avermi aiutato

[vict85]

"giacomovicinanza":Si mi è tutto chiaro grazie mille per avermi aiutato

Un altro modo in cui avresti potuto fare HTtoBST_exemption, consisteva nel "rimuovere" completamente la lista dal bucket e reinserire gli elementi con [inline]info.key % 10 != 0[/inline] e poi cancellare la lista originale. In questo modo non avresti iterato su una lista da cui stavi rimuovendo elementi, anche se al costo di qualche allocazione in più.