Structures de Données I - 2022 - UAM

Structure des données I
PAR SOUMAILA M., ING., OCP,OCE

EXPERT CERTIFIÉ ORACLE
1
Présentation
➢ Directeur centre de Formation professionnelle DGI
❖ Expert informaticien du Projet SyGMEF
19 ans d’expériences dans le domaine des systèmes d’informations
Certifié Expert Oracle performance Tuning
Certifié professionnel Database administrateur (11g, 12c)
Ingénieur en mathématiques appliquées et informatique(jan,2004)
Plusieurs formations: Linux, oracle, Microsoft sql serveur , ITIL,

Leadership, cisco, php, html5, css3… Adobe suite
Compétences: SE oracle linux, bases de données : oracle, SQL

serveur, Mysql
Développement: site web sur JOOMLA, liferay, dreamweaver
Gestion documentaire sur Alfresco
Etc.
2
Informations pratiques
15 heures de cours;
15 heures TD;
10 heures de TP;
Evaluation
◦ Examen 75%
◦ TM 20%
◦ Présence 5%
3
Plan du Cours
Introduction
Rappel sur l’algorithmique;
Notion du langage java J.SE;
Structures données
◦ Listes- liées (simple et doublement);
◦ File(queue);
◦ File à priorité;
◦ Pile (stack);
◦ Array-vecteur;
◦ Arbre;
◦ Monceau (heap);
◦ Table de hachage(hash table);
◦ Graphe.
4
Références du cours
Ce cours vous a été préparé sur la base des références suivantes:
Data structures and Algorithm in Java, Mitchel Waite, Edition signature series ed.1998
Data structures in Java, a laboratory course, SANDRA Anderson ed. 2002
Object-oriented Data structures in Java, NELL DALE, DANIEL JOYCE ed. 2002
INF3015 Structures de données et algorithme, Notes de cours , Éric Beaudry Département

d’informatique ,Université du Québec à Montréal (UQAM)
www.geeksforgeeks.org
http://mbodjsystem.sn
http://udemy.com
http://pluralsight.org
………
5
Introduction
6
Introduction 1/5
Une structure de données est une manière d’organiser et de stocker
l’information en vue de faciliter l’accès ou pour d’autres buts.
Une structure de données a une interface qui consiste en un ensemble de

procédures pour ajouter, effacer, accéder, réorganiser les données, elle
conserve des données et éventuellement des métadonnées.
Notre cours porte sur les structures de données crées et organisées en
mémoire dans un programme encours d’exécution.
Résumé du cours
7
Introduction 2/5
Structures de données standards
Liste : collection d’objets ordonnées accessible à partir de leur position;
Pile : collection d’objets accessible selon une politique LIFO;
File : collection d’objets accessible selon une politique FIFO;
File double: combinaison des accès LIFO et FIFO;
File a priorité : accès uniquement à l’élément de clé (priorité) maximale;
Vecteur: collection d’objet ordonnées accessible à partir de leur rang;
Arbre
◦ Arbre binaire et arbre binaire de recherche;
Monceau (heap)= arbre binaire complet, chaque nœud parent est supérieur ou égal aux
fils;
Table de hachage;
Graphe.
Résumé du cours
8
Introduction 3/5
Opérations standard sur les
structures
Deux types: recherche, accès au données et modifications
Recherche
◦ Recherche (S,k) : retourne un pointeur x vers un élément dans S tel que x,
key=k, ou Nil si un tel élément n’appartient pas à S;
◦ Minimum(S) , Maximum(S): retourne un pointeur vers l’élément avec la plus
petite clé;
◦ Successeur(S,x), Predecesseur(S, x) retourne un pointeur vers l’élément tout
juste plus grand( resp. petit) que x dans S, NIL si x est le maximum;
Modification
◦ Insert(S,x): insère l’élément x dans S
◦ Supprimer(S,x): supprime l’élémént x dans S
9
Introduction 4/5
Implémentation d’une structure de
données
Les briques de base pour implémenter une structure de données
dépendent du langage d’implémentation
◦ Dans ce cours, les principaux outils de JAVA utilisés sont: tableaux(vecteur),
structures (objets avec attributs), listes liées (simple, doubles, …)
◦ Une structure de données peut être implémentée à l’aide d’une autre
structure de données de base ou non(ex. les arbres ; listes liées.
On peut implémenter les structures des données avec plusieurs langages

(c, python, java, c#, c++…).
10
Introduction 5/5
Structures de données et
algorithme
La plupart des bons algorithmes fonctionnent grâce à une méthode
astucieuse pour organiser les données qu’est: Les structures de données.
11
Pourquoi structure des
données?
12
Rappel sur l’algorithmique
13
Algorithmes 1/2
L'algorithmique est l’ensemble des règles et des techniques qui sont
impliquées dans la définition et la conception d'algorithmes, c'est-à-dire
de processus systématiques de résolution d'un problème permettant de
décrire les étapes vers le résultat. : http://fr.wikipedia.org/wiki/Algo;
L’algorithme est une manière bien structuré pour trouver des solutions
aux problèmes informatique ;
-Cormel et Al
Un ensemble fini de règles qui comprend une séquence d’opérations

pour résoudre spécifiquement un problème;
D. Knuth
Mot provenant du nom d’un mathématicien arabe du IXeme siècle EL-
Khawarizim
Résumé du
cours
14
Algorithmes 2/2
✓ Permet de résoudre un problème donné;
ex: Trier une liste de noms par ordre alphabétique
✓ Procédures de calcul bien définie;

✓ Séquences d'instructions élémentaires;
◦ termine en un temps fini
◦ prend une ou des valeur(s) en entrée
◦ donne une ou des valeur(s) en sortie
15
Exemple
Exemple de problème à résoudre:
Comment trier une liste d'élèves par ordre alphabétique?
Input: liste non triée

Output: liste triée
Algo: ???
16
Types de problèmes
1. Tris d'éléments d'une liste;
2. Recherche d'un élément;
3. Calcul sur des chaînes (caractères, nombres, bits, ...);
4. Problèmes de graphes;
5. Problèmes combinatoires;
6. Problèmes géométriques;
7. Problèmes numériques.
17
Algorithme et Programme
Un algorithme est implémenté dans un langage de programmation
Un même algorithme peut être implémenté dans différents langages (Java,

C, Python, c++, ...)
18
Validité d'un algorithme
Précondition
◦ doit être vérifiée avant un traitement donné;
◦ garantit que la possibilité de déroulement du traitement.
Postcondition
◦ doit être vérifiée après le déroulement du traitement,
◦ garantit que le traitement a bien permis de réaliser ce pourquoi il a été réalisé.
Invariant
◦ condition qui est toujours vraie,
◦ caractérise l'état interne de tout ou partie d'un algo.
19
Conception d'un algorithme
Stratégie de résolution d'un problème:
Approche incrémentale
◦ itérer jusqu'à obtention du résultat souhaité
Approche récursive
◦ diviser pour régner:
◦ diviser en sous-problemes;
◦ régner sur les sous-problemes;
◦ combiner les solutions des sous-problemes.
20
Structures de contrôle
Structures de contrôle conditionnelles
◦ Si cond Alors instr FinSi
◦ Si cond Alors instr sinon instr FinSi
(imbrications possibles)
Structures de contrôle itératives

◦ TantQue cond Faire instr FinTantQue
◦ variantes
(imbrications possibles)
21
Validité d'une boucle
Invariant de boucle
◦ Initialisation
◦ Montrer que I est vrai avant d'entrer dans la boucle
◦ Conservation
◦ Montrer que si C et I sont vrais, alors après la liste d'instructions, I est encore vrai.
◦ Terminaison
◦ On en déduit que (I et non C) est vrai à la sortie de la boucle (si la boucle termine).
22
Itérations
int i = 0;
while(i<10){
System.out.println(“Coucou”);
i +=1;
23
Itérations
int i = 0;
do{
i +=1;
}while(i<10);
for (i=0; i<10; i++)
24
Algorithme d’Euclide: pseudo code
PGCD(a,b)
n <- a; m <- b;
TantQue m != 0 Faire
r <- n mod m
n <- m
m <- r
FinTantQue
retourner n
25
PGCD(a, b)
n <- a; m <- b;
{ Invariant : pgcd(a,b)=pgcd(n,m) et n>=0 et m>=0 }
TantQue m != 0 Faire
r <- n mod m
n <- m
m <- r
{ pgcd(a,b)=pgcd(m,n) et m>=0 et n>0 }
FinTantQue
// pgcd(a,b)=pgcd(n,m) et n>=0 et m=0
// Donc n=pgcd(a,b)
26
Algorithme récursif
27
Fact(n)
i ← 1; fact ← 1
{ Invariant: fact = i ! et i ≤ n }
TantQue i < n Faire
i←i+1
fact ← fact * i
{ Invariant: fact = i ! et i ≤ n }
FinTantQue
(fact = i ! et i ≤ n ) et non(i<n)
retourner fact
28
Mémoire
Allocation dynamique de
la mémoire
(heap)
Données des fonctions
Instructions, fonctions, Pile

procédures
Les variables sont stockés
à ce niveau
Variables Statiques
Le reste de la mémoire
est occupé par le SE.
Code
29
Chargement d’un programme
Activation de
l’Enregistrement
} Heap
public static void

main(String[] args) {
int x=10;
System.out.println(“re
sultat”+x);
}
X=10
} La pile
}
Variables Statiques
code
Public void main ()
{
System.out.println(resultat)
}
30
Considérons une
entrée = 4➔ 4! =
public class Factorielle 1x2x3x4
{
public static double factorielle(int x) {
if (x < 0) return 0.0;
double fact = 1.0;
while (x > 1) {
fact = fact * x;
x = x - 1; 1
} 2 fac(1)
return fact; 3x fac(2)
} 4 xfac(3)
public static void main(String[] args) {

Variables Statiques
int entree = Integer.parseInt(args[0]);
double resultat = factorielle(entree);
System.out.println(resultat);
}
Factorielle(4)
}
31
Considérons entree =
4➔ 4! = 1x2x3x4
public class Factorielle
{
double fact = 1.0;
while (x > 1) {
fact = fact * x;
x = x - 1; 1
} 2 x1
return fact; 3x fac(2)
} 4 xfac(3)

Variables Statiques
}
Factorielle(4)
}
32
Considerons entree =
4➔ 4! = 1x2x3x4
{
double fact = 1.0;
while (x > 1) {
fact = fact * x;
x = x - 1;
} 2 x1
return fact; 3x 2
} 4 xfac(3)

Variables Statiques
}
Factorielle(4)
}
33
4➔ 4! = 1x2x3x4
{
double fact = 1.0;
while (x > 1) {
fact = fact * x;
x = x - 1;
}
return fact; 3x 2
} 4x6

Variables Statiques
}
Factorielle(4)
}
34
4➔ 4! = 1x2x3x4
{
double fact = 1.0;
while (x > 1) {
fact = fact * x;
x = x - 1;
}
return fact;
} Resultat = 24
Variables Statiques
}
Factorielle(4)
}
35
Fac(n)
Relation de récurence
◦ fac(n) = n * fac(n-1), n>0
◦ fac(0) = 1
Algorithme
◦ Si n = 0
◦ Alors retourner 1
◦ Sinon retourner n * fac(n-1)
◦ FinSi
36
Fac(n)
Complexité
◦ opération élémentaire
◦ nbre de fois où elle est effectuée
◦ fonction de n: M(n)
◦ relation de recurrence:
◦ M(n) = 1 + M(n-1) pour n>0 et M(0) = 0
◦ en développant, on a M(n) = M(n-i) – i pour tout i
◦ pour i=n, on obtient M(n) = M(O) + n = n
37
Tours de Hanoï
n disques de tailles décroissantes sur une tige
Problème: comment faire passer les n disques sur une autre tige, en
utilisant une tige intermédiaire afin qu'un disque ne soit jamais empilé
sur un plus petit?
Algorithme (récursif):
◦ faire passer n-1 disques sur la tige 2
◦ faire passer le plus grand disque sur la tige 3
◦ reste à faire passer les n-1 disques de t2 à t3
38
A B C
39
A B C
40
Tours de Hanoï - 4 disques
41
A B C
42
A B C
43
Tours de Hanoï
Algorithme:
◦ faire passer n-1 disques sur la tige 2
◦ faire passer le plus grand disque sur la tige 3
◦ reste à faire passer les n-1 disques de t2 à t3
Complexité
◦ on compte le nbre de déplacements
◦ il est fonction du nombre de disques
◦ M(n) = M(n-1) + 1 + M(n-1) pour n>1 et M(1)=1
◦ M(n) = 2*M(n-1)+1 = ... = 2n -1 (algo exponentiel)
44
Algorithmes de tri
Différents algorithmes
◦ tri par selection;
◦ tri par insertion;
◦ tri à bulles;
◦ tri fusion;
◦ tri rapide (quicksort);
◦ Tri shell;
◦ Tri de monceau.
45
Tri à bulles
Principe
◦ comparaison 2 à 2 des éléments adjacents
◦ et échange s'ils ne sont pas ordonnés
◦ comme les bulles, les plus grands élts remonte en fin de liste
46
Tri à bulles
Algorithme itératif
◦ Pour i de 0 à n-2 Faire
◦ Pour j de 0 à n-2-i Faire
◦ Si tab[ j+1 ] < tab[ j ]
◦ Alors échanger tab[ j+1 ] < tab[ j ]
◦ FinSi
◦ FinPour
◦ FinPour
47
10 2 8 6 7 3
48
10 8 6 7 3
49
2 3 6 7 8 10
50
Tri de Bubble: ALGO
2 5 7 8 12
i
j
Pseudo code:
For i=0 to A.taille-2

for j= 0 à A.taille -2-1
if A[j]>A[j+1]
tmp= A[j+1]
A[j+1] = A[j]
A[j] = tmp
51
Tri de Bubble
2 5 7 8 12
i
j Temps Quadratique de n ,
taille de donnees
Pseudo code:
For i=0 to A.taille-2

for j= 0 à A.taille -2-1
i=0 0<= j <n-2 (n-1) swap
if A[j]>A[j+1]
tmp= A[j+1] i=1 0<= j <n-3 (n-2) swap
A[j+1] = A[j]
A[j] = tmp
… … …
i=n-2 0<= j <0 1
52
Analyse algorithmique
Pourquoi analyser un algorithme?
❖ Connaitre le temps d’exécution
❖ Décider du prérequis matériel
❖ Qu’est ce qui possible ou impossible
53
400 pas 100 pas
300 pas 150 pas

300 pas
100 pas
400 pas
54
Comment calculer le temps d’un algo
Deux algo : 100 -10ms
Elements Algo1 (ms) Algo2(ms)
200 Progression 20 40 Progression

linéaire quadratique
1000 100 1000
10000 1000 100000
Progression de temps
55
3 cas de complexité
❑dans le pire des cas

❑dans le meilleur des cas
❑en moyenne
Exemple: recherche d'un élément dans une liste?
Exemple: recherche du plus grand élément d'une liste?
56
Modèle de calcul mémoire
Considérons:
❑Mémoire illimitée
❑Chaque opération (+,-, *, /,=) prend un certain nombre
de temps
❑Chaque accès mémoire consomme un temps
processeur ( déplacement de données)
❑Les données sont accessibles soit au niveau mémoire
ou disk, et supposons que les données sont en
mémoire
57
Considerons un vecteur (array) Tri à Bulles
12
8 12
8 12
7 5 12
7 12
5 2 2 comparaison swap
1 3
1 3
1 3
1 3
16
58
Tri à Bulle
8
7 7
8
5 52
8 28 12 comparaison swap
1 3
1 3
1 3
12
59
Tri de Bulles
comparaison swap
7
5 5
7
2 2
7 8 12 1 3
1 3
60
Tri de Bulles
comparaison swap
52 25 7 8 12 1 3
16+12+8+4 4
=4(4+3+2+1)
Pour n éléments on aura =4(n-1+n-2+….+3+2+1) =4xnx(n-1)/2
Pn2 +qn + r , p ,q , r
=2xnx(n-1) sont des constantes :
équation quadratique
61
Notation grand (O)
Limite supérieur
Suppose c2n2 > t(n) T(n)=pn2+qn+r

Observations:
Temps
c2n2
Ɐ n > n0
2 2
c3n2 C2n ≥ pn +qn+r
Suppose c1n2 < t(n)
c1n2
n0 n
62
Grand Oh
O(n2)= { f(n) : il existe une constante positive c et n0 tel
que 0 ≤ f(n) ≤ cn2 pour tout n ≥n0
Soit g(n)=n2 on peut écrire
O(g(n))= { f(n) : il existe une constante positive c et n0 tel

que 0 ≤ f(n) ≤ cg(n) pour tout n ≥n0 (pour donner sur la limite supérieur
de la fonction)
63
Notation de Grand O
5n2+6 ε o(n2)
suppose
Cn2 , et c = 6 , n0=3 => 6n2 > 5n2
5n2+6 ε o(n2)
64
Notation de Grand O
5n+6 ε o(n2)
suppose
Cn2 , et c = 11 , n0=1 => 11n2> 5n +6
Considérons le polynôme
N3+2n2+4n +8 ε o(n2) parce que :
On ne peut pas trouver une valeur
constante c tel que Cn2 ≥ n3+2n2+4n +8
65
amnm+am-1nm-1------------------------+a0 ꜫ O(nm)
O(n) est le meilleur temps d’un algo
Logn ≤ √𝑛 ≤ n ≤ nlogn ≤ n2 ≤ n3 ≤ 2n ≤ n!
66
Exemple
Int[] a = {1,3,7,8,9,2}
1 3 7 8 9 2
A[4] 4e index
Int[] b = {5,8,1………..25,20} 100 Elts

5 8 1 …………. 25 20
Accéder à un élément à travers un index ne dépend pas de
la taille d’entrée, le temps d’exécution est constant et est
noté O(1), A[98] 98e index
67
Exemple
1 12 7 8 9
T5 ~ 50ms
1 3 7 8 9 2 6 4 11 5
T10 ~ 100ms
68
Efficacité d'un algorithme
Temps d'exécution
◦ fonction de la taille des données en entrée

◦ choix du bon paramètre
◦ taille d'une liste, degré d'un polynôme
◦ taille d'une matrice?
◦ nombre de noeuds, profondeur, largeur d'un graphe?
◦ nombre de mots d'un fichier ou nombre de caractères?
◦ fonction du nombre de fois où une opération de base est répétée dans

l'algorithme
69
Efficacité d'un algorithme
Classes de complexité
1, Logn ≤ √𝑛 ≤ n ≤ nlogn ≤ n2 ≤ n3 ≤ 2n ≤ n!
Notations asymptotiques:
◦ O(g(n))
70
Résumé du cours
▪Définition des structures
▪Listes de structures des données
▪Les algorithmes
▪Analyse algorithmique
71
Notion du langage Java
72
Notions du langage Java J2SE
Java est un langage généraliste de programmation synthétisant les
principaux langages existants lors de sa création en 1995 par Sun
Microsystems. Il permet une programmation orientée-objet. modulaire .
Il reprend une syntaxe très proche de celle du langage C.
Outre son orientation objet, Java a l’avantage d’être modulaire (on peut
écrire des portions de code génériques, c-à-d utilisables par plusieurs
applications), rigoureux (la plupart des erreurs se produisent à la
compilation et non à l’exécution) et portable (un même programme
compilé peut s’exécuter sur différents environnements).
En contre-partie, les applications Java ont le défaut d’être plus lentes à
l’exécution que des applications programmées en C par exemple.
73
74
75
76
77
Java
Langage orienté objet
◦ Notions d’objets, d’attributs, de classes, méthodes, héritage, polymorphisme…
Beaucoup d’outils disponibles (packages)

◦ JDK (Java Development Kit)
Historique
◦ Sun Microsystems
◦ 1991: conception d'un langage indépendant du hardware
◦ 1994: browser de HotJava, applets
◦ 1996: Microsoft et Netscape commencent à soutenir
◦ 1998: l‘édition Java 2: plus stable, énorme librairie
78
Java
Compiler un programme en Byte Code
◦ Byte code: indépendant de la machine
◦ Interprété par la machine
javac programme.java
◦ Génère programme.class
java programme
◦ Lance le programme
79
Source: infosecinstitute.Com
80
Écrire un programme
public class Hello Nom de la classe
{
public static void main(String[] args) Une méthode
{
// afficher une salutation commentaire
System.out.println("Hello, World!"); Une instruction
}
}
Stocker ce programme dans le fichier Hello.java
81
Lancer un programme
Compilation
◦ javac Hello.java
◦ Ceci génère Hello.class
Lancer l’exécution
◦ java Hello
Résultat de l’exécution
Hello, World!
82
Éléments de base dans un
programme
mots réservés: public, class, static, void
identificateurs: args, Hello,main , String, System ,out println
◦ main String System out println: ont une fonction prédéfinie
littéral: "Hello World!"

ponctuation: { accolade } [ crochet ] ( parenthèse )
Commentaires
◦ // note importante pour comprendre cette partie du code
◦ /* … commentaires sur plusieurs lignes
◦ */
83
Classe
Un programme en Java est défini comme une classe
Dans une classe:
◦ attributs, méthodes
L'en-tête de la classe
public class NomDeClasse
◦ public = tout le monde peut utiliser cette classe
◦ class = unité de base des programmes OO
Une classe par fichier
La classe NomDeClasse doit être dans le fichier NomDeClasse.java
S’il ya plus d’une classe dans un fichier .java, javac génère des fichiers .class
séparés pour chaque classe
84
Classe
Le corps
{
…
}
Contient les attributs et les méthodes
◦ Attributs: pour stocker les informations de la classe
◦ Méthodes: pour définir ses comportement, ses traitements, …
Conventions et habitudes
◦ nom de classe: NomDeClasse
◦ indentation de { }
◦ indentation de ...
◦ Les indentations correctes ne seront pas toujours suivies dans ces notes pour des
raisons de contraintes d’espace par PowerPoint…
85
Méthode: en-tête
L'en-tête:
public static void main(String[] args)
◦ main: nom de méthode
◦ void: aucune sortie (ne retourne rien)
◦ String[] args: le paramètre (entrée)
◦ String[]: le type du paramètre
◦ args: le nom du paramètre
Conventions
◦ nomDeParametre
◦ nomDeMethode
◦ nomDAttributs
◦ nomDObjet
86
Méthode: corps
Le corps:
{
// afficher une salutation
System.out.println("Hello, World!");
}
contient une séquence d'instructions, délimitée par { }

◦ // afficher une salutation : commentaire
◦ System.out.println("Hello, World!"): appel de méthode
les instructions sont terminées par le caractère ;
87
Méthode: corps
En général:
nomDObjet.nomDeMethode(<liste des paramètres>)
◦ System.out: l'objet qui représente le terminal (l’écran)
◦ println: la méthode qui imprime son paramètre (+ une fin de ligne) sur un
stream (écran)
◦ System.out.println("Hello, World!");
◦ "Hello, World!": le paramètre de println
La méthode main
◦ “java Hello” exécute la méthode main dans la classe Hello
◦ main est la méthode exécutée automatiquement à l’invocation du programme
(avec le nom de la classe) qui la contient
88
Variable
Variable: contient une valeur
◦ Nom de variable
◦ Valeur contenue dans la variable
◦ Type de valeur contenue
◦ int: entier, long: entier avec plus de capacité
◦ Integer: classe entier, avec des méthodes
◦ float: nombre réel avec point flottant, double: double précision
◦ String: chaîne de caractères ("Hello, World!")
◦ char: un caractère en Unicode (‘a’, ‘$’, ‘é’, …)
◦ booleen: true/false
Définition générale
◦ Type nomDeVariable;
0
◦ Exemple: int age;
Type: int
Nom: age
89
Modifier la valeur
Affecter une valeur à une variable
E.g. age = 40;
Type: int 40
Nom: age
Erreur si: age = "quarante";

◦ Type de valeur incompatible avec la variable
90
Condition et test
Une condition correspond à vrai ou faux
E.g. (age < 50)
Tester une condition:
◦ if condition A; else B;
◦ si condition est satisfaite, alors on fait A;
◦ sinon, on fait B
◦ E.g. if (age < 65)
◦ System.out.println("jeune");
◦ else
◦ System.out.println("vieux");
91
Tests
Pour les valeurs primitives (int, double, …)
◦ x == y : x et y ont la même valeur?
◦ x > y, x >= y, x != y, …
◦ Attention: (== != =)
Pour les références à un objet

◦ x == y : x et y pointent vers le même objet?
◦ x.compareTo(y): retourne -1, 0 ou 1 selon l’ordre entre le contenu des objets
référés par x et y
92
Un exemple de test
public class Salutation
{
public static void main(String[] args)
{
int age;
args[0]: premier argument
age = Integer.parseInt(args[0]); après le nom
// afficher une salutation selon l’age
System.out.print(“Salut, le "); Integer.parseInt(args[0]):
if (age < 65) reconnaître et transmettre
System.out.println(“jeune!"); la valeur entière qu’il
else représente
System.out.println(“vieux!");
}
} print: sans retour à la ligne
Utilisation: println: avec retour à la ligne
◦ java Salutation 20 // ici, args[0] = "20"
◦ Salut le jeune!
◦ java Salutation 70
Salut le vieux!,
93
Boucle
Pour traiter beaucoup de données en série
Schéma d’exécution
Schémas
somme=0; Attention:
Boucle for ‘i’ n’est déclarée ici qu’à
int somme = 0; i=0; l’intérieur de la boucle for
for (int i = 0; i<10; i++) somme = somme + i; i<10?

Boucle while oui
somme=somme+i;
int somme = 0; non
i++;
int i = 0;
Attention:
while (i<10) { somme = somme + i;
un ; après le for( ), itère sur
i++; la condition, et ‘somme’ ne sera
incrémentée qu’une seule fois
}
i: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
somme: 0 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, sortie

Que font ces deux boucles?
94
Boucle
do A while (condition) Schéma d’exécution
Faire A au moins une fois somme=0;
Tester la condition pour savoir s’il faut refaire A
int somme = 0; i=15;
int i = 15;
while (i<10) { somme = somme + i; i<10?
i++; oui
} somme=somme+i;
non
somme = 0 i++;
int somme = 0;
int i = 15; Schéma d’exécution
do { somme = somme + i; somme=0;
i++;
} i=15;
while (i<10)
somme=somme+i;
◦ somme = 15 i++;
i<10? oui
non
95
Exemple
Calcul des intérêts
Étant donné le solde initial, le solde souhaité et le taux d'intérêt, combien
d'années seront nécessaires pour atteindre le solde souhaité
◦ au lieu d'utiliser une formule, on simule le calcul
Algorithme (pseudocode):
◦ ans = 0;
◦ WHILE solde n'atteint pas le solde souhaité
◦ incrémenter ans
◦ ajouter l'intérêt au solde
96
Programme
public void nombreAnnees (double balance, double targetBalance, double rate ) {
int years = 0;
while (balance < targetBalance) {
years++;
double interest = balance * rate;

years = years + 1;
balance += interest;
balance = balance + interest;
}
System.out.println(years + " years are needed");
Appel de la méthode:
nombreAnnees(1000, 1500, 0.05)
Résultat:
56 years are needed
97
Factorielle
{
Si une méthode (ou un
public static double factorielle(int x) { attribut, une variable) de la
if (x < 0) return 0.0; classe est utilisée par la
double fact = 1.0;
méthode main (static), il
faut qu’il soit aussi static.
while (x > 1) {
fact = fact * x;
x = x - 1;
return fact;
} 98
Tableau : array
Pour stocker une série de données de même nature
Déclaration
◦ int [] nombre; // une série de valeurs int dans le tableau nommé nombre
◦ String [][] etiquette; // un tableau à deux dimensions de valeurs String
Création
◦ nombre = new int[10]; // crée les cases nombre[0] à nombre[9]
◦ etiquette = new String[3][5]; // crée etiquette[0][0] à etiquette[2][4]
◦ int[] primes = {1, 2, 3, 5, 7, 7+4}; // déclare, crée de la bonne taille et initialise
Utilisation
◦ nombre[0] = 4;
◦ for (int i=1; i<nombre.length; i++) nombre[i]=nombre[i]+1;
◦ etiquette[2][3] = "un texte";
◦ String texte = etiquette[2][3]; Attention:
Array a.length
Array list a.size()
String a.length()
99
String
Structure à deux parties:
◦ En-tête: nom, longueur, … u n t e x t e
◦ Corps: les caractères
etiquette[2][3]
a u t r e t e x t e
texte
◦ String texte = etiquette[2][3];
◦ Le contenu du corps ne peut pas être
changé, une fois qu’il est créé (String
est immutable)
◦ Par contre, on peut pointer/référer
etiquette[2][3] à un autre corps:
etiquette[2][3] = "autre texte";
etiquette[2][3]
u n t e x t e
texte
100
Classe et Objet
Classe: moule pour fabriquer des objets
Objet: élément concret produit par le moule
Définition de classe:
class NomClasse { class Personne {
Attributs; String nom;
Méthodes; int AnneeNaissance;
} public int age() {…}
}
Une classe regroupe un ensemble d’objets (instances)
101
Objet
Structure à deux parties:
◦ Référence
◦ Corps
Les étapes
◦ Déclaration de la classe (e.g. Personne)
◦ À l’endroit où on utilise:
◦ Déclarer une référence du type de la classe
◦ Créer une instance d’objet (new)
◦ Manipuler l’objet
102
Exemple
public class Personne {
public String nom;
public int anneeNaissance;
public int age() {return 2018 - anneeNaissance; }
class Utilisation { Déclaration de référence

Création d’une instance
Personne pers;
pers = new Personne(); Manipulation de l’instance

pers.nom = "Pierre";
référée par la référence
pers.anneeNaissance = 1980;
pers
System.out.println(pers.age());
} nom: "Pierre"
}
anneeNaissance: 1980
Personne:
age()
103
Manipulation des objets
Forme générale
◦ référence.attribut: réfère à un attribut de l’objet
◦ référence.méthode( ): réfère à une méthode de l’objet
static: associé à une classe

◦ Attribut (variable) statique: si on le change, ça change la valeur pour tous les
objets de la classe
◦ Méthode statique: on la réfère à partir de la classe
◦ Classe.méthode
◦ E.g. Math.sqrt(2.6): Appel à la méthode sqrt de la classe Math
◦ Constante: Math.PI
◦ Dans une classe: static final float PI = 3.14159265358979;
◦ Une constante n’est pas modifiable
104
Classes et Héritage
Héritage
◦ Les enfants héritent les propriétés du parent
◦ Classe enfant (sous-classe) possède systématiquement les attributs et les méthodes de la classe parent (super-classe)
◦ Héritage simple (une seule super-classe au plus)
E.g.
class Personne {
String nom;
int anneeNaissance;
public int age() { return 2008 - anneeNaissance; }

Personne
}
class Etudiant extends Personne {

Etudiant Professeur
String [] cours;
String niveau;
String ecole;
Gradue
Ce qui est disponible dans Etudiant:

◦ nom, anneeNaissance, age(),
◦ cours, niveau, ecole, …
105
Principe
Définir les propriétés communes dans la classe supérieure
Définir les propriétés spécifiques dans la sous-classe
Regrouper les objets le plus possible
Les objets d’une sous-classe sont aussi des objets de la super-classe
La classe dont tous les objets appartiennent: Object
Tester l’appartenance d’un objet dans une classe: instanceof (e.g. qui
instanceof Etudiant)
106
Casting
La classe de la référence détermine ce qui est disponible (a priori)
E.g.
class A {
public void meth() { System.out.println("Salut"); }
class B extends A {
int var;
A a = new A();
B b = new B();
a.meth(); // OK
b.meth(); // OK, héritée
b.var = 1; // OK
a.var = 2; // erreur
a = b;
a.var = 2; // erreur: var n’est a priori pas disponible pour une classe A
((B) a).var = 2; // OK, casting
Casting: transforme une référence d’une super-classe à celle d’une sous-classe
Condition: l’objet référé est bien de la sous-classe
108
Surcharge de méthode
class A {
public void meth() {System.out.println("Salut"); }
}
class B extends A {
public void meth(String nom) {
System.out.println("Salut" +nom);
}
}
Dans la sous-classe: une version additionnelle
◦ Signature de méthode: nom+type de paramètres
◦ Surcharge: créer une méthode ayant une autre signature
109
Overriding: écrasement
Par défaut, une méthode est héritée par une sous-classe
Mais on peut redéfinir la méthode dans la sous-classe (avec la même signature)
Les objets de la sous-classe ne possèdent que la nouvelle version de la méthode
E.g.
class A {
public void meth() {System.out.println("Salut");}
class B extends A {
public void meth() {System.out.println("Hello");}
A a = new A();
B b = new B();
a.meth(); // Salut
b.meth(); // Hello
a = b; // a réfère à un objet de classe B
a.meth(); // Hello. Même si la référence est de classe A, l’objet est de classe B
110
Classe abstraite
Certains éléments peuvent être manquants dans une classe, ou la classe
peut être trop abstraite pour correspondre à un objet concret
Classe abstraite
◦ Une classe non complétée ou une classe conceptuellement trop abstraite
◦ Classe Shape
◦ on ne connaît pas la forme exacte, donc impossible de créer un objet
◦ cependant, on peut savoir que chaque Shape peut être dessinée
abstract class Shape {

◦ abstract void draw();
111
Interface
Interface
◦ Un ensemble de méthodes (comportements) exigées
◦ Une classe peut se déclarer conforme à (implanter) une interface: dans ce cas, elle
doit implanter toutes les méthodes exigées
E.g.
public abstract interface Inter {
public abstract int carre(int a);
public abstract void imprimer();
}
class X implements Inter {
public int carre(int a) { return a*a; }
public void imprimer() {System.out.println("des informations"); }
}
112
Exemple
public interface Stack {
public void push(Integer data);
public Integer pop();
public boolean isEmpty();
public Integer peek();
public class ArrayStack implements Stack{
private int [] array;
private int top = -1;// initialize the stack is empty
private int size;
public void push(Integer data) {// put element on top of stack
if(top == array.length)
resize();
top = top +1;// top is the index we want to insert
array[top]= data;
size++;
113
Utilité de l’interface
Permet de savoir qu’une classe contient les implantations de certaines
méthodes
On peut utiliser ces méthodes sans connaître les détails de leur
implantation
Souvent utilisée pour des types abstraits de données (e.g. pile, queue, …)
114
Package
On organise les classes et les outils selon leurs fonctionnalités et les
objets qu’elles manipulent
Les classes qui traitent les mêmes objets: package
Exemple:
◦ Les classes pour traiter l’interface graphique sont dans le package awt
Organisation des packages java javax

◦ Hiérarchie
◦ java.awt awt swing
◦ java.awt.event
◦ javax.swing event
classes
◦ …
classes
115
Exception
Quand un cas non prévu survient, il est possible de le capter et le traiter
par le mécanisme d’Exception
◦ Si on capte et traite une exception, le programme peut continuer à se dérouler
◦ Sinon, le programme sort de l’exécution avec un message d’erreur
◦ Exemple d’exception: division par 0, ouvrir un fichier qui n’existe pas, …
Mécanisme de traitement d’exception

◦ Définir des classes d’exception
◦ Exception
◦ IOException
◦ EOFException, …
◦ Utiliser try-catch pour capter et traiter des exceptions
116
Attraper (catch) une exception
Attraper une exception pour la traiter
try { Bloc où une exception

statements
: peut se générer
:
} catch (ExceptionClass1 object) {
statements
:
:
} catch (ExceptionClass2 object) {
statements Blocs pour attraper
: les exceptions
:
}…
117
Exemple
public static void ouvrir_fichier(String nom) {
ouverture
try { d’un fichier
input = new BufferedReader(new FileReader(nom));

}
catch (IOException e) {
System.err.println("Impossible d'ouvrir le fichier d'entree.\n" +
e.toString());
System.exit(1);
}
}
try: on tente d’effectuer des opérations
catch: si une exception de tel type survient au cours, on la traite de cette façon
118
Résumé sur Java
▪Programmation classique: traiter des données des types primitifs
▪Programmation OO: regrouper les données (attributs) et leurs
traitements (méthodes)
▪Outils disponibles
◦ Classes regroupées dans des packages
◦ Interface graphique
◦ Communication à travers l’Internet
◦ Package pour interagir avec un SGBD (Système de gestion de base de données)
◦ …
119
À retenir
Comment un programme est traduit en code exécutable? (compilation ou
interprétation)
Environnement de programmation
Quels sont les opérations qu’on peut mettre dans un programme?
Concept de base: variable, type, classe, objet, héritage (OO), …
Utilisation des packages existants
Principe de gestion d’interface graphique
120
Structures de données
121
Liste simplement liée
Structure de données composée d’une séquence d’élément de liste
Chaque élément x de la liste est composé :
◦ D’un contenu utile x.data de type arbitraire (par exemple une clé)
◦ D’un pointeur x.next vers un élément suivant dans la séquence
Soit L une liste liée

◦ L.head(sommet) pointe vers le premier élément de la liste
◦ le dernier élément de la liste pointe vers null
122
Liste chainée
nextNode nextNode nextNode nextNode Null
Sommet Nœuds( node)

(head)
Référence de la liste
123
Noeud-( node)
donnée
nodeSuivant null
Cette donnée , peut être n’importe

quel type à stocker, int, double or réf
d’un objet
124
Liste chainée
nextNode nextNode nextNode nextNode Null
Sommet Nœuds( node)

(head)
Référence de la liste, en utilisant cette

référence on pourra, ajouter, supprimer
sur liste
125
Nœud: Code Java
public class Noeud {

// déclaration des variables donnee et noeud suivant
private int donnee;
private Noeud noeudSuivant;
// définir le constructeur du noeud

public Noeud (int donnee){
this.donnee= donnee;
}
// pour acceder , nous ecrivons des "getter"
126
Nœud: Code Java
// pour acceder , nous ecrivons des "getter"
public int getDonnee(){

return this.donnee;
}
public Noeud getNoeudSuivant(){
return this.noeudSuivant;
}
public void setDonnee(int donnee){
this.donnee=donnee;
}
public void setNoeudSuivant(Noeud noeudSuivant){
this.noeudSuivant= noeudSuivant;
}
}
127
Implémentation de liste chainée
public class ListeChainee {

// une liste chainée contient un
nœud
private Noeud tete;//head
}
128
Insérer un nouveau Nœud
1 4 7 9
Null
Sommet 5 Pour ajouter en tête de

(head) Null liste , on a besoin de
connecter le nœud en
début de liste et le
sommet (head) pointe
sur le nœud suivant.
129
Insérer un nouveau Noeud
x 4 7 9
Null
Tête de liste 5 Le reste de la liste

(head) Null deviendra est
inaccessible
130
1 4 7 9
Null
Sommet
√
5
(head) Null
131
5 1 4 7 9
Null
Tête de liste
(head)
AjouterEnDebut(Integer donnee) : O(1) c’est –à dire le
temps est constant, la liste n’est pas traversée.
132
Implémentation : insertion en
tête de liste
public void insererEnDebut(int donnee){
// creer le noeud
Noeud nouveauNoeud = new Noeud(donnee);
// connecter sur le noeud suivant

nouveauNoeud.setNoeudSuivant(this.tete);
this.tete = nouveauNoeud;
133
Taille ou longueur d’une liste
null
Taille = 0
Tête de liste (head) =>
pas de nœud dans la liste
Taille = 0
1 4 7 9 5
Null
134
null
Taille = 0
Taille = 1
1 4 7 9 5
Null
135
null
Taille = 0
Taille = 2
1 4 7 9 5
Null
136
null
Taille = 0
Taille = 3
1 4 7 9 5
Null
137
null
Taille = 0
Taille = 4
1 4 7 9 5
Null
138
null
Taille = 0
Taille = 5
1 4 7 9 5
Null
139
Implémentation
public int taille(){

int taille = 0; // initialisation de la taille
Noeud courant = this.tete;
while (courant !=null){
taille++;
courant = courant.getNoeudSuivant();
}
return taille;
}
140
Supprimer un noeud
1 4 7 9 5
Null
Tete de lsite
Supprimer en tête de liste

consiste à pointer la tête sur
le nœud suivant.
141
Supprimer un noeud
1 4 7 9 5
Null
Sommet
(head)
Le premier nœud ne pointe que sur le

suivant non pas sur le précédent.
142
Supprimer un noeud
4 7 9 5
Null
Sommet(hea
d)
Complexité = O(1) temps constant
143
Implémentation
public void supprimeDebutListe(){

this.tete = this.tete.getNoeudSuivant();
144
Recherche d’un élément
1 4 5 7 9 12 17 Null
Pour rechercher un élément, on

doit parcourir toute la liste jusqu’à
retrouver l’élément recherché. Rechercher(donnee)
L’élément peut ne pas exister.
Rechercher(12)
145
1 4 5 7 9 12 17 Null
Rechercher(donnee)
Rechercher(12)
Recherche un élément est une

opération linéaire, temps
constant O(n)
146
1 4 5 7 9 12 17 Null
Pire de cas,
O(n)
Rechercher(donnee)
Rechercher(15)
147
Implémentation
public Noeud recherche(int donnee){
Noeud current = this.tete;
while (current != null){
if (current.getDonnee() == donnee){
return current;
}
current = current.getNoeudSuivant();
}
return null;
}
148
Liste Chainée (2 extrémités)
5 1 4 7 9 6 Null
Fin de
Sommet =head
liste
2e type de liste chainée:

Début et une fin (head –tail).
On peut ajouter en début et fin

de liste les éléments. C’est une
technique peut utiliser.
149
Implémentation
public void insererFinListe(int donnee){
Noeud nouveauNoeud = new Noeud(donnee);
// tester s'il ya aucun element
if (this.tete==null){
this.tete = nouveauNoeud;// assigner tête au
nouveau noeud
}
150
Insertion dans une liste chainée
trié
1er cas la liste est vide
null

pointe vers un null
17
Null
151
trié
null

pointe vers le nouveau
noeud
17
Null
152
trié
17 Null
Tête de liste (head)
153
trié
2e cas la liste est triée
19 21 27 Null

pointe vers un null
17
Null
154
trié
19 21 27 Null

pointe vers un null
17
Null
155
trié
19 21 27 Null

pointe vers un null On compare le nouveau nœud et
la tête, si le nouveau élément est
plus petit alors la tête pointe sur
17 le nœud.
156
trié
17 19 21 27 Null
Tête de liste (head)
Alors la tête pointe sur le nœud

élément.
157
Liste chainée triée
5 7 10 15 16 19 Null
Tête de
liste On doit parcourir la liste pour
trouver à quel emplacement il
peut s’insérer en comparant
chaque élément.
17
Null
158
5 7 10 15 16 19 Null
Tête de
liste On doit parcourir la liste pour
trouver à quel emplacement il
peut s’insérer en comparant
chaque élément.
17
Null
159
5 7 10 15 16 19 Null
Tête de Le nœud en cours de

liste lecture est 19, comme
dans une liste
simplement chainée
un nœud ne connais
que le successeur et
17 Null jamais le prédecesseur
Ce n’est pas la bonne
manière d’insérer
dans une liste chainée
triée.
160
5 7 10 15 16 19 Null
Tête de
liste Dans une liste chainée chaque
nœud connait son successeur
17
Null
161
5 7 10 15 16 19 Null
Tête de
liste
17
Null
162
5 7 10 15 16 19 Null
Tête de
liste
17
Null
163
5 7 10 15 16 19 Null
Tête de
liste
Il pointe sur le nœud 16,
qui connait son
successeur.
17
Null
164
5 7 10 15 16 19 Null
Tête de Le nœud en cours de

liste lecture est 16 <17 ,
comme dans une liste
simplement chainée
un nœud connait le
successeur, 17 va
17 Null pointer sur 19
165
5 7 10 15 16 19 Null
Tête de
liste
17
166
5 7 10 15 16 17 19 Null
Tête de
liste
insert (Integer data) :
Complexité en temps : O(n) parce dans le pire

de cas on traverse toute la liste
167
Liste doublement liée 1/5
Structure de données composée d’une séquence d’élément de liste
Chaque élément x de la liste est composé :
◦ D’un contenu utile x.data de type arbitraire (par exemple une clé)
◦ D’un pointeur x.prec vers l’élément précédent dans la séquence
Soit L une liste liée

L.tail pointe vers le dernier élément de la liste
Le premier élément possède une pointeur x.prec vide
168
précédant:
NULL precNoeud
donnée
Suivant: suivNoeud NULL
169
Null 5 4 7 9 3 Null
Tête
8 Insérer un nouvel élément
Null 7 10 15 16
8 5 Null
Tête
170
Null 5 4 7 9 3 Null
Tête
Null 7 10 15 16
8 5 Null
Tête
171
Null 5 4 7 9 3 Null
Tête
Null 7 10 15 16
8 5 Null
Tête
172
Null 5 4 7 9 3 Null
Tête
précédent
Null 7 10 15 16
8 5 Null
Tête
173
5 4 7 9 3 Null
Tête
précédent
Null 7 10 15 16
8 5 Null
Tête
174
5 4 7 9 3 Null
Tête
précédent
Null 7 10 15 16
8 5 Null
Tête
175
Liste doublement chainée 2/4
Les avantages des listes Doublement chainées (DC) sur les simplement chainées
1) une liste DC peut être parcourus dans les deux directions suivant et précedant
2) l’operation de suppression est plus efficace si un pointeur sur un noeud devrait être supprimer.
Dans une liste simplement chainée, pour supprimer un noeud , un pointeur sur le précédent noeud est
necessaire. Pour atteindre le noeud précédant quelque fois la liste est parcouru.
Dans le cas des listes doublement chainées, nous pouvons atteindre le précédant en utilisant un pointeur.
Insertion
Un noeud peut être ajouter de quatre manière
1) en debut de liste.
2) Après un noeud donné .
3) Enfin de la liste
4) Avant un noeud donné.
176
Les inconvénients sur les listes doublement
chainées. 3/4
1) chaque nœud de la liste doublement chainée requiert un extra espace

mémoire pour le précèdent pointeur .
2) Toutes les opérations requièrent un pointeur supplémentaire pour

gérer le pointeur précédant.
Par exemple, en insérant, nous devons modifier les pointeurs
précédant ensemble avec le pointeur suivant.
177
Implémentation d’une à l’aide
d’une liste liée 4/4.
S est une liste simplement liée (S.head pointe vers le premier élément de
la liste)
Complexité en temps O(1), complexité en espace O(n) pour n opérations
178
Operations sur les listes
doublement chainées
Ensemble dynamique d’objets ordonnés accessibles relativement les uns
aux autres, sur base de leur position.
Interface
◦ Les fonctions d’une liste double (insertion et retrait en début et fin de liste)
◦ Insert-before(L,p,x): insére x p dans la liste
◦ Insert-after (L, p,x): insère x après dans la liste
◦ Remove(L, p): remplace par l’objet x l’objet situé à la position p
◦ First(L), Last(L): renvoie la première, resp. dernière position dans la liste
◦ Prev(L, p), Next(L,p): renvoie la position précédant (resp. suivant) p dans la
liste
Implémentation similaire à la file double, à l’aide d’une liste doublement

liée avec sentinelles)
179
Pile- stack
✓ Piles:Stacks
✓ Implémentations (array)
180
Pile- stack
Ensemble dynamique d’objets accessible selon une discipline LIFO(Last-In First-
Out).
Interface
◦ Stack-empty(S) renvoie vrai si et seulement si la pile est vide
◦ Push( S, x) pousse la valeur x sur la pile S
◦ Pop(S) extrait et renvoie la valeur sur le sommet de la pile S
Applications
◦ Option ‘undo’ dans le traitement de texte
◦ Langage PostScript
◦ Appel de fonctions dans un compilateur
Implémentation
◦ Avec un tableau (taille fixe a priori)
◦ Au moyen d’une liste liée (allouée de manière dynamique)
181
Piles -stacks
5 12 7 2
Push
Insérer(push) un élément dans une pile au début de la
pile
182
Pile -stacks
Pop
Retirer (pop) un élément dans une pile
12
La pile est vide
5
183
Pile -stacks
Peek
lis (peek) un élément de la pile se situant en tête de la
pile sans le retirer et renvoie sa valeur.
A retenir:
7
LIFO : Last In First Out 3 opérations possibles
sur les Piles:
12
PUSH
POP
5 PEEK
184
Type de données abstraites
Mémoire
- Pile Adresse Donnée
- File
0x000001 2
0x000002 7
0x000003 8
0x000004 9
2 7 8 9 12 0x00005 12
Tableau = array
Listes liées et tableau sont des structures de
données réelles et linéaires. Elles sont
représentés en mémoire et contiennent des
données 185
Pile -stacks
PILES
Files: Queues
7 0
6 0
5 0
4 0
0 0 0 0 0 0 0
3 0
0 1 2 3 4 5 6
2 0
1 0
Structures de données conceptuelles,
0 toujours implémentées avec les tableaux ou
0
les listes chainées;
186
Pile - implémentation par tableau
Déclarer le
vecteur
tailleMax tailleMax = 7
Int[] PileVecteur = new int [tailleMax]
187
tailleMax tailleMax = 7
Int[] PileVecteur = new int [tailleMax]
6 0 top= -1
5 0
4 0
3 0
2 0
1 0
0 0
top= -1
Les éléments sont initialisés à zéro

188
tailleMax
6 0 Push (5)
5 0
4 0
3 0
2 0
1 0
top= 0 (top incrementé par 1)
0 05
189
tailleMax
6 0 Push (12)
5 0
4 0
3 0
2 0
0 top= 1 (top incrementé par 1)

1 12
0 5
190
tailleMax
6 0 Push (7)
5 0
4 0
3 0
top= 2 (top incrementé par 1)
2 07
1 12
0 5
191
tailleMax
6 0 Push (2)
5 0
4 0
3 top= 3 (top incrementé par 1)

2
0
2 7
1 12
0 5
192
tailleMax
6 0 pop ()
5 0 Retire la valeur de l’élément qui pointe
le top
4 0
top= 3
3 2
2 7
1 12
0 5
194
tailleMax
6 0 pop ()
5 0 Retire la valeur 2 de l’élément qui pointe
le top
4 0
top= 2
3 20
2 7
1 12
0 5
195
tailleMax
6 0 pop ()
5 0 Retire la valeur 7 de l’élément que
pointe le top
4 0
3 20
top= 1
2 07
1 12
0 5
196
tailleMax
6 0
5 0 La pile est vide ( empty)

4 0
3 20
2 0
top=-1
1 0
0 0
197
Pile- stack: implémentation par
tableau
S est un tableau qui contient les éléments de la pile
top est la position courante de l’élément au sommet de S
Complexité en temps et en espace: O(1)
(inconvénient : l’espace occupé ne dépend pas du nombre d’objets)
198
Pile - Complexité en temps
La complexité en temps:
tailleMax PUSH : O(1)
POP :O(1)
PEEK :O(1)
6 0 Temps constant d’opérations
5 0
4 0
3 0
2 0
1 0
0 0
top=-1
199
File - Queue
✓ Files:Queues
✓ Implémentations (array)
✓ File à Double Extrémités (DE-
queues)
200
File - Queue
7
Tête: Head Tail
La File est aussi une

structure de donnée
abstraite comme la Pile Enfiler
Insère un élément dans la file à partir de tail vers la tête
(head) 12
21
4
201
File - Queue
7 12 21 4
Tête: Head Tail
202
File - Queue
12 21 4
Tête: Head Tail
defiler
Retire un élément dans la file à partir de la tête (head)
203
File - Queue
Sortie élts 21 4 Entrée élément sortie
Tête: Head Tail
Retire un élément dans la file à partir de la tête (head)
204
File - Queue
Sortie élts 21 4 Entrée élément sortie
Tête: Head Tail
FIFO: First In First Out
205
File - Queue
21 4
Tête: Head Tail
PEEK
Renvoie la valeur 21 sans retirer l’élément
A retenir :
3 types d’opérations On peut vérifier la
possibles sur une File taille, ou si la File est
ENQUEUE:ENFILER remplie.
DEQUEUE: DEFILER
PEEK
206
File - Queue
21 4
Tête: Head Tail
PEEK
Renvoie la valeur 21 sans retirer l’élément
On peut vérifier la
taille, ou si la File est
remplie
207
File – implémentation par tableau
0 1 2 3 4 5 6
Iniatilsés à
zéro 0 0 0 0 0 0 0
Tête: Head
Tail
tailleMax = 7
Int[] fileArray = new int[tailleMax]
int tete = -1 // parce que il n’ y est pas dans la file
int tail = -1
208
0 1 2 3 4 5 6
70 0 0 0 0 0 0
Incrémenter par 1 et
Tête: Head
Tail
devient la tête et la fin de

la file
Enfiler (7) // enqueue
209
File – implément° par tableau
0 1 2 3 4 5 6
7 12
0 0 0 0 0 0
Tête: Head
Tail
Enfiler (12)
210
0 1 2 3 4 5 6
7 12
0 17 73 19 12 30
Tête: Head
Tail
Enfiler ()
211
0 1 2 3 4 5 6
7 12
0 17 73 19 12 3
Tête: Head
Renvoie (l’élément
Tail
à la tête).
L’élément est alors logiquement sortie

de la file.
defiler (7)
212
0 1 2 3 4 5 6
7 12
0 17 73 19 12 3
Tête: Head
Tail
defiler (12)
213
0 1 2 3 4 5 6
7 12
0 17 73 19 12 3
Tête: Head
Tail
Renvoie 17 au niveau de la
tête
PEEK(17)
214
0 1 2 3 4 5 6
7 12
0 17 73 19 12 3
Tête: Head
Tail
Comment enfiler
l’élément 27 et
incrémenté le tail
Comme les éléments Enfiler (27)
sont defilés, cet espace
peut être réutiliser Pour programmer l’enfilement on fait:
Math.abs(tail.index - tete.index) < taille du vecteur // alors il y a de

l’espace dans la file
Math.abs(6-2) =4 <7
215
0 1 2 3 4 5 6
27
7 12
0 17 73 19 12 3
Tête: Head
Tail
Où placer le tail?
La file qui ramène le
tail à l’index 0 après
Enfiler (27)
avoir atteint l’index Tant que tail a atteint l’index
maximal s’appelle: maximal et que la tete(head)
n’est pas à l’index zéro, alors
on peut ramener le tail à
File circulaire l’index 0
Parce que le tail traverse la
file et revient à sa position
de départ
216
Files d'attente ouvertes aux deux
extrémités(double ended queue)
Tête: Head
Tail
Différent de la file normale,
On peut ajouter ou retirer à
Dans les files d'attente ouvertes aux partir de la tête ou de la
deux extrémités les conflits d'accès sont queue,
limités, ce qui permet d'aboutir à un
équilibrage dynamique des charges On peut les appelés des files d'attente
entre les chaînes d'exécution. de détournement à double extrémités, à
conflit réduit, permettent d'équilibrer la
charge dynamique entre les unités
d'exécution.
217
extrémités
7 3
Tête: Head
Tail
Insérer / Enfiler gauche
Insérer /Enfiler droite
218
extrémités
19 7 3 17
Tête: Head
Tail
Enfile gauche
Enfile droite
219
extrémités
19 7 3 17
Tête: Head
Tail
defile gauche
defile droite
220
Nota Bene
Array triée Liste liée
Recherche: Rapide O(logn) Recherche: Lente O(n)
Insertion: Lente O(n) Insertion: Rapide O(1)
Suppression: lente O(logn) Suppression: Rapide O(1)
221
Quiz-liste1
Dans une liste simplement chainée, le dernier noeud pointe sur le NULL?
• Vrai
• Faux
222
Quiz-liste2
La taille d’une liste liée de n éléments est de :
• n
• n-1
• n+1
• n-2
223
Quiz-liste3
Dans le pire des cas, quelle est la complexité en temps pour l’insertion d’un élément dans
une liste liée triée? :
• O(n)
• O(1)
• O(log2n)
• O(n2)
224
Quiz1
Dans une opération de Pile, Peek lis la valeur du dernier élément et le supprime ?
• Vrai
• Faux
225
Quiz2
Quelle structure de données n’est fait pas partie des structures abstraites? choisir la
meilleure réponse.
• Liste doublement chainés à deux extrémités

• File
• Pile
• Liste simplement chainée
226
Quiz3
Les opérations PUSH, POP, PEEK ,de la structure de données PILE ont une complexité en
temps de:
• O(n)
• O(1)
• O(log2n)
• O(n2)
227
Quiz4
La Pile est une structure de TYPE?
• LIFO
• FIFO
228
Quiz5
La File est une structure de TYPE?
• LIFO
• FIFO
229
Quiz6
Supposons une exécution de PUSH, qui insère respectivement, 10,20,30,40 dans une PILE.
Après une exécution de POP trois fois, quel élément trouveras-t-on dans la PILE?
• 10
• 20
• 30
• 40
230
Quiz7
Supposons un enfilement, qui insère respectivement, 10,20,30,40 dans une FILE. Après
trois défilement , quel élément trouveras-t-on dans la FILE?
• 10
• 20
• 30
• 40
231
File à priorité
Ensemble dynamique d’objets classés par ordre de priorité
◦ Permet d’extrait un objet possédant la plus grande priorité
◦ En pratique, on représente les priorités par les clés
◦ Suppose un ordre total sur les clés
Interface
◦ INSERT(S,x): insère l’élément x dans S.
◦ DELETE-EXTRACT-MIN(S): supprime et renvoie l’élément de S avec la plus petite clé.
Remarques:
◦ Extraire l’élément de clé maximale ou minimale sont des problèmes équivalents
◦ La file FIFO est une file à priorité où la clé correspond à l’ordre d’arrivé des
l’éléments.
Application : gestion des jobs sur un ordinateur partagé
232
Implémentation par tableau
extensible
➢Les éléments sont stockés dans un tableau extensible V.A de taille initial
V.c;
➢En cas de dépassement, la capacité du tableau est doublée;
➢V,n retient le nombre de composantes;
➢Insertion et suppression (langage JAVA).
233
Implémentation par tableau
extensible
Insertion et suppression (langage JAVA)
public Integer deleteMinKey() {
public void insert(int key) {
if (isEmpty())
if(isFull())
return null;
resize();
else if(header == tail){
if(isEmpty()){
int temp = array[header];
header = 0;
header = -1;
tail = 0;
tail = -1;
size =size +1;
size = 0;
array[0] = key;
return temp;
}
}
else tail =(tail + 1)% array.length;
else {
array[tail] = key;
if(key < array[header]){
header =(header + 1)% array.length;
size++;
array[header]= key;
int min = findMinKeyIndex();
array[tail] = temp;
if (array[min] < array[header]){
}
int tempVal = array[header];
size = size +1;
array[header]= array[min];
}
array[min] = tempVal;
}return temp;
}
}
234
Implémentations
Implémentation à l’aide d’un tableau statique
◦ Q est tableau statique de taille fixée Q.length.
◦ Les éléments de Q sont triés par ordre croissant de clés. Q.top pointe vers le
dernier élément.
◦ Complexité en temps : extraction en O(1) et insertion en O(n) où n est la taille
de la file
Implémentation à l’aide d’une liste liée

◦ Q est une liste liée où les éléments sont triés par ordre décroissant de clés
◦ Complexité en temps: extration en O(1) et insertion en O(n) où n est la taille
de la file
◦ Complexité en espace : O(n)
235
Implémentation à l’aide d’une
liste liée
La file est implémentée à l’aide d’une liste
public void insert(int key) {
Node n = new Node(key); public Integer deleteMinKey() {
if (size == 0){ if (size != 0){
header.next = n; int temp = header.next.data;
lastNode = n; header.next = header.next.next;
size++; size--;
} findMinKey();
else { return temp;
lastNode.next = n; }
lastNode = n ; return null;
if (lastNode.data < }
header.next.data){// interchanger les
valeurs
int temp = header.next.data;
header.next.data= lastNode.data;
lastNode.data = temp;
}size++;
}
}
236
Tableau
Ensemble dynamique d’objets occupant des rangs entiers successifs
permettant la consultation, le remplacement, l’insertion et la suppression
d’éléments à des rangs arbitraires
Interface
◦ ELEMT-AT-RANk(V, r) retourne l’ élément situé au rang r dans V.
◦ REPLACE-AT-RANK(V,r,x) remplace l’élément situé au rang r par x et retourne
cet objetL
◦ INSERT-AT-RANK(V, r, x) insert l’élément situé au rang r et le retire de r, en
diminuant le rang des objets suivants.
◦ REMOVE-AT-RANK(V, r) extrait l’élément situé au rang r et le retire de r , en
diminuant le rang des objets suivants
◦ Vector-Size(V) renvoie la taille du vecteur
Applications : tableau dynamique, gestion des élément d’un menu
237
Arbres
➢ Arbres binaires
➢ Type de données abstrait pour un arbre
➢Arbre binaire de recherche
238
Arbres
Nœuds :
node
Arêtes:edges
239
Arbres
Racine: root
Dans une structure de
A
données arbre, il ne peut y
avoir qu’une seule racine.
Pour chercher un D
élément dans un
arbre, on doit avoir B
au moins un chemin à
partir de la racine. C
Branches:edges
G
F Cette architecture n’est
pas autorisée dans la
structure de données
arbre.
240
Arbres
A
Tout autre nœud

que la racine aura
D
exactement une
branche connecté à B
un nœud et pas
plus.
C
« père » de F
Par exemple: G
F
241
Arbres
A
C
« père » de F
G
F
Les fils de C
242
Arbres
A
C Nœud feuille
G
F
Nœud feuille
Nœud feuille
Nœud feuille
243
Arbres
A
C
Sous-arbre:
subtree
E
G
F
244
Arbres
Niveau 0
La position ou niveau du
nœud c’est sa position par
rapport à la racine :
Niveau 1
Niveau 2
245
Arbres Binaires
On parle de l’arbre binaire, Au plus 2 fils.
plus spécifiquement de
l’arbre binaire de
recherche. C’est une
structure de données qui
permet la recherche très
rapide.
Dans cette structure de
données un nœud ne peut
avoir qu’au plus 2 fils.
Pas fils
Un fils
246
Le Nœud d’un Arbre
Data: Donnée
Null Null
247
Le Nœud d’un Arbre
Data: Donnée
Null
Data: Donnée
Null Null
248
Démo créer le l’arbre binaire et les méthodes
NœudArbre.java
ArbreBinaire.java
249
Arbre Binaire
Un arbre peut contenir
tout type de données
utilisateurs. 5
cet arbre contient des

entiers non ordonnés .
Lorsque les données se
présentent comme suit,
cela n’a pas une grande
valeur ajoutée pour
rechercher ou pour 28
26
insérer les données.
En général ce type
de structure n’est
50 19 pas utilisé. On
préfère utiliser un
arbre binaire de
recherche.
250
Arbre Binaire de recherche
Pour chaque nœud
parent, le fils gauche est 52
plus petit et celui de la
droite plus grand.
33 65
25
39 60 78
12 27 34 48 72 92
70
251
Arbre Binaire de recherche
52
Garder cette propriété
rend facile la recherche.
33 65
25
39 60 78
12 27 34 48 72 92
70
252
AB: recherche d’un élément
Comment rechercher un 52
élément?
On compare avec la racine

d’abord si l’élément 33 Recherche(52) 65
correspond on arrête la
recherche.
25
39 60 78
12 27 34 48 72 92
70
253
AB: recherche d’un élément
On compare avec la racine 52
d’abord si l’élément est
inférieur à la racine. Selon
la propriété de l’arbre
binaire il doit se trouver à 33 Recherche(39) 65
gauche de la racine.
25
39 60 78
12 27 34 48 72 92
70
254
AB: Insertion d’un élément
On commence par la 52
racine d’abord. l’élément Insérer(63)
est supérieur à la racine.
Selon la propriété de
l’arbre binaire de 33 On comparer avec le 65
recherche il doit se premier l’élément se
trouver à droite de la trouvant à droite de la
racine. racine. S’il est plus petit,
on continue vers la
25 gauche.
39 60 78
12 27 34 48 72 92
70
256
AB: Insertion d’un élément
52
Insérer(63)
33 65
25
39 60 78
12 27 34 48 63 72 92
70
257
Implémentation de la méthode
insertion
Demo
NœudArbre → insérer la méthode insertion
public void inserer(Integer donnee){

if (donnee>= this.donnee){
if(this.filsDroite == null)
this.filsDroite = new NoeudArbre(donnee);// recursion
else
this.filsDroite.inserer(donnee);
}else {
if (this.filsGauche== null)
this.filsGauche = new NoeudArbre(donnee);
else
this.filsGauche.inserer(donnee);
}
}
258
AB: suppression d’un élément
Cas1: le nœud à 52
supprimer est une feuille supprimer(34)
Cas2: le nœud à
supprimer à un fils 33 Cas1: le nœud à 65
Cas3: le nœud à supprimer est une feuille
supprimer à deux fils
25
39 60 78
12 27 34 48 72 92
Le nœud est trouvé, on

vérifie s’il est une 70
feuille.
259
52
supprimer(34)
Pour un nœud, on pointe le
nœud parent vers null
33 65
Cas1: le nœud à
supprimer est une feuille
25
39 60 78
Null
12 27 34 48 72 92
Le nœud est trouvé, on

vérifie s’il est une 70
feuille.
260
52
supprimer(34)
Pour un nœud, on pointe le
nœud parent vers null
33 65
Cas1: le nœud à
supprimer est une feuille
25
39 60 78
Null
12 27 34 48 72 92
70
261
AB: Implémentation -suppression
//cas:1 suppression de noeud sans fils
public void supprimer(Integer donnee){// etap 8
//etap13 --cas1 : le noeud n'a aucun fils

NoeudArbre current = this.racine; //initialisation
NoeudArbre parent = this.racine;// initialisation
boolean estFilsGauche = false;
if(current == null)// si racine est vide
return ;
while(current != null && current.getDonnee()!= donnee){ // si current on a atteint la fin
if (donnee < current.getDonnee()){
current = current.getFilsGauche();
estFilsGauche = true;
}else {
current = current.getFilsDroite();
estFilsGauche = false;
}
}
if (current == null)// l'element n'est pas retrouvé sur l'arbre
return;
if (current.getFilsGauche()==null && current.getFilsDroite()==null)
// verifie s'il pointe vers la racine
{ if (current == racine){
racine = null;
}else {
if (estFilsGauche)
parent.setFilsGauche(null);
else
parent.setFilsDroite(null);
}
} Demo
} ArbrebinaireRecherche.java
}
262
52
supprimer(72)
Cas2: le nœud à
33 supprimer a un fils 65
25
39 60 78
12 27 34 48 72 92
L’élément est retrouvé, on pointe alors le nœud

parent vers le fils du nœud à supprimer. 70
263
52
supprimer(72)
Cas2: le nœud à
33 supprimer a un fils 65
25
39 60 78
12 27 34 48 72 92
70
264
52
supprimer(72)
33 Cas2: le nœud à 65
supprimer a un fils
25
39 60 78
72
92
12 27 34 48
70
Si le fils du nœud à supprimer a aussi des fils. On
procède de la même manière.
71 73
265
52
supprimer(72)
33 Cas2: le nœud à 65
supprimer a un fils
25
39 60 78
72
92
12 27 34 48
70
71 71
266
Types de données abstrait pour
un arbre
Principe
◦ Des données sont associées aux nœuds d’un arbre
◦ Les nœuds sont accessibles les uns par rapport aux autres selon leur position dans
l’arbre
Interface : pour un arbre T et un nœud n
◦ PARENT(T, n): renvoie le parent d’un nœud n (signale erreur si n est la racine)
◦ Fils(T, n): renvoie une structure de données(ordonnée ou non) contenant les fils du
nœuds n ( exemple: une liste)
◦ EstRacine(T, n): renvoie vrai si n est la racine de l’arbre;
◦ estInterne(T, n): renvoie vrai si n est un nœud interne;
◦ estExterne(T, n) : renvoie vrai si n est un nœud externe;
◦ GetDonnee(T,n): renvoie les données associées au nœud n;
◦ FilsGauche(T, n), FilsDroit(T,n): renvoie les fils gauche et droit de n (pour un arbre
binaire)
◦ Racine(T): renvoie le nœud racine de l’arbre;
◦ Taille(T): renvoie le nombre de nœuds de l’arbre;
267
Implémentation d’un arbre
Première solution: numérotions de niveaux
▪L’arbre est représenté par un tableau;
▪Chaque position dans l’arbre est associé à un rang particulier:
▪ La racine est en position 1
▪ Si le nœud est au rang r, son successeur gauche est au rang 2r, son successeur
droit au rang 2r+1
▪Si l’arbre binaire n’est pas un arbre binaire complet, le tableau contiendra
des trous (qu’il faudra pouvoir identifier)
▪Complexité en temps des opérations : O(1)
▪Complexité en espace : O(2n) pour un arbre de n noeuds O(n) pour un arbre
binaire complet
268
Implémentation d’un arbre
binaire
✓Deuxième solution: structure liée
✓Un champ de données n.data;
✓Un pointeur vers son nœud parent (n.parent);
✓Un pointeur vers ses fils gauche et droit (n.left et n.right);
✓Complexité en temps des opérations : O(1);

✓Complexité en espace : O(n) pour n noeuds.
269
Implémentation des arbres
binaires
Implémentation des arbres binaires dans le reste de cours
◦ T représente l’arbre, qui consiste en un ensemble de nœuds
◦ T.root est le nœud racine de l’arbre T
◦ Nœud x
◦ X.parent est le parent du nœud x
◦ X.cle est la clé stockée au nœud x
◦ x.filsGauche est le fils de gauche du nœud x
◦ X.filsDroit est le fils de droite du nœud x
◦ Pour simplifier les notation, nos méthodes seront implémentées directement
sur base de cette implémentations (et pas de l’interface générale)
270
Arbres binaires de recherche
Une structure d’arbre binaire implémentant un dictionnaire, avec des
opérations en O(h) où est la hauteur de l’arbre
Chaque nœud de l’arbre binaire est associé à une clé
L’arbre satisfait à la propriété d’arbre binaire de recherche
◦ Soient deux nœuds x et y.
◦ Si y est dans le sous-arbre de gauche de x , alors y.cle <x.cle
◦ Si y est dans le sous-arbre de droite de x y.cle > x.cle
271
Arbres binaires de recherche
Toutes les opérations sont O(h) où h est la hauteur de l’arbre
Si n éléments ont été insérés dans l’arbre
◦ Au pire, h=n-1=O(n)
◦ Elément insérés en ordre
◦ Au mieux, h=[log2n]= O(logn)
◦ En moyenne, on peut montrer que h=O(logn)
◦ En supposant que les éléments ont été insérés en ordre aléatoire
272
Arbres binaires -parcours
1- Parcours infixe (In-order traversal)
2- Parcours prefixe (Pre-order traversal)
3- Parcours postfixe(Post – order traversal)
273
Arbres binaires -parcours
Parcours infixe (In-order traversal)
1. Parcours sous-arbre à Un parcours infixe, visite

gauche chaque nœud entre les
2. Visite la racine nœuds de son sous-arbre
3. Parcours sous-arbre à 28 de gauche et les nœuds de
26
droite son sous-arbre de droite.
Autrement dit, chaque
nœud est visité après son
enfant gauche mais avant
26 5 28 son enfant droit.
274
Arbres binaires –parcours infixe
52
33 65
25
39 60 78
72
92
12 27 34 48
12 25 27 33 34 39 48 52 60 65 72 78 92
275
275
Arbres binaires-parcours prefixe
Dans un parcours
5
prefixe( preorder
traversal) chaque
nœud est visité avant
1. Visite racine que ses enfants soient
2. Parcours Sous visités.
arbre à gauche
3. Parcours Sous 28
26
arbre à droite
5 26 28
276
Arbres binaires –parcours prefixe
52
33 65
25
39 60 78
72
92
12 27 34 48
52 33 25 12 27 39 34 48 65 60 78 72 92
277
277
Arbres binaires-parcours
postfixe
5 Dans un parcours
postfixe( post-order
traversal) chaque
1. Visite Sous arbre nœud est visité après
gauche que ses enfants soient
2. Visite Sous arbre visités.
droit 28
26
3. Visite racine
26 28 5
278
Arbres binaires –parcours postfixe
52
33 65
25
39 60 78
72
92
12 27 34 48
12 27 25 34 48 39 33 60 72 92 78 65 52
279
279
Hauteur d’un Arbre
n = nombres de nœuds
Niveau 1: 20
Niveau 2: 21
Niveau3: 22
----- ---------- -------- -------------- ---- -- - -- - - -- --- - - - - - - - - - - - - - - -- ------- -- ------------------ - - - - - - -

Niveau h: 2h-1
280
280
Niveau 1: 20
Niveau 2: 21
Niveau3: 22
1+2+4+…..+2h-1=n
Niveau h: 2h-1
281
281
1+2+4+…..+2h-1=n , suite géométrique
(2h-1 ) =n
(2-1)
(2h-1 ) =n
→ 2h = n+1
→ h = log2n+1
h= O(log2n)
282
282
Les monceaux: Heaps
Ces monceaux sont différents de ceux de la
mémoire de Java là où les objets sont crées.
un monceau( heap) , c’est une structure de
données
Heap est un arbre binaire mais pas un arbre binaire
de recherche
A la différence de l’arbre binaire de recherche :
le heap:
- complet: c’est-à-dire des nœuds à gauche
et à droite
- Arbre est dense
complet
incomplet
283
Les monceaux: Heaps
Le Monceau(Tas) est un arbre binaire mais pas un
arbre binaire de recherche
On ne peut pas
ajouter un nœud,
la structure ne
sera pas un
monceau
284
Les monceaux: Heaps
Heap est un arbre binaire mais pas un arbre binaire
de recherche.
285
Comment construire un monceau:
Heaps
Pour créer un Heap on commence par la racine
On ne peut pas le
construire de cette
manière. Le heap
perdra sa propriété.
286
Comment construire un monceau:
Heaps
Le nouveau nœud
doit être ici.
Une autre propriété du heap: chaque clé du nœud

parent est supérieur ou egal aux clés de ses fils ou bien
les données qui en sont contenues.
287
un monceau: Heaps
chaque clé du nœud parent est supérieur ou égal aux

clés de ses fils ou bien les données qui en sont
contenues.
15
13 12
3 11 8
6
15
13 12
3 14 8
6
288
Heaps: suppression de la racine
Pour supprimer, la racine on
fait usage de file à priorité
Pour conserver la structure 10

20
du heap, on ramène
premièrement le nœud à
la place de la racine 15 12
13 11 8
6
3 10
Ensuite, on fait descendre le nœud

pour maintenir la 2é propriété du
monceau. Ainsi on permute avec la
clé la plus élevée.
289
Heaps: suppression de la racine
Pour supprimer, la racine on
fait usage de file à priorité
Pour conserver la structure 15

du heap, on ramène
premièrement le nœud à
la place de la racine 13
10 12
10
13 11 8
6
Ensuite, on fait descendre le nœud La complexité en temps pour supprimer un

pour maintenir la 2é propriété du nœud = O(1 + log2n) = O(log2n)
monceau. Ainsi on permute avec la
clé la plus élevée.
1 , pour mettre le dernier Pour maintenir
au niveau de la racine le monceau
290
Heaps: insertion d’un noeud
Nous devrons insérer les
nœuds en conservant la
structure du heap, c’est-à-
dire commencer toujours 15
par la gauche pour ajouter
un nœud; la seule place
indiquer c’est au niveau
de la clé 3 13 12
3 11 8
6
Comme cela la 2e
propriété
10
291
Comme cela la 2e
propriété n’est pas
respectée, qui dit que la 15
clé du nœud parent doit
être supérieur des fils
13 12
10
3 11 8
6
10
3
20
292
Comme cela la 2e
respectée, qui dit que la
clé du nœud parent doit 15
13 12
10
20
13 11 8
6
3 10
20
293
Comme cela la 2e
être supérieur à celle des
fils
20
13 12
13
20 11 8
6
3 10
294
Comme cela la 2e
20
15
20 12
13 11 8
6
3 10
20
Reconstruire le monceau,
La complexité en temps:
O(log2n)
295
Heaps: comme file à priorité
Dans un heap la clé de la racine
est toujours plus élevé, c’est
pour cela qu’un monceau
pourrait être considéré comme
une file à priorité. 20
15 12
25
13 11 8
6
3 10
Alors l’élément à la racine aura

toujours la plus haute priorité.
296
est toujours plus élevé, c’est
15 12
13
25 11 8
6
3 10

297
est toujours plus élevée, c’est
25 12
15 11 8
6
3 10

298
est toujours plus élevée, c’est
20 12
15 11 8
6
3 10

299
Supposons, que l’on souhaite
7 changer la priorité à la clé 15
20
15 12
13 11 8
6
3 10
300
20
7
13 12
13
7 11 8
6
3 10
301
20
13 12
10
7 11 8
6
3 10
7
La complexité en temps pour
changer une clé dans un
monceau est : O(log2n)
302
Monceau/heap: comment implémenter?
Représentation d’un monceau comme un tableau
On peut représenter
les éléments du 20
20 0
monceau comme les
éléments du tableau
(vecteur-array) 0 15 1
15 12
12 2
1 2
13 11 8 13 3
6
11 4
3 4 5 6
6 5
3 10
8 6
i
7 8
3 7
2i + 1 2i +2 10 8
Pour maintenir les propriétés du monceau,
on commence l’insertion de gauche à droite
303
Table de hachage
Une table de hachage est une structure de données qui permet une association clé–valeur. Le but de cette
structure de données est d'accéder le plus rapidement possible à un élément à partir de sa clé.
Clés Valeurs
1 Item‘(1, ’’chocolat’’, ‘’L’’,55)
2 Item‘(1, ’’chocolat’’, ‘’s’’,25)
3 Item‘(3, ’’chocolat’’, ‘’M’’,45)
4
Item‘(4, ’’ananas’’, ‘’L’’,40)
*
*
*
*
140 Item‘(140, ’’mangue chip’’, ‘’M’’,15)
304
Table de hachage
Objets utilisateurs
Clés Valeurs
abc@abarta.com user(1, ’’A’’, ‘’B’’,’’ abc@abarta.com ’’)
abc1@abarta.com user1(1, ’’A’’, ‘’B’’,’’ abc@abarta.com ’’)
abc2@abarta.com user2‘(1, ’’A’’, ‘’B’’,’’ abc@abarta.com ’’)
Cette structure de données consiste en un tableau (la table de hachage) dont les
cases sont appelées alvéoles et une fonction( appelée la fonction de hachage).
305
Table de hachage
Les opérations permises par une table de hachage sont les suivantes :
Insertion : insère(H,élt,clé) : insère dans la table de hachage H un

élément élt dont la clef est clé.
Recherche :élément recherche(H,clé) : recherche dans la table de

hachage H si un élément est associé à la clef clé et
renvoie cet élément.
suppression :La suppression d'un élément dans une table de hachage ouverte
n'est pas une chose aisée.
306
Fonction de hachage
La fonction de hachage associe à une clé une valeur Une fonction de hachage mappe les clés de manière
de hachage. Elle fait donc correspondre la clé d'un aléatoire dans les alvéoles des tableaux Ces clés ne
élément à une valeur qui est utilisée peuvent être stockées à la même position.
comme index dans la table de hachage pour cet
élément.
0
1
2
C1*
3 m
C2*
C3* Lorsque deux clé

ont la même
C4* valeur de
m-1 hachage, on dit
qu'on a une
T collision.
Clés
Collision
307
Fonction de hachage
h(c) = c % m Une bonne fonction de hachage est utile aux performances, surtout si les collisions
sont résolues ensuite par des explorations séquentielles : toute fonction de hachage
provoquant beaucoup de collisions (par exemple la fonction qui à une clé associe la
n=25 m=25 valeur ASCII de son premier caractère) ralentira nettement la recherche. Un bon
compromis est à trouver entre :
rapidité de la fonction de hachage ;
h(501)=501 %25 = 1 taille à réserver pour l'espace de hachage ;
réduction du risque des collisions. Source: Wikipédia (08,10,19)
h(503)=503 %25 = 3
h(525)=525 %25 = 0 0
1
2
501*
3
502*
503*
******
525*
24
308
Fonction de hachage
Pour résoudre le
h(c) = c % m problème collision
n=25 m=12 on utilise le chainage
h(501)=501 %12 = 9
h(503)=503 %12 = 11
h(513)=513 %12 = 9 0
h(525)=525 %12 = 10 1
2
501*
3
503*
****
513* 9 513 501
****** 10 502
525*
11 503
309
Fonction de hachage
n=13 m=12
h(c) = c % m Collision au niveau
de la clé 8: Pour
résoudre le
h(500)=500 %12 = 8 problème collision
on utilise le
h(502)=502 %12 = 10 chainage
h(504)=504%12 = 0 0
*******
h(524)=524 %12 = 8 1
500*
2
502* 3
504*
****
506* 8 524 500
508*
10 502
******
524* 11 504
310
Collision et résolution
Pour gérer ce problème, on doit alors
utiliser une stratégie de résolution des
collisions.
C1*
C2* i
C3*
C4*
M-1
Clés
Il existe deux méthodes principales pour

gérer ce problème:
1. par chaînage;
2. par adressage ouvert
311
1, Par chainage:
Null
c1
obj1
C1*
C2* Null
i
c2 c4
C3*
obj2 Obj4
C4*
Null
c3
m-1
Clés obj3
312
Complexité en temps : chainage
Au pire de cas
C1*
Null
C2* i c1 c2 c3 c4
C3* obj obj obj obj
C4*
1 2 3 4
M-1
Clés
Rechercher(Ci)= O(n) en liste liée.

C’est un temps linéaire
313
Complexité en temps
Cas: En moyenne
𝒏
=α facteur de charge
𝒎
0
1
*
C1*
*
C2* *
Clés
C3* i
C4*
C5*
m-2
m-1
Si on a n clés à mettre dans m alvéoles, dans chaque alvéoles, on a en moyenne
314
Cas: En moyenne
Rechercher(Ci)= 𝑶(𝟏 +α)= O(1)

1: appel de fonction de hachage
α : taille moyenne de la liste dans une chaine Le temps est constant
n/m=constante.
0
1
*
C1* *
C2* *
Clés
C3* i
C4*
C5*
m-2
m-1
315
Par adressage ouvert:
L'adressage ouvert consiste, dans le cas d'une collision,

0 311 La position de ces alvéoles
est déterminée par une
à stocker les valeurs de hachage dans d'autres alvéoles
1 méthode de "sondage".
de la table. ,
h(256,0) 2 256
h(256,1) 3 512 L’adressage ouvert requiert

toujours cette condition:
h(256,2) * **
n≤m
*** n: nombres de clés,
m : la taille de la table
m-2 604
m-1
316
Par adressage ouvert: 0 321
0 → un pas de sondage 1
h(256,0) 2 256
h(256,1) 3 512
h(256,2) * **
***
m-2 604
Comment se passe le sondage( probing)?
Lors d'une recherche, si la case obtenue par m-1
hachage direct ne permet pas d'obtenir le bon
élément, alors une recherche sur les cases obtenues
par une méthode de sondage est effectuée jusqu'à
Quelles sont les méthodes de
trouver l'élément, ou non, ce qui indique qu'aucun sondage?
élément de ce type n'appartient à la table.
317
Par adressage ouvert: 0 321
1
h(256,0) 2 256
h(256,1) 3 512
h(256,2) * **
***
les méthodes de sondage:
m-2 604
Le sondage linéaire
m-1
Le sondage quadratique
Le double hachage
318
Adressage ouvert:
Le sondage linéaire 0 321
1
0 → un pas de sondage
h(256,0) 2 256
h(256,1) 3 512
h(256,2) 4 546
5 256
l'intervalle entre les cases est fixe, souvent 1. La position de

l'alvéole suivante pour le ième appel est donnée par la clé m-1
suivant ou next(clé, i) = (hash(clé) + i) mod m.
h(c, i)=(h(c,0)+i) % m
319
Adressage ouvert:
Le sondage quadratique 0 33211
1 511
h(256,0) 2
h(256,1) 3 512
h(256,2) 4 546
h(256,4) ****
256
l'intervalle entre les cases augmente linéairement. Les indices des
cases augmentent donc quadratiquement : +2 , +6, +12, +20 ... m-1
La position de l'alvéole suivante pour le ième appel est donnée par
Suiv(clé, i) = ((hash(clé) i + i 2) mod m.
h(c, i)=(h(c,0)+i2) % m
320
Adressage ouvert:
Le double sondage
l'adresse de la case est donnée par une deuxième fonction de

hachage, ou hachage secondaire.
h(c, i)=(h1(c)+h2(c) )% m
321
Adressage ouvert: complexité en temps
Supposons un hachage uniforme:
Dans le pire cas: O(n)
322
Quiz
Une feuille n’a pas de fils, dans un arbre ?
• Vrai
• Faux
323
Quiz
Un arbre binaire de recherche a :
• Le descendant gauche est inférieur à la racine

• Le descendant gauche est supérieur à la racine
• Le descendant droit est inférieur à la racine
• Des données aléatoire
324
Quiz
La hauteur d’un arbre équilibrée à n nœuds est de :
• log2n
• n2
• n
• O(n)
325
Quiz
Dans un arbre binaire de recherche, quelle est la méthode qui affiche les données dans un
ordre croissant?
• Infixe
• prefixe
• postfixe
• aucune
326
Quiz
Que signifie arbre binaire complet?
• Toutes les données sont ont été insérées.
• Toutes les rangées possèdent des nœuds, excepté probablement la dernière.
• Tous les nœuds de l’arbre contiennent des données.

• La disposition de nœud satisfait les critères de l’arbre binaire de recherche
327
Quiz
Un monceau peut être représenté par un tableau (array) parce qu’il est un arbre binaire
complet.
• Vrai.
• Faux
328
Quiz
Le dernier nœud dans un monceau est :
• Toujours le fils gauche.

• Toujours le fils droit.
• Toujours sur la dernière rangée ou dernier niveau
• Jamais inférieur aux enfants du même parent.
329
Quiz
Quelle serait l’ordre des éléments du tableau (array) ci-dessous, s’il satisfait les critères de
monceau?
[ 20,12,25,6,10,15,13 ]
• A: [ 25,12,20,6,10,15,13 ]
• B: [12,20,25,6,10,15,13 ]
• .
• C: [ 25,12,20,6,10,13,15 ].
• D: [ 25,12,20,6,13,10,15 ]
330
Quiz
Combien de tableau(x) est (sont ) nécessaire (s) pour un algo de tri pour un monceau?
• 1
• n
• 2
• n2
331
Quiz
La table de hachage est une structure de donnée qui associe chaque clé à une valeur
• Vrai
• Faux
332
Quiz
• 1
• n
• 2
• n2
333
Quiz
• 1
• n
• 2
• n2
334
Quiz
Soit n, le nombre de clés et m, le nombre d’alvéoles ; le facteur de charge d’une fonction
de hachage est:
• n/m
• n(m)
• m2
• n2
335
Quiz
Pour les problèmes de collisions dans une table de hachage, quelle structure de donnée
permet-elle de faire la résolution par chainage?
• File
• Liste liée
• pile
• tableau
336
Quiz
Le Hachage permet de stocker les données avec une complexité en temps de :
• O(1)
• O(log2n)
• O(n)
• O(n2 )
337
Quiz
L’adressage ouvert c’est :
• Un hachage d’une chaine de caractère
• Un hachage de n’importe quel objet

• Une méthode de résolution de collision
• N’a aucune signification
338
Quiz
Le facteur de charge doit être supérieur ou égal à 1 pour que l’adressage ouvert
fonctionne? :
• Vrai
• Faux
339
Graphes
340
Graphes
C’est une structure de données abstraite qui consiste en un ensemble fini
éventuellement mutable de sommets ou nœuds, ou points, avec un ensemble de paires
ordonnées ou non de tels éléments.
Un graphe (dirigé est un couple (V,E) où:
◦ V est une ensemble de nœuds( nodes), ou sommets( vertices et
◦ E inclus VxV est un ensemble d’arcs, ou arêtes(edges).
Un graphe non dirigé est caractérisé par une relation symétrique entre les sommets
◦ Une arête est un ensemble e ={u,v} de deux sommets
Applications : modélisation de :
◦ Réseaux sociaux
◦ Réseaux informatiques
◦ World wide web
◦ Cartes routière
◦ ……
341
Terminologie: graphe non dirigé
1 2
5 4
342
Terminologie: graphe non dirigé
Deux nœuds sont adjacents s’ils sont liés par une même arête
Une arête(v1,v2) est dite incidente aux nœud v1 et v2
Le degré d’un nœud est égal au nombre de ses arêtes incidentes
Le degré d’un graphe est le nombre maximal d’arête incidentes à tout
sommet.
Un graphe est connexe s’il existe un graphe non orienté et un sous-
graphe connexe maximal de ce graphe
343
Terminologie : graphe dirigé
1 2 3
4 5 6
V= {1,2,3,4,5,6}
E={ (1,2), (1,4), (2,5),(3,5),(3,6),(4,2),(5,4),(6,6)}
344
Terminologie : graphe dirigé
Une arête(v1, v2) possède l’origine v1 et la destination v2. cette arête est
sortante pour v1 et entrante pour v2
Le degré entrant (in-degree) et le degré sortant (out-degree) d’un nœud v
sont respectivement égaux aux nombre entrantes et d’arêtes sortantes
de v
Un graphe est acyclique s’il n’y a aucun cycle, c’est –à dire s’il est pas
possible de suivre les arêtes du graphes à partir d’un sommet x et de
revenir à ce même sommet x
345
Typologies de graphes
Trois grandes familles
◦ Graphes Structurés
◦ Homogènes, hiérarchiques, cycliques, centralisés/polaires
◦ Graphes Multipolaires
◦ Graphes quelconques
On parle souvent de graphe simple s’il ne possède pas de boucle composée

d’une seule arête, c’est-a-dire tel que :
◦ Un arbre est un graphe acyclique connexe
◦ Un multi graphe est une généralisation des graphes pour laquelle il est permis de
définir plus d’une arête liant un sommet à un autre ( network d’avions)
◦ Un graphe est pondéré si les arêtes sont annotées par des poids
◦ Exemple: réseau entre les villes avec comme poids de la distance entre les villes , réseau internet avec
comme poids la bande passante entre routeurs, etc.
346
Les opérations dans les graphes
Ajouter_arête(G, x,y) :ajouter l’arête
Supprimer_arête(G,x,y):supprimer l’arête
Ajouter_sommet(G, x): ajoute le sommet x s’il n’y figure pas
Supprimer_sommet(G, x) : supprime le sommet s’il existe
Sont_adjacents (G,x,y) verifie s’il ya une arête de x à y
Voisins (G, x) liste les sommets qui sont adjacents à x
Retourner_valeur_sommet(G,x)
Fixe_valeur_sommet(G,x,y)
347
Représentation
Pour l’implémentation des graphes, plusieurs structures de données sont
utilisées pour la représentation des graphes.
1. Liste d’adjacence
Les sommets sont représentés comme des objets ou enregistrement, et à
chaque sommet est associé une liste de sommets adjacents.
2. Matrices d’adjacences
1. C’est une matrices carrée V x V, ou les lignes représentent les sommets de
départ et les colonnes d’arrivée.( cas graphes non orientés)
3. Matrice d’incidence
1. C’est une matrice V x E où les lignes représentent les sommets et les
colonnes les arêtes.
Dans le cadre de ce cours, nous allons utiliser les liste adjacentes
348
Représentation : Listes
d’adjacentes
Les sommets sont représentés comme des objets ou enregistrement, et à chaque
sommet est associé une liste de sommets adjacents
Un objet G de type graphe est composé
D’une liste de nœuds G.V = { 1,2,…… |V|}
D’un tableau G.Adj de |V| listes tel que
◦ Chaque sommet u € G.V est représenté par une élément du tableau G.Adj
◦ G.Adj [u] est la liste d’adjacence de u c-a-dire la liste des sommets v telsque (u,v) €
E.
◦ Permet de représenter les graphes dirigé ou non
Si le graphe est dirigé (resp. non dirigé), la somme des longueurs des liste de
G.Adj est |E| (resp. 2|E|)
Permet de représenter un graphe pondéré en associant un poids à chaque
élément.
349
Exemple de représentation par liste
adjacente: graphe non dirigé
1 2 5 /
2 1 5 3 4 /
3 2 4 /
2 5 3 /
4
5 4 1 2 /
350
Exemple de représentation par
liste adjacente: graphe dirigé
1 2 4
1 2 3
2 5
3 6 5 /
4 2 /
4 5 6
5 4 /
6 6
351
❖ Ajout sommet :O(1)
❖ Ajout arête: O(1)
❖ Supprimer sommet: O(|E|)
❖ Supprimer arête: O(|V|)
❖ La suppression est lente parce qu’il faut trouver les sommets ou les
arêtes
352
Parcours de graphes
Objectif : parcourir tous les sommets d’un graphe qui sont accessible à
partir d’un sommet v donné
Un sommet v’ est accessible de v si
◦ Soit v’=v
◦ Soit v’ est adjacent à v
◦ Soit v’ est adjacent à un sommet v’’ qui est accessible à partir de v
Différents types de parcours:

◦ En profondeur d’abord (depth-first)
◦ En largeur d’abord (breadth-first)
353
Parcours en profondeur d’abord
Parcours du graphe en profondeur
◦ On suit immédiatement les arêtes incidentes au dernier sommet visité
◦ Au lieu de les mettre en attente dans une file
◦ On revient en arrière (backtrack) quand le sommet visité n’a plus de sommets adjacents non
visités
Voir exemple
354
Exemple: Parcours en
profondeur d’abord
A B C
D E
F G H
Parcours en profondeur à partir de A: A-D-F-G-B-E(C et H pas accessible)
355
Parcours en profondeur :
implémentions avec une pile
356
Parcours en largeur d’abord
(breadth-first search)
Breadth-first search est un des algorithmes les plus simple pour parcourir un
graphe.
Entrées: un graphe G = (v, E) et un sommet s € V

Parcourt le graphe en visitant tous les sommets qui sont accessibles à partir de s
Parcourt les sommets par ordre de croissant de leur distance (en nombre
minimum d’arêtes par rapports à S
◦ On visite s
◦ Tous les voisins de s
◦ Tous les voisins des voisins de s
◦ Etc
Fonctionne aussi bien pour des graphes dirigés que non dirigés
357
Exemple: parcours en largeur
d’abord
s f
c Parcours en largeur à partir de s :

s-a-c-e-g-b-h-i-f
g
a
i
e
h
Pour l’ implémentation:
- On doit retenir les sommets déjà visités de manière à éviter de boucler
infiniment
- On doit retenir les sommets visités dont on n’a pas encore visité les voisins
358
Résumé
Listes chainées (simplement et doublement );
Les tableaux (arrays);
Les piles;
Les files;
Les files à priorité;
Les arbres;
◦ Les arbres binaires
◦ Les arbres binaires de recherche
Les monceaux(heap);
Les tables de hachages;
Les graphes.
359
Merci de votre participation à ce
cours . SDD1
360

Structures de Données I - 2022 - UAM

Transféré par

Droits d'auteur :

Formats disponibles

Structures de Données I - 2022 - UAM

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Structures de Données I - 2022 - UAM

Transféré par

Droits d'auteur :

Formats disponibles

Structure des données I

PAR SOUMAILA M., ING., OCP,OCE

❖ Expert informaticien du Projet SyGMEF

19 ans d’expériences dans le domaine des systèmes d’informations

Certifié Expert Oracle performance Tuning

Certifié professionnel Database administrateur (11g, 12c)

Ingénieur en mathématiques appliquées et informatique(jan,2004)

Plusieurs formations: Linux, oracle, Microsoft sql serveur , ITIL,

Compétences: SE oracle linux, bases de données : oracle, SQL

Développement: site web sur JOOMLA, liferay, dreamweaver

Gestion documentaire sur Alfresco

INF3015 Structures de données et algorithme, Notes de cours , Éric Beaudry Département

Une structure de données a une interface qui consiste en un ensemble de

On peut implémenter les structures des données avec plusieurs langages

Un ensemble fini de règles qui comprend une séquence d’opérations

✓ Procédures de calcul bien définie;

Input: liste non triée

Un même algorithme peut être implémenté dans différents langages (Java,

Structures de contrôle itératives

for (i=0; i<10; i++)

Données des fonctions

Instructions, fonctions, Pile

public static void

public static void main(String[] args) {

public static void main(String[] args) {

public static void main(String[] args) {

public static void main(String[] args) {

For i=0 to A.taille-2

For i=0 to A.taille-2

300 pas 150 pas

Deux algo : 100 -10ms

Elements Algo1 (ms) Algo2(ms)

200 Progression 20 40 Progression

1000 100 1000

10000 1000 100000

❑dans le pire des cas

Suppose c2n2 > t(n) T(n)=pn2+qn+r

Suppose c1n2 < t(n)

Soit g(n)=n2 on peut écrire

O(g(n))= { f(n) : il existe une constante positive c et n0 tel

O(n) est le meilleur temps d’un algo

Int[] b = {5,8,1………..25,20} 100 Elts

◦ fonction de la taille des données en entrée

◦ fonction du nombre de fois où une opération de base est répétée dans

Beaucoup d’outils disponibles (packages)

System.out.println("Hello, World!"); Une instruction

Stocker ce programme dans le fichier Hello.java

littéral: "Hello World!"

contient une séquence d'instructions, délimitée par { }

Erreur si: age = "quarante";

Pour les références à un objet

for (int i = 0; i<10; i++) somme = somme + i; i<10?

somme: 0 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, sortie

while (balance < targetBalance) {

double interest = balance * rate;

System.out.println(years + " years are needed");

nombreAnnees(1000, 1500, 0.05)

56 years are needed

public static void main(String[] args) {