/*
* Una biblioteca deve riorganizzare alcuni elenchi di libri tra cui elenco1
* (un BST), elenco2 (una HT) ed elenco3 (una lista).
* In ciascuna struttura un libro e' rappresentato da
* un codice ISBN numerico (campo chiave) e da un titolo.
*
* Si dovra' realizzare un programma che individui tutti i libri presenti in
* entrambi gli elenchi, li stampi in ordine crescente di ISBN (completare nella
* funzione main) e che sostituisca in elenco2
* il codice ISBN di un libro in base al titolo.
* Infine, da elenco3 verranno rimossi tutti i libri con ISBN pari e anche l'elemento
* con ISBN piu' piccolo.
* Per realizzare tale programma occorre sviluppare le seguenti funzioni.
*
* 1) BSTHTdupList(bst, ht, list): funzione RICORSIVA che copia in list (lista
* ordinata) tutti i libri che sono presenti contemporaneamente sia in bst che
* in ht (fa fede il codice ISBN).
*
* 2) HTchangeKey(ht, value, newKey): funzione ITERATIVA che sostituisce in ht
* la chiave associata a value con la nuova chiave newKey.
* Se value non e' presente in ht allora non fa nulla.
* Se value compare piu' di una volta in ht allora alle fine ci sara' una sola
* coppia (newKey, value). Se newKey e' gia' presente in ht allora il vecchio valore
* viene rimosso e poi viene inserito il nuovo valore.
*
* 3) listDeleteEven(list): funzione RICORSIVA che elimina da list tutti i
* libri con ISBN pari. Restituisce la lista aggiornata.
*
* 4) deleteMinList(list): funzione che elimina il libro con ISBN piu' basso.
*/
#include <stdio.h>
#include <string.h>
#include "THT.h"
#include "TBST.h"
#include "TArray.h"
#include "TList.h"
TList BSTHTdupList(TBST bst, THT *ht, TList list) {
//CASO BASE: l'albero è vuoto, niente da aggiungere
if(bst != NULL) {
//DIVIDE E COMBINA: aggiungo il sotto-albero sinistro (elementi minori)
list = BSTHTdupList(bst->left, ht, list);
bst->left = BSTHTdupList(bst->left, ht, list);
//Aggiungo l'elemento
list = listInsert(list, bst->info);
//Aggiungo il sotto-albero destro (elementi maggiori)
list = BSTHTdupList(bst->right, ht, list);
bst->right = BSTHTdupList(bst->right, ht, list);
}
return list;
}
void HTchangeKey(THT* ht, TValue value, TKey newKey) {
TList list = listCreate();
TNode* node = nodeCreate(list->info);
if (list == NULL)
return;
for (int i = 0; i < ht->n_bucket; i++)
for (TNode *node = ht->bucket[i]; node != NULL; node = node->link)
if (HTsearch(ht, list->info.key) == NULL)
HTinsert(ht, list->info.key, list->info.value);
list = listInsert(list,node->info);
}
TList listDeleteEven(TList list) {
/* Caso Base */
if(list == NULL) {
return list;
}
/* Divide et Impera */
TList tail = listDeleteEven(list->link);
if(listDeleteEven(list->link))
list->link = tail;
else {
nodeDestroy(list);
list = tail;
}
/* Combina */
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;
}
int main() {
TBST elenco1 = BSTcreate();
elenco1 = BSTinsert(elenco1, (TInfo) {1321, "Le mille e una notte"});
elenco1 = BSTinsert(elenco1, (TInfo) {2372, "Orgoglio e pregiudizio"});
elenco1 = BSTinsert(elenco1, (TInfo) {3432, "Finzioni"});
elenco1 = BSTinsert(elenco1, (TInfo) {4223, "Delitto e castigo"});
elenco1 = BSTinsert(elenco1, (TInfo) {1445, "Il processo"});
elenco1 = BSTinsert(elenco1, (TInfo) {2234, "Madame Bovary"});
elenco1 = BSTinsert(elenco1, (TInfo) {1238, "L'amore ai tempi del colera"});
elenco1 = BSTinsert(elenco1, (TInfo) {6643, "Il vecchio e il mare"});
elenco1 = BSTinsert(elenco1, (TInfo) {1111, "Anna Karenina"});
THT* elenco2 = HTcreate(5);
HTinsert(elenco2, 3357, (TValue) {"Il rosso e il nero"});
HTinsert(elenco2, 7675, (TValue) {"Alla ricerca del tempo perduto"});
HTinsert(elenco2, 4222, (TValue) {"Moby-Dick"});
HTinsert(elenco2, 1445, (TValue) {"Il processo"});
HTinsert(elenco2, 3233, (TValue) {"Pippi Calzelunghe"});
HTinsert(elenco2, 3321, (TValue) {"L'uomo senza qualita'"});
HTinsert(elenco2, 1111, (TValue) {"Anna Karenina"});
HTinsert(elenco2, 9090, (TValue) {"Le metamorfosi"});
HTinsert(elenco2, 3432, (TValue) {"Finzioni"});
printf("Libri in elenco1 (BST):\n");
BSTprint(elenco1);
printf("\nLibri in elenco2 (HT):\n");
HTprint(elenco2);
TList elenco3 = listCreate();
printf("\nCopio in elenco3 (lista) i libri contenuti sia in elenco1 che elenco2.");
elenco3 = BSTHTdupList (elenco1, elenco2, elenco3);
printf("\nLibri in elenco3 in ordine crescente di ISBN:\n");
/* Completare con la chiamata a funzione corretta */
listPrint(elenco3);
TValue titolo = (TValue) {"Il processo"};
TKey nuovoISBN = 1000;
printf("\nCambio in elenco2 (HT) il codice di '%s' in %d", titolo, nuovoISBN);
HTchangeKey(elenco2, titolo, nuovoISBN);
printf("\nLibri in elenco2 dopo la modifica:\n");
HTprint(elenco2);
elenco3 = listDeleteEven(elenco3);
printf("\nStudenti in elenco3 (Lista)\n(dopo aver rimosso gli ISBN pari)\n");
listPrint(elenco3);
elenco3 = deleteMinList(elenco3);
printf("\nLibri in elenco3 (Lista)\n(tutti quelli di elenco3 tranne ISBN piu' basso)\n");
listPrint(elenco3);
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