Document sans nom

Le tableau des variables

Contact* Cherche(contact, id, insere)
Nom	Type	Commentaire
contact	Contact*	Argument sous la forme de pointeur sur un type Contact représentant notre "pointeur de travail"
id	entier	Argument contenant la valeur de l'identifiant recherché
insere	booléen	Argument précisant si la recherche doit être effectuée dans l'optique d'une insertion ou non

Le pseudo code

Le pseudo code correspondant à cette fonction est

Contact Cherche(travail, id, insere)
{
    Si(travail == NULL OU
       travail->id == id OU
       (travail->Precedent->id < id ET travail->Suivant->id > id ET insere = FAUX) OU
       (travail->Precedent == NULL ET travail->id > id ET insere = FAUX) OU
       (travail->Suivant == NULL ET travail->id < id ET insere = FAUX)
    {
        Renvoie travail |
    }
    Sinon
    {
        Si(travail->id > id)
        {
            renvoie cherche(travail->Precedent, id) |
        }
        Sinon
        {

            Renvoie cherche(travail->Suivant, id) |
        }
   }
}

Quelques explication

La grosse difficulté, si l'on veut utiliser une fonction récursive, est de déterminer ce qui sera le cas de base, surtout quand plusieurs cas sont envisageables.

Dans le cas qui nous intéresse, ce sont tous les cas qui sont susceptibles de provoquer le renvoi du contact sur lequel on travaille actuellement, à savoir:

Le fait que le pointeur de travail soit NULL, ce qui peut arriver quand on n'a encore rien introduit ou si l'on recherche un élément précis, et que l'on a parcouru toute la partie de la liste où il doit se trouver
Le fait que le contcact en cours soit celui que l'on cherche (son identifiant ayant alors la valeur de l'identifiant recherché)
Le fait que l'on veuille rajouter un élément et que l'on a atteint l'élément de référence pour l'insertion
Le fait que l'on veuille rajouter un élément et que la liste a été parcourrue (vers l'avant ou vers l'arrière, selon le cas) jusqu'au bout sans trouver de meilleure position (selon le cas, l'élément que l'on voudra rajouter prendra place en première ou en dernière position de la liste)

Par contre, une fois le cas de base déterminé, il devient très facile de décider dans quel sens parcourir la liste des éléments:

Si l'identifiant de l'élément sur lequel on se trouve est plus grand que l'identifiant de référence, il faut aller voir du côté de l'élément "Precedent", sinon, il faut aller voir du côté de l'élément "Suivant".

La fonction renvoie un pointeur sur l'élément de type Contact trouvé.