Chaînage XOR

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

On nomme chaînage XOR 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[modifier | modifier le code]

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[modifier | modifier le code]

Voici un exemple d'implémentation complète en C++ en trois classes.

La classe élément[modifier | modifier le code]

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;
};

La classe index[modifier | modifier le code]

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; // Si 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;
}
};

La classe chaîne_xor[modifier | modifier le code]

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 chaîne_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[modifier | modifier le code]

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[modifier | modifier le code]

  1. 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.