[code] listes chaînées, piles, files
, par
Un exemple d’utilisation des listes simplement chaînées pour implémenter les piles et les files (cours du 22 mars 2010). Les choix d’implémentation et des alternatives (parfois meilleures) ont été discutées pendant le cours. L’objectif était surtout de montrer les difficultés concrètes et l’importance de faire un croquis avant de coder.
- #include <stdlib.h>
- #include <stdio.h>
- #include <errno.h>
- /* Definir le type des listes chainees */
- typedef int element_t;
- typedef struct cellule_s {
- element_t e;
- struct cellule_s *suivant;
- } cellule_t, *liste_t;
- typedef liste_t pile_t;
- typedef struct {
- liste_t debut;
- liste_t fin;
- } *file_t;
- /* fonctions de base sur les listes */
- liste_t nouvelleListe() {
- return NULL;
- }
- liste_t ajouterListe(element_t e, liste_t l) {
- liste_t y;
- /* creer cellule pour e*/
- if (y == NULL) {
- }
- /* mettre la cellule en tete de l */
- y->e = e;
- y->suivant = l;
- /* retourner la nouvelle liste */
- return y;
- }
- int estVideListe(liste_t l) {
- return (l == NULL);
- }
- element_t teteListe(liste_t l) {
- if (estVideListe(l)) {
- }
- return l->e;
- }
- liste_t retirerTeteListe(liste_t l) {
- liste_t garbage;
- if (estVideListe(l)) {
- }
- /* effacer la premier cellule */
- garbage = l;
- l = l->suivant;
- return l;
- }
- liste_t rechercherListe(element_t a, liste_t l) {
- while ((!estVideListe(l)) && (teteListe(l) != a)) {
- l = l->suivant;
- }
- return l;
- }
- /* les piles */
- pile_t nouvellePile() {
- return nouvelleListe();
- }
- int estVidePile(pile_t p) {
- return estVideListe(p);
- }
- void empiler(element_t e, pile_t *pp) {
- *pp = ajouterListe(e, *pp);
- }
- element_t depiler(pile_t *pp) {
- element_t e;
- e = teteListe(*pp);
- *pp = retirerTeteListe(*pp);
- return e;
- }
- element_t sommet(pile_t p) {
- return teteListe(p);
- }
- /* Files */
- file_t nouvelleFile() {
- file_t f;
- if (f == NULL) {
- }
- f->debut = nouvelleListe();
- f->fin = f->debut;
- return f;
- }
- int estVideFile(file_t f) {
- return estVideListe(f->debut);
- }
- element_t teteFile(file_t f) {
- if (estVideFile(f)) {
- }
- return teteListe(f->debut);
- }
- void insererFile(element_t e, file_t f) {
- liste_t x;
- if (x == NULL) {
- }
- x->e = e;
- x->suivant = NULL;
- if (estVideFile(f)) {
- f->debut = x;
- f->fin = x;
- } else {
- (f->fin)->suivant = x;
- f->fin = x;
- }
- }
- element_t retirerFile(file_t f) {
- element_t e;
- if (estVideFile(f)) {
- }
- e = (f->debut)->e;
- if (f->debut == f->fin) {/* un seul element dans la file */
- f->debut = NULL;
- f->fin = NULL;
- } else {
- liste_t x;
- x = f->debut;
- f->debut = x->suivant;
- }
- return e;
- }
- /* afficher */
- void afficherListe(liste_t l) {
- while (!estVideListe(l)) {
- l = l->suivant;
- }
- }
- void afficherPile(pile_t p) {
- afficherListe(p);
- }
- void afficherFile(file_t f) {
- afficherListe(f->debut);
- }
- int main() {
- liste_t l;
- pile_t p;
- file_t f;
- l = nouvelleListe();
- l = ajouterListe(100, l);
- l = ajouterListe(200, l);
- l = ajouterListe(300, l);
- l = ajouterListe(400, l);
- afficherListe(l);
- l = retirerTeteListe(l);
- afficherListe(l);
- p = nouvellePile();
- empiler(100, &p);
- empiler(200, &p);
- empiler(300, &p);
- empiler(400, &p);
- afficherPile(p);
- depiler(&p);
- afficherPile(p);
- f = nouvelleFile();
- insererFile(100, f);
- insererFile(200, f);
- insererFile(300, f);
- insererFile(400, f);
- afficherFile(f);
- retirerFile(f);
- afficherFile(f);
- return EXIT_SUCCESS;
- }