Nous formons les experts de demain

ECOLE SUPERIEURE D’INGENIERIE ET

D’INNOVATION

EDO123 – ALGORITHMES & STRUCTURES DE

DONNEES
30 Heures – 3 ECTS
Licence professionnelle
informatique
1ère année - Tronc commun
Enseignant : M. Olyvier NZIGHOU
Master 2 Gestion de Projets Informatiques de
l’Université de Strasbourg.
Tél. : 066049840 / 077684285
Email : [Link]@[Link]

Reproduction interdite
Objectifs du cours

 Acquérir les notions de base d’algorithmique

 Acquérir l’aptitude à écrire des algorithmes (et des

programmes) simples

 Evoluer étape par étape à partir d’algorithme simple vers

des algorithmes
plus structurés et avec plus de possibilités

 Après la maitrise des types simples, il passe aux types

structurés et personnalisés

Reproduction 2
Evaluation

 Contrôle continu (40%) inclus

 Devoir
 Interrogation
 TP
 Examen final (60%)

Reproduction 3
Enseignement

 Cour magistral

 TD/TP

Reproduction 4
COMPETENCES À ACQUERIR

 Savoir transcrire un problème en

algorithmes

 Savoir manipuler des structures de

données

Reproduction 5
Contenu du cours
1. Concepts de base 4. Types structurés
 Structure d’un algorithme  Les tableaux
 Variables et constantes  Les matrices
 Les pointeurs
 Types de données
 Les listes
2. Expression et instructions  Les files
élémentaires  Les piles
 Expressions
5. Fonctions et
 Instruction Lire, Ecrire,  procédures
3. Structures de contrôle 6. Enregistrements et
 Structures alternatives les fichiers
 Structures conditionnelles 7. Optimisation des
 Structures itératives algorithmes

Reproduction 6
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE I
Introduction

Reproduction 7
Historique

 Le mot algorithme vient du savant perse

ALKHAWARIZMI, Muhammad Ibn Musa al-
Khawarizmi
 Né vers 780 mort vers 850
 Auteur d’un ouvrage « AL Jabre walmokabala »
traduit par « L’algèbre et le balancement » qui décrit
des méthodes de calculs algébriques;

 Par référence à ALKHAWARIZMI, le mot algorithme

est devenu en latin algorimus avant de devenir
algorithme en français en 1554.
Reproduction 8
DEFINITION d’un algorithme
Dans la vie courante, un algorithme peut par exemple
prendre la forme :
D’une recette de cuisine;
D’un mode d’emploi;
D’une notice de montage d’un meuble;
D’une indication de chemin à un touriste;

Un algorithme est donc une suite d’opérations (ou

instructions) qui doivent être exécutées dans un
ordre déterminé dans le but de résoudre un
problème.
Il est écrit en utilisant un Langage de Description
Algorithmique (LDA)Reproduction
appelé aussi pseudo-code 9
L’ALGORITHMIQUE dans le monde informatique

 L’algorithmique est une branche de

l’informatique qui étudie la rapidité et
l’efficacité des algorithmes dans le but
de les transformer en programme en les
traduisant dans un langage
compréhensible par l’ordinateur (langage
de programmation).

Reproduction 10
Pourquoi L’ALGORITHMIQUE ?

 Apprendre l’algorithmique  pour apprendre à

programmer
Description du problème : suite
Algorithme d’instructions pour résoudre un
problème, indépendamment des
particularités de tel ou tel langage
Passage (pseudo-code)
(obligatoire) pour les
programmeurs
Programme exécutable (écrit dans un
Programme langage de programmation : C, C+
+, Java, Python, PHP…) en
respectant la syntaxe propre à chaque
langage
Reproduction 11
RESOLUTION d’un PROBLEME en informatique
Plusieurs étapes sont nécessaires pour résoudre un
problème informatique :
Etape 1 : Définition du problème :
 Il s’agit de déterminer toutes les informations
disponibles et la forme des résultats désirés.
Etape 2 : Analyse du problème :
 Elle consiste a trouver le moyen de passer des
données aux résultats. Dans certains cas on peut
être amené à faire une étude théorique.
 Le résultat de l’analyse est un algorithme.
 Sachez aussi qu’il existe des problèmes pour
lesquels on ne peut trouver une solution et par
Reproduction
conséquent il est impossible de donner l’algorithme 12
RESOLUTION d’un PROBLEME en informatique
 Etape 3 : Ecriture d’un algorithme avec un
langage de description algorithmique (LDA) :
 Une fois qu’on trouve le moyen de passer des
données aux résultats, il faut être capable de
rédiger une solution claire et non ambiguë.
 Comme il est impossible de le faire en langage
naturel, l’existence d’un langage algorithmique
s’impose.
 Etape 4 : Traduction de l’algorithme dans un
langage de programmation
 Les étapes 1, 2, 3 se font sans le recours de la
machine. Si on veut rendre l’algorithme concret ou
pratique, il faudrait le traduire dans un langage de
Reproduction 13
RESOLUTION d’un PROBLEME en informatique

 Nous dirons qu’un programme est un algorithme

exprimé dans un langage de programmation.

 Etape 5 : Mise au point du programme

 Quand on soumet le programme à la machine,

cette dernière le traite en deux étapes :

1. La machine corrige l’orthographe, c’est ce

qu’on appelle syntaxe dans le jargon de la
programmation.
2. La machine traduit le sens exprimé par le
programme.

Reproduction 14
RESOLUTION d’un PROBLEME en informatique

 Si les résultats obtenus sont ceux attendus, la mise

au point du programme se termine.
 Si nous n’obtenons pas de résultats, on dira qu’il y
a existence des erreurs de logique.
 Le programme soit ne donne aucun résultat, soit
des résultats inattendus soit des résultats partiels.
Dans ce cas, il faut revoir en priorité si l’algorithme
a été bien traduit, ou encore est-ce qu’il y a eu une
bonne analyse.

Reproduction 15
PROPRIETES D’UN ALGORITHME

On peut énoncer les cinq propriétés suivantes que doit

satisfaire un algorithme :

1. Généralité : un algorithme doit toujours être

conçu de manière à envisager toutes les
éventualités d’un traitement.

2. Finitude : Un algorithme doit s’arrêter au bout

d’un temps fini.

3. Définitude : toutes les opérations d’un

algorithme doivent être définies sans ambiguïté

Reproduction 16
PROPRIETES D’UN ALGORITHME
4. Répétitivité : généralement, un algorithme
contient plusieurs itérations, c’est-à-dire des
actions qui se répètent plusieurs fois.

5. Efficacité : Idéalement, un algorithme doit être

conçu de telle sorte qu’il se déroule en un temps
minimal et qu’il consomme un minimum de
ressources.

Remarque :
Attention, certains problèmes n’admettent pas de
solution algorithmique exacte et utilisable. On utilise
dans ce cas des algorithmes heuristiques qui
fournissent des solutions approchées.
Reproduction 17
Convention D’ECRITURE : L’ORGANIGRAMME

 Historiquement, plusieurs types de

notation ont représenté les
algorithmes;
 Notamment une représentation
graphique (carrés, losanges,
parallélogrammes…) qu’on appelait
des organigrammes

Reproduction 18
Convention D’ECRITURE : le pseudo-code ou LDA

 Une série de conventions appelées « pseudo-code »

avec une syntaxe qui ressemble à un langage de
programmation;
 Ce pseudo-code est aussi appelé LDA (Langage de
Description d’Algorithme);
 Son avantage est de pouvoir être facilement
transcrit dans un langage de programmation.

Reproduction 19AZERY7I90
Convention D’ECRITURE : le pseudo-code ou LDA

Remarque
importante
 Ce pseudo-code peut varier d’un ouvrage à un autre
puisqu’il est purement conventionnel (Aucune machine
n’est sensé le reconnaitre)
Exemples

 Exemple pour déclarer les variables : Var / variables et

Const /constantes
 Affectation : signe égal = / 
 Point virgule ; ou pas à la fin de chaque instruction
 FINSI / fsi
 Commentaires : {commentaire} / (*commentaire*) /
%commentaire% Reproduction 20
Convention D’ECRITURE : le pseudo-code ou LDA
Algorithme Produit_2_nombres
variables a : entier
b : entier
DEBUT
Ecrire("saisir un entier a : ")
Lire(a)
Ecrire("saisir un entier b : ")
Lire(b)
SI ((a=0) OU (b=0)) ALORS
Ecrire ("Le produit est nul")
SINON SI ((a<0) ET (b<0) OU (a>0) ET
(b>0)) ALORS
Ecrire ("Le produit est positif")
SINON Ecrire ("Le produit est négatif")
FINSI
FIN

Reproduction 21
Convention D’ECRITURE : le pseudo-code ou LDA
Algorithme Produit_2_nombres L’entête de
variables a : entier l’algorithme
Déclaration des
b : entier
variables et
DEBUT constantes
Ecrire("saisir un entier a : ")
Lire(a)
Ecrire("saisir un entier b : ")
Lire(b)
SI ((a=0) OU (b=0)) ALORS Corps de
Ecrire ("Le produit est nul") l’algorithme
SINON SI ((a<0) ET (b<0) OU (a>0) ET (b>0))
ALORS
Ecrire ("Le produit est
positif")
SINON Ecrire ("Le produit est négatif")
FINSI
FIN Reproduction 22
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE II
Les types de variables

Reproduction 23
C’est quoi une variable ?

 Au cours de l’exécution d’un programme informatique

on aura besoin de stocker des informations :
 Saisies par l’utilisateur au clavier
 Résultat d’un programme (intermédiaire ou
définitif)
 Ces informations sont stockées dans des variables
 On peut à tout moment durant l’exécution de
l’algorithme changer la valeur de la variable en
écrasant l’ancienne à condition que la nouvelle
valeur soit du même type ou compatible avec.

Reproduction 24
Les types de DONNEES

 Les données sont contenues dans des cases

mémoires de l’ordinateur;
 La longueur de la case mémoire dépend du type
de données qu’elle contient
Mot
Type de variable Exemple de valeurs à contenir
clé
Entier -50; 0; 600; 1000 Entier
Numérique
Réel 20; -4; 36,123; 3,14 Réel
Caractère ‘a‘; ‘D‘; ‘+‘; ‘1‘ Car
Alphanumérique Chaîne de ˝Algorithme˝; ˝variable˝; Chaîne
caractères
VRAI; FAUX Boolée
Booléen
n

Reproduction 25
Les types NUMERIQUES

Type numérique Taille

Plage de valeurs
mémoire
Byte(octet) 0 à 255 1 octet
Entier simple -32 768 à 32 767 2 octets
Entier long -2 147 483 648 à 2 147 483 4 octets
647
Réel simple -3,40*1038 à 3,40*1038 4 octets
Réel double 1,7*10-308 à 1,7*10308 8 octets
Réel double long 3,4*10-4932 à 3,4*104932 10 octets

Reproduction 26
CHOIX DES IDENTIFICATEURS
 Le choix des noms de variables est soumis à
quelques règles :

 Un nom de variable doit commencer par une lettre

alphabétique

 exemple valide : A1 exemple

invalide : 1A

 Doit être constitué uniquement de lettres, de chiffres

et du soulignement ( _ ) (Eviter les caractères de
ponctuation et les espaces)

 valides : Info2022, Info_2022,

Reproduction
infoAlgoProgramme invalides : Info 2022, 27
DECLARATION DES
VARIABLES
 La déclaration des variables se fait au début de
l’algorithme

 Le but est de réserver une case mémoire (allouer de

l’espace mémoire) en précisant ce que l’on veut y
mettre  c’est ce qu’on appelle type de la variable
Syntaxe de déclaration Exemples
variable pi : Réel
variable prenom : Chaîne
Variable nomDeLaVariable : variable age : Entier
Type variable i,j,k : Entier
variable c : car
variable trouve : Booléen

Reproduction 28
Les constantes

 Servent à donner un nom à une valeur

 La case mémoire portant ce nom ne peut recevoir

aucune autre donnée durant l’exécution de l’algorithme

Syntaxe de déclaration Exemples

constante pi = 3,14
constante taux = 0,15
Constante nomDeLaConstante = valeur
constante trouve =
VRAI

Reproduction 29
EXPRESSION & OPERATEURS
 Une expression peut être une valeur, une variable ou une
opération constituée de variables reliées par des opérateurs
exemples : 1, b, a*2, a+3*b-c, …
 L'évaluation de l'expression fournit une valeur unique qui est le
résultat de l'opération
 Les opérateurs dépendent du type de l'opération, ils peuvent
être :
 des opérateurs arithmétiques :
 +, -, *, /, div, % (modulo), ^ (puissance)
 a = b * q + r avec r < b, q = a div b, r = a mod
b
 des opérateurs logiques : NON, OU, OU exclusif (XOR),
ET
 des opérateurs relationnels : =, <, >, <=, >=, <>
 des opérateurs sur
Reproduction
les chaînes : & (concaténation) 30
PRIORITE DES OPERATEURS
 Pour les opérateurs arithmétiques donnés ci-
dessus, l'ordre de priorité est le suivant (du plus
prioritaire au moins prioritaire) :
1) ^ (élévation à la puissance)
2) * , / , div (multiplication, division, division
entière)
3) % (modulo)
4) + , - (addition, soustraction)
 exemple : 2 + 3 * 7 vaut 23
 En cas de besoin (ou de doute), on utilise les
parenthèses pour indiquer les opérations à
effectuer en priorité
Reproduction 31

ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE III
L’instruction d’affectation

Reproduction 32
L’instruction d’affectation
 Permet d’attribuer des valeurs aux variables en utilisant le
symbole suivant 
Syntaxe Exemples de déclaration Exemples d’affectation
variable pi : Réel pi  3,14
variable prenom : Chaîne prenom  ˝Sylvie˝
variable age : Entier age  25
nomDeLaVariable 
variable i,j,k : Entier i0, j5, k-1, ij
valeur
variable c : car c‘A‘
variable trouve : Trouve  VRAI
Booléen

Reproduction 33
Les types d’affectation : Type 1

Nom_variable 
valeur_de_meme_type
Exemples Pi3,14
:
prenom˝Algorithme˝
age24
i0
Facture_payeeVRAI
Choix ‘Y‘;

Reproduction 34
Les types d’affectation : Type 2

Nom_variable 
variable_de_meme_type
Exemples prenom1˝Snoopy˝
:
prenom2˝Daniel˝
Prenom2prenom1

Reproduction 35
Les types d’affectation : Type 3

Nom_variable 
expression_retournant_meme_type
Exemples ki+j
:
consommationnouvel_index –
ancien_index
moyennesomme_notes / nombre_eleves
TVAHT*0,2

Reproduction 36
EXERCICE SIMPLE SUR L’affectation
 Donnez les valeurs des variables A, B et C
après exécution des instructions suivantes ?
Variables A, B, C: entier
DEBUT
A  -3
B  7
A  B
B  A-5
C  A + B
C  B – A
FIN

Reproduction 37
EXERCICE SIMPLE SUR L’affectation
 Donnez les valeurs des variables A et B après
exécution des instructions suivantes ?

Variables A, B : entier
DEBUT
A  4
B  9
A  B
B  A
FIN

 Les deux dernières instructions permettent-

elles d’échanger les valeurs de A et B ?

Reproduction 38
EXERCICE SIMPLE SUR L’affectation

 Ecrire un algorithme permettant d’échanger les

valeurs de deux variables A et B

Reproduction 39
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE IV
Lecture & ECRITURE

Reproduction 40
Instructions de lecture et d’ecriture

 Ecriture  afficher à l’écran

Ecrire(˝Entrez la valeur de la
tva :˝)
 Lecture  Saisir au clavier et affecter ce
qui est saisi aux variables déjà définies
Lire(tva)

Reproduction 41
ecriture

 Ecriture  Afficher à
l’écran

Cas Syntaxe Exemples

1 Ecrire(˝message˝) Ecrire(˝Entrez la valeur de a :˝)
2 Ecrire(nom_variable) Ecrire(moyenne)
3 Ecrire(˝message˝,nom_variable) Ecrire(˝votre note est :˝,moyenne)

Reproduction 42
Lecture
 lecture  Saisir au clavier et affecter ce qui est saisi aux
variables déjà définies

Syntaxe Exemples
Lire(a)
Lire(nom_variable)
Lire(TVA)
Lire(note)

Reproduction 43
Exercice

 Écrire un algorithme qui demande à l’utilisateur

de saisir deux nombres entiers et de calculer leur
somme et l’afficher à l’écran.

Reproduction 44
Solution de l’exercice
Algorithme Somme
Variables a, b, S : Entier

DEBUT
Ecrire(˝Saisir a :˝)
Lire(a)
Ecrire(˝Saisir b :˝)
Lire(b)
Sa+b
Ecrire(˝La somme est :˝,S)
FIN

Reproduction 45
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE V
Les INSTRUCTIONS CONDITIONELLES

Reproduction 46
LES INSTRUCTIONS
CONDITIONNELLES

 Les instructions conditionnelles servent à

n'exécuter une instruction ou une séquence
d'instructions que si une condition est vérifiée

Reproduction 47
TESTS : LES INSTRUCTIONS CONDITIONNELLES
 On utilisera la forme
suivante : SI (condition) ALORS
instruction ou suite
d'instructions1
SINON
instruction ou suite
d'instructions2
 La condition ne peut
FINSIêtre que vraie ou fausse
 Si la condition est vraie, se sont les instructions1 qui
seront exécutées
 Si la condition est fausse, se sont les instructions2 qui
seront exécutées
 La condition peut être une condition simple ou une
condition composée de plusieurs conditions
Reproduction 48
TESTS : LES INSTRUCTIONS CONDITIONNELLES

SI (condition) ALORS
instruction ou suite
d'instructions1
SINON
instruction ou suite
d'instructions2
FINSI

Reproduction 49
EXEMPLE
Algorithme : Test
Variable X : entier
DEBUT
Écrire(" Saisir un entier X ")
Lire(X)
SI (X > 0) ALORS
Écrire(" X est un nombre positif ")
SINON
Écrire(" X est un nombre négatif ou nul
")
FINSI
FIN

Reproduction 50
EXERCICE

 Ecrire un algorithme qui permet de lire et

d'afficher la valeur absolue d'un réel.

Reproduction 51
SOLUTION DE L’EXERCICE
Algorithme Affichage_Valeur_Absolue (version1)
Variable x : réel
DEBUT
Ecrire(" Entrez un réel : ")
Lire(x)
SI (x < 0) ALORS
Ecrire("La valeur absolue de ", x,
"est :",-x)
SINON
Ecrire("La valeur absolue de ", x,
"est :",x)
FINSI
FIN
Reproduction 52
TESTS : LES INSTRUCTIONS CONDITIONNELLES

 La partie Sinon n'est pas obligatoire, quand

elle n'existe pas et que la condition est
fausse, aucun traitement n'est réalisé

 On utilisera dans ce cas la forme simplifiée

suivante :
SI (condition) ALORS
instruction(s)
FINSI

Reproduction 53
EXEMPLE
Algorithme Affichage_Valeur_Absolue
(version2)
Variable x,y : réel
DEBUT
Ecrire(" Entrez un réel : ")
Lire(x)
y x
SI (x < 0) ALORS
y  -x
FINSI
Ecrire("La valeur absolue de ", x, "est :",y)
FIN

Reproduction 54
EXERCICE

 Ecrire un algorithme qui demande un nombre

entier à l'utilisateur, puis teste et affiche s'il est
divisible par 3.

Reproduction 55
SOLUTION DE L’EXERCICE
Algorithme Divsible_par3
Variable n : entier
DEBUT
Ecrire(" Entrez un entier : ")
Lire(n)
SI (n%3=0) ALORS
Ecrire(n," est divisible par 3")
SINON
Ecrire(n," n'est pas divisible par 3")
FINSI
FIN

Reproduction 56
Conditions COMPOSEES
 Une condition composée est une condition
formée de plusieurs conditions simples reliées
par des opérateurs logiques :

ET,
ET OU,
OU OU exclusif (XOR) et NON
 Exemples :

 x compris entre 2 et 6 : (x > 2) ET (x < 6)

 n divisible par 3 ou par 2 : (n%3=0) OU (n

%2=0)

 L'évaluation d'une condition composée se fait

selon des règles présentées généralement dans
Reproduction
ce qu'on appelle tables de vérité. 57
TABLES DE VERITE

Reproduction 58
EXEMPLE (1)

Expression Résultat
(4<7) ET (9>0) Vrai
(1<0) OU (1<>1) Faux
NON(13.4<15)
NON Faux

 Priorité : NON est prioritaire sur ET qui est

prioritaire sur OU

Reproduction 59
TESTS IMBRIQUEES
 Les tests peuvent avoir un degré quelconque
d'imbrications
SI (condition1) ALORS
SI (condition2) ALORS
instructionsA
SINON
instructionsB
FINSI
SINON
SI (condition3) ALORS
instructionsC
FINSI
FINSI

Reproduction 60
TESTS IMBRIQUEES : EXEMPLE (VESRION
1) Variable n : entier
DEBUT
Ecrire("entrez un nombre : ")
Lire(n)
SI (n < 0) ALORS
Ecrire("Ce nombre est négatif")
SINON
SI (n = 0) ALORS
Ecrire("Ce nombre est nul")
SINON
Ecrire("Ce nombre est positif")
FINSI
FINSI
FIN

Reproduction 61
TESTS IMBRIQUEES : EXEMPLE (VESRION
2) Variable n : entier
DEBUT
Ecrire("entrez un nombre : ")
Lire(n)
SI (n < 0) ALORS
Ecrire("Ce nombre est négatif")
FINSI
SI (n = 0) ALORS
Ecrire("Ce nombre est nul")
FINSI
SI (n > 0) ALORS
Ecrire("Ce nombre est positif")
FINSI
FIN

Reproduction 62
TESTS IMBRIQUEES : EXEMPLE (VESRION
2)

 Remarque : dans la version 2 on fait trois tests

systématiquement alors que dans la version 1, si le
nombre est négatif on ne fait qu'un seul test

 Conseil : utiliser les tests imbriqués pour limiter le

nombre de tests et placer d'abord les conditions les
plus probables

Reproduction 63
EXERCICE

 Ecrivez un algorithme qui demande à l’utilisateur

d’entrer la température de l’eau, et affiche ensuite
l’état de l’eau selon la température (on rappelle
que l’état de l’eau est glace pour une température
inférieure ou égale à 0, est vapeur pour une
température supérieure ou égale à 100 et liquide
pour une température comprise strictement entre 0
et 100).

Reproduction 64
SOLUTION DE L’EXERCICE
Variable Temp : réel
DEBUT
Ecrire(" Entrez la température de l’eau : ")
Lire (Temp)
SI (Temp <= 0 ) ALORS
Ecrire("C’est de la glace ")
SINON
SI (Temp < 100) ALORS
Ecrire("C’est du liquide ")
SINON
Ecrire("C’est de la vapeur ")
FINSI
FINSI
FIN

Reproduction 65
EXERCICE

 Ecrire un algorithme qui affiche la mention

dans les bulletins de note des étudiants selon
la note obtenue

Reproduction 66
SOLUTION DE L’EXERCICE
Algorithme mention
Variables note : Réel
mention : Chaîne
DEBUT
Ecrire(˝Saisir la note :˝)
Lire(note)
SI (note < 10) ALORS mention  ˝Ajourné˝
SINON SI (note < 12) ALORS mention  ˝Passable˝
SINON SI (note < 14) ALORS mention  ˝Assez
Bien˝
SINON SI (note < 16) ALORS mention 
˝Bien˝
SINON mention  ˝Très Bien˝
FINSI
FINSI
FINSI
FINSI
Ecrire(˝La mention est:˝, mention)
FIN
Reproduction 67
EXERCICE

 Ecrire un algorithme qui lit trois entiers A, B

et C, et affiche le plus grand.

Reproduction 68
SOLUTION DE L’EXERCICE
Variables A, B, C : entiers
DEBUT
Ecrire("Donner A, B et C ") ;
Lire(A, B, C) ;
SI (A > B) ALORS
SI (A > C) ALORS
Ecrire("Le plus grand nombre est : ", A)
SINON
Ecrire ("Le plus grand nombre est : ", C)
FINSI
SINON
SI (B > C) ALORS
Ecrire("Le plus grand nombre est : ", B)
SINON
Ecrire("Le plus grand nombre est : ", C)
FINSI
FINSI
FIN

Reproduction 69
Exercice

 Ecrire un algorithme qui calcule le carré d’un

nombre entier positif

Reproduction 70
Solution de l’exercice

Algorithme carré
Variables Nombre, Carre : Entier

DEBUT
Ecrire(˝Saisir le nombre :˝)
Lire(Nombre)
SI (Nombre > 0) ALORS
Carre Nombre*Nombre
Ecrire(˝Le carré est˝, Carre)
FINSI
FIN

Reproduction 71
Exercice

 Ecrire un algorithme qui calcule la taxe sur le chiffre

d’affaire sachant qu’elle est de 10% s’il est inférieur
strictement à 100000 XAF et 20% s’il est supérieur à
ce seuil

Reproduction 72
Solution de l’exercice
Algorithme calcul_taxe
Variables CA, taxe : Réel

DEBUT
Ecrire(˝Saisir le chiffre d’affaire :˝)
Lire(CA)
SI (CA < 100000) ALORS
taxe CA*0,1
SINON
taxe CA*0,2
FINSI
Ecrire(˝La taxe est˝, taxe)
FINSI
FIN

Reproduction 73
TESTS IMBRIQUEES : AUTRE
FORMELa structure alternative peut prendre une autre forme
qui permet d’imbriquer plusieurs conditions.
SELON Expression
Valeur1 : action1
Valeur2 : action2
.........
ValeurN : actionN
SINON : action
FINSELON

 Si expression est égale à valeuri, on exécute actioni et on passe

à la suite de l’algorithme.
 Sinon on exécute action et on passe à la suite de l’algorithme.
 On l’appelle « structure choix »
Reproduction 74
Exercice
 Ecrire un algorithme permettant de calculer le prix à
payer pour l’abonnement à un club qui décide de faire
des remises sur les prix d’abonnement :
 Ancien abonné : -15%
 Nouvel abonné : -10%
 Etudiant : -20%
 Enfant de moins de 12 ans : -30%
 Le calcul du prix d’abonnement se fait en fonction du
tarif normal d’abonnement et de la qualité de l’abonné,
(une seule qualité est accepté par abonné).

Reproduction 75
Solution de l’exercice
Algorithme calcul_abonnement
Variables QH : Entier (*Qualité SELON (QH) FAIRE
abonné*)
1 : TR  -0,15
TN : Réel (*Tarif normal*)
2 : TR  -0,1
TR : Réel (*Taxe de remise*)
3 : TR  -0,2
R : Réel (*Remise*)
4 : TR  -0,3
PAP : Réel (*Prix à payer*)
SINON : Ecrire(˝valeur incorrecte˝)
DEBUT
FINSELON
Ecrire(˝***** MENU *****˝)
R  TN * TR
Lire(TN)
PAP TN + R
Ecrire(˝Saisir le tarif normal:˝)
Ecrire(˝Le prix à payer est :˝,PAP)
Ecrire(˝1: Ancien abonné˝)
FIN
Ecrire(˝2: nouvel abonné˝)
Ecrire(˝3: Etudiant˝)
Ecrire(˝4: Enfant de moins de 12 ans˝)
Ecrire(˝Choisir la qualité de l’abonné˝)
Lire(QH)

Reproduction 76
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE VI
Les instructions ITERATIVES (les
boucles)

Reproduction 77
Les instructions ITERATIVES (les boucles)

 Les boucles servent à répéter l'exécution d'un

groupe d'instructions un certain nombre de fois.
 On distingue trois sortes de boucles en langages
de programmation :
 Les boucles « TANT QUE … FAIRE » : on y répète
des instructions tant qu'une certaine condition
est réalisée.
 Les boucles « REPETER … JUSQU’À » : on y
répète des instructions jusqu'à ce qu’une
certaine condition soit réalisée.
 Les boucles « POUR … FAIRE » ou avec compteur
: on y répète des instructions en faisant évoluer
un compteur (variable particulière) entre une
Reproduction 78
LA boucle « TANT QUE … FAIRE… »

TANTQUE (condition) FAIRE

Instruction(s)
FINTANTQUE

Reproduction 79
LA boucle « TANT QUE … FAIRE… »

 La condition (dite condition de contrôle de la boucle) est

évaluée avant chaque itération.

 Si la condition est vraie, on exécute instructions (corps

de la boucle), puis, on retourne tester la condition. Si
elle est encore vraie, on répète l'exécution, …

 Si la condition est fausse, on sort de la boucle et on

exécute l'instruction qui est après FINTANQUE.

Reproduction 80
LA boucle « TANT QUE … FAIRE… » : REMARQUES
 Le nombre d'itérations dans une boucle TANTQUE…FAIRE
n'est pas connu au moment d'entrée dans la boucle. Il
dépend de l'évolution de la valeur de condition.
 Une des instructions du corps de la boucle doit
absolument changer la valeur de condition de vrai à
faux (après un certain nombre d'itérations), sinon le
programme tourne indéfiniment.
Exemple de boucle infinie :
i 2
TANTQUE (i > 0)
i  i+1 (attention aux erreurs de frappe : + au lieu
de -)
FINTANQUE Reproduction 81
LA boucle « TANT QUE … FAIRE…» : EXEMPLE 1

Variable i : entier
DEBUT
i  0
TANTQUE (i < 3)
Ecrire("Bonjour tout le monde ")
i  i + 1
FINTANQUE
FIN

Reproduction 82
LA boucle « TANT QUE … FAIRE… » : EXEMPLE 2

Variable A : entier
DEBUT
A  10
TANTQUE (A > 0)
A  A - 2
FINTANTQUE
Ecrire(" La valeur de A est : ", A)
FIN

Reproduction 83
LA boucle « REPETER … JUSQU’À...»

REPETER
Instruction(s)
JUSQU’À
(condition)

 La condition est évaluée après chaque itération

 Les instructions entre REPETER et JUSQU’À sont
exécutées au moins une fois et leur exécution est
répétée jusqu’à ce que condition soit vrai (tant qu'elle
est fausse)
Reproduction 84
LA boucle « REPETER … JUSQU’À... » : EXEMPLE 1

Variables c : entier
DEBUT
REPETER
Lire(c)
c  c*c
Ecrire(c)
JUSQU’À (c = 0)
Ecrire("Fin")
FIN

Reproduction 85
LA boucle « REPETER … JUSQU’À... » : EXEMPLE 2
Variables a , somme , moyenne , compteur : entier
DEBUT
compteur  0
somme  0
REPETER
Ecrire(" Entrez un nombre : " )
Lire(a)
compteur  compteur + 1
somme  somme + a
JUSQU’À (a = 0)
Moyenne  somme / compteur
Ecrire(" La moyenne de valeurs saisies est : " ,
moyenne)
FIN

Reproduction 86
La boucle « POUR… FAIRE»
POUR compteur de initiale à finale pas valeur_de_pas
FAIRE
Instruction(s)
FINPOUR

Remarque : Si la valeur du « pas » n’est pas

précisée dans l’instruction « POUR », elle est par
défaut égale à un (1).
Reproduction 87
La boucle « POUR …FAIRE»
 Remarque : le nombre d'itérations dans une boucle
POUR est connu avant le début de la boucle.
 La variable compteur est en général de type entier. Elle
doit être déclarée.
 Pas est un entier qui peut être positif ou négatif. Pas
peut ne pas être mentionné, car par défaut sa valeur
est égal à 1. Dans ce cas, le nombre d'itérations est
égal à finale - initiale + 1 .
 Initiale et peuvent être des valeurs, des
finale
variables définies avant le début de la boucle ou des
expressions de même type que compteur .
Reproduction 88
DEROULEMENT DE La boucle « POUR …FAIRE»

1) La valeur initiale est affectée à la variable compteur.

2) On compare la valeur du compteur et la valeur de
finale :
a) Si la valeur du compteur est > à la valeur finale dans
le cas d'un pas positif (ou si compteur est < à finale
pour un pas négatif), on sort de la boucle et on continue
avec l'instruction qui suit FINPOUR.
b)Si compteur est <= à finale dans le cas d'un pas
positif (ou si compteur est >= à finale pour un pas
négatif), instructions seront exécutées.
i. Ensuite, la valeur de compteur est incrémentée de la
valeur du pas si pas est positif (ou décrémenté si pas
est négatif) . Reproduction 89
La boucle « POUR …FAIRE» : EXEMPLE 1

 Ecrire un algorithme qui fait le calcul de x à la

puissance n où x est un réel non nul et n un
entier positif ou nul

Reproduction 90
La boucle « POUR …FAIRE» : EXEMPLE 1
Variables x, puiss : réel
n, i : entier
DEBUT
Ecrire(" Entrez la valeur de x ")
Lire(x)
Ecrire(" Entrez la valeur de n ")
Lire(n)
puiss  1
POUR i de 1 à n FAIRE
Puiss puiss*x
FINPOUR
Ecrire(x, " à la puissance ", n, " est égal à ",
puiss)
FIN

Reproduction 91
La boucle « POUR …FAIRE» : EXEMPLE 1 (VERSION 2)
Calcul de x à la puissance n où x est un réel non nul et n
un entier positif ou nul (version 2 avec un pas
négatif)
Variables x, puiss : réel
n, i : entier
DEBUT
Ecrire(" Entrez respectivement les valeurs de x et n
")
Lire(x,n)
puiss  1
POUR i de n à 1 pas -1 FAIRE
puiss puiss*x
FINPOUR
Ecrire(x, " à la puissance ", n, " est égal à ",
puiss)
FIN Reproduction 92
La boucle « POUR …» : REMARQUE
 Il faut éviter de modifier la valeur du compteur (et de
finale) à l'intérieur de la boucle. En effet, une telle action
:
 Perturbe le nombre d'itérations prévu par la boucle
POUR
 Rend difficile la lecture de l'algorithme
 Présente le risque d'aboutir à une boucle infinie
POUR i de 1 à 5 FAIRE
Exemple :i  i-1
Ecrire(" i = ", i)
FINPOUR

Reproduction 93
LIEN ENTRE « POUR …» & « TANT QUE
… » La boucle POUR est un cas particulier de TANTQUE (cas où le
nombre d'itérations est connu et fixé) . Tout ce qu'on peut
écrire avec POUR peut être remplacé avec TANTQUE (la
réciproque est fausse)
POUR compteur de initiale à finale pas valeur_de_pas FAIRE
Instruction(s)
FINPOUR
Peut être compteur  initiale
remplacé par : TANTQUE (compteur <= finale)
(cas d'un pas
instructions
positif)
compteur  compteur + pas
FINTANQUE

Reproduction 94
LIEN ENTRE « POUR …» & « TANT QUE …» :
EXERCICE

 Calcul de x à la puissance n où x est un réel

non nul et n un entier positif ou nul (version
avec TANTQUE…FAIRE)

Reproduction 95
LIEN ENTRE « POUR …» & « TANT QUE …» :
SOLUTION
Variables x, puiss : réel
n, i : entier
DEBUT
Ecrire(" Entrez la valeur de x ")
Lire(x)
Ecrire(" Entrez la valeur de n ")
Lire(n)
puiss  1
i  1
TANTQUE (i<=n)
Puiss puiss*x
i  i+1
FINTANTQUE
Ecrire(x, " à la puissance ", n, " est égal à ",puiss)
FIN

Reproduction 96
BOUCLE IMBRIQUEES
 Les instructions d'une boucle peuvent être des
instructions itératives. Dans ce cas, on aboutit à
des boucles imbriquées

 Exemple 1 : Ecrire un carré de 8 fois 8

caractères ‘x’ POUR i de 1 à 8 FAIRE
POUR j de 1 à 8 FAIRE
Ecrire("x")
FINPOUR
FINPOUR

Reproduction 97
BOUCLE IMBRIQUEES
Exempl Exécuti
e2 on
POUR i de 1 à 5 FAIRE
POUR j de 1 à i FAIRE
Ecrire("O")
FINPOUR
Ecrire("X")
FINPOUR

Reproduction 98
CHOIX D’UN TYPE DE BOUCLE
(1)  Si on peut déterminer le nombre d'itérations
avant l'exécution de la boucle, il est plus naturel
d'utiliser la boucle POUR.
 S'il n'est pas possible de connaître le nombre
d'itérations avant l'exécution de la boucle, on fera
appel à l'une des boucles TANTQUE ou REPETER
JUSQU’À.
 Pour le choix entre TANTQUE et REPETER JUSQU’À :
 Si on doit tester la condition de contrôle avant
de commencer les instructions de la boucle, on
utilisera TANTQUE.
 Si la valeur de la condition de contrôle dépend
d'une première exécution des instructions de
Reproduction 99
CHOIX D’UN TYPE DE BOUCLE
(2)
SI nombre d'itérations connu ALORS
Boucle POUR
SINON
SI itération exécutée au moins une fois
ALORS
Boucle REPETER JUSQU’À
SINON
Boucle TANTQUE
FINSI
FINSI
Reproduction 100
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE VII
Les tableaux

Reproduction 101
TABLEAUX : DEFINITION

 Un tableau est un ensemble d'éléments de

même type désignés par un identificateur
unique.

 Une variable entière nommée indice permet

d'indiquer la position d’un élément donné au
sein du tableau et de déterminer sa valeur.

 La déclaration d'un tableau s'effectue en

précisant le type de ses éléments et sa
dimension (le nombre de ses éléments).

Reproduction 102
LES TABLEAUX : DECLARATION
variable tableau identificateur[dimension] :
type

Exemple :
variable tableau notes[30] : réel
 On peut définir des tableaux de tous types :
tableaux d'entiers, de réels, de caractères, de
booléens, de chaînes de caractères, …

Reproduction 103
TABLEAUX : REMARQUES
 L'accès à un élément du tableau se fait au
moyen de l'indice. Par exemple, notes[i] donne
la valeur de l'élément i du tableau notes.

 Selon les langages, le premier indice du tableau

est soit 0, soit 1. Le plus souvent (au niveau
algorithmique) c'est 1 (c'est ce qu'on va adopter
en pseudo-code).

 Un grand avantage des tableaux est qu'on peut

traiter les données qui y sont stockées de façon
simple en utilisant des boucles.

Reproduction 104
TABLEAUX : REMARQUES
 Un tableau peut être représenté graphiquement par
(exemple Note[15]) :

 Note[2]  15 met la valeur 15 dans la 2ème case du

tableau.
 En considérant le cas où a est une variable de type entier, a
 Note[2] met la valeur de la 2ème case du tableau dans a,
c’est- à- dire 15.
 Lire(Note [1]) met l’entier saisi par l’utilisateur dans la
première case du tableau.
 Ecrire(Note [1]) affiche la valeur de la première case du
Reproduction 105
TABLEAUX : SAISIE & AFFICHAGE

 Algorithme qui permet de saisir et d'afficher les

éléments d'un tableau de 30 notes:

Reproduction 106
TABLEAUX : SAISIE & AFFICHAGE
(SOLUTION)
Variables i : entier
Tableau notes[30] : réel
DEBUT
POUR i de 1 à 30 FAIRE
Ecrire("Saisie de l'élément ", i )
Lire(notes[i] )
FINPOUR
POUR i de 1 à 30 FAIRE
Ecrire(" notes[",i, "] =", notes[i])
FINPOUR
FIN

Reproduction 107
TABLEAUX : EXEMPLE (1)

 Pour le calcul du nombre d'étudiants ayant une

note supérieure strictement à 10 avec les
tableaux, on peut écrire :

Reproduction 108
TABLEAUX : EXEMPLE (1)
Variables i, nbre : entier
Tableau notes[30] : réel
DEBUT
nbre  0
POUR i de 1 à 30 FAIRE
SI (notes[i] >10) ALORS
nbre  nbre+1
FINSI
FINPOUR
Ecrire(" Le nombre de notes supérieures à 10 est : ",
nbre)
FIN

Reproduction 109
TABLEAUX : EXEMPLE (2)

 Soit T un tableau de vingt éléments de types

entiers. Un algorithme qui permet de calculer la
somme des éléments de ce tableau.

Reproduction 110
TABLEAUX : EXEMPLE (2)

Variables i , somme : entier

Tableau T[20] : entier
DEBUT
somme  0
POUR i de 1 à 20 FAIRE
somme  somme + T[i]
FINPOUR
Ecrire(" La somme de tous les éléments du tableau est : " ,
somme)
FIN

Reproduction 111
TABLEAUX : EXERCICE

 Soit T un tableau de N entiers. Ecrire l’algorithme qui

détermine le plus grand élément de ce tableau.

Reproduction 112
TABLEAUX : EXERCICE (SOLUTION)
Variables i , max : entier
Tableau T[N] : entier
DEBUT
max  T[1]
POUR i de 2 à N FAIRE
SI (T[i] > max) ALORS
max  T[i]
FINSI
FINPOUR
Ecrire(" Le plus grand élément de ce tableau : " , max)
FIN

Reproduction 113
TABLEAUX A DEUX DIMENSIONS
 Les langages de programmation permettent de déclarer
des tableaux dans lesquels les valeurs sont repérées
par deux indices. Ceci est utile par exemple pour
représenter des matrices.
matrices
 En pseudo code, un tableau à deux dimensions se
déclare ainsi :
variable tableau identificateur[dimension1][dimension2] :
type
 Exemple : une matrice A de 3 lignes et 4 colonnes
dont les éléments sont réels
variable tableau A[3][4] : réel
 A[i][j] permet d'accéder à l’élément de la matrice qui
se trouve à
Reproduction 114
LECTURE D’UNE MATRICE

 Algorithme qui permet de saisir les éléments

d'une matrice de vingt lignes et cinquante
colonnes :

Reproduction 115
LECTURE D’UNE MATRICE
Algorithme Saisie_Matrice
variables i, j : entier
Tableau A[20][50] : réel
DEBUT
POUR i de 1 à 20 FAIRE
Ecrire("Saisie de la ligne ", i )
POUR j de 1 à 50 FAIRE
Ecrire("Entrez l'élément de la ligne ", i , " et de la colonne ",
j)
Lire(A[i][j])
FINPOUR
FINPOUR
FIN

Reproduction 116
AFFICHAGE D’UNE MATRICE

 Algorithme qui permet d'afficher les éléments

d'une matrice de vingt lignes et cinquante
colonnes :

Reproduction 117
AFFICHAGE D’UNE MATRICE
Algorithme Affiche_Matrice
Variables i, j : entier
Tableau A[20][50] : réel
DEBUT
POUR i de 1 à 20 FAIRE
POUR j de 1 à 50 FAIRE
Ecrire("A[",i, "] [",j,"]=", A[i][j])
FINPOUR
FINPOUR
FIN

Reproduction 118
SOMME DE DEUX MATRICES

 Algorithme qui calcule la somme de deux

matrices de vingt lignes et cinquante colonnes :

Reproduction 119
SOMME DE DEUX MATRICES

Algorithme Somme_Matrices
Variables i, j : entier
Tableau A[20][50] , B[20][50] , C[20][50] :
réel
DEBUT
POUR i de 1 à 20 FAIRE
POUR j de 1 à 50 FAIRE
C[i][j]  A[i][j]+B[i][j]
FINPOUR
FINPOUR
FIN

Reproduction 120
Tableaux à N dimensions
 Les tableaux à n dimensions (n>2), peuvent être utilisés
pour diverses raisons telles que la création et le traitement
des objets 3D par exemple qui nécessitent des tableaux de
3 dimensions au minimum.
 La déclaration de ce type de tableaux est comme suit :
Syntaxe :
Tableau nom_tableau[taille1][taille2] … [tailleN] :
type
Exemple : Tableau T[10][20][50] : réel (*un tableau T
à 3 dimensions*)
 La manipulation d’un tableau à plusieurs dimensions suit le
même principe que celle des tableaux à deux dimensions.
Ceci s’appuie sur l’utilisation des boucles imbriquées pour
parcourir le tableau, de sorte qu’il y aura autant de boucles
Reproduction 121
qu’il y a de dimensions.
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE VIII
Les STRUCTURES

Reproduction 122
DEFINITION
 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

Reproduction 123
DECLARATION
 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 :

Reproduction 124
EXEMPLE

elt : STRUCTURE
nom : chaîne de caractères /* nom de
l'élément */
symbole : chaîne de caractères /* symbole
chimique */
Z : entier /* numéro atomique */
masse : réel /* masse atomique
*/
FINSTRUCTURE
Remarque : il est utile d'indiquer les rôles des
champs (comme pour les variables simples)

Reproduction 125
ACCES AU CHAMPS
Syntaxe<identificateur>.<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
Reproduction 126
procédure ou de fonction : Echanger(elt1.Z,
DEFINITION 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 :
Type <Nomtype> = <définition du type>

 Les déclarations qui utilisent un type défini se font

comme avec les types prédéfinis.

Reproduction 127
DEFINITIONS DE TYPE & DECLARATION DE VARIABLES

Définition de type :
Type t_tab = tableau[15] d'entiers

Déclaration de variable :
Variable tab : t_tab

Définition de type :
Type t_matrice = tableau[3][5] de caractères
Déclaration de variable :
Variable mat : t_matrice

Reproduction 128
DEFINITIONS DE TYPE & DECLARATION DE VARIABLES

Définition de type :
Type t_elt = STRUCTURE
nom : chaîne de caractères /* nom de
l'élément */
symbole : chaîne de caractères /* symbole
chimique */
Z : entier /* numéro atomique */
masse : réel /* masse atomique
*/
FINSTRUCTURE

Déclaration
Remarque : les de noms
variable :
de types suivent les règles des
identificateurs.
Variable C'est par simple commodité, pour les
elt : t_elt
distinguer des identificateurs des variables, que ceux des
exemples commencent par t_.
Reproduction 129
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

slides suivants donnent des exemples simples.

Reproduction 130
TABLEAUX DE STRUCTURES
Exemple : table des éléments
chimiques

Définitions des types :

Type t_elt = STRUCTURE
nom : chaîne de caractères /* nom de
l'élément */
symbole : chaîne de caractères /* symbole
chimique */
Z : entier /* numéro atomique */
masse : réel /* masse atomique
*/
FINSTRUCTURE

Variable t_table : tableau[120] de t_elt

Reproduction 131
TABLEAUX DE STRUCTURES

 Déclaration :
Variable 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'

Reproduction 132
STRUCTURES AVEC TABLEAUX
Exemple : liste de températures avec nombre,
minimum et maximum.

Définitions des types :

Type t_temp = tableau[100] de réel
Type t_liste = STRUCTURE
temp : t_mesure /* tableau des températures */
nb : entier /* nombre de
températures */
tmin : réel /* température minimale
*/
tmax : réel /* température maximale
*/
Reproduction
FINSTRUCTURE 133
STRUCTURES AVEC TABLEAUX

Déclaration :

Variable mesures : t_liste

Accès à un élément :

[Link] vaut 5

[Link][3] vaut 6,3

Reproduction 134
CONCLUSION STRUCTURES DE DONNEES

 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
Reproduction 135
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE IX
Les POINTEURS

Reproduction 136
LA MÉMOIRE CENTRALE

 La mémoire centrale (MC), qui peut

être vue comme un vecteur, est formée
de plusieurs cases ou cellules
numérotées (0, 1, 2, 3, 4, 5, etc.)
 Chaque case peut stocker 1 octet (8
bits ou 1 byte).
 Toutes les variables et instructions
utilisées existent en mémoire centrale.
Reproduction 137
Relation entre la variable & la MEMOIRE

 La variable occupe la mémoire, elle « habite » dans

la mémoire.

 Chaque variable occupe les cases mémoires qui lui

sont dédiées.

 Une variable de type caractère occupe 1 case

mémoire, soit 1 octet. Un entier va occuper 4 cases
Variable x 4 octets,
mémoires soit : un réel xoccupe soit 4 soit 8
entier
cases mémoire selon la précision
10 souhaitée.
DEBUT
100
x10

Reproduction 138
Relation entre la variable & la MEMOIRE
 x étant une variable de type entier, elle nécessite
4 cases ou 4 octets dans un espace contigüe pour
la représenter dans la mémoire.
 Supposons que le numéro de la première cellule
de la variable x soit 100, x occupe donc les
cellules ou les octets n°100, 101, 102, 103.
 On dit que la variable x se trouve à partir de
l’adresse 100.
 La mémoire est tellement grande qu’on a intérêt
à avoir l’adresse de chaque variable.
 Adresse ? : l’adresse est le numéro du
premier octet de la variable.
Reproduction 139
Relation entre la variable & la MEMOIRE

 Variable T : tableau [5] d’entier va occuper 5x4

= 20 cases ou octets dans la mémoire.
 Si on suppose que le tableau T commence à
partir de l’octet n°200, on peut déduire que
l’adresse du tableau T est le numéro du premier
octet de du tableau T, c’est-à-dire 200.
 Chaque variable possède 4 caractéristiques :
1) Son nom  x
2) Son type  entier
3) Sa valeur 10
4) Son adresse  100
Reproduction 140
VARIABLES STATIQUES / VARIABLES DYNAMIQUES

 Variable statique : déclarée dans la partie «

Variable », le système lui réserve l’espace
mémoire au moment de la compilation et reste
dans la mémoire jusqu’à la fin de l’algorithme
dans lequel elle est déclarée.

 Variable dynamique : créée ou supprimée à

l’exécution à travers les pointeurs et les
primitives d’allocation et de libération de l’espace
mémoire.

Reproduction 141
NOTION DE POINTEUR
 Un pointeur est une variable qui contient
l’adresse d’une autre variable.

Déclaration :
<NomPointeur> : pointeur sur <TypeVariable> (1)
<NomPointeur> : ˆ <TypeVariable> (2)

Variable x : entier
P : pointeur sur entier (P va contenir l’adresse d’un
entier) ou P : ^Entier

Reproduction 142
NOTION DE POINTEUR

Exemple : x = P^
DEBUT
x  10
P  Adr(x)

On dit que P pointe vers x, ou bien que x est

pointée par P.

P contient l’adresse de x, alors il peut aller

jusqu'à x, il peut travailler sur x.

Reproduction 143
NOTION DE POINTEUR

 Lorsque on dit que P pointe vers x, alors x et

Pˆ ou (Valeur(P)) sont équivalents. Pˆ ou
(Valeur(P)) c’est le contenu de la variable
pointée par P.

P^  5 ou Valeur(P)  5

Reproduction 144
EXERCICE 1
 Décrire l’évolution de chaque variable après
chaque instruction
Algorithme exemple1
Variable x, n : entier
pt : pointeur sur entier
DEBUT
pt  Adr(n)
Valeur(pt)  5 //pt^5
n  7
x  Valeur(pt) // xpt^
FIN

Reproduction 145
QU’Est-ce QU’ON PEUT FAIRE AVEC UN
POINTEUR ?

 On a modifié la valeur de x en utilisant le

pointeur P (adressage indirect).

 Jusqu’à maintenant la seule manière de

modifier x était par affectation ou lecture d’une
autre valeur dans x (adressage direct).

 Ici on a vu qu’on peut manipuler une variable x

en utilisant un pointeur à condition que le
pointeur contienne l’adresse de x.

Reproduction 146
CREER UNE VARIABLE DYNAMIQUE
Type pEntier = pointeur sur entier (définition du type
pEntier)
Variable P : pEntier //P est une variable statique

1. Création de la variable dynamique

La primitive Allouer(P) va faire deux choses :
1. Elle va créer en mémoire une variable
dynamique de type entier
2. L’adresse de l’espace mémoire sera sauvegarder
dans le pointeur P.

Reproduction 147
CREER UNE VARIABLE DYNAMIQUE

2) Manipulation de la variable
dynamique

P^  5 ou Valeur(P)  5

3) Suppression de la variable
dynamique

Libérer(P)

Reproduction 148
CREER UNE VARIABLE DYNAMIQUE
 La primitive Libérer(P) va supprimer la variable dynamique
Pˆ ou Valeur(P) et P va pointer vers une valeur
indéterminée.
 Après Libérer(P), l’instruction suivante Pˆ10 ou
Valeur(P) 10 occasionne une erreur à la compilation car
la variable dynamique Pˆ ou Valeur(P) n’existe plus.
 Pour initialiser une variables de type pointeur qui ne pointe
rien on écrit : PNIL
 Attention, le fait de mettre NIL dans un pointeur ne libère
pas l'emplacement sur lequel il pointait. L'emplacement
devient irrécupérable car le lien vers cet emplacement a été
coupé par la valeur NIL.
 Il faut libérer avant d'affecter le pointeur avec NIL.
Reproduction 149
EXEMPLE 1
 Dérouler l’algorithme suivant
Algorithme Exemple
Variable P,Q : pointeur sur entier
DEBUT
Allouer(P)
Valeur(P)  10 //P^10
Q  P
Valeur(Q)  valeur(P)+2//Q^ = P^+2
Q  NIL
Libérer(P)
FIN

Reproduction 150
EXEMPLE 2

 L'algorithme suivant n'a comme seul but que de

faire comprendre la manipulation des pointeurs.
 Avec des schémas, montrez l'état de la mémoire
en plus de ce qui s'affiche à l'écran.

Reproduction 151
EXEMPLE (CORRIGE)
Variables ptc : pointeur sur chaîne de caractères
ptx1, ptx2 : pointeur sur entier
DEBUT Ptx2^  ptx1^ +
Allouer(ptc) ptx2^

ptc^  ‘chat’ Ecrire(ptx1^, ptx2^)

Ecrire(ptc^) ptx1  NIL

Allouer(ptx1) Ecrire(ptx2^)

Lire(ptx1^) Libérer(ptx2)

ptX2  ptx1 ptx2  NIL

Ecrire(ptx2^) ptc  NIL

FIN
Où est l'erreur ? : on a coupé l'accès à la zone de mémoire sans la
libérer. Elle est irrécupérable
Reproduction 152
VARIABLE DYNAMIQUE DE TYPE TABLEAU
Type Tab = tableau[100] de réel
variable pTab : pointeur sur Tab
P : pTab
i : entier
DEBUT
//1. Création de la variable dynamique
Allouer(P)

Reproduction 153
VARIABLE DYNAMIQUE DE TYPE TABLEAU
//2. Manipulation de la variable dynamique
POUR i de 1 à 100 FAIRE
Pˆ[i]  i // Valeur(P,i)  i
FINPOUR

//2. Suppression de la variable dynamique

Libérer(P)

Reproduction 154
VARIABLE DYNAMIQUE DE TYPE
STRUCTURE
Type STRUCTURE = Date
J, m, a : entier
FINSTRUCTURE
pDate = pointeur sur Date

Variable P : pDate
DEBUT
//1. Création de la variable dynamique
Allouer(P)

Reproduction 155
VARIABLE DYNAMIQUE DE TYPE
STRUCTURE
//2. Manipulation de la variable dynamique

Pˆ.j  14 // Valeur(P,j) 14
Pˆ.m  09 // Valeur(P,m) 09
Pˆ.a  2022 // Valeur(P,a) 2022

//3. Suppression de la variable dynamique

Libérer(P)

Reproduction 156
EXERCICE 2

 Ecrire un algorithme qui calcul la somme de

deux valeurs entières en utilisant des pointeurs.

 Puis interchange leurs valeurs.

Reproduction 157
EXERCICE 2 (CORRIGE)
Algorithme exemple3 ; Allouer(Sauv)
P, Q, Sauv, Som : pointeur sur Valeur(Sauv)Valeur(P)
entier;
Valeur(P)Valeur(Q);
DEBUT
Valeur(Q) Valeur(Sauv)
Allouer(P)
Libérer(Sauv)
Écrire(‘donnez la première
Écrire(‘les nouvelles valeurs sont:
valeur:’)
Valeur(P), ‘et’, Valeur(Q))
Lire(Valeur(P))
Libérer(P)
Allouer(Q)
Libérer(Q)
Écrire(‘donnez la deuxième
FIN
valeur:’)
Lire(Valeur(Q))
Allouer(Som)
Valeur(Som)=Valeur(P)+Valeur(Q);
Écrire(‘La somme=‘, Valeur(Som))
Libérer(Som);
Reproduction 158
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE X
PROCEDURES & FONCTIONS

Reproduction 159
INTRODUCTION
 Lorsque l'on progresse dans la conception d'un
algorithme, ce dernier peut prendre une taille et
une complexité croissante.
 De même des séquences d'instructions peuvent se
répéter à plusieurs endroits.
 Un algorithme écrit d'un seul tenant devient
difficile à comprendre et à gérer dès qu'il dépasse
deux pages.
 La solution consiste alors à découper l'algorithme
en plusieurs parties plus petites. Ces parties sont
appelées des sous-algorithmes.
 Le sous-algorithme est écrit séparément du corps
de l'algorithme principal et sera appelé par celui-ci
quand ceci seraReproduction
nécessaire.
160
LES PROCEDURES

 Une procédure est une série d'instructions

regroupées sous un nom, qui permet
d'effectuer des actions par un simple appel de
la procédure dans un algorithme ou dans un
autre sous-algorithme.

 Une procédure ne renvoie aucune valeur.

Reproduction 161
DECLARATION D’UNE PROCEDURE
Syntaxe :
Procédure nom_proc(liste de paramètres)
Variables identificateurs : type
DEBUT
Instruction(s)
FINPROCEDURE

 Après le nom de la procédure, il faut donner la

liste des paramètres (s'il y en a) avec leur type
respectif.
 Ces paramètres sont appelés paramètres
formels.
 Leur valeur n'est pas connue lors de la création
Reproduction 162
de la procédure
EXEMPLE

 Ecrire une procédure qui affiche à l'écran

une ligne de 15 étoiles puis passe à la ligne
suivante.

Reproduction 163
EXEMPLE (CORRIGE)
Procédure Etoile()
Variables i : entier
DEBUT
POUR i de 1 à 15 FAIRE
Ecrire("*")
FINPOUR
Ecrire("retour à la ligne ")
FINPROCEDURE

Reproduction 164
L’APPEL D’UNE PROCEDURE
 Pour déclencher l'exécution d'une procédure dans
un programme, il suffit de l'appeler.
 L'appel de procédure s'écrit en mettant le nom de la
procédure, puis la liste des paramètres, séparés par
des virgules.
 A l'appel d'une procédure, le programme interrompt
son déroulement normal, exécute les instructions de
la procédure, puis retourne au programme appelant
et exécute l'instruction suivante.
Nom_Proc(liste de paramètres)

 Les paramètres utilisées lors de l'appel d'une

procédure sont appelés paramètres effectifs. Ces
paramètres donneront leurs valeurs aux paramètres
Reproduction 165
EXEMPLE

 En utilisant la procédure Etoiles déclarée dans

l'exemple précédent, écrire un algorithme
permettant de dessiner un carré d'étoiles de 15
lignes et de 15 colonnes.

Reproduction 166
EXEMPLE (CORRIGE)
Algorithme carré_étoiles
Variables j : entier
//Déclaration de la procédure Etoiles()
Procédure Etoile()
Variables i : entier
DEBUT
POUR i de 1 à 15 FAIRE
Ecrire("*")
FINPOUR
Ecrire(" retour à la ligne ")
FINPROCEDURE

Reproduction 167
EXEMPLE (CORRIGE)

//Algorithme principal (Partie principale)

DEBUT
POUR j de 1 à 15 FAIRE
//Appel de la procédure Etoiles
Etoile()
FINPOUR
FIN

Reproduction 168
REMARQUES

1. Pour exécuter un algorithme qui contient des

procédures et des fonctions, il faut commencer
l'exécution à partir de la partie principale
(algorithme principal)

2. Lors de la conception d'un algorithme deux

aspects apparaissent :

 La définition (déclaration) de la procédure ou

fonction.

 L'appel de la procédure ou fonction au sein de

l'algorithme principal.
Reproduction 169
PASSAGE DE PARAMETRES
 Les échanges d'informations entre une
procédure et le sous algorithme appelant se font
par l'intermédiaire de paramètres.

 Il existe deux principaux types de passages de

paramètres qui permettent des usages
différents :

1. Passage par valeur :

Dans ce type de passage, le paramètre
formel reçoit uniquement une copie de la
valeur du paramètre effectif. La valeur du
paramètre effectif ne sera jamais
modifiée. Reproduction 170
PASSAGE DE PARAMETRES
Exemple :
Soit l'algorithme suivant :
//Algorithme
Algorithme Passage_par_valeur principal
Variables N : entier DEBUT
//Déclaration de la procédure P1 N  5
Procédure P1(A : entier) P1(N)
DEBUT Ecrire(N)
A  A * 2 FIN
Ecrire(A)
FINPROCEDURE

Reproduction 171
PASSAGE DE PARAMETRES
 Cet algorithme définit une procédure P1 pour
laquelle on utilise le passage de paramètres par
valeur.

 Lors de l'appel de la procédure, la valeur du

paramètre effectif N est recopiée dans le
paramètres formel A.

 La procédure effectue alors le traitement et

affiche la valeur de la variable A, dans ce cas 10.

 Après l'appel de la procédure, l'algorithme affiche

la valeur de la variable N dans ce cas 5.

 La procédure ne modifie pas le paramètre qui est

Reproduction 172
passé par valeur.
PASSAGE DE PARAMETRES
2. Passage par référence ou par
adresse :

 Dans ce type de passage, la procédure

utilise l'adresse du paramètre
effectif.

 Lorsqu'on utilise l'adresse du paramètre,

on accède directement à son contenu.
La valeur de la variable effectif sera
donc modifiée.

 Les paramètres passés par adresse sont

précédés du mot clé Var.
Reproduction 173
PASSAGE DE PARAMETRES
Exemple :
Reprenons l'exemple précédent
: //Algorithme Principal
Algorithme Passage_par_référence DEBUT
N  5
Variables N : entier
P1(N)
//Déclaration de la procédure P1
Ecrire(N)
Procédure P1 (Var A : entier) FIN
DEBUT
A  A * 2
Ecrire(A)
FINPROCEDURE

Reproduction 174
PASSAGE DE PARAMETRES
A l'exécution de la procédure, l'instruction
Ecrire(A) permet d'afficher à l'écran 10.
 Au retour dans l'algorithme principal,
l'instruction Ecrire(N) affiche également 10.
 Dans cet algorithme le paramètre passé
correspond à la référence (adresse) de la
variable N. Elle est donc modifiée par
l'instruction : A  A*2
Remarque :
 Lorsqu'il y a plusieurs paramètres dans la
définition d'une procédure, il faut absolument
qu'il y en ait le même nombre à l'appel et que
l'ordre soit respecté.
Reproduction 175
LES FONCTIONS

 Les fonctions sont des sous algorithmes

admettant des paramètres et retournant un seul
résultat (une seule valeur) de type simple qui
peut apparaître dans une expression, dans une
comparaison, à la droite d’une affectation, etc.

Reproduction 176
DECLARATION D’UNE FONCTIONS

Syntaxe :
Fonction nom_Fonct (liste de paramètres) : type
Variables identificateur : type
DEBUT
Instruction(s)
Retourner (Expression)
FINFONCTION

Reproduction 177
DECLARATION D’UNE FONCTIONS

 La syntaxe de la déclaration d'une fonction

est assez proche de celle d'une procédure à
laquelle on ajoute un type qui représente le
type de la valeur retournée par la fonction et
une instruction « Retourner Expression ».
 Cette dernière instruction renvoie au
programme appelant le résultat de
l'expression placée à la suite du mot clé
Retourner.

Note :
 Les paramètres sont facultatifs, mais s'il n'y
pas de paramètres, les parenthèses doivent
Reproduction 178
rester présentes.
EXEMPLE
Définir une fonction qui renvoie le plus
grand de deux nombres différents.
//Déclaration de la fonction Max
Fonction Max(X: réel, Y: réel) : réel
DEBUT
SI (X > Y) ALORS
Retouner(X)
SINON
Retouner(Y)
FINSI
FINFONCTION

Reproduction 179
L’APPEL D’UNE FONCTION
 Pour exécuter une fonction, il suffit de faire appel
à elle en écrivant son nom suivie des
paramètres effectifs.

 C'est la même syntaxe qu'une procédure.

 A la différence d'une procédure, la fonction

retourne une valeur.

 L'appel d'une fonction pourra donc être utilisé

dans une instruction (affichage, affectation, ...)
qui utilise sa valeur.

Syntaxe :
Nom_Fonc(list Reproduction
de paramètres) 180
EXEMPLE

Ecrire un algorithme appelant, utilisant la fonction

Max de l'exemple précédent.

Reproduction 181
EXEMPLE (SOLUTION)
Algorithme Appel_fonction_Max
Variables A, B, M : réel
//Déclaration de la fonction Max
Fonction Max(X: réel, Y: réel) : réel
DEBUT
SI (X > Y) ALORS
Retourner(X)
SINON
Retourner(Y)
FINSI
FINFONCTION

Reproduction 182
EXEMPLE (SOLUTION)
//Algorithme principal
DEBUT
Ecrire("Donnez la valeur de A : ")
Lire(A)
Ecrire("Donnez la valeur de B : ")
Lire(B)
//Appel de la fonction Max
M  Max(A,B)
Ecrire("Le plus grand de ces deux nombres est : ",
M)
FIN

Reproduction 183
PORTEE DES VARIABLES
 La portée d'une variable désigne le domaine
de visibilité de cette variable. Une variable peut
être déclarée dans deux emplacements distincts.
 Une variable déclarée dans la partie
déclaration de l'algorithme principale est
appelée variable globale. Elle est accessible de
n'importe où dans l'algorithme, même depuis les
procédures et les fonctions. Elle existe pendant
toute la durée de vie du programme.
 Une variable déclarée à l'intérieur d'une
procédure (ou une fonction) est dite variable
locale. Elle n'est accessible qu’à l’intérieur de la
procédure au sein de laquelle elle définit, les autres
procédures n'y ont pas accès. La durée de vie d'une
Reproduction 184
variable locale est limitée à la durée d'exécution de
PORTEE DES VARIABLES
Algorithme Portée
Variables X, Y : entier X et Y sont des variables globales
Visibles dans tout l’algorithme.
Procédure P1()
Variables A : entier
DEBUT A est une variable locale
… visible uniquement à
l’intérieur de la procédure
FINPROCEDURE
//Algorithme principal
DEBUT
…
FIN

Remarque : Les variables globales sont à éviter pour la

maintenance des programmes.
Reproduction 185
LA RECURSIVITE

Une procédure (ou une fonction) est dite

récursive si elle s'appelle elle-même.

Reproduction 186
EXERCICE

Ecrire une fonction récursive permettant de

calculer la factorielle d'un entier positif.

Reproduction 187
EXERCICE (CORRIGE)
n != n * (n-1) ! : La factorielle de n est n fois la factorielle de
n-1
//Déclaration de la fonction Factorielle (Fact)
Fonction Fact(n : entier) : entier
DEBUT
SI (n > 1) ALORS
Retourner(Fact(n-1)*n)
SINON
Retourner 1
FINSI
FINFONCTION

Reproduction 188
commentaires

 Dans cet exemple, la fonction renvoie 1 si la

valeur demandée est inférieur à 1, sinon elle
fait appel à elle même avec un paramètre
inférieur de 1 par rapport au précédent.

 Les valeurs de ces paramètres vont en

décroissant et atteindront à un moment la
valeur une (1).

 Dans ce cas, il n'y a pas d'appel récursif et

donc nous sortons de la fonction.

Reproduction 189
commentaires

Note :
Toute procédure ou fonction récursive
comporte une instruction (ou un bloc
d'instructions) nommée « point terminal »
permettant de sortir de la procédure ou de la
fonction.
Le « point terminal » dans la fonction
récursive Fact est : retourner 1.

Reproduction 190
AVANTAGES DES PROCEDURES &
FONCTIONS
 Les procédures ou fonctions permettant de ne
pas répéter plusieurs fois une même
séquence d'instructions au sein du
programme (algorithme).

 La mise au point du programme est plus

rapide en utilisant des procédures et des
fonctions. En effet, elle peut être réalisée en
dehors du contexte du programme.

 Une procédure peut être intégrée à un autre

programme, ou elle pourra être rangée dans
une bibliothèque d'outils ou encore utilisée
par n'importe quel programme.
Reproduction 191
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE XI
LES LISTES

Reproduction 192
INTRODUCTION
 Un programme peut manipuler trois types de
données :

Données statiques : occupent un emplacement

réservé au début du traitement (lors de la
compilation), exemple : un tableau.

 Données automatiques : elles sont crées et

détruites en cours d’exécution du programme, elles
représentent les variables locales des fonctions et
des procédures, elles sont gérées sous forme
d’éléments d’une pile dans le segment pile alloué
pour le programme en cours d’exécution.

 Données dynamiques : elles sont crées et

libérées au furReproduction
et à mesure de l’exécution du 193
programme et selon les besoins, exemples : les
INTRODUCTION

 Dans le tableau, il n’ y a que les valeurs, alors que

dans la liste composée de structures, il y a pour
chacune d’elles la valeur et l’adresse de l’élément
suivant.
 Supposons qu’on veut veuille sauvegarder en
mémoire tous les nombres premiers inférieurs ou
égaux à n avec n strictement positif.
 Est-ce que vous connaissez tous les nombres
premiers qui sontReproduction
inférieurs ou égaux à n ? 194
ALGORITHMES & STRUCTURES DE
DONNEES
 Vous ne les connaissez pas car vous ne connaissez
même pas la valeur de n, parce que la valeur de n
est donnée par l’utilisateur.

 Il peut donner n=10, n=100, comme il peut

donner n=1 million, tout dépend de ce qu’il va
saisir au clavier.

 On ne sait donc pas le nombre d’éléments qu’on

peut sauvegarder en mémoire.

 L’utilisation d’un tableau nécessite que la taille de

ce dernier soit connue d’avance.

 En effet à chaque fois que je trouve un nombre

premier, je le stocke en mémoire
Reproduction 195
ALGORITHMES & STRUCTURES DE
DONNEES

 A chaque fois que je vais trouver un nombre

premier, je vais réserver un espace mémoire dédiée
à un entier afin d’ y stocker la valeur du nombre
premier

 Supposons que vous voulons afficher les éléments…

Existe-t-il un moyen pour le faire ?

 La solution du tableau ne convient pas !

Reproduction 196
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE XI
LES LISTES

Reproduction 197
DEFINITION
 Une liste est un ensemble fini d’éléments
ordonnés, chaque élément contient un ou
plusieurs champs.

 Le premier élément de la liste est appelé «

Tête ».

 Le dernier élément est appelé « Queue »

 Chaque élément possède un successeur sauf

la queue (son successeur est la valeur NIL).

Reproduction 198
OPERATIONS SUR LES LISTES

 On distingue deux sortes d’opérations sur les listes :

 Les opérations qui concernent les éléments de la
liste
 Les opérations concernant la liste elle-même.

1. Les opérations sur « les éléments » de la liste :

 Insérer un élément (la 1ère place, en queue, au
milieu)
 Supprimer un élément (le 1ère élément, le dernier
élément, un élément au milieu)
 Rechercher un élément afin d’afficher le contenue
ou le modifier.
Reproduction 199
OPERATIONS SUR LES LISTES
2. Les opérations globales sur la liste elle-même :
En plus des opérations vues précédemment, d’autres peuvent
être s’effectuent sur la liste elle-même tels que :
 Tester si la liste est vide.
 Création d’une liste.
 Vider une liste.
 Calculer le nombre d’éléments dans une liste.
 Trier une liste.
 Fusionner deux listes : consiste à regrouper 2 listes en
une seule.
 Eclatement d’une liste : consiste a diviser la liste
originale en 2 sous listes.
 Etc... Reproduction 200
REPRESENTATION CONTIGÜE
 Il existe plusieurs méthodes pour implémenter des
listes.
 Les plus courantes sont l’utilisation des tableaux
(représentation contiguë) et de pointeurs
(représentation chainée).
1. La représentation contiguë (Tableau) :
Les éléments de la liste sont simplement rangés dans
le tableau à leur place respective séquentiellement
(les uns à la suite des autres)
a) Inconvénients
L’utilisation de tableaux possède quelques
inconvénients :
[Link] dimension d’un tableau doit être définie lors
Reproduction 201
REPRESENTATION CONTIGÜE
Solution : définir un tableau dont la taille sera
suffisante pour accueillir le plus grand nombre
d’éléments
 Gaspillage d’espace mémoire pour des
petites listes.
 Si la taille maximum venait à être
augmentée, il faudrait modifier le
programme et le recompiler
[Link]’on veut retirer (ou insérer) un élément
du tableau « en début », il est nécessaire de
décaler tous les éléments situés après
l’élément supprimé.
b) Avantages :
i.L’accès au KReproduction
ème
élément est immédiate : T[K] 202
REPRESENTATION CHAÎNEE
2. La représentation chaînée (utilisation des
pointeurs) :
 Une liste chaînée est une structure linéaire qui n'a
pas de dimension fixée à sa création.
 Ses éléments de même type sont dispersés dans la
mémoire et reliés entre eux par des pointeurs.
 Un élément ou maillon d’une liste est toujours une
structure (Objet composé) avec deux ou plusieurs
champs :
 Un ou plusieurs champ  Valeur : contenant
l’information
 Un champ  Adresse : donnant l’adresse du
prochain élément.
Reproduction 203
REPRESENTATION CHAÎNEE
 La liste est accessible uniquement par sa tête de
liste c’est-à-dire son premier élément.

3. Structure d’un élément :

Un élément de la liste est une structure de donnée
définie comme suite :
Type element = STRUCTURE
Champ_1 : Type1
....
Champ_N : TypeN
Suivant : ^element
FINSTRUCTURE
Reproduction 204
REPRESENTATION CHAÎNEE
 Apres la déclaration de la structure élément, on
peut créer des élément dynamiques en utilisant
les pointeurs :
Variable E : ^element
Allouer(E)

Le résultat d’exécution de ce bloc d’instructions est

le suivant :
E^.champ_1 E^.Suivan
E
t
#100
Champ_1 … Champ_N Suivant

E^

Reproduction 205
C’EST QUOI UNE LISTE EXACTEMENT ?
 La déclaration d’un tableau T de N éléments mène
à la création de N variables : T[1],
T[2], ...,T[N] et T.
 T : un pointeur (adresse) de la première case.
 En quelque sorte, on peut dire que le tableau dans
un programme n’est que l’adresse de la 1ère case =
&T[0]
 Comme pour les tableaux, une liste n’est que
l’adresse du premier élément (Tête) de la liste.
La liste vide :
Une liste est dite vide si elle ne contient aucun
Liste
élément. En d’autre terme, une liste vide est un
NIL
pointeur qui est égale à NIL.
Variable Liste : ^element
Reproduction 206
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE XI
LES PILES & FILES

Reproduction 207
ALGORITHMES & STRUCTURES DE
DONNEES

CHAPITRE XII
LES FICHIERS

Reproduction 208