Algorithmique & structures de données 1

5. Tableaux & chaines de caractères

59
Algorithmique & structures de données 1

5.1 Introduction
Si le nombre de variables -de même type- à traiter est important, il n’est pas
adéquat de les nommer X1, X2, ….Xn. Il serait intéressant de les rassembler dans
une seule structure où chaque variable sera accessible par son indice. Cette
variable est un tableau unidimensionnel ou tableau linéaire qui est une variable
indicée permettant de stocker n valeurs de même type. Le nombre maximal
d'éléments précisé à la déclaration représente la dimension du tableau. Le type du
tableau est le type de ses éléments.

Dans un tableau tous les éléments sont homogènes de même type, La position
d'un élément du tableau s'appelle indice ou rang de l'élément. La dimension est
le nombre d’éléments du tableau.

5.2 La déclaration du type tableau

Un tableau est caractérisé par:
- Son nom (identificateur).
- Sa taille (le nombre d’éléments).
- Le type de ses éléments.
- Les indices pour accéder aux éléments du tableau.

T
20 i=1→T[1]=20
12 i=2→T[2]=12
5
i=3→T[3]=5
T[1] …
………….

Remarque importante: en C, l’indice commence à 0 et non à 1, le premier

élément du tableau sera donc référencé par T[0].
Syntaxe 1
Type Nom_Tableau= Tableau [1..taille] de type_element
Variable nomVariable : Nom_Tableau

Exemple :
Type T=Tableau [1..10] de entier ;
Variable Tab :T ;/* T et Tab de même type*/

60
Algorithmique & structures de données 1

Syntaxe 2
nom [taille] : type des elements ;
T[n] : type des éléments;
Avec T: nom du tableau et n le nombre des éléments.
C’est la syntaxe 2 qui sera élaborée dans ce cours
: On ne doit jamais dépasser la capacité du tableau
Implémentation en C
On déclare un tableau (statique) par type, identificateur, et le nombre d’éléments
du tableau. La dimension n du tableau indique une réservation statique (à
l’avance) de n cases contiguës et de même type en mémoire.
type identificateur [longueur];
Exemples :

Langage algorithmique En C
Tab[200] : Réel ; Float Tab[200] ;
T [100] : Entier ; int T [100] ;
nom [20] : caractère ; char nom [20] ;
Constante max=100; #define max 100
Tab[max]: réel; Float Tab[max] ;

Astuce : define est une macro de précompilation « # » elle servira à remplacer

max par la valeur déclarée dans toutes les occurrences de celle-ci avant la
compilation du programme .

5.2.1 Accès aux éléments d’un tableau

Les éléments d’un tableau sont des cases rangées successivement dans la RAM.
Les éléments d’un tableau sont numérotés par des indices. Par exemple, les
éléments du tableau Tab déclarés ci-dessous, qui comporte 10 éléments. Les
indices sont schématisés en dessous du tableau : 1, 2, ... , 10. Les éléments sont
du tableau sont donc les valeurs 20, 30, …i.e le contenu de tab[1], tab[2], tab[3]...

Tab[1] : valeur du tableau d’indice i=1

20 30 40 90 60 70 80 99 100 50
1 2 3 4 5 6 7 8 9 10

Tab désigne le nom du tableau (qui sera aussi l’adresse du premier élément).
61
Algorithmique & structures de données 1

L’élément d’indice 3 dans le tableau Tab est noté Tab [3].

Plus généralement, l’élément d’indice i dans le tableau tab est noté tab[i].

L’indice i doit impérativement être un nombre entier positif ou nul, il peut aussi
être représenté par une expression arithmétique qui une fois calculée donne un
entier.

Exemple 1 : tab [3*m+2], où m est un entier.

Exemple 2 : Algorithme qui remplit les valeurs (2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
dans un tableau Tab.
Algorithme tableau
Début
Tab [10], i : entier;
pour i de 1 à 10 faire
Tab [i] ← 2*i; // on pouvait sans boucle écrire tab[10] = {2,4,6,…}
fin pour;
Fin.

En langage C, nous avons signalé que les indices des éléments d’un tableau
commencent à 0 et non pas à 1. On verra par la suite que ceci est dû au fait que le
nom du tableau désigne aussi l’adresse du premier élément.

5.2.2 Saisie et affichage d’un tableau

 Lecture
La lecture (saisie) d’un tableau, c’est le remplir, ceci nécessite l’utilisation d’une
boucle. Pour un tableau en général, il est préférable d’utiliser une boucle
« pour » qui porte sur l’indice.

Syntaxe Langage algorithmique Implémentation en C

Pour i de 1 à 10 faire for (i=0; i<10; i++)
Ecrire (“donnez la valeur de la {
case [“,i, “]“) ; printf ("donnez la valeur de la case
[%d] : ", i);
Lire (T[i]) ; Scanf ("%d", &T[i]);
Fin faire }

62
Algorithmique & structures de données 1

Lire (T[1]) →c’est introduire par le clavier la valeur 20

Lire (T[2]) →c’est introduire par le clavier la valeur 30

………

Lire (T[10]) →c’est introduire par le clavier la valeur 50

T [1] : première valeur du tableau d’indice i=1

20 30 40 90 60 70 80 99 100 50
1 2 3 4 5 6 7 8 9 10

En Mémoire centrale, les adresses des cases du tableau se suivent (du moins
pour les caractères ou entiers).

Adresse mémoire valeur

T[0] 00001100 10
T[1] 00001101 20
00001010 30
00001011 40
……….
 Ecriture :
L’écriture signifie l’affichage des valeurs qui ont été introduites à l’écran
En Algorithmique Implémentation en C
Pour i de 1 à 10 faire for (i=0; i<10; i++)
Ecrire (« la case »,i, « contient la printf ("la case %d contient la valeur
valeur », T[i]) %d ", i, T [i]);
Fin pour

L’affichage à l’écran donnera (en exécution C)

La case 0 contient la valeur 20→T[0]
La case 1 contient la valeur 30→T[1]
La case 2 contient la valeur 40→T[2]
……………………………
Remarquer l’obligation de ‘<’ et non ‘<=’ car l’indice commence à 0.

63
Algorithmique & structures de données 1

4.3 Les Matrices ou tableaux à deux dimensions

Un calendrier, une table de multiplication, un bulletin de notes sont des
exemples de tableaux à deux dimensions. Vous avez peut être joué à la bataille
navale ou utilisé Excel qui est un tableur. Le principe est le même, nous avons
besoin de deux indices pour accéder à l’information, celle-ci se trouve à
l’intersection d’une ligne et d’une colonne.

4.3.1 Définition
Une matrice est tableau à deux dimensions avec n lignes et m colonnes ; on parlera
de matrice carrée si n=m.
Colonnes 1,m

a11 a12 a13 a14 ….. a1m

Lignes 1, n
a21 a22 a23 a24 ….. a2m

an1 an2 an3 an4 …..anm

Figure 5.1 matrice

On note généralement aij l’élément qui se trouve à la ième ligne et jème colonne où
0<i< =n et 0<j < =m.

4.3.2 Déclaration d’une matrice

Un tableau à deux dimensions (matrice) est caractérisé par deux cardinalités
(nombre de ligne) et (nombre de colonnes).

Dans la figure précédente n représentera le nombre de lignes, m le nombre de

colonnes, i est l’indice pour les lignes et j l’indice pour les colonnes.

De la même façon, nous pouvons imaginer des tableaux à plusieurs dimensions

(> 2), c’est le nombre d’indices utilisés qui déterminera la dimension de celle-ci.

Syntaxe 1
On déclare une matrice à deux dimensions de la façon suivante :
Type Nom_Matrice = Tableau [nombre_lignes, nombre_colonnes ] de nom_type
Variable nom Variable: Nom_Matrice ;

64
Algorithmique & structures de données 1

Exemple

Type Matrice =Tableau [10,12] de entier ;

Variable M : Matrice ;
Syntaxe 2
nom [nb_ligne, nb_colonne] : type d’éléments
Voir d’autres exemples ci contre

Langage En C
algorithmique
M[200,300] : Réel ; Float M[200][300] ;

T [100,100] : Entier ; int T [100][100] ;

Constante max=100; #define max 100

Tab[max,max]: réel; Float Tab[max][max] ;

4.3.3 Accès aux éléments d’une matrice

Dans une matrice, l’élément est désigné par l’identifiant de la matrice et sa
position représentée par deux indices ( i indice pour les lignes et j indice pour les
colonnes ).

Identifiant [indice ligne, indice colonne]

M[i , j] : élément positionné à la ième ligne et jème colonne.

Exemple :

Soit la matrice M [4,6] avec 4 lignes et 6 colonnes contenant des entiers naturels.
1 2 3 4 5 6
1
12 30 20 90 100 62
2 5 5 3 4 5 20
3 200 45 89 52 5 10
4 90 12 1 3 2 12

M[1,2] = 30 valeur à la 1ère ligne et 2ème colonne

65
Algorithmique & structures de données 1

4.3.4 Saisie et affichage d’une matrice (Lecture et écriture)

Le traitement de matrices nécessite d’utiliser des boucles imbriquées.
 Lecture :
Pour remplir une matrice on aura besoin de boucles imbriquées. Le remplissage
se fait ici ligne par ligne.
Pour i de 1 à n faire
Pour j de 1 à m faire
Ecrire (“donnez la valeur de la case [“,i, ,j, “]“) ;
Lire (M[i,j]) ;
Fin pour ;
Fin pour ;
 Ecriture
Syntaxe
Pour i de 1 à n faire
Pour j de 1 à m faire
Ecrire (“la ligne“,i, “et la colonne “,j, “contient la valeur“, M[i,j]) ;
Fin pour ;
Fin pour // on peut écrire aussi par abus fpour, fait, ou fpr
Exemple :

Ecrire un algorithme qui calcule et affiche l’addition de deux matrices de réelles

M1 et M2 de dimensions M et N.
Algorithme matrice
Constante N=100, M=100;
Variables M1[N, M], M2[N, M], S[N, M] : réel;
i, n, m : entier;
Début
Ecrire ("Veuillez saisir le nombre des lignes (≤ 100)");
lire (n);
Ecrire ("Veuillez saisir le nombre des colonnes (≤ 100)");
lire (m);
/*remplissage de la matrice M1*/
pour i de 1 à n faire
pour j de 1 à m faire
lire ( M1[i, j]);
fin pour;
fin pour;

66
Algorithmique & structures de données 1

/* Remplissage de la matrice M2*/

pour i de 1 à n faire
pour j de 1 à m faire
lire( M2[i, j]);
fin pour;
fin pour;
/* calcul de la matrice somme */
pour i de 1 à n faire
pour j de 1 à m faire
S[i, j] ← M1[i, j] + M2[i, j];
fin pour;
fin pour;
/* affichage de la nouvelle matrice résultat*/
pour i de 1 à n faire
pour j de 1 à m faire
Ecrire ("s [" , i , " , " , j , "] : " , s [i, j] );
fin pour;
fin pour;
Fin.
Remarque importante: dans un souci d’optimisation, nous pouvions réunir les
partie calcul et affichage dans la même boucle imbriquée. Nous aurons alors la
portion de code suivante :
/* calcul et affichage de la matrice somme */
pour i de 1 à n faire
pour j de 1 à m faire
S[i, j] ← M1[i, j] + M2[i, j];
Ecrire ("s [" , i , " , " , j , "] : " , s [i, j] ); // instruction ajoutée
fin pour;
fin pour;

4.4 Les Tableaux et chaines de caractères

4.4.1 Définition d’une chaine de caractères

Une chaîne de caractères est un tableau de caractères se terminant par le
caractère spécial ’\0’ (qui a 0 pour code ASCII).

Nom

b e n b e l l a \0 Nom[9] :caractère ;

67
Algorithmique & structures de données 1

Généralement, les tableaux de type caractère sont initialisés une liste d’éléments
du tableau fournis entre accolades.
Exemple :
Algorithme nom

Début
nom[20] : caractère;
nom[] = { ‘I’, ‘G’, ‘M’ ,’O’ , ‘\0’ } ; /* initialisation*/
Fin.

4.4.2 Traitement de chaînes de caractères

Fonctions fréquemment utilisés en C.

 Strlen (chaine) : fournit la longueur d’une chaine.

 Strcpy (chaine1,chaine2): copie la chaine 2 vers la chaine 1.
 Strcat (chaine1,chaine2): colle la chaine 2 à la fin de la chaine 1.
 Strcmp (<s>, <t>) compare les chaînes de caractères <s> et <t> de manière
lexicographique .

Exemple 1 : utilisation de strcmp

#include<stdio.h>
#include<string.h>
int main()
{
char chaine1[20], chaine2[20];
printf(" Entrez la 1ère chaine ");
gets(chaine1);
printf(" Entrez la 2ème chaine ");
gets (chaine2);
if (strcmp(chaine1,chaine2) == 0)
printf(" Les deux chaînes sont égales.\n");
else
printf(" Les deux chaînes ne sont pas égales.\n");
return 0;
}

68
Algorithmique & structures de données 1

Exemple 2 : utilisation de strcpy

#include<stdio.h>
#include<string.h>
main()
{
char chaine1[10]="etudiant";
char chaine2[10]="Licence";
strcpy(chaine1,chaine2);
printf("%s\n%s\n",chaine1,chaine2);
}

Exemple 3 : utilisation de strlen

#include<stdio.h>
#include<string.h>
int main () {
charch [] = "licence ";
printf("La longueur de %s est : %d",ch,strlen(ch));
}

4.4.3 Tableaux de chaines

On peut définir des tableaux de caractères à plusieurs dimensions qui peuvent
contenir des chaines de caractères.

Exemple :
Algorithme jour
Début
jour [7,9] : caractères ;
jour [7, 9] = {”dimanche”, “lundi” , ”mardi” , ”mercredi” , ”jeudi” , ”vendredi”,
”samedi”, };
Ecrire (“Aujourd’hui c’est : ”, jour[2]);
Fin
Soit la matrice jour[7,9]
j=1
j=1 j=2
j=2 j=3
j=3 j=4
j=4 j=5
j=5 j=6
j=6 j=7
j=7 j=8
j=8 j=9
j=9
i=1 dd II mm aa nn cc hh ee \0\0
i=1
i=2 ll uu nn dd ii \0\0
i=2
i=3 m aa rr dd ii \0\0
i=3 m
i=4 m ee rr cc rr ee dd i i \0\0
i=4 m
i=5 jj ee uu dd ii \0\0 69
i=5
i=6 vv ee nn dd rr ee dd i i \0\0
i=6
i=7 ss aa mm ee dd ii \0\0
Algorithmique & structures de données 1

Enfin, on dit qu’un tableau est trié si ses éléments sont classés par ordre croissant
(ou décroissant) ; cela facilite la recherche d’un élément.

Implémentation en C
#include<stdio.h>
main()

{
char JOUR[7][9]= {"dimanche"}, "lundi", "mardi",
"mercredi", "jeudi", "vendredi", "samedi"}
int i = 2;
printf ("Aujourd'hui, c'est %s !\n", JOUR[i]);
}
Les tableaux et matrices sont très utilisés en calcul numérique. Par exemple
en exercice vous pouvez calculer la valeur d’un polynôme de degré n en
représentant ses coefficients dans un tableau de même dimension. Des langages
comme Matlab possèdent des fonctions intégrées qui manipulent ces structures de
données (produit scalaire, produit matriciel, inverse de matrice …)
Remarques

Les tableaux de chaînes sont mémorisés ligne par ligne. La variable JOUR aura
donc besoin de 7*9*1 = 63 octets en mémoire. Il est possible d'accéder aux
différentes chaînes de caractères d'un tableau, en indiquant simplement la ligne
correspondante.

Soit float t[]= {.6, .8, 9.8 }, on aura 3 flottants sachant que la taille d’un float
simple en C est de 4 octets ce qui donne 3*4 octets .

Exemple : 0x10, 0x11,0x12 et 0x13 pour T[0] ;

0x14, 0x15,0x16 et 0x17 pour t[1] ,

et 0x18, 0x19, 0x20, 0x21 pour t[2].

Le programme n’aura pas à se soucier de ce problème c’est le compilateur qui

prendra les 4 cases à partir de l’adresse 0x14.

70
Algorithmique & structures de données 1

4.5 Enoncés des exercices d’application

Exercice 5.1
Soit un tableau de n cases entières, écrire un algorithme qui somme les valeurs
positives et négatives de ce tableau.
Exercice 5.2
Ecrire un algorithme qui affiche l’indice de la première occurrence d’une valeur
x si elle existe sinon il affiche -1.
Exercice 5.3
Ecrire un algorithme qui tri un tableau par ordre croissant.
Exercice 5.4
Ecrire un programme C qui inverse les éléments d’un tableau.
Option (non corrigé) permuter les éléments des deux diagonales en utilisant un
seul indice.
Exercice 5.5
Ecrire un programme en C qui sépare un tableau T en deux tableaux contenant
respectivement les éléments positifs et négatifs de T.
Exercice 5.6
Ecrire un programme C qui déclare une matrice, saisit les éléments de la matrice
et additionne les éléments de la matrice.
Exercice 5.7
Ecrire un programme C qui met à zéro les éléments de la diagonale principale
d'une matrice carrée.

Exercice 5.8
Ecrire un algorithme qui fait la fusion de deux tableaux d’entiers triés par ordre
croissant

Exercice 5.9
Soit une matrice M (nxm) de réels. On voudra créer un tableau T de n éléments
où chaque élément est la somme des éléments d’une ligne correspondante de la
matrice : T[i] est la somme de la ligne i, pour i allant de 1 à n. (Faire de même
pour les colonnes dans un autre tableau P).

71
Algorithmique & structures de données 1

Corrigés
5.1
Algorithme tableau
T [50] : entier ;
Variables i, n, SP, SN :entier ;
Debut
Ecrire (“donnez la dimension du tableau<50“) ;
Lire (n) ;
SP0 ;
SN0 ;
Pour i de 1 à n faire
Ecrire (“donnez la valeur de la case [“,i, “]“)
Lire (T [i]) ;
Si (T [i]>=0) alors SPSP+T [i] ;
Sinon SNSN+T [i] ;
Ecrire (“La somme des valeurs positives est “, SP, “et la somme des valeurs
négatives est “, SN ) ; // en fait les valeurs nulles seront ajoutées avec les valeurs négatives
fpour ;
Fin.
5.2
Algorithme recherche
Variables N, i, X, V[100]: entier
Début
Ecrire (‘donnez la dimension du tableau<100’) ;
Lire (N) ;
Pour i de 1 à N faire
Lire (V[i]) ;
Fin pour
Lire (X) ; /* saisie par le clavier de la valeur à chercher */
i←0 ;
Répéter
i=i+1 ;
jusqu'à i>N ou V[i]=X
/* on sort de la boucle soit la valeur a été trouvée soit le tableau a été parcouru
jusqu’à la fin */
Si i=N+1 ;
Alors ecrire (-1) ; /* élément non trouvé */

72
Algorithmique & structures de données 1

Sinon ecrire (i) ; /* élément trouvé à la position i */

Fin si
Fin.
Astuce : ici la boucle répéter ou tant que est mieux indiquée ; elle est utilisée
pour arrêter la boucle dès que l’élément est trouvé.
5.3
Algorithme tri
T [100] :réel ;
variables N ,i,j: entiers ;
variable temp: réel ;
Debut
Ecrire (‘donnez la dimension du tableau<100’) ;
Lire (N) ;
Pour i de 1 à N-1 Faire
Pour j de i+1 à N Faire
Si T[i] > T[j] alors
temp← T[i] ;
T[i]← T[j] ;
T[j] ← temp ;
Fin si ;
Fin pour;
Fin pour;
Fin.
5.4
#include<stdio.h>
main()
{
int T[50];
int N;
int I,J; /* indices courants */
int tmp; /* variable temporaire pour l’échange */
/* Saisie des données */
printf ("Donnez la dimension du tableau<50: ");
scanf("%d", &N );
for (I=0; I<N; I++)
{
printf("%d : ", I);
scanf("%d", &T[I]);}
73
Algorithmique & structures de données 1

/* Affichage du tableau */
printf("affichage : \n");
for (I=0; I<N; I++)
printf("%d ", T[I]);
printf("\n");
/* Inverser le tableau */
for (I=0, J=N-1 ; I<J ; I++,J--)
/* Echange de T[I] et T[J] */
{
tmp = T[I];
T[I] = T[J];
T[J] = tmp;
}
/* affichage */
printf("Tableau résultat :\n");
for (I=0; I<N; I++)
printf("%d ", T[I]);
printf("\n");
return 0;
}
Astuce : on pouvait aussi se passer de la variable j et faire l’échange de T[i]
avec T[N-i+1].
5 .5
#include<stdio.h>
main()
{
int T[50], P [50], N [50];
int N, NP, NN;
int I ;
/* Saisie des données */
printf("Dimension du tableau (<50) : ");
scanf("%d", &N );
for (I=0; I<N; I++)
{
printf("%d : ", I);
scanf("%d", &T[I]);
}

74
Algorithmique & structures de données 1

/* Affichage du tableau */
printf("Tableau donné :\n");
for (I=0; I<N; I++)
printf("%d ", T[I]);
printf("\n");
NP=0;
NN=0;
/* Transfer des données à partir de T*/
for (I=0; I<N; I++)
{ if (T[I]>0) {
P [NP]=T[I];
NP++;
}
if (T[I]<0) {
N [NN]=T[I];
NN++;
}
}//remarquer que les valeurs nulles sont ignorées
return 0;
}
5.6
#include<stdio.h>
main()
{
/* Déclarations */
Int M[50][50];
int L, C; /* dimensions de la matrice */
int I, J; /* indices lignes et colonnes */
long SOM; /* somme des éléments */
/* Saisie des données */
printf("Nombre de lignes (<50) : ");
scanf("%d", &L );
printf("Nombre de colonnes (<50) : ");
scanf("%d", &C );
for (I=0; I<L; I++)
for (J=0; J<C; J++)
{
printf("[%d][%d] : ",I,J);

75
Algorithmique & structures de données 1

scanf("%d", &M[I][J]);
}
/* Affichage du tableau */
printf("Tableau donné :\n");
for (I=0; I<L; I++)
{
for (J=0; J<C; J++)
printf("%7d", M[I][J]);
printf("\n");
}
/* Calcul de la somme */
for (SOM=0, I=0; I<L; I++)
for (J=0; J<C; J++)
SOM += M[I][J];
/* affichage de la somme */
printf("Somme des éléments : %ld\n", SOM);
return 0;
}
5.7
#include<stdio.h>
main()
{ int M[100][100];
int N;
int I, J;
printf("donnez la dimension : ");
scanf("%d", &N);
for (I=0; I<N; I++)
for (J=0; J<N; J++)
{ printf("[%d][%d] : ",I,J);
scanf("%d", &M[I][J]);
}
printf("affichage :\n");
for (I=0; I<N; I++)

76
Algorithmique & structures de données 1

{ for (J=0; J<N; J++)

printf("%7d", M[I][J]);
printf("\n"); }
for (I=0; I<N; I++)
M[I][I]=0;
printf("affichage :\n");
for (I=0; I<N; I++)
{ for (J=0; J<N; J++)
printf("%7d", M[I][J]);
printf("\n"); // on écrit new line fin de ligne
}
return (0);
}
5.8
L’hypothèse de tableaux triés est importante pour réaliser la fusion
autrement cela aurait été impossible. La méthode consiste à piocher les éléments
dans le tableau qui contient les plus petits éléments puis d’aller sur l’autre tableau
et ainsi de suite. Le tableau T résultat contiendra la fusion des deux de taille
N1 et N2, les indices i, i1, et i2 pour les trois tableaux respectivement.
Début
i1 = 0; i2 = 0; i = 0
tant que i1 < N1 et i2 < N2 faire
si T1[i1] < T2[i2] alors
T[i] = T1[i1] ; i++; i1++
sinon
T[i] = T2[i2]; i++; i2++
Finsi ;
fin tant que
si i1 < N1 alors // fin du premier tableau, on prend tous les éléments du 2ième
tant que i1 < N1 faire
T[i] = T1[i1]; i++; i1++
fin tant que
sinon
tant que i2 < N2 faire
T[i] = T2[i2]; i++; i2++
fin tant que
fin si
Fin.
77
Algorithmique & structures de données 1

5.9
Algorithme calcul_somme_ligne
Const M=20, M=10 ;
Variables M[N,M], T[N], i, j : entier ;
Debut
Pour i = 1 à N faire
T[i]= 0 ;
Pour j= 1 à M faire
T[i] = T[i] + M[i,j] ;
Fpour ;
Fpour ;
Pour i= 1 à N //affichage du résultat
Ecrire (‘T[‘, i, ‘]= ‘, T[i]) ;
Fpour ;
Fin.

Remarque : pour le vecteur P, faire la boucle sur j au lieu de i.

78