Td structures données avec c -Structures des données avec
Télécharger PDFIntroduction aux Structures de Données et Algorithmes en C
Ce document explore la mise en œuvre de diverses structures de données en langage C, notamment les listes simplement chaînées pour manipuler des nombres rationnels et les listes doublement chaînées pour gérer des enregistrements d'étudiants. Nous aborderons les fonctions essentielles pour créer, manipuler, afficher et trier ces listes, en mettant l'accent sur les concepts fondamentaux de la programmation structurée.
Partie 1 : Manipulation de Nombres Rationnels avec des Listes Simplement Chaînées
Définition des structures
Pour représenter un nombre rationnel (une fraction), une structure nommée rationnel est utilisée. Elle contient deux membres : un entier pour le numérateur (num) et un entier pour le dénominateur (den).
Les nombres rationnels sont ensuite organisés dans une liste simplement chaînée. Chaque nœud de cette liste, défini par la structure LSC, contient une variable de type rationnel et un pointeur (suivant) vers le nœud subséquent dans la séquence.
Allocation et Insertion de Nœuds
La fonction allouerNoeud est chargée de créer dynamiquement un nouveau nœud de type LSC en mémoire. Elle vérifie si l'allocation a réussi et initialise le pointeur suivant du nouveau nœud à NULL.
La fonction inserer_tete permet d'ajouter un nouveau nombre rationnel au début de la liste simplement chaînée. Si la liste est initialement vide, le nouveau nœud devient la tête. Sinon, le nouveau nœud est lié à l'ancienne tête, et il devient la nouvelle tête de la liste.
Saisie des Nombres Rationnels
La fonction Lire_rationnel interagit avec l'utilisateur pour obtenir le numérateur et le dénominateur d'un nombre rationnel. Une validation est intégrée pour s'assurer que le dénominateur saisi n'est pas zéro, demandant à nouveau la saisie si nécessaire.
Simplification des Fractions
Pour garantir que les fractions sont toujours présentées dans leur forme la plus réduite, des fonctions de simplification sont mises en œuvre :
Calcul du Plus Grand Commun Diviseur (PGCD)
La fonction pgcd calcule le plus grand commun diviseur entre deux entiers en utilisant l'algorithme d'Euclide. Cette fonction est fondamentale pour la simplification des fractions.
Application de la Simplification
La fonction simplifier reçoit un pointeur vers un objet rationnel. Elle utilise la fonction pgcd pour trouver le PGCD du numérateur et du dénominateur, puis divise ces deux composants par le PGCD afin de réduire la fraction à sa forme irréductible.
Affichage de la Liste des Rationnels
La fonction afficher parcourt tous les éléments de la liste simplement chaînée. Pour chaque nombre rationnel, elle assure d'abord sa simplification puis l'affiche. Si le dénominateur est 1, elle affiche uniquement le numérateur (l'entier) ; sinon, elle présente le nombre sous sa forme fractionnaire num/den.
Création de la Liste de Rationnels
La fonction CREER_LSC permet de construire la liste simplement chaînée des nombres rationnels. Elle sollicite la saisie de rationnels par l'utilisateur et les insère séquentiellement en tête de liste, continuant jusqu'à ce que l'utilisateur choisisse d'arrêter.
Opérations sur les Rationnels de la Liste
Calcul de la Somme
La fonction somme parcourt la liste et additionne tous les nombres rationnels qu'elle contient. Elle gère l'addition des fractions en les convertissant à un dénominateur commun avant d'effectuer la somme des numérateurs, puis elle simplifie le résultat final.
Calcul du Produit
La fonction multiplication calcule le produit de tous les nombres rationnels de la liste. Elle multiplie collectivement tous les numérateurs et tous les dénominateurs, puis simplifie la fraction résultante.
Partie 2 : Gestion d'Étudiants avec des Listes Doublement Chaînées
Définition des structures
Pour gérer les données des étudiants, une structure ETD est définie. Elle comprend les champs suivants : un code (entier), un sexe (caractère 'f' pour femme ou 'g' pour garçon), un nom (chaîne de caractères de 15 maximum), un prenom (chaîne de caractères de 30 maximum) et une moyenne (nombre flottant).
Chaque enregistrement d'étudiant est stocké dans un nœud d'une liste doublement chaînée, représenté par la structure LDC. Chaque nœud LDC contient une structure ETD ainsi que deux pointeurs : suivant vers le nœud postérieur et pred vers le nœud antérieur, permettant une navigation bidirectionnelle.
Saisie des Données Étudiant
La fonction lire_etudiant est conçue pour collecter les informations d'un étudiant. Elle intègre des mécanismes de validation pour chaque champ : le code doit être positif, le sexe doit être 'f' ou 'g', la longueur du nom et du prénom ne doit pas dépasser les limites spécifiées, et la moyenne doit être comprise entre 0 et 20.
Insertion dans la Liste Doublement Chaînée
Deux fonctions sont disponibles pour ajouter des étudiants à la liste doublement chaînée :
inserer_debut: Permet d'ajouter un nouvel étudiant au commencement de la liste, ajustant les pointeurs de manière appropriée.inserer_fin: Permet d'ajouter un nouvel étudiant à la fin de la liste, en parcourant la liste pour trouver le dernier nœud et en y attachant le nouveau.
Création de la Liste d'Étudiants
Différentes méthodes de création de la liste sont proposées :
CREER_LDC: Cette fonction crée une liste en insérant tous les nouveaux étudiants systématiquement au début de la liste.CREER_LDC_Choix: Cette version offre plus de flexibilité à l'utilisateur, lui permettant de choisir pour chaque nouvel étudiant s'il souhaite l'insérer au début ou à la fin de la liste.
Tri de la Liste d'Étudiants
La fonction trier_Liste implémente un algorithme de tri par comparaison (similaire à un tri à bulles) pour organiser les étudiants de la liste par ordre croissant de leur moyenne.
Affichage de la Liste d'Étudiants
La fonction afficher_LDC parcourt l'intégralité de la liste doublement chaînée et affiche les détails de chaque étudiant (code, nom, prénom, moyenne, sexe) sous une forme tabulaire pour une meilleure lisibilité.
Division de la Liste
La fonction diviser_liste est conçue pour scinder une liste d'étudiants existante en deux sous-listes distinctes :
L1: Contient tous les étudiants ayant obtenu une moyenne supérieure ou égale à 10. Ces étudiants sont insérés au début de la listeL1.L2: Contient tous les étudiants dont la moyenne est strictement inférieure à 10. Ces étudiants sont insérés à la fin de la listeL2.
FAQ - Questions Fréquentes
Qu'est-ce qu'une liste simplement chaînée ?
Une liste simplement chaînée est une structure de données linéaire où chaque élément, appelé nœud, contient deux parties : les données qu'il stocke et un pointeur qui référence l'adresse du nœud suivant dans la séquence. Le dernier nœud de la liste pointe vers une valeur nulle (NULL) pour marquer la fin de la chaîne.
Quelle est la différence entre une liste simplement chaînée et une liste doublement chaînée ?
La différence fondamentale réside dans la capacité de navigation. Une liste simplement chaînée permet de parcourir les éléments uniquement dans un sens (du début à la fin) grâce à un pointeur "suivant". En revanche, une liste doublement chaînée ajoute un pointeur "précédent" à chaque nœud, permettant de traverser la liste dans les deux sens (avant et arrière).
Pourquoi est-il important de simplifier les fractions dans les opérations sur les nombres rationnels ?
La simplification des fractions est essentielle pour maintenir l'exactitude des calculs, éviter l'accumulation de très grands nombres au numérateur et au dénominateur (ce qui peut conduire à des erreurs de débordement), et rendre les résultats finaux plus clairs, plus lisibles et plus gérables. Elle assure que chaque rationnel est représenté dans sa forme la plus simple.