Qui c'è l'esercizio con le strutture apposite
https://onlinegdb.com/CKS9ooQJJ
- Codice:
/*
* 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;
}
