code. compile. run. debug. share.
/*
* 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;
}
/*
* 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 |
|---|