Les listes chainées sont des structures informatiques permettant de mémoriser des informations de manière flexible et efficace. En effet, elles sont :
Cependant leur manipulation s’avère un peu plus complexe que les tableaux. En effet, les données ne sont pas mémorisées de manière contiguë en mémoire. Vous allez dans le cadre de ce TP expérimenter les mécanismes permettant de manipuler de telles structures afin de vous faire votre propre idée sur le sujet.
Il existe plusieurs manières d’implémenter des listes chaînés, nous vous en
proposons une version simple. Les listes chainées sont constituées d’éléments
mémoire non contigus (maillons de la chainés link_t
) et d’un en-tête
(list_t
) qui représentera la liste proprement dite. Dans cette version très
minimale, l’en-tête ne sera constitué que d’un pointeur vers le début de la
chaine des maillons.
Chaque maillon est une paire, qui stocke : une valeur et la
suite de la liste (c’est-à-dire, le maillon suivant) ou rien (pointeur
NULL
) si c’est le dernier maillon. Une telle liste est dite “simplement
chaînée”, les maillons ne connaissent que leur successeurs.
Pour représenter la liste (list_t
) et les maillons (link_t
), nous
utiliserons les structures suivantes :
struct list_t {
struct link_t *head;
};
struct link_t {
double value;
struct link_t* next;
};
Remarquez le type du champs suivant (next
). Peut-on ignorer le fait que c’est
un pointeur ?
Bien que les opérations de manipulation d’une liste puissent être plus
compliquée à réaliser que les mêmes opérations sur un tableau (ce n’est pas le
cas pour toutes les opérations), l’utilisateur final ne doit pas s’en rendre
compte. Pour cela nous appliquons le principe de séparation des préoccupations
en introduisant un Type abstrait de donnée. L’idée est que l’utilisateur
manipule des listes comme une boîte noire (il ne sait pas ce qu’il y a dedans),
et ne se sert que des fonctions mises à disposition par le programmeur du type
(dans ce TP, bien entendu, il s’agit de vous dans les deux cas). Les opérations
de manipulations sont exposés via un fichier d’en-tête (.h
),
l’implémentation proprement dite des opérations et des types se fait fans un
fichier C classique (.c
). Voir les slides associées.
Dans ce TP vous allez devoir développer des fonctions permettant de créer, modifier et afficher une liste chainée. Vous porterez une attention particulière à bien tester votre code. Vous penserez aussi à utiliser des assertions lorsque cela est nécessaire.
Dans un dossier dédié au TP, créez les fichiers : list.h
, list.c
et
test-list.c
. Le contenu du fichier list.h
vous est donnée à la fin du texte
du TP. Enfin rajoutez un fichier Makefile
contenant les lignes suivantes
(Attention rm
est précédé d’une tabulation et non d’espaces). Compilez
(make
) et testez ! Pourquoi votre programme ne compile pas ? Remédiez à ce
problème.
CFLAGS=-std=c99 -Wall
test-list: test-list.o list.o
clean:
rm -f *.o test-list
Écrivez le corps des fonctions list_empty()
, qui initialise une liste
(donc vide), et le prédicat is_list_empty
qui répond 1 si la liste et
vide, 0 sinon. Testez ces deux fonctions à l’aide d’un programme (main
).
void list_empty(struct list_t* list)
{
return (*list).head = NULL;
}
int is_list_empty(struct list_t* list)
{
return list->head == NULL; // cf slide Structures et pointeurs
}
Écrivez la fonctions struct link_t* new_node(double value, struct link_t*
next)
, qui alloue1 un nouveau maillon de liste, et list_push()
qui
insère un élément au début d’une liste. Les deux fonctions doivent elles êtres
accessibles par votre utilisateur ? Comment s’assurer que l’utilisateur ne
puisse pas s’en servir2. Améliorez votre main
pour tester ces
fonctions.
void exemple()
{
struct link_t *new = malloc(sizeof(struct link_t));
// ...
}
Développez une fonction nommée list_length()
qui retourne le nombre
d’éléments contenus dans la liste. Testez cette nouvelle fonction.
Développez la fonction void print_node(struct link_t* l)
qui affiche les
informations relatives à un élément de la liste (son adresse en mémoire, la
valeur qu’il contient et l’adresse de l’élément suivant). Écrivez ensuite la
fonction list_print()
qui affiche les mêmes informations pour tous les
maillons constituant la liste. Testez bien évidemment ces fonctions.
Écrivez les fonctions list_head()
et list_tail()
qui retournent
respectivement le premier et le dernier maillon de la liste. Développez une
fonction nommée list_get()
qui permet de récupérer un pointeur sur le nième
maillon de la liste chainée. Testez cette nouvelle fonction.
Développez deux fonctions nommées list_node_before()
et
list_node_after()
qui permettent respectivement de récupérer le pointeur sur
l’élément précédent ou suivant d’un maillon spécifique. Testez ces deux
nouvelles fonctions.
Développez la fonction list_insert
et list_append()
qui permettent
d’ajouter un élément respectivement, avant et après un nœud donnée. Testez ces
fonctions.
Développez une fonction nommée remove()
qui permet de supprimer l’élément
e
de la liste chainée. Testez cette nouvelle fonction.
Développez une fonction nommée list_clear()
qui permet de supprimer
l’ensemble des éléments contenus dans la liste chainée3. Testez cette
nouvelle fonction.
Variations autour de la liste simplement chainée. (Plutôt pour réfléchir)
tail
). Rajoutez ce
pointeur et changer les fonctions qui pourraient en tirer parti.Nos types sont dédiés aux nombres double
s. Le C ne permet pas de simplement
de généraliser ces listes à tous les types. Cependant il est possible de
généraliser à tous les types pointeurs. Pour cela, on peut se servir du type
polymorphe void *
. Généraliser votre liste pour qu’elle gère tous les types
de pointeurs. Essayer de faire une liste d’iris struct iris {int petal_width,
petal heigth; int sepal_width, sepal_height; };
. Un problème se pose pour les
fonctions d’affichages ? Que faudrait il faire pour que tous les types
structurés s’affichent correctement4 ?
Comme vous avez pu le constater, les listes chainées permettent facilement l’ajout et la suppression d’informations dans un ensemble déjà existant. Toutefois certaines opérations comme l’accès à l’élément précédent requièrent le parcours complet de la liste. Afin de pallier à ce problème, une évolution de la liste “simplement” chainée a été proposée, il s’agit de la liste “doublement” chainée. Dans cette version, les maillons possèdent un pointeur vers leur successeur mais aussi sur leur prédécesseur. Cela permet de minimiser le nombre d’opérations lorsqu’on recherche par exemple l’élément précédant.
list.h
#ifndef LIST_H
# define LIST_H
struct list_t {
struct link_t *head;
};
struct link_t {
double value;
struct link_t* next;
};
void list_empty(struct list_t* lst);
int is_list_empty(struct list_t* lst);
// Ajoute en tête de liste
void list_push(double v, struct list_t* lst);
// Affiche le contenu de la liste
void list_print(struct list_t* e);
// Retourne la taille de la liste
int list_length(struct list_t* lst);
// Ajoute un élement après `node`
void list_append(double v, struct list_t* lst, struct link_t *node);
// Ajoute un élement avant `node`
void list_insert(double v, struct list_t* lst, struct link_t *node);
// retourne le premier élément
struct link_t* list_head(struct list_t* lst);
// retourne le dernier élément d'une lst
struct link_t* list_tail(struct list_t* lst);
// Retourne le n-ème element de la liste
struct link_t* list_get(struct list_t* lst, int n);
// Retourne le noeud précédent `r` dans la liste `lst`
struct link_t* node_before(struct list_t* lst, struct link_t* r);
// Retourne le noeud suivant `e` dans la liste `lst`
struct link_t* node_after(struct list_t* lst, struct link_t* e);
// Retire le noeud `e` de la liste `lst`
void list_remove(struct list_t* lst, struct link_t* e);
// Vide toute la liste
void list_clear(struct list_t* lst);
#endif
Allouer consiste à demander un bloc de mémoire (provenant du tas) pour notre programme (malloc()
). Pourquoi doit on allouer une nouvelle mémoire dans ce cas la ? ↩
Le modificateur static
appliqué à une fonction, consiste à dire : cette fonction n’est pas exportée quoi qu’il arrive. Pourquoi ce n’est pas suffisant d’omettre le prototype dans le .h
↩
La fonction inverse de malloc
est free
. Trois règles sont à toujours respecter : Chaque bloc alloué doit être restitué (pas de fuite mémoire), et ce, une seule fois (pas de double free
), enfin le pointeur restitué doit être le même que celui fourni par malloc
(pas de décalage). ↩
Comme en mathématique pour les fonctions d’ordres supérieurs, en informatique il est possible de passer des fonctions à des fonctions. En C cela se traduit par un pointeur de fonction. Pour une fonction prenant un int
et retournant un int
, le type associés est int (* foo) (int)
où foo
est le nom du paramètre ou de la variable. L’utilisation d’un tel pointeur en tant que fonction est d’une simplicité absolue : foo(42)
. ↩