Lista lineare.

definizione: La lista lineare è:

- la lista vuota

- o una coppia di elementi in cui il primo è un dato, il secondo una lista.

La definizione proposta è ricorsiva: nella definizione di lista compare la parola lista.
Ogni lista si può immaginare come una coppia di elementi in cui il primo è un dato,il secondo è la lista degli elementi rimanenti.

Con questa definizione la lista lineare può essere realizzata utilizzando le seguenti primitive:

costruttori:

	Lista consNull();	/* crea la lista vuota */
	Lista cons(Dato, Lista);	/* crea la coppia che ha come primo elemento il dato, il secondo una lista */

selettori:

	Dato car(Lista);	/* restituisce il primo elemento di una coppia	*/
	Lista cdr(Lista);	/* restituisce il secondo elemento, cioè una lista	*/

E' necessaria una funzione che permetta di conoscere se una lista è vuota:

int isNull(Lista);

/* 1 se la lista è vuota, 0 altrimenti */

Esempi.

1. Realizzare una funzione che restituisce una lista di interi. Gli interi vengono letti da tastiera.

Lista leggi( void ) {
        int *i = (int*)malloc(sizeof(int));
        
        printf("$$ ");
        if(scanf("%d",i) == 1)

return cons(i, leggi());

        return consNull();
}

La funzione è ricorsiva. Si basa sulla seguente definizione:

        se non c'è numero da leggere la lista è vuota
        altrimenti la lista è la coppia formata dal dato letto e dai rimanenti da leggere.


2. Stampare una lista.

La definizione adottata è la seguente:
        se la lista non è vuota

		stampa il primo elemento
		stampa la lista rimanente

Che diventa:

void stampa(Lista l) {        
        if(!isNull(l)){

		printf("%d ", *(int*)car(l) );
		stampa(cdr(l));

        }
}

3. Stampa una lista in ordine inverso.

La definizione adottata è la seguente:

        se la lista non è vuota

		stampa gli elementi rimanenti
		stampa il primo elemento

Che diventa:

void stamparev(Lista l) {
        if(!isListaNull(l)){

		stamparev(cdr(l));
		printf("%d ", *(int*)car(l) );

        }
}

4. Sommare tutti gli elementi di una lista di interi.

La definizione adottata è la seguente:

        se la lista è vuota la somma è 0
        altrimenti si somma il primo elemento della lista con la somma della lista rimanente.

int somma(Lista l) {
        if(isNull(l)) return 0;
        return *(int*)car(l) + somma(cdr(l));
}

5. Sommare tutti gli elementi pari di una lista di interi.

La definizione adottata è la seguente:

        se la lista è vuota la somma è 0
        se il primo elemento è pari

lo si somma alla somma degli elementi pari della lista rimanente

        altrimenti si sommano gli elementi pari della lista rimanente.

int sommaPari(Lista l){
        if(isNull(l)) return 0;
        if(pari(car(l)))

		return *(int*)car(l) + sommaPari(cdr(l));
		return sommaPari(cdr(l));

}

6. Contare quanti elementi di una lista sono divisibili per 3.

La definizione adottata è la seguente:

        se la lista è vuota i numeri divisibili per 3 sono 0
        se il primo elemento è divisibile per 3 il numero degli elementi è

1 + il numero degli elementi divisibile per 3 della lista rimanente

        altrimenti è il numero degli elementi divisibile per 3 della lista rimanente

int conta3(Lista l){
        if(isNull(l)) return 0;
        if(mod3(car(l)))

return 1 + conta3(cdr(l));

        return conta3(cdr(l));
}