Enoncé exercice 11

Ecrire un programme C qui lit, vers une liste chaînée, une série d’entiers triée d’une manière croissante et la retrie dans l’ordre décroissant en jouant seulement sur les pointeurs de liaison.

Correction exercice 11

L’objectif de cet exercice est tout simplement d’apprendre à inverser l’ordre des cellules dans une liste chaînée. De façon à ce que la dernière cellule devient à la tête de la liste et vice versa. L’idée derrière, est trop simple. Si le pointeur d’une cellule q pointe sur la cellule p dans la liste, il suffira de rendre le pointeur de p pointant sur q. Bien que cette idée soit simple, sa mise en oeuvre demande un peu de technicité pour éviter de rompre la liste chaînée.

On commence comme toujours par la création et la lecture de la liste chaînée d’entiers, en précisant à l’utilisateur que les éléments doivent être triés d’une manière croissante (lignes 22-34).

Pour inverser la liste chaînée, on va la parcourir à l’aide d’une boucle while (lignes 40-47). Et on aura besoin à chaque itération, sauf pour la première, d’avoir sous la main la cellule actuelle p est celle qui la précède q. A ce stade il faudra affecter au pointeur de la cellule p, qui est (*p).suiv, l’adresse q (ligne 44). Et comme ça, la chaîne est localement inversée. Si on s’arrête là, un problème s’impose; on ne peut pas accéder au restant des cellules.

En effet, l’adresse de la cellule qui suivait p dans la liste chaînée d’origine, contenue dans (*p).suiv est perdue après l’altération du contenu de ce dernier pointeur. La solution à ce problème, est d’utiliser un troisième pointeur r où on va garder cette adresse avant d’effectuer la modification visée (ligne 42).

En ce qui concerne la première cellule, la seule modification à y apporter est de mettre son pointeur à NULL, puisqu’elle deviendra la dernière cellule de la liste inversée (ligne 43).

En guise de préparation à l’itération suivante, q doit passer à p et p doit passer à la cellule suivante (dans la liste d’origine) qui est r (lignes 45-46).

Une fois sortis, on va affecter à liste l’adresse de la dernière cellule traitée, qui est q (ligne 48).

Remarque : en ce qui concerne les deux initialisations r=liste et q=NULL (lignes 37-38); la première assure l’accès à la boucle while dans le cas où la liste n’est pas vide et l’interdit dans l’autre cas. Et la deuxième est là pour pouvoir affecter à liste (ligne 48) la valeur NULL dans le cas d’une liste vide. Car sans cette initialisation liste lui sera affecter dans ce cas une valeur arbitraire qui peut ne pas être NULL, chose qui va générer un problème lors de l’exécution de l’affichage de la liste vide.

Solution exercice 11

#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");
}
int main()
{
    struct cellule *liste,*p,*q,*r;
    int n,i;
    printf("Entrez le nombre d'elements:\n");
    scanf("%d",&n);
    printf("Entrez les elements de la liste (tries):\n");
    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;
        else (*q).suiv=p;
        q=p;
    }
    printf("Liste avant le tri:\n");
    Afficher(liste);
    p=liste;
    r=liste;
    q=NULL;
    while(r!=NULL)
    {
        r=(*p).suiv;
        if(p==liste) (*p).suiv=NULL;
        else (*p).suiv=q;
        q=p;
        p=r;
    }
    liste=q;
    printf("Liste apres le tri:\n");
    Afficher(liste);
    system("pause");
    return 0;
}

Enoncé exercice 12

Ecrire un programme C qui se base sur la notion des piles pour vérifier si une suite de crochets est équilibrée ou non.

Exemples : [ ][ ][ [ [ ] ] ] (Crochets équilibrés) et ] [ (Crochets non équilibrés).

Le programme doit s’inspirer des éléments suivants :

• Création d’une liste chaînée appelée pile ;
• Les cellules de la liste pile contiennent un caractère et un pointeur de liaison ;
• Une fonction Add qui ajoute une cellule à la tête de la liste pile en la remplissant par un caractère pris en paramètre ;
• Une fonction Drop qui supprime la cellule à la tête de pile ;
• Une fonction Top qui renvoie le caractère dans la tête de la liste pile ;
• Une fonction Vide qui renvoie 1 si pile est vide, et 0 dans le cas contraire.

Algorithme : Pour vérifier si une suite de crochets est équilibrée, il suffit de les ajouter à la pile, dans l’ordre, crochet par crochet. Sauf dans le cas suivant ; si le crochet à la tête de la pile est un crochet ouvrant [ et le crochet qu’on souhaite ajouter est un crochet fermant ]. Dans ce cas, le crochet fermant ne doit pas être ajouté à la pile, et en plus on supprime le crochet ouvrant de la tête de la pile. Puis, on passe au crochet suivant dans la suite.

Après le traitement de tous les crochets, on vérifie si la pile est vide ou non. Si elle l’est, la suite de crochets est équilibrée, sinon elle n’est pas équilibrée.

Correction exercice 12

Les piles sont des structures de données qui permettent en gros les trois opérations suivantes :

• L’accès à la valeur du dernier élément ajouté ;
• Suppression du dernier élément ajouté ;
• Ajout d’un nouvel élément au-dessus du dernier élément ajouté.

Un exemple de pile, peut être un empellement de livres. On ne peut voir que la couverture du livre au-dessus, on ne peut prendre que ce dernier et si on ajoute un autre livre on le mit au sommet de l’empellement.

Avant de passer à l’implémentation de l’algorithme de vérification de l’équilibrage d’une suite de crochets, on va tout d’abord définir les fonctions mentionnées dans l’énoncé.

Avec la fonction Add (lignes 8-15), on souhaitera ajouter une nouvelle cellule à la tête d’une liste chaînée. Pour faire ceci, il faudra d’abord créer la cellule en utilisant la fonction malloc puis la remplir avec le caractère passé en paramètre (lignes 11-12). Pour l’assembler avec la liste chaînée, il suffira de mettre l’adresse de l’ancienne cellule en tête, dans le pointeur de la cellule créée. Et modifier ensuite le contenu du pointeur qui permet l’accès à la liste chaînée en y mettant l’adresse de la cellule créée. Seulement que cette modification ne peut pas persister à l’extérieur de la fonction Add. C’est pourquoi on ne doit pas passer en paramètre le pointeur mais son adresse adr_pile.

Pour la fonction Drop (ligne 16-22), il suffira de mettre l’adresse de la deuxième cellule dans le pointeur de la liste chaînée. Toujours en gardant en tête qu’il faut transmettre à la fonction Drop l’adresse de ce pointeur et non pas le pointeur lui-même.

Pour la fonction Top (lignes 23-26) qui donne la valeur du caractère contenu dans la première cellule de la liste chaînée, il suffira de lui passer le pointeur de la liste chaînée et de renvoyer le caractère demandé (ligne 25).

En ce qui concerne la dernière fonction (lignes 27-31), qui vérifie si une liste chaînée est vide ou non, il suffira de faire un test sur la valeur du pointeur transmis, pour le comparer à la valeur NULL. Dans le cas d’égalité, la liste est vide et dans l’autre cas il ne l’est pas.

Dans la fonction main, on va lire une chaîne de caractères s composée de crochets (ligne 38). On va la parcourir à l’aide d’une boucle for de compteur i. Et pour chaque itération, si le crochet en tête de la pile Top(pile) est un crochet ouvrant [, et le crochet s[i] est un crochet fermant ], on fait appel à la fonction Drop, pour supprimer le crochet ouvrant [ de la pile. Lors de l’appel de la fonction Drop, il ne faut pas oublier qu’on doit lui passer &pile et non pas pile (ligne 45).

Dans le cas où cette condition n’est pas vérifiée, on utilisera la fonction Add pour ajouter le crochet s[i] à la pile (ligne 46). Sauf qu’un cas particulier doit être traité à part. C’est le cas où la pile est vide. Car la fonction Top ne marche pas pour une pile vide. Dans ce dernier cas, on ajoute directement le crochet en question à la pile (ligne 42).

Après la sortie de la boucle for, on vérifie si la pile est vide ou non, en s’aidant de la fonction Vide. Et on affiche le message adéquat, selon ce que dicte l’algorithme (lignes 49-50).

Solution exercice 12

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct cellule{
       char c;
       struct cellule *suiv;
};
void Add(struct cellule **adr_pile, char c)
{
    struct cellule *p;
    p=(struct cellule *)malloc(sizeof(struct cellule));
    (*p).c=c;
    (*p).suiv=*adr_pile;
    *adr_pile=p;
}
void Drop(struct cellule **adr_pile)
{
    struct cellule *p;
    p=*adr_pile;
    *adr_pile=(**adr_pile).suiv;
    free(p);
}
char Top(struct cellule *pile)
{
    return (*pile).c;
}
int Vide(struct cellule *pile)
{
    if(pile==NULL) return 1;
    return 0;
}
int main()
{
    struct cellule *pile;
    int i;
    char s[100];
    printf("Entrez la chaine de crochets:\n");
    gets(s);
    pile=NULL;
    for(i=0;i<strlen(s);i++)
    {
        if(Vide(pile)==1) Add(&pile,s[i]);
        else
        {
           if(Top(pile)=='[' && s[i]==']') Drop(&pile);
           else Add(&pile,s[i]);
        }
    }
    if(Vide(pile)==1) printf("Les crochets sont equilibres.\n");
    else printf("Les crochets ne sont pas equilibres.\n");
    system("pause");
    return 0;
}

Enoncé exercice 13

Ecrire un programme C qui lit des entiers vers une liste doublement chaînée puis inverse l’ordre de ses éléments sans toucher aux pointeurs de liaison.

Correction exercice 13

Pour la construction et le remplissage de la liste doublement chaînée (lignes 27-44), ils sont traités en détail dans l’exercice 10. Du coup ils ne seront pas revus ici. Seulement, il faut garder de cette première étape que le pointeur liste donne l’adresse du premier élément de la liste et queue celle du dernier.

Pour inverser l’ordre des éléments de la liste, on va utiliser deux pointeurs p et q pour parcourir la liste. Le pointeur p va commencer par le premier élément liste et q par le dernier queue (lignes 48-49). Et à chaque itération de la boucle de parcours, les composants entiers des deux cellules p et q seront permutés (lignes 52-54). Une fois cette permutation est effectuée, p doit passer à la cellule qui suit et q à la cellule qui précède (lignes 55-56).

En ce qui concerne la condition de la boucle while, il faudra qu’elle couvre le cas où le nombre d’éléments est pair et celui où il est impair. Pour un nombre d’éléments impair, les deux pointeurs p et q vont se rencontrer à la cellule du milieu, où il faudra quitter la boucle. Donc la condition p!=q va assurer cette sortie. Mais dans le cas d’un nombre d’éléments pair, les deux pointeurs ne vont jamais se rencontrer. Si on considère que q commence à droite de p, à un certain moment il deviendra à sa gauche. C’est exactement au moment de cette transition qu’il faudra quitter la boucle. Elle est caractérisée par le fait que le pointeur prec de p pointe sur la cellule q. Et c’est la négation de cette condition qu’il faudra adopter pour la boucle while. C’est-à-dire (*p).prec!=q.

La liste chainée est affichée avant et après inversion pour s’assurer de la réussite de l’opération (lignes 46 et 59).

Solution exercice 13

#include<stdio.h>
#include<stdlib.h>
struct cellule{
       int a;
       struct cellule *suiv;
       struct cellule *prec;
};
void Afficher(struct cellule * liste)
{
   struct cellule *p;
   p=liste;
   while(p!=NULL)
   {
       printf("%d ",(*p).a);
       p=(*p).suiv;
   }
   printf("\n");
}
int main()
{
    struct cellule *liste,*p=NULL,*q,*queue;
    int n,i,tmp;
    printf("Entrez le nombre d'elements:\n");
    scanf("%d",&n);
    printf("Entrez les elements de la liste:\n");
    queue=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;
    }
    queue=p;
    printf("La liste avant inversion:\n");
    Afficher(liste);
    p=liste;
    q=queue;
    while(p!=q && (*p).prec!=q)
    {
       tmp=(*p).a;
       (*p).a=(*q).a;
       (*q).a=tmp;
       q=(*q).prec;
       p=(*p).suiv; 
    }
    printf("La liste apres inversion:\n");
    Afficher(liste);
    system("pause");
    return 0;
}