Skip to content

EPST 2e année – TP5 Exercice 1

7 décembre 2012

Dans ce TP, nous allons jouer avec une figure de style célèbre : les palindromes. Ce sera une occasion d’utiliser les fonctions d’allocation et libération dynamiques de la mémoire.

Énoncé

Solution

Cette fois-ci, nous allons construire la solution par étapes.

1. La fonction palindrome()

Commençons par elle puisqu’elle est plutôt simple et ne demande aucune gestion dynamique de la mémoire. On veut seulement lui donner une chaîne (déjà allouée), et elle nous renverra une valeur « logique » indiquant si elle contient un palindrome ou pas.

Il faut d’abord rappeler qu’en C, une valeur logique est le plus souvent représentée par un entier (int). En fait, la norme ISO de 1999 (C99) définit un type logique booléen (bool) mais nous n’allons pas l’utiliser (de toute façon, c’est juste un artifice pour cacher la nature numérique de ces valeurs).

La logique du C veut que la valeur zéro soit comprise comme « faux » et une valeur non nulle comme « vrai ». Le compilateur n’est pas « intelligent », c’est juste que les instructions de contrôle sont faites comme ça. Par exemple, dans if (condition) instruction ou while (condition) instruction, l’instruction est exécutée non pas si la condition est « vraie » comme nous l’avons appris, mais tout simplement si elle est différente de zéro.

De même, les expressions « logiques » qui utilisent les opérateurs relationnels et logiques ont toujours pour valeur soit 0 (zéro) si elles donnent un résultat « faux », soit 1 (un) s’il est « vrai ». Là aussi, il n’y a pas « d’intelligence » de la part de l’ordinateur : c’est juste un calcul. L’opérateur && par exemple donne un si les opérandes sont tous les deux différents de zéro et il donne zéro si au moins un des deux est nul. Même chose pour l’opérateur relationnel > qui donne un si le premier opérande est le plus grand et zéro sinon.

Si vous n’êtes pas convaincu, essayez avec une instruction printf("%d", 3 > 2) ; ou en remplaçant 3>2 par n’importe quelle expression « logique » avec des opérateurs relationnels > < <= >= == != et logiques && || ! .

De même, il est convenu le plus souvent que les fonctions qui testent quelque chose et doivent renvoyer une valeur que nous (humains) comprenons comme « logique » renvoient en fait zéro pour « faux » et une valeur non nulle (le plus souvent un) pour « vrai ». C’est le cas par exemple de la fonction standard isalnum() qui permet de tester si un caractère donné est alphanumérique (une lettre de l’alphabet ou un chiffre) ou non (une espace, un caractère de ponctuation etc.).

En ce qui concerne notre fonction palindrome(), nous allons donc lui faire retourner un si la chaîne testée est un palindrome et zéro sinon (oui c’était déjà dans l’énoncé du TP, mais j’ai voulu expliquer ce choix).

Comme d’habitude il y a plusieurs façons de le faire. Le principe le plus habituel est de raisonner ainsi (par l’absurde ?) :

  • On considère que c’est un palindrome jusqu’à preuve du contraire : on initialise la valeur à renvoyer à un (vrai).
  • On compare chaque caractère d’indice i de la première moitié de la chaîne avec son symétrique par rapport au milieu, d’indice lg-i-1, lg étant la longueur de la chaîne : le premier (i=0) avec le dernier (lg-1=lg-0-1), le deuxième (i=1) avec l’avant-dernier (lg-2=lg-1-1), le troisième (i=2) avec l’avant-avant-dernier (lg-3=lg-2-1) etc.
  • On s’arrête soit quand on trouve une différence, qui prouve qu’on s’était trompé, et on renvoie alors zéro, soit quand on arrive au milieu de la chaîne sans trouver de différence, ce qui prouve qu’on avait raison, et on renvoie alors un.

En utilisant un indice entier et une boucle while par exemple :

int palindrome(char chaine[]) {
    int lg = strlen(chaine) ;
    int nodifference = 1 ;
    int i = 0 ;
    while (i < lg/2 && nodifference){
        nodifference = (chaine[i] == chaine[lg-i-1]) ;
        ++i ;
    }
    return nodifference ;
}

La variable nodifference indique si on a trouvé une différence entre les caractères comparés. On lui affecte 1 (vrai) au début (supposition de départ), puis le résultat de l’opération de comparaison (opérateur ==) qui, comme nous l’avons dit, est un entier valant 0 ou 1.

Pour faire plus joli (ça dépend des goûts), on peut aussi utiliser une boucle for, sachant que c’est exactement la même chose que la boucle while ci-dessus, et remplacer les lignes 4 à 8 par :

for (int i = 0 ; i < lg/2 && nodifference ; ++i)
    nodifference = (chaine[i] == chaine[lg-i-1]) ;

Remarque : la déclaration int i doit être faite avant le for si le compilateur ne connaît pas la norme ISO C99. Avec GCC, il suffit de compiler avec l’option -std=c99 pour qu’il la prenne en compte.

On peut aussi utiliser des pointeurs (pas pour frimer, mais pour s’entraîner). Examinons d’abord la fonction précédente : nous avons utilisé des crochets [] pour accéder aux éléments du « tableau » chaine, mais en réalité, chaine n’est pas un tableau, c’est un pointeur, et même si c’en était un, quand on utilise un tableau dans une expression, le compilateur le convertit en un pointeur qui contient son adresse en mémoire. La notation indicée avec des [] n’est qu’une commodité du C, faite pour rendre l’accès aux éléments d’un tableau plus facile. En réalité, quand on écrit t[0] c’est exactement la même chose que *t, c’est-à-dire l’élément dont l’adresse mémoire est t, et t[1] c’est exactement la même chose que *(t+1).

Que veut dire t+1 ? L’opérateur + ici n’est pas le même que celui de l’addition entière ou réelle, bien qu’il s’écrit de la même façon, c’est un opérateur de l’arithmétique des pointeurs.
L’opération t+1 ne signifie pas (adresse de t) + 1
mais plutôt adresse de l’élément de même type que *t qui le suit en mémoire.
De même, *(t-1) est l’élément de même type que *t qui le précède en mémoire,
*(t+2) ou t[2] est l’élément qui suit *(t+1).
Et *(t+i), que l’on peut noter t[i], est l’élément qui suit *(t+i-1) en mémoire.
Pour savoir quels sont les éléments qui suivent ou précèdent un pointeur, l’ordinateur doit connaître non seulement son adresse, mais aussi le type des éléments pointés : l’adresse qui suit un élément de type caractère ne serait pas la même s’il était de type réel (il prendrait plus de place en mémoire).

Reprenons donc notre fonction en changeant seulement la notation. Le compilateur le traduira exactement de la même façon, ce ne sera différent que pour nos yeux :

int palindrome(char *chaine) {
    int lg = strlen(chaine) ;
    int nodifference = 1 ;
    for (int i=0 ; i < lg/2 && nodifference ; ++i)
        nodifference = (*(chaine+i) == *(chaine+lg-i-1)) ;
    return nodifference ;
}

Maintenant, nous allons essayer de nous passer de i, et à la place, nous allons travailler avec un pointeur p qui va au fur et à mesure contenir l’adresse de chacun des caractères de la chaîne à parcourir. p va remplacer l’expression (chaine+i) de la fonction précédente, et donc à la place de i, nous allons mettre (p-chaine) : comme i, la différence entre l’adresse de p et celle de début de la chaîne correspondra au nombre de caractères déjà parcourus.

  • p est un pointeur initialisé avec l’adresse de début de la chaîne et sera incrémenté pour la parcourir.
  • on compare le caractère pointé avec son symétrique, c’est-à-dire celui dont l’adresse est chaine+lg-(p-chaine)-1
  • on s’arrête quand on a parcouru la moitié de la chaîne, c’est-à-dire quand (p-chaine) atteint lg/2, ou si on trouve une différence.
int palindrome(char *chaine) {
    int lg = strlen(chaine) ;
    int nodiff = 1 ;
    for (char *p = chaine ; p-chaine < lg/2 && nodiff ; ++p)
        nodiff = (*p == *(chaine+lg-(p-chaine)-1) ;
    return nodiff ;
}

Je ne sais pas ce que vous en pensez mais moi je ne trouve pas jolie l’expression (*p == *(chaine+lg-(p-chaine)-1). On peut la simplifier en enlevant les parenthèses : (*p == *(chaine+lg-p+chaine-1)).

On est tenté de simplifier encore en mettant (*p == *(2*chaine+lg-p-1)), mais cela ne fonctionnera pas à la compilation. Vous pourrez essayer, vous obtiendrez :

erreur: invalid operands to binary * (have ‘int’ and ‘char *’)

En effet, dans l’arithmétique des pointeurs, il n’y a que des + et des , pas de multiplications ni de divisions

Même l’expression (*p == *(chaine+chaine+lg-p-1)) n’est pas acceptée par le compilateur. Et pourtant nous n’avons fait que déplacer un terme vers la gauche. Elle provoque le message :

erreur: invalid operands to binary + (have ‘char *’ and ‘char *’)

On ne peut pas additionner deux pointeurs, cela n’a pas de sens.

Certains ont pensé à une autre solution, qui peut-être vous semblera plus esthétique :-) Elle consiste à utiliser deux pointeurs, p et q, qui seront initialisés en même temps, l’un à l’adresse du début de la chaîne (du 1er caractère) et l’autre à celle de la fin (du dernier). À chaque itération, on incrémente p et on décrémente q, en continuant tant qu’il n’y pas de différence entre les caractères pointés et que le milieu de la chaîne n’est pas atteint par p (ou par q si vous préférez, c’est kif-kif).

Voici ce que l’on obtient :

int palindrome(char *ch){
    int lg = strlen(texte);
    char *p, *q;
    for (p=ch, q=p+lg-1 ; (p-ch)<(lg/2) && (*p==*q) ; ++p, --q)
        ;
    return *p == *q;
}

Cela donne un exemple d’utilisation de l’opérateur virgule dans une boucle for, pour lequel vous trouverez des explications ici.

2. Allocation dynamique de la chaîne de caractère

Notre fonction palindrome() est faite pour examiner une chaîne de caractères déjà allouée. Pour l’essayer, nous pouvons d’ores et déjà l’utiliser avec un appel simple comme dans l’exemple ci-dessous :

int main(void){
    char chaine[] = "rester";
    printf("'%s' %s un palindrome.", chaine,
           palindrome(chaine)?"est":"n'est pas");
    return EXIT_SUCCESS;
}

Rappel : L’opérateur ternaire ? : permet de construire une expression conditionnelle condition?expression1:expression2 dont le résultat est expression1 si la condition est vraie ou expression2 si elle est fausse.

Ici, la ligne char chaine[] = "rester"; commande au compilateur d’allouer un tableau de 7 caractères et de l’initialiser avec les lettres du mot rester. En effet, elle est équivalente à :
char chaine[] = {'r','e','s','t','e','r',0};
L’allocation (la réservation) de la mémoire se fait de façon statique, pendant la compilation.

Je vous avais parlé à l’occasion de l’exercice 2 du TP4 d’une manière d’allouer dynamiquement de la mémoire, grâce à une nouveauté de la norme C99 : les tableaux à longueur variable. Ils sont utiles pour réserver de la mémoire de façon dynamique, pendant l’exécution, si on peut savoir pendant l’exécution quelle est la taille mémoire à allouer.

Dans ce TP, on nous demande d’utiliser une manière plus avancée d’allouer la mémoire en appelant des fonctions standard spéciales : malloc(), calloc(), realloc() et free().

Avant de les utiliser, je vous conseille d’examiner le manuel de ces fonctions en tapant la commande man malloc dans le terminal.

Ces fonctions sont déclarées dans le fichier d’en-tête stdlib.h. Il faut donc ajouter #include <stdlib.h> au début de notre programme pour les utiliser.
Les trois premières permettent de faire l’allocation dynamique de la mémoire. On indique en paramètre à l’une d’elles quelle est la taille à allouer, et elles s’occupent de réserver un bloc mémoire sur le tas (c’est comme ça qu’on appelle la partie de la mémoire faite pour cela). Ces fonctions vérifient qu’il y a assez de place, et si tout va bien, elles retournent en résultat un pointeur qui contient l’adresse du bloc mémoire alloué.
Si un problème empêche l’allocation (mémoire insuffisante par exemple), la fonction retourne la valeur NULL (qui est définie à zéro dans stdlib.h).
N’ignorez pas ces erreurs : elles ne sont pas si rares que vous pourriez le croire. Prenez toujours l’habitude de tester le résultat d’une fonction d’allocation pour prévoir une sortie en urgence en cas de problème. L’omission d’un test de ce genre entraîne parfois des bugs graves et difficiles à corriger. Mieux vaut prévenir que guérir.

Attention : il ne faut surtout pas oublier de faire le ménage avant de finir. En effet, si vous demandez la réservation d’un bloc de mémoire, vous en êtes responsable. Quand vous en aurez terminé avec, libérez-le pour qu’il puisse être utilisé par d’autres programmes. La quatrième fonction, free(), est là pour ça : on lui donne en paramètre un pointeur avec l’adresse du bloc mémoire alloué et elle le libère. Surtout, ne comptez sur personne pour le faire à votre place, ce serait comme laisser son plateau sur la table à la cantine après avoir fini de manger, c’est malpoli et ça dérange les autres. Souvent, le personnel de la cantine peut débarrasser après vous : les systèmes d’exploitation récents des PC libèrent la mémoire après la terminaison d’un programme… Mais ce n’est pas toujours le cas ! Vous serez peut-être un jour programmeurs pour des systèmes embarqués qui ne comportent pas de telles fonctionnalités. Et puis si vous ne prenez pas l’habitude de libérer la mémoire avec de petits programmes, quand vous participerez à des projets plus grands, votre code risque de causer des fuites de mémoire qui ralentiront le système et pourront causer de graves problèmes, surtout si ces programmes sont destinés à s’exécuter longtemps, voire continuellement.

Transformons notre fonction main() ainsi :

int main(void){
    char * chaine;
    chaine = malloc(100);
    if (chaine == NULL) {
        perror("Erreur d'allocation mémoire"); 
        exit(EXIT_FAILURE);
    }
    puts("Donnez un mot (sans espaces et < 100 lettres) :");
    scanf("%99s",chaine);
    printf("'%s' %s un palindrome.", chaine,
           palindrome(chaine)?"est":"n'est pas");
    free(chaine);
    return EXIT_SUCCESS;
}

sans oublier bien sûr #include <stdlib.h> au début.

Nous savons que la taille d’un caractère est, par définition, égale à un octet. C’est pourquoi nous avons demandé à malloc() de nous réserver un bloc de mémoire de taille 100. La taille maximale du mot demandé à l’utilisateur est de 99 lettres, puisqu’il faut prévoir la place de l’octet nul de fin de chaîne.

En cas d’erreur à l’allocation (si malloc() retourne la valeur NULL), nous affichons un message. Nous aurions pu le faire avec printf() ou puts() mais la fonction perror() est plus appropriée (elle ajoute le message d’erreur du système et affiche le tout sur la sortie d’erreur standard). Après l’affichage, une sortie en urgence est provoquée par la fonction système exit(), en lui demandant de renvoyer au système le code de sortie EXIT_FAILURE. Nous aurions pu également utiliser return EXIT_FAILURE;, cela donne le même résultat.

Remarque : le type de retour de malloc() est void * (pointeur générique) alors que nous voulons l’adresse d’un caractère, de type char *. On peut expliciter la conversion de type en utilisant un transtypage (ou cast) de cette façon :
chaine = (char *) malloc(100);
mais il faut savoir qu’en C standard la conversion de void * se fait de façon implicite (automatiquement, sans le demander) pendant une affectation (ce n’est pas le cas en C++ où le transtypage est obligatoire, mais on n’utilise pas malloc() en C++). Beaucoup de programmeurs C vous déconseilleront de transtyper le résultat de malloc() pour plusieurs raisons. Étant de nature paresseuse, je ne le fais pas moi-même mais je ne considère pas que c’est une erreur, alors vous êtes libres… (voir ici et here and here).

L’exemple ci-dessus est simple, mais on peut se demander quel est l’intérêt d’utiliser l’allocation dynamique dans ce cas. Puisqu’on fixe la taille du tableau à 100, pourquoi ne pas le déclarer de façon statique ? Parce que c’est demandé dans l’énoncé et que nous sommes obéissants :-) Non, sérieusement, on peut trouver une façon plus utile de se servir de l’allocation dynamique dans ce cas.
Au lieu de fixer la taille de la chaîne de caractères, on peut la faire augmenter au fur et à mesure qu’on lit chaque caractère entré par l’utilisateur grâce à realloc() qui permet de « réallouer » le bloc en changeant sa taille.

Dans ma solution finale ci-dessous, j’ai écrit une fonction qui permet de lire la chaîne de caractères de cette manière. Je détaille cette fonction dans ce billet.

/*
 *  EPST 2e année - 2012-2013
 *  TP5 - Allocation dynamique de la mémoire
 *  Exercice 1 : Palindromes
 *  Fichier source : palindrome.c
 *  Compiler avec :
 *  gcc -Wall -o palindrome palindrome.c -std=c99
 *  Auteur : Amine "nh2" Brikci-Nigassa
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <libgen.h>
#include <ctype.h>

#define MIN_BUFFER 7

/* utilisation : affiche l'aide sur l'utilisation du programme
 * Paramètre :
 *  - nom_prog : nom du programme
 */
void utilisation(char *nom_prog){
    printf("Utilisation : %s [CHAINE]\n",nom_prog);
    printf("Indique si une CHAINE de caractères est un palindrome ");
    puts("(i.e. reste la même quand elle est lue de droite à gauche).");
    printf("Utilisé avec un paramètre, %s renvoie ", nom_prog);
    puts("le code de sortie 0 si CHAINE est un palindrome, 1 sinon.");
    puts("Entourer CHAINE de guillemets si elle contient des espaces.");
    printf("Utilisé sans paramètre, le programme demande la ");
    puts("chaîne de caractères de façon interactive.");
    puts("N.B. : ne pas mettre de lettres accentuées dans CHAINE");
}

/* purge : met une chaîne en majuscules et élimine tout ce qui n'est pas
 *         alphanumérique (espaces, ponctuation, etc.)
 * Paramètre :
 *  -  texte : chaîne à 'purger'
 */
void purge(char *texte){
    char *q = texte;
    for (char *p = texte; *p ; ++p)
        if (isalnum(*p))
            *q++ = toupper(*p);
    *q = 0;
}

/* palindrome : détermine si une chaîne de caractères est un palindrome
 * Paramètre :
 *  - txt : chaîne de caractères à vérifier
 * Résultat : retourne 1 si c'est un palindrome, 0 sinon.
 */ 
int palindrome(char *txt){
    purge(txt);
    int lon = strlen(txt);
    if (lon == 0) return 0; // aucun caractère après la purge 
    char *p, *q;
    for (p=txt, q=p+lon-1 ; (p-txt)<(lon/2) && (*p==*q) ; ++p, --q)
        ;
    return *p == *q;
}

/* lire_chaine : affiche un message et lit une chaine de
 *       caractères (avec allocation dynamique)
 * Paramètre :
 *  -  message : invite à afficher
 * Résultat : retourne l'adresse de la chaîne créée
 *   dynamiquement contenant le texte lu ou NULL en cas
 *   d'échec.
 */
char * lire_chaine(char * message){
    printf("%s", message);
    size_t taillbuff = MIN_BUFFER;
    char *buffer = malloc(taillbuff);
    if (buffer == NULL) return NULL; // échec de malloc()
    char *p;
    for(p = buffer ; (*p = getchar()) != '\n' && *p != EOF ; ++p)
        if (p - buffer == taillbuff - 1) {       // buffer plein,
            p = realloc(buffer, taillbuff *= 2) ; // on le double
            if (p == NULL) {     // échec de realloc()
                free(buffer); 
                return NULL;
            } else buffer = p;  // bloc réalloué != buffer
            p += taillbuff/2 - 1; // p reprend sa place dans la 
        }                         // nouvelle zone
    *p = 0;
    p = realloc(buffer, p - buffer + 1);  // réajustement
    if (p == NULL) {          // échec de realloc
        free(buffer);
        return NULL;
    } else return p;
}

int main(int argc, char **argv){
    if ((argc > 2) || (argc == 2 && argv[1][0] == '-')) {
        utilisation(basename(argv[0]));
        return EXIT_FAILURE;
    } else if (argc == 2)
        return !palindrome(argv[1]);
    else { // (argc == 1) 
        char *texte = lire_chaine("Entrez une chaîne à tester : ");
        if (texte == NULL){
            fputs("Erreur d'allocation mémoire.",stderr);
            return EXIT_FAILURE;
        }
        printf("\n'%s' ",texte);
        printf(" %s un palindrome. \n", 
               palindrome(texte) ? "est" : "n'est pas" );
        /* montre la chaîne "purgée" :    */
        printf("\n(Chaîne testée : \"%s\")\n",texte);
        free(texte);
        return EXIT_SUCCESS;
    }
}
Publicités
Laisser un commentaire

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :