Cours Algorithmique : Structures de Données - les tableaux - listes chaînées - piles - files - arbres binaires

STRUCTURES DE DONNÉES

INTRODUCTION 

Ce  document  est  un  résumé  concernant les structures  les  plus  classiques  rencontrées  en informatique  pour  organiser  des  données.  On  suppose  que  le  lecteur  connait  déjà  les tableaux et  les enregistrements  (exemple: record en Pascal, struct en C). Pour aborder les différentes structures de données présentées ici, le lecteur devra également bien maîtriser la notion de pointeurs et de gestion dynamique de la mémoire.  

Les structures de données présentées ici sont : 

• les tableaux (arrays en anglais), 
• les listes chaînées (linked lists en anglais), 
• les piles (stacks en anglais), 
• les files (queues en anglais), 
• les arbres binaires (binary trees en anglais). 

Pour chacune de ces structures de données, nous présentons avant toutdifférentes manières de les modéliser. Ensuite, nous détaillons en langagealgorithmique les principales opérations qui  peuvent  être appliquées sur cesstructures.  Enfin, pour  certaines  d'entre  elles, nous développons quelques exemples d'utilisation. 

NOTATIONS                                                                                      

Avant d'entrer dans  les détails de chaque structure, nous  introduisons  ici quelques notations qui  seront utilisées  tout  au  long de  ce  document.  Elles  permettront  de  formaliser  les modélisations proposées pour  les différentesstructures de données ainsi que  les opérations applicables sur ces structures. 

Opérateurs

  

• *p est le contenu pointé par p;  

• T * est le type pointeur sur un élément de type T;  

• &x est l'adresse de l'élément x;  

• x <--  y affecte la valeur y à la variable x;  

• /* x */ signifie que x est un commentaire;  

• =, <=, <, !=, >, >= sont les opérateurs de test d'égalité, d'infériorité ou d'égalité, d'infériorité, de différence, de supériorité et de supériorité ou d'égalité;  

• rendre x termine la fonction en cours et renvoie la valeur x à la fonction appelante; 

• x.y est le champ y dans la structure x;  
   
• x --> y est le champ y dans la structure pointée par x.  

Déclarations

  
Fonction

  
On définit une fonction de la manière suivante. 

  
fonction TR   f(TX x, TY y): 
 ...  
fin fonction;  

Dans cet exemple, f a deux paramètres, x de type TX et y de type TY, et renvoie un élément de type TR.  

Type

On déclare un nouveau type de donnée de la manière suivante.  

  
type TX: TY *; 

Dans cet exemple, le type TX est défini comme étant un pointeur sur un élément de type TY.  

Enregistrement / Structure

  
On définit un enregistrement, appelé aussi une structure ici, de la manière suivante. 

  
structure S:
 TX x; 
 TY y; 
fin structure; 

Dans cet exemple,  la  structure  s est composée de deux champs: x de  type TX et y de  type TY. 

Types et constantes  

• BOOLEEN est le type booléen, il prend uniquement les valeurs VRAI ou FAUX; 
• ENTIER est le type nombre entier; 
• ELEMENT est le type des éléments stockés dans une structure de données; 
• NIL est une constante symbolique, un pointeur qui a cette valeur est un pointeur qui pointe sur rien du tout. 

Instructions

• T *   ALLOUER(T, ENTIER n) est une instruction qui alloue un espace mémoire pouvant contenir n éléments de type T. Si l'allocation est possible, la fonction retourne l'adresse de l'espace alloué. Dans le cas contraire, la valeur NIL est retournée, indiquant que l'allocation a échouée. 

• LIBERER(T * p) est une instruction qui libére l'espace mémoire pointé par p. Cet espace doit avoir été alloué auparavant avec l'instructionALLOUER.