/*
* 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 elenco1 ad elenco2, rimuovendo
* gli eventuali duplicati in conseguenza del travaso. Inoltre, si dovranno copiare in elenco3 (un TArray)
* tutti i pazienti di elenco2 con ID compreso tra min e max, rimuovendoli anche da elenco2.
* Bisogna anche rimuovere da elenco1 il paziente con ID piu' grande.
*
* Per realizzare tale programma occorre sviluppare le seguenti funzioni.
*
* 1) BSTtoHT_exemption(bst, ht): funzione RICORSIVA che copia da bst a ht tutti i
* pazienti con ID la cui ultima cifra sia 0, rimuovendoli da bst.
* Considerando l'ID, se un paziente di bst gia' esiste in ht esso non verra'
* duplicato (ma verra' comunque rimosso da bst).
*
* 2) HTtoArray_range(ht, array, min, max): funzione ITERATIVA che copia da ht ad array
* tutti i pazienti con ID compreso tra min e max e, inoltre, li rimuove da ht.
*
* 3) BSTremoveLast(bst): funzione RICORSIVA che rimuove da bst l'ultimo
* elemento in ordine di ID (ossia il paziente con ID massimo).
* Restituisce il bst aggiornato.
*
* 4) printOrderedArray(array): funzione ITERATIVA che stampa in ordine crescente di ID
* solo i pazienti con esenzione. Si possono utilizzare strutture dati di appoggio.
* Ad esempio, visite in order anche a spese della complessita' computazionale.
*
*
*/
#include <stdio.h>
#include "THT.h"
#include "TBST.h"
#include "TArray.h"
TBST BSTtoHT_exemption(TBST bst, THT* ht) {
if (bst != NULL) {
bst->left = BSTtoHT_exemption(bst->left, ht);
bst->right = BSTtoHT_exemption(bst->right, ht);
if ((bst->info.key%2) == 0) {
HTinsert(ht, bst->info.key, bst->info.value);
bst = BSTdelete(bst, bst->info);
}
}
return bst;
}
void HTtoArray_range(THT* ht, TArray* array, TKey min, TKey max) {
TList list = listCreate();
TInfo imin = {min}, imax = {max};
for (int i = 0; i < ht->n_bucket; i++)
for (TNode *node = ht->bucket[i]; node != NULL; node = node->link)
if (!infoLess(node->info, imin) && !infoGreater(node->info, imax))
arraySet(ht, array->info.key, array->info.value);
ht = HTdelete(ht, ht->info);
}
TBST BSTremoveLast(TBST bst) {
int min, max;
// Caso base
if (bst == NULL)
return 0;
// Divide et impera (+ combina)
if (!infoGreater(min, bst->info)) // tree->info >= min
BSTprintInterval2(bst->left, min, max);
if (!infoGreater(min, bst->info) && !infoLess(max, bst->info)) // tree->info >= min && tree->info <= max
infoPrint(bst->info);
if (!infoLess(max, bst->info)) // tree->info <= max
BSTprintInterval2(bst->right, min, max);
bst = BSTdelete(bst, bst->info);
}
void printOrderedArray_exemptions(TArray* array) {
int i;
TList list_ord = listCreate();
for(i=0; i<array->length; i++){
list_ord = listInsert(list_ord, array->items[i]);
}
}
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) {"Lucia", "Verdi"});
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 = BSTtoHT_exemption(elenco1, elenco2);
printf("\nPazienti in elenco1 (BST) dopo lo spostamento:\n");
BSTprint(elenco1);
printf("\nPazienti in elenco2 (HT) dopo lo spostamento\n:\n");
HTprint(elenco2);
TArray elenco3 = arrayCreate(0);
TKey min = 2000, max = 6000;
HTtoArray_range(elenco2, &elenco3, min, max);
printf("\nPazienti in elenco3 (Array):\n");
arrayPrint(&elenco3);
printf("\nPazienti in elenco1 (BST dopo aver rimosso l'elemento con ID massimo):\n");
elenco1 = BSTremoveLast(elenco1);
BSTprint(elenco1);
printf("\nPazienti con esenzione in elenco3 (Array) in ordine:\n");
printOrderedArray_exemptions(&elenco3);
BSTdestroy(elenco1);
HTdestroy(elenco2);
arrayDestroy(&elenco3);
return 0;
}
/*
* TArray: array dinamico
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "TArray.h"
#define C_EXP 5 // costante di espansione
#define C_RED 10 // costante di riduzione
TArray arrayCreate (int length) {
TArray a;
int size = length + C_EXP;
a.items = malloc(size * sizeof(TInfo));
assert (a.items != NULL);
a.length = length;
a.size = size;
return a;
}
void arrayDestroy (TArray *a) {
free(a->items);
a->items = NULL;
a->length = a->size = 0;
}
void arrayResize (TArray *a, int length) {
if (length > a->size || length < a->size - C_RED) {
int size = length + C_EXP;
a->items = realloc(a->items, size * sizeof(TInfo));
assert (a->items != NULL);
a->size = size;
}
a->length = length;
}
void arrayPrint(TArray *a) {
for (int i = 0; i < a->length; ++i)
infoPrint (a->items[i]);
}
/* FUNZIONI DI UTILITA' */
// Aggiunta di un elemento in coda all'array
void arrayAdd (TArray *a, TInfo info) {
arrayResize(a, a->length + 1);
a->items[a->length - 1] = info;
}
// Lettura di un elemento in posizione pos
TInfo arrayGet (TArray *a, int pos) {
return a->items[pos];
}
// Lettura della lunghezza dell'array
int arrayLength (TArray *a) {
return a->length;
}
// Inserimento di un elemento in posizione pos con ridimensionamento automatico
void arraySet (TArray *a, int pos, TInfo info) {
if (pos >= a->length)
arrayResize(a, pos + 1);
a->items[pos] = info;
}
/*
* TArray: array dinamico
*/
#ifndef TARRAY_H
#define TARRAY_H
#include "TInfo.h"
typedef struct {
TInfo* items; // puntatore agli elementi dell'array
int length; // lunghezza array
int size; // dimensione allocata (>= length)
} TArray;
TArray arrayCreate (int length);
void arrayDestroy (TArray *a);
void arrayResize (TArray *a, int length);
void arrayPrint(TArray *a);
// Funzioni di utilità
void arrayAdd (TArray *a, TInfo info);
TInfo arrayGet (TArray *a, int pos);
int arrayLength (TArray *a);
void arraySet (TArray *a, int pos, TInfo info);
#endif
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include "TInfo.h"
#include "TBST.h"
/* operazioni sui nodi */
TBSTnode *BSTnodeCreate (TInfo info) {
TBSTnode *node = malloc (sizeof(TBSTnode));
assert (node != NULL);
node->info = info;
node->left = node->right = NULL;
return node;
}
void BSTnodeDestroy (TBSTnode* node) {
free (node);
}
/* operazioni sugli alberi */
TBST BSTcreate () {
return NULL;
}
TBST BSTdestroy (TBST tree) {
if (tree == NULL)
return NULL;
BSTdestroy(tree->left);
BSTdestroy(tree->right);
BSTnodeDestroy (tree);
return NULL;
}
TBST BSTsearch (TBST tree, TInfo info) {
if (tree == NULL || infoEqual(info, tree->info))
return tree;
if (infoGreater(info, tree->info))
return BSTsearch(tree->right, info);
else
return BSTsearch(tree->left, info);
return tree;
}
TBST BSTmin (TBST tree) {
if (tree == NULL || tree->left == NULL)
return tree;
return BSTmin (tree->left);
}
TBST BSTmax (TBST tree) {
if (tree == NULL || tree->right == NULL)
return tree;
return BSTmax (tree->right);
}
TBST BSTinsert (TBST tree, TInfo info) {
if (tree == NULL)
return BSTnodeCreate(info);
if (infoGreater(info, tree->info))
tree->right = BSTinsert(tree->right, info);
else
tree->left = BSTinsert(tree->left, info);
return tree;
}
TBST BSTdelete (TBST tree, TInfo info) {
if (tree == NULL)
return NULL;
if (infoGreater(info, tree->info))
tree->right = BSTdelete(tree->right, info);
else if (infoLess(info, tree->info))
tree->left = BSTdelete(tree->left, info);
else { // trovato il nodo da rimuovere
if (tree->left == NULL) {
TBST right = tree->right;
BSTnodeDestroy(tree);
tree = right;
} else if (tree->right == NULL) {
TBST left = tree->left;
BSTnodeDestroy(tree);
tree = left;
} else {
TBST min = BSTmin(tree->right);
tree->info = min->info;
tree->right = BSTdelete(tree->right, min->info);
}
}
return tree;
}
int BSTheight(TBST tree) {
if (tree == NULL)
return -1;
int l = BSTheight(tree->left);
int r = BSTheight(tree->right);
if (l > r)
return l + 1;
return r + 1;
}
void BSTprint (TBST tree) {
if (tree != NULL) {
BSTprint(tree->left);
infoPrint(tree->info);
BSTprint(tree->right);
}
}
#ifndef TBST_H
#define TBST_H
#include "TInfo.h"
struct SBSTnode {
TInfo info;
struct SBSTnode *left;
struct SBSTnode *right;
};
typedef struct SBSTnode TBSTnode;
typedef TBSTnode *TBST;
TBSTnode *BSTnodeCreate(TInfo);
void BSTnodeDestroy(TBSTnode*);
TBST BSTcreate ();
TBST BSTdestroy (TBST);
TBST BSTsearch (TBST, TInfo);
TBST BSTmin (TBST);
TBST BSTmax (TBST);
TBST BSTinsert (TBST, TInfo);
TBST BSTdelete (TBST, TInfo);
void BSTprint(TBST);
#endif
/*
* THT: hash table a indirizzamento chiuso
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "THT.h"
#include "TInfo.h"
THT *HTcreate (int n) {
THT *ht = malloc (sizeof(THT));
assert (ht != NULL);
ht->bucket = malloc (n * sizeof(TList));
assert (ht->bucket != NULL);
for (int i=0; i<n; i++)
ht->bucket[i] = listCreate();
ht->n_bucket = n;
return ht;
}
void HTdestroy (THT* ht) {
for (int i=0; i<ht->n_bucket; i++)
ht->bucket[i] = listDestroy(ht->bucket[i]);
free (ht->bucket);
free (ht);
}
TValue *HTsearch (THT* ht, TKey key) {
unsigned h = keyHash(key) % ht->n_bucket;
TInfo info = {key};
TNode* node = listSearch(ht->bucket[h], info);
if (node != NULL)
return &node->info.value;
return NULL;
}
void HTinsert (THT* ht, TKey key, TValue value) {
unsigned h = keyHash(key) % ht->n_bucket;
TInfo info = {key, value};
TNode* node = listSearch(ht->bucket[h], info);
if (node != NULL)
node->info.value = value;
else
ht->bucket[h] = listInsert(ht->bucket[h], info);
}
void HTdelete (THT* ht, TKey key) {
unsigned h = keyHash(key) % ht->n_bucket;
TInfo info = {key};
ht->bucket[h] = listDelete(ht->bucket[h], info);
}
void HTprint(THT* ht) {
for (int i = 0; i < ht->n_bucket; i++)
for (TNode *node = ht->bucket[i]; node != NULL; node = node->link)
infoPrint(node->info);
}
void HTprintStructure (THT* ht) {
for (int i = 0; i < ht->n_bucket; i++) {
printf ("Bucket %2d -> ", i);
for (TNode *node = ht->bucket[i]; node != NULL; node = node->link)
infoPrint(node->info);
printf ("\n");
}
}
/*
* THT: hash table a indirizzamento chiuso
*/
#ifndef THT_H
#define THT_H
#include "TList.h"
typedef struct {
TList *bucket;
int n_bucket;
} THT;
THT *HTcreate (int n);
void HTdestroy (THT* ht);
void HTinsert (THT* ht, TKey key, TValue value);
void HTdelete (THT* ht, TKey key);
TValue *HTsearch (THT* ht, TKey key);
void HTprint(THT* ht);
void HTprintStructure(THT* ht);
#endif
/*
* TInfo: tipo elementare
*/
#include <stdio.h>
#include <string.h>
#include "TInfo.h"
int infoEqual (TInfo info1, TInfo info2) {
return info1.key == info2.key;
}
int infoGreater (TInfo info1, TInfo info2) {
return info1.key > info2.key;
}
int infoLess (TInfo info1, TInfo info2) {
return info1.key < info2.key;
}
void infoPrint (TInfo info) {
printf ("(%d: %s %s)\n", info.key, info.value.nome, info.value.cognome);
}
unsigned int keyHash (TKey key) {
return key;
}
/*
* TInfo: tipo elementare
*/
#ifndef TINFO_H
#define TINFO_H
typedef int TKey;
typedef struct {
char nome[20];
char cognome[20];
} TValue;
typedef struct {
TKey key;
TValue value;
} TInfo;
int infoEqual (TInfo, TInfo);
int infoGreater (TInfo, TInfo);
int infoLess (TInfo, TInfo);
void infoPrint (TInfo);
unsigned int keyHash (TKey);
#endif
/*
* TList: lista ordinata
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "TList.h"
/* operazioni sui nodi */
TNode *nodeCreate(TInfo info) {
TNode *new = malloc (sizeof(TNode));
if (new != NULL) {
new->info = info;
new->link = NULL;
}
return new;
}
void nodeDestroy(TNode *node) {
free (node);
}
/* operazioni sulle liste */
TList listCreate() {
return NULL;
}
TList listDestroy(TList list) {
TNode *node;
while (list != NULL) {
node = list;
list = list->link;
nodeDestroy(node);
}
return list;
}
void listPrint(TList list) {
if (list != NULL) {
infoPrint (list->info);
listPrint (list->link);
}
else
printf ("\n");
}
TNode *listSearch(TList list, TInfo info) {
if (list == NULL || infoGreater(list->info, info))
return NULL;
if (infoEqual(list->info, info))
return list;
return listSearch(list->link, info);
}
TList listInsert(TList l, TInfo info) {
if (l == NULL || infoGreater(l->info, info)) {
TNode *node = nodeCreate(info);
assert (node != NULL);
node->link = l;
return node;
}
l->link = listInsert(l->link, info);
return l;
}
TList listDelete(TList l, TInfo info) {
if (l == NULL || infoGreater(l->info, info))
return l;
if (infoEqual(l->info, info)) {
TList m = l->link;
nodeDestroy(l);
return m;
}
l->link = listDelete(l->link, info);
return l;
}
/*
* TList: lista ordinata
*/
#ifndef TLIST_H
#define TLIST_H
#include "TInfo.h"
struct SNode {
TInfo info;
struct SNode *link;
};
typedef struct SNode TNode;
typedef TNode *TList;
TNode *nodeCreate(TInfo);
void nodeDestroy(TNode*);
TList listCreate();
TList listDestroy(TList);
void listPrint(TList);
TNode *listSearch(TList, TInfo);
TList listInsert(TList, TInfo);
TList listDelete(TList, TInfo);
#endif