Bibliothèque de gestion des piles dynamiques en c

Soyez le premier à donner votre avis sur cette source.

Vue 10 004 fois - Téléchargée 565 fois

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 !

Codes Sources

A voir également

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.