Homework A.A. 2013/2014
Informazioni
Quest pagina contiene le informazioni relative agli Homework assegnati agli studenti.
Gli Homework consegnati saranno verificati automaticamente. In particolare si verificherà:
- che la compilazione non generi errori
- che l'esecuzione sia corretta su diversi input
- che non ci sia eccessiva somiglianza con altri Homework consegnati
La verifica di similarità sarà anch'essa effettuata in modo automatico. In caso di copiatura, si riterranno nulli sia gli elaborati del copiante che del copiato.
Gli Homework dovranno essere consegnati entro la relativa scadenza che sarà comunicata in classe e che sarà ben visibile nella
pagina delle consegne. Non si accetteranno proroghe.
La consegna si effettua online alla pagina
Consegna Homework. Per consegnare è necessario registrarsi su Twiki a questa
pagina.
Il superamento degli Homework permetterà di non sostenere la prova di laboratorio ed, eventualmente, di disporre anche di un bonus di incremento di 1 o due punti punto sul voto finale come descritto in
Modalità d'esame.
In caso vi siano domande o problemi, potete rivolgetevi a Simone Silvestri (
silvestris@diNOSPAM.uniroma1.it)
Regole generali
1) Seguire esattamente le specifiche dell'input e dell'output.
2) Non includere getchar(), scanf(), System("pause") o qualunque altra chiamata che blocchi l'esecuzione del programma alla fine del codice dell'esercizio (utilizzatele se volete per provare il funzionamento ma non includete le istruzioni di attesa alla fine del file nella versione inviata).
3) Leggere l'input con scanf semplici. Es: scanf("%d",&n) per leggere un intero n, non inserire stampe del tipo printf("Inserisci il valore\n");
4) Inviare un unico file .zip contenente
tutti i sorgenti (.c) degli esercizi dell'Homework.
ATTENZIONE: non si deve fare una cartella contenente i file sorgenti e poi fare il .zip della cartella, ma si deve creare un file .zip contenente solo i file .c. Controllare bene l'estensione dei file inseriti nel file .zip, essa deve essere (.c) e non (.cc o altro).
5) Vanno inviati SOLO i sorgenti di codice e NON i file compilati (.out, .exe).
6) Il nome da dare ai file contenenti i sorgenti c è:
NomeCognome.NumEsercizio.c . Per Paolino Paperino:
PaolinoPaperino.1.c per il primo esercizio,
PaolinoPaperino.2.c per il secondo,
PaolinoPaperino.3.c per il terzo e così via. Il nome da dare al file zip è:
NomeCognome.zip. Sulle macchine del laboratorio di calcolo ciò si ottiene col seguente comando di shell (relativamente ai sorgenti dell'esempio):
$ zip PaolinoPaperino.zip PaolinoPaperino.1.c PaolinoPaperino.2.c PaolinoPaperino.3.c
Per verifica si può impartire il comando:
$ unzip PaolinoPaperino.zip
che estrae i file contenuti nel file zip e li ricrea nello stesso direttorio.
7)
Per inviare i sorgenti C:
7.1) E' necessario essere iscritti al sito twiki.di.uniroma1.it (si può fare dal link:
TWikiRegistration) .
7.2) Creare un file .zip contenente tutti i sorgenti degli esercizi dell'Homework
7.3) Collegarsi alla pagina
Consegna Homework
7.4) Inserire i propri dati (wikiname e password sono i dati di accesso a twiki)
7.5) Cliccare su "Browse" (o "Sfoglia", a seconda della lingua del vostro browser internet) e selezionare il file .zip contentente le vostre soluzioni
7.3) Cliccare su "spedisci la tua soluzione!" per effettuare la consegna
7.4) Riceverete una e-mail di conferma a cui non bisogna inviare reply
8) Se le soluzioni vengono inviate più di una volta, ogni nuovo invio sovrascrive i precedenti. Verrà quindi considerato l'ultima versione da voi inviata.
Risultati
- I risultati del terzo Homework si possono trovare qui
- I risultati del secondo Homework si possono trovare qui
- I risultati del primo Homework si possono trovare qui
- I risultati dell'Homework di prova si possono trovare qui
Homework da consegnare
- Homework 3 - Consegna entro: 20 Giugno 2014 ore 24:00
Esercizio 1
Un albero binario e' definito attraverso la seguente struttura:
typedef struct int_bin_tree{
int key;
struct int_bin_tree *left;
struct int_bin_tree *right;
}int_bin_tree;
L'esercizio prevede lo sviluppo di una libreria per l'utilizzo di alberi binari che implementi le seguenti funzionalita':
- calcolo del numero di elementi contenuti nell'albero,
- verifica della presenza di un elemento con una certa chiave,
- calcolo del numero di occorrenze di una certa chiave,
- recupero del puntatore a un elemento con chiave massima,
- recupero del puntatore a un elemento con chiave minima,
- stampa ordinata delle chiavi degli elementi dell'albero,
- cancellazione di un elemento che ha una certa chiave.
In particolare, si devono implementare le seguenti funzioni:
int num_nodes(int_bin_tree *tree)
La funzione ritorna il numero di nodi presenti nell'albero tree. Un albero vuoto ha zero nodi.
int contains(int_bin_tree *tree, int x)
La funzione ritorna 1 se nell'albero tree e' presente almeno un nodo con chiave x.
int occurrences(int_bin_tree *tree, int x)
La funzione ritorna il numero di elementi dell'albero tree aventi chiave x. La funzione ritorna 0 se l'albero e' vuoto.
int_bin_tree* min_key(int_bin_tree *tree)
La funzione ritorna il puntatore al nodo dell'albero avente chiave minima, NULL se l'albero e' vuoto. Se sono presenti piu' nodi con chiave minima si puo' ritornare il puntatore ad uno qualsiasi di questi.
int_bin_tree* max_key(int_bin_tree *tree)
La funzione ritorna il puntatore al nodo dell'albero avente chiave massima, NULL se l'albero e' vuoto. Se sono presenti piu' nodi con chiave massima si puo' ritornare il puntatore ad uno qualsiasi di questi.
int * get_ordered_array(int_bin_tree *tree)
La funzione alloca un vettore di interi di dimensione pari al numero di elementi dell'albero. Il vettore deve contere le chiavi presenti nell'albero ordinate in modo crescente. Se l'albero e' vuoto la funzione ritorna NULL senza allocare nulla.
int_bin_tree * delete(int_bin_tree *tree, int x)
La funzione elimina un nodo con chiave x dall'albero, se presente. Se sono presenti piu' elementi con chiave x si puo' eliminare uno qualsiasi di questi. La funzione ritorna il puntatore alla radice dell'albero.
Si deve modificare
QUESTO file riempendo il corpo delle funzioni sopra elencate. Si possono tuttavia utilizzare funzioni ausiliarie. Il main prende in input un intero a ed una sequenza di interi positivi, terminata da un numero negativo. L'intero a serve a testare diverse funzioni, come spiegato in seguito, gli altri interi letti sono invece inseriti nell'albero. La funzione di inserimento insert() e' gia' implementata e non deve essere modificata.
L'homework e' suddiviso in tre parti. Nella prima parte (a = 1) si testeranno solamente le funzioni num_nodes(), contains() e occurencies(). Nella seconda parte (a = 2) si testeranno invece le funzioni min_key(), max_key(). Nella terza parte (a = 3) si testeranno infine le funzioni get_ordered_array() e delete(). Si deve comunque consegnare un unico file con estensione .1.c. La correzione verra' poi effettuata come se si trattasse di esercizi distinti.
Esempio 1 (a = 1)
Si inseriscono i valori
1
1
2
3
4
5
6
7
8
9
10
11
12
13
-1
Il programma deve stampare:
Num nodes 13
contains(0) = 0 occurences(0) = 0
contains(1) = 1 occurences(1) = 1
contains(2) = 1 occurences(2) = 1
contains(3) = 1 occurences(3) = 1
contains(4) = 1 occurences(4) = 1
contains(5) = 1 occurences(5) = 1
contains(6) = 1 occurences(6) = 1
contains(7) = 1 occurences(7) = 1
contains(8) = 1 occurences(8) = 1
contains(9) = 1 occurences(9) = 1
contains(10) = 1 occurences(10) = 1
contains(11) = 1 occurences(11) = 1
contains(12) = 1 occurences(12) = 1
contains(13) = 1 occurences(13) = 1
contains(14) = 0 occurences(14) = 0
...
contains(99) = 0 occurences(99) = 0
Esempio 2 (a = 2)
Si inseriscono i valori
2
1
2
3
4
5
6
7
8
9
10
11
12
13
-1
Il programma deve stampare
1
13
Esempio 3 (a = 3)
Si inseriscono i valori
3
5
5
5
5
3
3
3
5
5
5
1
1
1
3
3
5
5
-1
Il programma deve stampare
1 1 1 3 3 3 3 3 5 5 5 5 5 5 5 5 5
Deleting 1
Num nodes 16
Deleting 1
Num nodes 15
Deleting 1
Num nodes 14
Deleting 3
Num nodes 13
Deleting 3
Num nodes 12
Deleting 3
Num nodes 11
Deleting 3
Num nodes 10
Deleting 3
Num nodes 9
Deleting 5
Num nodes 8
Deleting 5
Num nodes 7
Deleting 5
Num nodes 6
Deleting 5
Num nodes 5
Deleting 5
Num nodes 4
Deleting 5
Num nodes 3
Deleting 5
Num nodes 2
Deleting 5
Num nodes 1
Deleting 5
Num nodes 0
Errori comuni
Homework precedenti