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 { ...
Voir