Subsections

• 2.1 Introduction
• 2.2 Les listes chaînées
• 2.3 Les listes doublement chaînées
• 2.4 Les listes et les tableaux
• 2.5 Les piles
• 2.6 Les files

2 Listes

       

2.1 Introduction

Les listes font parties des type de données abstraites très couramment utilisées dans les programmes. Une liste est une suite finie (éventuellement vide) d'éléments. Lorsque la liste est non vide, son premier élément est appelé tête et la suite constitué des autres élements est appelé queue . Un même élément peut apparaître plus d'une fois dans une liste. On parelera alors de la i ^ème occurence de l'élément x .

Le type de données liste permet de définir un très grand nombre d'opérations:

• le tri d'une liste,
• la fusion, la concaténation de deux listes,
• la recherche, l'insertion et la suppression d'un élément dans une liste,
• etc.

2.2 Les listes chaînées

L'implantation la plus naturelle du type de données liste est la structure de données listes chaînées .

Cette structure de donnée peut être définie en C comme suit:

 
struct UNE_CELLULE  {
    struct etiquette_info;
    struct UNE_CELLULE suivant;
}
typedef struct UNE_CELLULE POINTEUR_LISTE;
 

On se dotera d'un pointeur vers le premier élément de liste:

 
POINTEUR_LISTE liste;
 

Nous verrons en travaux dirigés les diverses opérations que l'on peut effectuer sur les listes chaînées.

2.3 Les listes doublement chaînées

2.4 Les listes et les tableaux

2.5 Les piles

Les piles sont des listes sur lesquels seul l'insertion et la suppression d'un élément en tête est permise; représentez vous une pile d'assiettes. Le terme de liste LIFO (Last In First Out ) est utilisé comme synonyme de pile.

2.6 Les files

Les piles sont des listes sur lesquels seul l'insertion en fin de liste et la suppression d'un élément en tête est permise; représentez vous une file d'attente. Le terme de liste LIFO (Last In First Out ) est utilisé comme synonyme de pile.