Complexité et structures des
données
Elaboré par Mme Elkamel Hager
FSM de Monastir 2020-2021
1ere année Licence en Sciences de l’Informatique
Complexité et structures H. Jamoussi Elkamel , FSM 1
Plan du cours
Chapitre 1: La récursivité
Chapitre 2 : Les enregistrements
Chapitre 3 : Les pointeurs
Chapitre 4 : Les Listes chainées
Chapitre 5 : Les Types Abstraits des données
Chapitre 6 : Les piles
Chapitre 7 : Les Files
Chapitre 8 : Les Arbres
Chapitre 9 : Les Arbres binaires de recherche
Chapitre 10 : Analyse et complexité des algorithmes
H. Jamoussi Elkamel , FSM 2
Complexité et structures
1
, Chapitre 3 : Les pointeurs
Complexité et structures H. Jamoussi Elkamel , FSM 3
Introduction
• Un programme qui s’exécute utilise au moins deux zones
mémoires appelées : segment.
o Le segment de données. : qui contient les données manipulées par
le programme
o Le segment de code : contient les instructions du programme.
H. Jamoussi Elkamel , FSM 4
Complexité et structures
2
, Introduction
• Le segment de données est décomposé en trois parties :
1. La zone statique : contient des variables statiques, ie : les
variables ayants une durée de vie égale à celle du programme (c’est
le cas des variables globales).
2. La pile : sert à gérer les éléments du programme dont la durée de
vie est limitée à un bloc (c’est le cas des paramètres des appels de
fonctions/procédure, variables locales). Elle sert également à
renvoyer les résultats des fonctions.
3. Le tas (La zone dynamique) : contient les variables crées d’une
manière dynamique par le programmeur au cours de l’exécution
du programme
Complexité et structures H. Jamoussi Elkamel , FSM 5
Introduction
• Toute variable manipulée dans un programme est stockée quelque part
en mémoire centrale.
• La mémoire peut être assimilée à un tableau dont chaque case mémoire
est identifié par une « adresse ».
• Par convention, une adresse est un nombre noté en hexadécimale,
précédé par ox.
• Lors de la déclaration d’une variable, une réservation d’un
ensemble des cases mémoires est réalisée. Le nombre des cases
mémoires dépend de type de la variable.
• Pour retrouver une variable, il suffit, donc, de connaître l'adresse
mémoire à partir de laquelle la variable est stockée.
• C'est le compilateur qui fait le lien entre l'identificateur d'une variable et
son adresse en mémoire.
• Il peut être cependant plus intéressant de décrire une variable non plus
par son
Complexité identificateur mais
et structures directement
H. Jamoussi Elkamelpar son adresse.
, FSM 6
3
données
Elaboré par Mme Elkamel Hager
FSM de Monastir 2020-2021
1ere année Licence en Sciences de l’Informatique
Complexité et structures H. Jamoussi Elkamel , FSM 1
Plan du cours
Chapitre 1: La récursivité
Chapitre 2 : Les enregistrements
Chapitre 3 : Les pointeurs
Chapitre 4 : Les Listes chainées
Chapitre 5 : Les Types Abstraits des données
Chapitre 6 : Les piles
Chapitre 7 : Les Files
Chapitre 8 : Les Arbres
Chapitre 9 : Les Arbres binaires de recherche
Chapitre 10 : Analyse et complexité des algorithmes
H. Jamoussi Elkamel , FSM 2
Complexité et structures
1
, Chapitre 3 : Les pointeurs
Complexité et structures H. Jamoussi Elkamel , FSM 3
Introduction
• Un programme qui s’exécute utilise au moins deux zones
mémoires appelées : segment.
o Le segment de données. : qui contient les données manipulées par
le programme
o Le segment de code : contient les instructions du programme.
H. Jamoussi Elkamel , FSM 4
Complexité et structures
2
, Introduction
• Le segment de données est décomposé en trois parties :
1. La zone statique : contient des variables statiques, ie : les
variables ayants une durée de vie égale à celle du programme (c’est
le cas des variables globales).
2. La pile : sert à gérer les éléments du programme dont la durée de
vie est limitée à un bloc (c’est le cas des paramètres des appels de
fonctions/procédure, variables locales). Elle sert également à
renvoyer les résultats des fonctions.
3. Le tas (La zone dynamique) : contient les variables crées d’une
manière dynamique par le programmeur au cours de l’exécution
du programme
Complexité et structures H. Jamoussi Elkamel , FSM 5
Introduction
• Toute variable manipulée dans un programme est stockée quelque part
en mémoire centrale.
• La mémoire peut être assimilée à un tableau dont chaque case mémoire
est identifié par une « adresse ».
• Par convention, une adresse est un nombre noté en hexadécimale,
précédé par ox.
• Lors de la déclaration d’une variable, une réservation d’un
ensemble des cases mémoires est réalisée. Le nombre des cases
mémoires dépend de type de la variable.
• Pour retrouver une variable, il suffit, donc, de connaître l'adresse
mémoire à partir de laquelle la variable est stockée.
• C'est le compilateur qui fait le lien entre l'identificateur d'une variable et
son adresse en mémoire.
• Il peut être cependant plus intéressant de décrire une variable non plus
par son
Complexité identificateur mais
et structures directement
H. Jamoussi Elkamelpar son adresse.
, FSM 6
3
