Prof : KONAN HYACINTHE
Initiation à l'algorithmique
Chapitre 6 : Variables structurées
Licence 1 SRIT 2016-2017
Plan du Chapitre
1. INSUFFISANCE DES VARIABLES SIMPLES.......................................................................................2
2. TABLEAUX.............................................................................................................................................. 2
3. STRUCTURES........................................................................................................................................ 10
4. DÉFINITION DE TYPES....................................................................................................................... 11
5. TYPES COMPLEXES............................................................................................................................ 12
6. CONCLUSION : STRUCTURES DE DONNÉES...................................................................................14
Objectif du chapitre
A la fin de ce chapitre, vous devez être capable d’utiliser les variables structurées
dans un algorithme.
p. 1
1. Insuffisance des variables simples
Les variables qui ont été utilisées jusque-là ne peuvent avoir qu'une valeur à un
instant donné. Si une nouvelle valeur leur est affectée, la précédente est perdue.
Ces variables sont des variables simples. Certains problèmes ne peuvent pas être
résolus uniquement avec des variables simples. Par exemple celui qui cherche à
partager une somme d'argent entre un nombre de travailleurs, proportionnellement
à leur temps de travail. Les durées de travail de chacun vont être saisies, sommées,
et pour calculer les parts de chacun il faudra revenir sur les durées saisies, donc les
avoir mémorisées. Le nombre de personnes n'est pas toujours le même d'une
exécution à l'autre du programme. Il est donc impossible de traiter ce problème
avec des variables simples, contenant chacune la durée de travail d'une personne.
Pour résoudre ce type de problème, et bien d'autres, on définira des variables de
type tableau. Il arrive fréquemment que certaines données soient liées entre elles
parce qu'elles caractérisent une même entité (par exemple les caractéristiques d'une
date : jour, mois, année). Il peut être intéressant de matérialiser ce lien en faisant
des différentes données des caractéristiques d'une seule variable. Pour établir ce
type de lien on utilisera des variables de type structure. Ce chapitre présente ces
deux types de variables structurées. Leur caractéristique commune est qu'elles
peuvent avoir plusieurs valeurs à un instant donné. Cependant elles se définissent
et s'utilisent de manières différentes.
2. Tableaux
2.1. Définitions
Un tableau à une dimension est une variable structurée, caractérisée par un
identificateur, qui peut contenir à un instant donné plusieurs valeurs de même type
(contrairement à une variable simple qui ne peut en contenir qu’une seule). On dit
qu'un tableau a plusieurs éléments contenant chacun une valeur. Chaque élément
du tableau est repéré par un indice, en général un nombre entier, qui prend ses
valeurs entre deux bornes.
Valeurs de l’indice→ 0 1 2 3 4 14 15
Valeurs de type entier→ 100 -5 10 13 28 …
Il faut noter que certains éléments peuvent être vides à un instant donné.
p. 2
2.2. Déclaration
La déclaration d'un tableau comprend deux informations :
les bornes : la borne inférieure et la borne supérieure que peut prendre
son indice. Celles-ci déterminent la réservation d’un certain nombre
d’éléments pour le tableau.
le type de valeurs prises par ses éléments.
<identificateur> : TABLEAU [<indice_début> .... <indice_fin>] DE <type>
Exemple : tab : TABLEAU [0 ....15] DE ENTIER
Dans un langage de programmation, la déclaration a pour effet de réserver en
mémoire le nombre de places voulues de la taille correspondant au type. Même si
certains langages de programmation autorisent de redéfinir la taille d'un tableau en
cours d'exécution du programme, un tableau est par nature une variable statique, à
laquelle on donne une taille qui ne varie pas. On se tiendra à cet usage en
algorithmique. C'est le contexte du programme qui doit permettre de déterminer la
taille nécessaire. Si le problème nécessite de faire évoluer la taille, un tableau n'est
pas le type de variable approprié. Il faut alors utiliser des variables dynamiques. Il
ne faut pas confondre place déclarée et place occupée. Un tableau peut très bien
avoir été déclaré avec un intervalle d'indice de 1 à 100 et ne contenir que 20
valeurs. Lorsqu'on doit déclarer un tableau, c'est le contexte du problème qui guide
sur la taille à déclarer. En effet il faut être sûr que le tableau sera assez grand pour
contenir toutes les valeurs qui lui sont destinées, mais il ne faut pas non plus sur-
dimensionner un tableau, ce qui conduit à un gaspillage de place en mémoire vive.
Chaque langage de programmation a ses règles pour l'échelle des indices. En
langage C (idem java), par exemple, le premier élément est toujours à l'indice 0.
p. 3
2.3. Accès à un élément de tableau
Chaque élément de tableau est repéré par une valeur de l'indice et s'écrit de la
manière suivante :
<identificateur>[<indice>]
L’indice peut être :
Une constante : tab [2] vaut 10
Une variable : ind ← 3 ; tab[ind] vaut 13
Une expression : tab [ind + 1] vaut 28
Règle générale :
Un élément de tableau se comporte exactement comme une variable simple et peut
faire partie de n'importe quelle expression. On peut trouver un élément de tableau :
Dans une instruction de lecture LIRE (tab [4])
Dans une instruction d'écriture ECRIRE (tab [4])
À gauche d'une flèche d'affectation tab [5] 45
Dans une expression ECRIRE (tab [5] * 10)
À la place d'un paramètre effectif ECHANGER (tab [1], tab [2])
2.4. Algorithmes pour remplir un tableau
Mettre des valeurs dans un tableau (1) : nombre de valeurs connu
ALGORITHME RemplirTableau1
VARIABLES
| texte : TABLEAU [0…100] DE CARACTERES{le texte}
| nbcar : ENTIER {nombre de caractères}
| i : ENTIER {variable de boucle et indice}
DEBUT
| LIRE (nbcar)
| POUR i DE 1 A nbcar FAIRE
| | LIRE (texte[i])
| FINPOUR
FIN
p. 4
Mettre des valeurs dans un tableau (2) : Dernier élément reconnu et rangé
dans le tableau. Nombre de caractères inconnu
ALGORITHME remplir_tableau_2
VARIABLES
texte : TABLEAU [1...100] DECARACTERE {le texte}
ncar : ENTIER {nombre de caractères}
DEBUT
ncar ← 0 {ncar est la variable de la boucle}
REPETER
LIRE (texte[ncar])
ncar ← ncar + 1
JUSQUA texte[ncar] = '.'
FIN
En exemple, simuler l’algorithme remplir_tableau_2 pour la phrase
"il était une fois."
\* l’espacement dans le tableau est fait par l’utilisateur avec la barre d’espacement
du clavier*/
Mettre des valeurs dans un tableau (3) : Terminé par un caractère fictif (par
exemple #) non rangé dans le tableau. Nombre de caractères inconnu
ALGORITHME remplir_tableau_3
VARIABLES
| texte : TABLEAU [1…100] de CARACTERES{le texte}
| ncar : ENTIER {nombre de caractères}
| carlu:CARATERE{variable de saisie}
DEBUT
| ncar ← 0
| LIRE (carlu)
| TANTQUEcarlu <> '#' FAIRE
| | ncar ← ncar + 1
| | texte[ncar] ← carlu
| | LIRE (carlu)
| FINTANTQUE
FIN
p. 5
p. 6
2.5. Algorithmes pour parcourir et exploiter un tableau
Exploiter un tableau (1) : remplacer les 'i' par des 'x' : nombre d'éléments
connus :
ALGORITHME parcourir_tableau_1
VARIABLE
texte : TABLEAU [1…100] DE CARACTERES {le texte}
ncar : ENTIER {nombre de caractères}
k : ENTIER {variable de boucle}
DEBUT
LIRE (ncar)
POUR k DE 1 A ncar FAIRE
SI texte[k] = 'i' ALORS
texte[k] ← 'x'
FINSI
FINPOUR
FIN
Exploiter un tableau (2) : remplacer les 'i' par des 'x' : le dernier élément du
tableau est connu et doit être traité :
ALGORITHME parcourir_tableau_2
VARIABLES
| texte : TABLEAU [1...100] de CARACTERE {le texte}
| k : ENTIER {variable de boucle}
DEBUT
| k←0
| REPETER
| | k←k+1
| | SI texte[k] = 'i' ALORS
| | | texte[k] ← 'x'
| | FINSI
| JUSQUA texte[k] = '.'
FIN
p. 7
Exploiter un tableau (3) : remplacer les 'i' par des 'x' : le dernier élément du
tableau est connu et ne doit pas être traité :
ALGORITHME parcourir_tableau_3
VARIABLES
texte : TABLEAU [1....100] de CARACTERE {le texte}
k : ENTIER {variable de boucle}
DEBUT
k←1
TANTQUE texte[k] <> '.' FAIRE
SI texte[k] = 'i' ALORS
texte[k] ← 'x'
FINSI
k←k+1
FINTANTQUE
FIN
2.6. Rechercher un élément dans un tableau
ALGORITHME rechercher_elt_tableau
VARIABLES
texte : TABLEAU [1...100] DE CARACTERE {le texte}
elt : CARACTERE {élément recherché}
k : ENTIER{variable de boucle}
DEBUT
ECRIRE (‘Saisissez l’élément à rechercher :’)
LIRE (elt)
k←1
TANTQUE texte[k] <>elt ET texte[k] <> '.' FAIRE
k←k+1
FINTANTQUE
ECRIRE (elt, "est en", k, "ième place du tableau")
FIN
p. 8
2.7. Tableaux à plusieurs dimensions
Les plus utilisés sont les tableaux à deux dimensions, mais on peut très bien
concevoir des tableaux à trois dimensions ou plus. Pour déclarer un tableau à n
dimensions, il faut donner n intervalles de valeurs pour les indices, ainsi que le
type des valeurs rangées dans le tableau.
Syntaxe : (bi pour borne inférieure, bs pour borne supérieure)
<identificateur> : TABLEAU [ <bi1. ... bs1>, <bin...bsn>] de <type>
L'accès se fait avec les valeurs des n indices :
<identificateur>[<valeur i1>, <valeur in>]
Les règles d'utilisation des éléments de tableau sont les mêmes que pour les
tableaux à une dimension.
Exemple :
mat : TABLEAU [0...3, 0...5] DE CARACTERES
L'élément mat[2, 3] contient la valeur 'Q'
p. 9
3. Structures
3.1. Définitions
Un autre type de variable structurée dite Structure est caractérisée par un
identificateur, qui peut contenir, à un instant donné, plusieurs valeurs de types
différents. Chaque valeur est rangée dans un champ et repérée par un identificateur
de champ.
3.2. Déclaration
Déclarer une variable structure revient à déclarer chaque champ sous la forme
d'un identificateur et d'un type.
Syntaxe de la déclaration :
<identificateur Structure> : STRUCTURE
<identificateur champ> : <type>
....
<identificateur champ> : <type>
<identificateur champ> : <type>
FINSTRUCTURE
Exemple :
elt : STRUCTURE { déclaration d’une variable de type structures}
nom : CHAINE {nom de l'élément}
symbole : CHAINE {symbole chimique}
Z : ENTIER {numéro atomique}
masse : REEL {masse atomique}
FINSTRUCTURE
p. 10
Remarque : il est utile d'indiquer les rôles des champs (comme pour les variables
simples)
3.3. Accès aux champs
Syntaxe : <identificateur Structure>.<identificateur champ>
Règle générale : un champ d'une variable structure se manipule comme une
variable simple. On peut le trouver :
dans une instruction de lecture : LIRE ([Link])
dans une instruction d'écriture : ECRIRE ([Link])
à gauche d'une flèche d'affectation : [Link] ← 'Na'
dans une expression : m ← [Link] * 4
à la place d'un paramètre réel dans un appel de procédure ou de fonction :
échanger (elt1.Z, elt2.Z)
4. Définition de types
Il peut être pratique de définir des types puis d'utiliser ces noms dans des
déclarations de variables. Syntaxe pour définir un type :
Syntaxe : <type> = <définition du type>
Les déclarations qui utilisent un type défini se font comme avec les types
prédéfinis.
Exemples de définitions de type suivies de déclarations de variables
Exemple 1 :
Définition de type tableau : t_tab = TABLEAU[0...15] DE ENTIER
Déclaration de variable : tab : t_tab
p. 11
Exemple 2 :
Définition de type :
t_matrice = TABLEAU[0...3, 0...5] DE CARACTERES
Déclaration de variable : mat : t_matrice
Exemple 3 :
Définition de type :
T_ELT = STRUCTURE {déclaration d’un type structure}
nom : CHAINE
symbole : CHAINE
Z : ENTIER
masse : REEL
FINSTRUCTURE
Déclaration de variable : elt : T_ELT {déclaration d’une variable de type
structure}
Remarque : les noms de types suivent les règles des identificateurs. C'est par
simple commodité, pour les distinguer des identificateurs des variables, que ceux
des exemples commencent par t_.
5. Types complexes
On peut construire des types complexes en composant tableaux et structures :
un élément de tableau peut être une structure,
un champ de structure peut être un tableau Il n'y a pas de limite à la
composition, les deux paragraphes suivants donnent des exemples simples.
5.1. Tableaux de structures (chaque élément du tableau est une structure)
Exemple : table des éléments chimiques
p. 12
Définitions des types :
T_ELT = STRUCTURE
nom : CHAINE {nom de l'élément}
symbole : CHAINE {symbole chimique}
Z : ENTIER {numéro atomique}
masse : REEL {masse atomique}
FINSTRUCTURE
T_TABLE = TABLEAU [0...120] DE T_ELT
Déclaration de variables :
table_periodique : T_TABLE
Accès à un élément :
Table_periodique[4].masse contient la valeur 10,8
table_periodique[2].symbole contient la valeur 'Li'
5.2. Structure avec tableaux (chaque élément de la structure est un tableau)
Exemple : liste de températures avec nombre (de temp relevé), minimum et
maximum.
Définitions des types :
T_TEMP = TABLEAU[0...100] DE REEL
T_LISTE = STRUCTURE
temp : T_TEMP /* tableau des températures */
nb : ENTIER /* nombre de températures */
tmin : REEL /* température minimale */
tmax : REEL /* température maximale */
FINSTRUCTURE
p. 13
Déclaration de variables :
mesures : T_LISTE
Accès à un élément :
[Link] vaut 5
[Link][3] vaut 6,3
6. Conclusion : structures de données
Les tableaux et les structures permettent de composer des structures complexes
dans lesquelles peuvent être organisés des rangements des données qu'on appelle
structures de données. D'autres types de données, en particulier des types de
variables dynamiques, peuvent contribuer à construire des structures de données
adaptées au problème à résoudre. Les structures de données et les méthodes
algorithmiques qui les exploitent sont le plus souvent dépendantes les unes des
autres.
FIN DU CHAPITRE 6
p. 14
