Corso di Programmazione 1
a.a.2007/2008
Prof.ssa Chiara Petrioli
Corso di Laurea in Informatica
Università degli Studi “La Sapienza”
(esercizi di preparazione al secondo
esonero)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 1
Data una lista L di interi e dato un intervallo [i,j] si
scriva una funzione che verifichi se esistono in L
valori interi nell’intervallo specificato
 La funzione dovrà prendere in input
 una lista L
 due valori interi (i,j)
 Dovrà restituire in output
0 se nessuno degli elementi di L ha valori nell’intervallo [i,j]
1 altrimenti
Diamo la soluzione ricorsiva
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 1-soluzione ricorsiva
int Rfindintervallista (LISTA L, int i, int j)
{
if (L==NULL)
return 0;
else if ((L->elem>=i)&&(L->elem<=j))
return 1;
else
return (Rfindintervallista(L->next,i,j));
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 2
Data una lista L di interi e dato un intervallo [i,j] si
scriva una funzione che calcoli il numero di elementi
di L che abbiano un valore intero nell’intervallo
specificato
 La funzione dovrà prendere in input
 una lista L
 due valori interi (i,j)
 Dovrà restituire in output
Il numero di elementi di L che ha un valore in [i,j]
Diamo la soluzione ricorsiva e la soluzione iterativa
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 2-soluzione ricorsiva
int Rnum_occintervallista (LISTA L,int i, int j)
{
if (L==NULL)
return 0;
else if ((L->elem>=i)&&(L->elem<=j))
return (1+Rnum_occintervallista(L->next,i,j));
else
return (Rnum_occintervallista(L->next,i,j));
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 2-soluzione iterativa
int num_occintervallista (LISTA L,int i, int j)
{
int count=0;
while (L!=NULL)
{
if ((L->elem>=i)&&(L->elem<=j))
count++;
L=L->next;
}
return count;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 3
Si scriva una funzione ricorsiva che data
una lista L elimini un elemento, ne lasci
val, elimini di nuovo un elemento, ne lasci
val etc.
Cosa intendiamo?
– se val=3 vogliamo eliminare:
il primo elemento
il quarto elemento (lasciamo tre elementi)
L’ottavo elemento etc.
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 3 –versione ricorsiva
LISTA eliminaognik (LISTA l1, int k, int val)
{
Si scriva una funzione
LISTA temp;
Ricorsiva
if (l1==NULL) return l1;
che, data una lista elimini
else if (k==0)
Un elemento ogni
{
val
La funzione è chiamata
temp=l1;
Dal main con k==0
l1=l1->next;
free (temp);
return eliminaognik(l1,val,val);
}
struct node {
else
int elem;
{
struct node *next;
l1->next=eliminaognik(l1->next,k-1,val);
};
return l1;
typedef struct node NODOLISTA;
}
typedef NODOLISTA *LISTA;
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 3-variante
void eliminaognikpuntpunt (LISTA *l1, int k, int val)
{
Si scriva una funzione
LISTA temp;
Ricorsiva
if (*l1==NULL) return;
che, data una lista elimini
else if (k==0)
Un elemento ogni
{
val
temp=*l1;
*l1=(*l1)->next;
struct node {
int elem;
free (temp);
struct node *next;
eliminaognikpuntpunt(l1,val,val);
};
return;
typedef struct node NODOLISTA;
}
typedef NODOLISTA *LISTA;
else
{
eliminaognikpuntpunt(&((*l1)->next),k-1,val);
return;
}
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 4
Data una lista si scriva una funzione che
elimini gli elementi con valori pari della
lista (si fornisca una versione ricorsiva)
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 4
void eliminapari(LISTA *l1)
{
LISTA temp;
if (*l1==NULL) return;
else if ((*l1)->elem %2)
{
eliminapari(&(*l1)->next);
Si scriva una funzione
return;
Ricorsiva
}
che, data una lista elimini
else
Gli elementi contenenti
{
Valori pari
temp=*l1;
*l1=(*l1)->next;
free(temp);
eliminapari(l1);
return;
}
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 5
Si scriva una funzione che date due liste
costruisca una terza lista data dall’unione
delle prime due
Potete utilizzare all’interno del codice
funzioni che abbiamo precedentemente
definito
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 5
void mergeliste (LISTA *PTRLISTA, LISTA L1, LISTA L2)
{
LISTA curr, temp;
temp=NULL;
PTRLISTA=&temp;
curr = L1;
while (curr!=NULL)
{
if (!(Rfindlista(*PTRLISTA,curr->elem)))
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 -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 6
Si scriva una funzione che date due liste
costruisca (e restituisca il puntatore alla
testa di) una terza lista i cui elementi
contengono tutti e soli i valori che sono
presenti in entrambe le prime liste (ogni
valore compare esattamente una volta)
Potete utilizzare funzioni precedentemente
definite
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 6
void intersezioneliste (LISTA *PTRLISTA, LISTA L1, LISTA L2)
{
LISTA curr, temp;
temp=NULL;
PTRLISTA=&temp;
curr = L1;
while (curr!=NULL)
{
if ((Rfindlista(L2,curr->elem))
&&(!(Rfindlista(*PTRLISTA,curr->elem))))
insertHEADlista(PTRLISTA,curr->elem);
curr = curr->next;
}
}
SUPPONETE CHE LE DUE LISTE L1 e L2 SIANO ORDINATE. POTETE
RENDERE PIU’ EFFICIENTE IL CODICE?
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Glicini
struct nodoramo{
int valore;
ramo
struct nodoramo *succ;
3
};
struct elemglicine{
6
struct nodoramo *ramo;
struct elemglicine *next;
};
1
typedef struct nodoramo NODO;
typedef NODO *RAMO;
typedef struct elemglicine GLICINE2;
typedef GLICINE2 *GLICINEPTR;
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
next
2
succ
9
succ
succ
5
succ
succ
succ
Esercizio 7
Si scriva una funzione che dato un glicine
stampi i valori dei suoi elementi
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 7
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
succ
1
succ
5
succ
9
succ
2
succ
succ
6
3
next
void stampaglicine (GLICINEPTR G)
{
RAMO r;
if (G!=NULL)
{
printf("[ ] ->");
r=G->ramo;
while(r!=NULL)
{
printf("[[%d]]->",r->valore);
r=r->succ;
}
printf("\n | \n");
stampaglicine(G->next);
}
}
ramo
G
Esercizio 8
Si scriva una funzione che dato un glicine
calcoli la somma dei suoi elementi pari
Si possono utilizzare funzioni ausiliarie
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008
Esercizio 8
Funzione ausiliaria
int sommapariramo(RAMO R)
{
if(R==NULL)
return 0;
else
return((R->valore%2)?sommapariramo(R>succ):(1+sommapariramo(R->succ)));
}
/*Post: restituisce il numero di valori pari nel glicine*/
int sommapari(GLICINEPTR G)
{
if (G==NULL)
return 0;
else
return(sommapariramo(G->ramo)+sommapari(G->next));
}
Prof.ssa Chiara Petrioli -- corso di
programmazione 1, a.a. 2007/2008