Structures de données linéaires

Chapitre 03

Plan

1 - Liste

2 - File

3 - Pile

Liste linéaire

Une liste linéaire est la forme la plus courante d'organisation des données. On l'utilise pour stocker des données de même type qui doivent être traitées de manière séquentielle. La structure doit également être évolutive, c'est a dire que l'on doit pouvoir ajouter et supprimer des éléments.

Liste linéaire(Structure logique)

Définition: Une liste est une suite finie (éventuellement vide) d'éléments de même type repérés selon leur rang dans la liste.

Remarques: • L'ordre des éléments est fondamental. Mais attention, il

ne s'agit pas d'un ordre sur les valeurs des éléments mais d'un ordre sur les places dans la liste.

• Chaque élément est rangé à une certaine position. Il ne faut pas confondre le rang et la position !

Liste linéaire(Structure logique)

Au niveau logique, on appelle une liste linéaire, la représentation d’un ensemble fini et ordonné d’éléments de type T. elle peut être dénotée par la simple énumération de ses éléments:

L=(e1,e2,…., en)Le nombre des éléments n’est pas connu

nécessairement au préalable et éventuellement variable.

Liste linéaire(Structure logique)

• Elle est entièrement déterminée par la connaissance de sa première place, i.e. celle de son premier élément appelé tête de la liste.

Liste linéaire(Structure fonctionnelle)

• Pour la manipulation des listes, on peut définir les primitives et fonctions suivantes :– Créer_liste() : création d'une liste vide– Position_debut(liste L) : retourne la position du

premier élément de la liste, INCONNUE si la liste est vide

– Position_n(liste L) : retourne la position du dernier élément de la liste, INCONNUE si la liste est vide

– Position_suivante(position p, liste L) : retourne la position de l'élément qui suit celui en position p, INCONNUE si on sort de la liste

– Position_precedente(position p, liste L) : retourne la position de l'élément qui précède celui en position p, INCONNUE si on sort de la liste

Liste linéaire(Structure fonctionnelle)

– Element_acces(position p,liste L) : retourne l'élément en position p– Longueur(liste L) : retourne le nombre d'éléments contenus dans la

liste– Insérer (élément e, rang r, liste L) : rajoute l'élément dans la liste (qui

est donc modifiée) au rang r– Supprimer(rang r, liste L) : supprime l'élément de rang r dans la liste

(qui est donc modifiée)– Liste_est_vide(liste L) : teste si la liste est vide, retourne VRAI ou

FAUX– Element_ieme(rang r, liste L) : retourne l'élément de rang r– Ajouter(élément e, position p, liste L) : ajoute l'élément e dans la liste

(qui est donc modifiée) après celui en position p– Enlever(position p, liste L) : supprime l'élément de position p dans la

liste (qui est donc modifiée).

Liste linéaire(Implémentation)

a. Implémentation contiguë:

• Les éléments sont rangés les uns à côté des autres, dans un tableau. La ième case du tableau contient le ième élément de la liste.

• Le rang est égale à la position (des entiers tout simplement) !

Liste linéaire(Implémentation contiguë)

• Remarques: – l’inconvénient, d’une telle représentation,

réside dans la suppression et l’insertion d’éléments qui nécessitent des décalages dans le tableau!

– L’insertion d’éléments à la liste (dans le tableau) peut provoquer un sur-débordement.

Liste linéaire(Implémentation)

b. Implémentation chaînée:

• Dans ce cas on parle de liste chaînée. Cette représentation permet d’éviter les inconvénients de la représentation contiguë.

Liste linéaire(Implémentation chaînée)

• Les éléments ne sont pas rangés les uns à côté des autres. On a besoin de connaître, pour chaque élément, la position (l'adresse) de l'élément qui le suit. La position n'a donc plus rien à voir avec le rang, mais c'est l'adresse d'une structure qui contient l'élément ainsi que la position du suivant .

Liste linéaire(Implémentation chaînée)

Elément Suivant Elément Suivant Elément NIL Tête

Liste linéaire(Implémentation chaînée)

• Chaque élément de la liste chaînée est représenté par un doublet contenant:– La valeur de l’élément– Et l’adresse (pointeur ou position) de

l’élément suivant.

Liste linéaire(Implémentation chaînée)

• Remarque: – dans une liste chaînée, l’accès à un élément

est une opération plus longue par rapport à l’implémentation contiguë, car on effectue un parcours effectif (élément par élément) de la liste.

Variable dynamique(pointeurs)

• un lien (adresse) est stocké dans une case mémoire particulière : appelée pointeur

• Un pointeur est une variable qui contient l’adresse (l’endroit où est rangé en mémoire) d’une autre variable dynamique.

Variable dynamique(pointeurs)

• Une variable dynamique est repérée par un pointeur. • Le pointeur est une variable dont la valeur est l’adresse

de la variable dynamique.• Un pointeur pointe sur une case (variable dynamique)

ayant un type précis.• Un pointeur peut contenir « NIL », dans ce cas il ne

repère aucune variable dynamique.• On dit qu’une variable P de type pointeur repère une

variable dynamique la valeur de P<> NIL et est égale à l’adresse de cette variable dynamique.

Pointeur^type

Variable dynamique(type)

Variable dynamique(pointeurs)

• Les variables dynamique ne sont pas déclarées dans un programme, seul les pointeurs sur leurs types qui doivent être définis.

• Une variable dynamique de type T repérée par un pointeur P est crée par l’appel de la primitive prédéfinie NEW(P).

• Une variable dynamique repérée par un pointeur P peut être supprimer à l’aide de la primitive prédéfinie DISPOSE(P).

Variable dynamique(pointeurs)

• Exemple: Début

q,p:^Entier;

New(p);

Lire(^p);

q:=p;

q^:=2*q^;

Ecrire(q^);

Dispose(p);

Fin.

Déclaration d’une liste chaînée

• Les variables dynamiques sont utilisées pour représenter les éléments d’une liste chaînée.

• Et comme chaque élément d’une liste chaînée est représenté par un doublet, on utilise alors la structure d’enregistrement comme suit:

TYPEPointeur = ^Elément;Elément = Enregistrement

Valeur : <type>; Suivant : Pointeur;

Fin;

Exemple

• Pour définir une liste de nombres réels:TYPEPointeur = ^Elément;Elément = Enregistrement

Valeur : Réel; Suivant : Pointeur;

Fin;VARL, P: Pointeur;

Application sur les listes

• Construction de liste (Fifo et Lifo)

• Insertion et suppression dans une liste

• Listes Bidirectionnelles

• Listes circulaires

La structure de FILE (Structure logique)

Définition: Une FILE est un cas particulier de liste pour laquelle on ne peut ajouter de nouvel élément qu’à la fin de la file et on ne peut extraire un élément qu’en tête de file. D’où l’appellation FIFO (First In, First Out).

File(Structure fonctionnelle)

• Les primitives suivantes sont utilisées pour la manipulation d’une File:

• Filevide : fonction booléenne = vrai si la file est vide et faux sinon

• Enfiler : Procédure d’ajout d’un élément à la queue de la file,

• Défiler : Procédure permettant de supprimer l’élément qui se trouve en tête de file,

• Filepleine: fonction booléenne = vrai si la file est pleine; càd l’ajout d’un élément provoque un sur-débordement et faux sinon.

• Initialisation : Initialise une file à vide.

File(Implémentation)

1. Représentation contiguë:

Une file peut être représentée par un vecteur:

1 TailleMax

↓ ↓

↑ ↑

tête Queue

F

File(Implémentation)

Représentation contiguë:

• File est vide si tête>queue

• Enfiler(F,X): queue:= queue +1; F[queue]:=x;

• Défiler(F,x): x:=F[tête]; tête :=tête+1

• File est pleine si queue=taillemax.

• Initialiser File : Tête:=1; queue:=0;

File(Implémentation)

Fonction FileVide(Entrée Tête,Queue:Entier):Booléen;

Début

FileVide:=(Tête>queue);

Fin; Procédure Enfiler(Entrée/Sortie F:file; Entrée x:<type>);

Début

queue:=queue+1;

F[queue]:=x;

Fin;

File(Implémentation)

2. Représentation chaînée:

Une liste linéaire Fifo peut être considérée comme une file.

Elément Suivant Elément Suivant Elément NIL

Tête Queue

File(Implémentation)

Représentation chaînée:

• File est vide := (tête=Nil)

• Enfiler(F,X): Exercice…

• Défiler(F,x): Exercice…

• File est pleine: Dépend du système

• Initialiser File : Tête:=Nil; queue:=Nil;

File(Application)

• Rechercher le maximum des éléments d’une file de nombres réels donnée.

• Supprimer les éléments négatifs d’une file de nombres réels donnée.

Structure de Pile(Structure logique)

• Définition: Une Pile est considérée comme un ensemble, éventuellement variable de données, de même type, structuré en un sommet et un corps. Le sommet de la pile est un élément particulier; c’est le seul point d’entrer dans la pile.

Sommet

…………… Corps

Base

Structure de Pile(Structure logique)

• Une PILE est donc un autre cas particulier de liste pour laquelle on n’accède qu’à un seul élément : le dernier (appelé Sommet), d’où l’appellation LIFO (Last In, First Out).

• Caractéristiques d’une Pile:– Principe de construction Lifo;– Seul le sommet de pile (dernier élément entré) est visible;– Les informations sont conservées temporairement; lors du

lancement du pgme, la pile est supposée vide, et à la fin du traitement celle-ci doit être également vide, et bien sûr durant le traitement la pile diminue et augmente de taille.

Pile(Structure fonctionnelle)

• Les primitives suivantes sont définies pour la gestion d’une Pile:

• Pilevide : fonction booléenne = vrai si la Pile est vide et faux sinon

• Empiler (Push): Procédure d’ajout d’un élément au sommet de pile,

• Dépiler (Pop): Procédure permettant de récupérer la valeur et supprimer l’élément qui se trouve en sommet de pile,

• Pilepleine: fonction booléenne = vrai si la Pile est pleine; càd l’ajout d’un élément provoque un sur-débordement et faux sinon.

• InitPile : Initialise une Pile à vide.• Sommetpile : permet de consulter la valeur du sommet

de pile (ne change pas l’état de la pile)

Pile(Implémentation)

1. Représentation contiguë:

La pile peut être représenter à l’aide d’un vecteur, le nombre maximum d’éléments constitue la taille de la pile.

Le sommet de la pile correspond à l’indice courant et la base correspond à l’indice 1.

Pile(Implémentation)

Représentation contiguë

TailleMax

Sommet

1 ( base )

Pile(Implémentation)

• Exercice: Donner les différentes primitives de manipulation de pile pour la représentation contiguë.

Pile(Implémentation)

2. Représentation Chaînée:

Une liste linéaire Lifo peut être considérée comme une Pile.

Valeur Suivant

Valeur Suivant

Valeur Suivant

Sommet

Base

Pile(Implémentation)

Représentation Chaînée

• Pile est vide := (Sommet=Nil)

• Empiler(P,X): Exercice…

• Dépiler(P,x): Exercice…

• Pile est pleine: Dépend du système

• InitPile : Sommet:=Nil; Base:=Nil;

Pile(Application)

• Trier une Pile de nombres réels.

• On dispose d’une pile de nombres réels ordonnés selon l’ordre décroissant des valeurs, i.e que le maximum se trouve au sommet de pile. Donner la procédure qui permet de rechercher dans cette pile une valeur x, et l’insert à sa place qu’il faut si elle est inexistante.