Structures des Données

Dr Pengwendé ZONGO
UFR-ST/UNZ

 1
 Volume horaire
• CM = 24h
• TD /TP = 12h

 2
 Objectifs
Acquérir des bases de développement
méthodique de logiciels en s'appuyant sur trois
niveaux d'approche:
• Niveau fonctionnel exprimant de façon
formelle le comportement sous forme de TAD
(type abstrait de données).
• Niveau logique exprimant sous une forme
algorithmique les principes de réalisation.
• Niveau physique exprimant dans un langage
de programmation la solution retenue.
 3
 Plan du cours
A. Généralités et rappel
B. Complexité des algorithmes
C. Structures de données
D. Gestion des fichiers

 4
 A Généralités
A.1 Notion d’algorithme

Abu Ja Far Mohamed Ibn Al-rhowâ-rismî

 Mathématicien arable du 9ème siècle
Définitions
 Un algorithme est la composition d’un ensemble fini
d’étapes (tâches) dont chacune est:
Définie de façon rigoureuse et non ambiguë
Effective (= pouvant être réalisée en un temps fini)

 5
 A Généralités
A.1 Notion d’algorithme

Définitions
 Un algorithme est une procédure de calcul bien
définie, qui prend en entrée une valeur(ensemble de
valeurs) et qui produit en sortie, une valeur (ensemble
de valeurs)
 C’est une séquence d’étapes de calcul permettant de passer de la
valeur d’entrée à la valeur de sortie

 6
A.1 Notion d’algorithme
Exemple d’algorithme
 Calcul du PGCD de 2 entiers n et m
fonction pgcd(m : entier, n : entier) : entier
var r : entier
début
r reçoit n
tant que r non nul faire
soit r, le reste de la division de m par n
si r est non nul alors
m reçoit n
n reçoit r
fsi
ftq
retourne n
fin n m r
10 35 10
 Exemple avec 35 et 10 35 10 5
10 5 0
 7
 A.2 Structures de données
 Ordinateur = Système de Traitement de
l’Information
 Unité de base = le bit (0/1)
 1 octet = 8 bits
 Pb = l’information n’est pas manipulable au même
niveau par l’homme et par la machine
 Agrégation et structuration de l’information
 Construction de structures plus abstraites

 8
 A.2 Structures de données

Structure de données =
 Un ensemble structuré de données construit par
agrégation et hiérarchisation de données (ou
structures de données) plus primitives c’est-à-dire
moins abstrait.

 9
 A.2 Structures de données
Niveaux de représentation
Structures de
listes, arbres
données

enregistrement, objet

Types
tableau structurés

booléen entier réel caractère … Types primitifs

octet Représentations
machine

bit (0/1)
 10
 A.2 Structures de données
Niveaux de représentation
Représentation des systèmes complexes :
• Système complexe briser en sous-système plus
simple.
• Sous-systèmes peuvent représenter par des
structures de données connues (piles, files,
arbre,…)
Il est possible de résoudre un problème de deux
façons, en utilisant des structures de données
différentes.
Ceci implique des algorithmes différents qui sont
liés aux SD  Etude de complexité
 11
 A Généralités
A.3 Programme
Programme = Structures de données + algorithmes
La partie algorithmique d’un programme décrit les actions que
la machine doit effectuer alors que les données sont les
objets sur lesquels portent les actions du programme.
Exemple en C:
Algorithme : boucles (while, for, do..while), conditions (if,
switch), affectations (=), appels de fonctions, déclarations de
fonctions.
Données : types prédéfinis (int, float, char...), tableaux, struct,
arbres….

 12
 A Généralités
A.3 Programme
Programme = Structures de données + algorithmes

• Le pb = concevoir les structures de données de manière à

ce que :
– La mémoire utilisée soit minimale
– les algorithmes soient les plus simples et les
plus efficaces possible (2 besoins
potentiellement contradictoires)

 13
 A Généralités
A.3 Programme
Programmation structurée
Une fois le modèle de données défini, le
programme doit être écrit de manière
structurée, c'est-à-dire être décomposé en
petites entités ou sous-programmes
(fonctions en C).
Chaque sous programme réalise une tâche
précise, en ayant bien défini données
nécessaires et celle retournées.
 14
 15
 A.4 Récursivité
Introduction
Récursivité (informatique) <-> récurrence (maths)
Une démonstration par récurrence d’une propriété p(n) avec
n un entier >0:
– Propriété vraie pour une valeur initiale n0;
– Montrer que si la Propriété est vraie pour n alors vraie
pour n+1

 16
 A.4 Récursivité
Introduction
Même principe pour le programme récursif mais en sens inverse.
Ainsi, pour réaliser une tâche sur des données de taille n, on va
devoir d'abord la réaliser sur des données de taille n-1.
Appeler de façon récursive le même programme en diminuant la
taille des arguments.
L'équivalent de l'initialisation d'une preuve par récurrence est
une condition d'arrêt de l'appel récursif.
Lorsque la taille est suffisamment petite alors s’exécute la partie
non récursive du programme.

 17
A.4 Récursivité
Définition
Paradigme de calcul semblable au
raisonnement par induction.
Une fonction ou un algorithme est dit récursif lorsqu’il est
auto-référent : elle fait référence à elle-même
(directement ou indirectement)dans sa définition.

Direct. Indirect.
int fonct(…) { Int f1(…){ Int f2(…){
x = fonct(…); x=f2(…); x=f1(…);
} } }
 18
A.4 Récursivité
Motivation
Cela simplifie la résolution du problème.
Diviser pour régner : réappliquer un même traitement sur
un échantillon de données d’une taille de plus en plus petite.
► La Récursivité sert aussi pour définir des structures de
données : arbres, expressions arithmétiques,
grammaires…
► La Récursivité est utilisable dans tous les langages de
programmation modernes. En particulier, les langages
fonctionnels.

 19
A.4 Récursivité
Propriétés
Trois éléments à considérer lors de l’élaboration d’une
procédure récursive :
Expression récursive du problème :
L’ « équation » de la récursivité.
Condition d’arrêt :
Quand est-ce qu’on arrête les appels récursifs?
Convergence (vers la condition d’arrêt):
Une petite « preuve» et les conditions qui nous
assure qu’un jour on va atteindre la condition
d’arrêt.

 20
A.4 Récursivité
Propriétés
Une fonction récursive doit posséder les deux propriétés
suivantes:
 il doit exister certains critères, appelés critères d'arrêt ou
conditions d'arrêt, pour lesquels la fonction ne s’appelle
pas elle-même;
 chaque fois que la procédure s’appelle elle-même
(directement ou indirectement), elle doit converger vers
ses conditions d'arrêt.

Une fonction récursive possédant ces

deux propriétés est dite bien définie.

 21
A.4 Récursivité
Exemple La factorielle (n!)
Expression récursive du problème :
n!= n ( n –1) … (2) (1) = n (n –1)!
Condition d’arrêt:
n = 1 ou n = 0
Convergence (vers la condition d’arrêt):
Si n = 1 ou n = 0, alors on a «convergé »!
Si n > 1, alors la soustraction à l’étape suivante nous
approche de n = 1
si n est une entier non négatif ça converge!

 22
A.4 Récursivité
Exemple La factorielle (n!)

Exercice d’application: proposer un algorithme

récursif pour calculer le pgcd(m,n).
 23
 A.4 Récursivité
Itératif vs récursif
• Exemple : suite de Fibonacci
– U0 = U 1 = 1
– Un = Un-1 + Un-2
•
fonction fibo(n : entier) : entier
début
si (i = 0) ou (i = 1)
alors retourne 1
sinon retourne fibo(n-1) + fibo(n-2)
fin

 24
 A.4 Récursivité
Itératif ou récursif
Solution itérative

fonction fibo(n : entier) : entier

var un, un_1, un_2, i : entier
début
un_1 = un_2 = 1
pour i = 2 jusqu’à i = n faire
un = un_2 + un_1
un_2 = un_1
un_1 = un
fait
retourne un
fin

 25
 A.4 Récursivité
Itératif ou récursif
• Les tours de Hanoï
– Situation initiale :

– Situation finale :

– Déplacements autorisés
• Un disque à la fois
• Toujours sur un disque de dimensions supérieures (ou sur le
plateau)

 26
A.4 Récursivité
Itératif ou récursif
• Solution itérative : très complexe
• Solution récursive :
procédure déplacer(n, pile1, pile2, pile3 : entier)
– Cas trivial = déplacer 1 disque
début
si (n > 1) alors
– Cas général = déplacer
déplacer(n-1, n disques
pile, pile, pile)
•déplacer(1,
Déplacer n-1pile1,
disquespile2,
vers pile3)
l’axe
déplacer(n-1, pile, pile, pile)
auxiliaire
• Déplacer le disque n vers l’axe destination
sinon
afficher("déplacement d’1 disque de " + pile 1 +
• "vers" + pile3
fsi
fin

 27
 28
 D Structure de données
D1- structure linéaire
On appelle structure de données linéaire une structure conçue de
telle sorte que chaque fois qu’on passe du début à la fin de la
structure, on parcourt tous ses éléments, toujours dans le même
ordre.
Les listes
Une liste est Ensemble ordonné d’éléments dans lequel
on peut accéder à n’importe quel élément

Exemples : liste de passage à un examen, file d’attente à un

guichet.

 29
 D Structure de données
D1 structure linéaire
Les listes
Exemple de liste.
Liste d’éléments (entier)
• L = <8,1,5,4,6>
• L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6
• <8,1,5,4,6> ≠ <8,1,4,6,5>
Dans une liste on parle de position, donc le premier
élément est en position 1. Il ne faut pas la
confondre avec un tableau et commencer à l’indice
0.
 30
 Les listes
Quelques opérations de base sur les listes.
• |L| Quel est le nombre d’éléments ?
• L = {} ? Est-ce que la liste est vide ?
• x ∈ L ? Est-ce que l’élément x appartient à L?
• Li Avoir accès à l’élément en iième position
• x = Li ? Quelle est la position de l’élément x ?
• L +i x → L Ajouter l’élément x en iième position
• L – Li → L Supprimer l’élément en iième position
• L – x → L Supprimer la première occurrence de
l’élément x
• L = L’ ? Est-ce que les deux listes sont identiques ?
• L ⊂ L’ ? Est-ce que la liste L est incluse dans L’ ?
• → L Créer une liste vide
 31
Réalisation par tableau

 32
 Implantation d’une liste
a) réalisation par tableau
Ce premier modèle d’implantation retenu est le
plus simple : l’utilisation d’un tableau de taille
fixe.
Comme il s’agit d’un tableau statique, il faut
décider quelle est sa taille.
Modèle d’implantation
DÉBUT
TypeEl tab[TAILLE_MAX]
int taille
FIN

 33
 Implantation d’une liste
a) Implantation par tableau
Insertion d’un élément
Faire un ajout se traduit par une insertion dans
un tableau. Il faut donc, à partir de la fin jusqu’à
la position à laquelle nous devons insérer,
décaler tous les éléments d’une place vers la
droite et ajouter l’élément à la position voulue.
Complexité linéaire

 34
 Implantation d’une liste
a) Implantation par tableau
Suppression d’un élément
Pour faire la suppression d’une position, il faut
simplement décaler d’une place vers la gauche les
éléments situés à droite de la position à supprimer.
Complexité linéaire
Recherche d’un élément
Pour faire une recherche, il suffit maintenant
parcourir séquentiellement le tableau.
Complexité linéaire

 35
 Implantation d’une liste
a) Implantation par tableau
Les limites du modèle
• Lorsque la taille données dépasse celle du tableau.
• Quand il y a une grande fluctuations des données.
L‘occupation de la mémoire n’est pas optimisée
• l’opération de décalage des éléments vers la
gauche ou vers la droite cause une lenteur dans
l’exécution :
Pour contourner ce problème, il faut se tourner vers
un modèle d’implantation qui a une grande
importance dans les structures de données : le
chaînage ! 36
 Implantation d’une liste
a) Implantation par chaînage
une liste chaînée est un ensemble fini d’élément
de même type qui se suivent logiquement (mais
non physiquement).
Dans une liste chaînée, chaque élément
comporte un pointeur vers l’élément suivant.

C’est l’un des modèles d’implantation les plus

importants en informatique.

 37
 Implantation d’une liste
b) Implantation par chaînage
Le chaînage simple
le chaînage simple consiste à inclure dans chaque
élément de la liste un autre champ qui sert à pointer
l‘élément qui le suit logiquement. Les éléments d’une
liste sont souvent appelés des nœuds.

 38
 Implantation d’une liste
b) Implantation par chaînage
Le chaînage simple
• Un élément comportera donc au minimum
une partie « information » et une partie «
pointeur sur le prochain élément ».
• Le dernier élément n’a pas de successeur il a
donc l’adresse null

 39
 Implantation d’une liste
b) Implantation par chaînage
Le chaînage simple
Les nœuds d’une chaîne sont généralement
modélisés par une structure.
NOUVEAU TYPE Noeud
DEBUT
TypeEl info
Noeud *suivant
FIN
Info: contient l’information du nœud

 40
 Implantation d’une liste
b) Implantation par chaînage
Le chaînage simple
on a représenté un pointeur nommé sommet.
Il est fourni au moment de la création du premier nœud de la liste.
NOUVEAU TYPE Liste
DEBUT
Noeud *sommet
FIN
Le champ sommet est un pointeur sur la tête de la liste. Il est d’ailleurs possible
(et même utile) d’ajouter un autre champ : taille. Ce qui donnerait la longueur de
la liste et éviterait
d'avoir à la calculer à chaque fois que nous en avons besoin.

Perdre le pointeur sur une liste équivaut à perdre la liste et entraîne donc
la création d’ordures.

 41
 Implantation d’une liste
b) Implantation par chaînage
Le chaînage simple
La figure suivante montre une liste de quatre articles rangés aux
adresses physiques 100, 150, 140 et 120.

 42
 Implantation d’une liste
b) Implantation par chaînage
Le chaînage simple
La fonction d’initialisation d’une telle Liste ne fera que mettre le
pointeur sommet à NULL.
DEBUT
Liste l
l.sommet ← NULL {Initialiser le pointeur
a NULL}

 43
 Implantation d’une liste
b) Implantation par chaînage
Nombre d’éléments
Cette opération va parcourir la liste chaînée en commençant par le
sommet et compter le nombre de nœuds. Cela revient à compter
le nombre de pointeurs non NULL.
nbElementsListe
DEBUT
Courant ← l.sommet {le pointeur courant pour se déplacer
dans la liste }
Cpt ← 0 {Pour compter le nombre d’elements}
TANT QUE courant != NULL
DEBUT
cpt ← cpt + 1
courant ← courant->suivant
FIN
{A: cpt contient le nombre d’elements de la Liste l}
 44
b) Implantation par chaînage
Insertion d’un élément.
Il suffit de changer les valeurs de quelques pointeurs.
Considérez cet exemple :

Inséré « Marc » entre le deuxième et le troisième nœuds.

On suppose que le nouveau nœud occupe déjà la case mémoire
d'adresse 110. Le lien du second
article est changé de 140 à 110. Le lien du nouvel article reçoit la
valeur 140.
Comment Ajouté marc au début de la liste?
 45
b) Implantation par chaînage
Insertion d’un élément
ajoutListe(l,x,pos)
DEBUT
Nouveau ← nouveauNoeud(x) {nouveau est différent de NULL, sinon PAM}
SI pos = 1 ALORS FAIRE
DEBUT
nouveau-> suivant ← l.sommet
l.sommet ← nouveau
FIN
SINON
DEBUT
precedent ← l.sommet
REPETER pour i e [2, pos[
DEBUT
prededent ← prededent->suivant
FIN {precedent est le noeud en pos-1}
nouveau -> suivant ← precedent->suivant
precedent -> suivant ← nouveau
 46
b) Implantation par chaînage
Suppression d’un élément
La suppression d'un article se fait de façon similaire.

Si l’on avait éliminé le dernier article (René), il aurait fallu

donner la valeur NULL au pointeur de Paul. Si l’on avait éliminé
le premier article (Alain), il aurait fallu donner à sommet la
valeur 150.

 47
b) Implantation par chaînage
Suppression d’un élément
enleverPosListe
DEBUT
SI pos = 1 ALORS FAIRE
DEBUT
aSupprimer = l.sommet
l.sommet = aSupprimer->suivant
FIN
SINON
DEBUT
precedent = l.sommet {precedent est le noeud en pos-1}
REPETER pour i e [2, pos[
DEBUT
prededent = prededent->suivant
FIN
aSupprimer = precedent->suivant
precedent->suivant = aSupprimer->suivant
FIN
LIBERER aSupprimer {La fonction FREE en C}
 48
 D1 structure linéaire
Les piles
Une pile est une structure linéaire qui se caractérisent
par la manière d'insertion et d'extraction d'un élément.
Les opérations d'insertion et de retrait se font toujours
à la même extrémité de la pile.
les éléments ne peuvent pas être retirés dans un ordre
différent de celui de leur insertion dans la pile.

Ce principe est appelé en anglais LIFO (last in, first

out)

 49
D1 structure linéaire
Les piles
Exemple de traitement utilisant les piles
Traitement des structures emboîtées (par exemple,
analyse d'un programme : boucles imbriquées,
procédures locales, parcours d'arbres, récursivité,
etc.) pour lesquelles il faut que les sous-structures
soient traitées avant la structure qui les contient.

 50
Implantation d’une pile
Les opérations sur les piles
• Ajouter un nouvel élément (empiler)
• Enlever un élément (dépiler)
• Regarder le sommet de la pile ( top)
• Est-ce que la pile est vide ?
• Est-ce que l’élément x appartient à la pile ?
Il existe d’autres opérateurs

 51
 Implantation d’une pile
Implantation par tableau
Le modèle d’implantation par tableau est le plus simple.
Le meilleure choix de gestion du flux est d’ajouter toujours à la
fin du tableau, autrement dit d’empiler et de dépiler toujours à
la fin du tableau.
NOUVEAU TYPE Pile
DEBUT
TypeEl tab[TAILLE_MAX]
int nbElements
FIN

 52
 Implantation d’une pile
empiler
DEBUT
{A : p.nbElements < TAILLE_MAX, sinon Pile Pleine}
p.tab[nbElements] = x
p.nbElements = p.nbElements + 1
FIN
Encore une fois, le problème avec ce modèle d’implantation, c'est la taille fixe
du tableau. Il est possible d’utiliser plutôt un tableau dynamique.
Une autre façon de faire l’implantation de la pile est d’utiliser le chaînage de
structures. Quel
est le type de chaînage le plus approprié parmi tous ceux que nous avons
déjà rencontrés ?

 53
 Implantation d’une pile
Implantation chaînage
NOUVEAU TYPE Noeud
DEBUT
TypeEl info
Noeud *suivant Empiler(p,x)
FIN DEBUT
nouveau = nouveauNoeud(x)
NOUVEAU TYPE Pile nouveau->suivant = p.sommet
DEBUT p.sommet = nouveau
Noeud *sommet FIN
FIN

 54
 Implantation d’une pile
Exercice d’application
Des parenthèses de différentes formes peuvent être présentes
dans une expression mathématique : ' ( ) ' , '{ }' et ' [ ]‘ <>
Pour que l'expression soit correcte, il faut que les parenthèses
soient bien équilibrées, c’est-à-dire qu'une parenthèse ouverte
par '[' doit être fermée par ']' et pas par ')' ou '}'.
L’expression 3*(2-[4 / (2 +x)] * y) est bien équilibrée au niveau
des parenthèses.
A l’aide d’une pile proposer un algorithme qui vérifie l’équilibre
des parenthèses d’une expression mathématique.

 55
 D1 structure linéaire
Les files
Cette structure linéaire se caractérise par un comportement
particulier en ce qui concerne l'insertion et l'extraction d'un
élément : l'insertion se fait à une extrémité et l'extraction à
l'autre extrémité.
En anglais, on parle de FIFO (First In First Out)
Dans une file d'attente l'ordre d'arrivée des éléments est
préservé.

 56
 D1 structure linéaire
Les files
Applications
• L'exécution des programmes dans un système multi-usagers.
Puisque l'ordinateur n'a qu'une unité centrale de traitement
(CPU), qu'une mémoire et qu'il ne peut traiter qu'un
programme à la fois, il a fallu créer une file d'attente.
• processus d’impression pour une imprimante partagée dans
un laboratoire. Un document envoyé pour impression est
ajouté à une file d’attente.
• Etc

 57
 D1 structure linéaire
Les files
Quelques opérations sur les files
• Ajouter un nouvel élément (enfiler)
• Enlever un élément (défiler)
• Regarder le premier élément de la file (sans le défiler)
• Regarder le dernier élément de la file
• Est-ce que la file est vide ?
• Est-ce que l’élément x appartient à la file ?

 58
 Implantation d’une file
Implantation par tableau
On peut réaliser une file par l'entremise d'un tableau à
une dimension et deux pointeurs (dans ce cas les indices
du tableau), tete qui vise la tête de la file et queue qui
vise la queue, le dernier élément de la file.
Exemple: une file F implémentée à l’aide d’un tableau de
T de taille 8.

 59
 Implantation d’une file
Implantation par tableau
On peut épuiser la mémoire et ce, même si la
file n'est jamais très chargée. Cela s'est produit parce que le déplacement des
pointeurs se fait toujours dans le même sens et, entraînant plus tard un
débordement du tableau.
Exemple

 60
 Implantation d’une file
Implantation par tableau

Pour éviter ce problème, on rend le tableau circulaire.

on fait un calcul modulo n (n est la longueur de la file). Lorsque nous voulons
avancer un pointeur
d'une position, on fait : p = p mod n +1

 61
 Implantation d’une file
Implantation par tableau
Dans le précédent exemple, on aurait eu:

Attention à ce que les pointeurs de tête et de queue ne se dépassent pas .

Comment vérifier que la file est pleine?

 62
 63
D2 Structures arborescentes (Arbre)
Introduction
La structure d'arbre est une structure de données
primordiale en informatique.
Diverses variantes sont utilisées : arbres binaires, B-arbres,
arbres AVL, forêts d'arbres ...
Un arbre est une structure homogène dont chaque
élément, appelé nœud, contient de
l'information et plusieurs liens (pointeurs) vers des
élément s du même type appelés nœuds fils ou
successeurs.

 64
Synthèse sur les structures de données : Définitions
• Algorithme = structuration des tâches (données
entrées + instructions + données sorties)
• Contexte des structures de données :
 Format des données
 Stockage des données Structures de données

 Échange des données. Primitive

• Entier Non primitive
• Types de structures des données :
•
•
Décima
Booléens
• Décimaux, etc.

Séquentiel : Non
• Tableau, séquentiel :
• Pile, • Arbre
• file • Etc.
Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : Pile
Exemples d’applications basées sur le modèle des piles :
• Bouton Précédent d’une fenêtre empiler depiler

• Bouton Annuler
Mode de traitement : LIFO Méthodes
Concept de Sommet : empiler()
• Là où l’on insert un élément depiler()
• Si Sommet != 0 Alors
estVide()
Pile Non vide
estPleinne
FinSi Sommet

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : Pile
 Implantation en C
Définition du type struct
# ifndef PILE_H_INCLUDED
# define PILE_H_INCLUDED
typedef struct {
int sommet;
int taille;
int pile[50];
}myPile;

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : Pile
 Implantation en C
Définition de la méthode estVide
int estVide(myPile P){
if(P.sommet==0){
return 1; }
else{
return 0;}
}

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : Pile
 Implantation en C
Définition de la méthode estPleine
int estPleine(myPile P){
return P.sommet == P.taille;
}

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : Pile
 Implantation en C
Définition de la méthode empliler
void empiler(myPile *P, int V){
P->pile[P->sommet++] = V;
}
Définition de la méthode depliler
int depiler(myPile *P){
return P->pile[P->sommet--];
}

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : Pile
 Implantation en C
Définition du programme principal main
# include <studio.h>
# include <stdlib.h>
# include "pile.h"
int main(){
myPile P1, P2; int n; P1.sommet=0;
print("Donner la taille max de la pile 1 : ");
scanf("%d", &P1.taille);
while(!estPleine(P1)){
Print("Donner une valeur : ");
scanf("%d", &n);
empiler(&P1, n);
}

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : File
Exemples d’applications basées sur le modèle des piles :
• Bouton Impression dans un réseau
• Processus au niveau du processeur
Mode de traitement : FIFO

enfiler defiler
Queue tete

taille
Méthodes
Principes : enfiler()
• File est vide si tete = Queue defiler()
• File est pleine si Queue = taille estVide()
estPleine

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : File
 Implantation en C
Définition du type struct
# ifndef FILE_H_INCLUDED
# define FILE_H_INCLUDED
typedef struct {
int tete;
int queue;
int taille;
int file[50];
}myFile;

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : File
 Implantation en C
Définition de la méthode estVide
int estVide(myFile F){
return F.tete == F.queue;
}

Définition de la méthode estPleine

int estPleine(myFile F){
return F.queue == F.taille;
}

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : File
 Implantation en C
Définition de la méthode enfiler
void enfiler(myFile *F, int V){
F->file[F->queue++] = V;
}
Définition de la méthode defiler
int defiler(myFile *F){
return F->file[F->tete--];
}

Dr Pengwendé ZONGO
UFR/ST
Synthèse sur les structures de données : File
 Implantation en C
Définition du programme principal main
# include <studio.h>
# include <stdlib.h>
# include "file.h"
int main(){
myFile f1; int V; f1.queue=f1.tete=0;
print("Donner le nombre des éléments de la file 1 : ");
scanf("%d", &f1.taille);
while(!estPleine(f1)){
Print("Donner une valeur : ");
scanf("%d", &V);
enfiler(&f1, V);
}

Dr Pengwendé ZONGO
UFR/ST
D2 Structures arborescentes (Arbre)
introduction
Exemples:
• Représenter les distances de Ouaga à toutes les
autres villes du Burkina.
• Représenter votre arbre généalogique à partir de
votre grand-père.

 78
D2 Structures arborescentes (Arbre)
Introduction
Expressions arithmétiques
Un arbre arithmétique permet de représenter des expressions
arithmétiques. Il est constitué soit de feuilles qui sont des
entiers, des nœuds qui contiennent un opérateur arithmétique (
+, −, ∗ ou /), un sous arbre gauche et un sous arbre droite.

 79
D2 Structures arborescentes (Arbre)
Terminologie
Un arbre (orienté ou enraciné) est un ensemble
de nœuds muni d’une relation de « parenté » qui
vérifie les conditions suivantes :
1. Il y a un seul nœud qui n'a pas de
prédécesseur (père). Ce nœud s'appelle
racine.
2. Tous les nœuds, sauf la racine, n'ont qu'un
seul père (prédécesseur).
3. Il existe un chemin unique de la racine à
chaque nœud.
 80
D2 Structures arborescentes (Arbre)
Terminologie
Racine

Nœuds
internes

père(O) = {N}
père(R) = {} Feuilles
fils(M) = {A,B} ou
fils(B) = {} nœuds externes

 81
Terminologie
Les nœuds terminaux, qui n’ont pas de fils, sont
appelés feuilles ou nœuds externes.
Les nœuds qui ne sont pas des feuilles ou
racine sont appelés nœuds internes.
Le prédécesseur d'un nœud s'appelle le père ou
l’ancêtre direct du nœud.
Le successeur est appelé le fils ou le
descendant direct du nœud.
Un nœud peut avoir plusieurs fils.

 82
Terminologie
Le nombre de fils d’un nœud n dans un arbre
est appelé le degré de n.

Un arbre ordonné est un arbre dont dans lequel

les fils de chaque nœuds sont ordonnées. En
d’autres termes: si nœuds à k fils, il y a un 1er
fils, 2e fils … Kième fils.

 83
Terminologie

Un chemin de longueur k entre nœuds u et v

d’un arbre est la suite de nœuds {n0, n1, ..., nk}
telle que n0=u, nk=v et pour tout i appartenant à
l’intervalle [1..p], ni-1 = père(ni)

Une branche de l’arbre est un chemin de la

racine à l’une de ses feuilles.

 84
D2 Structures arborescentes (Arbre)

Terminologie

Le bord gauche de l’arbre est le plus long chemin

depuis la racine en ne suivant que les fils gauches

Le bord droit de l’arbre est le plus long chemin

depuis la racine en ne suivant que les fils droits

 85
D2 Structures arborescentes (Arbre)
Terminologie
Soit A arbre et n nœud de A.
Un sous-arbre d’arbre ayant pour racine n est la
partie de l’arbre constitué des descendant de n.

Le(s) sous arbres d’un nœud x sont le(s) sous-

arbes dont les racines sont des fils de x.

 86
A arbre, x nœud de A
SA(x) = sous-arbre de A qui a racine x
A = SA( racine(A) )

2 3 4

SA (2) 5 6 7 8
SA (3)
SA (4) 9 10

SA(2), SA(3) et SA( 4) sont des sous-arbres de 1

 87
Terminologie
Hauteur
• La hauteur d'un nœud est le nombre
maximum de liens qu'il faut parcourir pour
aller à une feuille.
• La hauteur d’un arbre est la hauteur de sa
racine.
Définition récursive
Soit A arbre et n nœud de A
hA(n) = 0 si n = feuille
1+max{ hA(e), où e fils de n }
 88
Terminologie
Hauteur
Soit A un arbre de 10 nœuds

Hauteur 3 1

hA (8) = 0 2 3 4
hA (7) = 1
hA (3) = 2 5 6 7 8
h(A) = hA (1) = 3
9 10

 89
Parcours

Il y a deux catégorie de parcours :

parcours en profondeur (branche après branche)
– préfixe,
– suffixe,
– symétrique
parcours en largeur (niveau après niveau)

 90
 Parcours
1
Arbre non vide
A = (r, SA1, SA2, …, SAk) 2 3 4
SAi = sous-arbre de r
5 6 7 8

Parcours préfixe : priorité au père 9 10

Cette visite se fait dans ce sens
• Visiter la racine r;
• Visite les sous arbres SA1, SA2, …, SAk

P(A) = (r).P(SA1). ... .P(SAk) : (1, 2, 5, 6, 3, 7, 9, 10, 4, 8)

 91
 Parcours
1
Arbre non vide
A = (r, SA1, SA2, …, SAk) 2 3 4
SAi = sous-arbre de r
5 6 7 8

Parcours suffixe : priorité aux fils 9 10

• Visite les sous arbres SA1, SA2, …, SAk
• Visiter la racine r;

S(A) = S(SA1). ... .S(SAk).(r) (5, 6, 2, 9, 10, 7, 3, 8, 4, 1)

 92
 Parcours
1
Arbre non vide
A = (r, SA1, SA2, …, SAk) 2 3 4
SAi = sous-arbre de r
5 6 7 8

Parcours symétrique (ou interne ) 9 10

• Visite le sous arbres SA1
• Visiter la racine r;
• , SA2, …, SAk
I(A) = I(A1).(r).I(A2). ... .I(Ak) (5, 2, 6, 1, 9, 7, 10, 3, 8,
4)

 93
 Parcours

Arbre non vide

A = (r, SA1, SA2, …, SAk) 1
SAi = sous-arbre de r
2 3 4

5 6 7 8

 Parcours en largeur ou hiérarchique 9 10

H(A) = (r, x1, …, xi, xi+1, ... xj, xj+1, ..., xn)
 nœuds de niveau 0, 1, 2, ...
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

 94
 95
Arbres binaires
Un arbre de degré 2 est appelé arbre binaire.
Un arbre binaire est un arbre orienté qui vérifie les
conditions suivantes :
• Chaque fils d'un nœud est soit fils gauche, soit
fils droit.
• Aucun nœud n'a plus d'un fils gauche ni plus
d'un fils droit.

Un arbre de degré n supérieur à 2 est appelé

arbre n-aire.
 96
 Arbres binaires

Définition récursive
Un arbre binaire non vide A = <r, A1, A2>
– r = nœud racine,
– A1 = arbre binaire, sous-arbre gauche de r,
– A2 = arbre binaire, sous-arbre droit de r,
• Un arbre binaire qui ne contient aucun nœud est appelé arbre vide
• Si A1 n’est pas vide sa racine est fils gauche de r, de même si A2 n’est
pas vide sa racine est fils droit de r.
• Si un sous-arbre est vide on dit que le fils est absent ou manquant

 97
 Arbres binaires
Préfixé: 9,6,3,1,4,8,7,12,11,15,19
Exemple:
Racine

SAG SAD
Fils g.
de r
Fils d.
de r

Postfixé: 1,4,3,7,8,6,11,19,15,12,9
Infixé: 1,3,4,6,7,8,9,11,12,19,15  98
Arbres binaires

 99
Arbres binaires

Exercice d’application:
Dessiner tous les arbres binaires ayant les
nœuds a, b, et c avec a pour racine.

 100
 Arbres binaires

Parcours ou visites
Accéder à l'information contenue dans les nœuds
d'un arbre pour
• faire une recherche,
• compter des éléments,
• faire une insertion,
• faire une suppression,
• …
Parcourir ou visiter les nœuds

 101
 Arbres binaires

Parcours ou visites
Dans le cas d'une structure linéaire, le choix est
facile : on y passe en ligne droite, du début à la fin.
Cependant, dans les arbres comme dans les
graphes, la ligne droite n'existe pas. Alors,
comment peut-on passer par tous les nœuds ?

 102
 Arbres binaires

Parcours ou visites
Deux types de parcours
– En largeur d’abord
– En profondeur d’abord
–Préfixé (ordre de priorité au père)
–Postfixé (ordre de priorité aux fils)
–Infixé (l'ordre de priorité symétrique)

 103
 Arbres binaires

Parcours en profondeur
• Ces trois ordres viennent de la définition
récursive d’un arbre : un arbre est vide ou est une
racine avec un arbre à gauche et un arbre à
droite.
• Il y a donc trois arbres et c’est l’ordre de visite de
ces trois arbres qui change.

 104
 Arbres binaires

Parcours Préfixé (ordre de priorité au père)

Cet parcours se fait dans ce sens :
– Visiter la racine r;
– Visiter selon la priorité au père les sous arbres SAG, SAD de
r;
Parcprefixe(Racine)
Début
SI Racine ≠ Nul ALORS FAIRE
debut
Traiter Racine
Parcprefixe (filsGauche)
Parcprefixe(filsDroit)
fin
Fin

 105
 Arbres binaires

Parcours Postfixé (ordre de priorité au fils)

Cet parcours se fait dans ce sens :
– Visiter les sous arbres SAG, SAD de r selon la priorité au fils ;
– Visiter la racine r;
Parcpostfixe(Racine)
Début
SI Racine ≠ Nul ALORS FAIRE
debut
Parcpostfixe (filsGauche)
Parcpostfixe(filsDroit)
Traiter Racine
fin
Fin

 106
 Arbres binaires

Parcours infixé (ordre de priorité symétrique)

Cet parcours se fait dans ce sens :
• Visiter selon la priorité symétrique le fils gauche de r;
• Visiter la racine r;
• Visiter selon la priorité symétrique le fils droit de r.
Parcinfixe(Racine)
Début
SI Racine ≠ Nul ALORS FAIRE
debut
Parcinfixe (filsGauche)
Traiter Racine
Parcinfixe(filsDroit)
fin
Fin  107
Arbres binaires

Implantation Par tableau

On crée une tableau de N éléments, un
élément par nœud, et ensuite on fait une
correspondance des nœuds de l'arbre sur les
éléments du tableau.
Pour ce faire, on identifie chaque nœud de
l'arbre :
 La racine a comme identificateur 1; 0
 Un fils gauche a comme identificateur 2D; 2D+1
 Un fils droit a comme identificateur 2D + 1; 2D+2
où D est l'identificateur du père.
 Arbres binaires

Implantation Par tableau

Si on ne connaît pas exactement la taille de
l’arbre, on ajouter une marge de sécurité dans
l'allocation de la mémoire.

Exemple d'un arbre de 15 nœuds :

 Arbres binaires

Implantation Par tableau

L’arbre par excellence à implanter dans un

tableau est l’arbre binaire complet. Un arbre
binaire complet remplit tout le tableau.
 Arbres binaires

Implantation Par tableau

Les avantages de ce modèle d’implantation
sont surtout au niveau de la manipulation de
l’arbre : il s’agit de la manipulation des indices.
 Pour trouver le père est simple. Il suffit de
prendre la partie entière de l’indice diviser
par 2 et nous avons son indice dans le
tableau.
 Avec le modèle d’implantation dynamique,
retrouver le père est un peu plus compliqué
que cette opération:
indiceDuPereDe(i) = [i/2]
Arbres binaires

Exercices d’application.
Simuler tous les parcours sur cette arbre
binaire.

 112
Gestion des fichiers

 113
Gestion de fichiers
Introduction
Nous n’avons manipulé que des données en
mémoire jusqu’à présent, ce qui nous
empêchait de les stocker de manière
permanente.
Maintenant nous allons voir comment conserver
des informations de manière permanente à
l’aide des fichiers.

 114
Gestion de fichiers
Introduction
Pour pouvoir manipuler (lire/ecrire) un fichier un
programme a besoin d'un certain nombre
d'informations : l'adresse de l'endroit de la
mémoire où se trouve le fichier, la position de la
tête de lecture, le mode d'accès au fichier (lecture
ou écriture).
• Ces informations sont rassemblées dans une
structure FILE , est défini dans stdio.h.
Une objet de type FILE * est appelé flot de
données (en anglais, stream).
 115
Gestion de fichiers
Introduction
• Pour manipuler un fichier, on utilise une variable
pointeur de type « FILE ».

FILE *p_fichier;
La variable « p_fichier » contiendra l’adresse en
mémoire-tampon du début du fichier.

 116
Gestion de fichiers
Introduction
Trois flots standard peuvent être utilisés en C sans
qu'il soit nécessaire de les ouvrir ou de les fermer :
• stdin (standard input) : unité d'entrée (par
défaut, le clavier) ;
• stdout (standard output) : unité de sortie (par
défaut, l'écran) ;
• stderr (standard error) : unité d'affichage des
messages d'erreur (par défaut, l'écran).

 117
Gestion de fichiers
Ouverture de fichiers
La fonction fopen
Cette fonction ouvre un fichier et renvoie un
pointeur FILE sur le fichier ouvert. fopen est définie
dans le fichier stdio.h par :
FILE *fopen (char *nom, char *mode)
• nom est une chaîne de caractères contenant le
nom du fichier sur la mémoire permanente

 118
Gestion de fichiers
Ouverture d’un fichier
• mode chaîne de caractère qui désigne le mode
d’accès du fichier.
– “r” ( read) : lecture (si le fichier existe)
– “w” (write) : écriture (le fichier est écrasé s’il existe et
s’il n’existe pas, il est crée)
– “a” (append) : écriture à la fin d’un fichier existant. Le
fichier peut ne pas exister, dans ce cas, il sera créé. Si le
fichier existe déjà, les nouvelles données seront
ajoutées à la fin du fichier précédent.

 119
Gestion de fichiers
Ouverture d’un fichier
Exemple
FILE *fp, *fl;
fp = fopen(“C:\\Users\\Documents\\myData.txt”, ”w”);
fl = fopen(“info.txt”, ”r”);

– Ouverture en écriture du fichier myData.txt dans le

dossier Documents.
– Ouverture en mode lecture du fichier info.txt dans le
répertoire courant.

 120
Gestion de fichiers
Fermeture d’un fichier avec fclose
La fonction fclose permet de fermer le flot qui a été
associé à un fichier par la fonction fopen. Sa
définition dans le fichier stdio.h est.
int fclose(FILE *pfichier) ;

Il faut toujours fermer un fichier après l’avoir

utilisé Afin de libérer la mémoire

 121
Gestion de fichiers
Écriture‐lecture de fichiers textes
• La fonction fprintf, analogue à printf, permet
d'écrire des données dans un fichier. Le
prototype de la fonction est:
int fprintf(FILE *fich, char *format,…) ;
Les spécifications de format sont ici les mêmes
que celles de printf .
Exemple // a est une variable entier
fprintf(fp, “%d”, a);

 122
#include <stdio.h>
int main(){
int a; float b;
a=5; b = 8.34;
// Déclaration d’un pointeur FILE qui recevra l’adresse
du fichier ouvert
FILE *monfichier;
/* ouverture du fichier en mode écriture SYNTAXE
GENERALE
File *fopen(char *nom, char * mode ) */
monfichier = fopen("mesDonnees.txt","w");

 123
 if (monfichier != NULL){
printf("Success! Fichier Ouvert\n");
//Ecriture du fichier a l’aide du flot monfichier
fprintf(monfichier,"%d\n", a);
fprintf(monfichier,"%f\n", b);
fclose(monfichier); //fermeture du fichier
}
else {
printf("Echec d'ouverture du Fichier\n");
}
return 0;
}

 124
Gestion de fichiers
Écriture‐lecture de fichiers textes
• La fonction fscanf, analogue à scanf, permet de
lire des données dans un fichier. Le prototype
de la fonction est:
int fscanf(FILE *fich, char *format,…) ;
Les spécifications de format sont ici les mêmes
que celles de scanf.
Exemple: //a est un entier
fscanf(fichier,"%d",&a);

 125
#include<stdio.h>
#include<stdlib.h>
int main() {
FILE *fp;
int a;
float b;
fp = fopen("data.txt", "r");
if(fp == NULL) {
printf("Erreur Ouverture du fichier\n");
exit(1);
}
 126
/*lecteur selon le format des données dans le
fichier Data.txt, EOF est la valeur retournée par
fscanf pour indiquer la fin du fichier.*/
while( fscanf(fp, " %d %f \n" , &a, &b) != EOF ) {
printf("%d %f\n", a,b);
}
fclose(fp);
return 0;
}

 127
TP
Déclarer un type qui permettent de stocker un
étudiant caractérisé par son nom, prénom, sa date
de naissance.
• Ecrire une fonction LireEtudiant() qui permet de
lire au clavier et retourner les informations d’un
étudiant.
• Dans la fonction main(), l’utilisateur saisie d’abord
le nombre d’étudiants puis entre les données.
• Faire une fonction WriteFile() qui enregistre les
données étudiants lues dans un fichier
donnees.txt. Chaque ligne du fichier contiendra
les informations d’un étudiant.
 128