Homework 3 - Consegna entro: 24 Maggio 2012 ore 24:00 

Esercizio 1

Si definisce la struttura dyn_array come segue:

typedef struct dyn_array{
   int *V;
   int lenght;
   int next_index;
} dyn_array;

Tale struttura rappresenta un array dinamico di interi. In particolare, V e' il vettore che contiene gli elementi interi, length e' la lunghezza attuale di V, next_index e' l'indice del prossimo elemento di V su cui scrivere.

In un certo momento dell'esecuzione del programma, il vettore V ha dimensione length ed e contiene valori da 0 a next_index-1.

Lo scopo dell'homework e' quello di fornire un interfaccia, costituita da un insieme di funzioni, che permettano di utilizzare la struttura dyn_array senza preoccuparsi dell'attuale dimensione di V. Deve cioe' essere possibile eseguire operazioni su V, come l'inserimento e la cancellazione, come se V avesse una capacità infinita, ma contemporaneamente facendo sì che V abbia una dimensione ragionevole rispetto agli elementi che effettivamente contiene.

Il programma definisce una costante SIZE, posta a 10. Si vuole che la dimensione attuale di V ed il numero di elementi effettivamente contenuti non si discostino mai di piu' di SIZE, cioe' sia da un puntatore ad un dyn_array, si vuole che ((da->length - da->next_index) < SIZE). In altre parole, non devono esserci piu' SIZE-1 elementi vuoti.

Se il vettore non contiene elementi, cioe' se da->next_index = 0, il vettore V dovra' avere dimensione SIZE.

L'homework prevede che sia il main, la funzione di stampa, la struttura dati e la costante SIZE, siano gia' implementate e quindi NON DEVONO ESSERE MODIFICATE.

Possono essere aggiunte ulteriori funzioni oltre a quelle da implementare.

Si dovranno invece implementare le seguenti funzioni:

Funzione di creazione ed inizializzazione:

   dyn_array * create_dyn_array(int size)

Tale funzione prende in input la dimensione predefinita iniziale del vettore size e restituisce il puntatore alla struttura allocata.

La funzione deve:

    allocare la zona di memoria per la struttura dyn_array
    allocare il vettore di interi di interi di dimensione size
    inizializzare i valori di length a size e next_index a 0. 

Funzione di aggiunta di un elemento:

   
   void add_elem(dyn_array *da, int value, int size)

Tale funzione aggiunge un elemento con valore value in posizine da->next_index al vettore da->V

Se il vettore e' pieno, cioe' prima dell'inserimento da->next_index == da->length, la funzione deve:

    allocare un nuovo vettore V' di dimensione da->length + size
    copiare i valori di V in V'
    inserire il nuovo elemento in V'
    liberare la memoria occupata da da->V
    Sostituire da->V con V'
    Aggiornare da->next_index e da->length in modo opportuno 

Funzione di rimozione di un elemento in una data posizione:

   void remove_elem_at(dyn_array *da, int index, int size)

La funzione rimuove l'elemento in posizine index dal vettore da->V. Se index > da->next_index la funzione non fa nulla, altrimenti rimuove l'elemento in posizione index spostando verso sinistra tutti gli altri di una posizione.

Se il vettore risultante ha una zona vuota di dimensione maggiore di size, cioe' se (da->next_index <= (da->length - size)), la funzione deve:

    allocare un nuovo vettore V' di dimensione da->length - size
    copiare i valori di V in V'
    liberare la memoria occupata da da->V
    Sostituire da->V con V'
    Aggiornare da->next_index e da->length in modo opportuno 

Funzione di rimozione di tutti gli elementi con un certo valore:

   void remove_value(dyn_array *da, int value, int size)

La funzione rimuove dal vettore da->V tutti gli elementi con valore value Gli elementi rimanenti devono essere spostati verso sinistra cosi' da non lasciare posizioni vuote.

Se il vettore risultante ha una zona vuota di dimensione maggiore di size, cioe' se (da->next_index <= (da->length - size)), la funzione deve:

    trovare il piu' piccolo valore k tale che k*size > da->next_index
    allocare un nuovo vettore V' di dimensione k*size
    copiare i valori di V in V'
    liberare la memoria occupata da da->V
    Sostituire da->V con V'
    Aggiornare da->next_index e da->length in modo opportuno 

Funzione di ordinamento:

   void sort_dyn_array(dyn_array *da)

La funzione deve ordinare il vettore da->V in modo CRESCENTE. Le sue dimensioni rimangono invariate. Si puo' implementare con un qualsiasi algoritmo di quelli visti a lezione.

Si dovra' modificare QUESTO file scrivendo il corpo delle funzioni sopra elencate.

Il main e la funzione di stampa sono date e NON DEVONO ESSERE MODIFICATE.

I programmi saranno verificati sullo stesso main presente nel codice. Non si devono aggiungere stampe ulteriori.

Esempio:

Si vogliono inserire i seguenti valori,:

83
64
77
15
93
35
86
92
64
21
62
27
90
64
63
26
40
26

La lettura termina quando si inserisce -1, quindi si inseriranno da tastiera i valori precedenti seguiti da -1, premendo invio dopo OGNI numero inserito.

I numeri inseriti sono 18, quindi il vettore avrà dimensione 20 e due posizioni saranno non utilizzate. Il programma stampera':

20
18
83 64 77 15 93 35 86 92 64 21 62 27 90 64 63 26 40 26 X X 

Successivamente il main prevede l'eliminazione di alcuni elementi in determinate posizioni. Gli elementi restanti sono 9, possono essere quindi accomodati in un vettore di dimensione SIZE (10). Il programma quindi stampera':

10
9
64 15 35 92 21 27 64 26 26 X 

Il main prevede ora l'eliminazione di tutti gli elementi con valore 64, nel vettore ne sono presenti due. Rimarranno quindi 3 posizioni inutilizzate. Il programma quindi stampera':

10
7
15 35 92 21 27 26 26 X X X 

Infine, il programma prevede l'ordinamento del vettore. La stampa quindi sara':

10
7
15 21 26 26 27 35 92 X X X 

L'esecuzione corretta e' quindi:

83
64
77
15
93
35
86
92
64
21
62
27
90
64
63
26
40
26
-1
20
18
83 64 77 15 93 35 86 92 64 21 62 27 90 64 63 26 40 26 X X 
10
9
64 15 35 92 21 27 64 26 26 X 
10
7
15 35 92 21 27 26 26 X X X 
10
7
15 21 26 26 27 35 92 X X X 

L'input utilizzato nell'esempio puo' essere scaricato qui, il relativo output qui.

Si puo' utilizzare questo programma per generare input validi di grandi dimensioni (centinaia, migliaia, ..., di elementi) e poi utilizzarli con l'indirizzamento dell'input. Dopo aver compilato il programma lo si puo' eseguire come segue:

$crea_input_hw_3 nomefile 1000

Il programma creera' un file di nome nomefile che conterra' 1000 valori seguiti da -1. Sara' possibile passare al vostro eseguibile tale file tramite indirizzamento dell'input.

$./a.out < nomefile