Examen module i133 liste doublement chainee mip s3 2021 2022
Télécharger PDFGestion de Produits avec une Liste Doublement Chaînée en C
Ce guide explore la gestion de produits pour un magasin en utilisant une liste doublement chaînée en langage C. Chaque produit est caractérisé par sa référence, sa description, son prix unitaire hors taxes et sa quantité en stock. La liste est contrôlée par un pointeur principal, où chaque nœud représente un produit.
Déclaration des Structures
Pour implémenter cette structure, nous définissons d'abord la structure Produit, puis la structure element qui constitue les nœuds de notre liste doublement chaînée, incluant des pointeurs vers l'élément suivant et précédent.
typedef struct {
int ref;
char description[20];
float prix_unitaireHT;
int quantite;
} Produit;
typedef struct element {
Produit Prd;
struct element * suivant;
struct element * precedent;
} Liste;
Fonctions Essentielles pour la Gestion de la Liste
Voici les fonctions clés nécessaires pour manipuler efficacement notre liste doublement chaînée de produits :
Allocation d'un Nouveau Nœud (AllouerNoeud)
Cette fonction est chargée d'allouer dynamiquement l'espace mémoire nécessaire pour un nouveau nœud de la liste. Elle retourne un pointeur de type Liste * vers le nœud alloué, prêt à contenir les informations d'un produit.
Liste * AllouerNoeud()Affichage Inversé de la Liste (affichageEnvers)
Cette fonction parcourt la liste doublement chaînée (par exemple, en remontant à partir du dernier élément si un pointeur de queue est disponible, ou de manière récursive) et affiche les détails de tous les produits dans l'ordre inverse de leur insertion ou de leur position normale.
void affichageEnvers(Liste * P)Ajout d'un Produit en Fin de Liste (ajouterProduitFin)
Cette fonction permet d'ajouter un nouveau produit à la fin de la liste. Si un produit avec la même référence existe déjà, la fonction mettra à jour sa quantité en stock en l'incrémentant, plutôt que d'ajouter un duplicata. Elle retourne un pointeur vers la nouvelle tête de la liste si elle a été modifiée.
Liste * ajouterProduitFin(Liste * P, Produit nv)Suppression des Produits Épuisés (supprimerProduitsEpuises)
Cette fonction identifie et supprime de la liste tous les produits dont la quantité en stock est nulle, aidant ainsi à maintenir la liste à jour et à n'afficher que les articles disponibles. Elle retourne un pointeur vers la nouvelle tête de la liste si elle a été modifiée.
Liste * supprimerProduitsEpuises(Liste * P)Calcul du Montant TTC d'un Produit (montantTTC)
Cette fonction prend en paramètre la référence d'un produit et retourne son montant total toutes taxes comprises (TTC) au format float. La TVA est fixée à 20%. Le calcul est le suivant : Montant TTC = Prix unitaire HT + (Prix unitaire HT × TVA).
float montantTTC(Liste * P, int ref1)Principes des Piles et des Files
Les piles (stacks) et les files (queues) sont des structures de données fondamentales en informatique, chacune avec ses propres règles d'accès aux éléments.
Fonctionnement des Files (Queues)
Une file fonctionne selon le principe du FIFO (First-In, First-Out), ce qui signifie que le premier élément inséré est aussi le premier à être retiré. Imaginez une file d'attente à la caisse : la première personne arrivée est la première servie.
Si les éléments 4, 3, 12, 7, 4 sont insérés dans une file dans cet ordre, ils en ressortiront dans le même ordre : 4, 3, 12, 7, 4.
Fonctionnement des Piles (Stacks) et Opération de Dépilement (Pop)
Une pile fonctionne selon le principe du LIFO (Last-In, First-Out), ce qui signifie que le dernier élément inséré est le premier à être retiré. Pensez à une pile d'assiettes : on prend toujours la dernière assiette posée sur le dessus.
L'opération de dépilement (pop) consiste à retirer l'élément situé au sommet de la pile.
Implémentations de la fonction pop
Voici différentes implémentations de la fonction pop pour une pile dynamique. L'objectif est de retirer le premier élément (le sommet) et de libérer sa mémoire.
// Implémentation 1 (Incorrecte)
Pile * pop_1 ( Pile * S) {
if (S == NULL) return S;
Pile *tmp;
tmp = S->suivant; // tmp pointe vers le deuxième élément
S = S->suivant; // S devient le deuxième élément
free(tmp); // Libère le deuxième élément, pas le premier (le sommet)
return S;
}
// Implémentation 2 (Correcte)
Pile * pop_2 ( Pile * S) {
if (S == NULL) return S;
Pile *tmp;
tmp = S; // tmp pointe vers l'élément au sommet (celui à dépiler)
S = S->suivant; // Le sommet de la pile avance au prochain élément
free(tmp); // Libère l'ancien sommet
return S;
}
// Implémentation 3 (Correcte, mais avec une gestion du cas NULL légèrement différente)
Pile * pop_3 ( Pile * S) {
Pile *tmp;
tmp = S; // tmp pointe vers l'élément au sommet
if (tmp == NULL) return tmp; // Gère le cas de pile vide
S = S->suivant; // Le sommet de la pile avance au prochain élément
free(tmp); // Libère l'ancien sommet
return S;
}
// Implémentation 4 (Incorrecte)
Pile * pop_4 ( Pile * S) {
if (S == NULL) return S;
Pile *tmp;
S = S->suivant; // S devient le deuxième élément
tmp = S; // tmp pointe vers le nouveau sommet (le deuxième élément)
free(tmp); // Libère le nouveau sommet, pas l'ancien
return S;
}
L'implémentation pop_2 est la plus correcte et idiomatique pour dépiler un élément d'une pile implémentée dynamiquement, car elle s'assure de libérer la mémoire de l'ancien sommet tout en déplaçant correctement le pointeur du sommet de la pile.
L'implémentation pop_3 est également correcte dans son fonctionnement final, bien que la vérification de NULL après l'assignation puisse être perçue comme moins directe que l'implémentation pop_2.
Questions Fréquemment Posées (FAQ)
Qu'est-ce qu'une liste doublement chaînée ?
Une liste doublement chaînée est une structure de données linéaire où chaque élément (nœud) contient non seulement les données, mais aussi deux pointeurs : un vers le nœud suivant dans la séquence et un autre vers le nœud précédent. Cela permet une traversée bidirectionnelle de la liste.
Quelle est la différence entre une pile et une file ?
La principale différence réside dans leur principe d'accès : une pile (stack) utilise le principe LIFO (Last-In, First-Out), où le dernier élément ajouté est le premier à être retiré. Une file (queue) utilise le principe FIFO (First-In, First-Out), où le premier élément ajouté est le premier à être retiré.
Pourquoi utiliser des pointeurs pour gérer des structures de données comme les listes et les piles ?
Les pointeurs permettent une gestion dynamique de la mémoire, ce qui est crucial pour des structures comme les listes et les piles dont la taille peut varier pendant l'exécution d'un programme. Ils évitent les contraintes de taille fixe des tableaux et permettent d'insérer ou de supprimer des éléments sans avoir à réorganiser l'intégralité de la structure en mémoire contiguë.