Les structures de données simples dynamiques

profThiernesse
9,472 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content
Next: Exercice 1

Introduction

Dans cette partie du cours, des structures de données simples construites à l'aide de pointeurs seront abordées:

  • les piles
  • les files
  • les listes ordonnées

L'utilisation de pointeurs, de l'allocation dynamique et du chaînage va constituer une solution pour travailler sur un nombre d'éléments non connu au préalable, contrairement aux vecteurs de taille fixe.

Les piles

Les piles correspondent au principe LIFO : Last In First Out. Pour comprendre le principe de pile chaînée, il est utile de représenter la mémoire (la pile du programme et le heap). Soit la structure C suivante qui va permettre de construire une pile d'entiers :

struct pile{
  int val;
  struct pile * prec;
};

L'état initial de la pile

Au départ, la pile est vide, elle ne contient aucun élément :

struct pile *p;

Etat initial d'une pile d'entiers

L'ajout d'un élément : l'opération push()

Les éléments 2, 1 et 10 (valeurs servant pour l'exemple) sont insérés sur la pile dans cet ordre. On observe que le pointeur p ainsi que le heap est modifié à chaque ajout. Chaque élément possède un pointeur prec qui permet de désigner l'élément inséré précédemment. La représentation de la mémoire à chaque étape est la suivante :

push d'un elementpush d'un deuxième élémentpush d'un troisième élément
push d'un elementpush d'un deuxième élémentpush d'un troisième élément

La supression d'un élément : l'opération pop()

Si la pile n'est pas vide , l'opération pop() va permettre de récupérer et retirer l'élément à son sommet. Dans certaines implémentations, une opération top() permet d'accéder à l'élément au sommmet de la pile sans le retirer alors que pop() le retire sans le renvoyer. Dans l'exemple, la mémoire allouée sur le heap pour l'élément est récupérée. L'élément 10 désigné par p est retiré et la pile se retrouve dans l'état suivant: L'état  de la pile d'entiers après l'opération pop()

Les files

Les files correspondent au principe FIFO : First In First Out.

struct file{
  int val;
  struct file * suiv;
};

L'état initial de la file

Au départ, la file est vide, elle ne contient aucun élément :

struct file *f;

Etat initial d'une file d'entiers

L'ajout d'un élément : l'opération add()

Lorsque la file est vide, le pointeur de tête est modifié. Dans le cas contraire, il ne l'est pas et le nouvel élément est ajouté en fin de liste.

add d'un elementadd d'un deuxième élémentadd d'un troisième élément
add d'un elementadd d'un deuxième élémentadd d'un troisième élément

La récupération d'un élément : l'opération get()

Si la file n'est pas vide , l'opération get() va permettre de récupérer et retirer le premier élément de la file. La mémoire allouée sur le heap pour l'élément est récupérée. Dans l'exemple, l'élément 2 désigné par f est retiré et la file se retrouve dans l'état suivant: L'état  de la file d'entiers après l'opération get

Les listes ordonnées

Sur une liste ordonnées, les opérations classiques que l'on peut réaliser sont :

  • insérer un élément
  • supprimer un élément
  • rechercher un élément
  • tester si la liste est vide

Inserer un élément : insert()

Un élément peut être insérer en tête, au sein ou en fin de liste selon sa valeur. Dans l'exemple ci-dessous, un élément de valeur 3 est inséré au sein de la liste et l'élément 5 sera insérer en fin de liste ordonnée.

insert d'un element dans la listeinsert d'un élément en fin de liste
insert d'un elementinsert d'un élément à la fin

Supprimer un élément : remove()

L'élément à supprimer peut se trouver en tête , au sein de la liste ou en fin de liste. L'opération permettra de retirer l'élément du chaînage et de désallouer la mémoire qu'il occupait sur le heap.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content