Séance d'exercices 8, Programmation I

Sciences et Technologies du Vivant, Semestre 1

Exercice 1 - Tableaux, chaînes de caractères et pointeurs

Le but de cet exercice est de revenir en détail sur le fonctionnement des chaînes de caractères et de bien comprendre la relation entre une chaîne, un tableau et un pointeur. Prenez-donc soin de lire attentivement les explications qui suivent.

Ecrivez un nouveau programme. Commencez par déclarer une variable chaîne de caractères de longueur 8 que vous nommerez nom.
```
      char nom[8];
```
Demandez ensuite à l'utilisateur d'entrer un nom et stockez-le dans la variable nom que vous venez de déclarer.
```
      cin >> nom;
```
La figure 1 illustre ce qui se passe dans la mémoire de l'ordinateur à l'exécution du programme, après que l'utilisateur a entré un nom (ici Dupont). On remarquera que
- le compilateur a alloué de la mémoire pour 8 caractères;
- la variable nom est en fait une constante contenant l'adresse du premier caractère de la chaîne (= premier élément du tableau);
- la fonction cin a stocké la chaîne entrée par l'utilisateur dans l'espace mémoire sur lequel pointe la variable nom;
- la fonction cin a ajouté un caractère fin de chaîne (\0) à la fin du nom;
- en déclarant une chaîne de 8 caractères, on ne pourra stocker que 7 caractères utiles au maximum, car la chaîne doit obligatoirement se terminer par \0.
Figure 1: Représentation d'une chaîne de caractres en mémoire
$\begin{figure}\begin{center} % \input{fig/memoire.pstex_t} \end{center} \end{figure}$
Ajoutez, à la fin de votre programme, une instruction permettant d'afficher à l'écran le nom contenu dans la variable nom. Compilez et testez votre programme. Essayez d'entrer un nom faisant plus de 7 caractères. Vous devriez constater que le programme fonctionne quand même et affiche correctement (et entièrement) le nom que vous avez entré.

Figure 2: Dépassement de la mémoire allouée
$\begin{figure}\begin{center} % \input{fig/memoire2.pstex_t} \end{center} \end{figure}$

La figure 2 illustre ce qui se passe dans ce cas-là. On voit que la commande cin n'effectue aucune vérification de taille. Elle stocke simplement la chaîne entrée par l'utilisateur à partir du début de la zone mémoire pointée par la variable nom. Si la chaîne est plus grande que la zone allouée, elle va simplement la dépasser. Avec un peu de chance, cela ne va pas écraser des données importantes et le programme va quand même fonctionner. Cependant, si vous essayez d'entrer une chaîne vraiment grande (une cinquantaine de caractères) vous constaterez que le programme va planter, car des données importantes vont être écrasées.
Il est donc très important de prévoir suffisamment de place pour la chaîne que va entrer l'utilisateur. Changez la déclaration de la variable nom et allouez-lui 128 caractères, ce qui devrait être largement suffisant pour stocker un nom.
Vous allez maintenant ajouter une variable pointeur sur char nommée prenom:
```
      char *prenom;
```
Comme nous l'avons vu en cours, la variable nom[8] est une constante qui contient l'adresse du premier élément du tableau. Au contraire, prenom est un pointeur sur char. En d'autres termes, c'est une variable qui contient l'adresse d'une variable char.

Figure 3: Occupation mémoire des deux variables nom et prenom
$\begin{figure}\begin{center} % \input{fig/memoire3.pstex_t} \end{center} \end{figure}$

Il y a deux différences fondamentales entre les variables nom et prenom.
1. Bien que les deux contiennent l'adresse d'un char, nom est une constante et pointera toujours sur le premier élément du tableau. A l'opposé, prenom est un pointeur et pourra donc contenir n'importe quelle adresse.
2. Lors de la déclaration d'un tableau (char nom[8]), le compilateur alloue automatiquement de la mémoire pour stocker tous les éléments du tableau. Lorsqu'on déclare prenom, aucune allocution de mémoire n'est faite et le pointeur pointe sur rien.
Si l'on veut stocker une chaîne de caractères dans prenom il faudra tout d'abord lui allouer de la mémoire. Pour ce faire ajoutez la ligne suivante après la déclaration de prenom:
```
      prenom = new char[128];
```
Figure 4: La mémoire après l'allocation dynamique de prenom
$\begin{figure}\begin{center} % \input{fig/memoire4.pstex_t} \end{center} \end{figure}$

La figure 4 montre le contenu de la mémoire après l'instruction new. On y voit qu'une nouvelle zone mémoire a été allouée et que prenom pointe à présent sur cette zone.
Peut-on utiliser les deux instructions
```
      char chaine1[10];
```
et
```
      char *chaine2 = new char[10];
```
de manière équivalente ? Mis à part la différence de type des deux variables (char[10] vs. char *), leur utilisation présente deux différences importantes:
- la mémoire allouée pour chaine1 sera supprimée automatiquement par le compilateur à la fin de sa portée. Au contraire, la mémoire allouée pour chaine2 devra être supprimée manuellement par le programmeur en appelant l'instruction delete:
```
	delete[] chaine2;
```
- on ne peut utiliser l'allocation char chaine1[10]; que lorsqu'on connaît la taille du tableau à la compilation (i.e. en écrivant le programme). Si la taille du tableau est déterminée à l'exécution, il faut utiliser l'allocation dynamique à l'aide de la commande new. Exemple:
```
	int n;
	cin >> n;
	char *chaine2 = new char[n];
```
Un nom propre commence toujours par une majuscule. Vous allez implémenter une fonction qui vérifie que la première lettre d'une chaîne est bien une majuscule et la modifie au besoin. Commencez par écrire l'en-tête de la fonction
```
      void majuscule(char *mot)
```
Notez bien qu'on ne déclare pas ici la variable mot, comme on l'avait fait pour nom. On spécifie juste le type de paramètre à passer à la fonction majuscule.
Il faut à présent vérifier que le premier caractère de mot est une majuscule. Pour accéder au $i^{eme}$ caractère de la chaîne, il suffit d'utiliser la syntaxe
```
      mot[i]
```
vu qu'une chaîne n'est rien d'autre qu'un tableau de caractères.
On se rappellera qu'on peut comparer les caractères entre eux. Ainsi, pour vérifier qu'un caractère est en majuscule, il suffit de s'assurer qu'il se trouve entre 'A' et 'Z', y compris. Ajoutez donc le code suivant à votre fonction:
```
      if (mot[0] >= 'A' && mot[0] <= 'Z')
```
Si le premier caractère est bien en majuscule, il n'y a plus rien à faire et on peut quitter la fonction en appelant l'instruction return. Sinon, il faut remplacer la première lettre par sa version capitalisée.
Si vous consultez la table des caractères (septième slide du cours 8), vous remarquerez qu'il y a une différence constante de 32 caractères entre un caractère minuscule et le même caractère en majuscule. Pour transformer un caractère minuscule en majuscule, il suffit donc de lui soustraire 32. Faites-le en ajoutant la ligne suivante à votre fonction:
```
      mot[0] = mot[0] - 32;
```
La fonction majuscule est désormais terminée. Pour la tester, appelez votre fonction en lui passant comme paramètre la variable nom. Ajoutez cette instruction juste avant d'afficher le nom à l'aide de cout.
Revenons un instant sur l'en-tête de la fonction majuscule. Vous avez écrit char mot[128] pour indiquer au compilateur que la fonction reçoit un tableau de 128 caractère. Cependant, le compilateur ne se préoccupe pas de la taille du tableau. Ce qui lui importe, c'est de connaî tre l'adresse du premier élément. Pour cette raison, il est totalement équivalent de définir le paramètre de la fonction comme un pointeur sur char:
```
      void majuscule(char *mot)
```
Remplacez l'en-tête de la fonction par la version ci-dessus et testez votre programme. Vous constaterez qu'il n'y a absolument aucune différence.
Vous avez déclaré plus haut deux variables pour stocker le nom et le prénom d'une personne. Vous allez maintenant créer une fonction qui va réunir nom et prénom à l'intérieur d'une seule nouvelle chaîne. Votre fonction aura l'en-tête suivant:
```
      char *concatenation(char *mot1, char *mot2)
```
Avant d'allouer de la mémoire pour la nouvelle chaîne dans laquelle seront stockées les variables mot1 et mot2, il nous faut déterminer sa taille. Vous allez le faire à l'aide de la ligne suivante:
```
      int longueur = strlen(mot1) + strlen(mot2) + 2;
```
La taille en question vaut la taille de mot1 + la taille de mot2 + un espace entre les deux + le caractère final (\0). La fonction strlen nous permet de déterminer la longueur d'une chaîne de caractères. Pour pouvoir l'utiliser, il faut cependant déclarer #include <string.h> au début du programme.
Maintenant que la taille de la nouvelle chaîne est connue, vous pouvez la déclarer et lui allouer de l'espace mémoire. Au point 3, nous avons vu qu'il y a deux manières de le faire: char mot3[longueur] et char *mot3 = new char[longueur]. Dans le cas présent, il est impératif d'utiliser la deuxième solution. En allouant la chaîne avec la première solution, elle serait automatiquement désallouée lorsque l'on sort de la fonction concatenation, et donc inutilisable par la suite. D'autre part, la taille de la nouvelle chaîne n'est pas connue au moment de la compilation, ce qui nous force également à utiliser l'allocation dynamique.
Après avoir déclaré mot3, il va falloir y copier mot1 et mot2. Pour cela, vous pouvez utiliser la fonction strcpy. Ajoutez la ligne suivante à votre fonction:
```
      strcpy(mot3, mot1);
```
Ceci aura pour résultat de copier la chaîne mot1 au début de mot3. La figure 5 illustre l'état de la mémoire après l'appel à strcpy. On voit que mot1 a été copié au début de mot3 et que strcpy a également copié le caractère terminal (\0).

Figure 5: La mémoire après avoir utilisé strcpy
$\begin{figure}\begin{center} % \input{fig/memoire5.pstex_t} \end{center} \end{figure}$

Comme nous désirons introduire un espace entre les deux mots, il faut maintenant l'insérer au bon endroit dans mot3. Ajoutez la ligne suivante
```
      mot3[strlen(mot1)] = ' ';
```
Puisque la longueur de mot1 est strlen(mot1), l'espace sera inséré juste après le mot1 (n'oubliez pas que le premier élément d'un tableau est à l'indice 0). Notez que l'espace écrasera le caractère terminal (\0) ajouté par strcpy.
La prochaine étape consiste à copier mot2 dans mot3. Il convient de bien réfléchir, car la commande strcpy(mot3, mot2) copierait mot2 au début de mot3 en écrasant les caractères que nous avons déjà copiés. Vous savez que mot3 est un pointeur qui pointe sur le premier caractère de la chaî ne. Or, nous aimerions copier mot2 après le caractère espace. Nous devons donc avoir un pointeur sur le caractère qui suit l'espace. Cela s'obtient simplement en additionnant strlen(mot1)+1 au pointeur mot3 (comme illustré sur la figure 6). Pour copier le second mot, il vous faut donc ajouter la ligne
```
      strcpy(mot3 + strlen(mot1) + 1, mot2);
```
Figure 6: La mémoire après le second appel à strcpy
$\begin{figure}\begin{center} % \input{fig/memoire6.pstex_t} \end{center} \end{figure}$

Sur la figure 6, vous pouvez voir que la fonction est maintenant terminée. Il ne reste plus qu'à retourner mot3 en écrivant return mot3.
Pour tester votre fonction, demandez à l'utilisateur d'entrer un prénom (dans main, bien sûr). Creez une variable nom_complet et initialisez-là à l'aide de la fonction concatenation.
```
      char *nom_complet = concatenation(prenom, nom);
```
Vous pouvez ensuite afficher nom_complet. Comme nom_complet a été alloué à l'aide de new (dans la fonction concatenation), il appartient au programmeur de libérer la mémoire. Pour finir, désallouez prenom et nom_complet avec delete.

**Figure 1:** Représentation d'une chaîne de caractres en mémoire
$\begin{figure}\begin{center} % \input{fig/memoire.pstex_t} \end{center} \end{figure}$

**Figure 2:** Dépassement de la mémoire allouée
$\begin{figure}\begin{center} % \input{fig/memoire2.pstex_t} \end{center} \end{figure}$

**Figure 3:** Occupation mémoire des deux variables `nom` et `prenom`
$\begin{figure}\begin{center} % \input{fig/memoire3.pstex_t} \end{center} \end{figure}$

**Figure 4:** La mémoire après l'allocation dynamique de `prenom`
$\begin{figure}\begin{center} % \input{fig/memoire4.pstex_t} \end{center} \end{figure}$

**Figure 5:** La mémoire après avoir utilisé `strcpy`
$\begin{figure}\begin{center} % \input{fig/memoire5.pstex_t} \end{center} \end{figure}$

**Figure 6:** La mémoire après le second appel à `strcpy`
$\begin{figure}\begin{center} % \input{fig/memoire6.pstex_t} \end{center} \end{figure}$

Exercice 2 - Arguments

Ecrivez un programme addition, dont le but sera d'additionner les deux arguments passés au programme en ligne de commande. Il s'utilisera comme ceci:
```
jerome@cosunrays1 ~$ ./addition 21 24
21 + 24 = 45
```
Le programme devra donc additionner les deux arguments et afficher le résultat de l'addition. Avant toute opération, prenez soin de vérifier que l'utilisateur a bien passé deux arguments. Comme les arguments d'un programme sont toujours de type chaîne de caractères, il faudra les convertir en int pour pouvoir les additionner. Cela peut se faire à l'aide de la fonction atoi (man atoi pour plus d'information).
Ecrivez à présent un programme division, affichant le résultat de la division (réelle) des deux arguments du programme. Cette fois-ci, faites attention au cas particulier d'une division par 0.
Finalement, écrivez un programme intitulé somme. Celui-ci devra effectuer et afficher la somme d'un nombre quelconque d'arguments. Exemple d'utilisation:
```
jerome@cosunrays1 ~$ ./somme 1 2 3 4 5 6 7 8
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
```

Exercice 3 - Séquences génétiques

Un brin d'ADN est formé de la répétition ordonnée des quatre bases adénine, guanine, thymine et cytosine. On écrit généralement une séquence d'ADN en juxtaposant les initiales des quatres bases (selon la Table 1).

Tableau 1: Les 4 nucléotides de l'ADN et leur représentation

G	Guanine
A	Adenine
T	Thymine
C	Cytosine

Du point de vue informatique, une séquence ADN peut être simplement représentée par une chaîne de caractéres contenant les lettres A, G, T et C représentant les quatre bases de l'ADN. Exemple:

    char *sequence_adn = "ACGGTAGCTAGTTTCGACTGGAGGGGTA";

Dans cet exercice, vous allez vous entraîner à manipuler des séquences d'ADN à l'aide de chaînes de caractères.

Commencez par copier la fonction main ci-dessous dans une nouvelle fenêtre Emacs. Elle vous servira à tester les fonctions que vous allez écrire dans les points suivants.

int main(int argc, char **argv) {
  char seq1[512], seq2[512];

  do {
    cout << "Entrez une sequence ADN: ";
    cin >> seq1;
  } while (!adn_valide(seq1));

  do {
    cout << "Entrez une seconde sequence ADN: ";
    cin >> seq2;
  } while (!adn_valide(seq2));
  
  if (compare(seq1, seq2))
    cout << "Les deux sequences sont identiques." << endl;
  else
    cout << "Les deux sequences sont differentes." << endl;

  cout << "'" << seq1 << "' transcrit en ARN vaut '";
  adn_to_arn(seq1);
  cout << seq1 << "'" << endl;

  cout << "Le complementaire de '" << seq2 << "' vaut '" 
       << complementaire(seq2) << "'" << endl;
  return 0;
}

Ecrivez une fonction
```
      bool adn_valide(char *sequence)
```
qui vérifie si la séquence passée en argument est bien une séquence ADN valide, c.-à-d. si elle est composée uniquement de caractères A, G, T et C. La fonction devra retourner true si la chaîne est valide et false si elle ne l'est pas.
Afin de tester votre fonction, écrivez la fonction main dans laquelle vous demanderez à l'utilisateur d'entrer une séquence ADN et afficherez si elle est valide ou non.
Ecrivez maintenant une fonction qui compare deux séquences ADN et retourne true si les deux séquences sont similaires et false sinon. La fonction aura l'en-tête suivant:
```
      bool compare(char *seq1, char *seq2)
```
Indice: si deux séquences n'ont pas la même longueur, il est clair qu'elles seront différentes. Il n'est dès lors pas utile de les comparer caractère par caractère.
Les nucléotides de l'ARN sont les mêmes que pour l'ADN sauf la thymine (T) qui est remplacée par l'uracile (U).
Ecrivez une fonction qui transcrit une séquence ADN en ARN, en remplaçant tous les T par des U. Utilisez l'en-tête de fonction suivante:
```
      void adn_to_arn(char *adn).
```
Notez bien que la séquence d'ADN est passée par référence (pointeur). Votre fonction va donc modifier la chaîne originale. Notamment, l'instruction suivante
```
      char *sequence = "ACGGTAGCTAGTTTCGACTGGAGGGGTA";
      adn_to_arn(sequence);
```
ne va pas fonctionner, car sequence est une chaîne de caractères constante qu'on ne peut modifier.
Les deux brins antiparallèles d'ADN sont toujours étroitement reliés entre eux par des liaisons hydrogène, formées entre les bases complémentaires A-T et G-C. Ces deux brins d'ADN sont dit complémentaires car les purines (Adénine et Guanine) d'un brin font toujours face à des pyrimidines de l'autre brin (Thymine et Cytosine). Ainsi, l'adénine est complémentaire de la thymine et la guanine est complémentaire de la cytosine.
Ecrivez une fonction qui retourne le complémentaire d'une séquence ADN. Pour ce faire, il suffit de remplacer chaque nucléotide de la séquence par son complémentaire. Pour cette fonction, vous utiliserez le prototype suivant:
```
      char *complementaire(char *seq_originale)
```
Contrairement à la fonction du point précédent, vous n'allez pas modifier la séquence passée en paramètre, mais vous allez allouer une nouvelle chaî ne de caractères dans laquelle vous stockerez la séquence complémentaire. Après avoir calculé la séquence complémentaire, la fonction retournera un pointeur sur la nouvelle chaîne.

Exercice 4 - Conversion $\dagger$

Ecrivez une fonction qui convertit une chaîne de caractères contenant un entier positif en int. La fonction prendra une chaîne de caractères en paramètres et retournera un int. Si la chaîne de caractères contient des caractères non-valides (autres que les chiffres de 0 à 9), la fonction devra retourner 0. Contrairement à l'exercice 2, il ne faut pas utiliser atoi, sinon l'exercice serait trivial.

Exercice 5 - Palindrome $\dagger$

Ecrivez une fonction qui demande à l'utilisateur d'entrer une chaîne de caractères et qui vérifie si celle-ci est un palindrome. Un palindrome est un mot qui s'écrit de la même manière à l'endroit et à l'envers. Exemple:

    sms est un palindrome
    stylo n'est pas un palindrome
    ressasser est un palindrome

Retour

Séance d'exercices 8, Programmation I Sciences et Technologies du Vivant, Semestre 1