Correction TP 6 - Les listes chaînées

Ce travail pratique porte sur la manipulation des listes chaînées simples et des piles en langage C. Il détaille la mise en œuvre des opérations fondamentales : création, parcours, insertion, suppression d'éléments et calculs sur des structures de données dynamiques. L'objectif est d'assimiler la gestion explicite des pointeurs et de la mémoire.

Objectifs pédagogiques

• Comprendre la structure et le fonctionnement d'une liste chaînée simple en langage C.
• Allouer et libérer dynamiquement la mémoire pour des structures de données.
• Insérer des éléments en début et en fin de liste.
• Parcourir une liste pour effectuer un affichage ou des calculs (moyenne, élévation au carré).
• Supprimer le premier ou le dernier élément d'une liste.
• Mettre en œuvre une pile (structure LIFO) avec les opérations d'empilement et de dépilement.

Prérequis et environnement

• Maitrise de la syntaxe du langage C : pointeurs, structures et fonctions.
• Utilisation des fonctions d'allocation dynamique (malloc, free).
• Environnement de développement C fonctionnel (compilateur GCC, Clang ou un IDE dédié).

Initialisation d'une liste chaînée

L'initialisation prépare la structure globale de la liste. Celle-ci s'appuie sur une structure Liste qui conserve les pointeurs vers le premier, l'élément courant et le dernier élément.

void initListe(Pliste L){
   L = (Pliste) malloc(sizeof(Liste));
   L->premier = (Pelement) malloc(sizeof(Element));
   L->courant = (Pelement) malloc(sizeof(Element));
   L->dernier = (Pelement) malloc(sizeof(Element));
   L->premier = NULL;
   L->courant = NULL;
   L->dernier = NULL;
}

À l'issue de l'exécution, les pointeurs de contrôle de la liste sont positionnés à NULL, indiquant une liste vide.

Création d'une liste décroissante

La fonction creeListeDecroissante génère une liste contenant les entiers de 1 à n. L'insertion consécutive en tête de liste inversant l'ordre des éléments, la liste finale présente des valeurs décroissantes.

void creeListeDecroissante(Pliste L, int n){
   printf("***** creeListeDecroissante() *****\n");
   int i;
   Pelement Pel;
   for(i=1; i<=n; i++){
      Pel = (Pelement) malloc(sizeof(Element));
      Pel->x = i;
      insereUnElemt(L, Pel);
   }
}

Chaque élément est inséré en tête au moyen de la fonction insereUnElemt :

void insereUnElemt(Pliste L, Pelement nouveau){
   nouveau->suivant = L->premier;
   L->premier = nouveau;
   if(L->dernier == NULL)
      L->dernier = nouveau;
}

Pour n = 5, le premier élément vaudra 5 et le dernier sera 1.

Affichage des éléments d'une liste

Le parcours séquentiel pour l'affichage débute à l'adresse mémoire contenue dans L->premier et suit les pointeurs suivant jusqu me rencontrer NULL.

void afficheListe(Pliste L){
   L->courant = L->premier;
   printf("Liste = [ ");
   while(L->courant != NULL){
      printf("%d, ", L->courant->x);
      L->courant = L->courant->suivant;
   }
   printf("]\n");
}

L'exécution produit une chaîne sous la forme : Liste = [ 5, 4, 3, 2, 1, ].

Calcul de la moyenne des éléments

Le calcul de la moyenne nécessite un parcours complet de la liste pour accumuler la somme des entiers et déterminer le nombre exact d'éléments présent dans la structure.

float moyenne(Pliste L){
   int som = 0, cpt = 0;
   L->courant = L->premier;
   while(L->courant != NULL){
      cpt++;
      som += L->courant->x;
      L->courant = L->courant->suivant;
   }
   return (float)som / cpt;
}

Pour la liste de 5 à 1, la somme vaut 15 et le compteur 5, ce qui renvoie une moyenne de 3.00.

Insertion en fin de liste

L'insertion en queue s'appuie sur le pointeur dernier de la structure de contrôle. Lorsque la liste est vide, la fonction bascule automatiquement sur une insertion en tête.

void inserFinListe(Pliste L, Pelement nouveau){
   if(L->dernier == NULL){
      insereUnElemt(L, nouveau);
   } else {
      nouveau->suivant = L->dernier->suivant;
      L->dernier->suivant = nouveau;
      L->dernier = nouveau;
   }
}

Cette méthode permet un ajout en complexité temporelle constante O(1) sans reparcourir toute la liste.

Création d'une liste des carrés

La fonction carres parcourt une liste d'origine, calcule le carré de chaque entier rencontré avec la fonction pow, puis construit une seconde liste par insertions successives en fin de chaîne.

void carres(Pliste L, Pliste Lc){
   Pelement el;
   initListe(Lc);
   L->courant = L->premier;
   while(L->courant != NULL){
      el = (Pelement) malloc(sizeof(Element));
      el->x = pow(L->courant->x, 2);
      inserFinListe(Lc, el);
      L->courant = L->courant->suivant;
   }
}

Appliquée à la liste [5, 4, 3, 2, 1], cette fonction génère la liste [25, 16, 9, 4, 1].

Suppression du premier élément

La suppression en tête met à jour la référence premier vers l'élément suivant avant de restituer la mémoire du nœud supprimé au système.

void supprimePremier(Pliste L){
   Pelement el = L->premier;
   L->premier = L->premier->suivant;
   free(el);
   el = NULL;
}

Cette opération supprime la tête de liste et évite toute fuite mémoire grâce à la fonction free.

Suppression du dernier élément

La suppression du dernier nœud requiert un parcours jusqu'à l'avant-dernier élément pour mettre à jour son pointeur suivant à NULL et réajuster la référence dernier.

void supprimeDernier(Pliste L){
   Pelement el = L->dernier;
   Pelement avDernier;
   L->courant = L->premier;
   while(L->courant->suivant->suivant != NULL){
      L->courant = L->courant->suivant;
   }
   avDernier = L->courant;
   free(avDernier->suivant);
   avDernier->suivant = NULL;
   L->dernier = avDernier;
}

Gestion d'une pile (structure LIFO)

Une pile suit une logique « Dernier Entré, Premier Sorti » (LIFO). Dans cette implémentation, la structure est dérivée d'une liste chaînée sur laquelle s'appliquent les opérations d'initialisation, d'empilement et de dépilement.

Initialisation de la pile

void initialiserPile(Pliste P){
   P = (Pliste) malloc(sizeof(Liste));
   P->premier = (Pelement) malloc(sizeof(Element));
   P->courant = (Pelement) malloc(sizeof(Element));
   P->premier = NULL;
   P->courant = NULL;
   P->taille = 0;
}

Empilement et dépilement

L'empilement réalise un ajout en sommet de pile (équivalent au début de liste), tandis que le dépilement extrait ce sommet.

void empiler(Pliste P, int i){
   Pelement nouveau = (Pelement) malloc(sizeof(Element));
   nouveau->n = i;
   if(pileVide(P)){
      nouveau->suivant = NULL;
      P->premier = nouveau;
   } else {
      nouveau->suivant = P->premier;
      P->premier = nouveau;
   }
   P->taille++;
}

void depiler(Pliste P){
   if(!pileVide(P)){
      Pelement asupprimer = P->premier;
      P->premier = P->premier->suivant;
      printf("Element retire de la pile : %d\n", asupprimer->n);
      free(asupprimer);
      asupprimer = NULL;
      P->taille--;
   }
}

Menu interactif de la pile

Un menu interactif permet à l'utilisateur de piloter les fonctionnalités de la structure via la console.

int menu(){
   int choix, a;
   printf("*** Gestion d'une pile ***\n");
   printf(" 1 - Initialiser\n");
   printf(" 2 - afficher\n");
   printf(" 3 - Empiler \n");
   printf(" 4 - Depiler\n");
   printf(" 5 - Quitter\n");
   printf("Saisissez votre choix : ");
   scanf("%d", &choix);
   switch(choix){
      case 1:
         initialiserPile(pile);
         printf("Pile initialisee\n");
         menu();
         break;
      case 2:
         afficher(pile);
         menu();
         break;
      case 3:
         printf("Saisir entier a inserer dans la pile : ");
         scanf("%d", &a);
         empiler(pile, a);
         menu();
         break;
      case 4:
         depiler(pile);
         menu();
         break;
      case 5:
         exit(0);
      default:
         printf("/!\\ Choix non valide /!\\ \n");
         menu();
   }
}

Bilan des résultats d'exécution

• Création et affichage d'une liste de 5 éléments : Liste = [ 5, 4, 3, 2, 1, ].
• Calcul de la moyenne : Moyenne(Liste) = 3.00.
• Liste des carrés calculée : Liste = [ 25, 16, 9, 4, 1, ].
• Après suppression de la tête : Liste = [ 4, 3, 2, 1, ].
• Après suppression de la queue : Liste = [ 5, 4, 3, 2, ].

Analyse des pièges et conseils d'implémentation

• Pointeurs d'initialisation : Toujours s'assurer que les pointeurs de structure vide pointent vers NULL avant toute manipulation pour éviter les déréférencements sauvages.
• Mise à jour des extrémités : Veiller à maintenir la cohérence du pointeur dernier lors des opérations d'insertion et de suppression.
• Fuites mémoire : Tout appel à malloc doit obligatoirement être compensé par un free lors de la suppression d'un élément.
• Conditions aux limites : Dans supprimeDernier, s'assurer que la liste contient au moins deux éléments pour éviter un accès invalide via L->courant->suivant->suivant.
• Passage de pointeurs par valeur : En C, la modification de l'adresse contenue dans un pointeur à l'intérieur d'une fonction nécessite un passage par adresse (double pointeur), ce qui évite les pertes d'allocation.