Enoncé exercice 1

Ecrire un programme C qui permet de créer et de lire une liste chaînée d’entiers et affiche ensuite ses éléments.

La structure utilisée pour les cellule de la liste doit être constituée d’:

• un entier;
• un pointeur sur la structure de la liste.

Illustration:

Correction exercice 1

Dans cet exercice on va essayer de se familiariser avec la notion des listes chaînées. Une liste chaînée est composée d’un ensemble d’éléments qu’on appelle ici des cellules. La première chose à faire lorsqu’on traite un exercice sur les listes chaînées, est de définir le type de cette cellule. Bien évidement ce type ne sera pas un des types prédéfinis du langage C, mais on aura à le créer selon le besoin de l’exercice en utilisant les structures.

On veut donc, pour cet exercice, construire une liste chaînée qui contient des entiers, un seul par cellule. Et qui doit en plus avoir un pointeur dans chaque une de ces cellules pour créer la liaison entre elles afin de pouvoir se déplacer tout au long de la liste chaînée. Et comme ce pointeur doit contenir l’adresse d’une cellule, et si on appelle la structure utilisée cellule, le type de ce pointeur sera alors struct cellule *.

Après la définition du type de la cellule (lignes 3-6), on demande à l’utilisateur d’entrer le nombre d’éléments avec lesquels il souhaite travailler, et qui sera lu dans la variable n.

Pour une liste chaînée, il faut toujours garder dans l’esprit qu’un pointeur vers la première cellule de la liste doit être gardé quelque part, en général dans un pointeur de type struct cellule * qu’on appelle ici tete.

Pour pouvoir abriter les n élément qui seront entrés, on aura besoin de créer une liste chaînée composée de n cellules. Et ceci bien sûr sera fait manuellement. Donc pour ainsi faire, on va utiliser une boucle for à n itérations (lignes 14-21).

La création d’une cellule sera réalisée d’une façon dynamique, comme ça on pourra créer autant de cellules que l’utilisateur en aura besoin. On va se servir donc de la fonction malloc qui va prendre comme paramètre 1*sizeof(struct cellule) ou tout simplement sizeof(struct cellule) puisqu’on veut créer un seul élément de type struct cellule. Et on converti la valeur renvoyée par malloc vers le type du pointeur p par le biais de (struct cellule *) (ligne 16).

La cellule créée est maintenant pointée par p. Pour lire son composant entier on peut y accéder en utilisant (*p).a (ligne 17).

Pour assurer la liaison entre les différentes cellules, on doit toujours avoir sous la main l’avant dernière cellule créée. Concrètement un pointeur q sur elle sera conservé. Cette cellule doit contenir un pointeur sur la dernière cellule créée p. Pour réaliser cette liaison, on doit mettre l’adresse p dans la partie suiv (réservée au pointeur dans la structure cellule) de la cellule pointée par q (ligne 19). Elle faudra garder à jour le pointeur q en lui affectant l’adresse de la cellule dernièrement créée, en guise de préparation pour le nouvelle itération (ligne 20).

La première cellule créée, vu sa position dans la tête de la liste, bénéficiera d’un traitement différent. On doit seulement garder son adresse dans le pointeur tete (ligne 18).

Après la sortie de la boucle for, on doit mettre le pointeur suiv de la dernière cellule à NULL pour signaler ainsi la fin de la liste (ligne 22).

Pour afficher le contenu de la liste il faudra la parcourir. Généralement ceci est fait à l’aide d’une boucle while. Et on commence par son premier élément qui est pointé par tete et avec lequel on va initialiser le pointeur q qui va servir à parcourir la liste (ligne 24).

Après qu’on a entré dans la boucle, on va afficher à chaque fois le contenu de la cellule pointée par q. Puisque q pointe vers une cellule, donc cette cellule est la variable *q qui est de type struct cellule. On peut accéder donc à son élément entier par (*q).a (ligne 27).

Pour passer dans l’itération qui suit vers la cellule contiguë, on affecte à q le pointeur vers cette cellule et qui est (*q).suiv (ligne 28). Ce processus va se répéter jusqu’à ce qu’on arrive à la dernière cellule qui est marquée par le pointeur NULL dans sa partie suiv.

Solution exercice 1

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule * suiv;
       };
int main()
{
    struct cellule *p,*q,*tete=NULL;
    int i,n;
    printf("Donnez le nombre d'elements de la liste:\n");
    scanf("%d",&n);
    printf("Donnez les elements de la liste:\n");
    for(i=0;i<n;i++)
    {
        p=(struct cellule *)malloc(sizeof(struct cellule));
        scanf("%d",&((*p).a));
        if(i==0) tete=p;
        else (*q).suiv=p;
        q=p;
    }
    (*q).suiv=NULL;
    printf("Les elements de la liste:\n");
    q=tete;
    while(q!=NULL)
    {
       printf("%d ",(*q).a);
       q=(*q).suiv;
    }
    printf("\n");
    system("pause");
    return 0;
}

Enoncé exercice 2

On définit une matrice creuse comme étant une matrice dont plus que la moitié des éléments sont nuls.

Pour minimiser l’espace occupé par ce type de matrice on choisi de les représenter sous forme d’un tableau de listes chaînées, de sorte que la i^ième liste chaînée contient les éléments non nuls de la ligne i de la matrice et chacun d’eux accompagné du numéro de la colonne où il se trouve.

Tâches à faire:

• Définir la structure qui sera utilisée pour les cellules des listes chaînées;
• Transformer une matrice M de taille nxm en tableau de listes chaînées T comme défini précédemment;
• Afficher un élément M[i][j] à partir de T.

Correction exercice 2

Dans cet exercice on va utiliser un tableau de listes chaînées pour représenter une matrice creuse. Chaque liste dans ce tableau va contenir les éléments non nuls de la ligne correspondante de la matrice, ainsi que leurs indices de colonne pour conserver la position qu’ils occupent dans la matrice.

Les cellules constituantes des listes chaînées seront des structures composées de trois éléments : deux entiers indice et valeur. Le premier pour l’indice de la colonne où il se trouve l’élément non nul, et le deuxième pour la valeur de ce dernier. Et un troisième composant qu’est un pointeur sur une cellule, et qui va servir de liaison entre les cellules de chaque liste chaînée et il sera appelé suivant (lignes 3-7).

Le tableau de listes chaînées qu’on appellera T, est un tableau à une dimension de pointeurs sur le type struct cellule. Sa taille est la même que le nombre de lignes de la matrice creuse appelée M. Ce tableau peut être un simple tableau statique qu’on peut déclarer de la façon suivante : struct cellule * T [20], mais dans cet exercice on va utiliser un tableau dynamique qu’on créera en utilisant la fonction malloc (ligne 20).

Après la lecture de la matrice M et l’allocation de l’espace mémoire pour le tableau T, viennent la création et le remplissage des listes chaînées et leur association à la position adéquate du tableau T. Pour ceci on va parcourir les lignes de la matrice M avec une boucle for de compteur i, et pour chaque ligne on va se servir d’une deuxième boucle pour rechercher les éléments non nuls dans celle-ci, et chaque fois qu’on en trouve un on crée une cellule en utilisant la fonction malloc, puis on affecte à son composant indice le numéro de colonne j et au composant valeur on affecte M[i][j] (lignes 28-30). Cette cellule va être assemblée avec les autres cellules créées pour la même ligne afin de construire une liste chaînée en procédant comme décrit dans le paragraphe suivant.

Comme on a vu dans le premier exercice, le premier élément d’une liste chaînée est traité séparément des autres pour la seule raison qu’il n’est pas pointé par le composant suivant d’une autre cellule, mais plutôt par le pointeur qui représente la liste chaînée. Donc, à chaque fois qu’une cellule est créée en vérifie si elle la première en utilisant une variable ok initialisée par 0 et qui prendra la valeur 1 une fois la première cellule est créée (ligne 39).

Le pointeur p récupéré en réservant l’espace mémoire à une cellule sera affecté à T[i] pour la première cellule (ligne 38) et au composant suivant de la cellule qui vient juste avant pour le reste des cellules (ligne 34). Ceci impose de garder à portée de main un pointeur sur cette dernière. Dans le programme il est conservé dans le pointeur q (ligne 41). Il est très important d’initialiser les composant suivant des cellules crées par NULL pour s’assurer que ce composant suivant est égale à NULL pour la dernière cellule de la liste chaînée. Et de même pour les T[i], ils doivent à leur tour être initialisés à NULL pour pouvoir signaler qu’une liste est vide dans le cas où une ligne de la matrice est complètement constituée de zéros (ligne 23).

Une fois que le tableau des listes chaînées est créé, on va demander à l’utilisateur d’entrer les deux indices i et j d’un élément de la matrice M et on va l‘afficher à partir du tableau T. Pour faire ceci, on va aller à la liste chaînée T[i], qu’on va parcourir à l’aide d’un pointeur p et une boucle while (lignes 47-56).

Pour chaque cellule pointée par p on vérifie si son composant indice est égal à j. Et si c’était le cas, on affiche le composant valeur de la même cellule, et on quitte la boucle while (lignes 49-54). Dans le cas où cet indice n’a pas été trouvé dans la liste, on va conclure que l’élément à la position aux indices i et j de la la matrice M est nul. Après la boucle while, on peut facilement détecter si l’indice a été retrouvé ou non en comparant p avec la valeur NULL qui vaudra dire que la boucle à arriver à la dernière cellule sans trouver cet indice et a essayé de chercher dans la cellule suivante et qui n’existe pas bien sûr. Dans ce dernier cas on affiche 0 en utilisant la fonction printf (ligne 57).

Solution exercice 2

#include<stdio.h>
#include<stdlib.h>
struct cellule{
           int indice;
           int valeur; 
           struct cellule * suivant;
       };
int main()
{
    int M[20][20];
    int n,m,i,j,ok;
    struct cellule ** T;
    struct cellule *p,*q;
    printf("Donnez le nombre de lignes et de colonnes: ");
    scanf("%d%d",&n,&m);
    printf("Entrez les elements de la matrice:\n");
    for(i=0;i<n;i++)   
       for(j=0;j<m;j++)
          scanf("%d",&M[i][j]);
    T = (struct cellule **) malloc(n*sizeof(struct cellule *));
    for(i=0;i<n;i++)
    {
        T[i] = NULL;
        ok = 0;
        for(j=0;j<m;j++)
            if(M[i][j]!=0)
            {
               p = (struct cellule *) malloc(sizeof(struct cellule));
               (*p).indice = j;
               (*p).valeur = M[i][j];
               (*p).suivant = NULL;
               if(ok==1)
               {
                   (*q).suivant = p;      
               }
               else
               {
                   T[i] = p;
                   ok = 1;
               }
               q=p;
            }
    }
    printf("Donnez la position de l'element a afficher: ");
    scanf("%d%d",&i,&j);
    p=T[i];
    while(p!=NULL)
    {
       if((*p).indice==j)
       {
          printf("%d\n",(*p).valeur);
          ok=1;
          break;
       }
       p=(*p).suivant;
    }
    if(p==NULL) printf("0\n");
    system("pause");
    return 0;
}

Enoncé exercice 3

Ecrire un programme C qui crée et lit une liste chaînée d’entiers, et lit ensuite un entier et une position et insère l’entier dans la position précisée.

Correction exercice 3

Dans cet exercice, il est demandé de créer et de remplir une liste chaînée d’entiers, puis d’y insérer un entier dans une position donnée. Donc, après la définition de la structure cellule, qui va servir pour la construction de la liste chaînée (lignes 3-6), on va demander à l’utilisateur d’entrer le nombre d’entiers que va contenir la liste. Et on procédera ensuite à leur lecture, chose qui se fera en parallèle avec la création de la liste.

Comme il en est l’habitude, on va utiliser la fonction malloc pour créer les cellules, puis lire l’entier vers le composant entier de la cellule et on terminera par l’assurance de la connexion de la cellule créée avec les autres cellules (lignes 15-25). Tout ceci en se servant d’une boucle for.

Une fois la liste chaînée est créée, on va lire l’entier à insérer et la position d’insertion vers les deux variables b et pos. Insérer un élément dans la position pos revient à récupérer les deux pointeurs q et p sur les cellules dont les deux positions sont pos-1 et pos, puis créer la nouvelle cellule r en utilisant la fonction malloc et faire pointer le pointeur de la cellule q qui est (*q).suivant sur la nouvelle cellule r, et celui de r sur la cellule p (lignes 42-43).

Il faut remarquer que toutes les cellules de la liste chaînées, à l’exception de la première, sont précédées par une cellule et pointent sur une autre (y compris la dernières cellule qui pointe sur NULL) ceci implique la nécessité de traiter différemment le cas d’insertion d’une cellule dans la première position.

Si on souhaite insérer la nouvelle cellule r au début de la liste, c’est-à-dire dans le cas ou pos est égale à 1, il suffira de faire pointer (*r).suivant sur la première cellule qui est liste, puis signaler que la première cellule deviendra r et ceci en affectant à liste le pointeur r (lignes 30-34). L’ordre de ces deux opérations est important et doit s’effectuer comme mentionné ici.

Pour déterminer les deux cellules précitées q et p, il suffira d’utiliser une boucle for allant de 0 à pos-1 en veillant à ce que la cellule dans la position actuelle (itération actuelle de la boucle) soit pointée par q et que p reçoit l’adresse de la cellule qui suit q et qui est (*q).suivant. Cette valeur de p doit être reprise par q dans l’itération qui suivra pour assurer que q représente toujours la cellule dans la position i où i est le compteur de la boucle for (lignes 36-41).

Pour terminer le programme on affichera la liste après l’insertion du nouvel élément pour pouvoir observer la modification introduite (lignes 46-52).

Si on souhaite commencer la numérotation des positions à partir de 0 au lieu de 1 il suffira seulement de faire commencer le compteur de la boucle utilisée pour chercher les deux cellules q et p par 0 et de remplacer la condition du bloc if else de pos==1 à pos==0 (lignes 30).

Solution exercice 3

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule * suivant;
       };
int main()
{
    struct cellule *liste,*p,*q,*r;
    int n,pos,b,i;
    printf("Entrez le nombre d'elements de la liste:\n");
    scanf("%d",&n);
    liste=NULL;
    printf("Entrez les elements de la liste:\n");
    for(i=0;i<n;i++)
    {
       p = (struct cellule *)malloc(sizeof(struct cellule));
       scanf("%d",&(*p).a);
       if(i==0) liste=p;
       else{
       (*q).suivant=p;
       (*p).suivant=NULL;
       }
       q=p;
    }
    printf("Entrez l'entier a inserer et la position d'insertion:\n");
    scanf("%d%d",&b,&pos);
    r = (struct cellule *)malloc(sizeof(struct cellule));
    (*r).a=b;
    if(pos==1)
    { 
       (*r).suivant=liste;
       liste=r;
    }
    else{
       p=liste;
       for(i=1;i<pos;i++)
       {
          q=p;
          p=(*q).suivant;
       }
       (*q).suivant=r;
       (*r).suivant=p;
    }
    n++;
    p=liste;
    for(i=0;i<n;i++)
    {
       printf("%d ",(*p).a);
       p=(*p).suivant;
    }
    printf("\n");
    system("pause");
    return 0;
}

Enoncé exercice 4

Ecrire un programme C qui crée et lit une liste chaînée d’entiers, puis supprime de cette liste toutes les occurrences d’un entier entré par l’utilisateur.

Correction exercice 4

Dans cet exercice on va lire des entiers vers une liste chaînée, et on va supprimer de cette dernière toutes les occurrences d’un entier entré par l’utilisateur. Et comme on en a l’habitude jusqu’à ici, le premier élément de la liste nécessite un traitement particulier lors de l’opération de suppression. En plus de ceci s’ajoute le problème de transition entre les cellules de la liste chaînée et qui aura trois modes selon le cas:

• cas où on supprime le premier élément de la liste ;
• cas où on supprime un élément au milieu ou en fin de la liste ;
• cas d’une simple transition sans aucune suppression.

Pour cette partie du programme on va utiliser une boucle while et un pointeur p pour parcourir la liste chaînée liste (lignes 30-50).

Si le premier élément de la liste contient l’entier qu’on souhaite supprimer de la liste, on va affecter à liste le deuxième élément qui est (*p).suivant puis on libérera l’espace mémoire occupé par le premier élément qui est toujours pointé par p en faisant appel à la fonction free (ligne 37). Une fois cet espace est libéré, il faudra réinitialiser la valeur de p en lui affectant de nouveau le pointeur liste pour pouvoir vérifier sa nouvelle valeur dans la prochaine itération (lignes 34-39).

Pour supprimer un élément au milieu ou à la fin de la liste chaînée, il faudra tenir à portée de main un pointeur q sur la cellule juste avant p. Et on va faire pointer le pointeur de la cellule q sur la cellule juste après p à savoir la (*p).suivant. Puis on libérera l’espace occupé par p et on réinitialisera ensuite sa valeur par l’adresse de la cellule qu’on doit tester dans l’itération suivante et qui est (*q).suivant (lignes 40-44).

Il faut noter que même si aucune mise à jour du pointeur q n’apparaît avant le bloc qu’on vient de décrire (lignes 40-44), le pointeur q sera forcément mis à jour dans les dernières lignes de la boucle while avant d’avoir à exécuter ce bloc. Car le fait de parler d’un élément au milieu de la liste veut dire qu’on a déjà passé sur des cellules non supprimées et c’est à cet instant que le pointeur q sera mis à jour.

Dans le cas où la cellule p ne doit pas être supprimée, il suffira de mettre à jour le pointeur q et de faire pointer p sur la cellule qui suit (lignes 46-49).

On terminera le programme par l’affichage de la liste chaînée, après avoir supprimer toutes les occurrences de l’entier entré par l’utilisateur pour observer le résultat (lignes 51-57).

Solution exercice 4

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule * suivant;
       };
int main()
{
    struct cellule *liste,*p,*q;
    int n,i,b;
    printf("Entrez le nombre d'elements de la liste:\n");
    scanf("%d",&n);
    liste=NULL;
    printf("Entrez les elements de la liste:\n");
    for(i=0;i<n;i++)
    {
       p = (struct cellule *)malloc(sizeof(struct cellule));
       scanf("%d",&(*p).a);
       if(i==0) liste=p;
       else{
       (*q).suivant=p;
       (*p).suivant=NULL;
       }
       q=p;
    }
    printf("Entrez l'entier a supprimer:\n");
    scanf("%d",&b);
    p=liste;
    q=liste;
    while(p!=NULL)
    {
       if((*p).a==b)
       {
          if(p==liste)
          {  
             liste=(*p).suivant;
             free(p);
             p=liste;
          }
          else{
             (*q).suivant=(*p).suivant;
             free(p);
             p=(*q).suivant;
          }
       }
       else{
          q=p;            
          p=(*p).suivant;
       }
    }
    p=liste;
    while(p!=NULL)
    {
       printf("%d ",(*p).a);
       p=(*p).suivant;
    }
    printf("\n");
    system("pause");
    return 0;
}

Enoncé exercice 5

Ecrire un programme C qui inverse une liste chaînée en manipulant seulement ses pointeurs de liaison.

Correction exercice 5

L’idée pour cet exercice est de parcourir la liste chaînée, et pour chaque cellule associer à son composant pointeur l’adresse de la cellule qui la précède au lieu de celle qui la suit. Toutefois il faut démontrer un peu de technicité pour réussir ceci (lignes 23-32).

Pour faire pointer le pointeur d’une cellule p sur la cellule qui la précède, il est clair qu’on doit garder un pointeur sur cette dernière qu’on a appelé q. D’un autre côté, sachant que du moment où ce changement prend place, la liaison avec le reste de la liste sera détruite, d’où la nécessité de préserver l’adresse de la cellule suivante avant d’altérer la valeur du composant suivant de la cellule p. Cette adresse sera gardée dans le pointeur r (ligne 26).

Dans le cas où p correspond à la première cellule, on va affecter à son pointeur la valeur NULL, puisque cette cellule deviendra la dernière dans la liste inversée (ligne 27). Et pour les autres cellules il suffit de leur affecter q, l’adresse de la cellule précédente (ligne 28).

Pour assurer le parcours complet de la liste chaînée il faudra affecter à p le pointeur r qui contient l’adresse de la cellule suivante (ligne 30).

Finalement il ne faut pas oublier d’affecter l’adresse de la dernière cellule parcourue au pointeur liste car elle représente à cet instant la nouvelle entrée de la liste chaînée (ligne 32).

Solution exercice 5

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule *suivant;
       };
int main()
{
   struct cellule *liste,*p,*q,*r;
   int n,i;
   printf("Donner le nombre d'elements de la liste:\n");
   scanf("%d",&n);
   printf("Entrer les elements de la liste:\n");
   for(i=0;i<n;i++)
   {
      p=(struct cellule *)malloc(sizeof(struct cellule));
      scanf("%d",&(*p).a);
      if(i==0) liste = p;
      else (*q).suivant=p;
      q=p;
   }
   (*p).suivant=NULL;
   p=liste;
   while(p!=NULL)
   {
      r=(*p).suivant;
      if(p==liste) (*p).suivant=NULL;
      else (*p).suivant=q;
      q=p;
      p=r;
   }
   liste=q;
   p=liste;
   while(p!=NULL)
   {
      printf("%d ",(*p).a);
      p=(*p).suivant;
   }
   printf("\n");
   system("pause");
   return 0;
}