TD 3: Piles

Tristan Crolard - François Pottier

Résumé:

Tableaux de taille variable. realloc, free.

Objectif

On désire écrire un module qui implémente la structure de données pile. On entend par là définir le type des piles, ainsi que les opérations élémentaires permettant de les manipuler. Ces opérations sont au nombre de quatre:

• création d'une nouvelle pile vide;
• ajout d'un élément au sommet de la pile;
• retrait d'un élément du sommet de la pile;
• destruction d'une pile.

Comme toujours, ce module se composera de deux fichiers. Le fichier d'en-têtes, ou header, contiendra les déclarations de types, ainsi que les prototypes des fonctions correspondant aux quatre opérations ci-dessus. Le fichier source contiendra la définition de ces quatre fonctions.

Écriture du fichier d'en-têtes

Nous souhaitons que notre code soit aussi indépendant que possible du type des éléments contenus dans la pile. Aussi, attribuons-lui un nom:

typedef int element;

Partout où il sera nécessaire de faire référence au type du contenu de la pile, on utilisera element, et non pas int. Il suffira alors de changer la définition ci-dessus pour obtenir une pile de float, une pile de char*, etc.

Une pile se compose de deux informations: le nombre d'éléments qu'elle contient, et les éléments eux-mêmes, que nous stockerons dans un tableau de taille variable.

typedef struct {
  int      taille;
  element* elements;
} pile;

Le tableau element étant de taille variable, il sera alloué dans le tas; c'est pourquoi nous avons besoin d'opérations d'allocation et de destruction pour les piles. La structure pile elle-même est de taille fixe, aussi nous n'aurons pas besoin de l'allouer dans le tas; elle sera toujours stockée dans une variable locale.

Par convention, les opérations d'ajout et de retrait renverront un entier dont la valeur sera 0 en cas de succès, 1 en cas d'opération illégale (par exemple, lorsqu'on tente de retirer un élément à une pile vide) et 2 en cas d'erreur système (par exemple, lorsque la mémoire disponible est insuffisante). Les prototypes des quatre opérations sont donc

void create (pile *outPile);
int push (pile *ioPile, element inElem);
int pop (pile *ioPile, element *outElem);
void delete (pile *inPile);

Écriture du fichier source

Implémenter les quatre fonctions ci-dessus. On fera en sorte que la taille du tableau d'éléments soit toujours égale au nombre d'éléments contenus dans la pile. (Dans le cas où la pile est la vide, on pourra se passer entièrement de tableau, plutôt que de conserver un tableau de taille nulle.)

On utilisera la fonction suivante, fournie par la librairie standard <stdlib.h>:

void* realloc (void* ptr, size_t size);

pour augmenter ou réduire la taille du tableau sans en perdre le contenu. On signale que l'appel realloc(NULL, size) se comporte de la même façon que malloc(size).

Amélioration

L'implémentation ci-dessus effectue un appel à realloc à chaque opération push ou pop, ce qui est coûteux en temps. L'améliorer de façon à n'appeler realloc qu'après N opérations push consécutives, où N est une constante quelconque fixée. De plus, on ne réduira plus la taille de la pile lors de l'opération pop. On devra modifier la déclaration du type pile pour distinguer la taille physique de la pile (i.e. la taille du tableau elements) de sa taille logique (i.e. son nombre d'éléments), la seconde étant toujours inférieure ou égale à la première.