Lorsque l'on a plusieurs listes à gérer simultanément et que ces listes peuvent contenir des éléments en commun, se pose le problème de traiter ce partage si l'on veut éviter de simplement duplifier l'information à mettre en commun. L'approche la plus souple et qui ne limite pas le nombre de listes auxquelles un élément peut appartenir consiste à mettre le contenu des atomes en dehors de la structure de liste. Chaque noeud de la liste pointe soit vers une sous-liste, soit vers un atome. Cela peut s'illustrer de la manière suivante :
Fig. 9.3 Partage d'éléments par plusieurs listes
Dans l'exemple ci-dessus, les deux listes ont deux éléments en commun : un atome et une sous-liste.
Le problème principal lié à cette approche a trait à la suppression d'éléments dans une des listes. En effet, la suppression d'un élément d'une liste ne doit s'accompagner de la destruction de cet élément que si cet élément n'est pas partagé par une autre liste. Dans le même ordre d'idée, la destruction d'une liste ne doit impliquer que la destruction des éléments de cette liste qui ne sont pas partagés par d'autres.
Pour ce faire, il faut associer à chaque objet susceptible d'être partagé (atome ou sous-liste) un compteur de références qui indique le nombre de références à cet objet. Chaque fois qu'un objet est supprimé d'une liste, son compteur de références est décrémenté. Seul un objet dont le compteur de références est à zéro sera effectivement détruit.
La solution consistant à gérer un compteur de
références n'est pas toujours suffisante. Dans le cas de listes
récursives, le compteur de références de la liste ne
sera jamais à zéro puisque la liste fait référence
à elle-même. Si le cas de listes récursives peut se
présenter, il faudra, lors du ramassage des miettes, parcourir à
nouveau toutes les listes existantes et marquer les objets
référencés pour ensuite dé truire tous les objets
qui n'ont pas été marqués
9.4. Isomorphisme
liste-arbre
Site Hosting: Bronco
Table des
matières.