Exercice 1 : (Listes simplement chaînées)
Nous proposons maintenant une nouvelle structure de liste chainée il s’agit de suivre la liste des produits achetés par un client au niveau d’une supérette.
Chaque élément de la liste est composé des champs suivants :
code_prod(9 alphanumérique),
Désignation(50 car),
UM (3 car), // Unité de mesure (U, Kg, L, bout, cart, …)
PUA_HT(réel), // Prix Unitaire d’Achat Hors Taxe
Qte(réel), // Quantité achetée
TVA(9% ou 21%) // Taxe sur Valeur Ajoutée
Ce programme affichera le menu suivant :
- AJOUTER des produits Au début de la liste
- AFFICHER la liste des produits achetés
- Afficher le nombre total des produits achetés ainsi que les montants total HT, total TVA et total TTC(net à payé)
- Demander au client le paiement et calculer la différence entre le montant payé et le net à payé
- SUPPRIMER des produits
- Afficher le prix max et le prix min
- VIDER la liste.
- ARRÊT du programme.
Et effectuera le traitement (fonctions/ procédures) correspondant au choix effectué.
Solution :
#include <iostream>
#include <string.h>
using namespace std ;
struct produit
{
char code[9] ;
char name[50] ;
char MU[3] ;
int Qty ;
double PET ;
double VAT ;
struct produit * next ;
};
typedef struct produit Element ;
typedef Element * List ;
List create_node()
{
List ptr = new Element ;
cout << "Give the product code : " ;
cin >> ptr->code ;
cout << "Give the product name : " ;
cin >> ptr->name ;
cout << "Give the product MU : " ;
cin >> ptr->MU ;
cout << "Give the product quantity : " ;
cin >> ptr->Qty ;
cout << "Give the product PET : " ;
cin >> ptr->PET ;
cout << "Give the product VAT : " ;
cin >> ptr->VAT ;
ptr->next = NULL ;
return ptr ;
}
void display_list(List lst)
{
List ptr = lst ;
if(lst == NULL)
{
cout << "The product list is empty." << endl << endl ;
return ;
}
while(ptr != NULL)
{
cout << "The product code is : " << ptr->code << endl ;
cout << "The product name is : " << ptr->name << endl ;
cout << "The product MU is : " << ptr->MU << endl ;
cout << "The product quantity is : " << ptr->Qty << endl ;
cout << "The product PET is : " << ptr->PET << endl ;
cout << "The product VAT is : " << ptr->VAT << endl << endl ;
ptr = ptr->next ;
}
return ;
}
List add_node(List list)
{
List ptr = create_node() ;
ptr->next = list ;
list = ptr ;
return list ;
}
List delete_node(List lst, char new_code[])
{
if(lst != NULL)
{
List ptr = lst ;
while((ptr != NULL)&&(strcmp(ptr->code, new_code) != 0))
ptr = ptr->next ;
if((ptr != NULL)&&(strcmp(ptr->code, new_code) == 0))
{
if(ptr == lst)
{
lst = lst->next ;
delete ptr ;
return lst ;
}
else
{
List prv = lst ;
while(prv->next != ptr)
prv = prv->next ;
prv->next = ptr->next ;
delete ptr ;
return lst ;
}
}
else
return lst ;
}
else
return NULL ;
}
List empting_list(List lst)
{
List ptr ;
while(lst != NULL)
{
ptr = lst ;
lst = lst->next ;
delete ptr ;
}
return lst ;
}
void min_max(List lst)
{
List ptr = lst ;
double min = 0.0, max = 0.0 ;
if(lst != NULL)
{
min = lst->PET ;
max = lst->PET ;
}
while(ptr != NULL)
{
if(ptr->PET < min)
{
min = ptr->PET ;
}
if(ptr->PET > max)
{
max = ptr->PET ;
}
ptr = ptr->next ;
}
cout << "Minimum price = " << min << endl ;
cout << "Maximum price = " << max << endl ;
return ;
}
int nodes_number(List lst)
{
List ptr = lst ;
int number = 0 ;
while(ptr != NULL)
{
ptr = ptr->next ;
number++ ;
}
return number ;
}
double total_PET(List lst)
{
List ptr = lst ;
double pet = 0.0 ;
while(ptr != NULL)
{
pet += (ptr->PET * ptr->Qty) ;
ptr = ptr->next ;
}
return pet ;
}
double total_PIT(List lst)
{
List ptr = lst ;
double pwt = 0.0 ;
while(ptr != NULL)
{
pwt += ((ptr->PET + (ptr->PET * ptr->VAT)) * ptr->Qty) ;
ptr = ptr->next ;
}
return pwt ;
}
int main()
{
List lst = NULL ;
int option = 0 ;
cout << "CASHIER PROGRAM" << endl ;
do
{
cout << endl << "you have many options :" << endl ;
cout << "1. add a product." << endl ;
cout << "2. display all bought products." << endl ;
cout << "3. display the number of bought products, their price without taxes and price with taxes, and the taxes amount." << endl ;
cout << "4. checkout, and get the taxes amount." << endl ;
cout << "5. delete a product." << endl ;
cout << "6. display the minimum and the maximum price." << endl ;
cout << "7. empty the product list." << endl ;
cout << "8. end the program." << endl << endl ;
cout << "Enter the corresponding option number :" ;
cin >> option ;
switch(option)
{
case 1 :
cout << "add information of the new product :" << endl ;
lst = add_node(lst) ;
break ;
case 2 :
cout << "display all bought products :" << endl << endl ;
display_list(lst) ;
break ;
case 3 :
cout << "the number of bought products is : " << nodes_number(lst) << endl ;
cout << "the products price without taxes : " << total_PET(lst) << endl ;
cout << "the products price with taxes : " << total_PIT(lst) << endl ;
cout << "the taxes amount : " << total_PIT(lst) - total_PET(lst) << endl ;
break ;
case 4 :
cout << "the total price is : " << total_PIT(lst) << endl ;
cout << "the taxes amount : " << total_PIT(lst) - total_PET(lst) << endl ;
lst = empting_list(lst) ;
break ;
case 5 :
char code[9] ;
cout << "Give the code of the product to delete : " ;
cin >> code ;
lst = delete_node(lst, code) ;
break ;
case 6 :
min_max(lst) ;
break ;
case 7 :
lst = empting_list(lst) ;
break ;
case 8 :
lst = empting_list(lst) ;
break ;
default :
lst = empting_list(lst) ;
return 0 ;
}
}
while(option != 8);
return 0 ;
}
Exercice 2 : (Chaînage arrière d’une Liste doublement chaînée)
Concevoir un algorithme qui réalise le chaînage arrière d’une liste doublement chaînée dont seul le chaînage avant a été effectué.
Solution :
#include <iostream>
using namespace std ;
struct element
{
int data ;
struct element * next ;
struct element * prev ;
};
typedef struct element Element ;
typedef Element * DLList ;
DLList creat_simple_list(DLList lst, int value)
{
DLList ptr = new Element ;
ptr->data = value ;
ptr->next = lst ;
ptr->prev = NULL ;
lst = ptr ;
return lst ;
}
void display_list(DLList lst, bool direction)
{
DLList ptr = lst ;
if(lst == NULL)
cout << "Empty list." << endl ;
if(direction)
{
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
}
else
{
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->prev ;
}
}
cout << endl ;
}
void display_list_in_reverse(DLList lst)
{
DLList ptr = lst ;
if(lst == NULL)
cout << "Empty list." << endl ;
while(ptr->next != NULL)
{
ptr = ptr->next ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->prev ;
}
cout << endl ;
}
DLList make_circule_the_list(DLList lst)
{
if(lst != NULL)
{
DLList ptr = lst ;
while(ptr->next != NULL)
ptr = ptr->next ;
ptr->next = lst ;
return lst ;
}
else
return NULL ;
}
DLList double_link_the_list(DLList lst)
{
if(lst != NULL)
{
DLList ptr = lst ;
while((ptr->next != NULL)&&(ptr->next != lst))
{
if(ptr->next->prev == NULL)
{
ptr->next->prev = ptr ;
}
ptr = ptr->next ;
}
if(ptr->next != NULL)
{
lst->prev = ptr ;
cout << "This is a circle linked list." << endl ;
}
return lst ;
}
else
return NULL ;
}
int main()
{
DLList lst = NULL ;
for(int i = 0 ; i < 4 ; i++)
{
lst = creat_simple_list(lst, i) ;
}
display_list(lst, true) ;
lst = make_circule_the_list(lst) ;
lst = double_link_the_list(lst) ;
system("pause");
display_list(lst, true) ;
//display_list_in_reverse(lst) ;
return 0 ;
}Exercice 3 : (Liste doublement chaînée)
Insérer et supprimer dans une liste doublement chaînée :
- Écrire un algorithme d’insertion dans une liste doublement chaînée.
- Écrire un algorithme de suppression dans une liste doublement chaînée.
Solution :
#include <iostream>
using namespace std ;
struct element
{
int data ;
struct element * next ;
struct element * prev ;
};
typedef struct element Element ;
typedef Element * DList ;
void display_list(DList lst)
{
DList ptr = lst ;
if(lst == NULL)
{
cout << "Empty list." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
bool node_exist(DList lst, DList pos)
{
DList ptr = lst ;
while(ptr != NULL)
{
if(ptr == pos)
return true ;
ptr = ptr->next ;
}
return false ;
}
DList insert_node(DList lst, int value, DList pos, bool &succ)
{
succ = true ;
if(!node_exist(lst, pos)&&(pos != NULL))
{
succ = false ;
return lst ;
}
DList ptr = new Element ; // creating the node
ptr->data = value ; // filling the node fields
ptr->prev = NULL ;
ptr->next = NULL ;
if(lst == NULL) // List empty, the node becomes the list
{
return ptr ;
}
else
{
if(pos == lst) // Insert in the first position
{
ptr->next = lst ;
lst->prev = ptr ;
lst = ptr ;
return lst ;
}
else
{
if((pos == NULL)||(pos->next == NULL)) // Insert in the last position
{
DList pLast = lst ;
while(pLast->next != NULL) // looking for the last node
{
pLast = pLast->next ;
}
pLast->next = ptr ; // connecting the last node to the new node
ptr->prev = pLast ; // connecting the new node to the lest node
return lst ;
}
else // Inserting the new node in the middle of the list
{
// connecting the node following the insertion position to the new node
pos->next->prev = ptr ;
// connecting the new node to the node following the insertion position
ptr->next = pos->next ;
// connecting the node of the insertion position to the new node
pos->next = ptr ;
// connecting the new node to the node of the insertion position
ptr->prev = pos ;
return lst ;
}
}
}
}
DList delete_node(DList lst, DList pos, bool &succ)
{
succ = true ;
if((lst == NULL)||!node_exist(lst, pos))
{
succ = false ;
return lst ;
}
if(pos->next != NULL)
pos->next->prev = pos->prev ;
if(pos->prev != NULL)
pos->prev->next = pos->next ;
else
lst = lst->next ;
delete pos ;
return lst ;
}
int main()
{
DList lst = NULL ;
bool test = false ;
// DList ptr = new Element ;
lst = insert_node(lst, 5, NULL, test) ;
cout << "insertion in an empty list ? : " << test << endl ;
display_list(lst) ;
lst = delete_node(lst, lst, test) ;
cout << "deletion of one element list ? : " << test << endl ;
display_list(lst) ;
cout << "made a small list by inserting in the beginning :" << endl ;
for(int i = 1 ; i <= 4 ; i++)
lst = insert_node(lst, i, lst, test) ;
display_list(lst) ;
// DList ptr = lst ;
// while(ptr->next != NULL)
// {
// ptr = ptr->next ;
// }
lst = insert_node(lst, 7, NULL, test) ;
cout << "insertion in the end of the list ? : " << test << endl ;
display_list(lst) ;
lst = insert_node(lst, 10, lst->next, test) ;
cout << "insertion in the middle of the list ? : " << test << endl ;
display_list(lst) ;
lst = delete_node(lst, lst, test) ;
cout << "deletion in the beginning of a list ? : " << test << endl ;
display_list(lst) ;
lst = delete_node(lst, lst->next, test) ;
cout << "deletion in the middle of a list ? : " << test << endl ;
display_list(lst) ;
lst = delete_node(lst, lst->next->next->next, test) ;
cout << "deletion in the end of a list ? : " << test << endl ;
display_list(lst) ;
return 0 ;
}Exercice 4 : (Liste de listes simplement chaînées)
Fonction de calcul de moyenne des étudiants :
Le département dans lequel vous êtes inscrit souhaite gérer les notes de ses étudiants. Les étudiants ont pour identifiant leur numéro d’étudiant. Ils ont un nom et un prénom. Ces informations sont stockées dans une liste chaînée dont chaque élément comporte aussi un champ moy pour la moyenne de l’étudiant et un champ eval qui est un pointeur sur sa liste de notes. La liste de notes de chaque étudiant est aussi une liste chaînée dont la tête est le champ eval de la cellule de l’étudiant. On dispose des déclarations suivantes :
Etudiant = Structure
No: Ch10
Nom: Ch30
Prenom: Ch30
moy: Nb
eval: Pn
suivatn: Pe
Note = Structure
note: Nb
coeff : Ent
suivant: Pn
Types :
Ch10 = Chaine de 10 caractères
Ch30 = Chaine de 30 caractères
Ent = entier
Nb = réel
Pe = *Etudiant
Pn = *Note
Questions:
Faire un schéma de cette structure.
On suppose que tous les champs de la liste des étudiants sont remplis sauf le champ moy. On suppose que toutes les notes des étudiants et tous les coefficients sont remplis.
Écrire une procédure moyennesEtudiants qui parcourt la liste des étudiants, et qui calcule et met à jour le champ moy de chaque étudiant à l’aide de la liste des notes sur laquelle pointe le champ eval. La procédure moyennesEtudiants prend en paramètre la tête de la liste des étudiants.
Solution :
#include <iostream>
#include <string.h>
using namespace std ;
struct student
{
char no[10] ;
char fname[30] ;
char lname[30] ;
double avge ;
struct grade * glst ;
struct student * next ;
};
typedef struct student Student ;
typedef Student * SList ;
struct grade
{
double mark ;
int coef ;
struct grade * next ;
};
typedef struct grade Grade ;
typedef Grade * GList ;
void average(SList lst)
{
SList pStd = lst ;
while(pStd != NULL)
{
GList pMrk = pStd->glst ;
double sum = 0.0 ;
int cnt = 0 ;
while(pMrk != NULL)
{
sum += (pMrk->mark * pMrk->coef) ;
cnt += pMrk->coef ;
pMrk = pMrk->next ;
}
pStd->avge = sum/cnt ;
cout << "The average marks of " << pStd->lname << " is : " << pStd->avge << endl ;
pStd = pStd->next ;
}
return ;
}
int main()
{
SList s1 = new Student ;
strcpy(s1->no, "123") ;
strcpy(s1->fname, "abdelaziz") ;
strcpy(s1->lname, "kara") ;
SList s2 = new Student ;
strcpy(s2->no, "456") ;
strcpy(s2->fname, "azouz") ;
strcpy(s2->lname, "chougui") ;
s1->next = s2 ;
s2->next = NULL ;
GList m1 = new Grade ;
m1->mark = 10.0 ;
m1->coef = 2 ;
GList m2 = new Grade ;
m2->mark = 15.0 ;
m2->coef = 3 ;
m1->next = m2 ;
m2->next = NULL ;
GList m3 = new Grade ;
m3->mark = 5.0 ;
m3->coef = 1 ;
GList m4 = new Grade ;
m4->mark = 18.0 ;
m4->coef = 4 ;
m3->next = m4 ;
m4->next = NULL ;
s1->glst = m1 ;
s2->glst = m3 ;
average(s1) ;
delete s1 ;
delete s2 ;
delete m1 ;
delete m2 ;
delete m3 ;
delete m4 ;
return 0 ;
}Exercice 5 : (Listes doublement chaînées circulaires)
Implémenter une liste doublement chaînée circulaire en c++. La liste doit permettre les opérations suivantes :
- Ajouter un élément à la fin de la liste.
- Supprimer un élément de la liste.
- Afficher tous les éléments de la liste.
- Rechercher un élément dans la liste.
Solution :
#include <iostream>
#include <string.h>
using namespace std ;
struct element
{
int data ;
struct element * next ;
struct element * prev ;
};
typedef struct element Element ;
typedef Element * DList ;
DList add_node(DList lst, int val)
{
DList elm = new Element ;
elm->data = val ;
if(lst == NULL)
{
elm->next = elm ;
elm->prev = elm ;
lst = elm ;
return lst ;
}
DList ptr = lst->prev ;
elm->next = lst ;
elm->prev = ptr ;
lst->prev = elm ;
ptr->next = elm ;
return lst ;
}
void display_list(DList lst)
{
if(lst == NULL)
{
cout << "Empty list." << endl ;
return ;
}
DList ptr = lst ;
do
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
while(ptr != lst);
cout << endl ;
return ;
}
DList search_node(DList lst, int val)
{
if(lst == NULL)
{
return NULL ;
}
DList ptr = lst ;
do
{
if(ptr->data == val)
{
return ptr ;
}
ptr = ptr->next ;
}
while(ptr != lst);
return NULL ;
}
DList delete_node(DList lst, int val)
{
DList pos = search_node(lst, val) ;
if(pos == NULL)
{
return lst ;
}
if((lst->next == lst)&&(lst->prev == lst))
{
lst = NULL ;
}
else
{
pos->next->prev = pos->prev ;
if(lst == pos)
lst = lst->next ;
pos->prev->next = pos->next ;
}
delete pos ;
return lst ;
}
int main()
{
DList lst = NULL ;
display_list(lst) ;
if(search_node(lst, 2) == NULL)
cout << "not found." << endl ;
else
cout << "error." << endl ;
lst = add_node(lst, 1) ;
display_list(lst) ;
lst = add_node(lst, 2) ;
display_list(lst) ;
lst = add_node(lst, 3) ;
display_list(lst) ;
lst = delete_node(lst, 2) ;
display_list(lst) ;
lst = delete_node(lst, 4) ;
display_list(lst) ;
lst = delete_node(lst, 1) ;
display_list(lst) ;
lst = delete_node(lst, 3) ;
display_list(lst) ;
return 0 ;
}