Liste a concatenamento semplice

In genere le liste sono costituite da una struttura in cui `e inserito un puntatore dello stesso tipo della struttura che si collegher´a ad un altro elemento della lista e cos´ı via. Per inserire un nuovo elemento nella lista si possono usare due criteri differenti: se si vuole ottenere una lista ordinata il nuovo elemento deve essere inserito nella posizione corretta; l’altro criterio `e di inserire un nuovo elemento in un posto generico della lista, solitamente all’inizio o alla fine.

Logicamente il primo criterio `e molto pi`u difficile da rispettare perch´e impone che prima di effettuare l’inserimento debba essere fatta una ricerca all’interno della lista in modo tale da stabilire la posizione in cui deve essere inserito il nuovo elemento. Ovviamente questo criterio ha i suoi lati positivi, infatti se volessimo stampare la lista ordinatamente basterebbe soltanto im- plementare la funzione che scorrendo la lista ne va stampando gli elementi. Se invece la lista non fosse stata precedentemente ordinata, prima della stampa

9.7 Le liste Imparare il C pag. 69 gli elementi in ordine, avremmo dovuto ordinarli. Naturalmente se non ci interessa l’ordine della lista, ma soltanto la momorizzazione di dati, potremo decidere di inserire gli elementi in modo disordinato.

Operazioni sulle liste:

inserimento di un nuovo elemento cancellazione

scorrimento

Anche se nominalmente le operazioni possibili sulle liste sono simili a quelle sulle code e sulle pile, praticamente si differiscono per dei particolari molto importanti. Infatti le liste consentono l’estrazione non distruttiva di ogni singolo elemento, mentre le pile e le code no.

In oltre, quando si lavora con le liste allocate dinamicamente dovremo in- evitabilmente lavorare con dei puntatori semplici o doppi, e questo richieder`a maggiore attenzione da parte del programmatore. Infatti una cattiva gestione dei puntatori potrebbe portare ad un comportamento anomalo del program- ma stesso; tipico esempio: il programmma funzione correttamente quasi sem- pre, ma quando si caricano troppi dati o una lista diviene molto grande si hanno risultati imprevedibili (scomparsa di dati o sovrascrittura di quelli esistenti. 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define VAL 4 5

6 /* elemento della lista */ 7 struct elemento{

8 int x;

9 struct elemento *next; 10 };

11 12

13 void ins_lista(int n, struct elemento **lista); 14 void stampa_lista(struct elemento *lista); 15 void svuota(struct elemento **lista); 16

17 18 19

20 int main(){

22 int i,p; 23 24 for(i=0;i<VAL;i++){ 25 printf("inserisci un numero: "); 26 scanf("%d",&p); 27

28 /* funzione di inserimento (si possono 29 scegliere 3 tipi di inserimento) */ 30 ins_lista(p,&lista); 31 } 32 stampa_lista(lista); 33 svuota(&lista); 34 stampa_lista(lista); 35 } 36 37

38 void stampa_lista(struct elemento *lista){ 39 struct elemento *tmp;

40 int i=0; 41

42 tmp=lista;

43 while(tmp){ /* equivale a scrivere while(tmp!=NULL) */ 44 printf("elemento: %d\n",tmp->x);

45 tmp=tmp->next;

46 i++;

47 }

48 printf("in questa lista ci sono %d elementi\n",i); 49 }

50 51

52 /* funzione che cancella tutti gli elementi della lista */ 53 void svuota(struct elemento **lista){

54 struct elemento *tmp; 55 56 if(*lista==NULL) 57 return; 58 else{ 59 tmp=*lista; 60 *lista=(*lista)->next; 61 free(tmp); 62 svuota(&(*lista));

9.7 Le liste Imparare il C pag. 71

63 /* funzione ricorsiva che richiama se stessa ma con 64 l’indirizzo del puntatore successivo */

65 }

66 }

La funzione non inserita nel codice precedente sar`a studiata adesso in modo da far vedere come avviene l’inserimento ordinato, quello in testa e quello in coda.

Quando si vuole inserire un nuovo elemento in una lista, se si vuole man- tenere uno specifico ordine si dovranno fissare delle regole. Ad esempio, si vuole realizzare una lista con ordine crescente; ci`o vuol dire che ogni elemen- to della lista dovr`a essere preceduto da un elemento pi`u piccolo e dovr`a essere seguito da un elemento pi`u grande. Quindi la funzione prima di inserire un nuovo elemento nella lista deve cercare la posizione corretta di inserimento. void ins_lista(int n, struct elemento **lista){

struct elemento *punt, *punt_prec, *punt_cor; punt_cor=*lista;

/* se punt_cor e’ nullo o n e’ minore o uguale di punt_cor->next */ if(punt_cor==NULL || //se la lista e’ vuota o

n <= punt_cor->x)

/*il nuovo elemento e’ minore o uguale

a punt_cor->x lo inserisce in testa alla lista */ {

punt=(struct elemento *)malloc(sizeof(struct elemento)); punt->x=n;

punt->next=punt_cor; *lista=punt;

} else{

while(punt_cor!=NULL && n > punt_cor->x){

/* fino a quando non raggiunge la fine della lista o fino a quando n e’ monore di pun_cor->x scorre la lista; queste 2 condizioni devono essere verificate entrambe per scorrere la lista */ punt_prec=punt_cor;

punt_cor=punt_cor->next; }

punt->x=n;

/* inserisce il nuovo elemento tra punt_prec e punt_cor */ punt->next=punt_cor;

punt_prec->next=punt; }

}

Se invece vogliamo che ogni elemento sia inserito all’inizio della lista basta fare in modo che la lista punti al nuovo elemento e il resto della lista venga attaccata al nuovo elemento inserito.

void ins_lista(int n, struct elemento **lista){ struct elemento *new;

/* alloca lo spazio per un nuovo elemento */

new=(struct elemento *)malloc(sizeof(struct elemento)); new->x=n;

new->next=(*lista);//il puntatore del nuovo elemento punta a *lista *lista=new; //il nuovo elemento e’ inserito in testa alla lista }

Se vogliamo che il nuovo elemento venga inserito alla fine della lista, cio`e vogliamo che sia l’ultimo della lista, basta ricordarci che il puntatore dell’ultimo elemento della lista sar`a un puntatore nullo, quindi per trovare l’ultimo elemento della lista basta andare alla ricerca di questo puntatore nullo e ridirigerlo verso il nuovo elemento della lista che cos`ı sar`a attaccato ad essa.

void ins_lista(int n, struct elemento **lista){ struct elemento *new;

if(*lista==NULL){

//controllo per verificare se la lista e’ vuota

new=(struct elemento *)malloc(sizeof(struct elemento)); new->x=n; new->next=NULL; *lista=new; } else ins_lista(n, &(*lista)->next);

9.7 Le liste Imparare il C pag. 73 /* viene richiamata la funzione ricorsivamente fino a quando non

si raggiunge la fine della lista */ }

Capitolo 10

Tempo

Sorry, questo capitolo deve essere ancora iniziato, stiamo provvedendo. Se hai suggerimenti non esitare a contattarci.

Capitolo 11

Lo standard c99

11.1

Introduzione

Come tutti sanno l’informatica si evolve a ritmi vertiginosi in ogni suo cam- po. L’hardware aumenta di potenza in tempi brevissimi e nuovi linguaggi di programmazione tendono ad avanzare per soddisfare particolari richieste del- l’utenza. Accanto al fiorire di questi nuovi linguaggi si assiste alla manuten- zione ed all’aggiornamento di quelli pi´u datati ma dalle potenzialit`a e dalle prestazioni straordinarie. Il C `e fra questi.

Al termine di una revisione del linguaggio operata nel 1995 `e stato in- trapreso un lavoro di aggiornamento dello stesso che ha portato al rilascio dello standard C99. Alcune modifiche apportate al linguaggio possono essere ritenute abbastanza importanti, ma in generale si sono eseguite delle aggiunte e sono state inserite nuove funzioni di libreria. Naturalmente i programmi scritti col pi´u datato standard C89 continueranno a funzionare e comunque potranno essere aggiornate al C99 mediante delle semplici modifiche.

11.2

C89 VS C99

11.2.1

Aggiunte

Sono state aggiunte delle nuove parole riservate di cui riportiamo un elenco: 1. inline

2. restrict 3. Bool 4. Complex

5. Imaginary

Sono state inoltre aggiunte le seguenti grandezze: • Supporto per l’aritmetica dei valori complessi • Array di lunghezza variabile.

• Array flessibili come membri delle strutture. • Aggiunte al preprocessore.

• Letterali composti. • Il tipo long long int. • Il commento //.

• Dichiarazione di variabili in una istruzione for. • Possibilit`a di amalgamare codice e dati.

• Inizializzatori designati.

• Modifiche alle funzioni printf() e scanf(). • Identificatore predefinito func .

• Librerie e files header.

11.2.2

Rimozioni

Tra le funzionalit`a rimosse facciamo notare l’eliminazione dal C99 la regola dell’int implicito. Secondo questa regola se una variabile dichiarata non era preceduta dal tipo quest’ultimo era assunto come int.

11.2.3

Modifiche

Tra le modifiche apportate riportiamo le pi´u importanti: • Incremento dei limiti di traduzione.

• Tipi interi estesi.

• Regole di promozione per i tipi interi estesi. • Irrobustimento dell’uso di return

11.3 inline Imparare il C pag. 79

11.3

inline

L’utilizzo di questa parola riservata inoltra al compilatore la richiesta di ot- timizzare le chiamate alla funzione la cui dichiarazione essa precede. Sostanzial- mente il codice relativo alla funzione verr`a espanso in linea e non richiamato. Naturalmente non `e detto che un compilatore supporti questa richiesta, per questo motivo potrebbe essere ignorata. Riportiamo un piccolo esempio di funzione che utilizza questa parola riservata.

Esempio:

inline void stampa_numero(int num) { printf("Numero: %d\n")

}

Naturalmente vanno evidenziati alcuni concetti. In primo luogo, come abbiamo detto, questa funzione evita che la funzione venga richiamata sem- plicemente usando delle sue copie per ogni chiamata. Questo comporter`a un diverso codice assembler. Occorre inoltre notare che l’utilizzo di questa paro- la riservata, pur migliorando le prestazioni in termini di velocit`a, comporta un aumento delle dimensioni del codice eseguibile, essendo duplicato quel- lo delle funzioni. Consigliamo di usare questa caratteristica del C99 solo se strettamente necessario, per funzioni compatte e significative, e solamente dopo un’accurata fase di debugging.

11.4

restrict

Il qualificatore restrict riguarda solo i puntatori: ogni puntatore qualificato mediante esso risulta essere l’unico modo per accedere all’oggetto puntato. Il compilatore risulta allora in grado di ottimizzare maggiormente il codice.

11.5

il tipo Bool

Come certamente saprete il C89 non includeva parole chiave come True e False come invece poteva avvenire in altri linguaggi. Queste funzioni erano svolte rispettivamente da qualsiasi numero diverso da 0 e da 0. Utilizzando il file stdbool.h nel programma in C99 si includono delle macro in cui sono definiti true e false. Questo tipo ha assunto una sintassi (vedasi il nome) particolare perch´e molti, per ovviare alla carenza del c89 avevano gi`a creato dei propri .h per ovviare a questa mancanza.

11.6

Complex ed Imaginary

Queste parole riservate sono state introdotte al fine di per il supporto all’ar- itmetica dei numeri complessi, assieme a nuovi file header e nuove librerie. Sono stati definiti i seguenti tipi complessi:

float _Complex; float _Imaginary; double _Complex; double _Imaginary; long double _Complex; long double _Imaginary;

`

E inoltre possibile includere l’apposito complex.h dove sono anche defi- nite le macro complex ed imaginary che nella compilazione verranno espanse in Complex ed Imaginary