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