• 20 hours
  • Medium

Free online content available in this course.

course.header.alt.is_certifying

Got it!

Last updated on 3/10/17

TP : Créez une liste chaînée générique

Log in or subscribe for free to enjoy all this course has to offer!

Ahh, un peu de pratique histoire de vérifier que nous avons bien compris les génériques. C'est un concept assez facile à appréhender mais relativement difficile à mettre en œuvre. Quand en ai-je besoin ? Comment ?

Voici donc un petit exercice qui va vous permettre d'essayer de mettre en œuvre une classe générique.

Instructions pour réaliser la première partie du TP

Dans la première partie du TP, nous allons réaliser une liste chaînée. Il s’agit du grand classique des TP d’informatique en C. Je vous rappelle le principe.

La liste chaînée permet de naviguer d’élément en élément. Quand nous sommes sur le premier élément, le suivant est accessible par sa propriété Suivant. Lorsque nous accédons au suivant, l’élément précédent est accessible par la propriété Precedent et le suivant toujours accessible par la propriété Suivant. S’il n’y a pas de précédent ou pas de suivant, l’élément est null :

Image utilisateur

Si on insère un élément à la position 1, les autres se décalent :

Image utilisateur

Voilà, il faut donc créer une telle liste chaînée d’éléments. Le but est bien sûr de faire en sorte que l’élément soit générique.
N’hésitez pas à réfléchir un peu avant de vous lancer. Cela pourrait paraître un peu simpliste, mais en fait cela occasionne quelques nœuds au cerveau.

Toujours est-il que je souhaiterais disposer d’une propriété en lecture seule permettant d’accéder au premier élément ainsi qu’une autre propriété également en lecture seule permettant d’accéder au dernier élément. Bien sûr, il faut pouvoir naviguer d’élément en élément avec des propriétés précédent et suivant.

Il faut évidemment une méthode permettant d’ajouter un élément à la fin de la liste. Nous aurons également besoin d’une méthode permettant d’accéder à un élément à partir de son indice et enfin d’une méthode permettant d’insérer un élément à un indice, décalant tous les suivants. Voilà pour la création de la classe !

Ensuite, notre programme instanciera notre liste chaînée pour lui ajouter les entiers 5, 10 et 4. Puis nous afficherons les valeurs de cette liste en nous basant sur la première propriété et en naviguant d’élément en élément.
Nous afficherons ensuite les différents éléments en utilisant la méthode d’accès à un élément par son indice.
Enfin, nous insérerons la valeur 99 à la première position (position 0), puis la valeur 33 à la deuxième position et enfin la valeur 30 à nouveau à la deuxième position.
Puis nous afficherons tout ce beau monde.

Fin de l’énoncé, ouf ! :)

Pour ceux qui n’ont pas besoin d’aide, les explications sont terminées. Ouvrez vos Visual Studio Express (ou vos Visual Studio si vous êtes riches ;) ) et à vos claviers.

Pour les autres, je vais essayer de vous guider un peu plus en essayant tout de même de ne pas trop vous donner d’indications non plus.

En fait, votre liste chainée n’est pas vraiment une liste, comme pourrait l’être la List<> que nous connaissons. Cette liste chainée possède un point d’entrée qui est le premier élément. L’ajout du premier élément est très simple, il suffit de mettre à jour une propriété. Pour ajouter l’élément suivant, il faut en fait brancher la propriété Suivant du premier élément à l’élément que nous sommes en train d’ajouter. Et inversement, la propriété Precedent de l’élément que nous souhaitons ajouter sera mise à jour avec le premier élément.

On se rend compte que l’élément est un peu plus complexe qu’un simple type. Nous allons donc avoir une classe générique possédant trois propriétés (Precedent, Suivant et Valeur). Et nous aurons également une classe du même type générique possédant la propriété Premier et la propriété Dernier et les méthodes d’ajout, d’obtention de l’élément et d’insertion.

Allez, je vous en ai assez dit. À vous de jouer ! ^^

Correction

Pas si facile hein ?
Mais bon, comme vous êtes super entrainés, cela n’a pas dû vous poser trop de problèmes.

Voici la correction que je propose.
La première chose à faire est de créer la classe générique permettant de stocker un élément :

public class Chainage<T>
{
    public Chainage<T> Precedent { get; set; }
    public Chainage<T> Suivant { get; set; }
    public T Valeur { get; set; }
}

C’est une classe générique toute simple qui possède une valeur du type générique et deux propriétés du même type que l’élément pour obtenir le précédent ou le suivant.
Peut-être que la plus grande difficulté réside ici, de bien modéliser la classe qui permet d’encapsuler l’élément.
Il faudra ensuite créer la liste générique et ses méthodes :

public class ListeChainee<T>
{
}

La liste chainée possède également un type générique. Nous créons sa propriété Premier :

public class ListeChainee<T>
{
    public Chainage<T> Premier { get; private set; }
}

Là, c’est très simple, il s’agit juste d’une propriété en lecture seule stockant le premier élément. C’est la méthode Ajouter() qui permettra de mettre à jour cette valeur. Notez quand même que nous utilisons le type générique comme type générique de la classe encapsulante.

Par contre, pour la propriété Dernier, c’est un peu plus compliqué. Pour la retrouver, nous allons parcourir tous les éléments à partir de la propriété Premier. Ce qui donne :

public class ListeChainee<T>
{
    […Code supprimé pour plus de clarté…]

    public Chainage<T> Dernier
    {
        get
        {
            if (Premier == null)
                return null;
            Chainage<T> dernier = Premier;
            while (dernier.Suivant != null)
            {
                dernier = dernier.Suivant;
            }
            return dernier;
        }
    }
}

On parcourt les éléments en bouclant sur la propriété Suivant, tant que celle-ci n’est pas nulle. Il s’agit là d’un parcours assez classique où on utilise une variable temporaire qui passe au suivant à chaque itération.

Nous pouvons à présent créer la méthode Ajouter :

public class ListeChainee<T>
{
    […Code supprimé pour plus de clarté…]

    public void Ajouter(T element)
    {
        if (Premier == null)
        {
            Premier = new Chainage<T> { Valeur = element };
        }
        else
        {
            Chainage<T> dernier = Dernier;
            dernier.Suivant = new Chainage<T> { Valeur = element, Precedent = dernier };
        }
    }
}

Cette méthode traite dans un premier temps le cas du premier élément. Il s’agit simplement de mettre à jour la propriété Premier. De même, grâce au calcul interne de la propriété Dernier, il sera facile d’ajouter un nouvel élément en se branchant sur la propriété Suivant du dernier élément.

Notez que vu que nous ne la renseignons pas, la propriété Suivant du nouvel élément sera bien à null.

Pour obtenir un élément à un indice donné, il suffira de reprendre le même principe que lors du parcours pour obtenir le dernier élément, sauf qu’il faudra s’arrêter au bon moment :

public class ListeChainee<T>
{
    […Code supprimé pour plus de clarté…]

    public Chainage<T> ObtenirElement(int indice)
    {
        Chainage<T> temp = Premier;
        for (int i = 1; i <= indice; i++)
        {
            if (temp == null)
                return null;
            temp = temp.Suivant;
        }
        return temp;
    }
}

Ici, plusieurs solutions. J’ai choisi d’utiliser une boucle for. Nous aurions très bien pu garder la boucle while comme pour la propriété Dernier.

Enfin, il ne reste plus qu’à insérer un élément :

public class ListeChainee<T>
{
    […Code supprimé pour plus de clarté…]

    public void Inserer(T element, int indice)
    {
        if (indice == 0)
        {
            Chainage<T> temp = Premier;
            Premier = new Chainage<T> { Suivant = temp, Valeur = element };
            temp.Precedent = Premier;
        }
        else
        {
            Chainage<T> elementAIndice = ObtenirElement(indice);
            if (elementAIndice == null)
                Ajouter(element);
            else
            {
                Chainage<T> precedent = elementAIndice.Precedent;
                Chainage<T> temp = precedent.Suivant;
                precedent.Suivant = new Chainage<T> { Valeur = element, Precedent = precedent, Suivant = temp };
                temp.Precedent = precedent.Suivant;
            }
        }
    }
}

Nous traitons dans un premier temps le cas où l’on doit insérer l'en-tête. Il suffit de mettre à jour la valeur du premier en ayant au préalable décalé ce dernier d’un cran. Attention, si Premier est null, nous allons avoir un problème. Dans ce cas, soit nous laissons le problème, en effet, peut-on vraiment insérer un élément avant les autres s'il n'y en a pas ? Soit nous gérons le cas et décidons d'insérer l'élément en tant que Premier :

public class ListeChainee<T>
{
    […Code supprimé pour plus de clarté…]

    public void Inserer(T element, int indice)
    {
        if (indice == 0)
        {
            if (Premier == null)
                Premier = new Chainage<T> { Valeur = element };
            else
            {
                Chainage<T> temp = Premier;
                Premier = new Chainage<T> { Suivant = temp, Valeur = element };
                temp.Precedent = Premier;
            }
        }
        else
        {
            Chainage<T> elementAIndice = ObtenirElement(indice);
            if (elementAIndice == null)
                Ajouter(element);
            else
            {
                Chainage<T> precedent = elementAIndice.Precedent;
                Chainage<T> temp = precedent.Suivant;
                precedent.Suivant = new Chainage<T> { Valeur = element, Precedent = precedent, Suivant = temp };
                temp.Precedent = precedent.Suivant;
            }
        }
    }
}

Pour les autres cas, si nous tentons d’insérer à un indice qui n’existe pas, nous insérons à la fin en utilisant la méthode Ajouter() existante. Sinon, on intercale le nouvel élément dans la liste en prenant soin de brancher le précédent sur notre nouvel élément et de brancher le suivant sur notre nouvel élément.

Voilà pour notre classe.

Reste à utiliser notre classe :

static void Main(string[] args)
{
    ListeChainee<int> listeChainee = new ListeChainee<int>();
    listeChainee.Ajouter(5);
    listeChainee.Ajouter(10);
    listeChainee.Ajouter(4);
    Console.WriteLine(listeChainee.Premier.Valeur);
    Console.WriteLine(listeChainee.Premier.Suivant.Valeur);
    Console.WriteLine(listeChainee.Premier.Suivant.Suivant.Valeur);
    Console.WriteLine("*************");
    Console.WriteLine(listeChainee.ObtenirElement(0).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(1).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(2).Valeur);
    Console.WriteLine("*************");
    listeChainee.Inserer(99, 0);
    listeChainee.Inserer(33, 2);
    listeChainee.Inserer(30, 2);
    Console.WriteLine(listeChainee.ObtenirElement(0).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(1).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(2).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(3).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(4).Valeur);
    Console.WriteLine(listeChainee.ObtenirElement(5).Valeur);
}

Ce qui nous donnera :

Image utilisateur

Voilà pour ce TP. Nous avons créé une classe générique permettant de gérer les listes chainées. Ceci nous a permis de manipuler ces types ô-combien indispensables et de nous entrainer à la généricité.

Notez bien sûr que cette classe est fonctionnellement incomplète. Il aurait été judicieux de rajouter une méthode permettant de supprimer un élément par exemple. D’ailleurs, n’hésitez pas à la créer et à la proposer si vous souhaitez continuer à vous entrainer. D’autres méthodes pourraient être intéressantes, comme vider la liste d’un seul coup…

J’espère que ce TP n’a pas été trop compliqué à réaliser.

À noter qu’une classe qui fait à peu près le même travail existe dans le framework .NET, elle s’appelle LinkedList.

Example of certificate of achievement
Example of certificate of achievement