IN102

TD03a Les chaînes de caractères

Avant de commencer…

Consultez les corrections du TD02.

Qu’est-ce qu’on apprend

  1. Encodage des chaînes de caractères.
  2. Travailler avec les chaînes de caractères.
  3. Les chaînes servent comme une entrée dans le monde merveilleux des tableaux.

Attention: La bibliothèque string.h fournit un tas de fonctions pour travailler avec les chaînes. Le but de ce TD est de faire ces fonctions à la main, pour comprendre comment ça marche sous le capot. Donc, merci de ne pas utiliser les fonctions de string.h (strstr,strcmp,…), puisque sinon les exercices perdraient leur intérêt.

Lecture…

Chaînes de caractères:

Au boulot…

D’ailleurs : Pas de quizz pour le TD03.

IMPORTANT: Donnez votre prénom et nom au début du fichier de réponse, sous forme de commentaire. Ajoutez également les réponses aux questions dans votre programme, sous forme de commentaires. Exemple:

/* Jeanne LAGAFFE */
#include <stdio.h>
int main () {
   printf("Hello World !!\n");
}
/* 
Q1: Ceci est la réponse à la question 1.
Q2: Voilà la réponse à la question 2.
*/

Q1:

Ecrivez un programme qui stocke la chaîne suissesse dans une variable M, puis affiche le contenu de M avec printf.

Astuce: Utilisez le format %s de printf.

Q2:

Ecrivez une fonction

void affichage(char* ch)

qui affiche la chaîne ch suivi par un retour à la ligne. L’affichage doit être codé sans utilser le format %s de printf. Vous pouvez afficher les caractères uniquement en utilisant printf avec le format %c. Testez la fonction en l’appelant depuis main() pour afficher M.

Astuce: Pour parcourir la chaîne, utiliser une boucle while qui augmente un compteur i et qui s’arrête quand ch[i]==0.

Q3:

Ecrivez une fonction

int compter_lettre(char* ch, char x)

qui prend en entrée une chaîne de caractères ch et une lettre x et qui donne le nombre d’occurences de la lettre dans la chaîne. Testez la fonction en l’appelant depuis main() selon les exemples suivants:

  • compter_lettre("suissesse",'s') donne 5
  • compter_lettre("suissesse",'x') donne 0
  • compter_lettre("suissesse",'e') donne 2

Q4:

Ecrivez une fonction

int position(char* ch, char x)

qui parcourt la chaîne et donne la position (en partant de 0) de la première occurrence de la lettre dans x. Si il n’y a pas cette lettre, la fonction donne -1. Testez la fonction en l’appelant depuis main() selon les exemples suivants:

  • position("suissesse",'s') donne 0
  • position("suissesse",'x') donne -1
  • position("suissesse",'e') donne 5

Q5:

Attention, ça chauffe. Ecrivez une fonction

int position_chaine(char* ch, char* m)

qui parcourt la chaîne et donne la position (en partant de 0) de la première occurrence de la chaîne dans m. Si il n’y a pas cette chaîne, la fonction donne -1. Testez la fonction en l’appelant depuis main() selon les exemples suivants:

  • position_chaine("suissesse","ss") donne 3
  • position_chaine("suissesse","ee") donne -1
  • position_chaine("suissesse","suissesse") donne 0
  • position_chaine("suissesse","suissesses") donne -1

Anecdote: Le problème ci-dessus est connu sous le nom de l’algorithme de recherche de sous-chaîne. La plupart des algorithmes (même les bons) prennent dans le pire cas un temps qui est proportiennel à

\[\text{longeur de ch}*\text{longeur de m}.\]

Mais, en 1991, Maxime Crochemore et Dominique Perrin de l’université Paris 7 ont découvert un algorithme qui ne prend pas plus que

\[\text{longeur de ch}+\text{longeur de m}.\]

Pour des longues chaînes, ça fait une sacrée différence!

Validez:

Nommez le fichier T03a.c et envoyez-le à votre chargé de TD

Recherche