Td 1 structures de donnees c listes simplement chainees mip
Télécharger PDFStructures de Données en Langage C : Introduction aux Listes, Piles et Files
Ce guide explore les concepts fondamentaux des structures de données en langage C, notamment les listes simplement et doublement chaînées, les piles et les files. Nous détaillerons leur implémentation et les opérations courantes pour chaque type.
TD 1 : Listes Simplement Chaînées
Gestion d'une Bibliothèque avec une Liste Simplement Chaînée
L'objectif est de créer un programme en C permettant la gestion d'une bibliothèque. Cette bibliothèque contient un grand nombre de livres de différentes spécialités. Chaque livre est caractérisé par un code, un titre, une spécialité, un auteur et une édition. Nous gérerons cette bibliothèque à l'aide d'une liste simplement chaînée.
Déclarations des Structures
Les structures suivantes sont utilisées pour représenter l'édition, le livre et les éléments de la liste :
typedef struct {
int mois;
int année;
} Edition;
typedef struct {
int code;
char titre[30];
char specialite[30];
char auteur[30];
Edition edit;
} Livre;
typedef struct element {
Livre Liv;
struct element * suivant;
} Liste;Fonctions à Implémenter
Voici les fonctions essentielles pour la gestion de la liste de livres :
Livre LireLivre(): Lit et retourne un livre.Liste * AllouerNoeud(): Alloue de la mémoire pour un nouveau nœud de la liste.Liste * insererDebut(Liste * L, Livre nv): Insère un nouveau livre en début de liste.Liste * insererFin(Liste * L, Livre nv): Insère un nouveau livre en fin de liste.void afficherListe(Liste * L): Affiche tous les éléments de la liste, du premier au dernier.Liste * supprimer(Liste * L, char * nomAuteur): Supprime tous les livres d'un auteur donné.int comparerEdit(Edition X, Edition Y): Compare deux éditions et retourne :- -1 : si X est avant Y
- 0 : si X et Y sont identiques
- 1 : si X est après Y
Liste * trierListe(Liste * L): Retourne une liste contenant les livres classés par ordre croissant selon la date d'édition (utilisecomparerEdit).void diviser(Liste * L, Liste ** L1, Liste ** L2): Crée deux sous-ensembles de livres (deux listes), selon la spécialité (mathématique dans L1 et physique dans L2).- Donner un programme principal (
main) pour tester les différentes fonctions.
TD 2 : Listes Doublement Chaînées
Manipulation des Polynômes avec une Liste Doublement Chaînée
Ce TD propose la manipulation des polynômes à une variable par une liste chaînée. Un polynôme est représenté par une liste doublement chaînée, où chaque nœud correspond à un monôme. Un monôme est caractérisé par son coefficient (réel) et son exposant (entier). Seuls les monômes de coefficient non nul sont stockés en mémoire.
Exemple : Le polynôme P(x) = 15x6 + 7x4 + 5x2 + 3 peut être représenté par une liste doublement chaînée.
Déclaration des Structures
Les structures suivantes sont utilisées pour les monômes et les nœuds de la liste :
typedef struct {
float coef;
int exp;
} Monome;
typedef struct element {
Monome M;
struct element * suivant;
struct element * precedent;
} Poly;Fonctions à Implémenter
Voici les fonctions nécessaires à la manipulation des polynômes :
Monome lireMonome(): Crée et retourne un monôme dont le coefficient et l'exposant sont lus au clavier.Poly * AllouerNoeud(): Alloue de l'espace mémoire pour un nouveau nœud et retourne son adresse en cas de succès, NULL en cas d'échec.Poly * supprimerMonomeNul(Poly * P): Supprime les monômes dont le coefficient est nul.Poly * ajouterMonome(Poly * P, Monome nv): Insère un monôme à la position appropriée dans la liste, en respectant un ordre décroissant des exposants.float evaluer(Poly * P, float x): Évalue un polynôme pour une valeur réelle x. (Utiliser la fonctionpowdemath.h). Par exemple, pour x = 1, P(1) = 30.void affichagePolynome(Poly * P): Affiche un polynôme.Poly * derivePolynome(Poly * P): Calcule et retourne la dérivée d'un polynôme.Poly * detruirePolynome(Poly * P): Détruit un polynôme et libère la mémoire.- Donner un programme principal (
main) qui présente un menu de choix.
TD 3 : Piles (Implémentation Statique)
Gestion des Piles à l'aide de Tableaux
L'implémentation statique des piles utilise des tableaux. La capacité de la pile est alors limitée par la taille du tableau. L'ajout (empilement) se fait en incrémentant l'indice, et le retrait (dépilement) en le décrémentant. La structure de données pour gérer une telle pile est la suivante :
Déclaration de la Structure de Pile
#include <stdio.h>
#define MAX 10
typedef struct TPile {
char Elts[MAX];
int NbElts;
} TPile;Fonctions de Manipulation de Pile
Une implémentation complète des fonctions suivantes est requise :
void initialiser(TPile *pile): Initialise la pile.int pileVide(TPile pile): Teste si la pile est vide (retourne 1 si vide, 0 sinon).int pilePleine(TPile pile): Teste si la pile est pleine (retourne 1 si pleine, 0 sinon).void empiler(TPile *pile, char obj): Empile un élément dans la pile.void depiler(TPile *pile, char *obj): Dépile une valeur de la pile.void afficher(TPile pile): Affiche le contenu de la pile.
Vérification de Palindrome
Un palindrome est une chaîne de caractères qui se lit de la même manière de gauche à droite et de droite à gauche. Exemple : "AYA" est un palindrome, mais "MOHAMED" ne l'est pas.
- En utilisant une pile avec une implémentation statique, écrire une fonction qui permet de vérifier si une chaîne de caractères (un mot) est un palindrome.
- Donner un programme principal (
main) pour tester les différentes fonctions.
TD 4 : Files (Implémentation Statique)
Gestion des Files à l'aide d'un Tableau Circulaire
L'implémentation statique d'une file peut être réalisée par un tableau circulaire, où la tête et la queue sont toutes deux variables. Nous souhaitons implémenter une file à l'aide d'un tableau circulaire en utilisant la structure définie ci-après :
Déclaration de la Structure de File
#include <stdio.h>
#define MAX 10
typedef struct TFile {
int Elts[MAX];
int id; // Représente généralement l'indice de la tête (front)
int NbElts; // Représente le nombre d'éléments, permettant de déduire la queue (rear)
} TFile;Fonctions de Manipulation de File
- Écrire les fonctions suivantes :
void initialiser(TFile *file): Initialise la file.int fileVide(TFile file): Teste si la file est vide.int filePleine(TFile file): Teste si la file est pleine.void enfiler(TFile *file, int obj): Enfile un élément dans la file.void defiler(TFile *file, int *obj): Défile une valeur de la file.void afficher(TFile file): Affiche le contenu de la file.
Tri d'une File
On dispose d'une file d'entiers que l'on souhaite trier de manière à ce que le plus grand élément soit en fin de file. Seules les fonctions de manipulation de file implémentées ci-dessus et deux files sont autorisées.
- Donner un algorithme de tri qui utilise seulement les opérations ci-dessus et deux files. La file F1 contiendra les entiers à trier, et la file F2 contiendra les entiers triés après exécution. Le prototype de la fonction est :
void trier(TFile *F1, TFile *F2). - Donner un programme principal (
main) qui présente un menu de choix.
FAQ sur les Structures de Données en C
Qu'est-ce qu'une structure de données et pourquoi est-elle importante en programmation C ?
Une structure de données est une manière particulière d'organiser les données dans un ordinateur afin qu'elles puissent être utilisées efficacement. En C, cela permet de gérer des collections de données (comme des listes de livres ou des monômes de polynômes) de manière optimisée pour des opérations spécifiques comme l'ajout, la suppression, la recherche ou le tri. Elles sont cruciales pour écrire des programmes performants et maintenables.
Quelle est la différence principale entre une liste simplement chaînée et une liste doublement chaînée ?
Dans une liste simplement chaînée, chaque nœud contient une donnée et un pointeur vers le nœud suivant, permettant un parcours unidirectionnel. En revanche, une liste doublement chaînée contient en plus un pointeur vers le nœud précédent, ce qui permet un parcours bidirectionnel (avant et arrière). Les listes doublement chaînées offrent plus de flexibilité pour la suppression ou l'insertion mais consomment plus de mémoire par nœud.
Quels sont les avantages et les inconvénients des implémentations statiques par rapport aux implémentations dynamiques pour les piles et les files ?
Les implémentations statiques (utilisant des tableaux de taille fixe) sont simples à gérer et offrent un accès rapide aux éléments. Cependant, leur taille est limitée et ne peut pas être modifiée pendant l'exécution, ce qui peut entraîner des problèmes de débordement si la capacité maximale est atteinte. Les implémentations dynamiques (utilisant des listes chaînées) peuvent s'étendre ou se réduire selon les besoins, évitant les limites de taille, mais elles peuvent être plus complexes à gérer et potentiellement plus lentes en raison des allocations de mémoire et de l'accès aux pointeurs.