Josky AIZAN Structure de données
Structures de données
1
Josky AIZAN Structure de données
Table des matières
I- LES LISTES CHAINEES ....................................................................................................................... 4
DEFINITIONS .................................................................................................................... 4
DECLARATION ET UTILISATION ..................................................................................... 4
I-1-PROCEDURE CréerListe (Permet de créer une liste chainée de n entiers) .................. 5
I-2- PROCEDURE Affichage(Permet d’afficher les éléments de la liste) ............................ 5
I-3- FONCTION Recherche (Permet de rechercher un element x dans la liste) ................. 6
I-4- PROCEDURE AjouterTete (Permet d’ajouter une tete de la liste) ............................... 7
I-5- PROCEDURE Supprimer (Permet de supprimer un element de la liste) ...................... 7
I-6- PROCEDURE Inverse (Permet d’inverser une liste) .................................................... 8
I-7- PROCEDURE TriBulle (Permet de trier une liste chainee selon le principe de tri a
bulle) .................................................................................................................................. 9
I-8- PROCEDURE Concatener (Permet de concatener deux listes chainees L1 et L2
d’entiers dans une troisieme liste L3) ................................................................................10
I-9- PROCEDURE Fusion (Permet de fusionner deux listes triée L1 et L2 dans la liste L1)
.........................................................................................................................................11
I-10- PROCEDURE SupprimeDoublons(Permet de Supprimer les doublons dans une liste
chainee) ............................................................................................................................12
I-11- FONCTION Palindrome (Permet de vérifier si une liste est palindrome ou non) .......13
II- LES PILES ........................................................................................................................................ 13
II-1- DEFINITION ..............................................................................................................13
II-2- CREATION DE LA STRUCTURE D’UNE PILE..........................................................14
II-3- DECLARATION D’UNE VARIABLE DE TYPE PILE ..................................................14
II-4- PROCEDURE InitialiserPile(var P : Pile) (permet de créer une pile vide) .....................14
II-5- FONCTION EstPileVide(P: Pile) (permet de vérifier si une pile est vide)......................14
II-6- PROCEDURE Empiler(x : Entier ; var P : Pile) (permet d’ajouter l’élément x au sommet
de la pile) ..........................................................................................................................15
II-7- PROCEDURE Dépiler (var x : Entier ; var P : Pile) (permet de supprimer le sommet de la
pile et de le mettre la valeur dans la variable x) ................................................................15
III- LES FILES .................................................................................................................................... 15
III-1- DEFINITION .............................................................................................................15
III-2- CREATION DE LA STRUCTURE D’UNE FILE .........................................................16
III-3- DECLARATION D’UNE VARIABLE DE TYPE FILE..................................................16
III-4- PROCEDURE InitialiserFile(var F : File) (permet de créer une file vide) ...................16
III-5- FONCTION EstFileVide(F : File) (permet de vérifier si une file est vide) .....................16
III-6- PROCEDURE Enfiler(x : Entier ; var F : File) (permet d’ajouter l’élément x au sommet
de la file) ...........................................................................................................................17
2
Josky AIZAN Structure de données
III-7- PROCEDURE Défiler(var x : Entier ; var F : File) (permet de supprimer le sommet de la
file et de le mettre la valeur dans la variable x) .................................................................17
3
Josky AIZAN Structure de données
I- LES LISTES CHAINEES
Objectifs :
Savoir déclarer, construire des listes chainées.
Manipuler, traiter et apprendre à utiliser des listes chainées.
Distinguer entre les différents types de listes chainées.
DEFINITIONS
1) Un pointeur P est une variable statique dont les valeurs sont des adresses.
2) La différence entre une structure de données statique et une structure de données
dynamique est la taille, la première est définie au début en spécifiant la taille qui est
fixe, par contre pour la deuxième la taille est variable et qui est basée sur l’allocation
dynamique.
DECLARATION ET UTILISATION
P : ^Entier //déclare un pointeur vers une donnée de type entier
Allouer(P) // alloue de l’espace mémoire nécessaire à une donné de type entier et
place son adresse dans P
P^=5 // affecte la donnée 5 à l’espace mémoire alloué
Libérer(P) // libère l’espace mémoire dont l’adresse se trouve dans P
EXEMPLE
4
Josky AIZAN Structure de données
I-1-PROCEDURE CréerListe (Permet de créer une liste chainée de n entiers)
I-2- PROCEDURE Affichage(Permet d’afficher les éléments de la liste)
5
Josky AIZAN Structure de données
I-3- FONCTION Recherche (Permet de rechercher un element x dans la liste)
6
Josky AIZAN Structure de données
I-4- PROCEDURE AjouterTete (Permet d’ajouter une tete de la liste)
I-5- PROCEDURE Supprimer (Permet de supprimer un element de la liste)
7
Josky AIZAN Structure de données
I-6- PROCEDURE Inverse (Permet d’inverser une liste)
8
Josky AIZAN Structure de données
I-7- PROCEDURE TriBulle (Permet de trier une liste chainee selon le principe de
tri a bulle)
9
Josky AIZAN Structure de données
I-8- PROCEDURE Concatener (Permet de concatener deux listes chainees L1 et
L2 d’entiers dans une troisieme liste L3)
10
Josky AIZAN Structure de données
I-9- PROCEDURE Fusion (Permet de fusionner deux listes triée L1 et L2 dans la
liste L1)
11
Josky AIZAN Structure de données
I-10- PROCEDURE SupprimeDoublons(Permet de Supprimer les doublons dans
une liste chainee)
12
Josky AIZAN Structure de données
I-11- FONCTION Palindrome (Permet de vérifier si une liste est palindrome ou
non)
II- LES PILES
II-1- DEFINITION
Une pile est une structure de données dynamique (liste chaînée) dont l’insertion et la
suppression d’un élément se font toujours en tête de liste.
On peut résumer les contraintes d’accès par le principe « dernier arrivé, premier sorti
» qui se traduit en anglais par : Last In First Out.
13
Josky AIZAN Structure de données
II-2- CREATION DE LA STRUCTURE D’UNE PILE
II-3- DECLARATION D’UNE VARIABLE DE TYPE PILE
II-4- PROCEDURE InitialiserPile(var P : Pile) (permet de créer une pile vide)
II-5- FONCTION EstPileVide(P: Pile) (permet de vérifier si une pile est vide)
14
Josky AIZAN Structure de données
II-6- PROCEDURE Empiler(x : Entier ; var P : Pile) (permet d’ajouter l’élément x
au sommet de la pile)
II-7- PROCEDURE Dépiler (var x : Entier ; var P : Pile) (permet de supprimer le
sommet de la pile et de le mettre la valeur dans la variable x)
III- LES FILES
III-1- DEFINITION
Une file est une structure de données dynamique (liste chaînée) dont les contraintes
d’accès sont définies comme suit :
- On ne peut ajouter un élément qu’en dernier rang de la suite.
- On ne peut supprimer que le premier élément.
On peut résumer les contraintes d’accès par le principe « premier arrivé, premier
sorti » qui se traduit en anglais par : Fast In First Out.
15
Josky AIZAN Structure de données
III-2- CREATION DE LA STRUCTURE D’UNE FILE
III-3- DECLARATION D’UNE VARIABLE DE TYPE FILE
III-4- PROCEDURE InitialiserFile(var F : File) (permet de créer une file vide)
III-5- FONCTION EstFileVide(F : File) (permet de vérifier si une file est vide)
16
Josky AIZAN Structure de données
III-6- PROCEDURE Enfiler(x : Entier ; var F : File) (permet d’ajouter l’élément x au
sommet de la file)
III-7- PROCEDURE Défiler(var x : Entier ; var F : File) (permet de supprimer le
sommet de la file et de le mettre la valeur dans la variable x)
17
