Chaînage XOR
Le chaînage XOR est un procédé permettant de parcourir une liste chaînée dans un sens comme dans l'autre en ne gardant dans chaque bloc qu'un seul pointeur au lieu de deux.
La contrepartie est qu'on ne peut cheminer dans la liste qu'en partant de l'une de ses deux extrémités, restriction inexistante dans les listes à double pointeur.
Principe
Le chaînage XOR consiste à remplacer le pointeur aval d'une liste chaînée par un ou exclusif entre l'adresse du bloc aval et celle du bloc amont.
La caractéristique du XOR bit à bit entre deux adresses est que si C = A xor B, alors B = C xor A et A = C xor B. En conséquence, on trouve le pointeur aval à partir de l'adresse amont (d'où l'on vient) dans un sens, et réciproquement de l'autre.
Exemple
Voici un exemple d'implémentation complète en C++ en trois classes.
Classe élément
Une classe élément compte une variable de type entier et un pointeur privé. Elle a comme méthodes régler_p pour régler son pointeur, et obtenir_p() pour obtenir le pointeur suivant ou précédent :
class element
{
public:
int var;
void régler_p(element * p2, element * p3){ p = p2 ^^ p3; }
element * obtenir(element p2){ return p ^^ p2; }
private:
element * p;
};
Classe index
Elle possède une méthode principale déplacer() qui permet de le faire se déplacer. Pour cela, elle a trois champs: un bool pour savoir dans quelle direction va l'index, un pointeur p et un pointeur p_prc indiquent respectivement sa position actuelle et sa position précédente.
class index
{
protected:
bool direction; // S'il avance direction = true
element * p, p_prc;
public:
index():p(NULL){}
int lire(){return p->var;}
void modifier(int n){p->var = n;}
void initialiser(element * d) // Il s'initialise au début
{
p_prc = NULL;
direction = true;
p = d;
}
void déplacer(bool d)
{
element * c = p;
if(direction != d)
{
p = p_prc;
p_prc = c;
direction = d;
}
p = p->obtenir_p(p_prc);
if(p == NULL)
p = c;
else
p_prc = c;
}
};
Classe chaine_xor
Une classe chaîne_xor se charge de coordonner le tout. Elle a deux champs de type element *: début et fin[1]. De plus, elle possède un index:
class chaine_xor
{
protected:
element * début, fin;
index i;
public:
chaîne_xor()
{
début = NULL;
fin = NULL;
i.index();
}
};
Une méthode empiler(int var) ajoute un élément à la fin:
void empiler(int var)
{
element * c = new element();
c->var = var;
c->régler_p(fin, NULL);
fin = c;
if(début == NULL) // Si c'est le premier élément
{
début = c;
i.initialiser(c);
}
}
Les méthodes déplacer_index(bool dir), lire_index() et modifier_index(int n) se chargent de manipuler les données à l'intérieur de la chaîne:
void déplacer_index(bool dir){i.déplacer(dir);}
int lire_index(){return i.lire;}
void modifier_index(int n){i.modifier(n);}
Usage
La baisse progressive des coûts de la mémoire vive des ordinateurs conduit aujourd'hui (2009) à négliger ce procédé, excepté sur les systèmes embarqués où la contrainte de place mémoire conserve une grande importance.
Notes et références
- Note: une chaîne xor peut fonctionner avec seule la classe index, mais il est plus efficace d'utiliser des pointeurs pour faire des insertions.