Corrige td 1 structures de donnees en langage c i133 mip s3
Télécharger PDFStructures de Données en Langage C : Corrigés de Travaux Dirigés
Ce document présente les corrigés de plusieurs travaux dirigés (TD) portant sur l'implémentation de structures de données fondamentales en langage C. Il couvre les listes chaînées simples et doublement chaînées, les piles et les files, ainsi que leurs applications concrètes.
TD N° 1 : Gestion de Livres via Listes Chaînées Simples
Ce premier TD explore la manipulation de listes chaînées simples pour gérer une collection de livres. Chaque livre est une structure composée d'un code, d'un titre, d'une spécialité, d'un auteur et d'informations d'édition (mois et année).
Définition des Structures
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;
La structure Edition contient le mois et l'année de publication. La structure Livre encapsule toutes les informations relatives à un ouvrage. Enfin, la structure Liste représente un nœud de la liste chaînée, contenant un livre et un pointeur vers l'élément suivant.
Fonction Lire_livre()
Livre Lire_livre() {
Livre A;
printf("Code : ");
scanf("%d", &A.code);
printf("Titre :");
scanf("%s", A.titre);
printf("Specialite : ");
scanf("%s", A.specialite);
printf("Auteur :");
scanf("%s", A.auteur);
printf("Edition (mois / année) : ");
scanf("%d %d", &A.edit.mois, &A.edit.année);
return A;
}
Cette fonction permet de saisir les informations d'un livre depuis l'entrée standard et de retourner une structure Livre remplie.
Fonction AllouerNoeud()
Liste * AllouerNoeud() {
Liste *L;
L = (Liste *)malloc(sizeof(Liste));
if (L == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
L->suivant = NULL;
return L;
}
}
Cette fonction alloue dynamiquement de l'espace mémoire pour un nouveau nœud de la liste et initialise son pointeur suivant à NULL. En cas d'échec d'allocation, le programme se termine.
Fonction inserer_debut()
Liste * inserer_debut(Liste *L, Livre nv) {
Liste *q;
q = AllouerNoeud();
q->Liv = nv;
if (L == NULL) L = q;
else {
q->suivant = L;
L = q;
}
return L;
}
Elle insère un nouveau livre (nv) au début de la liste chaînée L. Le nouveau nœud devient la nouvelle tête de la liste.
Fonction dernier()
Liste * dernier(Liste *L) {
Liste *q = L;
while (q->suivant != NULL) {
q = q->suivant;
}
return q;
}
Cette fonction parcourt la liste et retourne un pointeur vers le dernier élément de celle-ci.
Fonction inserer_fin()
Liste * inserer_fin(Liste *L, Livre nv) {
Liste *q, *d;
q = AllouerNoeud();
q->Liv = nv;
if (L == NULL) L = q;
else {
d = dernier(L);
d->suivant = q;
}
return L;
}
Permet d'insérer un nouveau livre (nv) à la fin de la liste. Si la liste est vide, le nouveau nœud devient la tête.
Fonction affichage()
void affichage(Liste *L) {
if (L == NULL) printf("Liste vide .\n");
else {
Liste *q = L;
printf("Affichage de la liste en avant :\n");
while (q) {
printf("%d\t %s\t %s\t %s\t edition %d\t %d\n", q->Liv.code, q->Liv.titre,
q->Liv.specialite, q->Liv.auteur, q->Liv.edit.mois, q->Liv.edit.année);
q = q->suivant;
}
}
}
Cette fonction affiche les détails de tous les livres présents dans la liste chaînée, du début à la fin.
Fonction supprimer()
Liste * supprimer(Liste * L, char * nom_auteur) {
Liste *courant, *elem_supp;
Liste *Pred = NULL; // Garder l’adresse de l’élément précédent, pendant le parcours
courant = L;
while (courant != NULL) {
if (strcmp(courant->Liv.auteur, nom_auteur) != 0) {
Pred = courant; // Mettre à jour le précédent seulement si l'élément n'est pas supprimé
courant = courant->suivant;
} else {
elem_supp = courant;
if (courant == L) { // Suppression au début
L = courant->suivant;
courant = L; // Le nouveau début est le courant
} else { // Suppression au milieu ou à la fin
Pred->suivant = courant->suivant;
courant = courant->suivant;
}
free(elem_supp);
}
}
return L;
}
Cette fonction supprime tous les livres dont l'auteur correspond au nom_auteur donné. Elle gère la suppression en début, milieu et fin de liste, en libérant la mémoire des nœuds supprimés.
Fonction comparer_edit()
int comparer_edit(Edition X, Edition Y) {
if (X.année < Y.année) return -1;
else {
if (X.année > Y.année) return 1;
else {
if (X.mois < Y.mois) return -1;
else if (X.mois > Y.mois) return 1;
else return 0;
}
}
}
Compare deux éditions (X et Y) en se basant d'abord sur l'année, puis sur le mois. Retourne -1 si X est antérieure, 1 si X est postérieure, et 0 si elles sont identiques.
Fonction Tri_liste()
Liste * Tri_liste(Liste * L) {
if (L != NULL) {
Liste *courant1, *courant2, *min;
Livre aux;
for (courant1 = L; courant1->suivant != NULL; courant1 = courant1->suivant) {
min = courant1;
for (courant2 = courant1->suivant; courant2 != NULL; courant2 = courant2->suivant) {
if (comparer_edit(min->Liv.edit, courant2->Liv.edit) == 1)
min = courant2;
}
if (min != courant1) {
aux = courant1->Liv;
courant1->Liv = min->Liv;
min->Liv = aux;
}
}
}
return L;
}
Cette fonction trie la liste chaînée des livres par ordre croissant des éditions (année puis mois), en utilisant un algorithme de tri par sélection.
Fonction diviser()
void diviser(Liste * L, Liste ** L1, Liste ** L2) {
if (L != NULL) {
Liste *courant = L;
while (courant != NULL) {
if (strcmp(courant->Liv.specialite, "mathematique") == 0) {
*L1 = inserer_debut(*L1, courant->Liv);
}
if (strcmp(courant->Liv.specialite, "physique") == 0) {
*L2 = inserer_debut(*L2, courant->Liv);
}
courant = courant->suivant;
}
}
}
Divise une liste de livres (L) en deux sous-listes (L1 pour les mathématiques, L2 pour la physique). Les livres sont insérés au début des nouvelles listes.
Fonction enregistrer()
void enregistrer(Liste *L, char * nom_fichier) {
FILE * F;
F = fopen(nom_fichier, "w");
Liste *q = L;
while (q != NULL) {
fprintf(F, "%d %s %s %s edition %d %d\n", q->Liv.code, q->Liv.titre,
q->Liv.specialite, q->Liv->auteur, q->Liv.edit.mois, q->Liv.edit.année);
q = q->suivant;
}
fclose(F);
}
Enregistre les informations de tous les livres de la liste dans un fichier texte spécifié.
Programme principal main()
Le programme principal offre un menu interactif permettant à l'utilisateur de manipuler la liste de livres : insérer au début ou à la fin, afficher, supprimer, diviser en sous-listes, trier, et enregistrer dans un fichier.
TD N° 2 : Manipulation de Polynômes avec Listes Doublement Chaînées
Ce TD se concentre sur l'implémentation de polynômes en utilisant des listes doublement chaînées. Chaque terme (monôme) d'un polynôme est représenté par un coefficient et un exposant.
Définition des Structures
typedef struct {
float coef;
int exp;
} Monome;
typedef struct element {
Monome M;
struct element *suivant;
struct element *precedent;
} Poly;
La structure Monome stocke le coefficient et l'exposant d'un terme. La structure Poly est un nœud de la liste doublement chaînée, contenant un monôme et des pointeurs vers les éléments suivant et précédent.
Fonction lire_monome()
Monome lire_monome() {
Monome A;
printf("Donner le coef ");
scanf("%f", &A.coef);
printf("Donner l exposant ");
scanf("%d", &A.exp);
return A;
}
Saisit le coefficient et l'exposant d'un monôme.
Fonction AllouerNoeud()
Poly * AllouerNoeud() {
Poly *q;
q = (Poly *)malloc(sizeof(Poly));
if (q == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
q->suivant = NULL;
q->precedent = NULL;
return q;
}
}
Alloue un nouveau nœud pour la liste de polynômes et initialise ses pointeurs suivant et precedent à NULL.
Fonction supprimer_monome_null()
Poly * supprimer_monome_null(Poly *P) {
Poly *elem_supp;
Poly *courant = P;
while (courant != NULL) {
if (courant->M.coef != 0) {
courant = courant->suivant;
} else {
elem_supp = courant;
if (courant == P) { // Suppression au début
if (courant->suivant != NULL) {
courant->suivant->precedent = NULL;
P = courant->suivant;
courant = P;
} else { // Si c'est le seul élément et qu'il est nul
free(elem_supp);
return NULL;
}
} else if (courant->suivant == NULL) { // Suppression à la fin
courant->precedent->suivant = NULL;
courant = courant->precedent;
} else { // Suppression au milieu
courant->precedent->suivant = courant->suivant;
courant->suivant->precedent = courant->precedent;
courant = courant->suivant;
}
free(elem_supp);
}
}
return P;
}
Supprime de la liste tous les monômes dont le coefficient est nul, afin de maintenir le polynôme sous une forme simplifiée. Gère les cas de suppression en début, fin ou milieu de liste.
Fonction ajouterMonome()
Poly * ajouterMonome(Poly * P, Monome m1) {
Poly *q;
q = AllouerNoeud();
q->M = m1;
if (P == NULL) return q;
else {
if (m1.exp > P->M.exp) { // Insertion au début (exposant plus grand)
q->suivant = P;
P->precedent = q;
P = q;
return P;
}
if (m1.exp == P->M.exp) { // Combinaison avec le premier monôme
P->M.coef += m1.coef;
P = supprimer_monome_null(P);
return P;
}
else { // Insertion ailleurs
Poly *courant = P;
while (courant->suivant != NULL && courant->suivant->M.exp > m1.exp)
courant = courant->suivant;
if (courant->suivant != NULL && courant->suivant->M.exp == m1.exp) { // Combinaison au milieu ou fin
courant->suivant->M.coef += m1.coef;
P = supprimer_monome_null(P);
} else {
if (courant->suivant == NULL) { // Insertion fin
q->precedent = courant;
courant->suivant = q;
} else { // Insertion milieu
q->suivant = courant->suivant;
q->precedent = courant;
courant->suivant->precedent = q;
courant->suivant = q;
}
}
return P;
}
}
}
Ajoute un monôme (m1) à un polynôme (P) en maintenant l'ordre décroissant des exposants. Elle gère la combinaison de monômes ayant le même exposant et la suppression des monômes dont le coefficient devient nul.
Fonction evaluer()
float evaluer(Poly * P, float x) {
Poly *courant = P;
float S = 0;
while (courant) {
S += (courant->M.coef) *pow(x, courant->M.exp);
courant = courant->suivant;
}
return S;
}
Évalue la valeur du polynôme pour une valeur donnée de x.
Fonction affichage_polynome()
void affichage_polynome(Poly * P) {
if (P == NULL) printf("vide .\n");
Poly *p = P;
while (p != NULL) {
if (p->M.exp > 1) {
printf("%.2fX^%d", p->M.coef, p->M.exp);
} else {
if (p->M.exp == 1)
printf("%.2fX", p->M.coef);
else
printf("%.2f", p->M.coef);
}
p = p->suivant;
if (p != NULL) printf(" + ");
}
printf("\n");
}
Affiche le polynôme sous une forme lisible, en respectant les conventions mathématiques (par exemple, X^1 affiché comme X, X^0 comme un simple nombre).
Fonction deriver_Polynome()
Poly * deriver_Polynome(Poly * P) {
Poly *courant = P;
Poly *derive = NULL;
Monome m;
while (courant != NULL) {
m.coef = (courant->M.coef) * (courant->M.exp);
m.exp = courant->M.exp - 1;
if (courant->M.exp != 0) { // La dérivée d'une constante est 0
derive = ajouterMonome(derive, m);
}
courant = courant->suivant;
}
return derive;
}
Calcule la dérivée d'un polynôme donné. Pour chaque monôme, le nouveau coefficient est l'ancien coefficient multiplié par l'exposant, et le nouvel exposant est l'ancien exposant moins un.
Fonction detruire_polynome()
Poly * detruire_polynome(Poly * P) {
Poly *elem_supp, *courant = P;
while (courant != NULL) {
elem_supp = courant;
courant = courant->suivant;
free(elem_supp);
}
return courant; // Retourne NULL
}
Libère toute la mémoire allouée pour les nœuds d'un polynôme, le détruisant ainsi complètement.
Programme principal main()
Le programme principal crée un polynôme, l'affiche, calcule sa dérivée, l'affiche, évalue le polynôme original pour une valeur donnée, puis détruit le polynôme.
TD N° 3 : Implémentation de Piles et Vérification de Palindromes
Ce TD illustre l'utilisation des piles (stacks) en langage C, avec une application concrète : la vérification si une chaîne de caractères est un palindrome.
Définition de la Structure TPile
#define MAX 10
typedef struct TPile {
char Elts[MAX];
int NbElts;
} TPile;
La structure TPile représente une pile statique (de taille fixe MAX). Elts est un tableau pour stocker les éléments, et NbElts indique le nombre d'éléments actuellement dans la pile.
Fonction initialiser()
void initialiser(TPile * pile) {
pile->NbElts = 0;
}
Initialise une pile en mettant son nombre d'éléments à zéro.
Fonction pilevide()
int pilevide(TPile pile) {
return pile.NbElts == 0;
}
Vérifie si la pile est vide. Retourne 1 (vrai) si elle est vide, 0 (faux) sinon.
Fonction pilepleine()
int pilepleine(TPile pile) {
return pile.NbElts == MAX;
}
Vérifie si la pile est pleine. Retourne 1 (vrai) si elle est pleine, 0 (faux) sinon.
Fonction empiler()
void empiler(TPile *pile, char obj) {
if (pilepleine(*pile)) {
fprintf(stderr, "Erreur, pile pleine \n");
} else {
pile->Elts[pile->NbElts] = obj;
pile->NbElts++;
}
}
Ajoute un élément (obj) au sommet de la pile (opération LIFO - Last In, First Out). Gère le cas où la pile est pleine.
Fonction depiler()
char depiler(TPile * pile) {
char obj = '\0'; // Initialisation pour éviter un avertissement si pile vide
if (pilevide(*pile)) {
fprintf(stderr, "Erreur, pile vide \n");
} else {
pile->NbElts--;
obj = pile->Elts[pile->NbElts];
}
return obj;
}
Retire et retourne l'élément au sommet de la pile. Gère le cas où la pile est vide.
Fonction afficher()
void afficher(TPile pile) {
int i;
if (pilevide(pile)) printf("La pile est vide \n");
else {
if (pilepleine(pile)) printf("La pile est pleine \n");
printf("NbElts = %d\n", pile.NbElts);
for (i = pile.NbElts - 1; i >= 0; i--) {
printf("pile[%d]=%c ", i, pile.Elts[i]);
}
printf("\n");
}
}
Affiche le contenu de la pile, du sommet vers la base.
Fonction palindrome()
void palindrome(TPile *P, char *ch) {
int i = 0;
int est_palindrome = 1;
char x;
// Empiler tous les caractères de la chaîne
while (ch[i] != '\0') {
empiler(P, ch[i]);
i++;
}
i = 0;
// Dépiler et comparer avec la chaîne originale
while (!pilevide(*P) && (est_palindrome == 1)) {
x = depiler(P);
if (x != ch[i]) est_palindrome = 0;
i++;
}
if (est_palindrome == 1) printf("%s est un palindrome \n", ch);
else printf("%s n'est pas un palindrome \n", ch);
}
Cette fonction utilise une pile pour déterminer si une chaîne de caractères est un palindrome. Elle empile tous les caractères de la chaîne, puis les dépile un par un en les comparant avec les caractères de la chaîne originale. Si la séquence est la même dans les deux sens, c'est un palindrome.
Programme principal main()
Le programme principal initialise une pile, demande à l'utilisateur de saisir une chaîne, puis utilise la fonction palindrome pour vérifier et afficher si la chaîne est un palindrome.
TD N° 4 : Implémentation de Files et Tri
Ce TD aborde les files (queues), une autre structure de données linéaire, et propose un algorithme de tri appliqué à une file.
Définition implicite de la Structure TFile
La structure TFile n'est pas explicitement fournie, mais son utilisation dans les fonctions suggère qu'elle contient les éléments de la file (Elts), l'indice du premier élément (id pour "head" ou "front"), et le nombre d'éléments (NbElts). La constante MAX est utilisée pour définir la taille maximale de la file circulaire.
#define MAX ... // Supposons une taille maximale, par exemple 10
typedef struct TFile {
int Elts[MAX]; // Tableau pour stocker les éléments
int id; // Indice du premier élément (tête de la file)
int NbElts; // Nombre actuel d'éléments dans la file
} TFile;
Fonction initialiser()
void initialiser(TFile * file) {
file->id = 0;
file->NbElts = 0;
}
Initialise une file en définissant l'indice de tête et le nombre d'éléments à zéro.
Fonction enfiler()
void enfiler(TFile *file, int obj) {
if (filepleine(*file)) {
fprintf(stderr, "Erreur, file pleine \n");
} else {
int indice;
indice = (file->id + file->NbElts) % MAX; // Calcul de l'indice circulaire pour l'insertion
file->Elts[indice] = obj;
file->NbElts++;
}
}
Ajoute un élément (obj) à la fin de la file (opération FIFO - First In, First Out). La gestion circulaire de la file est assurée par l'opérateur modulo.
Fonction defiler()
void defiler(TFile *file, int *obj) {
if (filevide(*file)) {
fprintf(stderr, "Erreur, file vide \n");
} else {
*obj = file->Elts[file->id]; // Récupérer l'élément en tête
file->id++; // Avancer l'indice de tête
if (file->id == MAX) file->id = 0; // Gérer le débordement circulaire
file->NbElts--;
}
}
Retire et retourne l'élément en tête de la file. Gère la file circulaire et le cas où la file est vide.
Fonction filevide()
int filevide(TFile file) {
return (file.NbElts == 0);
}
Vérifie si la file est vide. Retourne 1 (vrai) si elle est vide, 0 (faux) sinon.
Fonction filepleine()
int filepleine(TFile file) {
return file.NbElts == MAX;
}
Vérifie si la file est pleine. Retourne 1 (vrai) si elle est pleine, 0 (faux) sinon.
Fonction afficher()
void afficher(TFile file) {
int i, indice;
if (filevide(file)) printf("La file est vide \n");
else {
if (filepleine(file)) printf("La file est pleine \n");
printf("id = %d, NbElts = %d\n", file.id, file.NbElts);
for (i = 0; i < file.NbElts; i++) {
indice = (file.id + i) % MAX; // Calcul de l'indice réel dans le tableau circulaire
printf("file[%d]=%d ", i, file.Elts[indice]);
}
printf("\n");
}
}
Affiche le contenu de la file, du premier élément au dernier, en gérant la structure circulaire.
Fonction trier()
void trier(TFile *F1, TFile *F2) {
int min, m, t, s;
if (filevide(*F1)) printf("La file est vide \n");
else {
while (!filevide(*F1)) {
defiler(F1, &min); // On défile le premier élément comme minimum potentiel
if (!filevide(*F1)) {
t = 0;
m = F1->NbElts; // Nombre d'éléments restants à parcourir dans F1
while (t < m) {
defiler(F1, &s); // Défiler un élément pour le comparer
if (min >= s) { // Si l'élément actuel est plus petit ou égal au minimum trouvé
enfiler(F1, min); // L'ancien minimum retourne dans F1
min = s; // Le nouvel élément devient le minimum
} else {
enfiler(F1, s); // Sinon, l'élément retourne dans F1
}
t++;
}
}
enfiler(F2, min); // Le minimum actuel est enfilé dans F2 (la file triée)
}
}
}
Cette fonction implémente un tri par sélection pour une file. Elle déplace les éléments de F1 vers F2 en extrayant le minimum à chaque itération et en le plaçant dans F2. C'est un processus itératif qui reforme la file F1 pour trouver le prochain minimum, construisant ainsi F2 comme une file triée.
Programme principal main()
Le programme principal propose un menu interactif pour manipuler une file : initialiser, enfiler, défiler, afficher et trier. Il utilise deux files, file1 pour les opérations initiales et file2 pour stocker le résultat du tri.
FAQ sur les Structures de Données en C
Qu'est-ce qu'une structure de données et pourquoi est-elle importante en C ?
Une structure de données est une manière d'organiser les données dans un ordinateur pour qu'elles puissent être utilisées efficacement. En C, cela permet de créer des types de données complexes (comme un livre ou un polynôme) et de définir des relations entre elles (comme dans une liste chaînée), ce qui est essentiel pour gérer de grandes quantités de données et écrire des programmes performants et modulaires.
Quelle est la différence entre une pile (stack) et une file (queue) ?
La principale différence réside dans l'ordre d'accès aux éléments. Une pile fonctionne sur le principe "Dernier arrivé, premier sorti" (LIFO - Last In, First Out) : l'élément ajouté en dernier est le premier à être retiré. Une file fonctionne sur le principe "Premier arrivé, premier sorti" (FIFO - First In, First Out) : l'élément ajouté en premier est le premier à être retiré. On peut visualiser la pile comme une pile d'assiettes et la file comme une file d'attente à la caisse.
Quand faut-il utiliser une liste chaînée simple plutôt qu'une liste doublement chaînée ?
Une liste chaînée simple est suffisante lorsque les opérations ne nécessitent de parcourir la liste que dans un seul sens (par exemple, de la tête à la queue) et que les insertions/suppressions ne nécessitent pas un accès facile à l'élément précédent. Elle est plus économe en mémoire car chaque nœud ne stocke qu'un seul pointeur. Une liste doublement chaînée est préférable si des parcours bidirectionnels sont souvent nécessaires (avant et arrière) ou si les insertions/suppressions au milieu de la liste sont fréquentes et doivent être réalisées efficacement, car elle permet d'accéder directement au nœud précédent.