ESERCIZIO
Riscrivere con funzioni ricorsive le procedure
// PROTOTIPI
void costruisciLista(Pnodo &);
void stampaLista(Pnodo );
void creaNodo (int, Pnodo&);
Pnodo inserisciNodoTesta (int,Pnodo &);
void inserisciNodoCoda (int,Pnodo &);
void inserisciNodoMezzo (int,Pnodo &);
void cancellaNodo (int,Pnodo &);
void cercaItem(int ,Pnodo ,Pnodo &);
bool listaVuota(Pnodo);
int cercaPosizione(int, Pnodo);
int contaNodi(Pnodo);
// PROTOTIPI
void costruisciLista(Pnodo &, string &);
void stampaLista(Pnodo );
void creaNodo (int, Pnodo&);
Pnodo inserisciNodoTesta (int,Pnodo &);
Pnodo inserisciNodoCoda(int ,Pnodo , Pnodo &) ;
Pnodo inserisciNodoMezzo(int,Pnodo,Pnodo &);
Pnodo cancellaNodo (int,Pnodo &,Pnodo &);
Pnodo cercaItem(int ,Pnodo ,Pnodo &);
bool listaVuota(Pnodo);
int cercaPosizione(int, Pnodo);
int contaNodi(Pnodo);
void inserisciNodoCoda ( int info1,Pnodo &L)
{// inserisce un nuovo nodo in coda alla lista
Pnodo prec, curr;
if (L==NULL)
creaNodo(info1, L);
else {
curr=L; prec=NULL;
while (curr!=NULL) {
Pnodo
inserisciNodoCoda ( int
info1,Pnodo
L, &L)
Pnodo
void inserisciNodoCodaNew
( int
info1,Pnodo
prec=curr;
&TL)
{// inserisce un nuovo nodo in coda
alla lista
curr=curr->next;
{// inserisce un nuovo nodo in coda alla lista
}
if (L==NULL)
temp;
creaNodo(info1, prec->next); Pnodo
{temp=L;
}
}
if creaNodo(info1,
(temp==NULL) L);
return
L;
creaNodo(info1,
L);
} {
else
else
{ (temp->next!=NULL) {
while
iftemp=temp->next;
(L->next!=NULL)
}return inserisciNodoCoda(info1, L->next, TL);
creaNodo(info1, temp->next);
} creaNodo(info1, L->next);
} return TL;
}
}
void inserisciNodoMezzo( int info1,Pnodo &L)
{// inserisce un nuovo nodo in mezzo alla lista
Pnodo inserisciNodoMezzo( int info1,Pnodo L,
int inf;
Pnodo &TL)
Pnodo prec, curr, Temp;
{ // inserisce un nuovo nodo in mezzo alla lista
cout<<"Dammi valore nodo ";
int inf;
cin>>inf;cout<<endl;
Pnodo Temp;
if (L==NULL)
if (L==NULL) {
creaNodo(info1, L);
creaNodo(info1, L);
else {
return L;
curr=L; prec=NULL;
} //Se la lista è nulla la crea con il nuovo nodo
while ((curr->info!=info1)&&(curr->next!=NULL))
else {
// cerca il nodo
{prec=curr;
if (L->info!=info1)&&(L->next!=NULL))
curr=curr->next;
return inserisciNodoMezzo(info1, L->next, TL);
}
else
if (curr->info==info1)
{
{ creaNodo(inf, Temp);
if ((L->info!=info1)
Temp->next=curr->next;
return TL ; // se non c'è esce
curr->next=Temp;
else
// se c'è lo aggiunge
}
cout<<"Dammi valore nodo da aggiungere";
}
cin>>inf;cout<<endl;
}
creaNodo(inf, Temp);
Temp->next=L->next;
L->next=Temp;
return TL ;}
}
}
Pnodo cancellaNodo (int item1,Pnodo &L,
Pnodo &TL)
{ // cancella un nodo di chiave item1
Pnodo Temp;
if (L!=NULL)
{ if (L->info==item1)
{ Temp=L;
L=L->next;
delete Temp;
return TL;
}
else
return cancellaNodo(item1, L->next, TL);
}
void cercaItem(int item1,Pnodo L, Pnodo &p) else return TL;
}
{
if (L!=NULL) {
if (L->info==item1) {
p=L;
Pnodo cercaItem (int item1,Pnodo L)
return; }
{// cerca la chiave item1
else
if (L==NULL) {
cercaItem(item1, L->next,p);
return false;
}
}
else if (L->info==item1)
else
return true;
{
else
p=NULL;
return cercaItem(item1, L->next);
return;}
void cancellaNodo (int item1,Pnodo &L)
{
Pnodo Temp;
if (L!=NULL) {
if (L->info==item1) {
Temp=L;
L=L->next;
delete Temp;
}
else
cancellaNodo(item1, L->next);
}
}
int cercaPosizione(int item1, Pnodo L)
{ // cerca la posizione nella lista di item1
{ if ((L->next==NULL)&&(L->info!=item1) )
return -100;
else
if (L->info==item1)
return 1;
else
return cercaPosizione(item1, L->next)+1;
}
Pnodo cancellaNodoUguali (int item1,Pnodo &L,
}
Pnodo &TL)
{ // cancella un nodo di chiave item1
Pnodo Temp;
if (L!=NULL)
int contaNodi(Pnodo L)
{
{ // conta i nodi della lista
if (L->info==item1)
if (L==NULL)
{ Temp=L;
return 0;
L=L->next;
else
delete Temp;
return contaNodi(L->next)+1;
cancellaNodoUguali(item1, L, TL); }
}
else
return cancellaNodoUguali(item1, L->next, TL);
}
listeFileGenRic2
return TL; }
•Date due liste legate di interi L1 ed L2,
contenenti eventuali ripetizioni, costruire Pnodo Lista3(Pnodo M,Pnodo M2, Pnodo &M3)
la lista legata L3, senza ripetizioni, che {
contiene tutti gli interi presenti sia in L1
if (M==NULL) return M3;// se L1 è vuota ritorna NULL
che in L2. UNIONE
else
{
Pnodo L1,L2, L3,p3;
aggiornaM3(M,M3); //inserisci L1 in M3 senza ripetizioni
costruisciLista(L1);
aggiornaM3(M2,M3); //inserisci L2 in M3 senza ripetizioni
stampaLista(L1);
}
cout<<endl;
return M3;
costruisciLista(L2);
}
stampaLista(L2);
cout<<endl;
void aggiornaM3(Pnodo L,Pnodo &L3)
system("pause");
{Pnodo Lx, temp;
L3=NULL;
while (L!=NULL) // Finchè L non è finita
p3=Lista3(L1 ,L2 , L3);
{if (L3==NULL) // Se siamo all'inizio in L3 metti L
if (p3==NULL) cout<<"UNIONE VUOTA"<<endl;
{creaNodo(L->info,L3);
}
else
else
{ cout<<"\n UNIONE "<<endl;
{
stampaLista(p3);
Lx=L3;
}
//Finchè non trovo in L3 L oppure non finisce L3
}
while ((Lx->info!=L->info)&&(Lx->next!=NULL))
Lx=Lx->next;
if (Lx->info!=L->info) // Se non c'è l'aggiungo
{ creaNodo(L->info,temp);
Lx->next=temp;
}
listeUnione3
}
L=L->next; }
}
Date due liste legate di caratteri L1 ed L2, contenenti
eventuali ripetizioni, costruire la lista legata L3, senza
ripetizioni, che contiene tutti e soli i caratteri
presenti in entrambe le liste. INTERSEZIONE
Pnodo Lista3(Pnodo M1,Pnodo M2, Pnodo &M3){ bool bol;
Pnodo L1,L2, L3,L4;
while (M1!=NULL){
costruisciLista(L1);
if (cercaItem(M1->info,M2)) aggiungiNodo(M1->info,M3);
stampaLista(L1);
M1=M1->next;
costruisciLista(L2);
}
stampaLista(L2);
return M3;
L3=NULL;
}
cout<<"\n INTERSEZIONE "<<endl;
L4=Lista3(L1 ,L2 , L3);
if (L4==NULL) cout<<" Intersezione vuota "<<endl;
stampaLista(L4);
void aggiungiNodo ( int info1,Pnodo &M3)
{ Pnodo curr=M3;
if (M3==NULL){ creaNodo(info1,M3);
return;}
else {
while ((curr->next!=NULL)&&(curr->info!=info1))
curr=curr->next;}
if (curr->next==NULL)
creaNodo(info1,curr->next);
return;
}
bool cercaItem(int item1,Pnodo L)
{// cerca la chiave item1
if (L==NULL) {
return false;
}
else if (L->info==item1)
return true;
else
return cercaItem(item1, L->next);
}
listeIntersezione3
Siano L1 ed L2 due liste legate, di eguale lunghezza. Scrivere una procedura
o funzione ricorsiva che restituisca la lista L1 contenente in successione gli
elementi di L1 ed L2, alternati fra loro.
Esempio: se L1 = (1,4,3,5) ed L2 = (7,6,2,6) ,L1 = (1,7,4,6,3,2,5,6)
Pnodo Alterna(Pnodo &Tl1,Pnodo L1,Pnodo L2)
{ Pnodo temp1, temp2;
if (L1->next==NULL)
{L1->next=L2;
return Tl1;}
else
{
temp1=L1->next;
temp2=L2->next;
L1->next=L2;
L2->next=temp1;
return Alterna(Tl1, L1->next->next,temp2);
}
}
void inserisciNodo ( int info1,Pnodo &L,Pnodo &TL)
{
listeAlternate4
if (TL==NULL)
{ creaNodo(info1, TL);
L=TL;}
else {
creaNodo(info1, L->next);
L=L->next;}
}
•Assegnate due liste legate L1 e L2 contenenti numeri interi, fondere le
due liste in un’unica lista in cui nella prima parte ci siano solo i numeri
dispari e nella seconda parte solo i numeri pari.
int main() {
Pnodo L1, L2,;
costruisciLista(L1);
costruisciLista(L2);
spostaNodi(L1,L2);
cout<<"\n Lfinale "<<endl;
stampaLista(L1);
}
void spostaNodi(Pnodo &TL1, Pnodo TL2)
{
Pnodo plett, TL,prec;
TL=TL1;
prec=TL;
if (TL->next!=NULL) {
plett=TL->next;
while (plett->next!=NULL) {
Sposta(plett,prec,TL);
}
void Sposta(Pnodo &plett, Pnodo &prec,Pnodo &TL)
plett->next=TL2;
{ // se dispari lo metto in testa, se pari lo lascio stare
Sposta(plett,prec,TL); //ultimo nodo di TL1
if ((plett->info)%2!=0)
TL1=TL;
{ prec->next=plett->next;
}
plett->next=TL;
else
TL=plett;
{TL->next=TL2;
plett=prec->next;
plett=TL->next;
cout<<" "<<endl;
}
}
while (plett->next!=NULL) {
else
Sposta(plett,prec,TL1);
{ prec=plett;
}
plett=plett->next;
Sposta(plett,prec,TL1);
}
TL2=NULL; //ultimo nodo di TL2
return;
}
}
spostanodi4
while (!filista.eof())
{
filista>>item;
cout<<"
NODO DA INSERIRE "<<item<<endl;
creaNodo(item, temp);
L=TL; prec=NULL;
while ((L->info<item)&&(L->next!=NULL)) {
prec=L;
L=L->next;}
{
if ((prec==NULL)&&(L->info>=item))
{ temp->next=TL;
TL=temp;
void costruisciLista(Pnodo &TL, string
cout<<"\n metti in testa "<<item<<end; }
&NomeIn)
else
{Pnodo L=NULL, temp,prec=NULL;
if (L->next==NULL)
int item;
{ if (L->info<item)
ifstream filista;
{ L->next=temp;
ofstream outlista;
cout<<"\n metti in coda "<<item<<endl;
NomeIn="L2.txt";
}
// item è più grande dell'ultimo
filista.open(NomeIn.c_str());
else
if (!filista)
{ prec->next=temp;
{ cerr<<"Non si puo' aprire il file"<<endl;
temp->next=L; // item precede l'ultimo
system("pause");}
cout<<"\n metti penultimo "<<endl;}
filista>>item;
}
if (L==NULL)
else
{ creaNodo(item, temp);
{ prec->next=temp;
TL=temp; }
cout<<"\n metti in mezzo "<<endl;
temp->next=L;
}
}
}
listeInsertionSort
}
Dato un file di interi non
ordinati metterli in una lista
in ordine crescente
Un polinomio in una sola variabile può essere rappresentato sotto forma di lista
mediante due numeri, il coefficiente e la potenza della variabile (che è sempre un
8
4
numero non negativo); per esempio il polinomio P1(x)= 4x -5x +8 è rappresentato
come: P1
4
8
-5
4
8
0
Assegnati due polinomi rappresentati da due liste P1 e P2, determinare il polinomio P3
6
4
dato dalla somma di P1 e P2. Es. sia P2 (x)= 3x +2x -4x -2
3
6
2
-4
4
1
-2
0
P3(x)= 4x8+3x6-3x4-4x+6
4
8
3
6
3
4
4
1
6
0
// MAIN
Pnodo Somma(Pnodo L1, Pnodo L2)
int main()
{Pnodo L3, TL3;
{ int item, pot, coef;
L3=NULL; TL3=NULL;
Pnodo poL1, poL2;
while (L1!=NULL)
cout<<"
PRIMO POLINOMIO "<<endl; {
costruisciPolinomio(poL1,nome);
if (L1->grado>L2->grado){
stampaPolinomio(poL1);
inserisciNodoCoda (L1->coeff, L1->grado, L3);
cout<<"
SECONDO POLINOMIO "<<endl;
L1=L1->next;
costruisciPolinomio(poL2,nome);
}
stampaPolinomio(poL2);
else
cout<<"
POLINOMIO SOMMA "<<endl;
if (L1->grado<L2->grado){
stampaPolinomio(Somma(poL1 , poL2));
inserisciNodoCoda (L2->coeff, L2->grado, L3);
system("pause");
}
L2=L2->next;
}
else
void costruisciPolinomio(Pnodo &L,
{
string &NomeIn)
inserisciNodoCoda (L1->coeff+L2->coeff, L1->grado, L3);
{Pnodo nodo;
L1=L1->next;
int coe, po;
L2=L2->next; }
ifstream filista;
}
ofstream outlista;
stampaPolinomio(L3);
filista.open(NomeIn.c_str());
}
----------------------------------filista>>coe; filista>>po;
{
creaNodo(coe,po,L);
filista>>coe;
filista>>po;
while (!filista.eof())
{ inserisciNodoCoda(coe,po,L);
filista>>coe;
filista>>po;
}
}
Si presume che i due polinomi siano ordinati
void inserisciNodoCoda ( int c1,int p1,Pnodo &L)
{// inserisce un nuovo nodo in coda alla lista
Pnodo prec, curr;
if (L==NULL)
creaNodo(c1,p1, L);
else {
curr=L; prec=NULL;
while (curr!=NULL) {
prec=curr;
curr=curr->next; }
creaNodo(c1,p1, prec->next);
}
}
listePolinomi
void stampaPolinomio(Pnodo L)
{ char segno;
segno=' ';
if (L!=NULL)
{ if (L->coeff>=0) segno='+';
if (L->grado==0)cout<<segno<<L->coeff<<" ";
else
cout<<segno<<L->coeff<<"x^"<<L->grado<<" ";
return stampaPolinomio(L->next);
}
}
void creaNodo (int c1, int p1, Pnodo& Temp)
{
Temp= new Rnodo;
Temp->coeff=c1;
Temp->grado=p1;
Temp->next=NULL;
}
Data una lista di interi non ordinata, renderla ordinata .
TL
precPT
pTL
FL
prec
L
Definizioni
Sia TL l’inizio della lista ordinata;
Sia FL La fine della lista ordinata;
Sia L il puntatore di scorrimento sulla parte di lista non ordinata ;
Sia prec il puntatore che precede L ;
Sia pTL il puntatore di scorrimento sulla parte di lista ordinata ;
Sia precpT il puntatore che precede pTL;
Inizializzazioni
Sia TL l’inizio della lista ordinata;
Sia FL La fine della lista ordinata;
Sia L il puntatore di scorrimento sulla parte di lista non ordinata ;
Sia prec il puntatore che precede L ;
Sia pTL il puntatore di scorrimento sulla parte di lista ordinata ;
Sia precpT il puntatore che precede pTL;
FL, TL, L, prec,
pTL, precpT,
TL
precPT
pTL
FL
prec
L
Algoritmo
Fino a che non termina la lista da ordinare
se la chiave di L è maggiore della chiave in prec allora avanza prec e L
altrimenti collega prec con il successivo di L
se L è minore della chiave TL poni L in testa e aggiorna TL
altrimenti scorri a partire da TL e fino a FL, utilizzando pTL, la lista
ordinata.
Non appena trovi una chiave maggiore di quella da inserire, la inserisci
se questo non accade e arrivi alla fine della lista non ordinata
allora controlla
se la chiave va inserita immediatamente prima o dopo FL.
In questo secondo caso dopo l’inserimento aggiorna FL al valore L.
Continua a scorrere la lista
Data una lista di interi non
ordinata, renderla ordinata .
int main()
{
int item; string nome;Pnodo L1;
cout<<"
LISTA DI PARTENZA "<<endl;
costruisciLista(L1,nome);
cout<<"\n LISTA ASSEGNATA"<<endl;;
ordinaLista(L1,L1);
stampaLista(L1);
}
void ordinaLista(Pnodo FL,Pnodo &TL)
{
Pnodo prec,L,pTL,precPT;
prec=TL;
L=FL->next;
// parto dal secondo elemento
while (L!=NULL) // scorro la lista a partire da FL
{
pTL=TL;
if (L->info>=prec->info) // se L è maggiore del suo prec
{ if (prec=FL) FL=prec->next; //se il suo prec coincide con FL aggiorna FL
prec=L;
// aggiorna prec e L
L=L->next;
// avanza
else
// se L è minore del suo prec
{
//sconnetto L
prec->next=prec->next->next; // collego prec con post L
//per collocare L vediamo se siamo all'inizio
if (L->info<=TL->info) { L->next=TL; // L va in testa
TL=L;
}
else
ordinaLista4
ESERCIZIO
Assegnato un insieme dei numeri interi, ad esempio tra 1 e 90, scrivere
un algoritmo che, utilizzando le liste, estragga combinazioni a 5 a 5 dei
suddetti numeri senza mai estrarre un numero già estratto.
Generatore casuale (tra 1 e 8)
Numero 3  Estratto 3
1
2
8
Numero 4  Estratto 7
3
Numero 1  Estratto 8
7
4
Numero 5  Estratto 6
---------
6
5
tombola1
ESERCIZI
Scrivere un algoritmo che trasforma una lista L di interi in una lista priva
di zeri e conti il numero di elementi cancellati.
Siano L1 ed L2 due liste legate che contengono interi, con L1 che contiene
anche ripetizioni.
Costruire una terza lista L3, senza ripetizioni, che contenga tutti gli elementi
di L1 non appartenenti ad L2 .
Siano assegnate due liste astratte, Lpari e Ldispari. Scrivere un algoritmo
che data la lista L non ordinata, contenente numeri interi pari e dispari,
sposti da essa sia i numeri pari che i numeri dispari inserendoli in maniera
ordinata rispettivamente nelle liste Lpari e Ldispari.
Trasformare una lista L disordinata e contenente ripetizioni in una lista
ordinata senza ripetizioni che contiene soltanto gli elementi di L che si ripetono
esattamente k volte.
SFIDA
Verifica se una lista è palindroma utilizzando una funzione ricorsiva
listePalindroma2
{ precPT=NULL;
// a partire da TL trova dove collocare L
while ((L->info>pTL->info)&&(pTL->next!=FL)) // avanza tra TL e FL se L>pTL
{ precPT=pTL;
pTL=pTL->next; }
{ if (L->info<=pTL->info)
{
precPT->next=L; //inserisci subito prima di pTL
L->next=pTL; }
else
{ // sono arrivato a FL controllo se L va prima o dopo
if (L->info<FL->info)
{ pTL->next=L;
L->next=FL; }
else
{ L->next=FL->next;
FL->next=L;
FL=L; }
L->next=pTL->next->next; //inserisci in mezzo
pTL->next=L;
}
}
}
}
// se non ho finito incremento L
L=prec->next;
}
}
Assegnato un file di record denominato Anagrafe.dat
I record hanno la seguente struct:
struct TPersona {
char cognome[20];
char nome[20];
Tpdata nascita;
char luogo[20];
};
Mostrare a video tutti i record ordinati prima per cognome, poi per
luogo e infine per data di nascita.
Si possono costruire degli array di puntatori ai record e quindi
ordinarli ognuno secondo il campo desiderato.
struct Tpersona {
char cognome[30];
char nome[20];
Tpdata nascita;
char luogo[20];
};
typedef Tpersona* Ppersona;//Ppersona è un nuovo tipo: puntatore a Tpersona
// PROTOTIPI
void Stampa(Ppersona[],int);
void bubble(Ppersona [] ,int,int(*)(Ppersona ,Ppersona));
int cognome(Ppersona,Ppersona);
int luogo(Ppersona,Ppersona);
int nascita(Ppersona ,Ppersona );
// MAIN
main () {
Tpersona persona1;
Ppersona PuntaP1[101], PuntaP2[101], PuntaP3[101];
const int Lrec=sizeof(Tpersona);
fstream filepers;
filepers.open(Nomefile,ios::in|ios::out|ios::binary|ios::ate);
int NumPers, esiste;
if (!filepers) { …………. }
NumPers=filepers.tellg()/Lrec;
filepers.seekg(0,ios::beg);
for (int i=0; i<NumPers; i++) {
filepers.read((char*) &persona1, Lrec); //leggi I dati della persona
PuntaP1[i] = new Tpersona;
// Inserisci i dati letti in PuntaPx[i]
* PuntaP1[i] = persona1;
PuntaP2[i] = PuntaP1[i];
PuntaP3[i] = PuntaP1[i]; }
cout<<"
INIZIALE"<<endl;
Stampa(PuntaP1,NumPers);
cout<<"\n
COGNOME"<<endl;
bubble(PuntaP1,NumPers,cognome);
Stampa(PuntaP1,NumPers);
cout<<"\n
LUOGO"<<endl;
bubble(PuntaP2,NumPers,luogo);
Stampa(PuntaP2,NumPers);
cout<<"\n
NASCITA"<<endl;
bubble(PuntaP3,NumPers,nascita);
Stampa(PuntaP3,NumPers);
filepers.close();
void bubble(Ppersona vet[], int N,
int(*confronta)(Ppersona ,Ppersona))
{ int j, k;
Ppersona s;
for (k=0; k<N-1; k++)
{ for (j=N-2; j>=k; j--)
{ if (confronta(vet[j], vet[j+1])>=1)
{ s=vet[j];
vet[j]=vet[j+1];
vet[j+1]=s; }
}}}
int cognome(Ppersona Px , Ppersona Py)
{ return ((strcmp(Px->cognome, Py->cognome)));
}
int luogo(Ppersona Px , Ppersona Py)
{
return ((strcmp(Px->luogo, Py->luogo)));
}
int nascita(Ppersona Px , Ppersona Py)
{ double data1,data2;
data1=(Px->nascita.anno)*10000+(Px->nascita.mese)*100+(Px->nascita.giorno);
data2=Py->nascita.anno*10000+Py->nascita.mese*100+Py->nascita.giorno;
return (data1-data2);
}