Algoritmi e strutture dati

Fai una domanda Tutte le categorie
giacomovicinanza
giacomovicinanza
6 lug 2022, 15:57
Salve. Purtroppo ho ricevuto un voto basso (20) all'esame di algoritmi e strutture dati e naturalmente ho rifiutato. Sono consapevole che la funzione listLastNode(list) è un disastro ma non so davvero come implementarla. Qualcuno potrebbe aiutarmi? Grazie mille

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

/*
 * La segreteria di una Universita' deve riorganizzare alcuni elenchi di studenti 
 * tra cui elenco1 (un BST) ed elenco2 (una HT). In ciascuna struttura uno studente 
 * è rappresentato dalla matricola (campo chiave), dal nome e dal cognome.
 * 
 * Si dovrà realizzare un programma che sposti tutti gli studenti con matricola
 * dispari in elenco1 e tutti gli studenti con matricola pari in elenco2 rimuovendo
 * gli eventuali duplicati. Inoltre, si dovranno copiare in elenco3 (una lista)
 * tutti gli studenti di elenco2 (dopo le operazioni suddette).
 * Infine, bisognera' eliminare lo studente con la matricola piu' bassa in elenco3
 * e stampare lo studente con la matricola piu' alta.
 *
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 * 
 * 1) HTtoBSTodd(ht, bst): funzione ITERATIVA che copia da ht a bst tutti gli studenti
 *    con matricola dispari, rimuovendoli da ht.
 *    Se uno studente di ht gia' esiste in bst esso non verra' 
 *    duplicato (ma verra' comunque rimosso da ht).
 *    
 * 2) BSTtoHTeven(bst, ht): funzione RICORSIVA che copia da bst a ht tutti gli 
 *    studenti con matricola pari rimuovendoli da bst. Se uno studente di bst 
 *    gia' esiste in ht esso non verrà duplicato (ma verra' comunque rimosso da bst).
 * 
 * 3) HTtoList(ht, list): funzione ITERATIVA che copia tutti gli studenti
 *    di ht in list.
 * 
 * 4) deleteMinList(list): funzione che elimina lo studente con la matricola piu' bassa.
 *
 * 5) listLastNode(list): funzione RICORSIVA che restituisce il riferimento (puntatore)
 *    all'ultimo elemento della lista (per poi stamparne il contenuto nella funzione main). 
 */

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

int isEven(TKey num){
    if(num%2==0)
    return 1;
    else
    return 0;
}


TBST HTtoBSTodd(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 (isEven(node->info.key) == 0) {
                if (BSTsearch(bst, node->info) == NULL)
                    bst = BSTinsert(bst, node->info);
                HTdelete(ht, node->info.key);
            }
    return bst;

}

TBST BSTtoHTeven(TBST bst, THT* ht) {
   if (bst != NULL) {
        bst->left = BSTtoHTeven(bst->left, ht);
        bst->right = BSTtoHTeven(bst->right, ht);
        if (isEven(bst->info.key) == 1) {
            HTinsert(ht, bst->info.key, bst->info.value);
  
            bst = BSTdelete(bst, bst->info);
        }
    }

    return bst;
}

TList HTtoList(THT *ht, TList list) {
    TNode* node = nodeCreate(list->info);
      
for (int i = 0; i < ht->n_bucket; ++i)
        for (TNode* node = ht->bucket[i]; node != NULL; node = node->link)
        HTdelete(ht, node->info.key);
        list = listInsert(list, node->info);
    
    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;

    
}

TNode* listLastNode(TList l){
    TNode* node;
    /* Caso Base */
    if(l == NULL) {
        return 0;
    }
    
    /* Divide et Impera (+ combina) */
        if(node->right == NULL){
        return node->left;
    }
    // Divide et Impera (+ combina)
    if(node->right == NULL){
        return node->left;
    }
    node->right = listLastNode(node->right);
    
    return l;


}

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Mario", "Rossi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Antonio", "Bianchi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Lucia", "Verdi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Camilla", "Neri"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Aldo", "Giallini"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Carlo", "Aranci"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "Maria", "Scarlatti"});
    elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Luigi", "Turchesi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Giovanni", "Argento"});

    THT *elenco2 = HTcreate(5);
    HTinsert(elenco2, 3357, (TValue) {"Nicola", "Grigetti"});
    HTinsert(elenco2, 7675, (TValue) {"Costanza", "Violetti"});
    HTinsert(elenco2, 4222, (TValue) {"Filippa", "Azzurri"});
    HTinsert(elenco2, 1445, (TValue) {"Aldo", "Giallini"});
    HTinsert(elenco2, 3233, (TValue) {"Anna", "Indaco"});
    HTinsert(elenco2, 3321, (TValue) {"Luigi", "Rosi"});
    HTinsert(elenco2, 1111, (TValue) {"Giovanni", "Argento"});
    HTinsert(elenco2, 3432, (TValue) {"Lucia", "Verdi"});
    HTinsert(elenco2, 1238, (TValue) {"Maria", "Scarlatti"});

    printf("Studenti in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT):\n");
    HTprint(elenco2);

    elenco1 = HTtoBSTodd(elenco2, elenco1);
    elenco1 = BSTtoHTeven(elenco1, elenco2);

    printf("\nStudenti in elenco1 (BST) dopo lo spostamento\n(solo matricole dispari senza duplicati):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT) dopo lo spostamento\n(solo matricole pari senza duplicati):\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    elenco3 = HTtoList(elenco2, elenco3);
    
    printf("\nStudenti in elenco3 (Lista)\n");
    listPrint(elenco3);
    
    elenco3 = deleteMinList(elenco3);
    printf("\nStudenti in elenco3 (Lista)\n(tutti quelli di elenco2 tranne la matricola piu' bassa)\n");
    listPrint(elenco3);
    
    printf("\nUltimo studente in elenco3 (Lista)\n(matricola piu' alta):\n");
    TNode* last_node = listLastNode(elenco3);
    infoPrint(last_node->info);

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

    return 0;
}
Risposte
vict85
vict85
6 lug 2022, 14:54
Perché usi left e right se hai a che fare con una lista? Insomma era sufficiente qualcosa come questo:
TNode* listLastNode(TList l){
    if(l == NULL || l->link == NULL) {
        return l;
    }
    return listLastNode(l->link);
}


Detto questo, in HTtoBSTodd non è appropriato chiamare [inline]HTdelete(ht, node->info.key);[/inline] mentre stai iterando sul bucket. È inoltre inefficiente dato che sai esattamente dove si trova l'elemento che vuoi eliminare.

Stessa cosa per BSTtoHTeven.

HTtoList è anche peggio perché cancelli un elemento di cui possiedi un puntatore e che ancora non hai copiato altrove.

Anche deleteMinList è sbagliato e non capisco come mai stai cercando massimo e minimo e cancelli il valore all'interno del ciclo e non dopo.
giacomovicinanza
giacomovicinanza
10 lug 2022, 13:40
https://onlinegdb.com/ojQuuoyage Ho aggiornato il codice ma lo stesso non funziona

/*
 * La segreteria di una Universita' deve riorganizzare alcuni elenchi di studenti 
 * tra cui elenco1 (un BST) ed elenco2 (una HT). In ciascuna struttura uno studente 
 * è rappresentato dalla matricola (campo chiave), dal nome e dal cognome.
 * 
 * Si dovrà realizzare un programma che sposti tutti gli studenti con matricola
 * dispari in elenco1 e tutti gli studenti con matricola pari in elenco2 rimuovendo
 * gli eventuali duplicati. Inoltre, si dovranno copiare in elenco3 (una lista)
 * tutti gli studenti di elenco2 (dopo le operazioni suddette).
 * Infine, bisognera' eliminare lo studente con la matricola piu' bassa in elenco3
 * e stampare lo studente con la matricola piu' alta.
 *
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 * 
 * 1) HTtoBSTodd(ht, bst): funzione ITERATIVA che copia da ht a bst tutti gli studenti
 *    con matricola dispari, rimuovendoli da ht.
 *    Se uno studente di ht gia' esiste in bst esso non verra' 
 *    duplicato (ma verra' comunque rimosso da ht).
 *    
 * 2) BSTtoHTeven(bst, ht): funzione RICORSIVA che copia da bst a ht tutti gli 
 *    studenti con matricola pari rimuovendoli da bst. Se uno studente di bst 
 *    gia' esiste in ht esso non verrà duplicato (ma verra' comunque rimosso da bst).
 * 
 * 3) HTtoList(ht, list): funzione ITERATIVA che copia tutti gli studenti
 *    di ht in list.
 * 
 * 4) deleteMinList(list): funzione che elimina lo studente con la matricola piu' bassa.
 *
 * 5) listLastNode(list): funzione RICORSIVA che restituisce il riferimento (puntatore)
 *    all'ultimo elemento della lista (per poi stamparne il contenuto nella funzione main). 
 */

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

int isEven(TKey num){
    if(num%2==0)
    return 1;
    else
    return 0;
}


TBST HTtoBSTodd(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 (isEven(node->info.key) == 0) {
                if (BSTsearch(bst, node->info) == NULL)
                    bst = BSTinsert(bst, node->info);
            }
    return bst;

}

TBST BSTtoHTeven(TBST bst, THT* ht) {
   if (bst != NULL) {
        bst->left = BSTtoHTeven(bst->left, ht);
        bst->right = BSTtoHTeven(bst->right, ht);
        if (isEven(bst->info.key) == 1) {
            HTinsert(ht, bst->info.key, bst->info.value);
        }
    }

    return bst;
}

TList HTtoList(THT *ht, TList list) {
    TNode* node2 = nodeCreate(list->info);
      
for (int i = 0; i < ht->n_bucket; ++i)
        for (TNode* node = ht->bucket[i]; node != NULL; node = node->link)
        if (listSearch(list, node2->info) == NULL)
        list = listInsert(list, node2->info);
                HTdelete(ht, node2->info.key);
    
    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;

    
}

TNode* listLastNode(TList l){
    if(l == NULL || l->link == NULL) {
        return l;
    }
    return listLastNode(l->link);
}

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Mario", "Rossi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Antonio", "Bianchi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Lucia", "Verdi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Camilla", "Neri"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Aldo", "Giallini"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Carlo", "Aranci"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "Maria", "Scarlatti"});
    elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Luigi", "Turchesi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Giovanni", "Argento"});

    THT *elenco2 = HTcreate(5);
    HTinsert(elenco2, 3357, (TValue) {"Nicola", "Grigetti"});
    HTinsert(elenco2, 7675, (TValue) {"Costanza", "Violetti"});
    HTinsert(elenco2, 4222, (TValue) {"Filippa", "Azzurri"});
    HTinsert(elenco2, 1445, (TValue) {"Aldo", "Giallini"});
    HTinsert(elenco2, 3233, (TValue) {"Anna", "Indaco"});
    HTinsert(elenco2, 3321, (TValue) {"Luigi", "Rosi"});
    HTinsert(elenco2, 1111, (TValue) {"Giovanni", "Argento"});
    HTinsert(elenco2, 3432, (TValue) {"Lucia", "Verdi"});
    HTinsert(elenco2, 1238, (TValue) {"Maria", "Scarlatti"});

    printf("Studenti in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT):\n");
    HTprint(elenco2);

    elenco1 = HTtoBSTodd(elenco2, elenco1);
    elenco1 = BSTtoHTeven(elenco1, elenco2);

    printf("\nStudenti in elenco1 (BST) dopo lo spostamento\n(solo matricole dispari senza duplicati):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT) dopo lo spostamento\n(solo matricole pari senza duplicati):\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    elenco3 = HTtoList(elenco2, elenco3);
    
    printf("\nStudenti in elenco3 (Lista)\n");
    listPrint(elenco3);
    
    elenco3 = deleteMinList(elenco3);
    printf("\nStudenti in elenco3 (Lista)\n(tutti quelli di elenco2 tranne la matricola piu' bassa)\n");
    listPrint(elenco3);
    
    printf("\nUltimo studente in elenco3 (Lista)\n(matricola piu' alta):\n");
    TNode* last_node = listLastNode(elenco3);
    infoPrint(last_node->info);

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

    return 0;
}
vict85
vict85
11 lug 2022, 16:14
No, gli elementi devi eliminarli, ma non puoi farlo mentre stai iterando. Provo a commentarti la prima versione di [inline]HTtoBSTodd[/inline]:
TBST HTtoBSTodd(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 (isEven(node->info.key) == 0) {
                if (BSTsearch(bst, node->info) == NULL)
                    bst = BSTinsert(bst, node->info);
                HTdelete(ht, node->info.key);
            }
    return bst;
}

La parte dell'inserimento nell'albero è OK. Analizziamo quindi la parte che elimina gli elementi dispari (ho rinominato la funzione per meglio descrivere che cosa ci si aspetta che faccia), ovvero:
void HTRemoveOdd(THT* ht) {
    for (int i = 0; i < ht->n_bucket; ++i)
        for (TNode* node = ht->bucket[i]; node != NULL; node = node->link)
            if (isEven(node->info.key) == 0) {
                HTdelete(ht, node->info.key);
            }
}


[inline]HTdelete[/inline] ricalcola [inline]i[/inline] da [inline]node->info.key[/inline] usando la funzione di hash, quindi prova ad eliminare [inline]node->info.key[/inline] da [inline]ht->bucket[/inline]. Ovvero prova ad eliminare [inline]node[/inline]. In sostanza, quel codice è equivalente a:
void HTRemoveOdd(THT* ht) {
    for (int i = 0; i < ht->n_bucket; ++i)
        TNode** prev = &ht->bucket[i];
        for (TNode* node = ht->bucket[i]; node != NULL; node = node->link)
            if (isEven(node->info.key) == 0) {
                *prev = node->link;
                free(node);
            }
            else {
                *prev = &(node->link);
            }
}

che ovviamente crasha dato che stai cercando di accedere ad una memoria dopo aver chiamato free su quella memoria. Prova a pensare a come puoi modificare il ciclo per evitare il problema.
giacomovicinanza
giacomovicinanza
12 lug 2022, 11:29
https://onlinegdb.com/qjhT53z_84 --> codice aggiornato

I primi quattro punti del main vengono stampati il problema si preesenta dalla riga 152 che non mi stampa i studenti in elenco3

/*
 * La segreteria di una Universita' deve riorganizzare alcuni elenchi di studenti 
 * tra cui elenco1 (un BST) ed elenco2 (una HT). In ciascuna struttura uno studente 
 * è rappresentato dalla matricola (campo chiave), dal nome e dal cognome.
 * 
 * Si dovrà realizzare un programma che sposti tutti gli studenti con matricola
 * dispari in elenco1 e tutti gli studenti con matricola pari in elenco2 rimuovendo
 * gli eventuali duplicati. Inoltre, si dovranno copiare in elenco3 (una lista)
 * tutti gli studenti di elenco2 (dopo le operazioni suddette).
 * Infine, bisognera' eliminare lo studente con la matricola piu' bassa in elenco3
 * e stampare lo studente con la matricola piu' alta.
 *
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 * 
 * 1) HTtoBSTodd(ht, bst): funzione ITERATIVA che copia da ht a bst tutti gli studenti
 *    con matricola dispari, rimuovendoli da ht.
 *    Se uno studente di ht gia' esiste in bst esso non verra' 
 *    duplicato (ma verra' comunque rimosso da ht).
 *    
 * 2) BSTtoHTeven(bst, ht): funzione RICORSIVA che copia da bst a ht tutti gli 
 *    studenti con matricola pari rimuovendoli da bst. Se uno studente di bst 
 *    gia' esiste in ht esso non verrà duplicato (ma verra' comunque rimosso da bst).
 * 
 * 3) HTtoList(ht, list): funzione ITERATIVA che copia tutti gli studenti
 *    di ht in list.
 * 
 * 4) deleteMinList(list): funzione che elimina lo studente con la matricola piu' bassa.
 *
 * 5) listLastNode(list): funzione RICORSIVA che restituisce il riferimento (puntatore)
 *    all'ultimo elemento della lista (per poi stamparne il contenuto nella funzione main). 
 */

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

int isEven(TKey num){
    if(num%2==0)
    return 1;
    else
    return 0;
}


TBST HTtoBSTodd(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 (isEven(node->info.key) == 0) {
                if (BSTsearch(bst, node->info) == NULL){
                    bst = BSTinsert(bst, node->info);
                    HTdelete(ht, node->info.key);
                }
            }
    return bst;

}

TBST BSTtoHTeven(TBST bst, THT* ht) {
   if (bst != NULL) {
        bst->left = BSTtoHTeven(bst->left, ht);
        bst->right = BSTtoHTeven(bst->right, ht);
        if (isEven(bst->info.key) == 1) {
            HTinsert(ht, bst->info.key, bst->info.value);
                bst = BSTdelete(bst, bst->info);
        }
    }

    return bst;
}

TList HTtoList(THT *ht, TList list) {
    TNode* node2 = nodeCreate(list->info);
      
for (int i = 0; i < ht->n_bucket; ++i)
        for (TNode* node = ht->bucket[i]; node != NULL; node = node->link)
        if (listSearch(list, node2->info) == NULL)
        list = listInsert(list, node2->info);
                HTdelete(ht, node2->info.key);
    
    return list;

}

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

    
}

TNode* listLastNode(TList l){
    if(l == NULL || l->link == NULL) {
        return l;
    }
    return listLastNode(l->link);
}

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Mario", "Rossi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Antonio", "Bianchi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Lucia", "Verdi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Camilla", "Neri"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Aldo", "Giallini"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Carlo", "Aranci"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "Maria", "Scarlatti"});
    elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Luigi", "Turchesi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Giovanni", "Argento"});

    THT *elenco2 = HTcreate(5);
    HTinsert(elenco2, 3357, (TValue) {"Nicola", "Grigetti"});
    HTinsert(elenco2, 7675, (TValue) {"Costanza", "Violetti"});
    HTinsert(elenco2, 4222, (TValue) {"Filippa", "Azzurri"});
    HTinsert(elenco2, 1445, (TValue) {"Aldo", "Giallini"});
    HTinsert(elenco2, 3233, (TValue) {"Anna", "Indaco"});
    HTinsert(elenco2, 3321, (TValue) {"Luigi", "Rosi"});
    HTinsert(elenco2, 1111, (TValue) {"Giovanni", "Argento"});
    HTinsert(elenco2, 3432, (TValue) {"Lucia", "Verdi"});
    HTinsert(elenco2, 1238, (TValue) {"Maria", "Scarlatti"});

    printf("Studenti in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT):\n");
    HTprint(elenco2);

    elenco1 = HTtoBSTodd(elenco2, elenco1);
    elenco1 = BSTtoHTeven(elenco1, elenco2);

    printf("\nStudenti in elenco1 (BST) dopo lo spostamento\n(solo matricole dispari senza duplicati):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT) dopo lo spostamento\n(solo matricole pari senza duplicati):\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    elenco3 = HTtoList(elenco2, elenco3);
    
    printf("\nStudenti in elenco3 (Lista)\n");
    listPrint(elenco3);
    
    elenco3 = deleteMinList(elenco3);
    printf("\nStudenti in elenco3 (Lista)\n(tutti quelli di elenco2 tranne la matricola piu' bassa)\n");
    listPrint(elenco3);
    
    printf("\nUltimo studente in elenco3 (Lista)\n(matricola piu' alta):\n");
    TNode* last_node = listLastNode(elenco3);
    infoPrint(last_node->info);

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

    return 0;
}
vict85
vict85
12 lug 2022, 15:10
Stati continuando a fare lo stesso errore. Detto questo, il minimo di una lista ordinata in ordine crescente non è altro che il primo elemento, quindi il tuo codice fa operazioni inutili. Nota che [inline]min[/inline] non è inizializzata.
giacomovicinanza
giacomovicinanza
12 lug 2022, 17:46
Per le prime due funzioni se metto HTDelete e BSTdelete al di fuori del ciclo non funzionano. Per quanto riguarda l'altra funzione non saprei cosa fare
vict85
vict85
12 lug 2022, 20:12
Il problema è chiamare [inline]node->link[/inline] dopo aver fatto [inline]free(node)[/inline], quindi ti basta chiamarlo prima.
TBST HTtoBSTodd(THT* ht, TBST bst) {
    for (int i = 0; i < ht->n_bucket; ++i)
    {
        for (TNode* node = ht->bucket[i]; node != NULL; ) 
        {
            TNode* temp = node;
            node = node->link;
            if (isEven(temp->info.key) == 0) {
                if (BSTsearch(bst, temp->info) == NULL) {
                    bst = BSTinsert(bst, temp->info);
                    HTdelete(ht, temp->info.key);
                }
            }
        }
    }
    return bst;
}
oppure 
TBST HTtoBSTodd(THT* ht, TBST bst) {
    for (int i = 0; i < ht->n_bucket; ++i)
    {
        TNode* next = NULL;
        for (TNode* node = ht->bucket[i]; node != NULL; node = next ) 
        {
            next = node->link;
            if (isEven(node->info.key) == 0) {
                if (BSTsearch(bst, node->info) == NULL) {
                    bst = BSTinsert(bst, node->info);
                    HTdelete(ht, node->info.key);
                }
            }
        }
    }
    return bst;
}

Chiamare [inline]HTdelete[/inline] è un po' uno spreco computazionale, ma almeno non stai accedendo ad una memoria deallocata. Di fatto dato che accedi subito dopo, senza alcun multithreading e che non stai runnando il codice con un AddressSanitizer, il codice funziona lo stesso, ma è comunque una cattiva pratica.
giacomovicinanza
giacomovicinanza
13 lug 2022, 14:18
mentre per le altre funzioni cosa dovrei cambiare?
vict85
vict85
14 lug 2022, 08:09
BSTtoHTeven è ok, non stai accedendo a nulla dopo averlo eliminato.
HTtoList si fa uguale a HTtoBSTodd.
Per quanto riguarda deleteMinList ti ho già detto: List è una lista ordinata in ordine crescente.
giacomovicinanza
giacomovicinanza
14 lug 2022, 13:37
Funziona perfettamente. Grazie mille per avermi aiutato a capire :lol:

https://onlinegdb.com/5BKiNUjEI -> codice aggiornato

/*
 * La segreteria di una Universita' deve riorganizzare alcuni elenchi di studenti 
 * tra cui elenco1 (un BST) ed elenco2 (una HT). In ciascuna struttura uno studente 
 * è rappresentato dalla matricola (campo chiave), dal nome e dal cognome.
 * 
 * Si dovrà realizzare un programma che sposti tutti gli studenti con matricola
 * dispari in elenco1 e tutti gli studenti con matricola pari in elenco2 rimuovendo
 * gli eventuali duplicati. Inoltre, si dovranno copiare in elenco3 (una lista)
 * tutti gli studenti di elenco2 (dopo le operazioni suddette).
 * Infine, bisognera' eliminare lo studente con la matricola piu' bassa in elenco3
 * e stampare lo studente con la matricola piu' alta.
 *
 * Per realizzare tale programma occorre sviluppare le seguenti funzioni.
 * 
 * 1) HTtoBSTodd(ht, bst): funzione ITERATIVA che copia da ht a bst tutti gli studenti
 *    con matricola dispari, rimuovendoli da ht.
 *    Se uno studente di ht gia' esiste in bst esso non verra' 
 *    duplicato (ma verra' comunque rimosso da ht).
 *    
 * 2) BSTtoHTeven(bst, ht): funzione RICORSIVA che copia da bst a ht tutti gli 
 *    studenti con matricola pari rimuovendoli da bst. Se uno studente di bst 
 *    gia' esiste in ht esso non verrà duplicato (ma verra' comunque rimosso da bst).
 * 
 * 3) HTtoList(ht, list): funzione ITERATIVA che copia tutti gli studenti
 *    di ht in list.
 * 
 * 4) deleteMinList(list): funzione che elimina lo studente con la matricola piu' bassa.
 *
 * 5) listLastNode(list): funzione RICORSIVA che restituisce il riferimento (puntatore)
 *    all'ultimo elemento della lista (per poi stamparne il contenuto nella funzione main). 
 */

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

int isEven(TKey num){
    if(num%2==0)
    return 1;
    else
    return 0;
}

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

TBST BSTtoHTeven(TBST bst, THT* ht) {
   if (bst != NULL) {
        bst->left = BSTtoHTeven(bst->left, ht);
        bst->right = BSTtoHTeven(bst->right, ht);
        if (isEven(bst->info.key) == 1) {
            HTinsert(ht, bst->info.key, bst->info.value);
                bst = BSTdelete(bst, bst->info);
        }
    }

    return bst;
}

TList HTtoList(THT* ht, TList list) {
    for (int i = 0; i < ht->n_bucket; ++i)
    {
        for (TNode* node = ht->bucket[i]; node != NULL;)
        {
            TNode* temp = node;
            node = node->link;
                if (listSearch(list, temp->info) == NULL) {
                    list = listInsert(list, temp->info);
                    HTdelete(ht, temp->info.key);
                }
        }
    }
    return list;
}

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

    
}

TNode* listLastNode(TList l){
    if(l == NULL || l->link == NULL) {
        return l;
    }
    return listLastNode(l->link);
}

int main() {
    TBST elenco1 = BSTcreate();
    elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Mario", "Rossi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Antonio", "Bianchi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Lucia", "Verdi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Camilla", "Neri"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Aldo", "Giallini"});
    elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Carlo", "Aranci"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1238, "Maria", "Scarlatti"});
    elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Luigi", "Turchesi"});
    elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Giovanni", "Argento"});

    THT *elenco2 = HTcreate(5);
    HTinsert(elenco2, 3357, (TValue) {"Nicola", "Grigetti"});
    HTinsert(elenco2, 7675, (TValue) {"Costanza", "Violetti"});
    HTinsert(elenco2, 4222, (TValue) {"Filippa", "Azzurri"});
    HTinsert(elenco2, 1445, (TValue) {"Aldo", "Giallini"});
    HTinsert(elenco2, 3233, (TValue) {"Anna", "Indaco"});
    HTinsert(elenco2, 3321, (TValue) {"Luigi", "Rosi"});
    HTinsert(elenco2, 1111, (TValue) {"Giovanni", "Argento"});
    HTinsert(elenco2, 3432, (TValue) {"Lucia", "Verdi"});
    HTinsert(elenco2, 1238, (TValue) {"Maria", "Scarlatti"});

    printf("Studenti in elenco1 (BST):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT):\n");
    HTprint(elenco2);

    elenco1 = HTtoBSTodd(elenco2, elenco1);
    elenco1 = BSTtoHTeven(elenco1, elenco2);

    printf("\nStudenti in elenco1 (BST) dopo lo spostamento\n(solo matricole dispari senza duplicati):\n");
    BSTprint(elenco1);
    printf("\nStudenti in elenco2 (HT) dopo lo spostamento\n(solo matricole pari senza duplicati):\n");
    HTprint(elenco2);

    TList elenco3 = listCreate();
    elenco3 = HTtoList(elenco2, elenco3);
    
    printf("\nStudenti in elenco3 (Lista)\n");
    listPrint(elenco3);
    
    elenco3 = deleteMinList(elenco3);
    printf("\nStudenti in elenco3 (Lista)\n(tutti quelli di elenco2 tranne la matricola piu' bassa)\n");
    listPrint(elenco3);
    
    printf("\nUltimo studente in elenco3 (Lista)\n(matricola piu' alta):\n");
    TNode* last_node = listLastNode(elenco3);
    infoPrint(last_node->info);

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

    return 0;
}
vict85
vict85
15 lug 2022, 10:09
La mia impressione è che tu stia scrivendo i programmi copiando e incollando soluzioni qua e là, invece dovresti farlo come se stessi scrivendo la ricetta di un ciambellone. Insomma ti devi chiarire i passaggi e poi scriverli nel linguaggio appropriato.

In questo codice usi [inline]min[/inline] senza averla inizializzata. 
TList deleteMinList(TList list) {
    TNode* curr = list;
    TNode* prev;
    TInfo min;
    
    /* Ricerca degli elementi da cancellare */
    while(curr != NULL) {
        if(infoGreater(curr->info, min)) {
            prev = curr;
            list = listDelete(list, curr->info);
            curr = prev->link;
        } else curr = curr->link;
    }
    return list;  
}
tra l'altro, non hai ascoltato il mio consiglio: TList è una lista ordinata. Quindi ti sarebbe bastato scrivere:
TList deleteMinList(TList list) {
    if ( list != NULL )
    {
        list = listDelete(list, list->info);
    }
    return list;
}

o anche
TList deleteMinList(TList list) {
    if ( list != NULL )
    {
        TList temp = list;
        list = list->link;
        nodeDestroy(temp);
    }
    return list;
}
Rispondi
Per rispondere a questa discussione devi prima effettuare il login.