TD/TP 02 Listes chaînées

brahim bakkas

14-03-2023

Exercice 1 Gestion des nombres

1. Créez une structure composée d’un nombre N de type entier et un pointeur vers la même structure nommé ListeEntier.
2. Ecrire une fonction ajouterDebut qui permet d’ajouter le nombre c à la liste des entier.
ListeEntier* ajouterDebut( ListeEntier * debut, int c);

3. Ecrire une fonction ajouterFin qui permet d’ajouter le nombre c à la liste des entiers.
ListeEntier* ajouterFin( ListeEntier * debut, int c);

4. Donner une fonction qui permet de créer une liste chaînée ListeChiffre des chiffres d’un nombre entier N (convertir un
nombre entier N vers une liste chaînée des chiffres qui le compose). Par exemple le nombre N= 1234 est composé des
chiffres 1 -> 2 -> 3 -> 4.
typedef ListeEntier ListeChiffre; // redéfinir le nom de la liste
ListeChiffre * nombreToListe(int N);

5. Donner une fonction qui calcule la moyenne de la liste des chiffres.

double moyenne(ListeChiffre* tete);

6. Donner une fonction qui permet de supprimer un chiffre au début de la liste.

listeChiffre* supprimer (listeChiffre* tete);

7. Ecrire une fonction qui permet de tester si un nombre n est premier ou non.
bool premier (int n);

8. Donner une fonction qui permet de supprimer tous les nombres premiers de la liste ListeEntier
listeChiffre* suppAllprim(listeChiffre* tete);

9. Ecrire une fonction qui permet de renverser les éléments d’une liste.
ListeChiffre* renverser(ListeChiffre * tete);

10. Ecrire une fonction palindome qui permet de tester si un nombre n est palindrome ou non. un nombre palindrome est
un entier n dont la listes de ses chiffres et son inversse sont egaux deux à deux.
bool palindrome(int n);

11. Ajouter un programme main qui permet d’initialiser la liste et programmer les appels des fonctions avec un menu.

1
Exercice 1 correction
1. Créez une structure composée d’un nombre N de type entier et un pointeur vers la même structure nommé ListeEntier.
struct ListeEntier{
int N;
ListeEntier* suiv;
};

2. Ecrire une fonction ajouterDebut( ListeEntier * debut, int c) qui permet d’ajouter le nombre c à la liste des entier.
//Q2
ListeEntier* ajouterDebut(ListeEntier * debut, int c){
ListeEntier* nouveau;
nouveau = new ListeEntier;
nouveau->N=c;
nouveau->suiv= NULL;
if (debut==NULL){
debut=nouveau;
}else{
nouveau->suiv=debut;
debut=nouveau;
}
return debut;
}

3. Ecrire une fonction ajouterFin (ListeEntier * debut, int c) qui permet d’ajouter le nombre c à la liste des entiers.
// Q3
ListeEntier* ajouterFin(ListeEntier* debut, int c){
ListeEntier* nouveau;
nouveau = new ListeEntier;
nouveau->N=c;
nouveau->suiv= NULL;
if (debut==NULL){
debut=nouveau;
}else{
ListeEntier* p;
p=debut;
while(p->suiv!=NULL)
p=p->suiv; // avancé vers le noed suivant
p->suiv=nouveau;
nouveau->suiv= NULL;
}
return debut;
}

4. Donner une fonction qui permet de créer une liste chaînée ListeChiffre des chiffres d’un nombre entier N (convertir un
nombre entier N vers une liste chaînée des chiffres qui le compose). Par exemple le nombre N= 1234 est composé des
chiffres > 1 -> 2 -> 3 -> 4.
//Q4
typedef ListeEntier listeChiffre;
listeChiffre* NombreToListe(int N){
listeChiffre* liste=NULL;
while( N!=0 ){
liste = ajouterDebut(liste,N%10);
N= N/10;
}
return liste;
}

2
 5. Donner une fonction qui calcule la moyenne de la liste des chiffres.
//Q5
double moyenne(listeChiffre* tete){
int nb=0;
int somme;
listeChiffre* p;
p=tete;
while (p!=NULL){
nb++;
somme+=p->N;
p =p->suiv;
}
if (nb==0)
return 0;
else
return (double)somme/nb;
}

6. Donner une fonction qui permet de supprimer un chiffre au début de la liste. listeChiffre* supprimer (listeChiffre*
tete)
//Q6
listeChiffre* supprimer (listeChiffre* tete){
if (tete==NULL){
cout<<"Liste vide\n";
}
else{
listeChiffre* p;
p = tete;
tete = p->suiv;
cout<<"valeur entete"<< p->N <<endl;
}
return tete;
}

7. Ecrire une fonction qui permet de tester si un nombre n est premier ou non. bool premier (int n)
//Q7
bool premier(int n){

if (n<=1){
return false;
}
for (int i=2;i<n; i++){
if (n%i==0)
return false;
}
return true;
}

8. Donner une fonction qui permet de supprimer tous les nombres premiers de la liste ListeEntier listeChiffre* suppAll-
prim(listeChiffre* tete)
//Q8
listeChiffre* suppAllprim(listeChiffre* tete){
listeChiffre *p, *cur;
if (tete == NULL){
cout<<"liste vide\n";
return tete;
}else{

3
 cur = tete;
p = cur->suiv;
while (p->suiv!= NULL){
if (premier(p->N)){
cout<<p->N<<" \n";
cur->suiv = p->suiv;
p = p->suiv;
}else{
cur=cur->suiv;
p =p->suiv;
}

}
}
return tete;
}

9. Ecrire une fonction qui permet de renverser les éléments d’une liste.
//Q9
listeChiffre* renverser(listeChiffre* tete){
listeChiffre* inv=NULL;
listeChiffre * p=tete;
while ( p!=NULL){
inv=ajouterDebut(inv, p->N);
p=p->suiv;
}
return inv;
}

10. Ecrire une fonction qui permet de tester si un nombre n est palindrome ou non. bool palindrome(int n)
//Q10
bool palindrome(int n){
listeChiffre *p, *q;
p = NombreToListe(n);
q = renverser(p);
listeChiffre *ptr1, *ptr2;

ptr1=p;
ptr2=q;

while (ptr1 !=NULL && ptr2 !=NULL){

if (ptr1->N != ptr2->N)
return false;
else{
ptr1=ptr1->suiv;
ptr2=ptr2->suiv;
}
}
if (ptr1 ==NULL && ptr2 ==NULL)
return true;
else
return false;
}

11. Ajouter un programme main qui permet d’initialiser la liste et programmer les appels des fonctions avec un menu.

int main() {

4
int choix, c;
listeChiffre*tete;
cout<<"Programme de test\n";
do{
cout<<"------- Menu ---------------------\n";
cout<<"1:------- créer liste N ----------\n";
cout<<"2:------- ajouter début ----------\n";
cout<<"3:------- ajouter fin ------------\n";
cout<<"4:------- supprimer entete -------\n";
cout<<"5:------- suppAllprim ------------\n";
cout<<"6:------- afficher liste ---------\n";
cout<<"7:------- moyenne liste ---------\n";
cout<<"8:------- is palindrome ---------\n";
cout<<"0:------- Sortir -----------------\n";
cout<<"----------------------------------\n";
cin>> choix;
int N;
switch (choix){
case 1:
cout<<"Donner un entier N";
cin>>N;
tete =NombreToListe(N);
afficheListe(tete);
break;
case 2:
cout<<"-- Donner chiffre au début--\n";
cin>>c;
tete=ajouterDebut(tete,c);
afficheListe(tete);
break;
case 3:
cout<<"--Ajouter à la fin --:\n";
cin>>c;
tete=ajouterFin(tete,c);
afficheListe(tete);
break;
case 4:
cout<<"-- Supprimer au début--:\n";
tete=supprimer (tete);
afficheListe(tete);
break;
case 5:
cout<<"- Supprimer all prim--:\n";
tete=suppAllprim(tete);
afficheListe(tete);
break;
case 6:
afficheListe(tete);
break;
case 7:
cout<<"moyenne liste:"<<moyenne(tete);
break;
case 8:
cout<<"Donner un entier N";
cin>>N;
if (palindrome(N))
cout<<N <<" est palindrome \n";

5
 else
cout<< N<<" est non palindrome \n";
break;
default:
cout<<"Au revoir --";
choix=0;
exit(0);
break;
}
}while(choix !=0);

return 0;
}

6
TP02 Solution Exercice 1
// by B.BBAKKAS
#include <iostream>
using namespace std;

// structure de données
struct ListeEntier{
int N;
ListeEntier* suiv;
};

//Q2
ListeEntier* ajouterDebut(ListeEntier * debut, int c){
ListeEntier* nouveau;
nouveau = new ListeEntier;
nouveau->N=c;
nouveau->suiv= NULL;

if (debut==NULL){
debut=nouveau;
}else{
nouveau->suiv=debut;
debut=nouveau;
}
return debut;
}

// Q3
ListeEntier* ajouterFin(ListeEntier* debut, int c){
ListeEntier* nouveau;
nouveau = new ListeEntier;
nouveau->N=c;
nouveau->suiv= NULL;
if (debut==NULL){
debut=nouveau;
}else{
ListeEntier* p;
p=debut;
while(p->suiv!=NULL)
p=p->suiv; // avancé vers le noed suivant
p->suiv=nouveau;
nouveau->suiv= NULL;
}
return debut;
}

//Q4
typedef ListeEntier listeChiffre;

listeChiffre* NombreToListe(int N){

listeChiffre* liste=NULL;
while( N!=0 ){
liste = ajouterDebut(liste,N%10);
N= N/10;
}
return liste;

7
}

//Q5
double moyenne(listeChiffre* tete){
int nb=0;
int somme;
listeChiffre* p;
p=tete;
while (p!=NULL){
nb++;
somme+=p->N;
p =p->suiv;
}
if (nb==0)
return 0;
else
return (double)somme/nb;
}

//Q6
listeChiffre* supprimer (listeChiffre* tete){
if (tete==NULL){
cout<<"Liste vide\n";
}
else{
listeChiffre* p;
p = tete;
tete = p->suiv;
cout<<"valeur entete"<< p->N <<endl;
}
return tete;
}

//Q7
bool premier(int n){

if (n<=1){
return false;
}
for (int i=2;i<n; i++){
if (n%i==0)
return false;
}
return true;
}

//Q8
listeChiffre* suppAllprim(listeChiffre* tete){
listeChiffre *p, *cur;
if (tete == NULL){
cout<<"liste vide\n";
return tete;
}else{
cur = tete;
p = cur->suiv;
while (p->suiv!= NULL){
if (premier(p->N)){

8
 cout<<p->N<<" \n";
cur->suiv = p->suiv;
p = p->suiv;
}else{
cur=cur->suiv;
p =p->suiv;
}
}
// traitement du premier element de la liste
if (premier(tete->N))
tete=supprimer(tete);
}
return tete;
}

//Q9
listeChiffre* renverser(listeChiffre* tete){
listeChiffre* inv=NULL;
listeChiffre * p=tete;
while ( p!=NULL){
inv=ajouterDebut(inv, p->N);
p=p->suiv;
}
return inv;
}

//Q10
bool palindrome(int n){
listeChiffre *p, *q;
p = NombreToListe(n);
q = renverser(p);
listeChiffre *ptr1, *ptr2;

ptr1=p;
ptr2=q;

while (ptr1 !=NULL && ptr2 !=NULL){

if (ptr1->N != ptr2->N)
return false;
else{
ptr1=ptr1->suiv;
ptr2=ptr2->suiv;
}
}
if (ptr1 ==NULL && ptr2 ==NULL)
return true;
else
return false;

// afficheList
void afficheListe(listeChiffre* tete){
listeChiffre *p=tete;
cout<<"Contenu de la liste:\n";
while(p!=NULL){
cout<< p->N <<"->";

9
 p=p->suiv;
}
cout<<"\n";
}

int main() {
int choix, c;
listeChiffre*tete;
cout<<"Programme de test\n";
do{
cout<<"------- Menu --------------\n";
cout<<"1:------- créer liste N ----------\n";
cout<<"2:------- ajouter début ----------\n";
cout<<"3:------- ajouter fin ------------\n";
cout<<"4:------- supprimer entete -------\n";
cout<<"5:------- suppAllprim ------------\n";
cout<<"6:------- afficher liste ---------\n";
cout<<"7:------- moyenne liste ---------\n";
cout<<"8:------- is palindrome ---------\n";
cout<<"0:------- Sortir -----------------\n";
cout<<"----------------------------------\n";
cin>> choix;
int N;
switch (choix){
case 1:
cout<<"Donner un entier N";
cin>>N;
tete =NombreToListe(N);
afficheListe(tete);
break;
case 2:
cout<<"-- Donner chiffre au début--\n";
cin>>c;
tete=ajouterDebut(tete,c);
afficheListe(tete);
break;
case 3:
cout<<"--Ajouter à la fin --:\n";
cin>>c;
tete=ajouterFin(tete,c);
afficheListe(tete);
break;
case 4:
cout<<"-- Supprimer au début--:\n";
tete=supprimer (tete);
afficheListe(tete);
case 5:
cout<<"- Supprimer all prim--:\n";
tete=suppAllprim(tete);
afficheListe(tete);
break;
case 6:
afficheListe(tete);
break;
case 7:
cout<<"moyenne liste:"<<moyenne(tete);

10
 break;
case 8:
cout<<"Donner un entier N";
cin>>N;
if (palindrome(N))
cout<<N <<" est palindrome \n";
else
cout<< N<<" est non palindrome \n";
break;
default:
cout<<"Au revoir --";
choix=0;
exit(0);
break;
}
}while(choix !=0);

return 0;
}

11
Exercice 2 : Gestion d’une liste de produit
TD
Créer une structure produit identifiée par :
• une référence (int) ,
• un nom (tableau de 30 caractères),
• un prix d‘achat et un prix de vente de type réels et une variable suivant de type pointeur sur la structure produit.
1. Une fonction initPrduit qui permet d’initialiser et retourner un nouveau produit
porduit * initProduit( int ref, char nom[], float pAchat, float pVente)

2. Rechercher un produit par référence.

bool rechercher_produit(produit* list, int ref)

3. Ajouter une fonction qui permet de tester si un produit existe ou non dans la liste des produits (référence doivent être
unique)
bool existe( produit* list, produit * prod)

4. Ajouter un produit en tête de liste si la référence de ce produit n’existe pas déjà dans la liste. La référence est unique
dans la liste (clé primaire).
porduit* ajouterDebut(produit* list, produit* prod)

5. Ajouter un produit en fin de liste. La référence est une clé primaire.

produit* ajouter-fin(produit* list)

6. Afficher tous les produits de la liste.

void afficher_tout(produit* list)

7. Supprimer un produit de la liste sachant sa référence.

produit* supprimer(produit* list, int red)

8. Calculer le nombre d’occurrences d’un nom de produit. Càd, rechercher le nombre de produits qui partagent le même
nom.
int* nb_occurrences(produit* list, char nom[])

9. Ecrire le programme principal qui appelle les fonctions précédentes via un menu.

TP solution

#include<iostream>
using namespcae std;

// Déclaration de la structure
struct produit{
int ref;
char nom[30];
float p_vente,p_achat;
produit* next;
};

produit* ajouter_produit_entete(produit* list){

produit* nv=new produit;
if(list==NULL){

12
 cout<<"on va initialiser la liste"<<endl;
}
cout<<"donner la reference du produit"<<endl;
cin>> nv->ref;
produit* tmp;
tmp=list;
while(tmp !=NULL){
if(tmp->ref==nv->ref){
cout<<" cette reference existe deja, donner une autre"<<endl;
return list;
}

tmp=tmp->next;
}

cout<<"donner le nom de produit"<<endl;

cin>>nv->nom ;
cout<<"donner la prix d'achat "<<endl;
cin>>nv->p_achat;
cout<<"donner la prix de vente"<<endl;
cin>>nv->p_vente;
nv->next=list;
return nv ;
}

produit* ajouter_enfin(produit*list){
produit* nv=new produit;;
if(list==NULL){ cout<<"on va initialiser la liste"<<endl; }
cout<<"donner la ref du produit"<<endl;
cin>> nv->ref;
produit* tmp;
tmp=list;
while(tmp!=NULL){
if(tmp->ref==nv->ref){
cout<<" cette reference concerne un autre produit"<<endl;
return list;
}
tmp=tmp->next;
}
cout<<"donner le nom de produit"<<endl;
cin>> nv->nom;
cout<<"donner la prix d'achat "<<endl;
cin>>nv->p_achat;
cout<<"donner la prix de vente"<<endl;
cin>>nv->p_vente;
nv->next=NULL;
if(list==NULL){
return nv;
}else{
produit*tmpe;
tmpe=list;
while(tmpe->next!=NULL){
tmpe=tmpe->next;
}
tmpe->next=nv;
return list;
}

13
 }

// Question affiche tt

void afficher_tout(produit*list){
produit* tmp;
tmp=list;
if(tmp==NULL){
cout<<"aucune liste a afficher, ajoutez une liste"<<endl;
}
while(tmp!=NULL){
cout<<"la reference du produit est:"<<tmp->ref;
cout<<"le nom de produit est:"<<tmp->nom;
cout<<"le prix d'achat de produit est:"<<tmp->p_achat;
cout<<"le prix de vente de produit est:"<<tmp->p_vente;
tmp=tmp->next;
}
}

// recherche par ref

void rechercher_par_ref_et_affiche(produit*list){
int a;
cout<<"donner la reference du produit à afficher"<<endl;
cin>>a;
produit* tmp;
tmp=list;
while(tmp->ref!=a ){
tmp=tmp->next;
if(tmp==NULL){
cout<<"la ref du produit n'existe pas\n "<<endl;
return ;
}
}
cout<<"la reference du produit est:"<<tmp->ref;
cout<<"le nom de produit est:"<<tmp->nom;
cout<<"le prix d'achat de produit est:"<<tmp->p_achat;
cout<<"le prix de vente de produit est:"<<tmp->p_vente;
}

// fonciton supprimer

produit* supprimer(produit* list){

int a;
if(list==NULL){
return list;
}
cout<<"donner la reference à supprimer"<<endl;
cin>>a;
produit* tmp =list;
while(tmp!=NULL){
if(tmp->ref==a){
cout<<" Ce produit va etre supprime"<<endl;
if(tmp==list){
list=list->next;
}
else{
produit*tmp2; tmp2=list;

14
 while(tmp2->next!=tmp){ tmp2=tmp2->next; }
tmp2->next=tmp->next;
delete tmp;
};
return list;
}
tmp=tmp->next;
}
if(tmp==NULL){
cout<<"la reference n'existe pas"<<endl;
return list;
}

cout<<"il n'y a aucun produit a supprimer"<<endl;

return list;
}

// modifier produit
produit* modifier(produit*list){
int a, b;
if(list==NULL){
cout<<" elle n'y'a aucune liste a modifier"<<endl;
return list;
}
else{
cout<<"donner la reference du produit à modifier"<<endl;
cin>>a;
produit *tmp =list;
while(tmp->ref!=a){
tmp=tmp->next;
if(tmp==NULL){
cout<<"Cette reference n'exite pas"<<endl;
return list;
}
}

cout<<"donner la nouvelle reference"<<endl;

cin>> b;

produit * tmpe;
tmpe=list;
if(tmp->ref!=b){
while(tmpe!=NULL){
if(tmpe->ref==b) {
cout<<"cette reference concerne un autre produit "<<endl; return list;
}
tmpe=tmpe->next;
}
}
tmp->ref=b;
cout<<"donner le nom du produit"<<endl;
cin>>tmp->nom;
cout<<"donner la prix d'achat "<<endl;
cin>>tmp->p_achat;
cout<<"donner la prix de vente"<<endl;
cin>>tmp->p_vente;
return list;

15
 }
}

// Menu
void Menu(produit * ma_liste){
int a;
while(a!=0){
cout<<"\n ********** Menu **********************\n";
cout<<" 0-pour sortir du menu \n";
cout<<" 1-ajouter un produit en tete de liste\n";
cout<<" 2-ajouter un produit en fin de liste\n";
cout<<" 3-afficher tous les produits\n";
cout<<" 4-rechercher un produit par référence\n";
cout<<" 5-supprimer un produit de la liste\n";
cout<<" 6-modifier les informations d'un produit\n";

cin>> a;
switch(a){
case 1:
ma_liste=ajouter_produit_entete(ma_liste);
break;
case 2: ma_liste=ajouter_enfin(ma_liste);
break;
case 3: afficher_tout(ma_liste);
break;
case 4: rechercher_par_ref_et_affiche(ma_liste);
break;
case 5: ma_liste=supprimer(ma_liste);
break;
case 6: ma_liste=modifier(ma_liste);
break;
default : break;
} } }
//Programme principal
int main(){
produit* ma_liste;
ma_liste=NULL;
Menu(ma_liste);
return 0;
}

16