Skip to content

EPST 2e année – TP3

20 novembre 2012

Dans ce TP, vous allez faire « tourner » des chaînes de caractères…
Merry-go-round !
Pas vraiment comme dans un manège, mais un peu comme dans les panneaux d’affichage défilant.
Texte en rotation


Je vous conseille de bien réfléchir avec un stylo dans la main et une feuille de brouillon…

Comme d’habitude, il y a plusieurs façons d’obtenir le résultat cherché. Voici quelques méthodes que j’ai observées chez certains élèves :

  • On déclare une nouvelle variable pour le résultat et on traite la chaîne en deux parties, avec deux boucles for qui se suivent (non imbriquées) :
    • l’une traite la partie qui sera décalée
    • l’autre traite la partie qui passera à l’autre bout de la chaîne

Ce qui donne pour la fonction gauche() :

void gauche(char * texte, int r, char * resultat){
    int n = strlen(texte);
    r = -r ;    // rend r positif (plus clair)
    for (int i = 0 ; i < (n-r) ; ++i ){
        resultat[i] = texte[i+r];
    }
    for (int i = n-r ; i < n ; ++i ){
        resultat[i] = texte[i-n+r];
    }
    resultat[n] = 0; // caractère nul en fin de chaîne
 }
  • Certains ont utilisé la même méthode mais avec une seule boucle for et une instruction conditionnelle if qui teste l’indice incrémenté :
   for (int i = 0 ; i < n ; ++i ){
       if (i < (n-r))
           resultat[i] = texte[i+r];
       else
           resultat[i] = texte[i-n+r];
   }
  • D’autres ont choisi de modifier la chaîne originale et obtenir le résultat dans la même variable chaîne pour économiser la mémoire. Le problème qui se pose alors, c’est comment déplacer des caractères sans écraser les autres. Une solution proposée considère que le tableau de caractères est plus grand que la chaîne originale, et il y a assez de place à droite pour transférer la partie gauche. Ensuite on fait un décalage à gauche du reste :
   for (int i = 0 ; i < n+r ; ++i ){
       if (i < r)
           texte[n+i] = texte[i];
       else
           texte[i-r] = texte[i];
   }
   texte[n] = 0; // caractère nul en fin de chaîne

Pour la rotation à droite c’est aussi simple, on décale tout à droite puis on transfère les r derniers caractères à gauche :

   for (int i = n+r-1 ; i >= 0 ; --i ){
       if (i >= r)
           texte[i] = texte[i-r];
       else
           texte[i] = texte[n+i];
   }
   texte[n] = 0; // caractère nul en fin de chaîne</code></p>

Rappel : les caractères qui suivent le caractère nul sont ignorés ; ils ne font pas partie de la chaîne.

Remarquez que si cette méthode économise la mémoire, elle est cependant plus longue à l’exécution puisqu’elle nécessite r itérations de plus que les précédentes.

  • Certains m’ont demandé s’il n’existait pas une fonction en C qui permet de transférer une portion d’une chaîne de caractères vers une autre. Je leur ai montré les fonctions  strcpy() et strncpy() dans le manuel (n’oubliez pas la commande man d’Unix : vous pouvez taper man strncpy dans le shell pour tout savoir sur la fonction strncpy). Ils les ont utilisées pour copier les r derniers caractères vers le début de l’autre chaîne, on utilise strcpy (resultat, texte+n-r, r) ; pour copier les r premiers vers la fin, on fait l’inverse : strcpy(resultat+n-r, texte, r). En effet, resultat et texte sont des tableaux mais sont convertis par le compilateur en des pointeurs contenant l’adresse de leur premier élément ; l’arithmétique des pointeurs permet de trouver l’adresse de début de la sous-chaîne à copier.
  • La méthode que j’ai préférée a été trouvée par certains en réfléchissant à la suite des indices des caractères à copier. Si on considère que i et j sont les indices des chaînes initiale et finale respectivement et n leur taille, pour une rotation de r caractères à droite on ajoute à chaque fois r, c’est-à-dire : j = i + r sauf quand j dépasse n, alors on revient à zéro. Ça ne vous rappelle rien ? L’indice j est en fait le résultat de (i + r) modulo n. Ce qui, en C, s’écrit j = (i + r) % n ;

Pour une rotation à gauche, c’est presque kif-kif : on ne peut pas faire j = (i - r) % n car on aurait des problèmes quand i-r <0 mais rappelez vous, en maths, k+n ≡ k [n] donc on peut ajouter n et  calculer à la place j = (i - r + n) % n ;

Ce qui permet d’obtenir la solution suivante :

void gauche(char t1[], char t2[], int r){
   n = strlen(t1);
   for (i = 0; i < n; i++){
       j = (i + n + r) % n ;   // car r < 0
       t2[j] = t1[i];
   }
}
void droite(char t1[], char t2[], int r){
   n = strlen(t1);
   for (i = 0; i < n; i++){
       j = (i + r) % n ;
       t2[j] = t1[i];
   }
}
  • Vous voyez bien qu’il y a toujours plein de façons de faire. Et ce n’est pas fini ! En regardant bien la méthode ci-dessus, vous remarquerez qu’on peut ramener la rotation à droite à la même formule que la rotation à gauche : on peut également faire  j = (i + r + n) % n puisque ajouter ne change rien ! Et on se retrouve alors avec ma solution (ou presque) :
    /*
     *  EPST 2e année - 2012-2013
     *  TP3 - Manipulation des chaînes de caractères - Rotation de texte
     *  Fichier source : tp3.c
     *  Compiler avec :
     *  gcc -Wall -o tp3 tp3.c -std=c99
     *  Solution par Amine "nh2" Brikci-Nigassa
     */
     
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define LIGNE 80
    
    /* rotation : rotation d'une chaîne de caractères
     * Paramètres : 
     *  -  texte : chaîne originale
     *  -  r : nombre de caractères de la rotation
     *  -  resultat : chaîne obtenue après la rotation
     */
    void rotation(char * texte, int r, char * resultat){
        int n = strlen(texte);
        for (int i = 0 ; i < n ; ++i ){
            resultat[i] = texte[(i - r + n) % n];
        } 
        resultat[n] = 0; // la chaîne doit finir par '\0'
    }
     
    int main(void){
        char texte[LIGNE];
        printf("Le texte original est : ");
        fgets(texte, LIGNE, stdin);
        texte[strlen(texte)-1] = 0;  // enlève '\n' pris par fgets
    
        int nbre;
        printf("Le nombre de caractères dont on doit tourner le texte: ");
        scanf("%d",&nbre);
        
        char resultat[strlen(texte)+1]; // ne pas oublier le '\0'
        printf("\nLe texte en sortie : ");
        rotation(texte, nbre, resultat);
        puts(resultat);
        
        return EXIT_SUCCESS;
    }
    

    Remarque : fgets permet de mettre des espaces dans le texte.

    Remarque : Si vous oubliez de mettre le caractère nul de fin de chaîne, il est possible que votre programme fonctionne quand même. Faites attention : si votre chaîne de caractère est déclarée comme variable globale, en dehors de toute fonction, le compilateur l’initialise automatiquement en remplissant le tableau de zéros MAIS si vous l’avez déclarée comme variable locale, dans une fonction (main() ou une autre), alors son contenu n’est pas initialisé automatiquement et il contient des valeurs indéterminées, qui peuvent être des zéros mais qui peuvent aussi changer d’une exécution à l’autre. Je vous conseille donc de prendre vos précautions : mieux vaut mettre à zéro une valeur qui était déjà nulle que se retrouver avec un bug caché qui attend de vous mordre !

    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 :