Enoncé exercice 6

Ecrire un programme C qui trie une liste chaînée d’entiers en utilisant le tri à bulles.

Correction exercice 6

Le tri d’une liste chaînée est similaire à celui des tableaux, avec la seule petite différence que le compteur j de la deuxième des deux boucles caractéristiques du tri à bulles ne permet pas l’accès aux cellules de la liste, tout simplement parce qu’il ne le peut pas.

Pour pallier à ce problème il faudra utiliser en parallèle avec ce compteur, un pointeur p pour parcourir la liste chaînée. Ce pointeur devra être initialisé avec le compteur j et recevoir l’adresse de la cellule suivante q en fin de chaque itération de la boucle (ligne 37).

Lors de chaque parcours de la liste chaînée, on doit permuter les deux composants entiers des cellules adjacentes chaque fois que celui de la première cellule est supérieur à celui de la deuxième (lignes 31-36).

A la fin du programme on affiche la liste chaînée pour s’assurer qu’elle est bien triée (lignes 40-46).

Solution exercice 6

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule * suivant;
       };
int main()
{
    struct cellule *liste,*p,*q;
    int n,tmp,i,j;
    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;
    }
    for(i=0;i<n-1;i++)
    {
       for(j=0,p=liste;j<n-1-i;j++)
       {
          q=(*p).suivant;
          if((*p).a>(*q).a)
          {
             tmp=(*p).a;
             (*p).a=(*q).a;
             (*q).a=tmp;
          }
          p=q;
       }
    }
    p=liste;
    for(i=0;i<n;i++)
    {
       printf("%d ",(*p).a);
       p=(*p).suivant;
    }
    printf("\n");
    system("pause");
    return 0;
}

Enoncé exercice 7

Ecrire un programme C qui supprime tous les éléments redondants d’une liste chaînée d’entiers.

Correction exercice 7

Le principe de suppression des doublons pour les listes chaînées est le même que celui des tableaux. On doit utiliser deux boucles imbriquées; la première pour parcourir les éléments de la liste jusqu’à l’avant dernier, et pour chaque élément choisi par cette dernière on va utiliser la deuxième boucle pour parcourir les éléments qui le suivent en recherche des éléments contenant le même entier que le sien afin de les supprimer.

On ne va pas revenir ici sur le procédé de suppression d’un élément de la liste (lignes 33-42) qui est traité en détail dans l’exercice 4 sauf qu’ici les choses sont plus simples puisqu’on n’aura pas à supprimer le premier élément de la liste. Par contre, ce qui peut poser des problèmes dans cet exercice est la condition d’arrêt de la première boucle.

On a dit que la première boucle doit s’arrêter à l’élément avant dernier, donc une condition telle que while((*p).suivant!=NULL) semble logique, mais en réalité elle s’avère insuffisante. Prenant par exemple une liste chaînée constituée des éléments 1 2 2, dans ce cas pour la deuxième (et dernière) itération de la première boucle on va supprimer le dernier élément de la liste sans aucun problème. A cet instant, p représente le dernier élément et non plus l’avant dernier. Donc lors de l’exécution de l’instruction p=(*p).suivant; qui assure la transition entre les éléments de la liste, p aura la valeur NULL. Maintenant si on essaye de vérifier la condition de la boucle while le programme va se planter car le pointeur NULL n’est pas du type struct cellule * donc l’écriture (*p).suivant n’aura pas de sens. Une solution pour éviter ce problème sera d’utiliser l’instruction break en fin de boucle si p est égal à NULL (ligne 45).

Solution exercice 7

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule * suivant;
       };
int main()
{
    struct cellule *liste,*p,*q,*r;
    int n,i,a;
    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;
    }
    p=liste;
    while((*p).suivant!=NULL)
    {
       r=(*p).suivant;
       q=p;
       while(r!=NULL)
       {
          if((*r).a==(*p).a)
          {
             (*q).suivant=(*r).suivant;
             free(r);
             r=(*q).suivant;
          }
          else{
             q=r;
             r=(*r).suivant;
          }
       }
       p=(*p).suivant;
       if(p==NULL) break;
    }
    p=liste;
    while(p!=NULL)
    {
       printf("%d ",(*p).a);
       p=(*p).suivant;
    }
    printf("\n");
    system("pause");
    return 0;
}

Enoncé exercice 8

Ecrire un programme C qui, à partir des éléments d’une liste chaînée, crée deux autres listes telles que la première contient les nombres pairs et la deuxième ceux impairs.

Correction exercice 8

Dans cet exercice on va découvrir comment on peut créer et remplir deux listes chaînées en parallèle. Comme exemple d’application on va construire deux listes chaînées de façon à ce que l’une d’entre elles contienne les nombres pairs et l’autre ceux impairs parmi les éléments d’une liste d’entiers.

Le programme commencera par la lecture des entiers entrés par l’utilisateur vers une liste chaînée appelée Liste. La création de cette dernière va suivre la méthode usuelle, qui consiste dans un premier temps à déclarer le pointeur Liste qui représentera le point de départ de la liste chaînée, puis à l’aide d’une boucle for créer les cellules en utilisant la fonction malloc et en veillant à assurer la liaison entre celles-ci (lignes 26-31).

Les cellules adoptées pour cet exercice sont des variables de structure à deux composants. Le premier est un entier et le second un pointeur qui liera les cellules afin de construire la liste chaînée.

Chaque fois qu’une cellule est créée, on lit son composant entier a avec scanf et on initialise son pointeur avec la valeur NULL. Puis on l’ajoute à la queue de la liste en affectant son adresse au pointeur de la cellule créée juste avant elle, à l’exception de la première cellule dont l’adresse doit être affectée au pointeur Liste (lignes 28-32).

Une fois la liste est remplie, on procédera à la création des deux listes chaînées Pair et Impair, qui sont dans l’ordre: la liste des nombres pairs et celle des nombres impairs. Pour ceci on va utiliser une boucle while et un pointeur p pour parcourir la liste chaînée Liste, et pour chaque cellule *p on créera une copie *pp et selon la parité de l’entier (*p).a on va ajouter la cellule *pp à la liste correspondante (lignes 41-52). La comparaison de Pair ou Impair avec la valeur NULL est pour voir si la liste est toujours vide ou non. Car dans ce cas l’ajout de la cellule *pp est différents (lignes 43 et 49).

Le processus d’ajout de la cellule *pp à l’une des listes Pair ou Impair nécessitera de garder un pointeur sur la dernière cellule de chaque une des deux listes. Ce qui est exactement le rôle des deux pointeurs q1 et q2.

Pour l’affichage des trois listes, on va utiliser une fonction Afficher (lignes 7-17) qui prend comme paramètre le pointeur sur la première cellule d’une liste chaînée, qui est ici soit Liste, Pair ou Impair et affiche tous les entiers contenus dans celle-ci.

Solution exercice 8

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule * suivant;
       };
void Afficher(struct cellule * liste)
{
    struct cellule *p; 
    p=liste;
    while(p!=NULL)
    {
       printf("%d ",(*p).a);
       p=(*p).suivant;
    }
    printf("\n");
}
int main()
{
    struct cellule *Liste=NULL,*Pair=NULL,*Impair=NULL;
    struct cellule *p,*q,*q1,*q2,*pp;
    int i,n;
    printf("Entrez la taille de la liste:\n");
    scanf("%d",&n);
    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);
        (*p).suivant=NULL;
        if(i==0) Liste = p;
        else (*q).suivant=p;
        q=p;
    }
    p=Liste;
    while(p!=NULL)
    {
        pp = (struct cellule *)malloc(sizeof(struct cellule));
        (*pp).a = (*p).a;
        (*pp).suivant=NULL;
        if((*pp).a%2==0)
        {
            if(Pair==NULL) Pair = pp;
            else (*q1).suivant = pp;
            q1=pp;
        }
        else
        {
            if(Impair==NULL) Impair = pp;
            else (*q2).suivant = pp;
            q2=pp;
        }
        p=(*p).suivant;
    }
    printf("Liste complete:\n");
    Afficher(Liste);
    printf("Liste des nombres pairs:\n");
    Afficher(Pair);
    printf("Liste des nombres impairs:\n");
    Afficher(Impair);
    system("pause");
    return 0;
}

Enoncé exercice 9

Ecrire un programme C, qui définit et utilise trois fonctions pour réaliser chacune l’une des trois tâches suivantes :

• Boucler une liste chaînée en liant son dernier élément au premier ;

• Chercher et renvoyer un pointeur sur un max d’une liste chaînée bouclée ;
• Dissocier une liste bouclée vers une liste ouverte qui commence par un élément maximal.

Correction exercice 9

L’objectif de cet exercice est de prendre une liste chaînée et de changer sa cellule de départ, en simulant ainsi une rotation de ses éléments. Ceci, en jouant seulement sur ses pointeurs de liaison. La procédure adoptée ici, consiste dans un premier temps à boucler la lister chaînée pour pouvoir la découper par la suite dans la position souhaitée.

En ce qui concerne la première étape du travail demandé, une fonction appelée Boucler (lignes 18-31) sera définie pour boucler une liste chaînée. Boucler une liste chaînée est une opération trop simple qui consiste à la parcourir jusqu’à trouver son dernier élément (lignes 22-30). Cet élément est caractérisé par le fait que son composant pointeur a la valeur NULL. Une fois cet élément est repéré, on affecte à son pointeur, l’adresse de la première cellule (liste). Cette adresse sera transmise à travers le paramètre de la fonction (lignes 24-28).

Pour la condition de la boucle while utilisée pour le parcours de la liste, il est difficile d’exploiter la comparaison du pointeur de parcours avec la valeur NULL, puisque une fois cette valeur est trouvée dans une cellule, elle sera remplacée par liste à l’intérieur du corps de la boucle, ce qui va résulter en une boucle infinie. Cette boucle infinie vient du fait que la liste deviendra bouclée et le pointeur NULL inexistant. Pour éviter ce problème on va utiliser une boucle infinie qui sera quittée en utilisant l’instruction break une fois la modification visée est effectuée (ligne 27).

Dans la fonction main, on va créer et remplir une liste chaînée liste, dont les cellules sont constituées d’un entier et d’un pointeur de liaison (lignes 68-86). On appelle ensuite la fonction Boucler en lui passant liste comme paramètre (ligne 88). Cet appel va assurer le bouclage de la liste.

Pour la deuxième tâche, la procédure de recherche du max dans une liste bouclée ne diffère pas trop de la recherche dans une liste chaînée ouverte. En effet, la seule différence c’est au niveau de la condition d’arrêt.

Pour une liste chaînée ouverte, il suffit de s’arrêter à la rencontre de l’élément contenant le pointeur NULL. Or, dans une liste chaînée bouclée, un tel élément n’existe pas. Et garder la même condition va résulter dans une boucle infinie. Ce qu’il faut faire par contre, est de s’arrêter lorsqu’on revient à la cellule par laquelle on a commencé la recherche.

La fonction Max qui va incorporer cette démarche, nécessite un seul argument q qui représente un pointeur sur n’importe quel élément de la liste bouclée (lignes 32-48). La variable max, utilisée pour trouver la valeur du max, sera initialisée par la valeur dans la première cellule qui est (*q).a (ligne 36). Un pointeur p_max sera utilisé pour garder l’emplacement de l’élément maximal.

D’après ce qui a été dit en dessus, il faudra comparer le pointeur de parcours p avec le pointeur de départ q. Et une fois les deux égaux, on sort de la boucle. Le problème est que p doit être initialisé par q avant la rentrée dans la boucle. Et si on vérifie cette condition au départ, on ne pourra jamais accéder à la boucle. D’où l’utilisation de la boucle do while qui est plus adaptée pour ce parcours que la boucle while, puisque elle ne vérifie la condition qu’à la fin des itérations.

La troisième fonction qu’on va définir, a comme objectif de transformer une liste chaînée bouclée en une liste chaînée ouverte, qui commence par une cellule contenant la valeur maximale. Pour la position de découpe de la liste on va exploiter le pointeur renvoyé par la fonction Max. Cette fonction qui sera appelée Dissocier, va devoir donc prendre le pointeur sur la position du max comme paramètre (lignes 49-63).

Dissocier une liste chaînée bouclée est en quelque sorte l’inverse de la démarche de son bouclage. Ça revient tout simplement à parcourir la liste pour trouver la cellule qui vient juste avant la position du max et affecter à son pointeur la valeur NULL (lignes 53-61).

Pour finaliser la dissociation de la liste bouclée, il faudra affecter au pointeur liste de la fonction main l’adresse du nouveau premier élément de la liste, qui est p_max. Ceci peut être fait de plusieurs façons. Ici, le pointeur p_max (ligne 62) est renvoyé par la fonction Dissocier puis intercepté par liste lors de l’appel de la fonction (ligne 91).

Pour terminer, une fonction Afficher est créée pour pouvoir afficher les différents états de la liste chaînée ouverte.

N.B. : l’instruction max=(*q).a; (ligne 36) va générer une erreur lors de l’exécution du programme pour une liste chaînée vide (nombre d’éléments entré est 0). Car dans ce cas, q qui est identique à liste aura la valeur NULL, c’est à dire qu’il ne pointe sur aucune cellule, donc l’écriture (*q).a n’aura pas de sens.

Solution exercice 9

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule *suiv;
       };
void Afficher(struct cellule *liste)
{
    struct cellule *p;
    p=liste;
    while(p!=NULL)
    {
       printf("%d ",(*p).a);
       p=(*p).suiv;
    }
    printf("\n");
}
void Boucler(struct cellule *liste)
{
    struct cellule *p;
    p=liste;
    while(1)
    {
       if((*p).suiv==NULL)
       {
          (*p).suiv=liste;
          break;
       }           
       p=(*p).suiv;
    }
}
struct cellule * Max(struct cellule *q)
{
    struct cellule *p,*p_max;
    int max;
    max=(*q).a;
    p_max=q;
    p=q;
    do{
        if((*p).a>max)
        {
           max=(*p).a;
           p_max=p;
        }
        p=(*p).suiv;
    }while(p!=q);
    return p_max;
}
struct cellule * Dissocier(struct cellule *p_max)
{
    struct cellule *p;
    p=p_max;
    while(1)
    {
       if((*p).suiv==p_max)
       {
          (*p).suiv=NULL;
          break;
       }           
       p=(*p).suiv;
    }
    return p_max;
}
int main()
{
    struct cellule *liste,*p,*q,*p_max;
    int n,i;
    printf("Entrez le nombre d'elements de la liste:\n");
    scanf("%d",&n);
    printf("Entrez les elements de la liste:\n");
    liste=NULL;
    for(i=0;i<n;i++)
    {
       p=(struct cellule *)malloc(sizeof(struct cellule));
       scanf("%d",&(*p).a);
       if(i==0)
       {
           liste=p;
       }
       else
       {
           (*q).suiv=p;
       }
       (*p).suiv=NULL;
       q=p;
    }
    Afficher(liste);
    Boucler(liste);
    p_max=Max(liste);
    printf("Le max est %d.\n",(*p_max).a);
    liste=Dissocier(p_max);
    Afficher(liste);
    system("pause");
    return 0;
}

Enoncé exercice 10

Ecrire un programme C qui permet de créer une liste d’entiers doublement chaînée, la lit et affiche ensuite ses éléments du premier au dernier puis inversement.

Correction exercice 10

À l’encontre des listes chaînées simples, qui ne permettent le parcours des éléments que dans un seul sens, une liste doublement chaînée permet de traverser les éléments dans les deux sens. Et ce, grâce à la construction de ses cellules, qui se composent de deux pointeurs de liaison au lieu d’un seul. Le premier pointe sur l’élément suivant, et l’autre sur l’élément précédent.

Dans cet exercice, on souhaite créer et lire une liste doublement chaînée. Puis la traverser dans les deux sens pour afficher ses éléments du premier au dernier et du dernier au premier.

Comme d’habitude, la création et la lecture de la liste sont faites en parallèle. Ceci sera réalisée grâce à une boucle for juste après ce que la demande du nombre des éléments de la liste soit effectuée (lignes 16-33). Ce processus sera le même que pour une liste chaînée simple, à l’exception de deux instructions supplémentaires qu’il faudra ajouter pour assurer la liaison dans le sens inverse. Il s’agit du marquage du pointeur prec par la valeur NULL pour la première cellule, pour signaler ainsi la fin du parcours dans le sens inverse (ligne 25). Et puis l’implémentation de la liaison dans ce même sens pour le restant des cellules, en mettant l’adresse de la cellule précédente dans le composant prec de la dernière cellule créée (ligne 30).

Une fois la liste doublement chaînée est créée et remplie, on procédera à cet instant à l’affichage de ses éléments comme il est demandé.

Le parcours des listes doublement chaînées pour l’affichage, ne pose aucun problème, puisqu’il est exactement le même que celui des listes chaînées simples. Et plus que ça, il n’y a pas de grande différence entre le parcours dans les deux sens. Pour le premier sens, on utilise le pointeur suiv et on ignore prec (lignes 36-41). Et pour l’autre, on utilise prec et on ignore suiv (lignes 43-48). La petite différence qui existe, est que l’adresse de la cellule de départ est connue pour le sens direct (c’est liste), mais elle n’est pas connue pour le sens inverse. C’est pourquoi il faudra garder l’adresse de la dernière cellule quelque part. Et c’est le rôle de du pointeur fin auquel on a affecté le pointeur sur la dernière cellule créée à l’intérieur du bloc de la boucle for (ligne 34). Ces deux adresses liste et fin vont servir pour les initialisations du pointeur de parcours p (lignes 36 et 43).

Solution exercice 10

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