Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
Al ith i t St t d Algorithmique et Structures de Données
1.1
Jean-Charles Régin
Données
Licence Informatique 2ème année
JC Régin - ASD - L2I - 2010
Listes et variantes1.2
Jean-Charles Régin
Licence Informatique 2ème année
JC Régin - ASD - L2I - 2010
ListesListes
li h3
Une liste chaînée désigne une structure de données représentant une collection ordonnée et de taille
bit i d'élé tarbitraire d'éléments.L'accès aux éléments d'une liste se fait de manière é i ll séquentielle
chaque élément permet l'accès au suivant ( t i t d t bl d l l l' è (contrairement au cas du tableau dans lequel l accès se fait de manière absolue, par adressage direct de chaque cellule dudit tableau).c aque ce u e dud ab eau).
Un élément contient un accès vers une donnée
JC Régin - ASD - L2I - 2010
ListeListe
L i i d l li t h î é t h élé t 4
Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, des pointeurs vers les éléments qui lui sont logiquement adjacents dans la q g q jliste.
premier(L) désigne le premier élément de la listenil désigne l’absence d’élément
Liste simplement chaînée : donnée(elt) désigne la donnée associée à l’élément eltsuivant(elt) désigne l’élément suivant elt
JC Régin - ASD - L2I - 2010
ListeListe5
Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, des pointeurs vers les éléments qui lui sont logiquement adjacents dans la liste.
Liste doublement chaînée :Liste doublement chaînée :donnée(elt) désigne la donnée associée à l’élément elt
i ( l ) dé i l’élé i lsuivant(elt) désigne l’élément suivant eltprécédent(elt) désigne l’élément précédant elt
JC Régin - ASD - L2I - 2010
Liste doublement chaînéeListe doublement chaînée6
Représentation : lien
d1 d2 d3
e1 e2 e3
premier(L)=e1suivant(e1) = e2; précédent(e1) = nilsuivant(e2) = e3; précédent(e2) = e1suivant(e2) e3; précédent(e2) e1suivant(e3) = nil; précédent(e3) = e2
JC Régin - ASD - L2I - 2010
Liste : opérationsListe : opérations7
Trois opérations principalesParcours de la listeAjout d’un élémentSuppression d’un élémentpp
A partir de là d’autres opérations vont être A partir de là d autres opérations vont être obtenues : recherche d’une donnée, remplacement,
té ti d li t f i d li t tconcaténation de liste, fusion de listes, etc.
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément8
Liste L doublement chaînéeOn veut insérer l’élément elt dans la liste avant le premier élément de la liste qui est associée à une donnée > 8
E l L 5 7 4 9 6 5 i è 5 7 4 lt 9 6 5 Exemple : L : 5 7 4 9 6 5, on insère 5 7 4 elt 9 6 5
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
i ( l l)9
inserer(L,elt,val) // on suppose que L n’est pas videe ← premier(L);e ← premier(L);// on cherche la positiontant que(e ≠ nil et donnee(e)<=val){q ( ( ) ){
e ← suivant(e);}if (e = nil){ // on insère en fin Z t j ’ i l fi !!!Zut je n’ai pas la fin !!!
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
inserer(L elt al)
10
inserer(L,elt,val) // on suppose que L n’est pas videe ← premier(L);// on cherche la position// pdernier ← e;tant que (e ≠ nil et donnee(e) <= val){
dernier ← e;e ← suivant(e);e ← suivant(e);
}if (e = nil){ // on insère en fin
suivant(dernier) ← eltprécédent(elt)← derniersuivant(elt)← nil
} else {} else {// on insère avant e
Pb : faut tester avec le premier !!!
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
inserer(L elt val)
11
inserer(L,elt,val) // on suppose que L n’est pas videe ← premier(L);// on cherche la positiondernier ← e;tant que (e ≠ nil et donnee(e) <= val){
dernier ← e;dernier ← e;e ← suivant(e);
}if (e = nil){
// on insère en fin suivant(dernier) ← elté éd t( lt) d iprécédent(elt)← dernier
suivant(elt)← nil} else {
// on insère avant eprec ← précédant(e)précédent(e) ← eltsuivant(elt) ← eprécédent(elt) ← precif (prec = nil){
premier(L) ← elt} else {
suivant(prec) ← eltp}
}
JC Régin - ASD - L2I - 2010
Listes avec sentinellesListes avec sentinelles
O i t d it d élé t « bid » lé ti ll
12
On introduit deux éléments « bidon », appelé sentinelles A la fois comme premier et comme dernier.
Ces éléments sont cachésL i i t l i t d l ti llLe vrai premier est le suivant de la sentinelleLe vrai dernier est le précédent de la sentinelle
Cela évite les problèmes avec les tests avec la valeur nil, puisqu’il y a toujours un suivant ou un précédant pour les éléments visibles dans la listesuivant ou un précédant pour les éléments visibles dans la liste.
Insertion après e de elt
suivant(elt) ← suivant(e) précédent(elt) ← eprécédent(suivant(e)) ← eltsuivant(e) ← eltsuivant(e) ← elt
Marche toujours ! Plus besoin de tests !
JC Régin - ASD - L2I - 2010
Listes avec sentinellesListes avec sentinelles
O i t d it d élé t « bid » lé ti ll
13
On introduit deux éléments « bidon », appelé sentinellesÀ la fois comme premier et comme dernier.
Cet élément est cachéLe vrai premier et le suivant de la sentinelleLe vrai dernier est le précédent de la sentinelle
Cela évite les problèmes avec les tests avec la valeur nil, puisqu’il y a toujours un suivant ou un précédent pour les éléments visibles dans la liste.
Suppression d’un elt non bidonSuppression d un elt non bidon
précédant(suivant(elt)) ← précédant(elt) suivant(précédant(elt)) ← suivant(elt)
Marche toujours ! Plus besoin de tests !
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
inserer(L elt val)
14
inserer(L,elt,val) // on suppose que L n’est pas videe ← suivant(premier(L));// on cherche la positiondernier ← e;tant que (e ≠ sentinelle(L) et donnee(e) <= val){
dernier ← e;dernier ← e;e ← suivant(e);
}if (e = nil){
// on insère en fin suivant(dernier) ← elté éd t( lt) d iprécédent(elt)← dernier
suivant(elt)← nil} else {
// on insère avant eprec ← précédent(e)précédent(e) ← eltsuivant(elt) ← eprécédent(elt) ← precif (prec = nil){
premier(L) ← elt} else {
suivant(prec) ← eltp}
}
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
i (L lt l)
15
inserer(L,elt,val) // on suppose que L n’est pas videe ← suivant(premier(L));// on cherche la position// on cherche la positiontant que(e ≠ sentinelle(L)et donnee(e)<=val){
e ← suivant(e);}}// on insère avant eprec ← précédent(e)précédent(e) ← eltp ( )suivant(elt) ← eprécédent(elt) ← precsuivant(prec) ← elt
JC Régin - ASD - L2I - 2010
Listes avec sentinellesListes avec sentinelles16
On peut utiliser les données des sentinelles pour simplifier les algorithmesOn traverse la liste et on s’arrête
Si on a trouvé un élément plus grandSi on a trouvé un élément plus grandSi on a atteint le dernier
O t éli i t t ff t t à l d é On peut éliminer un test en affectant à la donnée de la sentinelle, une donnée qui arrête le test.
On recherche un élément dont la donnée est < 9. On met 9 dans la donnée de la sentinelle
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
i (L lt l)
17
inserer(L,elt,val) // on suppose que L n’est pas videe ← suivant(premier(L));// on cherche la position// on cherche la positiondonnée(sentinelleFin(L)) ← val+1tant que(e ≠ sentinelle(L)et donnee(e)<=val){
e ← suivant(e);e ← suivant(e);}// on insère avant eprec ← précédent(e)p p ( )précédent(e) ← eltsuivant(elt) ← eprécédent(elt) ← precsuivant(prec) ← elt
JC Régin - ASD - L2I - 2010
Insertion sous condition d’un élémentInsertion sous condition d un élément
i (L lt l)
18
inserer(L,elt,val) // on suppose que L n’est pas videe ← suivant(premier(L));// on cherche la position// on cherche la positiondonnée(sentinelleFin(L)) ← val+1tant que (donnee(e) <= val){
e ← suivant(e);e ← suivant(e);}// on insère avant eprec ← précédent(e)p p ( )précédent(e) ← eltsuivant(elt) ← eprécédent(elt) ← precsuivant(prec) ← elt
JC Régin - ASD - L2I - 2010
Listes circulairesListes circulaires
d l f l d b19
Le suivant de la fin est le débutLe précédent du début est la fin
Une seule sentinelle est suffisantQuand elle est vide, elle pointe sur elle-mêmesuivant(sentinelle) ← sentinelleprécédent(sentinelle) ← sentinelle
premier(L) : suivant(sentinelle) dernier(L) : précédent(sentinelle)Elt d’arrêt : sentinelle
JC Régin - ASD - L2I - 2010
Listes: stockage interne et externeListes: stockage interne et externe
Q d é l f à h
20
Quand on crée une liste, on est face à un choix :Stockage externe : on crée une structure spéciale pour les éléments (ListElement par exemple) qui contient les pointeurs de éléments (ListElement par exemple) qui contient les pointeurs de la liste + un pointeur vers les donnéesStockage interne : on ajoute aux données les pointeurs de la liste
Stockage externe Li El {ListElement {
MaClasseDonnee _obj;ListElement suiv;ListElement _suiv;ListElement _prec;
}
JC Régin - ASD - L2I - 2010
Listes: stockage interne et externeListes: stockage interne et externe
Q d é li t t f à h i 21
Quand on crée une liste, on est face à un choix :Stockage externe : on crée une structure spéciale pour les éléments (ListElement par exemple) qui contient les pointeurs de la liste + un pointeur vers les donnéesStockage interne : on ajoute aux données les pointeurs de la liste
Stockage interneMaClasseDonnee {
MaDonnee _data;int _unEntier; MaClasseDonnee _suiv;_ ;MaClasseDonnee _prec;
}
JC Régin - ASD - L2I - 2010
Listes: stockage interne et externeListes: stockage interne et externe
St k t
22
Stockage externe ListElement {
MaClasseDonnee _obj;ListElement suiv;ListElement _suiv;ListElement _prec;
}A t Avantages :
Très génériqueIndifférent aux types et à la taille des données (MaClasseDonnee peut ê Obj )être Object)Très souple
Inconvénients :Allocation séparéeCode séparé (liste vs utilisation des données)
JC Régin - ASD - L2I - 2010
Listes: stockage interne et externeListes: stockage interne et externe
St k i t
23
Stockage interneMaClasseDonnee {
MaDonnee _data;int _unEntier; M Cl D iMaClasseDonnee _suiv;MaClasseDonnee _prec;
}Avantages :Avantages :
Accès aux données plus efficaceMoins de mémoire requiseMeilleure localitéSimplification de la gestion mémoire (les données des éléments de la liste sont détruites en même temps que les éléments)
Inconvénients :On doit connaître à l’avance le nombre de listes auxquelles un donnée peut appartenir simultanémentPerte de mémoire si on prévoit une appartenance qui n’est pas réalisée
JC Régin - ASD - L2I - 2010
Sdd : modifications et itérationsSdd : modifications et itérations
f f f24
De façon générale, il faut faire attention à la modification des structures de données pendant une ité tiitération
l’élément courant peut-être supprimél h i ê i éle prochain peut-être supprimé
Pas de solution générale : il faut être vigilantParfois il est interdit de modifier pendant une itération. On peut alors procéder comme suit :
Pendant l’itération, on sauve les modificationsOn effectue les modifications après l’itération
JC Régin - ASD - L2I - 2010
Listes : modifications et itérationsListes : modifications et itérations
P l li t ’ t t è i ibl25
Pour les listes, c’est très visibleEx : je supprime les éléments dont la donnée est paire. On considère une liste circulaire avec sentinelle.Voici un algorithme faux :supprimerPairs(L)
elt ←premier(L)tant que (elt != bidon(L)){
if (donnee(elt) est pair){supprimer(elt);
}}elt ← suivant(elt);
} elt a été supprimé : que vaut le suivant ?
JC Régin - ASD - L2I - 2010
Listes : modifications et itérationsListes : modifications et itérations
P l li t ’ t t è i ibl26
Pour les listes, c’est très visibleEx : je supprime les éléments dont la donnée est paire. On considère une liste circulaire avec sentinelle.Voici un algorithme juste :supprimerPairs(L)
elt ←premier(L)tant que (elt != bidon(L)){
suiv ← suivant(elt); if (donnee(elt) est pair){
i ( lt)supprimer(elt);}elt ← suiv;
}} On prend le suivant avant la suppression
JC Régin - ASD - L2I - 2010
Sdd : intégrité des donnéesSdd : intégrité des données27
Il est important que l’organisation interne des données dans une Sdd soit cohérente.Certaines propriétés doivent être respectéesCes propriétés sont dépendantes de la SddCes propriétés sont dépendantes de la SddPour une liste doublement chaînée circulaire avec
ti ll il t i t t t t élé t lt d l sentinelle, il est important que tout élément elt de la liste vérifie
précédent (suivant(elt)) = eltsuivant(précédent(elt)) = elt
JC Régin - ASD - L2I - 2010
Sdd : intégrité des donnéesSdd : intégrité des données
Af f28
Afin d’assurer le bon fonctionnement interne de la Sdd on a intérêt
à éviter d’utiliser la structure interne de la Sddà préférer utiliser des accesseurs/modificateurs portant
l Sdd t élé tsur la Sdd et non sur ses élémentsCas de liste :
f f SExcepté pour définir des fonctions internes de la Sdd, comme supprimer, ajouter, rechercher etc… :
on n’utilisera pas les primitives suivant(elt) précédent(elt) on n utilisera pas les primitives suivant(elt), précédent(elt) …on préférera toujours passer par la structure de données : supprimer (L,elt), ajouerEnTete(L,elt) etc…
JC Régin - ASD - L2I - 2010
Sdd : intégrité des donnéesSdd : intégrité des données29
L’utilisation de fonction impliquant toujours la structure de données se contrôle aisément avec les langages à objetsAucun modificateur et certains accesseurs de la classe EltList ne sont accessibles. Seule la liste a le droit d’accéder à ces méthodesdroit d accéder à ces méthodesLa class List fournit l’API (advance programminginterface) de la classe List et on doit passer par elleinterface) de la classe List et on doit passer par elle
JC Régin - ASD - L2I - 2010