Chapitre 5 : Listes chainées

Illustration

1 éléments contient :

• 1 valeur

• 1 pointeur vers un autre élément

NULL : liste vide

---

Definition

Une liste chainée représente une liste de valeurs. Chaque valleur rst écrite à côté de l’adresse de la prochaine valeur. Il faut une convention pour représenter une liste vide.

---

En C :

typedef struct _cel_t{
    int v; //valeur
    (struct _cel_t)* s; //adresse cellule suivante
} cellule_t;
struct _cel_t a;
a.v = 0;
struct _cel_t b;
a.s = &b;
cellule_t c; // struct _cel_t c;

---

#include<stdlib.h>
cellule_t* allouerCellule(int v, cellule_t* bs){
    cellule_t* r = (cellule_t*) malloc(sizeof * bs); //ou malloc(sizeof(cellule_t));
    if (r ==  NULL){
        exit(1);
    }
    (*r).v = v;
    (*r).s = bs; //ou r->s = bs;
    return r;
}

---

cellule_t* l = NULL;
l = allouerCellule(3,l);
l = allouerCellule(2,l);
l = allouerCellule(1,l);
afficherListe(l) ; //1 2 3 \n

typedef int entier[3]
entier.c; //int c[3]

void afficherListe(cellule_t* i){
    while (i !=NULL){
        printf("%d" ,(*i).v);
        i = i->s; //i = (*i).s;
    }
    printf("\n") ;
}

void libererListe((cellule_t*)* ini){
    if (*ini == NULL) return;
    libererListe(&(*ini)->s); //ou (&(*(*ini)).s);
    free(*ini);
    *ini = NULL;
}