Gestione di sequenze di elementi: strutture dati elementari

Sequenza di elementi: una sequenza di variabili (numerate con interi progressivi, a partire da 0)che permette di fare le seguenti operazioni:
1) accesso al k-esimo elemento della sequenza
2) scansione (o attraversamento) della sequenza, ovvero un ciclo in cui ad ogni
	iterazione si accede ad un elemento della sequenza, in ordine
3) inserimento di un nuovo elemento nella sequenza in posizione h
	(senza modificare gli altri elementi, ma allungando la sequenza)
4) concatenare due sequenze

Mostriamo, attraverso esempi, le più semplici strutture dati per memorizzare una sequenza di N interi.
Consideriamo solo strutture dati allocate staticamente.

Per ciascuna struttura che consideriamo, mostriamo un esempio di dichiarazione e discutiamo come realizzare le 4 operazioni sopra descritte.
	
A) sequenza in array allocato staticamente

int array[ N ] = { 1, 2, 3, 4 };

1) si può realizzare facendo un semplice accesso
	array[ k ]
	richiede 1 operazione
	
2) si può realizzare con
	for ( int i = 0 ; i < N ; i++ )
		printf( "%d\n", a[ i ] );
	richiede un numero di operazioni proporzionale a N
	
3) e 4) non sono possibili

B) sequenza in buffer allocato staticamente
con buffer si intende un array che ha lunghezza fissa ma maggiore di 
quella della sequenza, il che consente di allungare la sequenza fino
a raggiungere una lunghezza massima

B.1) Realizzazione del buffer mediante un array allocato staticamente e
uso di un valore speciale per indicare la fine della sequenza

esempio: una sequenza 4 di interi positivi in un buffer di lunghezza 10;
il valore -1 indica la fine della sequenza

int array[ 10 ] = { 1, 2, 3, 4, -1 };

1) si può realizzare facendo un semplice accesso
	array[ k ]
	richiede 1 operazione
	
2) si può realizzare con
	for ( int i = 0 ; array[ i ] >=0 ; i++ )
		printf( "%d\n", a[ i ] );
	richiede un numero di operazioni proporzionale a N
	
3) (inserimento di 6 in posizione h) si può realizzare con
	for ( i = h ; array[ i ] >= 0 ; i++ ) ; 
	for ( int j = i ; j > h ; j-- ) a[ j + 1 ] = a[ j ];
	a[ h ] = 6;
	richiede un numero di operazioni proporzionale a N
	
4) (concatenazione della sequenza di N2 elementi in array2 a quella di N1 elementi in array1) si può realizzare con
	for ( i = 0 ; array1[ i ] >= 0 ; i++ ) ;
	for ( j = 0 ; array2[ j ] >= 0 ; j++ ) array1[ i + j ] = array2[ j ];
	array1[ i + j + 1 ] = -1;
	richiede un numero di operazioni proporzionale a N1+N2
	
B.2) Realizzazione del buffer mediante un array allocato staticamente e
memorizzazione esplicita della lunghezza della sequenza

esempio: una sequenza 4 di interi positivi in un buffer di lunghezza 10;

struct buf {
	int arr[ 10 ] = { 1, 2, 3, 4 };
	int len = 4;
} buffer;

1) si può realizzare con un semplice accesso
	buffer.arr[ k ]
	richiede 1 operazione
	
2) si può realizzare con
	for ( int i = 0 ; i < buffer.len ; i++ )
		printf( "%d\n", buffer.arr[ i ] );
	richiede un numero di operazioni proporzionale a N
	
3) (inserimento di 6 in posizione h) si può realizzare con
	for ( int j = buffer.len ; j > h ; j-- )
		buffer.arr[ j + 1 ] = buffer.arr[ j ];
	buffer.arr[ h ] = 6;
	richiede un numero di operazioni proporzionale a N-h
	
4) (concateno la sequenza di N1 elementi in buffer1 a quella di N2 elementi in buffer2) si può realizzare con
	i = buffer1.len;
	for ( j = 0 ; j < buffer2.len ; j++ ) buffer1.arr[ i + j ] = array2[ j ];
	array1[ i + j + 1 ] = -1;
	richiede un numero di operazioni proporzionale a N1 + N2


C) Uso di liste: si veda l'esempio Sequences Lists

Confronto tra soluzione B.2 e soluzione C

1) accesso ad un elemento in posizione h
	B.2) 1 operazione
	C) numero di operazioni proporzionale ad h
	
2) scansione della sequenza di lunghezza N
 	B.2) numero di operazioni proporzionale a N
 	C) numero di operazioni proporzionale a N
 	
3) inserimento di un elemento in posizione h di una sequenza di lunghezza N
 	B.2) numero di operazioni proporzionale a N-h
 	C) numero di operazioni proporzionale a h

4) concatenazione di una sequenza di N1 elementi con una di N2 elementi
	B.2) numero di operazioni proporzionale a N1 + N2
	C) numero di operazioni proporzionale a N1