TP 2 : Listes chaînées

En attendant que Binder remarche, vous pouvez utiliser un compilateur C online. Par exemple : https://replit.com/languages/c

Pensez à revoir le cours sur les pointeurs et les structures si besoin.

On implémente dans ce TP des listes chaînées en C. En voici la définition :

In [1]:

typedef struct list {
    list* next;
    int elem;
} list;

typedef struct list { list* next; int elem; } list;

Ajout et création¶

Exercice

Écrire une fonction permettant d'ajouter un élément dans une liste chaînée avec le prototype suivant :

list* add(list* l, int e)

Cette fonction prend un pointeur l sur le début (premier noeud) d'une liste et renvoie un pointer l_new sur le noeud ajouté avant l, comme sur le dessin suivant :

Solution

In [2]:

list* add(list* l, int e) {
    list* l_new = (list*)malloc(sizeof(list));
    l_new->next = l;
    l_new->elem = e;
    return l_new;
}

list* add(list* l, int e) { list* l_new = (list*)malloc(sizeof(list)); l_new->next = l; l_new->elem = e; return l_new; }

Exercice

Écrire une fonction range qui renvoie une liste contenant les entiers de 0 à n - 1 :

list* range(int n);

Solution

In [3]:

list* range(int n) {
    list* res = NULL;
    // on fait un for à l'envers pour que les éléments soient dans le bon sens
    for(int i = n - 1; i > -1; i--)
        res = add(res, i);
    return res;
}

list* range(int n) { list* res = NULL; // on fait un for à l'envers pour que les éléments soient dans le bon sens for(int i = n - 1; i > -1; i--) res = add(res, i); return res; }

Parcours de liste¶

Exercice

Écrire une fonction print_list affichant les éléments d'une liste chainée :

void print_list(list* l);

Solution

In [4]:

void print_list(list* l) {
    while(l != NULL) {
        printf("%d ", l->elem);
        l = l->next;
    }
}

list* l = range(6);
print_list(l);

void print_list(list* l) { while(l != NULL) { printf("%d ", l->elem); l = l->next; } } list* l = range(6); print_list(l);

0 1 2 3 4 5 

Exercice

Écrire une fonction has pour savoir si un élément appartient à une liste chaînée :

bool has(list* l, int e);

Solution

In [5]:

bool has(list* l, int e) { // version récursive
    if(l == NULL)
        return false;
    return l->elem == e || has(l->next, e);
}

has(l, 3) && not has(l, 7) // test

bool has(list* l, int e) { // version récursive if(l == NULL) return false; return l->elem == e || has(l->next, e); } has(l, 3) && not has(l, 7) // test

Out[5]:

true

Exercice

Écrire une fonction size pour connaître la taille d'une liste chainée :

unsigned size(list* l);

Solution

In [24]:

unsigned size(list* l) {
    if(l == NULL)
        return 0;
    return 1 + size(l->next);
}

size(l)

unsigned size(list* l) { if(l == NULL) return 0; return 1 + size(l->next); } size(l)

Out[24]:

5

Libérer la mémoire¶

Exercice

Écrire une fonction free_list permettant de supprimer du tas (avec free) tous les noeuds d'une list.

Solution

In [7]:

void free_list(list* l) {
    if(l != NULL) {
    list* next = l->next; // on aura plus accès à l->next après free(l)
    free(l);
    free_list(next);
    }
}
list* l = range(5);
free_list(l);

void free_list(list* l) { if(l != NULL) { list* next = l->next; // on aura plus accès à l->next après free(l) free(l); free_list(next); } } list* l = range(5); free_list(l);

Inverse¶

Exercice

Écrire une fonction reverse pour inverser l'ordre des éléments d'une liste. On renverra un pointeur sur le premier élément de la liste inversé (qui est aussi le dernier élément de la liste en argument).

list* reverse(list* l);

Solution

In [11]:

// version itérative, en créant une nouvelle liste
// cela revient à copier une pile dans une autre pile, ce qui l'inverse
list* reverse(list* l) {
    list* res = NULL;
    while(l != NULL) {
        res = add(res, l->elem);
        l = l->next;
    }
    return res;
}
list* l = range(5);
print_list(reverse(l))

// version itérative, en créant une nouvelle liste // cela revient à copier une pile dans une autre pile, ce qui l'inverse list* reverse(list* l) { list* res = NULL; while(l != NULL) { res = add(res, l->elem); l = l->next; } return res; } list* l = range(5); print_list(reverse(l))

4 3 2 1 0 

Solution

In [12]:

// version itérative, en modifiant la liste en argument
// on parcourt tous les noeuds de la liste avec l
// prev est le noeud avant l (qui devient donc le next de l)
list* reverse(list* l) {
    list* prev = NULL;
    while(l != NULL) {
        list* tmp = l->next;
        l->next = prev;
        prev = l;
        l = tmp;
    }
    return prev;
}
print_list(reverse(range(5)))

// version itérative, en modifiant la liste en argument // on parcourt tous les noeuds de la liste avec l // prev est le noeud avant l (qui devient donc le next de l) list* reverse(list* l) { list* prev = NULL; while(l != NULL) { list* tmp = l->next; l->next = prev; prev = l; l = tmp; } return prev; } print_list(reverse(range(5)))

4 3 2 1 0 

Solution

In [13]:

// version récursive, en modifiant la liste en argument (assez difficile)
list* reverse2(list* l) {
    if(l == NULL || l->next == NULL)
        return l;
    list* snd = l->next;
    list* last = reverse2(l->next);
    l->next = NULL;
    snd->next = l;
    return last;
}

print_list(reverse2(range(5)))

// version récursive, en modifiant la liste en argument (assez difficile) list* reverse2(list* l) { if(l == NULL || l->next == NULL) return l; list* snd = l->next; list* last = reverse2(l->next); l->next = NULL; snd->next = l; return last; } print_list(reverse2(range(5)))

4 3 2 1 0