Le Langage C++

cours n° 6

Patrick TRAU 11/12/04

Cours n° 6

11) pointeurs, tableaux et chaînes

11.1) adresses, pointeurs et références

L'endroit où le compilateur a choisi de mettre une variable ou un objet est appelé adresse de la variable (c'est en général un nombre, chaque mémoire d'un ordinateur étant numérotée de 0 à ? ). Cette adresse ne nous intéresse que rarement de manière explicite, mais souvent de manière indirecte. Par exemple, dans un tableau, composé d'éléments consécutifs en mémoire, en connaissant son adresse (son début), on retrouve facilement l'adresse des différentes composantes par une simple addition. On appelle pointeur une variable dans laquelle on place (mémorise) une adresse de variable (où elle est) plutôt qu'une valeur (ce qu'elle vaut).

On déclare un pointeur par « type_pointé * nom; ». On obtient l'adresse d'un objet par l'opérateur &. Quand à l'opérateur * (dit d'indirection), placé devant un pointeur, il signifie « valeur pointée », j'aime aussi l'appeler « bout de la flèche » (voir schéma ci-dessous).

Voyons cet exemple. La gestion des adresses est simplifiée par rapport à la réalité.

int i,j;	Je déclare deux entiers i et j. Le compilateur cherche deux mémoires disponibles, supposons qu'il ait choisi les mémoires numéro 101 et 102.
int p,q;	Je déclare deux pointeurs d'entiers p et q. Ce sont deux variables (peut-être placées dans en 103 et 104)
p=&i;	quelle est l'adresse de i ? 101. Copions cette adresse dans p (qui ne doit contenir qu'une adresse d'entier)
*p=4;	mettons 4 dans l'entier pointé par p (donc en mémoire 100). Désormais i vaut 4.
q=&j;	q pointe sur j (il contient l'adresse de j)
q=(p)+2;	on place, dans la case pointée par q, la valeur pointée par p augmentée de 2

Quel est l'intérêt de cet exemple ? Uniquement de vous faire comprendre comment fonctionnent les pointeurs. Nous verrons plus tard des cas où l'on s'en sert (tableaux dynamiques par exemple).

En déclarant int &r; on crée une référence. C'est proche d'un pointeur, les deux principales différences sont :

en parlant de « r » on parle directement de la valeur pointée. Cela simplifie l'écriture du code en évitant toutes ces *. Mais contrairement à ce que pensent les débutants, ce n'est une simplification que si on parfaitement compris le mécanisme des pointeurs (on ne voit plus les pointeurs mais le fonctionnement et les risques restent les mêmes).
un pointeur est une variable, qui peut au cours du temps comporter des adresses différentes. Une référence pointe toute sa durée de vie sur la même variable (donc r++ est interdit).

En fait, les références sont surtout pratiques pour le passage d'arguments et retour des fonctions (voir le chapitre sur les fonctions), pour le reste ne vous en servez pas dans un premier temps.

11.2) tableaux unidimensionnels statiques

Un tableau est le regroupement en une seule variable de plusieurs éléments (tous les éléments doivent être de même type, mais celui-ci peut être complexe). Avant tout, il faut déclarer le tableau. Le mieux est de déclarer d'abord (de manière globale) comment sera le (ou les) tableau :

typedef type_elements type_tableau[nombre_d_elements];

Par exemple, si l'on déclare :

#define DIM 100
typedef float tableau[DIM];

Alors on a défini qu'un tableau sera un regroupement de 100 flottants. Mais on n'a toujours pas réellement créé de tableau, ceci se fait, comme les autres variables, en déclarant (en local si possible) :

type_tableau liste de variables;

dans notre exemple, pour créer deux tableaux on écrira :

tableau x,y;

On accède aux éléments d'un tableau par

nom_du_tableau[indice]

L'indice est un entier qui permet de désigner quel élément précis on désire. C'est obligatoirement un entier, mais ce peut être une constante (x[5]), une variable (x[i]), ou même toute expression qui retourne un entier (x[(2*a+b)/3]). L'indice du premier élément d'un tableau est 0. Pour traiter tous les éléments d'un tableau, il faut :

expliquer comment traiter le i^ième
insérer ce traitement dans une boucle pour traiter tous les i (du premier au dernier).

Par exemple pour mettre à 0 tout le tableau x déclaré précédemment :

for(i=0;i<DIM;i++) x[i]=0;

L'intérêt principal d'un tableau n'est donc pas de regrouper plusieurs valeurs, mais bien de regrouper des valeurs sur lesquelles on désire faire le même traitement, les mêmes calculs.

Une grosse limitation de ces tableaux est que la dimension (nombre d'éléments réservés lors de la déclaration) doit être connue lors de la compilation, alors qu'on aimerait souvent pouvoir la décider lors de l'exécution. La seule solution est de prévoir, lors de la compilation, une dimension suffisante, et de n'utiliser qu'une partie du tableau lors des exécutions. Par exemple, si je sais que je n'ai jamais plus de 100 étudiants dans une promo, et que je veux mémoriser les notes des GSI2 et des LTM :

#define MAX 100
typedef float notes[MAX];
notes gsi2, ltm;
int i, nb_gsi2, nb_ltm;
cout<<"nb de GSI ? ";
cin>>nb_gsi2;
cout<<"nb de LTM ? ";
cin>>nb_ltm;
for(i=0;i<nb_gsi2;i++)
 {
  //traitement de tous les gsi2[i]
 }
for(i=0;i<nb_ltm;i++)
 {
  //traitement de tous les ltm[i]
 }

11.3) exemple 1 (objet comportant un tableau)

Pour commencer, voici un exemple de définition d'une classe permettant de d'utiliser des polynômes (exemple : 5x⁴+2x³-x+2). Un certain nombre de problèmes nécessitent d'utiliser des polynômes. Un polynôme est caractérisé par son degré (ici 5) et ses coefficients (ici 5,2,0,-1,2 si on les donne du poids fort au poids faible). Ce programme définit une classe de polynômes, avec une certain nombre de méthodes qui seront utiles dans tout programme devant traiter des polynômes. Le programme principal donné ici n'est là que pour tester si notre classe est correcte. Vous pouvez voir le code dans une seconde fenêtre, télécharger le source (bouton droit) ou la version pdf.

On se limite aux polynômes de degré 19 maximum. Un polynôme est donc défini par deux attributs : son degré, et un tableau contenant ses coefficients. Comme (presque) toujours pour mes objets, les attributs sont privés. Ils sont accessibles en lecture (get_degre et get_coef), mais pas modifiables directement. Par contre on peut modifier leur valeur, par exemple via les méthodes saisie, copie ou raz. Certaines méthodes n'ont besoin d'aucun argument (par exemple raz) car l'accès aux attributs leur suffit. D'autres ont besoin d'un argument, comme additionner : il faut dire ce que l'on veut additionner au polynôme. On peut remarquer qu'ici j'ai utilisé la surcharge : j'ai donné le même nom à l'addition d'un flottant et à celle d'un autre polynôme.

Comment appelle-t-on cette addition ? Si j'ai déclaré deux polynômes p1 et p2, alors p1.additionner(3.5); additionne le flottant à p1, et p1.additionner(p2); additionne les deux polynômes, mais seul p1 est modifié (puisque c'est à lui qu'on applique la méthode).

J'ai également surchargé les opérateurs afin qu'ils s'appliquent aux polynômes (là aussi avec surcharges suivant les types d'arguments.

11.4) les chaînes de caractères

En C, comme dans les autres langages, certaines fonctionnalités ont été ajoutées aux tableaux afin de traiter du texte. En C, on représente les chaînes par un tableau de caractères, dont le dernier est un caractère de code nul (\0). Une constante caractères est identifiée par ses délimiteurs, les guillemets " (double quote).

exemples :

 cout<<"salut";
 char mess[]="bonjour"; /* évite de mettre ={'b','o',..,'r','\0'} */
 cout<<(mess);

mess est un tableau de 8 caractères (\0 compris). On peut au cours du programme modifier le contenu de mess, à condition de ne pas dépasser 8 caractères (mais on peut en mettre moins, le \0 indiquant la fin de la chaîne). On peut également initialiser un pointeur avec une chaîne de caractères :

 char *strptr="bonjour";

Le compilateur crée la chaîne en mémoire, et une variable strptr contenant l'adresse de la chaîne. Le programme pourra donc changer le contenu de strptr (et donc pointer sur une autre chaîne), mais pas changer le contenu de la chaîne initialement créée.

En C++, il y a une classe spécifique pour les chaînes de caractères : les « string ». Ils sont associés à de nombreuses méthodes, bien utiles en cas d'utilisation importante de chaînes de caractères.

Mais déjà en C, la bibliothèque de chaînes (inclure string.h) possède des fonctions utiles à la manipulation de chaînes :

int strlen(chaîne) donne la longueur de la chaîne (\0 non compris)

char *strcpy(char *destination,char *source) recopie la source dans la destination, rend un pointeur sur la destination (dest=source quand à lui ne recopie pas la chaîne mais uniquement son adresse !). Faites attention de ne pas dépasser la dimension de la destination, sinon utilisez le suivant.

char *strncpy(char *destination,char *source,int longmax) idem strcpy mais s'arrête au \0 ou longmax (qui doit comprendre le \0)

char *strcat(char *destination,char *source) recopie la source à la suite de la destination, rend un pointeur sur la destination

char *strncat(char *destination,char *source,int longmax) idem, mais plus sûr

int strcmp(char *str1,char*str2) rend 0 si str1= =str2, <0 si str1<str2, >0 si str1>str2 (classé alphabétiquement, donc test du premier caractère, si différents test du second, etc...) Les majuscules sont différentes des minuscules (inférieures). Idem pour strncmp, qui lui vérifie la dimension.

Des fonctions similaires, mais pour tous tableaux (sans s'arrêter au \0) sont déclarées dans mem.h. La longueur est à donner en octets (on peut utiliser sizeof) :

int memcmp(void *s1,void *s2,int longueur);
void *memcpy(void *dest,void *src,int longueur);

Dans ctype.h, on trouve des fonctions utiles (limitées au caractères) :

int isdigit(int c) rend un entier non nul si c'est un chiffre ('0' à '9'), 0 sinon. De même : isalpha (A à Z et a à z, mais pas les accents), isalnum (isalpha||isdigit), isascii (0 à 127), iscntrl (0 à 31), islower (minuscule), isupper, isspace (blanc, tab, return...), isxdigit (0 à 9,A à F,a à f)...

int toupper(int c) rend A à Z si c est a à z, rend c sinon (attention, les accents ne sont pas gérés). Egalement tolower

11.5) exemple 2 (objets utilisant les chaînes de caractères, tableau d'objets)

Vous pouvez voir le code dans une seconde fenêtre, télécharger le source (bouton droite) ou la version pdf. Cet exemple est volontairement assez court, je n'ai mis qu'un minimum de méthodes pour voir comment ça fonctionne, dans un cas pratique j'aurais bien entendu prévu bien plus de méthodes.

Pour commencer, dans cet exemple, j'ai défini un type « chaîne de 20 caractères » nommé tnom.

Un étudiant possède les attributs nom (de type tnom), et deux notes (TP et exam). Comme à mon habitude, ces attributs sont privés, on ne peut y accéder que par les accesseurs. D'ailleurs, un utilisateur de la classe dispose d'un accesseur à la note moyenne, sans savoir qu'en fait cette note n'est même pas mémorisée dans l'objet mais recalculée à chaque fois. Pour le nom, je n'ai prévu comme accesseur que la saisie au clavier et l'affichage à l'écran.

Une méthode permet de comparer le nom de l'étudiant avec un nom donné en argument (le résultat sera celui de strcmp, donc un entier positif, négatif ou nul). Il serait pratique de surcharger les opérateurs de comparaison = =, <, etc...

Puis dans cet exemple j'ai créé une classe « promo » contenant un tableau d'étudiants (100 au maximum). nb représente le nombre réel d'étudiants, car bien que j'ai réservé de la place pour 100, je peux en utiliser une partie uniquement (mais pas plus). Une fois de plus, à l'extérieur de la classe on ne sait pas comment sont gérés les attributs : ici, bien que les indices du tableau aillent de 0 à 99, on accède aux étudiants par un numéro entre 1 et 100. Ici aussi on utilise la surcharge : la méthode « affiche » est prévue avec trois signatures différentes : sans arguments, tous les étudiants sont affichés. Avec un argument entier n, seul le n^ième étudiant est affiché. Avec un argument de type tnom, l'étudiant portant ce nom est affiché (donc ses notes), du moins s'il existe.

11.6) équivalence d'écriture pointeurs et tableaux

En déclarant, par exemple, int TAB[10]; l'identificateur TAB correspond en fait à l'adresse du début d'un tableau de 10 entiers. Les deux écritures TAB et &TAB[0] sont équivalentes (ainsi que TAB[0] et *TAB). On définit l'opération d'incrémentation pour les pointeurs par : TAB+1<=>adresse de l'élément suivant du tableau. L'arithmétique des pointeurs en C a cette particularité que l'opération dépend du type de variable pointée, ajouter 1 consistant à ajouter à l'adresse la taille de l'objet pointé. On définit donc l'addition (pointeur+entier) : TAB+i <=> &TAB[i], la soustraction (pointeur - entier), mais également la soustraction (pointeur - pointeur) qui donne un nombre d'éléments. Les opérations de comparaisons entre pointeurs sont donc également possibles.

Déclarons : int TAB[10],i,*ptr;

Ceci réserve en mémoire

la place pour 10 entiers, l'adresse du début de cette zone est TAB,
la place pour l'entier i,
la place pour un pointeur d'entier (le type pointé est important pour définir l'addition).

Analysons les instructions suivantes :

ptr=TAB; /*met l'adresse du début du tableau dans ptr*/
for(i=0;i<10;i++)
 {
  cout<<"entrez la "<<i+1<<"ième valeur :\n";  // +1 pour commencer à 1
  cin>>*(ptr+i);    // ou TAB[i] 
 }
cout<<"affichage du tableau";
for(ptr=TAB;ptr<TAB+10 /* ou &TAB[10] */;ptr++)
  cout<<*ptr;
cout<<"\n";
// attention actuellement ptr pointe derrière le tableau ! 
ptr-=10; // ou ptr=TAB qui lui n'a pas changé 
cout<<*ptr+1;   // affiche (TAB[0])+1 
cout<<*(ptr+1); // affiche TAB[1]
cout<<*ptr++;   // affiche TAB[0] puis pointe sur TAB[1]
cout<<(*ptr)++; // affiche TAB[1] puis ajoute 1 à TAB[1]

TAB est une "constante pointeur", alors que ptr est une variable (donc TAB++ est impossible). La déclaration d'un tableau réserve la place qui lui est nécessaire, celle d'un pointeur uniquement la place d'une adresse.

Quand on passe un tableau en argument d'une fonction, on ne peut que le passer par adresse (recopier le tableau prendrait de la place et du temps). Voyez cet exemple utilisant les deux écritures équivalentes :

void annule_tableau(int *t,int max)
 {
  for(;max>0;max--)*(t++)=0;
 }
void affiche_tableau(int t[], int max)
 {
  int i;
  for(i=0;i<max;i++) cout<<i<<":"<<t[i])<<"\n";
 }
int main(void)
 {
  int tableau[10];
  annule_tableau(tableau,10);
  affiche_tableau(tableau,10);
 }

Il aurait néanmoins été plus simple de définir le type tableau et l'utiliser partout :

typedef int tabint[10];

void annule_tableau(tabint t,int max)   //le même bloc d'instructions
void affiche_tableau(tabint t, int max) //le même bloc
int main(void)
 {
  tabint tableau;
  annule_tableau(tableau,10);
  affiche_tableau(tableau,10);
 }

11.7) tableaux dynamiques

Les tableaux définis jusqu'ici sont dits « statiques », car il faut qu'au moment de l'écriture du programme le programmeur décide de la taille maximale que pourra atteindre le tableau, sans exagérer pour ne pas consommer trop de mémoire. Mais grâce à l'équivalence d'écriture tableaux-pointeurs, on peut créer des tableaux dont la dimension n'est définie que lors de l'exécution. Exemple :

int* tab; //tab est pointeur, il contiendra l'adresse d'un entier, en fait le premier du tableau.
int nb;
cout<<"combien d'éléments ? "
cin>>nb;
tab=new int[nb]; //ceci réserve de la place pour nb entiers, met l'adresse du premier dans tab.

désormais on peut utiliser tab comme un tableau classique (et écrire tab[i]). On peut même libérer la place prise par le tableau par l'instruction :

delete[] tab; //attention, n'oubliez pas les crochets !!

Mais si vous ne le faites pas, la mémoire sera de toute façon libérée à la fin du programme.

Les tableaux dynamiques sont donc aussi faciles à utiliser que les tableaux statiques, c'est une caractéristique importante du C++. Ils ne sont néanmoins pas totalement dynamiques : il faut connaître la dimension avant la première utilisation du tableau. Nous ne pourrons donc pas facilement faire un programme qui demande « entrez vos valeurs, terminez par -1 » mais « combien de valeurs ? » puis « entrez vos valeurs ».

11.8) tableaux d'objets, de tableaux...

On peut faire un tableau de n'importe quel type d'éléments. Par exemple, voici une matrice 10,10 :

#define DIM10
typedef float ligne[DIM]; //une ligne contient 10 float
typedef ligne matrice[DIM]; //une matrice contient 10 lignes
matrice m;
m[5][2]=0; //on met 0 dans la ligne d'indice 5, colonne d'indice 2.

On peut également faire un tableau de pointeurs (et donc de tableaux dynamiques), un tableau d'objets contenant eux-même des tableaux...

autre exemple de déclaration (partielle, il manque des attributs et méthodes) :

class date {int j,m,a;};
class produit {char reference[10];float prix;};
class facture {date d;int nbproduits;produit p[20];};
class compta {facture f[1000];};
compta livre;

livre contient au maximum 1000 factures. livre.f[499].p[0].reference[1] correspond au deuxième caractère de la référence du premier produit de la 500ème facture du livre.

11.9) algorithmes pour les tableaux

Supposons maintenant avoir une classe, quelle qu'elle soit, contenant différents attributs, les méthodes saisie, affiche; les accesseurs permettant d'obtenir une valeur (qui servira pour classer les objets). Appelons cette classe « element ». Définissons maintenant une classe « tableau » qui contient un tableau regroupant plusieurs éléments. Nous pouvons alors créer les méthodes saisie et affiche, qui utilisent les méthodes des éléments. Vous pouvez voir le code dans une seconde fenêtre, télécharger le source (bouton droite) ou la version pdf de cette version de départ. Nous allons maintenant développer des méthodes utiles pour les tableaux (Vous pouvez voir le code, télécharger le source (bouton droite) ou la version pdf du programme complet).

Pour commencer, pour rechercher un élément d'une valeur donnée, la méthode la plus simple consiste à balayer tout le tableau jusqu'à ce qu'on trouve la valeur désirée (si on arrive à la fin du tableau, cela signifie que la valeur n'est pas présente dans le tableau). Par contre, si le tableau est trié, on peut rechercher par dichotomie : regarder si l'élément du milieu est plus grand ou plus petit, pour en déduire s'il faut continuer à chercher dans la première ou la seconde moitié du tableau. Puis recommencer avec le milieu, et ainsi de suite.

Pour rajouter un élément dans le tableau, si c'est à la fin c'est facile, il suffit de le mettre au bout et d'ajouter 1 à nb (du moins s'il restait de la place). Par contre si c'est à insérer entre les autres, il faut d'abord faire un décalage. Imaginez qu'on ait des voitures dans une suite de garages. Pour en insérer une (sans changer l'ordre), il faut tout décaler : décaler la dernière d'un cran (c'est la seule place de libre actuellement), puis décaler l'avant-dernière, et continuer jusqu'à ce que le box destination soit libre pour y insérer la nouvelle voiture. Pour supprimer un élément, contrairement aux voitures, il n'est pas nécessaire de vider un élément du tableau pour pouvoir l'écraser par un autre (et une fois de plus, il faut tout décaler, puisqu'on les veut continues et dans l'ordre). Pour supprimer la dernière, il suffit de soustraire 1 à nb, même en laissant la valeur puisqu'on ne regarde jamais au delà des nb premières valeurs.

Avant de trier, on commence par prévoir quelques méthodes qui nous serviront. Pour échanger deux valeurs, il faut (comme les voitures) : en stocker une dans un endroit temporaire, déplacer l'autre (qui maintenant ne risque plus d'écraser la première), puis ranger la première. Une seconde méthode nous permet de chercher l'élément le plus petit, depuis une position donnée du tableau jusqu'à la fin (pour chercher dans tout le tableau il suffit de lui dire de chercher à partir de 0) : on suppose que le premier est le plus petit (pp), puis on teste tous les autres, à chaque fois qu'on en trouve un encore plus petit on remet à jour pp, arrivé au bout pp ne peut être que la position du plus petit. La troisième recherche la position (à partir du début) du premier élément plus grand que celui donné en argument (si jamais il n'en trouve pas, il retourne nb, c'est à dire la première position libre).

Pour trier, je vous propose trois algorithmes : le tri bulle consiste à comparer chaque élément avec son voisin. Si l'ordre n'est pas bon, on échange les deux. Ce tri est facile à mettre en oeuvre mais est complètement idiot dans la plupart des cas, car une valeur va faire de multiples « sauts de puce » avant d'arriver à sa position définitive. Le tri sélection est bien plus malin : chaque échange met une des deux valeurs dans sa position définitive, l'autre par contre étant déplacé moins intelligemment : on cherche le plus petit, on le place en première position (en l'échangeant avec celui qui y était). Puis on ne s'occupe plus que de ceux qui restent, en cherchant le plus petit et le mettant en seconde position, etc... Troisième proposition (pas très efficace dans le cas des tableaux, mais utile dans d'autres cas) : le tri insertion. C'est l'algorithme que vous utilisez pour trier vos cartes à jouer : vous comparez la deuxième carte avec la première. Si elles ne sont pas dans le bon ordre, on sort la deuxième et on l'insère au début. Puis on teste la troisième, si elle n'est pas bien placée par rapport aux précédentes, on la sort et on la réinsère à la bonne position. Puis on vérifie la quatrième, etc...

Enfin un petit programme permet de tester ces méthodes.

Patrick TRAU, ULP - IPST décembre 04