ASD - SOIE - Institut Supérieur de Gestion de Tunis

Report
LOGO
Institut Supérieur
de Gestion de Tunis
Soltana Ghanem : [email protected]
1ère année IAG
2009 - 2010
Objectifs
L’étudiant devra :
connaître l’utilité des structures de données
connaître les structures de données linéaires
connaître les avantages et inconvénients
de chaque structure
Pouvoir implémenter les structures de données
linéaires
Être capable de choisir la structure adéquate à chaque
problème
2
Références
 Michel Divay : Algorithmes et structures de données
génériques
 Abdelali Guerid, Pierre Breguet, Henri Röthlisberger :
Algorithmes et structures de données avec C++ et Java
 Cours Mme Nahla Ben Amor : Algorithmes et structures
de données , http://isgprog2.ifrance.com/
3
Plan
1
Définitions
2
Structures de données linéaires
Tableau contiguë
Liste chainée
File
Pile
3
Exercice
4
Définitions
Algorithme
Structure
de données
C’est un programme écrit
dans un langage naturel
C’est une structure logique destinée à contenir des
données, afin de leur donner une organisation
permettant de simplifier leur traitement
5
Définitions
Mise en situation :
Vous voulez créer une application qui calcule votre
moyenne (6 matières)
Vous décidez de créer 12 variables qui serviront à
contenir les notes exemple : mat1_exam, mat2_exam..
On vous demande de réaliser une application qui calcule la
moyenne de tout les étudiants de ta classe(40)
 Vous allez définir et gérer manuellement 40 * 12 variables!
6
Tableau contiguë
Un tableau est un ensemble de cellules contigües visant
à Contenir des données homogènes
Un tableau est caractérisé par :
• Un nom
• Une taille physique
• Le type des données qu’il va contenir
7
Tableau contiguë
Exemple :
T =
12
7
8
18
Indice
1
2
3
4
3
5
• Pour récupérer la valeur d’une case :
Nom_du_tableau [ indice ]  T[4] contient la valeur 18
• Pour modifier une case :
Nom_du_tableau [ indice ] = Valeur  T[2] = 200
12
200
8
18
1
2
3
4
3
5
8
Tableau contiguë
Manipulation des tableaux contigües :
Taille () : entier= une fonction qui retourne la Taille logique du
tableau
Suppression
• A la création du tableau initialiser la variable taille 0
• Si une opération d’ajout est effectuée avec succès taille  taille +1
• Si une opération de suppression est effectuée avec succès taille taille -1
Récupérer ( indice : entier ) : Objet = fonction qui retourne l’élément à la
position indice
Pré condition :
• indice > 0 et indice <= taille ()
Traitement : retourner ( tableau [ indice ] )
9
Tableau contiguë
Ajouter ( élément : objet , indice : entier ) : booléenne = fonction qui
ajoute l’élément dans le tableau à la position indice
Pré condition :
• taille() < taille physique
• indice > 0 et indice <= taille ()+1
• élément à ajouter doit être de même nature que les
éléments contenus par le tableau
Ajouter ( 200 , 3 )
12
1
7
2
8
3
18
4
3
5
12
1
7
2
8
3
8
4
18
5
3
12
7
200
8
18
3
1
2
3
4
5
6
10
Tableau contiguë
Supprimer ( indice : entier ) : booléenne = fonction qui supprime
l’élément se trouvant à la position indice
Pré condition :
• indice > 0 et indice <= taille ()
Supprimer ( 3 )
12
7
200
8
18
1
2
3
4
5
12
7
8
8
18
1
12
1
2
7
2
3
8
3
4
18
4
5
18
5
L’élément d’indice 5 sera toujours présent mais l’décrémentation de la
taille le rendra inaccessible .
11
Tableau contiguë
Avantages
Inconvénients
Simple à implémenter
et à manipuler
On doit définir la taille
maximale au préalable
Accès directe aux
données
L’espace mémoire doit
être contiguë
Ajout et suppression en
fin de tableau en O(1)
Utilisation non optimisé
de la mémoire
12
Liste chainée
LISTE
Une Liste est un ensemble de
nœuds reliés entre eux
Nœud
Un nœud est une entité renfermant de
l’information et ayant un pointeur sur le
nœud qui la suit
Implémentation
Une liste peut être caractériser par un
nœud tête car ce dernier sera le point de
départ pour retrouver les autres nœuds
13
Liste chainée
Exemple :
Pointeur
suivant
12
7
suivant
8
18
3
Nœud
Tête de liste
• la tête de liste représente le point d’accès à la liste
• Chaque nœud :
• Renferme une information
• Indique l’emplacement du prochain nœud
• Le dernier nœud ne pointe vers rien (null)
14
Liste chainée
Ajout : cas 1 : à la première position
12
7
8
18
3
22
22
12
7
8
18
3
15
Liste chainée
Ajout : cas 2 à la nième position
12
12
7
7
22
8
8
18
22
3
18
3
16
Liste chainée
Suppression: cas 1 : de la tête de liste
12
7
8
18
3
Il est préférable d’optimiser
la mémoire !!
7
8
22
18
3
17
Liste chainée
Suppression: cas 2 : suppression d’un élément autre que la tête de liste
À supprimer
12
7
12
8
7
18
18
3
3
18
Liste chainée
Avantages
Utilisation optimale de la
Mémoire
L’espace mémoire ne doit
pas être contiguë
Inconvénients
L’accès aux données
Est plus couteux (temps)
Ajout à la fin de liste
en O(n)
La taille de la liste peut ne
Pas être définie au préalable
Toutes les opérations Sur
la tête de liste sont en O(1)
Gestion des
pointeurs
19
File
Une file (Queue) est un type particulier de liste , où les
éléments sont insérés en queue et supprimer en tête
Le nom vient des files d’attente à un guichet, où le
premier Arrivé est le premier servi : FIFO (First In First
Out )
Les files sont d’un usage très répandu dans la
programmation système : gestion des processus,
Gestion des imprimantes…
20
File
Exemple :
Point de sorite
Station de traitement
12
7
8
18
3
1
2
3
4
5
• Seul le premier élément peut quitter la file
• Les nouveaux éléments sont ajoutés à la fin de la file
14
Un nouveau venu
21
File
Implémentation
Puisque les Files sont des cas particuliers de listes pourquoi ne pas
utiliser ces dernières pour les implémenter ?
Doit-on utiliser les tableaux contigües ou les listes chainées?
Liste doublement chainée !!
Enfiler ( élément )  revient à faire ajouter ( élément , taille ()+1 )
Défiler ( )  revient à faire supprimer (1)
22
Pile
Une pile (stack) représente une séquences d’éléments
accessibles par une seule extrémité appelée sommet
La stratégie de gestion d’une pile est : dernier arrivé,
premier servi : LIFO ( Last In First Out )
Les opérations de mise à jour (insertion et suppression) ,
d’après la définition, se font à partir du sommet
23
Pile
Exemple :
Sommet
3
18
Je vois mieux
maintenant !!
8
7
Base
12
• Le sommet de la pile est le seul élément manipulable
• Pour manipuler un élément se trouvant au milieu de la pile il faudra
dépiler tout ces prédécesseurs
•Si on ajoute un nouvel élément il serra empiler au dessus du sommet
24
Pile
Doit-on utiliser les tableaux contigües ou les listes chainées?
Tableau contiguë !!
liste chainée !!
Empiler ( élément )  revient à faire ajouter ( élément , taille () +1 )
Dépiler ( )  revient à faire supprimer (taille () )
Sommet ( )  revient à faire récupérer ( taille () )
Les piles sont utilisées pour gérer les appels récursifs !!!!
25
Exercice : Quiz
Quel est la structure de données linéaire la plus adéquate
à chaque problème?
1
La gestion d’une équipe de football
Tableau contiguë
2
La gestion des demandes de location d’une voiture
File
3
Le problème des tours de Hanoï
Pile
4
La gestion des clients d’une banque
Liste chainée
26

similar documents