Les listes chaînées

Soit Chose une classe quelconque. Si l'on veut instancier n objets de type Chose, on peut créer un tableau de n pointeurs d'objets de type Chose :

Chose *C[n];

On dispose maintenant de n pointeurs indicés de 0 à n-1, le premier pointeur est C[0] et le dernier C[n-1]. Mais pour l'instant aucun de ces pointeurs ne pointe quelque chose. On va donc créer n objets de type Chose pour chacun d'eux :

for(i=0; i<n; i++) C[i] = new Chose();

On dispose maintenant de n objets de type Chose instanciés ici avec le constructeur par défaut. Puis après utilisation, on détruira ces n objets par un delete en boucle :

for(i=0; i<n; i++) delete C[i];

Vous pouvez aussi ne déclarer qu'un pointeur de pointeurs (voyez mes articles sur les classes et les indirections si cette notation avec deux étoiles ne vous est pas familière).

Chose **C;

La variable C est ici un pointeur vers un tableau de pointeurs de type Chose, on ne sait pas encore combien de pointeurs aura ce tableau, c'est la suite du programme qui le dira, par exemple on va instancier n pointeurs par new comme suit :

C = new Chose*[n];

On dispose maintenant de n pointeurs indicés de 0 à n-1, on créera les n objets comme précédemment :

for(i=0; i<n; i++) C[i] = new Chose();

Après utilisation, on détruira d'une part les n objets comme précédemment

for(i=0; i<n; i++) delete C[i];

mais d'autre part le tableau de pointeurs avec une syntaxe de type delete[] puisqu'on a instancié par new[] (il suffit de se souvenir qu'à new correspond delete et à new[] correspond delete[]).

delete[] C;

Quel est l'inconvénient de ces méthodes à peu de chose près identiques ? C'est que le tableau est de longueur fixe, on dispose de n objets et ce nombre ne pourra pas être modifié par la suite.

Une première parade consiste à instancier les pointeurs d'objets non pas par new, mais par malloc (car malloc a son realloc ce qui n'est pas le cas de new). Donc on crée comme précédemment un pointeur de pointeurs Chose** C; mais on instancie les n pointeurs par malloc :

C = (Chose**) malloc(n*sizeof(Chose*));

On dispose ici de n pointeurs. On peut aussi utiliser realloc dès le départ, mais alors il faut que le pointeur de pointeurs soit initialisé à NULL, on peut donc aussi écrire (et ce serait identique) :

Chose** C = NULL;
C = (Chose**) realloc(C,n*sizeof(Chose*));

car realloc équivaut à malloc si le pointeur est initialisé à NULL.

Ceci est particulièrement utile quand vous ne voulez pas distinguer les premières instanciations des autres, on utilise toujours realloc, mais il faut simplement ne pas oublier l'initialisation à NULL du pointeur. On crée les objets comme précédemment, mais du fait que le tableau de pointeurs a été déclaré par malloc (ou realloc), celui-ci peut changer de longueur via realloc et notamment passer de n à m pointeurs.

On écrira donc pour disposer maintenant de m pointeurs :

C = (Chose**) realloc(C,m*sizeof(Chose*))

Bien sûr, si m < n, on ne dispose plus que de la section commençante de m des n anciens pointeurs, lesquels pointent toujours leurs objets, la situation n'a pas beaucoup changé si ce n'est qu'on n'a plus que les m premiers objets indicés de 0 à m - 1.

Si m = n, alors il ne s'est rien passé, on a toujours n objets.

Le cas critique est évidemment m > n, dans ce cas on dispose de m - n pointeurs nouveaux indicés de n à m - 1 pour lesquels il faudra créer les objets (en bouclant de n à m-1, car ce sont ces indices qui sont nouveaux).

for(i=n; i<m; i++) C[i] = new Chose();

Dans tous les cas on a maintenant m objets indicés de 0 à m-1, on les détruira après utilisation et on libérera les pointeurs :

for(i=0; i<m; i++) delete C[i];
free(C);

Cette dernière méthode semble donc légèrement supérieure du fait que le nombre de pointeurs peut varier et notamment être augmenté grâce aux reallocs, mais elle a l'inconvénient d'utiliser malloc/realloc/free.

Il y a donc deux problèmes, d'une part les tableaux de longueur fixe et d'autre part, si le tableau n'est pas de longueur fixe, l'utilisation de malloc/realloc/free à éviter autant que possible.

Les listes chaînées résolvent ces deux difficultés. D'une part les objets s'instancient par new et se détruisent par delete (on est donc en C++ pur) et d'autre part on peut toujours créer d'autres objets sans avoir à se poser de question sur leur nombre. L'astuce est très simple, elle consiste à déclarer dans la classe elle-même un pointeur vers le même type d'objet, donc dans la classe Chose, dans la zone « public », on déclarera simplement, en plus des membres qui constituent la classe, un pointeur du type Chose :

Chose *pSuiv;

Le pointeur pSuiv pointera l'objet suivant s'il existe. Lors de la création, on initialisera ce pointeur à NULL, ce sera alors le signe qu'on pointe le dernier objet de la liste.

Au moment de la construction d'un nouvel objet, on cherchera le premier pointeur pSuiv à NULL et on lui associera par new le nouvel objet. On déclare d'abord dans les variables générales un premier pointeur vers ce type d'objet et on l'initialise à NULL :

Chose *pPrem = NULL;

Nous mettons volontairement ce pointeur pPrem dans les variables générales pour qu'il soit accessible à tout endroit du programme. Voyons comment va se passer une instanciation d'objet. La fonction Creation reçoit en argument l'indice de l'objet.

On suppose que la classe Chose contient dans la zone « public » l'entier i qui sera une sorte d'indice. Cet indice n'est pas du tout obligatoire, ce sera simplement pour nous une indication, pour la première création on aura i = 1, pour la deuxième i = 2 et ainsi de suite.

Quoi qu'il en soit, pour la création d'objets on distingue deux cas, le cas où pPrem est NULL auquel cas il s'agit du tout premier objet à créer et le cas où pPrem n'est pas NULL, auquel cas il s'agit d'un objet quelconque. Si pPrem est NULL, c'est lui qui accueillera l'objet sinon c'est le pointeur pSuiv à NULL du dernier objet de la liste. Dans le premier cas, c'est la variable générale pPrem qui est invoquée, dans le second c'est la variable pSuiv de la dernière instance de la classe Chose. D'où cette distinction qu'on retrouvera d'ailleurs de façon systématique dans les algorithmes.

void Creation(int n)
{
    if(pPrem) Quelconque(n); else Premier(n);
}

Cela signifie que si pPrem est égal à quelque chose, alors il n'est pas NULL, donc on appelle la fonction Quelconque sinon on appelle la fonction Premier, les deux fonctions recevant en argument l'indice de création, ici l'entier n. La fonction Premier est très simple puisqu'il s'agit de la première instanciation à associer à pPrem.

void Premier(int n)
{
    pPrem = new Chose();
    pPrem->i = n;
    pPrem->pSuiv = NULL;
}

On crée l'objet via new en l'associant à pPrem pPrem = new Chose();, on renseigne l'indice qui est l'argument n pPrem->i = n; et on fait pointer le pointeur pSuiv de l'objet créé à NULL pPrem->pSuiv = NULL;, car ce tout premier objet n'a pour l'instant pas de suivant.

La fonction Quelconque est plus difficile. On sait que pPrem n'est pas NULL, donc il y a au moins un objet créé, il s'agit de rechercher en parcourant la liste d'objets le premier pointeur pSuiv à NULL et d'y associer l'objet.

void Quelconque(int n)
{
    Chose *pC, *pM;
    
    pC = <inline>pPrem</inline>;
    while(pC) 
    {
        pM = pC;
        pC = pC->pSuiv;
    }
    pM->pSuiv = new Chose();
    pM->pSuiv->i = n;
    pM->pSuiv->pSuiv = NULL;
}

On déclare d'abord deux pointeurs pC et pM, pC est un pointeur vers un objet de type Chose et pM un pointeur mémoire. On fait pointer pC sur le premier objet pC = pPrem;. Ensuite, tant que pC n'est pas NULL c'est-à-dire tant qu'il pointe un objet while(pC), on mémorise le pointeur de cet objet dans pM prévu à cet effet pM = pC; puis on fait pointer pC au pointeur suivant pC = pC->pSuiv;.

Dans ces conditions, pC va finir par être NULL et pM pointera alors le dernier objet de la liste. Au sortir de la boucle en while, pM pointe le dernier objet de la liste, car son pointeur suivant à savoir pM->pSuiv est NULL. On associe donc à ce pointeur l'objet suivant pM->pSuiv = new Chose();, pM->pSuiv pointe maintenant le dernier objet, on renseigne son indice pM->pSuiv->i = n; et on met à NULL son pointeur suivant pM->pSuiv->pSuiv = NULL; ce qui sera le signe futur que cette instance est la dernière de la liste. Dans ces conditions, si NbObj est le nombre d'objets à créer, on peut écrire :

for(i=0; i<NbObj; i++) Creation(i+1);

Et à tout moment, on peut appeler la fonction Creation qui attache à la fin de la liste un nouvel objet, il suffit par exemple d'avoir une variable générale Indice qui représente le dernier indice créé, on instanciera alors un nouvel objet par une syntaxe du type Creation(++Indice);

On a donc à tout moment un certain nombre d'objets liés les uns aux autres à partir du pointeur de base pPrem des variables générales, chaque pSuiv de tout objet instancié pointe l'objet suivant sauf le dernier qui pointe NULL. Voyons comment nous allons supprimer le nième objet de la liste. On va distinguer deux cas, le cas du premier objet pointé par pPrem et le cas d'un objet quelconque donc on écrit simplement :

void Supprim(int n)
{
    if(!--n) SupprimePremier(); else SupprimeQuelconque(n);
}

Si après décrémentation on a n = 0 alors il s'agit de supprimer le premier objet de la liste sinon il s'agit de supprimer l'objet numéro n (on envoie comme argument n déjà décrémenté). Voici comment on supprime le premier objet de la liste :

void SupprimePremier()
{
    Chose *pC;
    
    pC = pPrem->pSuiv;
    delete pPrem;
    pPrem = pC;
}

On mémorise dans pC le pointeur pSuiv du premier objet, car ce pointeur va être maintenant la toute première adresse de la liste après suppression pC = pPrem->pSuiv;, on supprime l'objet pointé par pPrem donc le premier objet delete pPrem; puis on fait pointer pPrem à l'adresse mémorisée pPrem = pC;. Le cas général est plus difficile.

void SupprimeQuelconque(int n)
{
    Chose *pC, *pMem, *pMem1;
    
    pC = pPrem;
    do
    {
        pMem = pC;
        pC = pC->pSuiv;
    } while(--n);
    pMem1 = pC->pSuiv;
    delete pC;
    pMem->pSuiv = pMem1;
}

En entrant dans cette fonction, le numéro n a déjà été décrémenté et on sait qu'il ne s'agit pas du premier objet. On initialise donc un pointeur pC avec l'adresse du premier objet pC = pPrem; puis on boucle en mémorisant dans pMem l'adresse de l'objet visé pMem = pC; ce qui libère pC pour y lire l'adresse de l'objet suivant pC = pC->pSuiv; tant que n prédécrémenté n'est pas nul while(--n);.

Au sortir de cette boucle en while, pC pointe l'objet à détruire et pMem l'objet précédent. On mémorise dans une autre variable pMem1 l'adresse pSuiv de l'objet à détruire pMem1 = pC->pSuiv; car cette adresse correspondra après destruction à l'adresse de l'objet suivant de pMem. On détruit l'objet, comme nous venons de le dire, il s'agit de l'objet d'adresse pC calculée par la boucle en while delete pC; puis on relie l'objet pointé par pMem (l'objet juste avant l'objet détruit) à pMem1 pMem->pSuiv = pMem1; c'est-à-dire l'adresse pSuiv de l'objet détruit, ainsi la liste est toujours chaînée, mais l'objet numéro n a disparu.

Voyons maintenant comment insérer un objet à l'emplacement numéro n. Comme d'habitude, on va distinguer une insertion au début de la liste (car c'est pPrem qui est concerné) d'une insertion quelconque qui concernera un des pSuiv de la liste.

void Insert(int n, int indice)
{
    if(!--n) InsertPremier(indice); else InsertQuelconque(n,indice);
}

La fonction Insert reçoit deux arguments, d'une part le numéro de l'emplacement dans la liste chaînée et d'autre part l'indice qu'on donnera à l'objet inséré. Si après décrémentation n est nul, alors il s'agit d'une insertion à titre de premier objet sinon il s'agit d'une insertion dans le cas général. Voici comme se passe l'insertion en début de liste.

void InsertPremier(int i)
{
    Chose *pC;
    
    pC = pPrem;
    pPrem = new Chose();
    pPrem->pSuiv = pC;
    pPrem->i = i;
}

On mémorise dans pC l'adresse du premier objet pC = pPrem; qui sera le deuxième après insertion, on instancie pour pPrem l'objet nouveau pPrem = new Chose(); puis on donne au pSuiv de l'objet créé l'adresse mémorisée pPrem->pSuiv = pC; ce qui a pour effet que l'ancien premier objet est en deuxième position. On donne enfin à l'objet créé l'indice envoyé en argument pPrem->i = i;.

Voici maintenant pour le cas général.

void InsertQuelconque(int n, int i)
{
    Chose *pC, *pMem;
    
    pC = pPrem;
    do
    {
        pMem = pC;
        pC = pC->pSuiv;
    } while(--n);
    pMem->pSuiv = new Chose();
    pMem->pSuiv->i = i;
    pMem->pSuiv->pSuiv = pC;
}

On initialise un pointeur pC en le faisant pointer sur le premier objet de la liste pC = pPrem;. Ensuite on boucle en mémorisant à chaque fois l'adresse de l'objet visé dans pMem pMem = pC; ce qui nous permet d'utiliser pC sans perte d'information en le faisant pointer sur l'objet suivant de la liste pC = pC->pSuiv; et ce, tant que n prédécrémenté n'est pas nul while(--n);.

Au sortir de cette boucle, pMem pointe l'objet dont l'adresse pSuiv doit accueillir le nouvel objet instancié et pC l'objet qui sera le suivant par rapport à l'objet créé, il s'agit donc d'intercaler le nouvel objet entre pMem et pC.

L'adresse pointée par pMem->pSuiv est l'adresse, avons-nous dit, qui accueille l'objet instancié pMem->pSuiv = new Chose();. Le nouvel objet créé se trouve donc à l'adresse pMem->pSuiv, on renseigne son indice pMem->pSuiv->i = i; et l'adresse de son élément suivant contenue dans pC pMem->pSuiv->pSuiv = pC;.

Par ce mécanisme, un nouvel objet a été inséré après l'objet numéro n de la liste chaînée puisque pMem au sortir de la boucle pointe l'objet d'avant celui à insérer, pMem->pSuiv accueille l'objet et pMem->pSuiv->pSuiv reçoit l'adresse de l'objet suivant mémorisée dans pC au sortir du while. Voyons comment nous pouvons inverser deux objets de la liste chaînée. Il faut encore distinguer deux cas, le cas où le premier élément de la liste entre en jeu dans l'inversion et le cas où il n'entre pas en jeu.

void Inversion(int a, int b)
{
    if (a==1) Inversion1(b); else Inversion2(a,b);
}

La fonction Inversion reçoit deux arguments a et b qui sont les numéros des éléments à inverser. On suppose ici que a < b. Si a est égal à 1 on appelle le premier algorithme Inversion1, car il fait intervenir le premier objet de la liste sinon on appelle Inversion2 qui est le cas général. Voyons d'abord le cas général. On reçoit bien entendu les deux nombres a et b correspondant à leur numéro d'ordre dans la liste.

void Inversion2(int i, int j)
{
    Chose *pC1, *pC2, *p1, *p2, *p3, *p4;
    bool Consec = (i==j-1);
    
    j-= i;
    i--;
    pC1 = pPrem;
    while(--i) pC1 = pC1->pSuiv;
    
    pC2 = pC1;
    do pC2 = pC2->pSuiv; while(--j);
    
    p1 = pC1->pSuiv;
    p2 = pC1->pSuiv->pSuiv;
    p3 = pC2->pSuiv;
    p4 = pC2->pSuiv->pSuiv;
    
    if(Consec)
    {
        pC1->pSuiv = p3;
        p3->pSuiv = p1;
        p1->pSuiv = p4;
    }
    else
    {
        pC1->pSuiv = p3;
        p3->pSuiv = p2;
        pC2->pSuiv = p1;
        p1->pSuiv = p4;
    }
}

On commence par positionner la variable booléenne Consec qui dira si les deux éléments sont consécutifs ou non. En effet, le principe d'inversion diffère si les deux éléments sont consécutifs. Donc Consec sera vrai si les deux éléments à inverser sont consécutifs sinon Consec sera faux Consec = (i==j-1);.

Ensuite on va positionner deux pointeurs pC1 et pC2, le premier juste avant l'élément numéro a (ici variable i) et le second juste avant l'élément numéro b (ici variable j). Donc, pour pC1, à partir de pPrem pC1 = pPrem;, on avance jusqu'à pointer l'élément d'avant le premier des deux éléments concernés while(--i) pC1 = pC1->pSuiv;. En fait comme i a été primitivement décrémenté avant la boucle i--; et comme on procède par prédécrémentation dans la boucle en while, cela correspond à avancer le pointeur pC1 i-2 fois à partir de pPrem.

Donc après cette boucle en while, pC1 pointe l'élément avant le premier à inverser. Ensuite, on passe la main à partir de pC1 au pointeur pC2 pC2 = pC1;. À partir de pC1, pC2 doit avancer j-i fois pour pointer l'élément avant le deuxième à inverser. C'est pourquoi, au début de la fonction nous avons soustrait i à j j-=i;, dans ces conditions, pC2 doit avancer j fois do pC2 = pC2->pSuiv; while(--j);.

Après ces deux boucles, pC1 pointe avant le premier élément et pC2 avant le deuxième. On mémorise dans quatre variables distinctes les adresses qui vont intervenir dans l'inversion, p1 pointe l'élément suivant de pC1 soit l'élément à inverser p1 = pC1->pSuiv;, p2 pointe l'élément qui suit l'élément à inverser p2 = pC1->pSuiv->pSuiv;, p3 pointe le deuxième élément c'est-à-dire le suivant de pC2 p3 = pC2->pSuiv; et enfin p4 pointe l'élément suivant du deuxième à inverser p4 = pC2->pSuiv->pSuiv;.

On interroge maintenant la variable booléenne Consec. Si les deux valeurs sont consécutives if(Consec), on ne modifie que trois adresses pour procéder à l'inversion. Puisque pC1 pointe avant l'élément à inverser, son élément suivant doit être maintenant p3 à savoir l'adresse du deuxième élément pC1->pSuiv = p3;, l'adresse suivante du second élément doit être l'adresse du premier élément soit p1 p3->pSuiv = p1; et enfin l'adresse suivante du premier élément maintenant inversé doit être l'adresse de l'élément qui suivait le deuxième avant l'inversion soit p4 p1->pSuiv = p4;.

Si maintenant les deux objets ne sont pas consécutifs, on commence par faire pointer l'adresse suivante de l'élément avant le premier à inverser à l'adresse du deuxième soit p3 pC1->pSuiv = p3;, l'adresse suivante du deuxième doit pointer après le premier élément soit p2 p3->pSuiv = p2;, l'élément d'avant le deuxième doit maintenant pointer le premier soit p1 pC2->pSuiv = p1; et l'adresse de cet élément doit être après le deuxième soit p4 p1->pSuiv = p4;.

Par ce mécanisme, les deux éléments ont été inversés. On voit que consécutifs ou non, le positionnement de pC1->pSuiv et p1->pSuiv est le même, le premier prenant l'adresse p3 et le second p4, on peut donc améliorer légèrement cette écriture en sortant ces deux instructions du test.

pC1->pSuiv = p3;
p1->pSuiv = p4; 
if(Consec) p3->pSuiv = p1; 
else
{
    p3->pSuiv = p2;
    pC2->pSuiv = p1;
}

S'il y a inversion avec le premier élément, le principe est évidemment du même type, mais l'algorithme est simplifié du fait qu'on connaît déjà l'adresse pPrem du premier élément de la liste. Mais il faudra toujours distinguer le cas d'éléments consécutifs du cas d'éléments non consécutifs. Comme on sait qu'on commute deux éléments dont le premier de la liste, on n'envoie en argument que le numéro d'ordre du deuxième et on sait qu'il s'agit d'éléments consécutifs si le numéro envoyé est 2.

void Inversion1(int n)
{
    Chose *pC, *p1, *p2, *p3, *p4;
    bool consec = (n==2);
    
    p1 = pPrem;
    p2 = pPrem->pSuiv;
    
    n -= 2;
    pC = pPrem;
    while(n--) pC = pC->pSuiv;
    p3 = pC->pSuiv;
    p4 = pC->pSuiv->pSuiv;
    
    p1->pSuiv = p4; 
    if(consec)
    {
        pPrem = p2;
        p2->pSuiv = p1;
    }
    else
    {
        pPrem = p3;
        p3->pSuiv = p2;
        pC->pSuiv = p1;
    }
}

Après utilisation de tous les objets instanciés, il ne faudra pas oublier de tout détruire en boucle par delete.

void DetruitTout(void)
{
    Chose *pC, *pM;
    
    pC = pPrem;
    while(pC)
    {
        pM = pC->pSuiv;
        delete pC;
        pC = pM;
    }
    pPrem = NULL;
}

On part de pPrem pC = pPrem;. Tant que pC pointe quelque chose while(pC), on mémorise dans pM l'adresse de l'élément suivant pM = pC->pSuiv;, ce qui nous permet de détruire l'élément pointé delete pC; puis ont fait passer dans pC l'adresse mémorisée pC = pM; en sorte que pC finira par pointer NULL, ce qui signifiera que tous les éléments ont été détruits.

Une fois la boucle terminée, on annule pPrem pPrem = NULL;, c'est inutile ici puisque notre analyse est terminée, mais cela pourrait s'avérer utile si le programme continuait puisqu'alors ce serait le signe que la liste est complètement vide.

Le seul inconvénient des listes chaînées est qu'elles se limitent au seul accès séquentiel, l'accès direct est impossible. Pour accéder au nième élément, il faut parcourir la liste séquentiellement jusqu'à pointer l'élément numéro n. Mais comme en général les éléments consécutifs ont à être traités dans l'ordre, ce défaut est amoindri par l'expérience même. Si toutefois un accès direct vous est nécessaire à un moment donné de l'algorithme pour des raisons de performance, rien ne vous empêche de construire un tableau de n pointeurs.

Chose *pC;
Chose **C = new Chose*[n];

pC = pPrem;
for(i=0; i<n; i++)
{
    C[i] = pC;
    pC = pC->pSuiv;
}

Ce fragment de code construit un tableau C de n pointeurs Chose **C = new Chose*[n];, n étant le nombre d'éléments de la liste (ce nombre est toujours connu à un moment donné et de toute façon peut toujours être calculé) puis renseigne tous les pointeurs C[i].

On part de pPrem pC = pPrem;. Pour chaque élément de la liste numéroté de 0 à n-1 for(i=0; i<n; i++), l'adresse numéro i est renseignée dans le tableau C[i] = pC; puis pC prend l'adresse de l'élément suivant pC = pC->pSuiv;. Dans ces conditions, tous les éléments sont maintenant accessibles directement par une syntaxe de type C[i] avec i compris entre 0 et n-1. Après utilisation de ce tableau qui permet un accès direct aux n éléments de la liste, on le détruira par l'instruction delete[] C.

Voici un exemple complet de programme C++ sous DOS, testé avec le compilateur gratuit de Borland. Comme les syntaxes utilisées sont tout à fait standard, il doit fonctionner avec tout autre compilateur.

Le programme commence par chercher un nombre aléatoire NbObj compris entre deux constantes arbitraires NbMin et NbMax, ce sera le nombre d'objets à créer. NbObj étant connu, on crée NbObj objets de type Chose. Ensuite on cherche un nombre aléatoire n entre 1 et NbObj et on supprime ce nième objet de la liste chaînée.

Puis on insère un objet à ce même emplacement avec pour indice 99, ce qui rend l'insertion très visible, car on affiche les indices de la liste après chaque test.

Ensuite on crée par une double boucle toutes les combinaisons de deux chiffres différents, le premier nombre i allant de 1 à NbObj-1 et le second j de i+1 à NbObj, pour chacun de ces couples (i,j) on procède à une inversion des objets numéro i et j puis on inverse cette inversion, en conséquence de quoi on revient à chaque fois à la position d'origine (inversion d'inversion).

Donc toutes les possibilités d'inversions sont éprouvées (avec premier élément en jeu, avec éléments consécutifs, etc.), au sortir de la boucle on constate qu'on est bien revenu en position d'origine, c'est la preuve de l'absolue correction de la fonction d'inversion. Ensuite on détruit tous les objets instanciés et c'est la fin de cet exemple de test.

Les inversions sont surtout utiles pour les tris, essayons avec le tri de Shell. On déclare une classe Chose contenant simplement un nombre N et un pointeur vers l'élément suivant.

class Chose
{
public:
    /* un nombre entier */
    int N;
    /* pointeur sur instance suivante */
    Chose *pSuiv;
};

Comme précédemment nous allons choisir un nombre aléatoire entre NbMin et NbMax :

NbObj = Alea(NbMin,NbMax);

puis nous allons créer NbObj objets en initialisant le Nombre N de chaque instance créée avec un nombre aléatoire compris entre 1 et 100.

for(i=0; i<NbObj; i++) Creation(Alea(1,100));

On a donc maintenant NbObj instances de la classe Chose, chacune contenant un nombre aléatoire. Nous allons trier cette liste en utilisant l'algorithme du « tri de Shell ».

Le principe est assez simple. On considère une variable ecart qui va être initialisée au nombre d'objets total soit NbObj. Puis on va diviser cet écart par 2, la première fois cet écart sera donc égal à NbObj/2. Cette variable représente l'écart qu'il y aura entre deux pointeurs p1 et p2.

Ainsi, au début de chaque passe, p1 va pointer le premier objet et p2 l'objet numéro ecart+1. Puis on compare les nombres des objets visés. Si le nombre de l'instance pointée par p1 est plus grand que le nombre de l'instance pointée par p2, alors on inverse les deux objets sinon on ne fait rien. Puis on avance les deux pointeurs et on compare à nouveau les nombres des instances pointées et ce, jusqu'à la fin de la liste c'est-à-dire jusqu'à ce que p2 soit NULL.

Si pour un écart donné, il y a eu au moins un échange, on recommence la passe avec le même écart sinon on divise l'écart par deux et on recommence avec ce nouvel écart jusqu'à ce que les passes aient été réalisées pour un écart égal à l'unité. Le principe général peut donc se coder comme suit :

void TriShell()
{
    int ecart = NbObj;
    while(ecart! = 1)
    {
        ecart/=2;
        while(Passe(ecart));
    }
}

La variable ecart est, comme nous l'avons dit, initialisée avec le nombre d'objets instanciés int ecart = NbObj;. Tant que cet écart n'est pas égal à 1 while(ecart != 1), on divise d'abord cet écart par 2 ecart/=2;, puis on appelle une passe pour cet écart autant de fois que la passe renvoie vrai while(Passe(ecart));.

La fonction booléenne Passe reçoit en argument l'écart à considérer et renverra « vrai » s'il y a eu suite à la réalisation de cette passe au moins une inversion et « faux » s'il n'y a pas eu d'inversion.

La boucle en while décidera alors d'appeler ou non une nouvelle fois Passe avec le même écart. S'il n'y a pas eu d'inversion, le while général testera l'écart pour lequel on sait qu'il n'y a plus d'inversion à opérer. S'il n'est pas égal à 1, alors on divisera l'écart par 2 et on exécutera autant de passes qu'il en faudra pour ce nouvel écart. Mais si l'écart est égal à 1, alors le tri est terminé puisque cela signifie qu'on a testé tous les couples de valeurs consécutives sans inversion, si donc aucune inversion n'a eu lieu en ne testant que les valeurs consécutives, c'est bien la preuve que les valeurs sont dans l'ordre.

bool Passe(int e)
{
    int i, j;
    Chose *p1, *p2, *pTemp;
    bool inv;
    
    i = 1;
    p1 = pPrem;
    p2 = PlaceToi(j = e+1);
    inv = false;
    do
    {
        if(p2->N < p1->N)
        {
            Inversion(i,j);
            inv = true;
            pTemp = p1;
            p1 = p2;
            p2 = pTemp;
        }
        i++;
        j++;
        p1 = p1->pSuiv;
        p2 = p2->pSuiv;
    } while(p2);
    return inv;
}

La fonction booléenne Passe reçoit donc l'écart à considérer. Cet écart correspond à la distance qu'il y aura entre les deux pointeurs p1 et p2. Nous allons donc positionner p1 et p2, mais comme nous devons savoir à chaque instant le numéro d'ordre des éléments qu'ils pointent dans la liste, nous allons utiliser deux autres variables i et j qui vont suivre en quelque sorte l'avancée de p1 et de p2.

Le pointeur p1 pointera l'élément numéro i et p2 l'élément numéro j. Donc, avant la boucle, on initialise i à 1 i = 1; et p1 à pPrem p1 = pPrem;, p1 pointe donc le premier élément de la liste. Puis on initialise j à e+1 et on place p2 à l'élément numéro j p2 = PlaceToi(j = e+1);. PlaceToi est donc une petite routine qui renvoie un pointeur de type Chose sur l'élément dont le numéro d'ordre est envoyé en argument, ici e+1.

On a vu que les listes chaînées n'ont pas d'accès direct, il faudra donc avancer un pointeur à partir de pPrem jusqu'à atteindre l'objet voulu. Donc après cette séquence d'instructions p1 pointe l'élément numéro i = 1 et p2 l'élément numéro j = écart+1.

Ensuite on initialise la variable booléenne inv à false inv = false;, c'est cette variable qui dira si, pour cette passe, il y a eu au moins une inversion. La boucle en do peut commencer, on compare les nombres des objets visés par p1 et p2 if(p1->N > p2->N). Si le nombre pointé par P1 est supérieur au nombre pointé par p2, alors il faut inverser ces deux objets Inversion(i,j);, on obtiendra ainsi un tri par ordre croissant.

On appelle la routine d'inversion qui est la même que précédemment, elle inverse l'élément numéro i et l'élément numéro j. Puisque dans ce cas une inversion a eu lieu, on met la variable booléenne inv à true inv = true;. Puis, on inverse p1 et p2.

En effet, pour l'instant ils sont bien placés, mais comme l'élément suivant de p1 se trouve après p2 et inversement, il faut inverser p1 et p2 de manière à ce qu'après leur avancée, p1 et p2 pointent après l'emplacement où ils se trouvaient. On fait ce swap entre p1 et p2 par rotation circulaire en utilisant une variable temporaire, p1 est d'abord sauvegardé dans cette variable temporaire pTemp = p1;, p2 est ensuite lu dans p1 p1 = p2; et la variable temporaire est lue dans p2 p2 = pTemp;.

Qu'il y ait eu inversion ou non, i et j sont incrémentés, p1 et p2 pointent leur objet suivant et la boucle se poursuit aussi longtemps que p2 n'est pas nul while(p2);, car comme p2 est devant p1, c'est lui qui accueillera le pointeur pSuiv de la dernière instance à NULL. La passe est terminée, on renvoie simplement la variable booléenne inv à l'appelant return inv;. Comme l'appelant est une boucle en while, la fonction booléenne sera appelée de nouveau avec le même écart si inv est à true. Il ne nous reste que la routine PlaceToi à écrire.

Chose* PlaceToi(int n)
{
    Chose* pC = pPrem;
    for(int i=0; i<n-1; i++) pC = pC->pSuiv;
    return pC;
}

Cette routine reçoit le numéro de l'élément à pointer dans la liste. Comme toujours on part de pPrem Chose* pC = pPrem;. Puis on avance n-1 fois for(int i=0; i<n-1; i++) pC = pC->pSuiv;. Après cette boucle, pC pointe l'objet numéro n de la liste chaînée, il suffit de le renvoyer à l'appelant return pC;.

Remarquez que pour n = 1, la boucle en for ne s'exécute pas du tout et comme pC est initialisé à pPrem, on renvoie pPrem qui est bien l'adresse du premier élément.

Dans ce dernier exemple, la liste chaînée est bidirectionnelle, on a donc en plus un pointeur pPrec sur l'élément précédent dans la classe Chose.

Chose *pSuiv, *pPrec;

Dans les variables générales, on a maintenant deux pointeurs initialisés à NULL, pPrem qui contiendra comme avant l'adresse du premier élément et pDern l'adresse du dernier élément de la liste chaînée.

Chose *pPrem = NULL, *pDern = NULL;

Au moment de la création du tout premier objet, celui-ci n'a ni suivant ni précédent.

pPrem->pSuiv = NULL;
pPrem->pPrec = NULL;

Pour la création d'un objet quelconque, on fait pointer pM sur le dernier objet à partir de pPrem

pC = pPrem;
while(pC) 
{
    pM = pC;
    pC = pC->pSuiv;
}

puis on crée l'objet en donnant cette adresse à pDern qui contient toujours l'adresse du dernier objet créé :

pDern = new Chose();

Puis on donne à pM->pSuiv cette dernière adresse :

pM->pSuiv = pDern;

L'indice i de l'objet créé est renseigné :

pM->pSuiv->i = n;

Puis on exprime que pSuiv de l'objet créé est NULL, car le dernier objet n'a pas de suivant :

pM->pSuiv->pSuiv = NULL;

Comme pM pointe maintenant l'avant-dernier objet, il correspond donc à pPrec du dernier objet créé d'où

pM->pSuiv->pPrec = pM;

Par ce mécanisme, la liste est doublement chaînée, on peut maintenant la parcourir en arrière à partir de pDern. Cela dit, l'avantage des listes bidirectionnelles n'est pas, en principe, de pouvoir les parcourir en sens inverse, l'exemple précédent ne sert qu'à montrer que c'est possible puisque chaque pPrec pointe bien l'élément précédent. En général, en utilisant les listes doublement chaînées, on n'a que le pointeur pPrem des variables générales qui pointera toujours le premier objet de la liste.

L'avantage des listes doublement chaînées est simplement de pouvoir reculer à tout moment. Ainsi, dans les algorithmes monodirectionnels, nous avons eu à mémoriser des adresses précédentes de passage et ce, parce qu'il nous était impossible de reculer. De telles mémorisations auraient été inutiles si la liste avait été bidirectionnelle, car à partir de pC pointant un élément quelconque, pC->pPrec pointe par définition l'élément précédent, et pC->pPrec->pPrec l'élément encore précédent et ainsi de suite.

Notre tutoriel s'arrête là, nous vous laissons le loisir de réécrire tout l'exemple 2 en bidirectionnel en adaptant l'insertion, la suppression et l'inversion, il faut simplement être précis avec les deux pointeurs pSuiv et pPrec de chaque objet instancié en s'aidant éventuellement par de petits schémas fléchés pour simuler les éléments pointés tout en veillant aux cas particuliers (premier et dernier élément et éléments consécutifs).

L'avantage des listes chaînées est donc de ne plus utiliser des tableaux de pointeurs pour pointer les objets instanciés. Chaque objet est simplement relié au suivant par un pointeur, voire également au précédent si nécessaire par un second pointeur. Car les tableaux de pointeurs déclarés par new sont de longueur fixe. Et s'ils sont déclarés par malloc, alors ils sont déclarés par malloc. Le grammairien exact nous accordera l'exception d'une apodose par trop tautologiquement protasique.