Argomenti
- Introduzione
- Il compattamento di un array
- La fusione di due array
- video della lezione
- Risorse Aggiuntive
Introduzione
Gli array sono una struttura dati omogenea costituita da elementi delo stesso tipo, nelle lezioni precedenti sono state esaminate l’operazione di caricamento dati, la stmpa degli elementi di un array, la ricerca e l’ordinamento.
Per questi argomenti vedasi la lezione 9 e lezione 10.
La lezione di oggi introduce alcune operazioni aggiuntive quali il compattamento di un array e la fusione di due array che coinvolgono più strutture dati contemporaneamente.
Il compattamento di un array
Il compattamento è un’operazione legata alla cancellazione degli elementi di un array.
Immaginiamo di voler eliminare degli elementi dall’array; esistono due metodi per completare questa operazione la cancellazione “logica” e quella “fisica”. Nel primo caso l’elemento da cancellare una volta individuato viene oscurato con un valore fuori dal contesto ad esempio se il mio vettore è costituito da numeri positivi, tutti i numeri negativi sono “logicamente cancellati”.
In questo modo è sempre possibile ripristinarli, oppure un array di stringhe composto dai nominativi di N persone, consideriamo un elemento cancellato quanto antepniamo un asterisco o altro simbolo che non fa parte dell’alfabeto.
Ad esempio assegnato l’array x di stringhe
Paolo | Albero | Michele | Pasquale | *Ettore | Lidia | Andrea | *Vincenzo | Luisa | Enrico |
Per eliminare in modo definitivo gli elementi è ncecessario traslare gli elementi non contrassegnati al posto di quelli contrassegnati. In altri termini il nuovo array avrà una dimensione pari alla dimensione iniziale dell’array meno il numero degli elementi da cancellare. Questa operazione sarà eseguita mediante il compattamento che ricopia l’array senza i valori contrassegnati in un nuovo array di dimensioni inferiore. Non è l’unico metodo per svolgere questa operazione, ma è la più semplice.
La modalità migliore è utilizzare gli array dinamici per fare questo, per far ciò è necessario introdurre i puntatori che saranno introdotti fra due lezioni.
L’algoritmo è quindi in temrini di flowchart:
L’algoritmo in questo caso elimina in modo definitivo dall’array tutti i valori negativi, ricopiando i valori positivi in un nuovo array e ritornando per riferimento l’array ottenuto e il valore della dimensione nuova dell’array.
Il codice C è:
void compatta(int x[],int y[], int l, int *m)
{
int i, j=0;
for (i=0;i<l;i++)
{
if (x[i]>=0)
{
*(y+j)=x[i];
j++;
}
}
*m=j;
}
La fusione di due ‘array
La fusione consiste nell’operazione di prendere due o più array di dimensioni non necessariamente identiche e fonderli in un unico nuovo array che eventualmente contiene gli elementi ordinati.
L’ordinamento puà essere fatto con due metodologie: la prima più semplice ovvero eseguendo l’ordinamento dopo la fusione, il secondo ordinando gli elementi man mano che sono inseriti nell’array (Insertion sort).
Il metodo più semplice è il primo e considerato i due array una di dimensione n1 e l’altro di dimensione n2, l’array risultante è di dimensione n1+n2.
Il codice C dell’algoritmo di fusione è:
void fusione(int x[],int y[], int z[], int l, int m)
{
int k;
printf("l:%d, m:%d ",l,m);
for (k=0;k<l;k++)
z[k]=x[k];
for (k=0;k<m;k++)
z[k+l]=y[k];
}
Questo procedimento algoritmico è molto semplice ma molto costoso in termini computazionali quando le dimensioni dei due array sono molto grandi in quanto il tempo di esecuzione cresce linearmente come la somma delle due dimensioni n1+n2 che può essere approssimato a n per n che tende ad infinito. In questo caso si dice che l’algoritmo è un O(n).
Questo argomento sarà discusso quando si parlerà della ricorsione.
Il programma completo è visibile nel video della lezione n.11
Video della Lezione n.11
Risorse aggiuntive
Sei interessato al C++ ? Iscriviti a questo corso base sul portale Udemy ove avrai la possibilità di provare i tuoi programmi e fruire di lezioni e contenuti esclusivi in promozione Link all’iscrizione al corso