Solution tp 1 et tp 2 structures de donnees en c lsc et ldc
Télécharger PDFSolutions de Travaux Pratiques en Structures de Données avec le Langage C
Ce document présente les solutions détaillées des Travaux Pratiques (TP) du module I133 sur les structures de données en Langage C, tels qu'élaborés pour l'année universitaire 2021/2022 dans le parcours MIP (S3) par le Pr. B. HSSINA. Il couvre les listes chaînées (simplement et doublement), les piles et les files.
TP 1 et 2 : Listes Chaînées (Listes Simplement Chaînées et Listes Doublement Chaînées)
Partie 1 : Listes Simplement Chaînées (LSC)
Cette section aborde les opérations fondamentales sur les listes simplement chaînées.
Q1 : Fonction d'Allocation de Nœud
Cette fonction alloue dynamiquement de la mémoire pour un nouveau nœud (cellule) et l'initialise. Elle vérifie également si l'allocation a réussi, signalant une erreur si la mémoire est insuffisante.
cellule * AllouerNoeud ()
{
cellule * l;
l = (cellule *) malloc(sizeof(cellule));
if (l == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
l->suivant = NULL;
return l;
}
}Q2 : Insertion en Tête de Liste
La fonction inserer_tete ajoute un nouvel élément au début de la liste simplement chaînée, mettant à jour le pointeur vers la tête de la liste.
cellule * inserer_tete (int v, cellule *l)
{
cellule *q;
q = AllouerNoeud();
q->valeur = v;
if (l == NULL) l = q;
else {
q->suivant = l;
l = q;
}
return l;
}Q3 : Insertion en Queue de Liste
Ces fonctions permettent de trouver le dernier élément de la liste et d'insérer un nouveau nœud à la fin.
Fonction auxiliaire pour trouver le dernier nœud
cellule * dernier (cellule *l)
{
cellule *q = l;
while (q->suivant != NULL)
{
q = q->suivant;
}
return q;
}Fonction d'insertion en queue
cellule * inserer_fin (int v, cellule *l)
{
cellule *q, *d;
q = AllouerNoeud();
q->valeur = v;
if (l == NULL) l = q;
else {
d = dernier(l);
d->suivant = q;
}
return l;
}Q4 : Somme des Éléments de la Liste
Cette fonction calcule la somme de toutes les valeurs stockées dans les nœuds de la liste en la parcourant du début à la fin.
int somme (cellule *l)
{
int S = 0;
cellule *q = l;
while (q != NULL) {
S += q->valeur;
q = q->suivant;
}
return S;
}Q5 : Suppression des Éléments Négatifs
La fonction supprimer parcourt la liste et supprime tous les nœuds dont la valeur est négative. Elle gère la mise à jour des pointeurs pour maintenir l'intégrité de la liste.
cellule * supprimer (cellule *l)
{
cellule * elem_supp; // pour récupérer l’adresse de l’élément à supprimer
cellule * courant = l; // parcourir la liste
cellule * Pred; // Garder l’adresse de l'élément précédent, pendant le parcours
while (courant != NULL)
{
if (courant->valeur >= 0) {
Pred = courant;
courant = courant->suivant;
}
else {
elem_supp = courant;
if (courant == l) {
l = courant->suivant;
courant = l;
}
else {
Pred->suivant = courant->suivant;
courant = courant->suivant;
}
free(elem_supp);
}
}
return l;
}Q6 : Affichage Récursif de la Liste à l'Envers
Cette fonction affiche les éléments de la liste dans l'ordre inverse en utilisant une approche récursive. Elle parcourt la liste jusqu'à la fin, puis affiche les éléments au fur et à mesure que les appels récursifs se terminent.
void affichage (cellule *l)
{
if (l->suivant != NULL) affichage(l->suivant);
printf("%d \t",l->valeur);
}Q7 : Enregistrement de la Liste dans un Fichier Texte
La fonction enregistrer écrit les valeurs des nœuds de la liste dans un fichier texte spécifié. Elle ouvre le fichier en mode écriture, y inscrit les données, puis le ferme.
void enregistrer (cellule *l, char * nom_fichier)
{
FILE * F;
F = fopen(nom_fichier,"w");
cellule *q = l;
while (q != NULL)
{
fprintf(F,"%d\t",q->valeur);
q = q->suivant;
}
fclose(F);
}Q8 : Programme Principal (Main) pour LSC
Le programme principal offre un menu interactif pour manipuler une liste simplement chaînée. Il permet d'insérer des éléments en tête ou en fin, de calculer la somme, de supprimer des éléments négatifs, d'afficher la liste à l'envers et d'enregistrer les données dans un fichier.
main ()
{
cellule *l = NULL;
char nom_fichier[10];
int val;
int choix;
do {
fflush(stdin); // Vide le tampon clavier (comportement non standard et déconseillé)
printf("Saisir votre choix :\n");
printf("1: pour insérer en tête.\n");
printf("2: pour insérer à la fin.\n");
printf("3: La somme des éléments de la liste.\n");
printf("4: Suppression des éléments négatifs.\n");
printf("5: Affichage de la liste à l'envers.\n");
printf("6: Enregistrement dans un fichier texte.\n");
printf("7: Pour arrêter.\n");
scanf("%d",&choix);
switch (choix)
{
case 1 : printf("Donner un entier : "); scanf("%d",&val); l = inserer_tete(val,l); break;
case 2 : printf("Donner un entier : "); scanf("%d",&val); l = inserer_fin(val,l); break;
case 3 : printf("La somme des éléments de la liste est : %d.\n",somme(l)); break;
case 4 : printf("Suppression des éléments négatifs.\n"); l = supprimer(l); break;
case 5 : printf("Affichage de la liste à l'envers : \n");
if (l == NULL) printf("Liste vide \n"); else affichage(l); printf(" \n"); break;
case 6 : printf("Enregistrement dans un fichier.\n");
printf("Donner le nom de fichier : ");
scanf("%s", nom_fichier); enregistrer(l, nom_fichier); break;
case 9 : printf("Fin du programme.\n"); break;
default : printf("Choix invalide \n");
}
} while (choix != 9);
return 0;
}Partie 2 : Listes Doublement Chaînées (LDC)
Cette section présente l'implémentation des listes doublement chaînées, qui, en ajoutant un pointeur vers le nœud précédent, permettent une navigation bidirectionnelle.
Définition de la Structure de Nœud
La structure maillon (ou LDC) est étendue pour inclure des pointeurs vers le nœud suivant et le nœud précédent, facilitant les parcours dans les deux sens.
typedef struct maillon {
int valeur;
struct maillon * suivant;
struct maillon * precedent;
}LDC;Q1 : Fonction d'Allocation de Nœud (LDC)
Similaire à la LSC, cette fonction alloue un nouveau nœud mais initialise également le pointeur precedent à NULL, en plus du pointeur suivant.
cellule * AllouerNoeud ()
{
cellule * l;
l = (cellule *) malloc(sizeof(cellule));
if (l == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
l->suivant = NULL;
l->precedent = NULL;
return l;
}
}Q2 : Insertion en Tête de Liste (LDC)
L'insertion en tête dans une LDC met à jour les pointeurs suivant du nouveau nœud vers l'ancien début, et precedent de l'ancien début vers le nouveau nœud.
cellule * inserer_tete (int v, cellule *l)
{
cellule *q;
q = AllouerNoeud();
q->valeur = v;
if (l == NULL) l = q;
else {
q->suivant = l;
l->precedent = q;
l = q;
}
return l;
}Q3 : Insertion en Queue de Liste (LDC)
La fonction dernier est identique à celle des LSC. L'insertion en queue pour les LDC met à jour le pointeur suivant du dernier nœud existant vers le nouveau nœud, et le pointeur precedent du nouveau nœud vers le dernier nœud existant.
Fonction auxiliaire pour trouver le dernier nœud
cellule * dernier (cellule *l)
{
cellule *q = l;
while (q->suivant != NULL)
{
q = q->suivant;
}
return q;
}Fonction d'insertion en queue
cellule * inserer_fin (int v, cellule *l)
{
cellule *q, *d;
q = AllouerNoeud();
q->valeur = v;
if (l == NULL) l = q;
else {
d = dernier(l);
d->suivant = q;
q->precedent = d;
}
return l;
}Q5 : Suppression des Éléments Négatifs (LDC)
La suppression dans une liste doublement chaînée est plus complexe que pour une LSC, car elle doit gérer à la fois les pointeurs suivant et precedent des nœuds adjacents à l'élément supprimé. La fonction gère les cas spécifiques de suppression au début, à la fin et au milieu de la liste.
cellule * supprimer (cellule *L)
{
cellule * elem_supp; // pour récupérer l’adresse de l’élément à supprimer
cellule * courant = L; // parcourir la liste
while (courant != NULL)
{
if (courant->valeur >= 0) {
courant = courant->suivant;
}
else {
elem_supp = courant;
// suppression au début
if (courant == L) {
if (courant->suivant != NULL)
{
courant->suivant->precedent = NULL;
L = courant->suivant;
courant = L;
} else {
free(elem_supp);
return NULL;
}
}
else if (courant->suivant == NULL) // suppression à la fin
{
courant->precedent->suivant = NULL;
courant = courant->precedent;
}
// suppression à une position quelconque
else {
courant->precedent->suivant = courant->suivant;
courant->suivant->precedent = courant->precedent;
courant = courant->suivant;
}
free(elem_supp);
}
}
return L;
}Q6 : Affichage de la Liste à l'Envers (LDC)
Grâce aux pointeurs precedent, l'affichage inversé d'une liste doublement chaînée peut être réalisé de manière itérative en partant du dernier nœud et en remontant la liste.
void affichage (cellule *l)
{
cellule *d, * courant;
d = dernier(l);
courant = d;
while (courant != NULL)
{
printf("%d \t",l->valeur);
courant = courant->precedent;
}
}Note : Dans l'implémentation fournie, la ligne printf("%d \t",l->valeur); devrait probablement être printf("%d \t",courant->valeur); pour afficher l'élément courant pendant le parcours.
Q8 : Programme Principal (Main) pour LDC
Ce programme principal permet de tester les fonctionnalités de base d'une liste doublement chaînée via un menu interactif, incluant l'insertion, la suppression d'éléments négatifs et l'affichage inversé.
main ()
{
cellule *l = NULL;
int val;
int choix;
do {
fflush(stdin); // Vide le tampon clavier (comportement non standard et déconseillé)
printf("Saisir votre choix :\n");
printf("1: pour insérer en tête.\n");
printf("2: pour insérer à la fin.\n");
printf("5: Suppression des éléments négatifs.\n");
printf("6: Affichage de la liste à l'envers.\n");
printf("7: Pour arrêter.\n");
scanf("%d",&choix);
switch (choix)
{
case 1 : printf("Donner un entier : "); scanf("%d",&val); l = inserer_tete(val,l); break;
case 2 : printf("Donner un entier : "); scanf("%d",&val); l = inserer_fin(val,l); break;
case 5 : printf("Suppression des éléments négatifs.\n"); l = supprimer(l); break;
case 6 : printf("Affichage de la liste à l'envers : \n");
if (l == NULL) printf("Liste vide \n"); else affichage(l); printf(" \n"); break;
case 9 : printf("Fin du programme.\n"); break;
default : printf("Choix invalide \n");
}
} while (choix != 9);
return 0;
}TP 3 : Piles (Implémentation Dynamique)
Ce TP explore l'implémentation dynamique des piles (structures LIFO - Last-In, First-Out) et leur application à l'analyse de la structure de parenthèses dans des expressions mathématiques.
Q1 : Implémentation des Fonctions de Pile
Cette section définit la structure d'une pile basée sur une liste chaînée et implémente les opérations courantes : AllouerNoeud (allocation d'un nœud), initialiser (création d'une pile vide), pile_vide (vérification de l'état de la pile), empiler (ajout d'un élément au sommet), depiler (retrait de l'élément au sommet), peek (consultation de l'élément au sommet) et affichage (affichage des éléments de la pile).
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
typedef struct cellule {
char d; // Le délimiteur ouvrant.
struct cellule * suivant;
} Pile;
Pile * AllouerNoeud ()
{
Pile * l;
l = (Pile *) malloc(sizeof(Pile));
if (l == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
l->suivant = NULL;
return l;
}
}
Pile * initialiser (Pile *P)
{
P = NULL; return P;
}
int pile_vide (Pile * P)
{
return (P == NULL);
}
Pile * empiler (Pile *P, char e)
{
Pile *q;
q = AllouerNoeud();
q->d = e;
q->suivant = P;
P = q;
return P;
}
Pile * depiler (Pile *P)
{
if (pile_vide(P)) printf("Pile vide.\n");
else {
Pile * elem_supp;
elem_supp = P;
P = P->suivant;
free(elem_supp);
}
return P;
}
char peek (Pile * P)
{
return P->d;
}
void affichage (Pile *P)
{
printf("Affichage des éléments de la pile :\n");
if (pile_vide(P)) printf("Pile vide.\n");
else {
Pile * courant = P;
while (courant)
{
printf("%c\t",courant->d);
courant = courant->suivant;
}
printf("\n");
}
}Q2 : Fonction d'Analyse d'Expression Mathématique
Cette fonction Analyser_exp utilise une pile pour vérifier la bonne imbrication et le balancement des délimiteurs (parenthèses, crochets, accolades) dans une expression mathématique. Elle garantit que chaque délimiteur ouvrant a un correspondant fermant correct et que l'ordre est respecté.
// Fonction auxiliaire
char ouvrant (char symb)
{
switch (symb)
{
case ']': return '['; break;
case ')': return '('; break;
case '}': return '{'; break;
}
}
int Analyser_exp (char exp [] , Pile *P1)
{
int i, Valide;
char symbole, S;
Valide = 1; // variable utilisée comme un témoin
i = 0;
while ((exp[i] != '\0') && (Valide == 1)) {
symbole = exp[i];
if ((symbole == '[') || (symbole == '(') || (symbole == '{')) {
P1 = empiler(P1, symbole);
}
if ((symbole == ']') || (symbole == ')') || (symbole == '}'))
{
if (pile_vide(P1)) Valide = 0;
else {
S = peek(P1);
P1 = depiler(P1);
if (S != ouvrant(symbole)) Valide = 0;
}
};
i++;
} /* fin de la boucle while */
if ((pile_vide(P1)) && (Valide == 1)) return 1;
else return 0;
}Programme Principal (Main) pour TP3
Le programme principal permet à l'utilisateur d'entrer une expression mathématique. Il initialise une pile et utilise la fonction Analyser_exp pour déterminer si les délimiteurs de l'expression sont correctement balancés.
main ()
{
char expression[20];
Pile *P1;
P1 = initialiser(P1);
printf("Entrer une expression mathématique ");
gets(expression); // Attention : gets() est une fonction dangereuse, vulnérable aux dépassements de tampon.
if (Analyser_exp(expression,P1)) printf("Expression correcte \n");
else printf("Expression incorrecte \n");
system("pause"); // Commande spécifique à certains systèmes d'exploitation (ex: Windows), utilisée pour maintenir la fenêtre console ouverte.
}TP 4 : Files (Implémentation Dynamique)
Ce TP se concentre sur l'implémentation dynamique des files (structures FIFO - First-In, First-Out), en particulier pour gérer des "Personnes" avec des priorités et pour trier la file selon ces priorités.
Q1 : Implémentation des Fonctions de File
Cette section définit les structures nécessaires pour une file de personnes (avec nom et priorité) et implémente les opérations de base : AllouerNoeudF (allocation d'un nœud d'élément de file), AllouerF (allocation de la structure de file elle-même), initialiser (création d'une file vide), file_vide (vérification de l'état de la file), enfiler (ajout d'un élément à la fin), defiler (retrait de l'élément du début), peek (consultation du premier élément) et afficher (affichage de tous les éléments de la file).
# include <stdio.h>
# include <stdlib.h>
typedef struct {
int priorite; // La priorité de la personne de type entier.
char nom[10]; // Son nom de type chaîne de caractères.
} Personne;
typedef struct cellule {
Personne pers;
struct cellule * suivant;
} Element;
typedef struct {
Element * Debut; // Pointeur vers le premier élément
Element * Fin; // Pointeur vers le dernier élément
int taille; // La taille de la file
} File;
Element * AllouerNoeudF ()
{
Element * Q;
Q = (Element *) malloc(sizeof(Element));
if (Q == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
Q->suivant = NULL;
return Q;
}
}
File * AllouerF ()
{
File * AF;
AF = (File *) malloc(sizeof(File));
if (AF == NULL) {
printf("Mémoire insuffisante \n");
exit(-1);
} else {
AF->Debut = NULL;
AF->Fin = NULL;
AF->taille = 0;
return AF;
}
}
File * initialiser (File *F)
{
F->Debut = NULL;
F->Fin = NULL;
F->taille = 0;
return F;
}
int file_vide (File * F)
{
return ((F->Debut == NULL) && (F->Fin == NULL));
}
File * enfiler (File *F, Personne e)
{
Element *q;
q = AllouerNoeudF();
q->pers = e;
if (F->Fin == NULL) {
F->Fin = q;
F->Debut = q;
}
else {
F->Fin->suivant = q;
F->Fin = q;
}
F->taille ++;
return F;
}
File * defiler (File * F) {
if (file_vide(F)) printf("File vide.\n");
else {
Element * elem_supp;
elem_supp = F->Debut;
if (F->taille == 1) {
F->Debut = NULL;
F->Fin = NULL;
}
else F->Debut = F->Debut->suivant;
free(elem_supp);
F->taille --;
return F;
}
}
Personne peek (File * F)
{
return F->Debut->pers;
}
void afficher (File *F)
{
printf("Affichage de la file :\n");
if (file_vide(F)) printf("File vide.\n");
else {
Element * courant = F->Debut;
int i;
for (i = 1; i <= (F->taille); i++)
{
printf("Personne (%s, %d)\t",courant->pers.nom , courant->pers.priorite);
courant = courant->suivant;
}
}
printf("\n");
}Q2 : Fonction de Tri d'une File
Cette fonction trier_file réorganise les éléments d'une file en fonction de leur priorité, en créant une nouvelle file triée. L'algorithme se comporte comme un tri par sélection : il trouve l'élément avec la plus petite priorité dans la file source à chaque itération et le transfère dans la nouvelle file triée.
File * trier_file (File *F1) {
int min, m, t, s;
Personne p1, p2;
File *F2;
F2 = AllouerF();
F2 = initialiser(F2);
if (file_vide(F1)) printf("La file est vide \n");
else
while (! file_vide(F1)) {
p1 = peek(F1);
F1 = defiler(F1);
if (! file_vide(F1)) {
t = 0; m = F1->taille;
while (t < m) {
p2 = peek(F1);
F1 = defiler(F1);
if (p1.priorite >= p2.priorite) {
enfiler(F1 , p1);
p1 = p2;
}
else enfiler(F1 ,p2);
t ++;
}
}
enfiler(F2 ,p1);
}
return F2;
}Q3 : Programme Principal (Main) pour TP4
Le programme principal fournit un menu interactif pour gérer une file de personnes, incluant l'initialisation, l'enfilement, le défilement, l'affichage et le tri de la file par priorité.
int main () {
File *F1 ,* F2;
int choix;
Personne p;
F1 = AllouerF();
F1 = initialiser(F1);
do {
printf("1 - Initialiser \n");
printf("2 - Enfiler \n");
printf("3 - Défiler \n");
printf("4 - Afficher \n");
printf("5 - Trier la file \n");
printf("0 - Quitter \n");
printf("\tChoix : ");
scanf("%d" ,&choix);
switch (choix) {
case 0: break;
case 1: F1 = initialiser(F1); break;
case 2: printf("\t\t Donner le nom : ");
scanf("%s",p.nom) ;
printf("\t Donner la priorité : ");
scanf("%d" ,&p.priorite) ;
F1 = enfiler(F1 ,p) ;
afficher(F1) ;
break;
case 3: F1 = defiler(F1) ;
afficher(F1) ;
break;
case 4: afficher(F1) ; break;
case 5:
F2 = trier_file(F1) ;
printf("La file après le tri \n") ;
afficher(F2) ; break;
default : printf("Erreur... \n") ; break;
}
} while (choix != 0) ;
system("pause"); // Commande spécifique à certains systèmes d'exploitation (ex: Windows), utilisée pour maintenir la fenêtre console ouverte.
}Foire Aux Questions (FAQ)
Qu'est-ce qu'une structure de données dynamique en C ?
Une structure de données dynamique est un moyen d'organiser des données dont la taille peut être modifiée pendant l'exécution d'un programme. Contrairement aux tableaux statiques, elle utilise l'allocation dynamique de mémoire (avec
malloc,calloc,reallocetfree) pour gérer l'espace mémoire au besoin. Les listes chaînées, les piles et les files en sont des exemples courants, offrant une grande flexibilité dans la gestion des données.Quelle est la différence entre une liste simplement chaînée et une liste doublement chaînée ?
Une liste simplement chaînée (LSC) est une séquence de nœuds où chaque nœud contient une donnée et un pointeur vers le nœud suivant, permettant une navigation unidirectionnelle. Une liste doublement chaînée (LDC) ajoute un pointeur vers le nœud précédent, permettant ainsi une navigation bidirectionnelle. Les LDC facilitent certaines opérations comme la suppression d'un nœud sans avoir besoin de son prédécesseur, mais consomment légèrement plus de mémoire par nœud en raison du pointeur supplémentaire.
Quand utiliser une pile plutôt qu'une file ?
Une pile (structure LIFO - Last-In, First-Out) est utilisée lorsque l'ordre d'accès aux éléments doit être l'inverse de leur ordre d'insertion, par exemple pour gérer des appels de fonctions (pile d'exécution), l'historique d'actions "annuler", ou la validation de parenthèses dans une expression. Une file (structure FIFO - First-In, First-Out) est appropriée lorsque l'ordre d'accès est le même que l'ordre d'insertion, comme pour gérer des tâches en attente, des processus dans un système d'exploitation, ou une file d'attente d'impressions.