Accueil > Enseignement > Anciens cours (avant 2015-2016) > Algorithmique et arbres (L2 cours/TD 2005-2011) > [code] listes chaînées, piles, files

[code] listes chaînées, piles, files

mardi 23 mars 2010, par Pierre

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*/
    y = malloc(sizeof(*y));
    if (y == NULL) {
	perror("plus de memoire ??");
    }
    /* 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)) {
	perror("Exception : tete sur liste vide");
    }
    return l->e;
}
 
liste_t retirerTeteListe(liste_t l) {
    liste_t garbage;
    if (estVideListe(l)) {
	perror("Exception : retirer tete sur liste vide");
    }
    /* effacer la premier cellule */
    garbage = l;
    l = l->suivant;
    free(garbage);
    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;
    f = malloc(sizeof(*f));
    if (f == NULL) {
	perror("Memoire !");
    }
    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)) {
	perror("Exception: tete sur file vide");       
    }
    return teteListe(f->debut);
}
 
void insererFile(element_t e, file_t f) {
    liste_t x;
    x = malloc(sizeof(*x));
    if (x == NULL) {
	perror("Memoire.. pas content");
    }
    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)) {
	perror("Exception: retrait dans une file vide");
    }
    e = (f->debut)->e;
    if (f->debut == f->fin) {/* un seul element dans la file */
	free(f->debut);
	f->debut = NULL;
	f->fin = NULL;
    } else {
	liste_t x;
	x = f->debut;
	f->debut = x->suivant;
	free(x);
    }
    return e;
}
 
/* afficher */
void afficherListe(liste_t l) {
    while (!estVideListe(l)) {
	printf("%d::", l->e);
	l = l->suivant;
    }
    printf("\n");
}
 
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;
}