Algoritmi e strutture dati

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

Codice:

/*
 * 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;
}


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.

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).

Per il primo quesito ho aggiunto una funzione di supporto.

Codice:

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

Codice:

  // 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;

Riguardo alla funzione di supporto:
1. L'espressione num % 10 == 0 restituisce già 1 (o true) quando l'espressione è vera e 0 (o false) altrimenti. La struttura di controllo if è 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 _Bool (o bool se viene incluso stdbool.h) che è maggiormente adatto a rappresentare un valore booleano.
3. Il nome della funzione dovrebbe essere rappresentativo di quello che fa e quindi Func è un pessimo nome.
4. La tua funzione di supporto restituisce un valore booleano ed è quindi totalmente ridondante confrontare tale valore con 1 quando utilizzi tale funzione in HTtoBST_exemption.
5. Sinceramente non mi sembra particolarmente utile l'idea di creare una funzione di supporto in questo caso.

La funzione avrebbe insomma dovuto essere:

Codice:

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;
}


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..

In questa maniera?

Codice:

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

}


Ultima modifica di giacomovicinanza il 14/05/2022, 10:13, modificato 1 volta in totale.

Riguardo alla funzione di supporto:
1. L'espressione num % 10 == 0 restituisce già 1 (o true) quando l'espressione è vera e 0 (o false) altrimenti. La struttura di controllo if è 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 _Bool (o bool se viene incluso stdbool.h) che è maggiormente adatto a rappresentare un valore booleano.
3. Il nome della funzione dovrebbe essere rappresentativo di quello che fa e quindi Func è un pessimo nome.
4. La tua funzione di supporto restituisce un valore booleano ed è quindi totalmente ridondante confrontare tale valore con 1 quando utilizzi tale funzione in HTtoBST_exemption.
5. Sinceramente non mi sembra particolarmente utile l'idea di creare una funzione di supporto in questo caso.

La funzione avrebbe insomma dovuto essere:

Codice:

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

Codice:

    // 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

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:

Codice:

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?