Corso di Fondamenti di
Programmazione
a.a.2009/2010
Prof.ssa Chiara Petrioli
Corso di Laurea in Informatica
Università degli Studi “La Sapienza”
(lezioni 16-19)
Strutture, Unioni e Liste
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Strutture
Le strutture sono collezioni di variabili correlate
sotto un unico nome
Possono contenere variabili di diversi tipi di dato
Esempio Etichetta di una struttura
Definisce un tipo di dato struttura
struct card{
struct card
costituita da due campi
char *face;
un campo face stringa che dice che carta è quella
corrente: asso, due,…,re
char *suit;
un campo suit stringa che dice il seme della
};
carta corrente (cuori,…,fiori)
Membri di una struttura
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
Il recordi di un impiegato
struct impiegato{
char *nome;
La struttura consente di raggruppare
Informazioni correlate, in questo caso
char *cognome;
Relative ad un singolo impiegato
int eta;
char sesso;
float stipendio;
};
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Dichiarazione di variabili struct
struct card a, deck[52], *cPtr;
a è una variabile di tipo struct card
viene allocata memoria per due campi puntatori
deck è un vettore di strutture. Contiene 52 elementi.
Ciascun elemento è una struttura costituita da due campi
face e suit
cPtr è un puntatore ad una struttura (contiene l’indirizzo
della locazione di memoria in cui è memorizzato un
elemento di tipo struct card)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Dichiarazione di variabili struct
struct card a, deck[52], *cPtr;
a è una variabile di tipo struct card
ALTERNATIVA
viene allocata
memoria per due campi puntatori
struct card{
*face;
deck è un vettore char
di strutture.
Contiene 52 elementi.
Ciascun elementochar
è una*suit;
struttura costituita da due campi
face e suit
}a,deck[52],*cPtr;
cPtr è un puntatore ad una struttura (contiene l’iundirizzo
della locazione di memoria in cui è memorizzato un
elemento di tipo struct card)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni su strutture
Assegnare variabili struct a variabili struct dello
stesso tipo di struttura
Determinare in che locazione di memoria è
memorizzata una struttura
Accedere ai membri di una struttura (per leggere
o scrivere il loro valore)
Con l’operatore sizeof determinare la
dimensione di una struttura (cosa che serve ad
esempio per sapere quanta memoria deve
essere allocata a ciascun elemento di quel tipo
di dato struttura)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni illecite
Due elementi di tipo struttura non possono
essere confrontati
– Ci possono essere dei bit con valore indeterminato
nelle locazioni di memoria allocate ad una struttura
– Ad esempio
Buco. In questo byte potrebbe
essere contenuto qualsiasi valore
struct example{
impossibile confrontare sample1 e
char c;
sample2 direttamente. Bisogna
int i;
confrontare i valori dei vari membri
delle due strutture.
} sample1,sample2;
Un computer con una parola di 2byte potrebbe
richiedere l’allineamento all’inizio della parola
successiva per membri successivi della struttura
01100001
00000000
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
01100001
Inizializzazione di strutture
struct card{
char *face;
char *suit;
};
struct card a={“Asso”,”Fiori”};
Se il valore di un membro non è indicato
tra le parentesi graffe è inizializzato
automaticamente a 0 (o a NULL se è di
tipo puntatore).
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Come si accede ai membri di una
struttura
Operatore membro di struttura (operatore
punto .)
– accede ad un membro della struttura
attraverso il nome della variabile di struttura
Esempio printf(“%s”, a.suit);
Stampa il campo suit della variabile a, di tipo
struct card
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Come si accede ai membri di una
struttura
Operatore puntatore a struttura ->
– accede ad un membro della struttura
attraverso un puntatore alla stessa
Esempio printf(“%s”, cPtr->suit);
Stampa il campo suit della struttura puntata da
cPtr. cPtr è un puntatore ad una struttura di
tipo struct card
Risolve il riferimento e accede al
membro suit della struttura usando
l’operatore membro di struttura
cPtr->suit equivale a (*cPtr).suit
le parentesi sono necessarie perché
l’operatore membro di struttura ha
priorità maggiore di * Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Un esempio
#include<stdio.h>
struct card{
char *face;
char *suit;
};
main()
{
struct card a;
struct card *aPtr;
a.face =“Asso”;
a.suit=“Picche”;
aPtr=&a;
printf(“%s di %s\n%s di %s\n %s di %s \n”,
a.face, a.suit, aPtr->face, aPtr->suit,
(*aPtr).face, (*aPtr).suit);
return 0;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Asso di Picche
Asso di Picche
Asso di Picche
Esempio
Il recordi di un impiegato
struct impiegato{
char *nome;
La struttura consente di raggruppare
Informazioni correlate, in questo caso
char *cognome;
Relative ad un singolo impiegato
int eta;
char sesso;
float stipendio;
};
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Usare le strutture con le funzioni
Le strutture possono essere passate alle
funzioni fornendo i singoli membri, l’intera
struttura o un puntatore ad una struttura.
Vettori di strutture sono passati per
riferimento. Per passare
una struttura per
Passati per valore
riferimento si deve passare alla funzione
l’indirizzo di memoria dove è memorizzata
la struttura.
Le funzioni possono restituire strutture
Può consentire ad una funzione di restituire
Chiara Petrioli -- Fondamenti di
più Prof.ssa
valori
programmazione, a.a. 2009/2010
Un esempio
Si scriva una funzione che dato un vettore
restituisca il più piccolo elemento del
vettore ed il più grande elemento del
vettore
Definiamo:
struct min_max{
int min;
int max;
};
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Soluzione
struct min_max minmax_v (int vett[ ], int n)
{
struct min_max temp;
La funzione minmax_v prende
if (n==1)
in input un vettore di interi vett
{
e la sua dimensione n
temp.min=vett[0];
restituisce in output una struttura
temp.max=vett[0];
di tipo min_max che contiene nei
return temp;
suoi membri il minimo ed il massimo
}
tra gli elementi del vettore
else
{
temp=minmax_v(vett,n-1);
if (vett[n-1]<temp.min)
temp.min=vett[n-1];
if (vett[n-1]>temp.max)
temp.max=vett[n-1];
return temp;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Come si può passare per valore un
vettore
Dobbiamo creare una struttura che
contenga come membro il vettore
Dato che una struttura o i membri della
struttura sono passati per valore il vettore
verrà passato nello stesso modo (basta
passare alla funzione il membro della
struttura che contiene il vettore)
– Verrà quindi fatta una copia del vettore e si
opererà su tale copia
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
typedef
La parola chiave typedef consente di creare
pseudonimi per i tipi di dato precedentemente
definiti, tipicamente per abbreviare i nomi di tali
tipi di dato
typedef struct card Card;
dice che nel seguito del programma quando si
troverà scritto Card di farà riferimento al tipo
struct card
Card deck[52];
Card NON è un nuovo tipo di dato, è un
sinonimo per struct card !
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
Mescolatore di carte (variante ad alta efficienza
di quello precedentemente visto)
Vettore di tipo Card fillDeck inizializzato in modo
da contenere le carte ordinate dall’asso al re per
ogni seme
La funzione shuffle che mescola il mazzo
riceverà come input un vettore di 52 strutture di
tipo Card, scorrerà le carte e per ogni carta
sceglierà un numero casuale tra 0 e 51 (carta
con cui la carta esaminata sarà scambiata).
Mescola effettuando scambi, non potendo
portare ad attese lunghe o indefinite per il
completamento.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Codice
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
struct card
{
char *face;
char *suit;
};
typedef struct card Card;
void fillDeck (Card *,char *[ ], char *[ ]);
void shuffle(Card *);
void deal(Card *);
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Codice
main()
Deck è un vettore
di strutture
{
Card deck[52];
char *face[ ]={“Asso”, “Due”, “Tre”, “Quattro”, “Cinque”,
“Sei”, “Sette”, “Otto”,
“Nove”, “Dieci”, “Fante”, “Donna”, “Re”};
char *suit[ ]={“Cuori”, “Quadri”, “Picche”, “Fiori”};
srand(time(NULL));
fillDeck(deck, face, suit);
shuffle(deck);
deal(deck);
return 0;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Codice
void fillDeck(Card *wDeck, char *wFace[ ], char *wSuit[ ])
{
int i;
Inizializziamo al
for (i=0;i<=51;i++)
caso in cui per
{
ciascun seme le
carte sono ordinate
wDeck[i].face=wFace[i%13];
wDeck[i].suit=wSuit[i/13];
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Codice
void shuffle(Card *wDeck)
{
int i,j;
Card temp;
for (i=0;i<=51;i++){
j=rand()%52;
temp=wDeck[i];
wDeck[i]=wDeck[j];
wDeck[j]=temp;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Codice
void deal (Card *wDeck)
{
int i;
for (i=0;i<=51;i++)
printf(“%s of %s \n, wDeck[i].face,
wDeck[i].suit);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Strutture di dati dinamiche
Abbiamo finora studiato strutture di dati con
dimensione fissa
– vettori a una o due dimensioni
– struct
Vedremo in queste lezioni un esempio di
struttura di dati dinamica (lista)
– le dimensioni della struttura crescono e decrescono
durante l’esecuzione del programma a seconda delle
esigenze (a seconda che venga aggiunto o eliminato
un elemento)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Strutture ricorsive
Una struttura ricorsiva contiene un
membro di tipo puntatore che fa
riferimento ad una struttura dello stesso
tipo di quella in cui è contenuto
Esempio
nextPtr punta a struct node
ovvero ad una struttura dello
struct node{
stesso tipo di quella che stiamo
dichiarando
int data;
 Struttura ricorsiva
struct node *nextPtr;
};
15
2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Allocazione dinamica della
memoria
Indica la capacità di un programma di
ottenere durante la sua esecuzione un
maggior spazio di esecuzione per
immagazzinare i nuovi elementi delle
strutture di dati dinamiche e la capacità di
rilasciare memoria quando elementi di tali
strutture vengono cancellati
– Funzioni
malloc
free
sizeof
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Allocazione dinamica della
memoria (malloc)
La funzione malloc prende come argomento il numero di
byte che dovranno essere allocati, alloca memoria
consecutiva per questo numero di byte e restituisce un
puntatore a void (void *) all’area di memoria allocata
(NULL se non può essere allocata memoria)
Un puntatore a void void * può essere assegnato ad una
variabile di tipo puntatore qualsiasi
Restituisce il numero
di byte necessari per
Esempio di uso:
memorizzare un elemento
newPtr=malloc(sizeof(struct node)); di tipo struct node
Alloca memoria sufficiente a contenere un nuovo
elemento di tipo struct node; restituisce l’indirizzo
dell’area di memoria allocata; tale indirizzo è
memorizzato in newPtr.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Deallocazione della memoria
Quando un elemento viene eliminato è
estremamente importante deallocare la memoria
associata all’elemento
 Renderla disponibile al sistema in modo che la
stessa/le stesse locazioni di memoria possano
essere usate nuovamente in futuro
 Nel caso di allocazione dinamica la
deallocazione deve essere fatta esplicitamente
con
free(newPtr);
tale funzione dealloca la memoria puntata da
newPtr. (per sapere quanta memoria deallocare
qui serve che newPtr sia un puntatore a un certo
tipo specifico di dato)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Liste
Una lista concatenata è una collezione di
strutture ricorsive (nodi) connesse da puntatori
(detti anche collegamenti o link).
15
2
NULL
La lista avrà un puntatore alla testa della lista
(primo elemento).
Agli altri elementi si accede per mezzo dei
puntatori che collegano un elemento al
successivo
Il puntatore dell’ultimo elemento inserito deve
essere posto a NULL in modo da consentire di
riconoscere la fine della lista.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esempio
struct node *Lista;
Lista sarà inizializzata in modo da puntare
alla testa della lista (conterrà il valore
4200, ovvero l’indirizzo della locazione di
memoria in cui è contenuto il primo
elemento)
3700
15
4200
2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Esempio
struct node *Lista;
Lista->val consentirà di accedere al valore
memorizzato nel primo elemento (15)
Lista->nextPtr conterrà l’indirizzo del
prossimo elemento della lista
3700
15
4200
2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Esempio
struct node *Lista;
Seguendo i puntatori nextPtr è possibile
accedere uno dietro l’altro ai vari elementi
della lista
Gli elemento di una lista NON sono
memorizzati consecutivamente in memoria
ma un elemento sa dove è memorizzato
l’elemento successivo
3700
15
4200
2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Esempio
struct node *Lista;
Un elemento può contenere dati di ogni tipo
(incluse altre struct)
Gli elementi vengono aggiunti e cancellati
dinamicamente.
3700
15
4200
2
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Vantaggi e svantaggi dell’uso di
liste concatenate
Pro: se non è possibile determinare a priori il
numero di elementi della collezione le liste
concatenate consentiranno di far crescere o
decrescere a seconda delle necessità la lista
– Un vettore può dover sovraallocare la memoria
portando a sprechi (la memoria allocata pone
comunque nel caso di vettori un limite alla crescita
della collezione)
– Cancellare elementi in un vettore è complesso,
richiede di spostare gli elementi successivi di una
posizione indietro. Cancellare e aggiungere elementi
è facile nelle liste concatenate
– E’ possibile inserire in modo ordinato gli elementi
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Vantaggi e svantaggi dell’uso di
liste concatenate
Con:mentre per un vettore gli elementi
sono memorizzati consecutivamente in
memoria (accedere all’elemento che
corrisponde ad un indice è una operazione
che richiede tempo costante) accedere ad
un elemento in una lista richiede di
scandire la lista fino a quell’elemento.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizi su liste
struct nodo
{
int elem;
struct nodo * next;
};
typedef struct nodo L_ELEM;
typedef struct nodo * L_PTR;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
– Verifica se la lista è vuota
– Inserimento in testa ad una lista
– Inserimento in una lista ordinata
– Cancellazione di un elemento in una lista
– Verifica se una lista è ordinata
– Stampa di una lista
– Somma degli elementi di una lista
– Numero di occorrenze di un valore in una lista
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 1
/*inserisci un nuovo elemento in testa alla lista*/
L_PTR inserisci_in_testa(L_PTR L1, int val)
{
L_PTR temp_ptr;
Si scriva una funzione
temp_ptr=malloc(sizeof(L_ELEM));
che, data una lista di
if (temp_ptr!=NULL)
Interi ed un valore
inserisca un nuovo
{
Elemento contenente
temp_ptr->elem=val;
Il valore in testa alla
temp_ptr->next=L1;
lista
L1=temp_ptr;
}
else
printf("memoria non disponibile per l'elemento della lista \n");
return L1;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
L2 (di tipo L_PTR) ha associata una locazione
di memoria che contiene l’indirizzo del primo
elemento della lista
2800
Indirizzo di memoria
In cui e’ memorizzato
Questo elemento
L2
L2->next contiene l’indirizzo di memoria del prossimo elemento della
lista (5700)
Vediamo ora cosa succede se dal main viene invocato:
L2=inserisci_in_testa(L2,v) dove v vale 5
L_PTR inserisci_in_testa(L_PTR L1, int val)
{………….
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
}
NULL
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
NULL
Vediamo ora cosa succede se dal main viene invocato:
L2=inserisci_in_testa(L2,v) dove v vale 5….
Quando viene invocata la funzione viene allocata memoria Indirizzo di memoria
In cui e’ memorizzato
per gli argomenti della funzione (L1 e val)
Questo elemento
L1
val
L_PTR inserisci_in_testa(L_PTR L1, int val)
{………….
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
Vediamo ora cosa succede se dal main viene invocato:
L2=inserisci_in_testa(L2,v) dove v vale 5….
Quando viene invocata la funzione viene allocata memoria
per gli argomenti della funzione (L1 e val).
2800
L1
5
val
In L1 viene copiato il valore di L2
In val viene copiato il valore di v
L_PTR inserisci_in_testa(L_PTR L1, int val)
{………….
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
L_PTR inserisci_in_testa(L_PTR L1, int val)
{L_PTR temp_ptr;
temp_ptr=malloc(sizeof(L_ELEM));
temp_ptr->elem=val;
temp_ptr->next=L1;
L1=temp_ptr;
return L1;
}
{
Nuovo
elemento
2800
L1
5
val
Alloca memoria
per il nuovo elemento
9100
9100
NULL
temp_ptr
temp_ptr contiene l’indirizzo della posizione di memoria allocata per
Prof.ssa Chiara Petrioli -- Fondamenti di
Il nuovo elemento
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
2800
NULL
L1
L_PTR inserisci_in_testa(L_PTR L1, int val)
val
5
{L_PTR temp_ptr;
temp_ptr=malloc(sizeof(L_ELEM));
Viene inserito il valore val nel
temp_ptr->elem=val;
campo elem del nuovo elemento
temp_ptr->next=L1;
Il campo next del nuovo elemento
L1=temp_ptr;
punta a quello che era il primo elemento
return L1;
}
della lista
{
Nuovo
elemento
5
9100
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
9100
temp_ptr
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
9100
NULL
L1
L_PTR inserisci_in_testa(L_PTR L1, int val)
{L_PTR temp_ptr;
temp_ptr=malloc(sizeof(L_ELEM));
L1 viene aggiornato con
temp_ptr->elem=val;
quello che e’ l’indirizzo
temp_ptr->next=L1;
della locazione di memoria
L1=temp_ptr;
del nuovo primo elemento della
return L1;
}
lista. Tale valore viene restituito
{
Nuovo
elemento
5
9100
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
9100
temp_ptr
5
val
Cosa succede in memoria…
3
2800
7
5
4
5700
1300
6900
9100
NULL
L1
L2=inserisci_in_testa(L2,v)}
Il valore ritornato e’ assegnato a
L2 che ora punta (correttamente)
al nuovo primo
elemento della lista
L2
{
Nuovo
elemento
5
9100
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
9100
temp_ptr
5
val
Esercizio 1-bis
(potevamo scrivere il codice come segue?)
/*inserisci un nuovo elemento in testa alla lista*/
void inserisci_in_testa(L_PTR L1, int val)
{
L_PTR temp_ptr;
Si scriva una funzione
temp_ptr=malloc(sizeof(L_ELEM));
che, data una lista di
if (temp_ptr!=NULL)
Interi ed un valore
inserisca un nuovo
{
Elemento contenente
temp_ptr->elem=val;
Il valore in testa alla
temp_ptr->next=L1;
lista
L1=temp_ptr;
}
else
printf("memoria non disponibile per l'elemento della lista \n");
Manca il
}
SBAGLIATO!!!
Capiamo il perche’
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
return L1;
in questo caso
la funzione non
restituisce
nulla
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
L2 (di tipo L_PTR) ha associata una locazione
di memoria che contiene l’indirizzo del primo
elemento della lista
2800
Indirizzo di memoria
In cui e’ memorizzato
Questo elemento
L2
L2->next contiene l’indirizzo di memoria del prossimo elemento della
lista (5700)
Vediamo ora cosa succede se dal main viene invocato:
inserisci_in_testa(L2,v) dove v vale 5
Void inserisci_in_testa(L_PTR L1, int val)
{………….
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
}
NULL
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
NULL
Vediamo ora cosa succede se dal main viene invocato:
inserisci_in_testa(L2,v) dove v vale 5….
Quando viene invocata la funzione viene allocata memoria Indirizzo di memoria
In cui e’ memorizzato
per gli argomenti della funzione (L1 e val)
Questo elemento
L1
val
void inserisci_in_testa(L_PTR L1, int val)
{………….
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
Vediamo ora cosa succede se dal main viene invocato:
inserisci_in_testa(L2,v) dove v vale 5….
Quando viene invocata la funzione viene allocata memoria
per gli argomenti della funzione (L1 e val).
2800
L1
5
val
In L1 viene copiato il valore di L2
In val viene copiato il valore di v
Void inserisci_in_testa(L_PTR L1, int val)
{………….
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
void inserisci_in_testa(L_PTR L1, int val)
{L_PTR temp_ptr;
temp_ptr=malloc(sizeof(L_ELEM));
temp_ptr->elem=val;
temp_ptr->next=L1;
L1=temp_ptr;
}
{
Nuovo
elemento
9100
NULL
2800
L1
5
val
Alloca memoria
per il nuovo elemento
9100
temp_ptr
Temp_ptr contiene l’indirizzo della posizione di memoria allocata per
Prof.ssa Chiara Petrioli -- Fondamenti di
Il nuovo elemento
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
2800
NULL
L1
L_PTR inserisci_in_testa(L_PTR L1, int val)
val
5
{L_PTR temp_ptr;
temp_ptr=malloc(sizeof(L_ELEM));
Viene inserito il valore val nel
nuovo elemento
temp_ptr->elem=val;
Il campo next del nuovo elemento
temp_ptr->next=L1;
punta a quello che era il primo elemento
L1=temp_ptr;
della lista
}
{
Nuovo
elemento
5
9100
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
9100
temp_ptr
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
9100
NULL
L1
Void inserisci_in_testa(L_PTR L1, int val)
{L_PTR temp_ptr;
temp_ptr=malloc(sizeof(L_ELEM));
L1 viene aggiornato con
quello che e’ l’indirizzo
temp_ptr->elem=val;
della locazione di memoria
temp_ptr->next=L1;
del nuovo primo elemento della
L1=temp_ptr;
lista. Si esce dalla funzione..
}
{
Nuovo
elemento
5
9100
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
9100
temp_ptr
5
val
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
9100
{
L1
2) L2 non e’ stato MAI modificato
Contiene quindi l’indirizzo di
memoria di quello che era prima
della chiamata a funzione il
primo elemento della lista non
c’e’ modo di accedere al nuovo
elemento
ERRORE!!!
1) La memoria per L1, temp_ptr
e val viene deallocata all’uscita
dalla funzione
Nuovo
elemento
NULL
5
9100
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
9100
temp_ptr
5
val
Allocazione dinamica dei vettori
• Cosa succede, se non si sa a priori (quando
scriviamo il programma) quanti elementi di un
array ci serviranno a tempo di esecuzione?
• La soluzione che abbiamo visto finora
prevede di sovraallocare memoria per il
vettore
• non è detto che risponda alle esigenze a
run time
• spreco di risorse
• Altra soluzione: allocazione dinamica di array.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Allocazione dinamica di vettori
(void*) calloc(unsigned int n, unsigned int size);
calloc = contiguous allocation
Alloca memoria per n elementi contigui ciascuno di
dimensione pari a size.
Restituisce un puntatore all’area di memoria allocata.
Per il resto, funziona come malloc
int* p;
p = calloc(5000,sizeof(int) );
Alloca un vettore di
5000 interi.
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Allocazione di vettori
Quale la differenza
int* v =
calloc(5000,sizeof(int) );
A) fixed size vector:
int v[5000];
• In entrambi i casi:
• ho un vettore di 5000 interi
• posso scrivere ad esempio:
v[2]= v[1]++;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Allocazione di vettori
• Differenza 1: dimensione variabile
• se x è una variabile intera, posso scrivere:
int* v = calloc(x,sizeof(int) );
• ma non posso scrivere:
int v[x];
la dimensione di un array statico è
una costante
La memoria allocata deve poi essere esplicitamente deallocata con una free
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Differenza tra malloc e calloc
(potremmo usare anche la malloc? si)
Calloc prende due input e quindi alloca memoria per n
elementi di una certa dimensione
Quando invocata la calloc inizializza a zero la memoria
allocata, di cui restituisce il puntatore
Setta a zero e restituisce
– Calloc(m, n) corrisponde a
p
p = malloc(m * n); memset(p, 0, m * n);
Riallocazione della memoria con
– void *realloc(void *ptr, size_t size);
Cambia la dimensione dell’oggetto di memoria puntato da ptr che ora
avrà allocata memoria pari a size. Se la nuova dimensione richiede di
spostare l’oggetto la memoria precedentemente allocata è liberata.
Dopo l’allocazione la prima parte dell’oggetto di memoria (i primi size
elementi se size < della precedente dimensione n, o i primi n elementi
altrimenti) mantengono lo stesso valore che avevano prima
dell’invocazione della realloc
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 1
/*inserisci un nuovo elemento in testa alla lista*/
L_PTR inserisci_in_testa(L_PTR L1, int val)
{
L_PTR temp_ptr;
Si scriva una funzione
temp_ptr=malloc(sizeof(L_ELEM));
che, data una lista di
if (temp_ptr!=NULL)
Interi ed un valore
inserisca un nuovo
{
Elemento contenente
temp_ptr->elem=val;
Il valore in testa alla
temp_ptr->next=L1;
lista
L1=temp_ptr;
}
else
printf("memoria non disponibile per l'elemento della lista \n");
return L1;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio 2
/*inserisci un nuovo elemento in testa alla lista */
void inserisci_in_testa2 (L_PTR * LISTAPTR, int val)
{
L_PTR temp_ptr;
Si scriva una funzione
temp_ptr=malloc(sizeof(L_ELEM));
che, data una lista di
if (temp_ptr !=NULL)
Interi ed un valore
inserisca un nuovo
{
Elemento contenente
temp_ptr->elem=val;
Il valore in testa alla
temp_ptr->next=*LISTAPTR;
lista
*LISTAPTR=temp_ptr;
}
else
printf("memoria non disponibile per l'elemento della lista \n");
}
LISTA_PTR e’ un puntatore a puntatore
Ovvero una variabile che contiene l’indirizzo di memoria di una variabile
di tipo puntatore (che a sua volta contiene l’indirizzo di memoria di un
Prof.ssa Chiara Petrioli -- Fondamenti di
Elemento della lista)
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
3
2800
7
5
4
5700
1300
6900
L2 (di tipo L_PTR) ha associata una locazione
di memoria che contiene l’indirizzo del primo
elemento della lista
2800
L2
Vediamo ora cosa succede se dal main viene invocato:
inserisci_in_testa(&L2,v) dove v vale 5
void inserisci_in_testa(L_PTR *LISTAPTR, int val)
{………….
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Cosa succede in memoria…
L2
2800
7500
3
2800
7
5
4
5700
1300
6900
Vediamo ora cosa succede se dal main viene invocato:
inserisci_in_testa(&L2,v) dove v vale 5….
Quando viene invocata la funzione viene allocata memoria
per gli argomento della funzione (LISTAPTR e val). LISTAPTR e’ un puntatore a
puntatore ovvero contiene l’indirizzo della locazione di memoria associata
ad una variabile di tipo puntatore. In LISTAPTR viene copiato l’indirizzo di L2
(dato che la funzione e’ invocata con argomento &L2)
7500
5
LISTAPTR
val
void inserisci_in_testa(L_PTR* LISTAPTR, int val)
{………….
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
NULL
Cosa succede in memoria…
L2
2800
3
2800
7500
7
5
4
NULL
5700
1300
6900
Vediamo ora cosa succede se dal main viene invocato:
inserisci_in_testa(&L2,v) dove v vale 5….
temp_ptr=malloc(sizeof(L_ELEM));
if (temp_ptr !=NULL)
{
temp_ptr->elem=val;
temp_ptr->next=*LISTAPTR;
*LISTAPTR=temp_ptr;
}
Viene allocata memoria
per un nuovo elemento
temp_ptr punta a tale
locazione di memoria
Nel campo elem di tale
locazione viene memorizzato
il valore di val
3500
LISTAPTR
7500
5
val
5
temp_ptr
Void inserisci_in_testa(L_PTR* LISTAPTR, int val)
{………….
Prof.ssa Chiara Petrioli -- Fondamenti di
}
programmazione, a.a. 2009/2010
Cosa succede in memoria…
L2
2800
3
2800
7500
7
5
4
5700
1300
6900
temp_ptr=malloc(sizeof(L_ELEM));
if (temp_ptr !=NULL)
{
temp_ptr->elem=val;
temp_ptr->next=*LISTAPTR;
*LISTAPTR=temp_ptr;
}
NULL
LISTAPTR
7500
5
3500
5
val
2800
temp_ptr
Al campo next del nuovo elemento viene assegnato *LISTAPTR (ovvero il contenuto
della locazione di memoria il cui indirizzo e’ in LISTAPTR  ovvero l’indirizzo del
Chiara Petrioli -- Fondamenti di
primo elemento della lista) Prof.ssa
programmazione, a.a. 2009/2010
Cosa succede in memoria…
3
2800
7
5
4
NULL
5700
1300
6900
LISTAPTR
temp_ptr=malloc(sizeof(L_ELEM));
if (temp_ptr !=NULL)
{
temp_ptr->elem=val;
temp_ptr->next=*LISTAPTR;
*LISTAPTR=temp_ptr;
}
7500
5
3500
5
val
2800
temp_ptr
L2
3500
7500
*LISTAPTR e’ il contenuto della locazione di memoria il cui indirizzo
è memorizzato in LISTAPTR, ovvero il valore di L2.
Con l’istruzione *LISTAPTR=temp_ptr viene modificato L2 che viene fatto puntare
al nuovo primo elemento. All’uscita dalla funzione L2 puntera’ quindi correttamente
Prof.ssa Chiara Petrioli -- Fondamenti di
al nuovo primo elemento della
lista.
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
– Verifica se la lista è vuota
– Inserimento in testa ad una lista OK
– Inserimento in una lista ordinata
– Cancellazione di un elemento in una lista
– Verifica se una lista è ordinata
– Stampa di una lista
– Somma degli elementi di una lista
– Numero di occorrenze di un valore in una lista
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio –stampa di una lista
/*stampa ricorsiva di una lista*/
void stampalista (L_PTR L1)
{
if (L1!=NULL)
L
{
printf("--> %d ",L1->elem);
stampalista(L1->next);
}
else 3
7
printf("-->NULL \n");
5700
} 2800
Si scriva una procedura
che data una lista
Ne stampi gli elementi
®
5
4
1300
6900
NULL
/*stampa di una lista (versione iterativa)*/
void stampalista_iter (L_PTR L1)
{
Si scriva una procedura
while (L1 !=NULL)
che data una lista
{
Ne stampi gli elementi
printf("--> %d", L1->elem);
(iterativa)
L1=L1->next;
3754NULL
}
printf("-->NULL \n");
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
– Verifica se la lista è vuota
– Inserimento in testa ad una lista OK
– Inserimento in una lista ordinata
– Cancellazione di un elemento in una lista
– Verifica se una lista è ordinata
– Stampa di una lista OK
– Somma degli elementi di una lista
– Numero di occorrenze di un valore in una lista
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio -somma degli
elementi di una lista
La somma degli elemento di una lista è data dall’elemento corrente
/*calcolapiù
la somma
deglidegli
elementi
una listadella
*/
la somma
altridielementi
lista
intLsum_elementi(L_PTR
L1)
OVVERO dall’elemento corrente + il risultato della chiamata ricorsiva
{
Si scriva una funzione
sul resto della lista
int sum=0;
Che dato una lista
while (L1 != NULL)
Calcoli la somma dei
{ 3
5
4
NULL
7
Suoi
elementi
sum+=L1->elem;
(iterativa)
L1=L1->next;
2800
5700
1300
6900
}
return sum;
}
19
/*versione ricorsiva*/
int sum_elementi(L_PTR L1)
Si scriva una funzione
{
Che dato una lista
if (L1!=NULL)
Calcoli la somma dei
return ((L1->elem)+(sum_elementi(L1->next)));
Suoi elementi
else
®
return 0;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
– Verifica se la lista è vuota
– Inserimento in testa ad una lista OK
– Inserimento in una lista ordinata
– Cancellazione di un elemento in una lista
– Verifica se una lista è ordinata
– Stampa di una lista OK
– Somma degli elementi di una lista OK
– Numero di occorrenze di un valore in una lista
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio
Il numero di occorrenze di val in una lista è dato da 1+ il numero
/*calcola il di
numero
di occorrenze
un dato
valore
in una
occorrenze
nel di
resto
della
lista
SElista*/
l’elemento corrente
int num_occorrenze(L_PTR L1, int val)
contiene il valore val
{
Si scriva una funzione che
Dal
numero
di
occorrenze
nel
resto
della
lista se l’elemento
int occorrenze
=
0;
L
Data una lista ed un valore
while (L1 !=NULL)
corrente NON contiene il valore val
Calcoli il numero di
{
if (L1->elem == val)
Occorrenze del valore
occorrenze++;
Nella lista
3
5
4
NULL
L1=L1->next;
7
(iterativa)
}
return
2800(occorrenze);
5700
1300
6900
}
val=7
Si scriva una funzione
che
Data
una lista ed un valore
1
/*versione ricorsiva*/
Calcoli il numero di
int num_occorrenze (L_PTR L1, int val)
Occorrenze del valore
{
Nella lista
if (L1 == NULL)
return 0;
®
else
return ((L1->elem == val)? (1+num_occorrenze(L1->next,val)):(num_occorrenze(L1->next,val)));
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
–
–
–
–
–
–
–
–
–
Verifica se la lista è vuota
Inserimento in testa ad una lista OK
Inserimento in una lista ordinata
Cancellazione di un elemento in una lista
Verifica se una lista è ordinata
Stampa di una lista OK
Somma degli elementi di una lista OK
Numero di occorrenze di un valore in una lista OK
Verifica se un elemento compare nella lista
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio
int verifica_presenza (L_PTR L1, int val)
{
if (L1 == NULL)
return 0;
else
return ((L1->elem==val)||
verifica_presenza(L1->next,val));
}
val compare in una lista se O l’elemento corrente è pari a val
OPPURE val occorre
nel resto
lista
Si scriva
unadella
funzione
Se la lista è vuota NON
ha elementi
quindi
Che data
una lista
ed qualsiasi elemento
non compare nella lista
Un valore verifichi
Se il valore compare tra
3
5 lista
4
NULL
7 Gli elementi della
val=6
2800
5700
1300
6900
Prof.ssa Chiara Petrioli -- Fondamenti
0 di
L
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo el seguenti operazioni
–
–
–
–
–
–
–
–
–
Verifica se la lista è vuota
Inserimento in testa ad una lista OK
Inserimento in una lista ordinata
Cancellazione di un elemento in una lista
Verifica se una lista è ordinata
Stampa di una lista OK
Somma degli elementi di una lista OK
Numero di occorrenze di un valore in una lista OK
Verifica se un elemento compare nella lista OK
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio
Verifica che la lista
int verifica_ordinata (L_PTR L1)
{
sia ordinata in ordine
L_PTR tempPtr;
crescente
if ((L1 == NULL) || (L1->next == NULL))
return 1;
else
{
tempPtr=L1;
while (tempPtr->next !=NULL)
{
due elementi consecutivi
if (tempPtr->elem> tempPtr->next->elem) non rispettano l’ordinamento
return 0;
else
tempPtr=tempPtr->next;
}
return 1;
}
}
Abbiamo considerato tutti gli elementi
e sono ordinati in ordine crescente
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio (versione avanzata)
/*verifica se la lista e' ordinata- E' ordinata se e' ordinata in ordine
crescente o decrescente.
Nel primo caso ord varra' 1 altrimenti 2. Alla prima chiamata ord sara'
inizializzato a 0*/
int verifica_se_ordinata (L_PTR L1, int ord)
{
Si scriva una funzione
if ((L1 == NULL) || (L1->next == NULL)) return 1;
che, data una lista verifichi
switch (ord)
se e’ ordinata (in ordine
{
crescente O decrescente)
case 0: if (L1->elem == L1->next->elem)
®
return (verifica_se_ordinata(L1->next,0));
else if (L1->elem < L1->next->elem)
return (verifica_se_ordinata (L1->next, 1));
else return (verifica_se_ordinata(L1->next, 2));
break;
case 1: return ((L1->elem <=L1->next->elem) && (verifica_se_ordinata (L1>next, 1)));
break;
case 2:return ((L1->elem >= L1->next->elem) && (verifica_se_ordinata (L1>next, 2)));
break;
Prof.ssa Chiara Petrioli -- Fondamenti di
default: break;
programmazione, a.a. 2009/2010
}
Operazioni sulle liste
Vedremo le seguenti operazioni
–
–
–
–
–
–
–
–
–
Verifica se la lista è vuota
Inserimento in testa ad una lista OK
Inserimento in una lista ordinata
Cancellazione di un elemento in una lista
Verifica se una lista è ordinata OK
Stampa di una lista OK
Somma degli elementi di una lista OK
Numero di occorrenze di un valore in una lista OK
Verifica se un elemento compare nella lista OK
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Verifica se la lista è vuota
int isempty (L_PTR L1)
{
return (L1==NULL);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
–
–
–
–
–
–
–
–
–
Verifica se la lista è vuota OK
Inserimento in testa ad una lista OK
Inserimento in una lista ordinata
Cancellazione di un elemento in una lista
Verifica se una lista è ordinata OK
Stampa di una lista OK
Somma degli elementi di una lista OK
Numero di occorrenze di un valore in una lista OK
Verifica se un elemento compare nella lista OK
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
Alloco memoria per il nuovo
elemento.
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
}
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
tempPtr
val
NULL
curr
prev
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
tempPtr
prev=NULL;
curr=L;
val
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
NULL
curr
prev
NULL
}
L
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
3
2800
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
8
NULL
while ((curr!=NULL) && (val >curr->elem)){
prev=curr;
curr=curr->next;
curr
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
prev
NULL
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
se val=8
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
8
NULL
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
se val=8
curr
prev
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
Si sfrutta il fatto8che si valuta la condizione
NULL
da sinistra a destra !!
se val=8
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
curr
prev
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
tempPtr
8
NULL
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
tempPtr
8
NULL
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
tempPtr
8
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
Esco dalla funzione. Dealloco
memoria per le var locali alla
funzione
tempPtr
8
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
Restituisco il valore di L che punta
correttamente alla testa della nuova
lista
8
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Ancora su inserimento ordinato
Cosa sarebbe successo nel caso in cui
val=2?
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
Alloco memoria per il nuovo
elemento.
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->elem)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
}
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
tempPtr
2
NULL
curr
prev
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
tempPtr
prev=NULL;
curr=L;
2
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
NULL
curr
prev
NULL
}
L
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
3
2800
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
2
NULL
while ((curr!=NULL) && (val >curr->elem)){
prev=curr;
curr=curr->next;
curr
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
prev
NULL
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
se val=2
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
tempPtr
2
se val=2
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
curr
prev
NULL
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
}L
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
3
2800
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
tempPtr
2
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
Si rilascia
la memoria
Allocata
per tempPtr
curr,
curr
prev
prev
NULL
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
}L
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
3
2800
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
Nel main
L=inserimento_ordinato(L,2);
L
2
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
Il valore restituito dalla funzione è
quello che era contenuto in tempPtr
ovvero l’indirizzo del nuovo primo
elemento della lista
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
}
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
3
2800
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Altro caso…
Cosa succederebbe nel caso in cui
val=12? (inserimento in fondo alla lista)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
Alloco memoria per il nuovo
elemento.
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
}
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
tempPtr
val
NULL
curr
prev
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
tempPtr
prev=NULL;
curr=L;
val
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
NULL
curr
prev
NULL
}
L
else{
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
}
}
3
2800
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
12
NULL
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
se val=12
curr
prev
NULL
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
12
NULL
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
se val=12
curr
prev
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
12
NULL
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
se val=12
curr
prev
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
12
NULL
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
se val=12
curr
prev
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
tempPtr
12
NULL
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next; NULL
}
L
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
}
se val=12
curr
prev
}
else{
3
}
2800
}
printf(“impossibiel inserire nuovo elemento 1n”);
9
return L;
4
5700
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
tempPtr
12
NULL
NULL
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
NULL
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
tempPtr
12
NULL
NULL
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
tempPtr
12
NULL
NULL
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
Esco dalla funzione. Dealloco
memoria per le var locali alla
funzione
tempPtr
NULL
12
NULL
curr
else{
prev
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
Inserimento in una lista ordinata
L_PTR inserimento_ordinato (L_PTR L, int val)
{
L_PTR tempPtr, prev, curr;
tempPtr=malloc(sizeof(struct nodo));
if (tempPtr!=NULL) {
tempPtr->elem=val;
tempPtr->next=NULL;
prev=NULL;
curr=L;
while ((curr!=NULL) && (val >curr->val)){
prev=curr;
curr=curr->next;
}
if (prev==NULL){
tempPtr->next=L;
return tempPtr;
}
Restituisco il valore di L che punta
correttamente alla testa della nuova
lista
NULL
12
else{
prev->next=tempPtr;
tempPtr->next=curr;
return L;
L
}
}
else{
}
}
3
2800
printf(“impossibiel inserire nuovo elemento 1n”);
return L;
4
5700
9
1300
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
Altri esercizi
Inserimento in coda alla lista (varie
versioni)
Cancellazione di un elemento (ricorsiva e
cancellazione di tutte le occorrenze)
Data una lista la si inverta
Data una lista si elimini un elemento ogni
val
Data una lista si eliminino i valori pari
contenuti nella lista
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio
/*prende un elemento e lo inserisce in coda alla lista*/
L_PTR inserisci_in_coda (L_PTR L1, int val)
{
L_PTR tempptr1, tempptr2;
tempptr2=malloc(sizeof(L_ELEM));
tempptr2->elem = val;
tempptr2->next=NULL;
if (L1 == NULL)
Si scriva una funzione
return tempptr2;
iterativa
else
Che inserisca un elemento
{
In coda alla lista
tempptr1=L1;
while (tempptr1->next !=NULL)
tempptr1=tempptr1->next;
tempptr1->next=tempptr2;
return L1;
}
Prof.ssa Chiara Petrioli -- Fondamenti di
}
programmazione, a.a. 2009/2010
Esercizio -bis
void insertTAILlista(LISTA *L1,int val)
{
LISTA temp,temp1;
if (*L1==NULL)
Si scriva una funzione
{
iterativa
temp=malloc(sizeof(NODOLISTA));
Che inserisca un elemento
temp->elem=val;
In coda alla lista
temp->next=NULL;
*L1=temp;
}
else
{
struct node {
temp1=*L1;
int elem;
while (temp1->next!=NULL)
struct node *next;
temp1=temp1->next;
};
temp=malloc(sizeof(NODOLISTA));
typedef struct node NODOLISTA;
temp->elem=val;
typedef NODOLISTA *LISTA;
temp->next=NULL;
temp1->next=temp;
Prof.ssa Chiara Petrioli -- Fondamenti di
}
programmazione, a.a. 2009/2010
}
Perché non andrebbe bene…
void insertTAILlista(LISTA L1,int val)
{
LISTA temp,temp1;
if (L1==NULL)
Si scriva una funzione
{
iterativa
temp=malloc(sizeof(NODOLISTA));
Che inserisca un elemento
temp->elem=val;
In coda alla lista
temp->next=NULL;
L1=temp;
All’uscita dalla funzione
}
Non rimarrebbe traccia delle
else
Modifiche fatte alla testa
{
struct node {
Della lista
temp1=L1;
int elem;
while (temp1->next!=NULL)
struct node *next;
temp1=temp1->next;
};
temp=malloc(sizeof(NODOLISTA));
typedef struct node NODOLISTA;
temp->elem=val;
typedef NODOLISTA *LISTA;
temp->next=NULL;
temp1->next=temp;
Prof.ssa Chiara Petrioli -- Fondamenti di
}
programmazione, a.a. 2009/2010
}
Esercizio -bis
void insertTAILlista(LISTA *L1,int val)
{
LISTA temp,temp1;
if (*L1==NULL)
Si scriva una funzione
{
iterativa
temp=malloc(sizeof(NODOLISTA));
Che inserisca un elemento
temp->elem=val;
In coda alla lista
temp->next=NULL;
*L1=temp;
}
else
{
struct node {
temp1=*L1;
int elem;
while (temp1->next!=NULL)
struct node *next;
temp1=temp1->next;
};
temp=malloc(sizeof(NODOLISTA));
typedef struct node NODOLISTA;
temp->elem=val;
typedef NODOLISTA *LISTA;
temp->next=NULL;
temp1->next=temp;
Prof.ssa Chiara Petrioli -- Fondamenti di
}
programmazione, a.a. 2009/2010
}
Esercizio -bis
(versione ricorsiva)
void RinsertTAILlista(LISTA *L1,int val)
{
Si scriva una funzione
LISTA temp;
Che inserisca un elemento
if (*L1==NULL)
in coda alla lista
®
{
struct node {
temp=malloc(sizeof(NODOLISTA));
int elem;
struct node *next;
temp->next=NULL;
};
temp->elem=val;
typedef struct node NODOLISTA;
*L1=temp;
typedef NODOLISTA *LISTA;
}
else RinsertTAILlista (&((*L1)->next),val);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Operazioni sulle liste
Vedremo le seguenti operazioni
–
–
–
–
–
–
–
–
–
Verifica se la lista è vuota OK
Inserimento in testa ad una lista OK
Inserimento in una lista ordinata OK
Cancellazione di un elemento in una lista
Verifica se una lista è ordinata OK
Stampa di una lista OK
Somma degli elementi di una lista OK
Numero di occorrenze di un valore in una lista OK
Verifica se un elemento compare nella lista OK
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
Cancella solo la prima occorrenza
if (val==L->elem){
di val nella lista
tempPtr=L;
L=L->next;
free(tempPtr);
Per esercizio cercate di generalizzare
return L;
facendo cancellare TUTTE le
}
else{
occorrenze di val nella lista
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
L
}
return L;
}
}
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
Supponiamo di voler cancellare la prima
occorrenza del valore 3 nella lista
tempPtr
else{
L
}
}
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
curr
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
Supponiamo di voler cancellare la prima
occorrenza del valore 3 nella lista
tempPtr
else{
L
}
}
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
curr
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
Supponiamo di voler cancellare la prima
occorrenza del valore 3 nella lista
tempPtr
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
Lreturn L;
}
return L;
}
}
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
curr
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
Supponiamo di voler cancellare la prima
occorrenza del valore 3 nella lista
tempPtr
La memoria che era stata allocata per il
primo elemento che conteneva il valore
cancellato è deallocata
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
Lreturn L;
}
return L;
}
}
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
curr
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
Supponiamo di voler cancellare la prima
occorrenza del valore 3 nella lista
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
Viene restituito al chiamante L che punta
return L;
Alla nuova testa della lista
}
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
Lreturn L;
}
return L;
}
}
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
Cosa succederebbe
Se il valore da cancellare fosse 9..
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
Supponiamo di voler cancellare la prima
occorrenza del valore 9 nella lista
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
tempPtr
prev=L;
curr=L->next;
L
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
curr
prev
}
}
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
Supponiamo di voler cancellare la prima
occorrenza del valore 9 nella lista
tempPtr
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
L
}
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
curr
prev
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
Supponiamo di voler cancellare la prima
occorrenza del valore 9 nella lista
tempPtr
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
L
}
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
curr
prev
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
Supponiamo di voler cancellare la prima
occorrenza del valore 9 nella lista
tempPtr
curr
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
L
}
return L;
3
}
}
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
Supponiamo di voler cancellare la prima
occorrenza del valore 9 nella lista
tempPtr
curr
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
L
}
return L;
3
}
}
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
Supponiamo di voler cancellare la prima
occorrenza del valore 9 nella lista
tempPtr
curr
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
L
}
return L;
3
}
}
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
prev
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
Restituiamo L che è il puntatore alla
testa della lista modificata
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
L
}
return L;
3
}
}
2800
4
5700Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
10
6900
Ulteriore caso…
Cosa succederebbe se volessimo
cancellare 5 (5 non compare tra gli
elementi della lista…)
Fate da soli il caso in cui si cancella
l’ultimo elemento della lista…
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
Supponiamo di voler cancellare la prima
occorrenza del valore 5 nella lista
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
tempPtr
prev=L;
curr=L->next;
L
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
curr
prev
}
}
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
Supponiamo di voler cancellare la prima
occorrenza del valore 5 nella lista
tempPtr
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
L
}
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
curr
prev
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
Supponiamo di voler cancellare la prima
occorrenza del valore 5 nella lista
tempPtr
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
L
}
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
curr
prev
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
Supponiamo di voler cancellare la prima
occorrenza del valore 5 nella lista
tempPtr
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
curr=curr->next;
}
L
}
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
curr
prev
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
L_PTR cancella(L_PTR L, int val)
{
L_PTR prev,curr,tempPtr;
if (val==L->elem){
tempPtr=L;
L=L->next;
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
Supponiamo di voler cancellare la prima
occorrenza del valore 5 nella lista
tempPtr
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
NULL
curr=curr->next;
}
L
}
}
if (curr !=NULL){
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
}
return L;
3
2800
9
4
-- Fondamenti di
5700Prof.ssa Chiara Petrioli
1300
programmazione, a.a. 2009/2010
10
6900
curr
prev
Cancellazione di un elemento dalla lista
/*pre: la lista non è vuota*/
Supponiamo di voler cancellare la prima
L_PTR cancella(L_PTR L, int val)
occorrenza del valore 5 nella lista
{
L_PTR prev,curr,tempPtr;
In questo caso la lista non va modificata
if (val==L->elem){
tempPtr=L;
L=L->next;
tempPtr
free(tempPtr);
return L;
}
else{
prev=L;
curr=L->next;
while ((curr!=NULL) && (curr->elem !=val)){
prev=curr;
NULL
curr
curr=curr->next;
}
if (curr !=NULL){
prev
tempPtr=curr;
prev->next=curr->next;
free(tempPtr);
return L;
L }
return L;
3
}
}
2800
9
4 Prof.ssa Chiara Petrioli
-- Fondamenti di
a.a. 2009/2010
5700 programmazione,
1300
10
6900
Altri esercizi
Cancellazione di tutte le occorrenze di un
dato valore da una lista (ricorsiva)
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio
void RdeleteELEMlista(L_PTR * L, int val)
{
L_PTR temp;
if (*L==NULL) return;
else if (((*L)->elem)==val)
{
temp=*L;
*L=(*L)->next;
free(temp);
RdeleteELEMlista(L,val);
}
else RdeleteELEMlista (&((*L)->next),val);
}
Si scriva una funzione
Ricorsiva
che, data una lista elimini
Le occorrenze di
val nella lista
struct node {
int elem;
struct node *next;
};
typedef struct node NODOLISTA;
typedef NODOLISTA *LISTA;
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Altri esercizi
Data una lista la si inverta
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Esercizio (inversione lista)
L_PTR Rinvertilista(L_PTR L)
{
L_PTR temp;
if ((L==NULL) ||(L->next == NULL))
return L;
else
{
temp=Rinvertilista(L->next);
L->next->next=L;
L->next=NULL;
return temp;
}
}
Si scriva una funzione
che, data una lista
La inverta
®
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Unione,intersezione e differenza di
insiemi (rappresentati tramite liste)
Unione di due insiemi
Intersezione di due insiemi
Differenza di due insiemi
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Unione di due insiemi
void mergeliste (LISTA *PTRLISTA, LISTA L1, LISTA L2)
{
LISTA curr;
(*PTRLISTA)=NULL;
curr = L1;
while (curr!=NULL)
{
insertHEADlista(PTRLISTA,curr->elem);
curr = curr->next;
}
curr = L2;
while (curr!=NULL)
{
if (!(Rfindlista(*PTRLISTA,curr->elem)))
insertHEADlista(PTRLISTA,curr->elem);
curr = curr->next;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Intersezione di due insiemi
void intersezioneliste (LISTA *PTRLISTA, LISTA L1, LISTA L2)
{
LISTA curr;
(*PTRLISTA)=NULL;
curr = L1;
while (curr!=NULL)
{
if ((Rfindlista(L2,curr->elem)) &&
(!(Rfindlista(*PTRLISTA,curr->elem))))
insertHEADlista(PTRLISTA,curr->elem);
curr = curr->next;
}
}
La parte in verde solo se
L1 e L2 non sono insiemi
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Differenza di due insiemi
void diffliste (LISTA *PTRLISTA, LISTA L1, LISTA L2)
{
LISTA curr;
(*PTRLISTA)=NULL;
curr = L1;
while (curr!=NULL)
{
if ((!(Rfindlista(L2,curr->elem))) &&
(!Rfindlista(*PTRLISTA,curr->elem)))
insertHEADlista(PTRLISTA,curr->elem);
curr = curr->next;
}
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010
Rappresentazione di una pila tramite lista
void push (PILA *PTRPILA, int val)
{
PILA temp;
temp=malloc(sizeof(NODOPILA));
if (temp==NULL)
printf("memoria non disponibile \n");
else
{
temp->elem=val;
temp->next = *PTRPILA;
*PTRPILA = temp;
}
}
/*Post: restituisce un puntatore a quello che era l'elemento in testa della
pila, ora cancellato. Se la pila e' vuota restituisce NULL */
PILA pop (PILA *PTRPILA)
{
PILA temp;
if ((*PTRPILA)!=NULL)
{
temp = *PTRPILA;
*PTRPILA = (*PTRPILA)->next;
return temp;
}
else
Prof.ssa Chiara Petrioli -- Fondamenti di
return NULL;
programmazione, a.a. 2009/2010
}
Verifica della parentesizzazione
int verifparentesi()
{
PILA L=NULL;
PILA t;
int c;
while ((c=getchar())!='\n')
{
switch(c)
{
case '(':push(&L,c);
break;
case ')':t=pop(&L);
if (t==NULL) return 0;
free(t);
break;
default:break;
}
}
return (L==NULL);
}
Prof.ssa Chiara Petrioli -- Fondamenti di
programmazione, a.a. 2009/2010