Développement XNA pour la XBox et le PC
194
Listes ouverte et fermée : la collection List
Il ne reste plus qu’une chose à préparer : une collection qui servira aux listes ouverte et
fermée. Il s’agit ici de créer une collection dérivée de la collection List, l’intérêt étant
de lui donner la possibilité de retourner un objet sans connaître son index, de savoir si un
nœud est déjà présent dans la liste et enfin, d’effectuer une insertion dichotomique dans
la liste.
Qu’est-ce qu’une insertion dichotomique ? Dans le principe de l’algorithme, vous avez
pu lire qu’à chaque itération, il faut choisir le nœud dont la distance avec le nœud de
destination est la plus faible. Vous pouvez donc parcourir à chaque fois la liste ouverte à
la recherche du nœud ayant la distance la plus faible ou alors entretenir une liste triée
dans laquelle vous savez que le premier élément de la liste est toujours celui qui a la
distance la plus faible. L’insertion dichotomique vous permet donc de placer cet élément
au bon endroit. Voici l’algorithme en pseudo-code :
Gauche <- 0 // Indice du premier élément
Droite <- Taille – 1 // Indice du dernier élément
TantQue Gauche <= Right
Faire
Centre <- (Gauche + Droite) / 2
Si distance du nœud à insérer < distance du nœud liste[centre]
// On peut se passer de toute la partie à droite de la liste
Droite = Centre - 1
Sinon Si distance du nœud à insérer > distance du nœud liste[centre]
// On peut se passer de toute la partie à gauche de la liste
Gauche = Centre + 1
Sinon
// On a trouvé le bon endroit pour l’insertion
Gauche = Centre
Arrêter l’algorithme
Fin Si
FinTantQue
Insérer le nœud à la position gauche
L’exemple de la figure 9-5 illustre l’insertion du chiffre 3 dans une liste triée contenant
les 8 autres premiers chiffres et le nombre 10. Il faut jouer avec les curseurs gauche et
droite jusqu’à en faire coïncider 1 avec le curseur centre. Les lignes contenant des lettres
correspondent à la position des curseurs, la ligne qui contient des chiffres en ordre croissant
correspond aux indices de la collection. Enfin, la ligne qui contient des chiffres en ordre
croissant, mais où il manque un chiffre, correspond aux valeurs de la collection.
=Labat FM.book Page 194 Vendredi, 19. juin 2009 4:01 16
194
Listes ouverte et fermée : la collection List
Il ne reste plus qu’une chose à préparer : une collection qui servira aux listes ouverte et
fermée. Il s’agit ici de créer une collection dérivée de la collection List
de lui donner la possibilité de retourner un objet sans connaître son index, de savoir si un
nœud est déjà présent dans la liste et enfin, d’effectuer une insertion dichotomique dans
la liste.
Qu’est-ce qu’une insertion dichotomique ? Dans le principe de l’algorithme, vous avez
pu lire qu’à chaque itération, il faut choisir le nœud dont la distance avec le nœud de
destination est la plus faible. Vous pouvez donc parcourir à chaque fois la liste ouverte à
la recherche du nœud ayant la distance la plus faible ou alors entretenir une liste triée
dans laquelle vous savez que le premier élément de la liste est toujours celui qui a la
distance la plus faible. L’insertion dichotomique vous permet donc de placer cet élément
au bon endroit. Voici l’algorithme en pseudo-code :
Gauche <- 0 // Indice du premier élément
Droite <- Taille – 1 // Indice du dernier élément
TantQue Gauche <= Right
Faire
Centre <- (Gauche + Droite) / 2
Si distance du nœud à insérer < distance du nœud liste[centre]
// On peut se passer de toute la partie à droite de la liste
Droite = Centre - 1
Sinon Si distance du nœud à insérer > distance du nœud liste[centre]
// On peut se passer de toute la partie à gauche de la liste
Gauche = Centre + 1
Sinon
// On a trouvé le bon endroit pour l’insertion
Gauche = Centre
Arrêter l’algorithme
Fin Si
FinTantQue
Insérer le nœud à la position gauche
L’exemple de la figure 9-5 illustre l’insertion du chiffre 3 dans une liste triée contenant
les 8 autres premiers chiffres et le nombre 10. Il faut jouer avec les curseurs gauche et
droite jusqu’à en faire coïncider 1 avec le curseur centre. Les lignes contenant des lettres
correspondent à la position des curseurs, la ligne qui contient des chiffres en ordre croissant
correspond aux indices de la collection. Enfin, la ligne qui contient des chiffres en ordre
croissant, mais où il manque un chiffre, correspond aux valeurs de la collection.
=Labat FM.book Page 194 Vendredi, 19. juin 2009 4:01 16