Programmation avancée

ListesWalter Rudametkin

Walter.Rudametkin@polytech-lille.frhttps://rudametw.github.io/teaching/

Bureau F011Polytech Lille

CM2

1 / 24

Structures de Données

Représentation de collections d’informations enfonction de :I traitements à privilégierI contraintes

I espace disponible / temps d’éxecutionI outils disponibles (selon les différents langages)

I propriétésI relations d’ordre ?I taux de dynamicitéI taille des informations

2 / 24

Structures de Données

Traitements typiquesI TrisI Recherche d’informations

I Par position: e.g., le kième élémentI Par valeur (associative) : v P C/P(v)

I Mises à jourI AjoutI SuppressionI Modification ñ recherche

3 / 24

Structures de Données:Classification des SD

SD

Non-linéaireLinéaire

Contiguës Chaînées

Hachées

Arbres Graphes

4 / 24

Structures de Données:Analyse des besoins

I Identification des informations et de leurscaractéristiques

I Identification des opérations (recherche, ajout,suppression, ...)

I Opérations à privilégier ?I Etude des représentations possibles (structures de

données), avec méthodes de résolution et coûtsassociés

I Choix de la structure en fonction des coûts

5 / 24

Les listes contiguës

Structures de données contiguësI Autorisent accès direct et calculé

I Déjà vu : tableaux

Représentation

A1 . . . . . . An

0 dernier MAX-1

Espace contigu occupé Zone d’extension contigue

6 / 24

Les listes contiguës — Définition

Définition du type liste_contiguë

type Liste_contigue = structureespace : Vecteur[MAX] de <T>dernier : Entier

fin

UtilisationI l : Liste_contiguëI l vide ðñ l.dernier = -1

Comment estimer MAX ?

7 / 24

Les listes contiguës — Exemple

Exemple : affichage des éléments d’une listecontiguë

Action affich(l)D : l : Liste_contiguëL : i : EntierPour i de 0 à l.dernier Faire

ecrire(l.espace[i])Fpour

Faction

8 / 24

Les listes contiguës — Recherche

Soit N le nombre d’éléments de la liste

Par positionI Accès direct en temps constant : Coût = 1

Par valeurI Non ordonnée ñ recherche séquentielle

I coût min : 1, coût max : NI Ordonnée

I Recherche séquentielle ordonnéeI coût min : 1, coût max : N

I Recherche dichotomiqueI coût min : 1, coût max : log2N

9 / 24

Les listes contiguës — Ajout

Non ordonnéeI Ajout n’importe où ñ en queueI Coût : 1

OrdonnéeI Insertion à l’indice pñ N´ p décalagesI Coût min : 1, coût max : N

10 / 24

Les listes contiguës — Suppression

Non ordonnéeI Recherche séquentielle de l’élément à supprimer

(min : 1, max N)I Permutation avec le dernier élément

Ordonnée — suppression à l’indice p

I Recherche dichotomique de l’élémentI Coût min : 1 , coût max : log2N

I N´ p+ 1 décalages (min : 1, max : N)I Coût min : 1, max : N+ log2N

11 / 24

Les listes chaînées

Représentation disperséeI Éléments rangés n’importe où en mémoire

. . . dans des cellules mémoire géréesdynamiquement. . . repérées par des pointeurs

ChaînéesI Chaque cellule repère la cellule suivanteI Un pointeur sur la première cellule définit la listeI La dernière cellule ne repère aucune cellule :

pointeur NULLI NULL = valeur de la liste vide

12 / 24

Les listes chaînéesSchématiquement

...

Liste vide l = NULL ou ∅

Déclarationstype Ptcellulle = Pointeur de Cellule

type Cellule = structurevaleur : <T>suivant : Ptcellule

fin

type Liste_chaînée = Ptcellule

l : Liste_chaînée13 / 24

Les listes chaînées :Notation sur les pointeurs

I pÒ : Cellule ñ Pointeur de CelluleI pÒ‚valeurI pÒ‚suivantI NULLñ pointeur vide

On trouve souvent la notation p->valeur à laplace de pÒ‚valeur

14 / 24

Les listes chaînées :Gestion dynamique des cellules

I Fonction allouer() : PtcelluleI Fonction qui alloue dynamiquement une celluleI Résultat : pointeur sur la cellule allouée

I Action libérer(p)I Récupère la cellule mémoire pointée par pI Valeur de p ???

15 / 24

Les listes chaînées — Recherche

SD essentiellement séquentielle ñ parcoursséquentielI Par position

I Parcours du chaînage jusqu’au kième élément(coût = k)

I Par valeurI Séquentielle (coût min : 1, max : N)I Séquentielle ordonnée (coût min : 1, max : N)I Pas de dichotomie possible

16 / 24

Les listes chaînées — Parcours séquentieltype Ptcellulle = Pointeur de Celluletype Cellule = structure

valeur : <T>suivant : Ptcellule

fintype Liste_chaînée = Ptcellule

1 Action affich (l)2 D : l : Liste_chaînée3 L : p : PtCellule4 p Ð l5 TQ p , NULL Faire6 ecrire(pÒ‚valeur)7 p Ð pÒ‚suivant8 FTQ9 Faction

17 / 24

Les listes chaînées — Mises à jourI Ajout / Suppression de cellules

I Modification locale du chaînageI Pas besoin de décalage de cellules

I Coût : constant (quelques affectations de pointeurs)I Ajout dans une liste non ordonnée

I N’importe où, e.g en têteI Ajout dans une liste ordonnée

I Coût ???

18 / 24

Les listes chaînées — Mise à jourAjout dans une liste non-ordonnée

1 Action ajout_tête(l, val)2 D : val : <T>3 D/R : l : Liste_chaînée4 L : p : Ptcellule5

6 p Ð allouer()7 pÒ‚valeur Ð val8 pÒ‚suivant Ð L9 l Ð p

10 Faction

Cas limite : liste vide

19 / 24

Les listes chaînées — Mises à jourAjout dans une liste ordonnée

Rechercher prec, pointeur précédent tel queI precÒ‚valeur ă val ď precÒ‚suivantÒ‚valeur

20 / 24

Les listes chaînées — Mise à jourAjout dans une liste ordonnée

1 Action ajout_après ( prec, val)2 D : prec : Ptcellule, val : <T>3 L : p : Ptcellule4

5 p Ð allouer()6 pÒ‚valeur Ð val7 pÒ‚suivant Ð precÒ‚suivant8 precÒ‚suivant Ð p9 Faction

Cas limitesI ajout en queue : OKI ajout en tête : pas de precñ algo ajout_têteI liste vide : idem

21 / 24

Les listes chaînées — Mises à jourSuppression

Rechercher la cellule précédant celle àsupprimer, soit prec

22 / 24

Les listes chaînées — Mise à jourSuppression

1 Action sup_après ( prec )2 D : prec : Ptcellule3 L : p : Ptcellule4

5 p Ð precÒ‚suivant6 precÒ‚suivant Ð pÒ‚suivant7 libérer (p)8 Faction

Cas limitesI en queue : okI en tête : pas de prec ñ action sup_tête

23 / 24

Les listes chaînées — Mise à jourSuppression

1 Action sup_tête ( l )2 D/R : l : Liste_chaînée3 L : p : Ptcellule4

5 p Ð l6 l Ð lÒ‚suivant7 libérer (p)8 Faction

24 / 24