Chapter 1

Quelques rappels algorithmiques

1.1 Concepts de base

1.1.1 Algorithme

Une succession finie d’opérations qui donne la solution d’un problème donné. Pour
écrire un algorithme, on utilise un pseudo-langage compréhensible par une com-
munauté. Donc, l’idée générale d’un algorithme est de donner la solution d’un
problème sous forme d’opérations qui peuvent être traduites dans un langage
compréhensible par la machine tout en le gardant lisible et compréhensible par
une personne ordinaire.

Figure 1.1: Démarche générale de résolution d’un problème informatique

1
 Comme illustré par la figure ci-dessus, plusieurs étapes sont nécessaires pour
résoudre un problème en informatique :

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.

2. Analyse du problème
Elle consiste à 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’étape d’analyse est un algorithme.
Note: Sachez qu’il existe des problèmes pour lesquels on ne peut trouver
une solution et par conséquent il est impossible de donner l’algorithme corre-
spondant. Cette catégorie de problèmes sera étudiée dans une autre unité
d’enseignement prévue dans ce cursus.

3. Ecriture d’un algorithme avec un langage de description algorith-

mique
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 im-
possible de le faire en langage naturel, l’existence d’un langage algorithmique
s’impose.

4. Traduction de l’algorithme dans un langage de programmation

Les étapes 1, 2 et 3 se font sans le recours à la machine. Si on veut ren-
dre l’algorithme concret ou pratique, il faudrait le traduire dans un langage
de programmation. Nous dirons alors qu’un programme est un algorithme

2
 exprimé dans un langage de programmation.

5. Mise au point du programme: Si les résultats obtenus sont ceux atten-

dus, 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.

1.1.2 Propriétés d’un algorithme

On peut énoncer les cinq propriétés suivantes que doit satisfaire un algorithme :

– Généralité : un algorithme doit toujours être conçu de manière à envisager

toutes les éventualités d’un traitement.

– Finitude : Un algorithme doit s’arrêter au bout d’un temps fini.

– Définitude : toutes les opérations d’un algorithme doivent être définies sans
ambiguı̈té.

– Répétitivité : généralement, un algorithme contient plusieurs itérations, c’est

à dire des actions qui se répètent plusieurs fois.

– 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.

3
1.1.3 Programme

Un programme est un assemblage et un enchaı̂nement d’instructions élémentaires

écrites dans un langage de programmation, et exécuté par un ordinateur afin de
traiter les données d’un problème et renvoyer un ou plusieurs résultats.

1.1.4 Langage de programmation

Un langage de programmation fournit un ensemble de mots-clés et de règles de

syntaxe qui permettent de créer des instructions formant des programmes et qui
peuvent s’exécuter, sans souci, sur une machine.

1.2 Variables et instructions

La figure suivante donne la structure générale d’un algorithme :

Figure 1.2: Structure d’un algorithme

La première ligne (1) permet juste d’identifier l’algorithme. Donc, le nom at-

4
tribué ne change pas l’exécution et les résultats. Avant de mettre les instructions,
il faut déclarer (2)les constantes(3) et les variables(4) utilisées dan l’algorithme.
La partie principale de l’algorithme se trouve entre les mots clés ‘début’ et ‘fin’
(5). Elle contient la suite d’instructions à exécuter.

Figure 1.3: Exemple algorithme

1.2.1 Notion de varible

Une variable est un mot qui permet l’identification de l‘emplacement mé- moire
où on stocke une valeur à manipuler. Malgré que le choix est libre du nom de la
variable, il préférable, pour des raisons de lisibilité et de compréhension de choisir
des noms de variables en fonctions de ce qu’elles représentent. Par exemple :
Moyenne, Poids, Taille,. . .etc.
La notion de type d’une variable est capitale, car elle implique le choix du codage
de la variable (par exemple, un entier sur 32 bits et un caractère sur 16 bits) ainsi
que les possibilité d’usage ( par exemple : on ne peut pas multiplier un caractère
par un nombre entier).
Exemple: TVA = 0,17

5
N = 50
Admis = Vrai

1.2.2 Les types d’instructions

La partie principale d’un algorithme contient la suite d’instruction qui va être

traduite vers un langage de programmation. Il existe quatre types d’instruction
dont le détail est donné par la suite :

[Link] Les instructions d’entrée / sortie

Ce type d’instruction est utilisé pour interagir avec l’utilisateur, en lui permettant
d’entrer des valeurs des variables. Ainsi, le résultat des traitements et des messages
d’information peuvent être affichés à l’utilisateur via ce type d’instruction. En
réalité, il existe plusieurs périphériques et manières pour échanger des données
avec un algorithme ou un programme (via des fichiers, des bases de données, des
formulaires,. . .). Toutefois, pour se concentrer sur les principes de l’algorithmique,
on se contente par les entrées et les sorties standards, à savoir, l’écriture sur le
clavier et l’affichage sur écran. L’exploitation des autres possibilités vont être
abordées dans la matière dédiée à la programmation.

[Link] Instruction d’entrée

C’est l’instruction de lecture de données sur le périphérique d’entrée.

Exemple :

6
Lire(Taille)
Lire (x, y)

[Link] Instruction de sortie

C’est l’instruction de restitution de résultats sur le périphérique de sortie.

Exemple :
Écrire (moyenne)
Écrire (‘ entrer la taille’)
Écrire (‘le résultat est :’, max)

1.2.3 L’instruction d’affectation

Cette instruction permet d’affecter une valeur à une variable, après l’évaluation
d’un expression logique ou arithmétique. A la place d’une expression, on peut
utiliser une simple valeur ou une variable Il faut noter que le résultat de l’évaluation
de l’expression doit avoir le même type que la variable qui va le recevoir.

Structure générale :

Exemple 1 :
x ← 15.2
x←y

7
x←y+4

Exercice Quelles sont les valeurs des variables a,b et c écrites par l’algorithme
suivant ? Algorithme Affectation1
Variables :a,b,c : entier
Début a ← 10
b←a∗2
a ← a − b/2
c←b+a∗2
Ecrire (a,b,c)
Fin.

Solution :
a = 10, b = 20, c = 40
a = −5, b = 20, c = 10
a = 0, b = 20, c = 20

1.2.4 Les instructions conditionnelles

Ces instructions sont utilisées pour faire le choix entre l’exécution ou non des blocs
d’instructions suite à l’évaluation d’une condition. On en distingue trois types :

[Link] L’instruction conditionnelle simple

Ce type d’instructions permet de faire le choix entre l’exécution ou non d’un seul
boc d’instructions.

8
 Structure :

Exemple :
A←5
B ← 12
SI(B > A ∗ 2) alors B ← A
Fin Si
Ecrire(B)

[Link] L’instruction conditionnelle alternative

Ce type d’instructions permet de faire le choix de l’exécution entre deux blocs

d’instructions. Structure :

Exemple:

9
[Link] L’instruction conditionnelle de choix

Ce type d’instructions permet de faire le choix de l’exécution entre plusieurs blocs

selon la valeur d’une variable donnée.

Structure :

Exemple : Exemple:

10
1.2.5 Les instructions itératives

Les instructions itératives ou répétitives, appelées aussi communément par les

développeurs les boucles, permettent d’exécuter plusieurs le même bloc d’instructions.
On en distingue trois types :

[Link] L’instruction ‘Pour’

Dans ce type d’instructions itératives on connait à l’avance le nombre d’itérations.

En effet, on doit préciser, dans l’entête de l’instruction ‘Pour’, la valeur initiale et
la valeur finale et éventuellement le pas (lorsqu’il est différent de 1).

Structure:

VI : valeur initiale de la variable i,

VF ; valeur finale de la variable i,
V : valeur à ajouter la variable i après chaque itération (par défaut 1).

Exemple : Pour i allant de 1 à 10 faire

Ecrire (‘MSI 2’)
Fin pour

11
[Link] L’instruction ‘Tant que’

Dans ce type d’instructions itératives on ne connait pas forcement à l’avance le

nombre d’itérations. En effet, on continue la répétition de l’exécution du bloc
d’instructions tant qu’une condition est encore satisfaite.

Exemple : i = 1
Tant que (i ⩽ 10) faire
Ecrire (‘L2 MSI’)
Fin Tant que

[Link] L’instruction ‘Répéter’

Comme le cas pour l’instruction ‘Tant que’, l’instruction ‘Répéter’ ne permet pas
de connaitre forcement à l’avance le nombre d’itérations. En effet, on continue la
répétition de l’exécution du bloc d’instructions jusqu’à la satisfaction d’une con-
dition.

Structure:

Exemple : i =1 Répéter Ecrire (‘TIC 4 2023’) Jusqu’à (i ¿ 10) Remarque :

L’instruction ‘Tant que’ s’exécute zéro ou plusieurs fois, au moment où, l’instruction

12
‘Répéter’ s’exécute une ou plusieurs fois.

1.3 Les procédures et fonctions

Les procédures et les fonctions sont des abstractions d’ opérations. Chaque opération
est décrite par son nom, quelques paramètres et ce qu’elle fait. Chaque procédure
ou fonction définit une opération en fournissant : son nom, une description de ses
paramètres, une valeur facultative qu’il peut renvoyer, et une spécification de la
relation entre les paramètres, la valeur renvoyée et toute autre valeur de données .

Lors de l’utilisation de telles opérations , il n’est pas nécessaire de se référer au

corps de la procédure ou fonction qui contient des informations détaillées sur la
manière dont elle produit réellement le résultat. Une telle abstraction présente de
nombreux avantages.

1.3.1 Les procédures

Une procédure est un bloc d’instructions nommé et déclaré dans l’entête de l’algorithme
et appelé dans son corps à chaque fois que le programmeur en a besoin.

13
1.3.2 Les fonctions

Une fonction est un bloc d’instructions qui retourne obligatoirement une et une
seule valeur résultat à l’algorithme appelant. Une fonction n’affiche jamais la
réponse à l’écran car elle la renvoie simplement à l’algorithme appelant.

1.4 Notion de types de données

1.4.1 Les types primitifs(ou simples)

Les types de données primitifs sont les types de données de base, souvent fournis
par les langages de programmation de manière native. Ils représentent des valeurs
indivisibles et simples. Voici les types de données primitifs les plus courants :

– Entiers: Représentent des nombres entiers (positifs, négatifs ou zéro).

– Nombres réels ou à virgule flottante (Float, Double): Représentent des nom-

bres réels avec une partie décimale.

– Caractères (Character): Représentent un seul caractère, qui peut être une

lettre, un chiffre ou un symbole.

– Booléens (Boolean): Représentent deux valeurs logiques : vrai (true) ou faux

(false).

14
1.4.2 Types de données composés (ou complexes)

Les types de données composés sont des combinaisons de types de données primitifs
qui permettent de regrouper plusieurs valeurs dans une seule entité.

– Tableaux (Array): Une collection ordonnée d’éléments de même type, in-

dexée par des entiers.

– Chaı̂nes de caractères (String): Une séquence de caractères utilisée pour

représenter du texte.

1.4.3 Les types définis par l’utilisateur

Cette catégorie de données peut être considérée comme type composé.

[Link] Les enregistrements

Un enregistrement est une structure de donnée formée d’un ou de plusieurs éléments

(ou champs) pouvant être de types différents.

La déclaration des enregistrements se fait dans la partie de déclaration des types

comme suit :

15
[Link] Les types énumérés

Les types énumérés constituent un autre type qui peuvent être définis par l’utilisateur/programme
où il peut listez un ensemble de valeurs dans une énumération. En d’autres mots,
une énumération est une liste de valeurs définie par l’utilisateur.

La déclaration des types énumérés se fait avec une syntaxe spéciale et voici
quelques exemples :

1.5 Types abstraits de données

Les types prédéfinis sont peu nombreux. C’est pourquoi des constructeurs de
types permettent de définir des types plus complexes, et donc des structures de
données moins élémentaires. Là encore, l’implémentation précise d’un array of char
par exemple importe peu au programmeur (est-il rangé par ligne, par colonne ?),
aussi longtemps que sa manipulation satisfait à des règles précises. En revanche,
lorsque l’on veut réaliser une pile (disons de caractères) , les problèmes se posent
autrement, puisqu’il n’existe pas, en Pascal par exemple, de constructeur perme-
ttant de définir des stack of char : il est nécessaire de recourir à une structure de
données.

16
1.5.1 Définitions

Une structure de données est un moyen pour stocker et organiser les données
pour en faciliter l’accès et la modification. C’est également une implémentation
explicite d’un ensemble organisé d’objets, avec la réalisation des opérations d’accès,
de construction et de modification afférentes.
Une structure de données regroupe :

– Un certain nombre de données à gérer ;

– Un ensemble d’opération pouvant être appliquées sur ces données.

Un type abstrait de données est la description d’un ensemble organisé

d’objets et des opérations de manipulation sur cet ensemble. Ces opérations com-
prennent les moyens d’accéder aux éléments de l’ensemble, et aussi, lorsque l’objet
est dynamique, les possibilités de le modifier. Plus formellement, on peut donner
une définition mathématique d’un type abstrait : c’est une structure algébrique,
formée d’un ou de plusieurs ensembles, munis d’opérations vérifiant un ensemble
d’axiomes.

Avec ces définitions, une structure de données est la réalisation, l’implémentation

explicite d’un type de données. Décrire un type de données, le spécifier comme on
dit, c’est décrire les opérations possibles et licites, et leur effet. Décrire une struc-
ture de données, c’est expliciter comment les objets sont représentés et comment
les opérations sont implémentées. Un TDA spécifie :

– La nature et les propriétés des données ;

17
 – Les modalités d’utilisation des opérations pouvant être effectuées indépendamment
de toute représentation interne de ces données ainsi que l’implémentation des
opérations .

1.5.2 Définition d’un type abstrait de données

Les TAD ou TDA sont caractérisés par:

– Son nom ;

– Les types (domaine de valeur) qu’il manipule ;

– Les opérations sur ces données ;

– Axiomes : Ils définissent les règles logiques qui régissent les opérations du
TAD et permettent de maintenir un comportement cohérent et prévisible
dans toutes les situations

1.5.3 Avantages des types abstraits de données

On peut citer comme avantages :

– La prise en compte des types de données complexe ;

– Séparation entre les services(données + opérations) et le codage ;

– L’utilisation d’un TDA n’a pas besoin de connaı̂tre les détails de codage ;

– L’écriture des programmes modulaire.

18
Chapter 2

Structures séquentielles

2.1 Les listes linéaires chaı̂nées (LLC)

2.1.1 Notion d’allocation dynamique

L’utilisation des tableaux statiques implique que l’allocation de l’espace se fait

tout à fait au début d’un traitement, c’est à dire que l’espace est connu à la com-
pilation. Pour certains problèmes, on ne connaı̂t pas à l’avance l’espace utilisé
par le programme. On est donc contraint à utiliser une autre forme d’allocation.
L’allocation de l’espace se fait alors au fur et à mesure de l’exécution du pro-
gramme. Afin de pratiquer ce type d’allocation, deux opérations sont nécessaires
: allocation et libération de l’espace.

Exemple: Supposons que l’on veuille résoudre le problème suivant : ”Trouver

tous les nombres premiers de 1 à n et les stocker en mémoire”. Le problème réside
dans le choix de la structure d’accueil. Si on utilise un tableau, il n’est pas possible

19
de définir la taille de ce tableau avec précision même si nous connaissons la valeur
de n (par exemple 10000). On est donc, ici, en face d’un problème où la réservation
de l’espace doit être dynamique

2.1.2 Définition d’une liste linéaire chaı̂née

Une liste linéaire chaı̂née (LLC) est un ensemble de maillons, alloués dynamique-
ment, chaı̂nés entre eux. Schématiquement, on peut la représenter comme suit
:

Un élément ou maillon d’une LLC est toujours une structure (Objet composé)
avec deux champs : un champ Valeur contenant l’information et un champ
Adresse donnant l’adresse du prochain élément. A chaque maillon est associée
une adresse. On introduit ainsi une nouvelle classe d’objet : le type Pointeur
qui est une variable contenant l’adresse d’un emplacement mémoire.

Une liste linéaire chainée est caractérisée par l’adresse de son premier élément
souvent appelé tête. Nil constitue l’adresse qui ne pointe aucun maillon, utilisé
pour indiquer la fin de la liste dans le dernier maillon.

2.1.3 Représentation réelle en mémoire

Soit la liste linéaire chainée représentée par la figure suivante :

20
 La représentation réelle en mémoire de cette liste ressemble à la représentation
suivante :

2.1.4 Modèle sur les listes linéaires chaı̂nées

Dans le langage algorithmique, on définira le type d’un maillon comme suit :

Afin de développer des algorithmes sur les LLCs, on construit une machine ab-
straite avec les opérations suivantes : Allouer, Libérer, Aff Adr, Aff Val, Suivant
et Valeur définies comme suit :

– Allouer(P) : allocation d’un espace de taille spécifiée par le type de P.

L’adresse de cet espace est rendue dans la variable de type Pointeur P.

– Libérer(P) : libération de l’espace pointé par P.

21
 – Valeur(P) : consultation du champ Valeur du maillon pointé par P.

– Suivant(P) : consultation du champ Suivant du maillon pointé par P.

– Aff Adr(P, Q) : dans le champ Suivant du maillon pointé par P, on range

l’adresse Q

– Aff Val(P,Val) : dans le champ Valeur du maillon pointé par P, on range

la valeur Val.

Cet ensemble est appelé modèle.

2.1.5 Algorithmes sur les listes linéaires chaı̂nées

De même que sur les tableaux, on peut classer les algorithmes sur les LLCs comme
suit :

– Algorithmes de parcours : accès par valeur, accès par position,...

– Algorithmes de mise à jour : insertion, suppression,...

– Algorithmes sur plusieurs LLCs : fusion, interclassement, éclatement,...

– Algorithmes de tri sur les LLCs : trie par bulle, tri par fusion,...

22
Création d’une liste et listage de ses éléments

Algorithme CréerListe;
Type TMaillon = Structure
Valeur : Typeqq ;
Suivant : Pointeur(TMaillon) ;
Fin ;
Var P, Q, Tete : Pointeur(TMaillon ;
i, Nombre : entier ;
Val : Typeqq ;
Début
Tete Nil ;
P Nil ;
Lire(Nombre) ;
Pour i de 1 à Nombre faire
Lire(Val) ;
Allouer(Q) ;
Aff_val(Q, val) ;
Aff_adr(Q, NIL) ;
Si (Tete 6= Nil) Alors
Aff_adr(P, Q)
Sinon
Tete Q
Fin Si;
P Q;
Fin Pour;
P Tete ;
Tant que ( P 6= Nil) faire
Ecrire(Valeur(P)) ;
P Suivant(P) ;
Fin TQ;
Fin.

23
 cet algorithme crée une liste linéaire chaînée à partir d’une suite de valeurs données,
puis imprime la liste ainsi créée.

Recherche d’un élément dans une liste

Il s’agit bien entendu de la recherche séquentielle d’une valeur donnée.

Algorithme Recherche;
Type TMaillon = Structure
Valeur : Typeqq ;
Suivant : Pointeur(TMaillon) ;
Fin ;
Var P, Tete : Pointeur(TMaillon ;
Trouv : booleen ;
Val : Typeqq ;
Début
Lire(Val) ;
P Nil ;
Trouv Faux ;
Tant que ( P 6= Nil et non Trouv) faire
Si (Valeur(P)=Val) Alors
Trouv Vrai
Sinon
P Suivant(P)
Fin Si;
Fin TQ;
Si (Trouv=Vrai) Alors
Ecrire(Val,’Existe dans la liste’)
Sinon
Ecrire(Val,’n”existe pas dans la liste’
Fin Si;
Fin.

24
2.1.6 Listes linéaires chaînées bidirectionnelles

C’est une LLC où chaque maillon contient à la fois l’adresse de l’élément précédent et
l’adresse de l’élément suivant ce qui permet de parcourir la liste dans les deux sens.

Déclaration

Type TMaillon = Structure

Valeur : Typeqq ; // désigne un type quelconque
Précédent, Suivant : Pointeur(TMaillon) ;
Fin ;
Var Tete : TMaillon ;

Modèle sur les listes linéaires chaînées bidirectionnelles

– Allouer : Création d’un maillon.

– Libérer : Libérer un maillon.
– Valeur(P) : retourne la valeur du champ val du maillon pointé par P .
– Suivant(P) : retourne le pointeur se trouvant dans le champs suivant du maillon
pointé par P
– Précédent(P) : retourne le pointeur se trouvant dans le champs suivant du maillon
pointé par P
– Aff_Val(P,x) : Ranger la valeur de x dans le champs val du maillon pointé par P
– Aff_Adr_Précedent(P,Q) : Ranger Q dans le champs précédent du maillon
pointé par P
– Aff_Adr_Suivant(P,Q) : Ranger Q dans le champs suivant du maillon pointé par
P

25
2.2 Les piles (stacks)

2.2.1 Définition

Une pile est une liste ordonnée d’éléments où les insertions et les suppressions d’éléments
se font à une seule et même extrémité de la liste appelée le sommet de la pile.
Le principe d’ajout et de retrait dans la pile s’appelle LIFO (Last In First Out) : "le dernier
qui entre est le premier qui sort"

2.2.2 Utilisation des piles

[Link] Dans un navigateur web

Une pile sert à mémoriser les pages Web visitées. L’adresse de chaque nouvelle page
visitée est empilée et l’utilisateur dépile l’adresse de la page précédente en cliquant le
bouton "Afficher la page précédente".

[Link] Annulation des opérations

La fonction "Annuler la frappe" d’un traitement de texte mémorise les modifications

apportées au texte dans une pile.

[Link] Gestion des appels dans l’exécution des programmes

Fact(4)=4*Fact(3)=4*3*Fact(2)=4*3*2*Fact(1)=4*3*2*1=4*3*2=4*6=24

26
[Link] Parcours en profondeur des arbres

Soit l’arbre suivant :

B C

D E F G

L’algorithme de parcours en profondeur est le suivant :

Mettre la Racine dans la pile ;

Tant que (La pile n’est pas vide) faire
Retirer un noeud de la pile ;
Afficher sa valeur ;
Si (Le noeud a des fils) Alors
Ajouter ces fils à la pile
Fin Si;
Fin TQ;

Le résultat de parcours en profondeur affiche : A, B, D, E, C, F, G.

[Link] Evaluation des expressions postfixées

Pour l’évaluation des expressions arithmétiques ou logiques, les langages de programma-

tion utilisent généralement les représentation préfixée et postfixée. Dans la représentation
postfixée, on représente l’expression par une nouvelle, où les opérations viennent toujours
après les opérandes.

Exemple
L’expression ((a + (b ⇤ c))/(c d) est exprimée, en postfixé, comme suit : bc ⇤ a + cd /
Pour l’évaluer, on utilise une pile. On parcourt l’expression de gauche à droite, en exécutant
l’algorithme suivant :

27
 i 1;
Tant que (i < Longeur(Expression)) faire
Si (Expression[i] est un Opérateur) Alors
Retirer deux éléments de la pile ;
Calculer le résultat selon l’opérateur ;
Mettre le résultat dans la pile ;
Sinon
Mettre l’opérande dans la pile ;
Fin Si;
i i + 1;

Fin TQ;

Le schéma suivant montre l’évolution du contenu de la pile, en exécutant cet algorithme

sur l’expression précédente.

2.2.3 Opérations sur les piles

Les opérations habituelles sur les piles sont :

– Initialisation de la pile (généralement à vide)
– Vérification du contenu de la pile (pile pleine ou vide)
– Dépilement (POP) : retirer un élément du sommet de la pile si elle n’est pas vide
– Empilement (PUSH) : ajout d’un élément au sommet de la pile si elle n’est pas
saturée.
Exercice : Donner l’état de la pile après l’exécution des opérations suivantes sur une pile
vide :
Empiler(a), Empiler(b), Dépiler, Empiler(c), Empiler(d), Dépiler, Empiler(e), Dépiler, Dé-
piler.

28
2.2.4 Implémentation des piles

Les piles peuvent être représentés en deux manières : par des tableaux ou par des LLCs :

[Link] Implémentation par des tableaux

L’implémentation statique des piles utilise les tableaux. Dans ce cas, la capacité de la
pile est limitée par la taille du tableau. L’ajout à la pile se fait dans le sens croissant des
indices, tandis que le retrait se fait dans le ses inverse.

[Link] Implémentation par des LLCs

L’implémentation dynamique utilise les listes linéaires chinées. Dans ce cas, la pile peut
être vide, mais ne peut être jamais pleine, sauf bien sur en cas d’insuffisance de l’espace
mémoire. L’empilement et le dépilement dans les piles dynamiques se font à la tête de la
liste.
Les deux algorithmes "PileParTableaux" et "PileParLLCs" suivant présentent deux
exemples d’implémentation statique et dynamique des piles.

29
Algorithme PileParTableaux;
Var Pile : Tableau[1..n] de entier ; Sommet : Entier ;
Procédure InitPile();
Début
Sommet 0;
Fin;
Fonction PileVide() : Booleen;
Début
P ileV ide (Sommet = 0) ;
Fin;
Fonction PilePleine() : Booleen;
Début
P ileP leine (Sommet = n) ;
Fin;
Procédure Empiler( x : entier);
Début
Si (PilePleine) Alors
Ecrire(’Impossible d’empiler, la pile est pleine ! !’)
Sinon
Sommet Sommet + 1 ;
P ile[Sommet] x;
Fin Si;
Fin;
Procédure Dépiler( x : entier);
Début
Si (PileVide) Alors
Ecrire(’Impossible de dépiler, la pile est vide ! !’)
Sinon
x P ile[Sommet] ;
Sommet Sommet 1;
Fin Si;
Fin;

Début
... Utilisation de la pile ...
Fin.

30
Algorithme PileParLLCs;
Type TMaillon = Structure
Valeur : entier ;
Suivant : Pointeur(TMaillon) ;
Fin ;
Var P, Sommet : Pointeur(TMaillon) ;
Procédure InitPile();
Début
Sommet N il ;
Fin;
Fonction PileVide() : Booleen;
Début
P ileV ide (Sommet = N il) ;
Fin;
Procédure Empiler( x : entier);
Début
Allouer(P) ; Aff_Val(P,x) ;
Aff_Adr(P,Sommet) ; Sommet P;
Fin;
Procédure Dépiler( x : entier);
Début
Si (PileVide) Alors
Ecrire(’Impossible de dépiler, la pile est vide ! !’)
Sinon
x V aleur(Sommet) ; P Sommet ;
Sommet Suivant(Sommet) ; Libérer(P) ;
Fin Si;
Fin;

Début
... Utilisation de la pile ...
Fin.

31
2.2.5 Exemple d’application : Remplissage d’une zone d’une image

Une image en informatique peut être représentée par une matrice de points 0 Image0
ayant M colonnes et N lignes. Un élément Image[x, y] de la matrice représente la couleur
du point p de coordonnées (x, y). On propose d’écrire ici une fonction qui, à partir d’un
point p, étale une couleur c autour de ce point. La progression de la couleur étalée s’arrête
quand elle rencontre une couleur autre que celle du point p. La figure suivante illustre cet
exemple, en considérant p = (3, 4).

Pour effectuer le remplissage, on doit aller dans toutes les directions à partir du point p.
Ceci ressemble au parcours d’un arbre avec les noeuds de quatre fils. La procédure suivante
permet de résoudre le problème en utilisant une pile.

32
Procédure Remplir( Image : T ableaux[0..M 1, 0..N 1] de couleur ; x, y : entier ;
c : couleur);
Var c1 : couleur ;
Début
c1 Image[x, y] ;
InitPile ;
Empiler((x, y)) ;
Tant que (¬ PileVide) faire
Depiler((x,y)) ;
Si (Image[x, y] = c1 ) Alors
Image[x, y] c;
Si (x > 0) Alors
Empiler((x 1, y))
Fin Si;
Si (x < M 1) Alors
Empiler((x + 1, y))
Fin Si;
Si (y > 0) Alors
Empiler((x, y 1))
Fin Si;
Si (y < N 1) Alors
Empiler((x, y + 1))
Fin Si;
Fin Si;
Fin TQ;
Fin;

33
2.3 Les Files d’attente (Queues)

2.3.1 Définition

La file d’attente est une structure qui permet de stocker des objets dans un ordre donné
et de les retirer dans le même ordre, c’est à dire selon le protocole FIFO ’first in first out’.
On ajoute toujours un élément en queue de liste et on retire celui qui est en tête.

2.3.2 Utilisation des files d’attente

Les files d’attente sont utilisées, en programmation, pour gérer des objets qui sont
en attente d’un traitement ultérieur, tel que la gestion des documents à imprimer, des
programmes à exécuter, des messages reçus,...etc. Elles sont utilisées également dans le
parcours des arbres.

Exercice

Reprendre le parcours de l’arbre de la section [Link] (parcours en profondeur) en

utilisant une file d’attente au lieu de la pile.

2.3.3 Opérations sur les files d’attente

Les opérations habituelles sur les files sont :

– Initialisation de la file
– Vérification du contenu de la file (vide ou pleine)
– Enfilement : ajout d’un élément à la queue de la file
– Défilement : retrait d’un élément de la tête de la file

2.3.4 Implémentation des files d’attente

De même que pour les piles, les files d’attente peuvent être représentées en deux ma-
nières :
– par représentation statique en utilisant les tableaux,
– par représentation dynamique en utilisant les listes linéaires chaînées.

34
[Link] Implémentation statique

L’implémentation statique peut être réalisée par décalage en utilisant un tableau avec
une tête fixe, toujours à 1, et une queue variable. Elle peut être aussi réalisée par flot
utilisant un tableau circulaire où la tête et la queue sont toutes les deux variables.

1. Par décalage

! La file est vide si Queue = 0

! La file est pleine si Queue = n
# Problème de décalage à chaque défilement

2. Par flot : La file est représentée par un tableau circulaire

! La file est vide si T ête = Queue

! La file est pleine si (Queue + 1) mod n = T ête
# On sacrifie une case pour distinguer le cas d’une file vide de celui d’une file pleine.

Exercice Pensez à une solution qui évite le sacrifice d’une case.

35
[Link] Implémentation dynamique

La représentation dynamique utilise une liste linéaire chaînée. L’enfilement se fait à la

tête de la liste et de défilement se fait de la queue. La file d’attente, dans ce cas, peut
devenir vide, mais ne sera jamais pleine.

Les deux algorithmes FileParFlot et FileParLLCs, à la fin de cette section, présentent

des exemples d’implémentation, respectivement, statique et dynamique.

2.3.5 File d’attente particulière (File d’attente avec priorité)

Une file d’attente avec priorité est une collection d’éléments dans laquelle l’insertion
ne se fait pas toujours à la queue. Tout nouvel élément est inséré, dans la file, selon sa
priorité. Le retrait se fait toujours du début.
Dans une file avec priorité, un élément prioritaire prendra la tête de la file même s’il arrive
le dernier. Un élément est toujours accompagné d’une information indiquant sa priorité
dans la file.
L’implémentation de ces files d’attente peut être par tableau ou listes, mais l’implémen-
tation la plus efficace et la plus utilisée utilise des arbres particuliers qui s’appellent ’les
tas’.

36
Algorithme FileParFlot;
Var File : Tableau[1..n] de entier ; Tête, Queue : Entier ;
Procédure InitFile();
Début
T ête 1 ; Queue 1;
Fin;
Fonction FileVide() : Booleen;
Début
F ileV ide (T ête = Queue) ;
Fin;
Fonction FilePleine() : Booleen;
Début
F ileP leine (((Queue + 1) mod n) = T ête) ;
Fin;
Procédure Enfiler( x : entier);
Début
Si (FilePleine) Alors
Ecrire(’Impossible d”enfiler, la file est pleine ! !’)
Sinon
F ile[Queue] x;
Queue (Queue + 1) mod n ;

Fin Si;
Fin;
Procédure Défiler( x : entier);
Début
Si (FileVide) Alors
Ecrire(’Impossible de défiler, la file est vide ! !’)
Sinon
x F ile[T ete] ;
T ête (T ête + 1) mod n ;
Fin Si;
Fin;

Début
... Utilisation de la File ...
Fin.

37
Algorithme FileParLLCs;
Type TMaillon = Structure
Valeur : entier ;
Suivant : Pointeur(TMaillon) ;
Fin ;
Var P, Tête, Queue : Pointeur(TMaillon) ;
Procédure InitFile();
Début
T ête N il ; Queue N il ;
Fin;
Fonction FileVide() : Booleen;
Début
F ileV ide (T ête = N il) ;
Fin;
Procédure Enfiler( x : entier);
Début
Allouer(P) ; Aff_Val(P,x) ;
Aff_adr(P,Nil) ;
Si (Queue = Nil) Alors
T ête P;
Sinon
Aff_Adr(Queue,P) ;
Fin Si;
P;
Queue
Fin;
Procédure Défiler( x : entier);
Début
Si (FileVide) Alors
Ecrire(’Impossible de défiler, la file est vide ! !’)
Sinon
x V aleur(T ete) ; P T ête ;
T ête Suivant(T ête) ; Libérer(P) ;
Fin Si;
Fin;

Début
... Utilisation de la File ...
Fin.

38
Chapitre 3

Structures Hiérarchiques

3.1 Les arbres

3.1.1 Introduction

Dans les tableaux nous avons :

+ Un accès direct par indice (rapide)
- L’insertion et la suppression nécessitent des décalages
Dans les listes linéaires chaînées nous avons :
+ L’insertion et la suppression se font uniquement par modification de chaînage
- Accès séquentiel lent
Les arbres représentent un compromis entre les deux :
+ Un accès relativement rapide à un élément à partir de sa clé
- Ajout et suppression non coûteuses
En plus plusieurs traitements en informatique sont de nature arborescente tel que
les arbres généalogiques, hiérarchie des fonctions dans une entreprise, représentation des
expressions arithmétiques,.. etc.

3.1.2 Définitions

[Link] Définition d’un arbre

Un arbre est une structure non linéaire, c’est un graphe sans cycle où chaque nœud a
au plus un prédécesseur.

Graphe

39
 Arbre

– Le prédécesseur s’il existe s’appelle père (père de C = A, père de L = H)

– Le successeur s’il existe s’appelle fils (fils de A = { B,C,D }, fils de H= {L,M })
– Le nœud qui n’a pas de prédécesseur s’appelle racine (A)
– Le nœud qui n’a pas de successeur s’appelle feuille (E,F,G,L,J,...)
– Descendants de C={G,H,I,L,M}, de B={E,F},...
– Ascendants de L={H,C,A t}, E={B,A},...

[Link] Taille d’un arbre

C’est le nombre de nœuds qu’il possède.

– Taille de l’arbre précédent = 13
– Un arbre vide est de taille égale à 0.

40
[Link] Niveau d’un nœud

– Le niveau de la racine = 0
– Le niveau de chaque nœud est égale au niveau de son père plus 1
– Niveau de E,F,G,H,I,J,K = 2

[Link] Profondeur (Hauteur) d’un arbre

– C’est le niveau maximum dans cet arbre.

– Profondeur de l’arbre précédent = 3

[Link] Degré d’un nœud

– Le degré d’un nœud est égal au nombre de ses fils.

– Degré de (A = 3, B =2, C = 3, E= 0, H=2,...)

[Link] Degré d’un arbre

– C’est le degré maximum de ses nœuds.

– Degré de l’arbre précédent = 3.

3.1.3 Utilisation des arbres

– Représentation des expressions arithmétiques

(A+B)*c - (d+E*f)/6

41
– Représentation d’un arbre généalogique

– Codage
Exemple : coder la chaine "structure arbre"

1. Construite la table des fréquences des caractères

Caractère Fréquence Caractère Fréquence

s 1 c 1
t 2 e 2
r 4 a 1
u 2 b 1

2. Construite l’arbre des codes

3. Construire la table des codes

42
 Caractère Code Caractère Code
s 0000 c 0001
t 010 e 001
r 11 a 100
u 011 b 101

4. Coder la chaine :

"structure arbre" ) 0000 010 11 011 0001 010 011 11 001 100 11 101 11 001

3.1.4 Implémentation des arbre

Les arbres peuvent être représentés par des tableaux, des listes non linéaires ou tous
les deux :

[Link] Représentation statique

L’arbre du premier exemple peut être représenté par un tableau comme suit :

Num Information Fils 1 Fils 2 Fils 3

1 A 2 3 4
2 B 5 6 0
3 C 7 8 9
4 D 10 11 0
5 E 0 0 0
6 F 0 0 0
7 G 0 0 0
8 H 12 13 0
9 I 0 0 0
10 J 0 0 0
11 K 0 0 0
12 L 0 0 0
13 M 0 0 0

43
[Link] Représentation dynamique

Type Tnœud = Structure

Info : typeqq ;
Fils : Tableau[1..NbFils] de Pointeur(Tnœud) ;
Fin ;
Var Racine : Pointeur(Tnœud) ;

3.1.5 Modèle sur les arbres

Pour manipuler les structures de type arbre, on aura besoin des primitives suivantes :
– Allouer (N) : créer une structure de type Tnœud et rendre son adresse dans N.
– Liberer(N) : libérer la zone pointée par N.
– Aff_Val(N, Info) : Ranger la valeur de Info dans le champs info du nœud pointé
par N.
– Af f _F ilsi (N1,N2) : Rendre N2 le fils numéro i de N1.
– F ilsi (N) : donne le fils numéro i de N.
– Valeur(N) : donne le contenu du champs info du nœud pointé par N.

3.1.6 Traitements sur les arbres

[Link] Parcours des arbres

Le parcours d’un arbre consiste à passer par tous ses nœuds. Les parcours permettent
d’effectuer tout un ensemble de traitement sur les arbres. On distingue deux types de
parcours :

44
1. Parcours en profondeur
Dans un parcours en profondeur, on descend le plus profondément possible dans
l’arbre puis, une fois qu’une feuille a été atteinte, on remonte pour explorer les autres
branches en commençant par la branche "la plus basse" parmi celles non encore
parcourues. L’algorithme est le suivant :

Procédure PP( nœud : Pointeur(Tnœud));

Début
Si (nœud 6= Nil) Alors
Pour i de 1 à NbFils faire
PP(F ilsi (nœud))
Fin Pour;
Fin Si;
Fin;

Le parcours en profondeur peut se faire en deux manière :

– Parcours en profondeur Prefixe : où on affiche le père avant ses fils
– Parcours en profondeur Postfixe : où on affiche les fils avant leur père.
Les algorithmes récursifs correspondant sont les suivants :

Procédure PPPrefixe( nœud : Pointeur(Tnœud));

Début
Si (nœud 6= Nil) Alors
Afficher(Valeur(nœud)) ;
Pour i de 1 à NbFils faire
PPPrefixe(F ilsi (nœud))
Fin Pour;
Fin Si;
Fin;

45
Procédure PPPostfixe( nœud : Pointeur(Tnœud));
Début
Si (nœud 6= Nil) Alors
Pour i de 1 à NbFils faire
PPPostfixe(F ilsi (nœud))
Fin Pour;
Afficher(Valeur(nœud)) ;
Fin Si;
Fin;

Le parcours en profondeur préfixe de l’arbre du premier exemple donne :

A,B,E,F,C,G,H,L,M,I,D,J,K

Tandis que le parcours en profondeur postfixe donne :

E,F,B,G,L,M,H,I,C,J,K,D,A

2. Parcours en largeur
Dans un parcours en largeur, tous les nœuds à une profondeur i doivent avoir été
visités avant que le premier nœud à la profondeur i + 1 ne soit visité. Un tel parcours
nécessite que l’on se souvienne de l’ensemble des branches qu’il reste à visiter. Pour
ce faire, on utilise une file d’attente.

46
Procédure PL( nœud : Pointeur(Tnœud));
Var N : Pointeur(Tnœud) ;
Début
Si (nœud 6= Nil) Alors
InitFile ; Enfiler(Neuud) ;
Tant que (Non(FileVide)) faire
Défiler(N) ;
Afficher(Valeur(N)) ;
Pour i de 1 à NbFils faire
Si (F ilsi (N) 6= Nil) Alors
Enfiler(F ilsi (N)) ;
Fin Si;
Fin Pour;
Fin TQ;
Fin Si;
Fin;

L’application de cet algorithme sur l’arbre du premier exemple donne

A,B,C,D,E,F,G,H,I,J,K,L,M

47
[Link] Recherche d’un élément

Fonction Rechercher( nœud : Pointeur(Tnœud) ; Val : Typeqq) : Booleen;

Var i : entier ;
Trouv : Booleen ;
Début
Si (nœud = Nil) Alors
Rechercher Faux ;
Sinon
Si (Valeur(nœud)=Val) Alors
Rechercher Vrai ;
Sinon
i 1;
Trouv Faux ;
Tant que ((i  NbFils) et non Trouv) faire ;
Trouv Rechercher(F ilsi (Neoud), Val) ;
i i + 1;
Fin TQ;
Rechercher Trouv ;
Fin Si;
Fin Si;
Fin;

48
[Link] Calcul de la taille d’un arbre

Fonction Taille( nœud : Pointeur(Tnœud)) : entier;

Var i,S : entier ;
Début
Si (nœud = Nil) Alors
Taille 0;
Sinon
S 1;
Pour i de 1 à NbFils faire
S S + Taille(F ilsi (nœud)) ;
Fin Pour;
Taille S;
Fin Si;
Fin;

49
 3.2 Les arbres binaires de recherche

3.2.1 Définition

Les arbres binaires de recherche sont utilisés pour accélérer la recherche dans les arbres
m-aires. Un arbre binaire de recherche est un arbre binaire vérifiant la propriété suivante :
soient x et y deux nœuds de l’arbre, si y est un nœud du sous-arbre gauche de x, alors
clé(y)  clé(x), si y est un nœud du sous-arbre droit de x, alors clé(y) clé(x).
G1: Les arbres m-maires

G2: Les b-arbres

G3: Les arbres binaires

Un nœud a, donc, au maximum un fils gauche et un fils droit.

3.2.2 Implémentation des ABR

Les arbres de recherche binaires sont implémentés de la même manière que celles m-aires
(statique ou dynamique)

[Link] Représentation Statique

Num Information Fils gauche Fils droit

1 15 2 3
2 6 4 5
3 18 6 7
4 3 8 9
5 7 0 10
6 17 0 0
7 20 0 0
8 2 0 0
9 4 0 0
10 13 11 0
11 9 0 0

50
[Link] Représentation dynamique

Type TNoeud = Structure

Clé : entier ;
Info : typeqq ;
FG,FD : Pointeur(TNoeud) ;
Fin ;
Var Racine : Pointeur(TNoeud) ;

3.2.3 Modèle sur les ABR

– Allouer (N) : créer une structure de type TNoeud et rendre son adresse dans N.
– Liberer(N) : libérer la zone pointée par N.
– Aff_Val(N, Info) : Ranger la valeur de Info dans le champs info du nœud pointé
par N.
– Aff_Clé(N, Clé) : Ranger la valeur de Clé dans le champs Clé du nœud pointé
par N.
– Aff_FG(N1,N2) : Rendre N2 le fils gauche de N1.
– Aff_FD(N1,N2) : Rendre N2 le fils droit de N1.
– FG(N) : donne le fils gauche de N.
– FD(N) : donne le fils droit de N.
– Valeur(N) : donne le contenu du champs info du nœud pointé par N.
– Clé(N) : donne le contenu du champs Clé du nœud pointé par N.

51
3.2.4 Traitements sur les ABR

[Link] Parcours

De même que pour les arbres m-aire le parcours des ARB peut se faire en profondeur
ou en largeur :
– En profondeur

Procédure PP( noeud : Pointeur(TNoeud));

Début
Si (nœud 6= Nil) Alors
PP(FG(noeud)) ;
PP(FD(noeud)) ;
Fin Si;
Fin;

Le listage des éléments de l’arbre en profondeur peut se faire en :

– préfixe (préordre) : Pére FG FD,
– infixe (inordre) : FG Père FD,
– postfixe (postordre) : FG FD Père.

Procédure PPréfixe( noeud : Pointeur(TNoeud));

Début
Si (nœud 6= Nil) Alors
Ecrire(Valeur(noeud)) ;
PPréfixe(FG(noeud)) ;
PPréfixe(FD(noeud)) ;
Fin Si;
Fin;

Trace : 15 6 3 2 4 7 13 9 18 17 20

52
Procédure Infixe( noeud : Pointeur(TNoeud));
Début
Si (nœud 6= Nil) Alors
Infixe(FG(noeud)) ;
Ecrire(Valeur(noeud)) ;
Infixe(FD(noeud)) ;
Fin Si;
Fin;

Trace : 2 3 4 6 7 9 13 15 17 18 20

Procédure Postfixe( noeud : Pointeur(TNoeud));

Début
Si (nœud 6= Nil) Alors
Postfixe(FG(noeud)) ;
Postfixe(FD(noeud)) ;
Ecrire(Valeur(noeud)) ;
Fin Si;
Fin;

Trace : 2 4 3 9 13 7 6 17 20 18 15
– En largeur

53
Procédure PL( noeud : Pointeur(TNoeud));
Var N : Pointeur(TNoeud) ;
Début
Si (noeud 6= Nil) Alors
InitFile ;
Enfiler(noeud) ;
Tant que (Non(FileVide)) faire
Défiler(N) ;
Afficher(Valeur(N)) ;
Si (FG(N) 6= Nil) Alors
Enfiler(FG(N)) ;
Fin Si;
Si (FD(N) 6= Nil) Alors
Enfiler(FD(N)) ;
Fin Si;
Fin TQ;
Fin Si;
Fin;

54
[Link] Recherche

Fonction Rechercher( noeud : Pointeur(TNoeud) ; xClé : entier) : Poin-

teur(TNoeud);
Var i : entier ; Trouv : Booleen ;
Début
Si ((noeud = Nil) ou Clé(noeud)=xClé)) Alors
Rechercher nœud ;
Sinon
Si (Clé(noeud) > xClé ) Alors
Rechercher Rechercher(FG(noeud)) ;
Sinon
Rechercher Rechercher(FD(noeud)) ;
Fin Si;
Fin Si;
Fin;

[Link] Insertion

L’élément à ajouter est inséré là où on l’aurait trouvé s’il avait été présent dans l’arbre.
L’algorithme d’insertion recherche donc l’élément dans l’arbre et, quand il aboutit à la
conclusion que l’élément n’appartient pas à l’arbre (l’algorithme aboutit sur NIL), il insère
l’élément comme fils du dernier nœud visité.

[Link] Suppression

Plusieurs cas de figure peuvent être trouvés : soit à supprimer le nœud N

55
 Cas
Action
FG(N) FD(N) Exemple
Nil Nil Feuille (2,4,17) Remplacer N par Nil
Nil 6= Nil 7 Remplacer N par FD(N)
6= Nil Nil 13 Remplacer N par FG(N)
1- Rechercher le plus petit descendant à droite de
6= Nil 6= Nil 6 N soit P (7)
2- Remplacer Valeur(N) par Valeur(P) (6 7)
3- Remplacer P par FD (P) (7 13 )

3.2.5 Equilibrage

Soit les deux ARB suivants :

Ces deux ARB contiennent les mêmes éléments, mais sont organisés différemment. La
profondeur du premier est inférieure à celle du deuxième. Si on cherche l’élément 10 on
devra parcourir 3 éléments (50, 20, 10) dans le premier arbre, par contre dans le deuxième,
on devra parcourir 5 élément (80, 70, 50, 20,10). On dit que le premier arbre est plus
équilibré.
Si on calcule la complexité de l’algorithme de recherche dans un arbre de recherche binaire,
on va trouver O(h) ou h est la hauteur de l’arbre. Donc plus l’arbre est équilibré, moins
élevée est la hauteur et plus rapide est la recherche.
On dit qu’un ARB est équilibré si pour tout nœud de l’arbre la différence entre la hauteur
du sous-arbre gauche et du sous-arbre droit est d’au plus égalé à 1. Il est conseillé toujours
de travailler sur un arbre équilibré pour garantir une recherche la plus rapide possible.
L’opération d’équilibrage peut être faite à chaque fois qu’on insère un nouveau nœud où
à chaque fois que le déséquilibre atteint un certain seuil pour éviter le coût de l’opération
d’équilibrage qui nécessite une réorganisation de l’arbre.

56
3.3 Les tas (Heaps)

3.3.1 Introduction

Pour implémenter une file d’attente avec priorité, souvent utilisée dans les systèmes
d’exploitation, on peut utiliser :
– Une file d’attente ordinaire (sans priorité), l’insertion sera alors simple (à la fin) en
O(1), mais le retrait nécessitera la recherche de l’élément le plus prioritaire, en O(n).
– Un tableau (ou une liste) trié où le retrait sera en O(1) (le premier élément), mais
l’insertions nécessitera O(n).
Les tas apportent la solution à ce problème.

3.3.2 Définition

Un tas (heap en anglais) est un arbre qui vérifie les deux propriétés suivantes :

1. C’est un arbre binaire complet c’est-à-dire un arbre binaire dont tous les niveaux sont
remplis sauf éventuellement le dernier où les éléments sont rangés le plus à gauche
possible.

2. La clé de tout nœud est supérieure à celle de ses descendants.

L’élément le plus prioritaire se trouve donc toujours à la racine.

Exemple d’un tas :

57
3.3.3 Opérations sur les tas

Pour coder une file d’attente avec priorité par un tas, on doit définir les opérations
d’ajout et de retrait.

[Link] Ajout

Pour ajouter un nouvel élément dans la file avec priorité c-à-d dans le tas on doit :

1. Créer un nœud contenant la valeur de cet élément,

2. Attacher ce nœud dans le dernier niveau dans la première place vide le plus à gauche
possible (créer un nouveau niveau si nécessaire). On obtient toujours un arbre binaire
complet mais pas nécessairement un tas.

3. Comparer la clé du nouveau nœud avec celle de son père et les permuter si nécessaire,
puis recommencer le processus jusqu’il n’y ait plus d’éléments à permuter.

Exemple : soit à ajouter l’élément de priorité 15 :

[Link] Retrait

L’élément le plus prioritaire se trouve toujours à la racine, donc le retrait consiste à

lire la racine puis la supprimer. Pour ce faire on doit :

58
 1. Remplacer la valeur de la racine par la valeur de l’élément le plus à droite dans le
dernier niveau.

2. Supprimer de l’arbre cet élément (le plus à droite dans le dernier niveau), on obtient
un arbre binaire mais pas nécessairement un tas.

3. On compare la valeur de la racine avec les valeurs de ses deux fils et on la permute
avec la plus grande. On recommence le processus jusqu’il n’y ait plus d’éléments à
permuter.

Exemple :

3.3.4 Implémentation des tas

Les tas peuvent être implémentés dynamiquement exactement comme les ARB, et sont
utilisés par le même modèle.
Une représentation statique très efficace utilisant des tableaux est très utilisée en pratique,
elle consiste à ranger les éléments du tas dans un tableau selon un parcours en largeur :

59
 On remarque sur le tableau obtenu que le fils gauche d’un élément d’indice i se trouve
toujours s’il existe à la position 2i, et son fils droit se trouve à la position (2i + 1) et son
père se trouve à la position i/2. Les opérations d’ajout et de retrait sur le tas statique se
font de la même façon que dans le cas du tas dynamique. Avec ce principe les opérations
d’ajout et de retrait se font d’une manière très simple et extrêmement efficace.
Les tas sont utilisés même pour le tri des tableaux : on ajoute les éléments d’un tableau à
un tas, puis on les retire dans l’ordre décroissant.

60
Chapitre 4

Les graphes

4.1 Introduction

La notion de graphe est une structure qui permet de représenter plusieurs situations
réelles, en but de leur apporter des solutions mathématiques et informatique, tel que :
– Les réseaux de transport (routiers, ferrés, aériens · · · ),
– Les réseaux téléphoniques, électriques, de gaz,· · · etc,
– Les réseaux d’ordinateurs,
– Ordonnancement des tâches,
– Circuits électroniques,
– ···
Les arbres et les listes linéaires chaînées ne sont que des cas particuliers des graphes.

4.2 Définitions

4.2.1 Graphe

Un graphe est défini par un couple (S, A) où S est un ensemble de sommets (nœuds ou
points) et A est un sous ensemble du produit cartésien (S ⇥ S) représentant les relations
existant entre les sommets.
Exemple : S = 1, 2, 3, 4, 5, 6, 7
A = (1, 2), (1, 4), (2, 5)(3, 5), (3, 6), (4, 2), (5, 4), (6, 6)

61
4.2.2 Graphe orienté

C’est un graphe où les relations entre les sommets sont définies dans un seul sens
(exemple précédent). Dans ce cas les relations sont appelées "arcs".

4.2.3 Graphe non orienté

C’est un graphe où les relations sont définies dans les deux sens. Dans ce cas, les
relations sont appelées "arêtes".

4.2.4 Graphe étiqueté ou pondéré

C’est un graphe orienté ou non où à chaque arc ou arête correspond une valeur ou une
étiquette représentant son coût (ou distance).

62
4.2.5 Origine et extrémité

Si a = (x, y) est un arc de x vers y alors :

– x est l’origine de a et y est son extrémité
– x est un prédécesseur de y et y est un successeur de x
Si l’origine et l’extrémité d’un arc se coïncident on l’appelle une boucle (6,6).

4.2.6 Chemin

Un chemin est un ensemble d’arcs a1 , a2 , · · · , ap où Origine(ai+1 ) = Extrémité(ai ),

1ip
On dit que le chemin est de longueur p 1
Exemple : {(1, 2), (2, 5), (5, 4)}

4.2.7 Circuit

Un circuit est un chemin a1 , a2 , · · · , ap où Origine(a1 ) = Extrémité(ap )

Exemple : {(2, 5), (5, 4), (4, 2)}

4.2.8 Chaine

Une chaine est un chemin non orienté.

Exemple : {(1, 4), (5, 4), (3, 5)}

4.2.9 Cycle

Un cycle est une chaîne fermée.

Exemple : {(1, 2), (2, 5), (5, 4), (1, 4)}

4.2.10 Graphe connexe

Un graphe connexe est un graphe où pour tout couple de sommets (x, y), il existe une
chaîne d’arcs les joignant.
Exemple : Pour le couple (1, 6), il existe une chaîne d’arcs, et il n’en existe pas pour (1,7).

4.2.11 graphe fortement connexe

Un graphe fortement connexe est un graphe où pour tout couple de sommets (x, y), il
existe un chemin d’arcs les joignant.

63
Exemple : Pour (3, 2) il existe un chemin {(3, 5), (5, 4), (4, 2)} mais il n’en existe pas pour
(2, 3).

4.3 Représentation des graphes

Les graphes peuvent être représentés en deux manières : en listes d’adjacence (dyna-
mique) ou en matrice d’adjacence (statique)

4.3.1 Listes d’adjacence

Dans cette représentation, les successeurs d’un nœud sont rangés dans une liste linéaire
chainée. Le graphe est représenté par un tableau T où T [i] contient la tête de la liste des
successeurs du sommet numéro i. Le graphe (S, A) présenté au début de cette section peut
être représenté comme suit :

Les listes d’adjacence sont triées par numéro de sommet, mais les successeurs peuvent
apparaître dans n’importe quel ordre.

Type TMaillon = Structure

Successeur : entier ;
Suivant : Pointeur(TMaillon) ;
Fin ;
Var Graphe : Tableau[1..n] de Pointeur(TMaillon) ;

64
4.3.2 Matrice d’adjacence

Dans cette représentation le graphe est stocké dans un tableau à deux dimensions de
valeurs booléennes ou binaires. Chaque case (x, y) du tableau est égale à vrai (1) s’il existe
un arc de x vers y, et faux (0) sinon. Dans la matrice suivante, on représente le graphe
précédent (1 pour vrai et 0 pour faux ) :

1 2 3 4 5 6 7
1 0 1 0 1 0 0 0
2 0 0 0 0 1 0 0
3 0 0 0 0 1 1 0
4 0 1 0 0 0 0 0
5 0 0 0 1 0 0 0
6 0 0 0 0 0 1 0
7 0 0 0 0 0 0 0

Il est clair que la matrice d’adjacence d’un graphe non orienté est symétrique puisque
chaque arête existe dans les deux sens.

Var Graphe : Tableau[1..n,1..n] de booléen ;

Pour un graphe étiqueté les valeurs de la matrice peuvent être les étiquettes elles-
mêmes, avec une valeur particulière pour les arcs inexistant. Par exemple le graphe étiqueté
de l’exemple peut être représenté comme suit :

1 2 3 4 5 6 7
1 -1 10 -1 200 -1 -1 -1
2 -1 -1 -1 -1 125 -1 -1
3 -1 -1 -1 -1 22 17 -1
4 -1 96 -1 -1 -1 -1 -1
5 -1 -1 -1 12 -1 -1 -1
6 -1 -1 -1 -1 -1 3 -1
7 -1 -1 -1 -1 -1 -1 -1

65
 La représentation matricielle permet de tirer des conclusions intéressantes sur les graphes
en utilisant les calculs matriciels.

4.4 Parcours de graphes

De même que pour les arbres, il est important de pouvoir parcourir un graphe selon
certaines règles, cependant, le parcours des graphe est un peut différent de celui des arbres.
Dans un arbre, si on commence à partir de la racine on peut atteindre tous les nœuds,
malheureusement, ce n’est pas le cas pour un graphe où on est obligé de reprendre le
parcours tant qu’il y a des sommets non visités. En plus un graphe peut contenir des
cycles, ce qui conduit à des boucles infinies de parcours.
Il existe deux types de parcours de graphes : le parcours en profondeur d’abord (Depth
First Search) et le parcours en largeur d’abord (Breadth First Search).

4.4.1 En profondeur d’abord (DFS)

Le principe du DFS est de visiter tous les sommets en allant le plus profondément
possible dans le graphe.

66
Var Graphe : Tableau[1..n,1..n] de booleen ;
Visité : Tableau[1..nn] de booleen ;
Procédure DFS( Sommet : entier ;);
var i : entier ;
Début
Visité[Sommet] Vrai ;
Afficher(sommet) ;
Pour i de 1 à n faire
Si (Graphe[sommet,i] et non Visité[i]) Alors
DFS(i)
Fin Si;
Fin Pour;
Fin;

Appel :
Pour s de 1 à n faire
Si (Non Visité[s]) Alors
DFS(s)
Fin Si;
Fin Pour;

Trace : 1 2 5 4 3 6 7

La procédure DFS peut être utilisée pour divers objectifs :

– Pour vérifier s’il existe une chemin d’un sommet s1 vers un autre s2 en initialisant
le tableaux Visité à faux et en appelant DFS(s1 ) pour ce sommet. Si Visité[s2 ] est à
vrai à la fin de l’appel de DFS, alors un chemin existe entre s1 et s2 .
– Pour vérifier si un circuit contentent deux sommets s1 et s2 existe, en appelant
DFS(s1 ) pour un tableaux Visité1 et DFS(s2 ) pour un tableaux Visité2, si Visité1[s2 ]
et Visité2[s1 ] sont à Vrai après l’appel alors un tel circuit existe.
– De la même manière pour vérifier si un graphe est cyclique (contient des circuits) ou
non.
– Pour trouver les chemins minimums d’un sommet s vers tous les autres.

67
4.4.2 En largeur d’abord (BFS)

Dans ce parcours, un sommet s est fixé comme origine et l’on visite tous les sommet
situés à une distance k de s avant de passer à ceux situés à k + 1. On utilise pour cela une
file d’attente.

Var Graphe : Tableau[1..n,1..n] de booleen ;

Visité : Tableau[1..n] de booleen ;
F : File d’attente ;
Procédure BFS( Sommet : entier ;);
Var i,s : entier ;
Début
Enfiler(F,Sommet) ;
Tant que (non File_Vide(F)) faire
Defiler(F,s) ;
Afficher(s) ;
Pour i de 1 à n faire
Si (Graphe[s,i] et non Visité[i]) Alors
Enfiler(F,i) ;
Fin Si;
Fin Pour;
Fin TQ;

Fin;

Appel :
Pour s de 1 à n faire
Si (non Visité[s]) Alors
BFS(s)
Fin Si;
Fin Pour;

Trace : 1 2 4 5 3 6 7

68