Algorithme et structure de données

Les Opérations

On peut déterminer qu’il y a aussi des opérations courantes telles que : aﬃcher une liste
accéder à l’élément précédent
rechercher la position (localiser) un élément
supprimer les éléments identiques (purger)
eﬀacer les éléments d’une liste (RAZ)

Traduction en C

Opérations dans lstop.h
utilise les « services » des primitives donc
#i n c l u d e < l s t p r i m . h>
void L i s t e A f f i c h e r ( LISTE L ) ;
POSITION L i s t e P r e c e d e n t ( POSITION p , LISTE L ) ;
POSITION L i s t e L o c a l i s e r (ELEMENT x , LISTE L ) ;
LISTE L i s t e P u r g e r ( LISTE L, LISTE LL) ;
void L i s t e R a z ( LISTE L ) ;

Avec entête/sentinelle

1ere cellule vide (entête)
1 cellule / élément
une liste = pointeur sur l’entête
fin = position de la Sentinelle

Les 6= types de chaînages

Il existe 6= types de réalisation avec chaînage :
chaînage simple
double chaînage
chaînage circulaire. . .
Traduction en C dans lstptr.h

Inconvénients des listes chaînées

Si taille pointeur > taille d’un élément
! plus de place pour organisation que pour les données
! eﬃcacité &
Si taille liste %
! nombre d’allocations dynamiques %
! Indirections vers des cellules dispersées %
! rapidité d’accès &
Par cellule contiguës
une liste = pointeur une structure qui contient
un tableau alloué automatiquement (taille max réservée à la compilation)
la position du dernier élément (taille réelle du tableau)
Si N listes alors N structures
Traduction en C dans lsttab.h
Simulation des pointeurs en mémoire
Simulation de la mémoire dans un tableau
Tableau Mémoire allouée automatiquement une liste
= @ du 1er élément dans le tableau mémoire
= un indice
N listes dans le même tableau Mémoire
Traduction en C dans lstfxptr.h

Par faux pointeurs

Intérêt :
pallie les inconvénients des « vrais » pointeurs
Inconvénient :
si tailles des listes % et/ou
si nombres des listes %
alors risque de débordement mémoire %

Traduction en C

Dans lstprim.h
#i n c l u d e < l s t s d d . h>
lstsdd.h
structure de donnée choisie pour réaliser les primitives du TDA liste
Contenu :
/ s i r é a l i s a t i o n p a r c e l l u l e s c h a i n e e s / #i n c l u d e < l s t p t r . h>
/ s i r é a l i s a t i o n p a r c e l l u l e s c o n t i g u e s / #i n c l u d e < l s t t a b . h>
/ s i r é a l i s a t i o n p a r f a u x p o i n t e u r s / #i n c l u d e < l s t f x p t r . h>

1 Définition du TDA Liste
2 Réalisation du TDA Liste
3 Type de stockage des éléments
4 Recherche d’un élément
Dans une liste non triée
Dans une liste triée
5 Fin