Bibliothèque de gestion des piles dynamiques en c

Télécharger le projet
Commenter

Description

(Plus de détails sur mon site : http://perso.orange.fr/beorn/progra_c/pile_dynamique.html )

Les fichiers pile.c et pile.h forment une bibliotheque permettant de gérer des piles dynamiques.

Le type utilisé pour les piles est "pile_t".
La pile est dite dynamique car de nouveaux tableaux sont alloués pour le stockage des éléments au fur et à mesure des besoins. La pile possède donc un nombre d'éléments théoriquement illimité.

Les différentes fonctions sont :
- vide : vaut 1 si la pile est vide, 0 sinon
- init : alloue une pile en mémoire (le paramètre de cette fonction est la taille d'allocation des tableaux/sections de la pile) et renvoie son adresse
- empile : permet d'empiler un nouvel élément sur la pile
- depile : dépile le dernier élément rajouté (renvoie 1 si la pile est vide, 0 sinon)
- supprime : libère tout l'espace mémoire utilisé par une pile

Plus de précisions dans les commentaires... :-)

Vous trouverez dans le .zip un petit main.c utilisant la bibliothèque et faisant deux ou trois manipulations élémentaires...
Pour ceux qui utilisent Dev-C++, vous avez même le fichier .dev correspondant.

Source / Exemple : 


pile.h :

#ifndef _pile_h_
#define _pile_h_

#include <stdlib.h>

typedef int variant; /* remplacer int par le type de donnees a empiler */

/*---------------- STRUCTURES DE PILE.C --------------------------------------------*/

/*
  Structure :
  Nom  :  section
  Fct  :  structure definissant une section d'elements de type "variant"


  • /


typedef struct section
{
  variant * tab;     /* tableau representant la section proprement dite */
  struct section * suiv;  /* pointeur sur la section suivante */
  struct section * prec;  /* pointeur sur la section precedente */
} section_t;

/*
  Structure :
  Nom  :  pile
  Fct  :  structure definissant une pile d'elements de type "variant"


  • /


typedef struct pile
{
  int n;             /* nombre d'elements presents dans la pile moins un */
  int pas;           /* nombre d'elements dans une section de pile */
  section_t * tete;  /* pointeur de tete de la pile */
  section_t * sect;  /* pointeur sur la dernière section ajoutée */
} pile_t;

/*---------------- FONCTIONS DE PILE.C ---------------------------------------------*/

/*
  Nom  :  vide
  Fct  :  retourne un booleen indiquant si la pile est vide
  Entree  :  (p) adresse de la pile
  Sortie  :  booleen indiquant que la pile est vide


  • /


unsigned short int vide(pile_t * p);

/*
  Nom  :  init
  Fct  :  cree une nouvelle pile et retourne son adresse
  Entree  :  (maxi) nombre maximal d'elements de la pile
  Sortie  :  adresse de la nouvelle pile


  • /


pile_t * init(int pas);

/*
  Nom  :  empile
  Fct  :  empile un nouvel element sur la pile
  Entree  :  (p) adresse de la pile
             (x) element a rajouter


  • /


void empile(pile_t * p, variant x);

/*
  Nom  :  depile
  Fct  :  depile un element de la pile et renvoie un booleen indiquant que tout s'est bien passe
  Entree  :  (p) adresse de la pile
             (x) adresse de stockage de l'element depile
  Sortie  :  booleen indiquant que tout s'est bien passe


  • /


unsigned short int depile(pile_t * p, variant * x);

/*
Nom  :  supprime
Fct  :  libère toute la mémoire occupée par une pile
Entree  :  (p) adresse de la pile


  • /


void supprime(pile_t * p);

#endif

pile.c :

#include "pile.h"

/*
  Nom  :  vide
  Fct  :  retourne un booleen indiquant si la pile est vide
  Entree  :  (p) adresse de la pile
  Sortie  :  booleen indiquant que la pile est vide


  • /


unsigned short int vide(pile_t * p)
{
  return ((p->n) == -1); /* la pile est vide si n = -1 */
}

/*
  Nom  :  init
  Fct  :  cree une nouvelle pile et retourne son adresse
  Entree  :  (pas) nombre d'elements d'une section de la pile
  Sortie  :  adresse de la nouvelle pile


  • /


pile_t * init(int pas)
{
  pile_t * adr_pile = NULL; /* l'adresse de la pile est NULL si l'allocation echoue */
  
  adr_pile = (pile_t *)malloc(sizeof(pile_t)); /* adresse de la pile cree */
  if ( adr_pile )
  {
    adr_pile->n = -1;       /* nombre d'elements presents (aucun) */
    adr_pile->pas = pas;    /* nombre d'elements par section */
    adr_pile->tete = NULL;  /* la pile est vide */
    adr_pile->sect = NULL;  /* la pile est vide */
  }
  
  return adr_pile;
}

/*
  Nom  :  empile
  Fct  :  empile un nouvel element sur la pile
  Entree  :  (p) adresse de la pile
             (x) element a rajouter


  • /


void empile(pile_t * p, variant x)
{
  if ( vide(p) )  /* si la pile est vide */
  {
    p->tete = (section_t *)malloc(sizeof(section_t));              /* creation d'une premiere section */
    p->sect = p->tete;
    p->sect->tab = (variant *)malloc((p->pas) * sizeof(variant));  /* allocation de la nouvelle section */
    p->sect->suiv = NULL;                                          /* pas de section suivante */
    p->sect->prec = NULL;                                          /* pas de section precedente */
  }
  else
  {
    if (!((p->n + 1) % (p->pas)))  /* si la section est pleine */
    {
      p->sect->suiv = (section_t *)malloc(sizeof(section_t));        /* rajout d'une nouvelle section */
      p->sect->suiv->prec = p->sect;                                 /* maj section precedente */
      p->sect = p->sect->suiv;                                       /* maj derniere section */
      p->sect->tab = (variant *)malloc((p->pas) * sizeof(variant));  /* allocation de la nouvelle section */
      p->sect->suiv = NULL;                                          /* pas de section suivante */
    }
  }
  p->n = p->n + 1;                          /* incrementation du nombre d'elements */


      
  • (p->sect->tab + (p->n) % (p->pas)) = x;  /* rajout du nouvel element sur la pile */

}

/*
  Nom  :  depile
  Fct  :  depile un element de la pile et renvoie un booleen indiquant que tout s'est bien passe
  Entree  :  (p) adresse de la pile
             (x) adresse de stockage de l'element depile
  Sortie  :  booleen indiquant que tout s'est bien passe


  • /


unsigned short int depile(pile_t * p, variant * x)
{
  unsigned short int succes = 0;
  
  if ( !vide(p) )
    {


          
  • x = *(p->sect->tab + (p->n) % (p->pas)); /* sortie du dernier element rajoute */

      p->n = p->n - 1;  /* decrementation du nombre d'elements */
      if (!((p->n + 1) % (p->pas)))  /* si la section est vide */
      {
        if ( p->sect->prec != NULL )  /* s'il y a au moins une section */
        {
          p->sect = p->sect->prec;  /* mise a jour de la derniere section */
          free(p->sect->suiv);      /* liberation de la derniere section */
          p->sect->suiv = NULL;     /* pas d'element suivant sur la derniere section */
        }
        else
        {
          free(p->tete);  /* liberation de la section */
          p->sect = NULL; /* raz du pointeur de derniere section */
        }
      }
      succes = 1;  /* marquage de la reussite */
    }
  return succes;
}

/*
Nom  :  supprime
Fct  :  libère toute la mémoire occupée par une pile
Entree  :  (p) adresse de la pile


  • /


void supprime(pile_t * p)
{
  section_t * cour = p->tete, * suiv;
  if ( cour != NULL )  /* s'il existe au moins une section */
  {
    suiv = p->tete->suiv;
    while ( cour != NULL )  /* tant qu'il reste des sections non supprimees */
    {
      suiv = cour->suiv;  /* progression du pointeur suivant */
      free(cour->tab);    /* liberation du contenu de la section courante */
      free(cour);         /* liberation de la section courante */
      cour = suiv;        /* progression du pointeur courant */
    }
  }
  free(p);  /* liberation de la structure pile */
}

Conclusion :


C'est je pense la version finale de mon code.

L'originalité ici est que lorsque la pile est pleine, on alloue un nouveau tableau : plus de limitation en taille !
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_Sunglasses)