Plan Listes > Définition Une liste est un ensemble d’objets de même type Algorithmeconstituant les éléments de la liste. Les éléments Types abstraits de donnéessont chaînés entre eux et on peut facilement ajouter ou extraire un ou plusieurs éléments. Pointeurs Une liste simple est une structure de données telle Listesque chaque élément contient : Piles Des informations caractéristiques de l’application développée. Files Un pointeur vers un autre élément de la liste ou une marqueur indiquant la fin de la liste. Tris Complexité20/09/2006 1 20/09/2006 2Listes > Exemple Listes > Opérations Créer_liste : ⇒ Liste Accès : Liste ⊗ Entier ⇒ PlaceDupond DurandPremier Contenu : Place ⇒ Element Longueur : Liste ⇒ Entier Supprimer : Liste ⊗ Entier ⇒ Liste Insérer : Liste ⊗ Entier ⊗ Element⇒Paul / ParkerListe Succ : Place ⇒ Place20/09/2006 3 20/09/2006 41Listes > Représentation en Listes > Représentation en mémoire mémoire > Allocation contiguë> Allocation dynamiqueAdressesPosition Element Suivantp500 DupondP0 Dupond 21 Paul /Toto1002 Toto 31000Titi3 Titi 1Paul /3504520/09/2006 5 20/09/2006 6Listes > Algorithme avec allocation Listes > Comparaisondynamique > Structure de donnéesEnregistrement Place{ Allocation dynamiqueElt : Pointeur[Element]; Plus de souplesse, virtuellement pas de Suivant : Pointeur[Place];limite de taille} Gestion du dépassement de capacité àprévoirEnregistrement Liste { ...
Une liste est un ensemble d’objets de même type constituant les éléments de la liste. Les éléments sont chaînés entre eux et on peut facilement ajouter ou extraire un ou plusieurs éléments.
Une liste simple est une structure de données telle que chaque élément contient : Des informations caractéristiques de l’application développée. Un pointeur vers un autre élément de la liste ou une marqueur indiquant la fin de la liste.
Listes > Représentation en mémoire > Allocation dynamique
Adresses
500
100
1000
350
20/09/2006
p
Dupond
Toto
Titi
Paul
/
Listes > Comparaison
Allocation dynamique Plus de souplesse, virtuellement pas de limite de taille Gestion du dépassement de capacité à prévoir Allocation contiguë Taille maximale doit être connue d’avance Structure semblable à un fichier sur un disque
20/09/2006
5
7
P
Listes > Représentation en mémoire > Allocation contiguë
Position 0 1 2 3 4 5
20/09/2006
Element Dupond Paul Toto Titi
Suivant 2 / 3 1
Listes > Algorithme avec allocation dynamique > Structure de données