GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Implémentation d'une Pile en C ======

===== Stratégie utilisant un tableau =====

On se contente d'une pile d'entiers.

La structure naturelle est le tableau. Mais le tableau a une taille fixe en C alors qu'une pile devrait avoir une taille variable. On pourrait créer un tableau de taille suffisamment grande pour stocker notre pile.

<code lang-none linenums>
pile vide : [?, ?, ?, ?, ...]
empiler 15 : [15, ?, ?, ?, ...]
empiler 28 : [15, 28, ?, ?, ...]
empiler 34 : [15, 28, 34, ?, ...]
dépiler : [15, 28, ?, ?, ...] et renvoie 34
</code>

Puisque cette pile est constituée d'un tableau contenant toujours des entiers, il faut savoir où se trouve le dessus de la pile. On pourrait décider que le dernier élément du tableau contient toujours la taille de la pile.

<code lang-none linenums>
pile vide : [?, ?, ?, ?, ..., 0]
empiler 15 : [15, ?, ?, ?, ..., 1]
empiler 28 : [15, 28, ?, ?, ..., 2]
empiler 34 : [15, 28, 34, ?, ..., 3]
dépiler : [15, 28, ?, ?, ..., 2] et renvoie 34
</code>

==== Création de la pile ====

  * il faut définir une constante ''%%N%%'', par exmple 1000 qui fixe la taille maximale de la pile,
  * définir un tableau d'entiers de taille ''%%N + 1%%'',
  * écrire ''%%0%%'' dans la dernière case du tableau.

Je rappelle que la variable qui résulte de la création d'un tableau de ''%%int%%'' contient l'adresse mémoire de la première case du tableau. Il s'agit d'un pointeur sur entier donc un ''%%int *%%''.

La fonction ''%%CREER_PILE_VIDE()%%'' renvoie donc un ''%%int *%%''.

On pourrait penser que ce ci convient
<Code:C>
#define N 1000

int *CREER_PILE_VIDE()
{
    int tableau[N+1];
    tableau[N] = 0;
    return tableau;
}
</Code>

Mais non, comme c'est expliqué [[..:malloc|ici]].

On est obligé de faire ceci :

<Code:C>
#define N 1000

int *CREER_PILE_VIDE()
{
    int *tableau = malloc((N+1)*sizeof(int));
    if (tableau == NULL)
    {
        printf("Erreur création pile.\n");
        exit(1);
    }
    tableau[N] = 0;
    return tableau;
}
</Code>

Le ''%%malloc%%'' a pour effet que l'espace mémoire réservé pour le tableau n'est pas libéré à la fin de la fonction. Il faudra penser à libérer cet espace quand on libérera la pile, on ajoute donc la fonction :

<Code:C>
void FREE_PILE(int *p)
{
    free(p);
}
</Code>

<WRAP tip>**Deux remarques :**
  * L'utilisation de ''%%malloc%%'' empêche ce programme de fonctionner avec un compilateur C++. Si vous utilisez C playground, pensez à configurer avec un compilateur C.
  * Certains compilateurs peuvent être gênés par le fait que l'on pourrait très bien écrire une déclaration comme ''%%int* truc = malloc((N+1)*sizeof(float))%%'' dans laquelle les parties gauche et droite ne coïncide pas.\\ Une solution est décrire ''%%int *truc = malloc((N+1)*sizeof(*truc))%%'' de sorte qu'il y a forcément correspondance des deux côtés.\\ On pourra donc écrire <code c>
int *tableau = malloc((N+1)*sizeof(*tableau));
</code>
</WRAP>

==== Autres fonctions ====

Le reste est beaucoup plus simple et direct.

<Code:C>
void EMPILER(int *p, int e)
{
    int s = p[N];
    if (s == N)
    {
        printf("Erreur : Pile pleine.\n");
        exit(1);
    }
    p[s] = e;
    p[N] = s + 1;
}

int DEPILER(int *p)
{
    int s = p[N];
    if (s == 0)
    {
        printf("Erreur : Pile vide.\n");
        exit(1);
    }
    int e = p[s-1];
    p[N] = s - 1;
    return e;
}

int EST_VIDE(int *p)
{
    if (p[N] == 0)
    {
        return 1;
    }
    return 0;
}

int EST_PLEINE(int *p)
{
    if (p[N] == N)
    {
        return 1;
    }
    return 0;
}
</Code>

==== Utilisation typedef ====

On constate que dans l'ensemble du programme, on utilise ''%%int*%%'' pour notre pile ce qui est lié au fait que notre pile est un tableau d'entiers. Pour rendre les choses plus claires, on peut définir une étiquette pour ''%%int*%%'' :

<Code:c>
typedef int* Pile;
</Code>

Ainsi, toutes les occurrences de ''%%int *%%'' ou ''%%int*%%'' pourront être remplacées par ''%%Pile%%''.

==== Fichier final ====

Avec un exemple d'utilisation

<Code:c>
#include <stdio.h>
#include <stdlib.h>

#define N 1000

typedef int* Pile;

Pile CREER_PILE_VIDE()
{
    Pile p = malloc((N+1)*sizeof(*p));
    if (p == NULL)
    {
        printf("Erreur création pile.\n");
        exit(1);
    }
    p[N] = 0;
    return p;
}

void FREE_PILE(Pile p)
{
    free(p);
}

void EMPILER(Pile p, int e)
{
    int s = p[N];
    if (s == N)
    {
        printf("Erreur : Pile pleine.\n");
        exit(1);
    }
    p[s] = e;
    p[N] = s + 1;
}

int DEPILER(Pile p)
{
    int s = p[N];
    if (s == 0)
    {
        printf("Erreur : Pile vide.\n");
        exit(1);
    }
    int e = p[s-1];
    p[N] = s - 1;
    return e;
}

int EST_VIDE(Pile p)
{
    if (p[N] == 0)
    {
        return 1;
    }
    return 0;
}

int EST_PLEINE(Pile p)
{
    if (p[N] == N)
    {
        return 1;
    }
    return 0;
}

int main()
{
    Pile p = CREER_PILE_VIDE();
    EMPILER(p, 45);
    EMPILER(p, 17);
    EMPILER(p, 19);
    EMPILER(p, 50);
    int x = DEPILER(p);
    printf("%d\n", x);
    x = DEPILER(p);
    printf("%d\n", x);
    FREE_PILE(p);
    return 0;
}
</Code>