code. compile. run. debug. share.
/*
* 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"
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;
}
/*
* 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
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|