{"id":341,"date":"2021-09-08T18:28:12","date_gmt":"2021-09-08T18:28:12","guid":{"rendered":"https:\/\/www.louismarchand.me\/?page_id=341"},"modified":"2022-09-23T13:49:54","modified_gmt":"2022-09-23T13:49:54","slug":"objet2-les-structures-de-donnees","status":"publish","type":"page","link":"https:\/\/www.louismarchand.me\/index.php\/objet2-les-structures-de-donnees\/","title":{"rendered":"Les structures de donn\u00e9es"},"content":{"rendered":"

Introduction<\/h2>\n

Les structures de donn\u00e9es permettent de stocker des donn\u00e9es en m\u00e9moire de mani\u00e8re structur\u00e9e et organis\u00e9e ou bien d’avoir acc\u00e8s \u00e0 des donn\u00e9es . L’important dans le choix d’une structure de donn\u00e9es, c’est de s’assurer d’avoir les fonctionnalit\u00e9s n\u00e9cessaires, de mani\u00e8re efficace, mais sans laisser trop de libert\u00e9. En effet, plus on donne d’acc\u00e8s lors de l’utilisation d’une structure de donn\u00e9es, plus le risque de probl\u00e9matique augmente.<\/p>\n

Les diff\u00e9rentes structures abstraites et leurs impl\u00e9mentations<\/h2>\n

Une structure abstraite est une version logique d’une structure de donn\u00e9es, sans prendre en compte l’impl\u00e9mentation de cette derni\u00e8re.<\/p>\n

Une structure de donn\u00e9e (non abstraite) consiste en l’impl\u00e9mentation de ces structures abstraites.<\/p>\n

Les indexables<\/h3>\n

Une structure indexable est une structure abstraite de donn\u00e9es qui permette d’acc\u00e9der \u00e0 une valeur en utilisant un index. L’index peut \u00eatre num\u00e9rique (comme dans un tableau) ou autre (comme dans une table de hachage).<\/p>\n

Il est \u00e0 noter que le langage Java n’a pas de classe abstraite repr\u00e9sentant ce type de structure (et c’est malheureusement un manque dans la librairie Java).<\/p>\n

Le langage Eiffel contient une classe abstraite \u00ab\u00a0INDEXABLE\u00a0\u00bb repr\u00e9sentant ce type de structure. Vous pouvez voir la documentation ici<\/a>.<\/p>\n

Voici un exemple d’utilisation un objet \u00ab\u00a0INDEXABLE\u00a0\u00bb en Eiffel:<\/p>\n

\n
print_from_indexable<\/span>(<\/span>a_indexable<\/span>:<\/span>INDEXABLE<\/span>[<\/span>STRING<\/span>,<\/span> INTEGER<\/span>]<\/span>)<\/span>\r\n\t\t-- Affiche les \u00e9l\u00e9ments de `a_indexable'<\/span>\r\n\tlocal<\/span>\r\n\t\tl_index<\/span>:<\/span>INTEGER<\/span>\r\n\tdo<\/span>\r\n\t\tfrom<\/span> l_index<\/span> :=<\/span> a_indexable<\/span>.<\/span>lower<\/span> until<\/span> l_index<\/span> ><\/span> a_indexable<\/span>.<\/span>upper<\/span> loop<\/span>\r\n\t\t\tprint<\/span>(<\/span>\"Valeur a l'index \"<\/span> +<\/span> l_index<\/span>.<\/span>out<\/span> +<\/span> \": \"<\/span> +<\/span> \r\n\t\t\t\t\ta_indexable<\/span>.<\/span>at<\/span> (<\/span>l_index<\/span>)<\/span> +<\/span> \"%N\"<\/span>)<\/span>\r\n\t\t\tl_index<\/span> :=<\/span> l_index<\/span> +<\/span> 1<\/span>\r\n\t\tend<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Pour tester ce code, vous pouvez y envoyer n’importe quelle variable ayant un type conforme \u00ab\u00a0INDEXABLE\u00a0\u00bb. Voici un exemple simple:<\/p>\n
\n
make<\/span>\r\n\t\t-- Ex\u00e9cute l'exemple<\/span>\r\n\tlocal<\/span>\r\n\t\tl_liste<\/span>:<\/span>ARRAYED_LIST<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tcreate<\/span> l_liste<\/span>.<\/span>make<\/span>(<\/span>10<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 1\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 2\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 3\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 4\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 5\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 6\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 7\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 8\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 9\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 10\"<\/span>)<\/span>\r\n\t\tprint_from_indexable<\/span>(<\/span>l_liste<\/span>)<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Les it\u00e9rables<\/h3>\n
Un it\u00e9rable (parfois appel\u00e9 traversable) est une structure abstraite avec laquelle il est possible de visiter chaque \u00e9l\u00e9ment de la structure une unique fois.<\/p>\n
En pratique, dans les langages, ce type de structure retourne un it\u00e9rateur puisqu\u2019un it\u00e9rateur sert pr\u00e9cis\u00e9ment \u00e0 effectuer le travail indiqu\u00e9 plus haut. Vois le patron conceptuel \u00ab\u00a0iterateur\u00a0\u00bb dans la page de th\u00e9orie pr\u00e9c\u00e9dente.<\/p>\n
La documentation de l’interface \u00ab\u00a0Iterable\u00a0\u00bb en Java est ici<\/a><\/p>\n
La documentation Eiffel de la classe \u00ab\u00a0ITERABLE\u00a0\u00bb est Eiffel est ici<\/a><\/p>\n
Voici un exemple d’utilisation en Java:<\/p>\n
\n
\/**<\/span>\r\n * Affiche les \u00e9l\u00e9ments d'un objet Iterable.<\/span>\r\n *<\/span>\r\n * @param aIterable L'objet contenant les \u00e9l\u00e9ments \u00e0 afficher.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> printIterable<\/span>(<\/span>Iterable<\/span><<\/span>String<\/span>><\/span> aIterable<\/span>)<\/span> {<\/span>\r\n    Iterator<\/span><<\/span>String<\/span>><\/span> lIterateur<\/span> =<\/span> aIterable<\/span>.<\/span>iterator<\/span>();<\/span>\r\n    while<\/span>(<\/span>lIterateur<\/span>.<\/span>hasNext<\/span>()){<\/span>\r\n        System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>lIterateur<\/span>.<\/span>next<\/span>());<\/span>\r\n    }<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Pour tester ce code, vous pouvez y envoyer n’importe quelle variable ayant un type conforme \u00e0 \u00ab\u00a0Iterable\u00a0\u00bb. Voici un exemple simple:<\/p>\n
\n
    \/**<\/span>\r\n     * Ex\u00e9cution de l'exemple.<\/span>\r\n     *\/<\/span>\r\n    public<\/span> void<\/span> execute<\/span>(){<\/span>\r\n        List<\/span><<\/span>String<\/span>><\/span> lListe<\/span> =<\/span> new<\/span> ArrayList<\/span><<\/span>String<\/span>>(<\/span>10<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 1\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 2\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 3\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 4\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 5\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 6\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 7\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 8\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 9\"<\/span>);<\/span>\r\n        lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 10\"<\/span>);<\/span>\r\n        printIterableFor<\/span>(<\/span>lListe<\/span>);<\/span>\r\n    }<\/span>\r\n<\/pre>\n<\/div>\n
Voici un exemple en Eiffel (noter qu’en Eiffel, un it\u00e9rateur est appel\u00e9 curseur):<\/p>\n
\n
print_from_iterable<\/span>(<\/span>a_iterable<\/span>:<\/span>ITERABLE<\/span>[<\/span>STRING<\/span>]<\/span>)<\/span>\r\n\t\t-- Affiche les \u00e9l\u00e9ments de `a_iterable'<\/span>\r\n\tlocal<\/span>\r\n\t\tl_iterateur<\/span>:<\/span>ITERATION_CURSOR<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tl_iterateur<\/span> :=<\/span> a_iterable<\/span>.<\/span>new_cursor<\/span>\r\n\t\tfrom<\/span> until<\/span> l_iterateur<\/span>.<\/span>after<\/span> loop<\/span>\r\n\t\t\tprint<\/span>(<\/span>l_iterateur<\/span>.<\/span>item<\/span> +<\/span> \"%N\"<\/span>)<\/span>\r\n\t\t\tl_iterateur<\/span>.<\/span>forth<\/span>\r\n\t\tend<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Pour tester ce code, vous pouvez y envoyer n’importe quelle variable ayant comme type une classe impl\u00e9mentant \u00ab\u00a0ITERABLE\u00a0\u00bb. Voici un exemple simple:<\/p>\n
\n
make<\/span>\r\n\t\t-- Ex\u00e9cute l'exemple<\/span>\r\n\tlocal<\/span>\r\n\t\tl_liste<\/span>:<\/span>ARRAYED_LIST<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tcreate<\/span> l_liste<\/span>.<\/span>make<\/span>(<\/span>10<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 1\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 2\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 3\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 4\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 5\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 6\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 7\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 8\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 9\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 10\"<\/span>)<\/span>\r\n\t\tprint_from_iterable<\/span>(<\/span>l_liste<\/span>)<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Il est \u00e9galement \u00e0 noter que, autant en Java qu’en Eiffel, l’objet \u00ab\u00a0Iterable\u00a0\u00bb est le type le plus abstrait pour lequel il est possible d’utiliser dans une boucle \u00ab\u00a0for\u00a0\u00bb (ou \u00ab\u00a0across\u00a0\u00bb en Eiffel). Par exemple, voici un exemple en Java utilisant un \u00ab\u00a0for\u00a0\u00bb:<\/p>\n
\n
\/**<\/span>\r\n * Affiche les \u00e9l\u00e9ments d'un objet Iterable en utilisant \"for\".<\/span>\r\n *<\/span>\r\n * @param aIterable L'objet contenant les \u00e9l\u00e9ments \u00e0 afficher.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> printIterable<\/span>(<\/span>Iterable<\/span><<\/span>String<\/span>><\/span> aIterable<\/span>)<\/span> {<\/span>\r\n    for<\/span>(<\/span>String<\/span> laElement<\/span>:<\/span>aIterable<\/span>){<\/span>\r\n        System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>laElement<\/span>);<\/span>\r\n    }<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Et voici un exemple en Eiffel:<\/p>\n
\n
print_from_iterable<\/span>(<\/span>a_iterable<\/span>:<\/span>ITERABLE<\/span>[<\/span>STRING<\/span>]<\/span>)<\/span>\r\n\t\t-- Affiche les \u00e9l\u00e9ments de `a_iterable' avec une boucle \"across\"<\/span>\r\n\tdo<\/span>\r\n\t\tacross<\/span> a_iterable<\/span> as<\/span> la_iterable<\/span> loop<\/span>\r\n\t\t\tprint<\/span>(<\/span>la_iterable<\/span>.<\/span>item<\/span> +<\/span> \"%N\"<\/span>)<\/span>\r\n\t\tend<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Les deux exemples (Java et Eiffel) peuvent utiliser le m\u00eame code d’ex\u00e9cution que pr\u00e9sent\u00e9 plus haut (les exemples avec les it\u00e9rateurs).<\/p>\n
Les tableaux<\/h3>\n
Un tableau (ou \u00ab\u00a0array\u00a0\u00bb) est une structure indexable et it\u00e9rable dont la taille est fixe. L’index d’un tableau doit \u00eatre num\u00e9rique et continue, entre deux bornes (index minimal et index maximal).<\/p>\n
Il est \u00e0 noter qu’en Java, les tableaux (\u00ab\u00a0array\u00a0\u00bb) sont consid\u00e9r\u00e9s comme des types primitifs et ne sont donc pas des classes ou des interfaces. Il est donc \u00e0 d\u00e9duire que les tableaux en Java n’impl\u00e9mentent pas \u00ab\u00a0Iterable\u00a0\u00bb et \u00ab\u00a0Indexable\u00a0\u00bb. Il n’y a \u00e9galement aucune documentation pour les tableaux en Java. Le tutoriel d’utilisation est ici<\/a>.<\/p>\n
La documentation de la classe \u00ab\u00a0ARRAY\u00a0\u00bb en Eiffel est ici<\/a>.<\/p>\n
Voici un exemple de tableau en Java:<\/p>\n
\n
\/**<\/span>\r\n * Affiche les \u00e9l\u00e9ments d'un tableau.<\/span>\r\n *<\/span>\r\n * @param aTableau La structure contenant les \u00e9l\u00e9ments \u00e0 afficher.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> printTableau<\/span>(<\/span>String<\/span>[]<\/span> aTableau<\/span>)<\/span> {<\/span>\r\n    for<\/span>(<\/span>int<\/span> i<\/span> =<\/span> 0<\/span>;<\/span> i<\/span> <<\/span> aTableau<\/span>.<\/span>length<\/span>;<\/span> i<\/span> =<\/span> i<\/span> +<\/span> 1<\/span>){<\/span>\r\n        System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>aTableau<\/span>[<\/span>i<\/span>]);<\/span>\r\n    }<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
On utilise cet exemple en envoyant un tableau de \u00ab\u00a0String\u00a0\u00bb \u00e0 la m\u00e9thode:<\/p>\n
\n
\/**<\/span>\r\n * Ex\u00e9cution de l'exemple.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> execute<\/span>(){<\/span>\r\n    String<\/span>[]<\/span> lTableau<\/span> =<\/span> new<\/span> String<\/span>[<\/span>10<\/span>];<\/span>\r\n    lTableau<\/span>[<\/span>0<\/span>]<\/span> =<\/span> \"Element 1\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>1<\/span>]<\/span> =<\/span> \"Element 2\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>2<\/span>]<\/span> =<\/span> \"Element 3\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>3<\/span>]<\/span> =<\/span> \"Element 4\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>4<\/span>]<\/span> =<\/span> \"Element 5\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>5<\/span>]<\/span> =<\/span> \"Element 6\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>6<\/span>]<\/span> =<\/span> \"Element 7\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>7<\/span>]<\/span> =<\/span> \"Element 8\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>8<\/span>]<\/span> =<\/span> \"Element 9\"<\/span>;<\/span>\r\n    lTableau<\/span>[<\/span>9<\/span>]<\/span> =<\/span> \"Element 10\"<\/span>;<\/span>\r\n    printTableau<\/span>(<\/span>lTableau<\/span>);<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Voici un exemple de \u00ab\u00a0ARRAY\u00a0\u00bb en Eiffel:<\/p>\n
\n
print_from_array<\/span>(<\/span>a_array<\/span>:<\/span>ARRAY<\/span>[<\/span>STRING<\/span>]<\/span>)<\/span>\r\n\t\t-- Affiche les \u00e9l\u00e9ments de `a_array'\"<\/span>\r\n\tlocal<\/span>\r\n\t\tl_index<\/span>:<\/span>INTEGER<\/span>\r\n\tdo<\/span>\r\n\t\tfrom<\/span> l_index<\/span> :=<\/span> a_array<\/span>.<\/span>lower<\/span> until<\/span> l_index<\/span> ><\/span> a_array<\/span>.<\/span>upper<\/span> loop<\/span>\r\n\t\t\tprint<\/span>(<\/span>\"Valeur a l'index \"<\/span> +<\/span> l_index<\/span>.<\/span>out<\/span> +<\/span> \": \"<\/span> +<\/span>\r\n\t\t\t\t\ta_array<\/span>.<\/span>at<\/span> (<\/span>l_index<\/span>)<\/span> +<\/span> \"%N\"<\/span>)<\/span>\r\n\t\t\tl_index<\/span> :=<\/span> l_index<\/span> +<\/span> 1<\/span>\r\n\t\tend<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Pour utiliser cet exemple, envoyer une variable ayant un type conforme \u00e0 \u00ab\u00a0ARRAY\u00a0\u00bb en argument. Voici un exemple simple:<\/p>\n
\n
make<\/span>\r\n\t\t-- Ex\u00e9cute l'exemple<\/span>\r\n\tlocal<\/span>\r\n\t\tl_array<\/span>:<\/span>ARRAY<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tcreate<\/span> l_array<\/span>.<\/span>make_filled<\/span>(<\/span>\"\"<\/span>,<\/span> 1<\/span>,<\/span> 10<\/span>)<\/span>\r\n\t\tl_array<\/span>[<\/span>1<\/span>]<\/span> :=<\/span> \"Element 1\"<\/span>\r\n\t\tl_array<\/span>[<\/span>2<\/span>]<\/span> :=<\/span> \"Element 2\"<\/span>\r\n\t\tl_array<\/span>[<\/span>3<\/span>]<\/span> :=<\/span> \"Element 3\"<\/span>\r\n\t\tl_array<\/span>[<\/span>4<\/span>]<\/span> :=<\/span> \"Element 4\"<\/span>\r\n\t\tl_array<\/span>[<\/span>5<\/span>]<\/span> :=<\/span> \"Element 5\"<\/span>\r\n\t\tl_array<\/span>[<\/span>6<\/span>]<\/span> :=<\/span> \"Element 6\"<\/span>\r\n\t\tl_array<\/span>[<\/span>7<\/span>]<\/span> :=<\/span> \"Element 7\"<\/span>\r\n\t\tl_array<\/span>[<\/span>8<\/span>]<\/span> :=<\/span> \"Element 8\"<\/span>\r\n\t\tl_array<\/span>[<\/span>9<\/span>]<\/span> :=<\/span> \"Element 9\"<\/span>\r\n\t\tl_array<\/span>[<\/span>10<\/span>]<\/span> :=<\/span> \"Element 10\"<\/span>\r\n\t\tprint_from_array<\/span>(<\/span>l_array<\/span>)<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Les listes<\/h3>\n
On appel liste, une structure abstraite indexable et it\u00e9rable ayant la possibilit\u00e9 de changer de taille. L’index d’une liste doit \u00eatre num\u00e9rique et continue, entre deux bornes (index minimal et index maximal).<\/p>\n
La documentation de l’interface \u00ab\u00a0List\u00a0\u00bb de Java est ici<\/a><\/p>\n
La documentation de la classe \u00ab\u00a0LIST\u00a0\u00bb de Eiffel est ici<\/a><\/p>\n
Les listes tableau<\/h4>\n
Une liste tableau (ou \u00ab\u00a0Array List\u00a0\u00bb) est une liste impl\u00e9ment\u00e9e \u00e0 l’aide d’un tableau m\u00e9moire (\u00ab\u00a0Array\u00a0\u00bb). L’avantage d’une liste tableau est qu’elle permet d’acc\u00e9der tr\u00e8s rapidement \u00e0 n’importe quel \u00e9l\u00e9ment de la liste (ordre de complexit\u00e9 O(1)).<\/p>\n
Le grand d\u00e9faut d’une liste tableau, c’est que, comme vu plus haut, un tableau m\u00e9moire est toujours de taille fixe. Donc, qu’afin de pouvoir modifier la taille de la liste, le tableau au complet doit \u00eatre copi\u00e9 dans un nouveau tableau d’une taille acceptable (ce qui est d’ordre de complexit\u00e9 O(n)). Avec optimisation, il est possible de r\u00e9duire cette complexit\u00e9 \u00e0 O(logn).<\/p>\n
\"\"<\/p>\n
Il est important de noter que le tableau n’est pas n\u00e9cessairement de la m\u00eame taille que la liste. En effet, si on retire des \u00e9l\u00e9ments de la liste, la capacit\u00e9 du tableau n’est pas n\u00e9cessairement r\u00e9duite et lorsqu’on ajoute un \u00e9l\u00e9ment dans la liste, le tableau n’est pas obligatoirement agrandit de 1 seul \u00e9l\u00e9ment.<\/p>\n
Nous obtenons donc que la liste a une taille (qui correspond au nombre d’\u00e9l\u00e9ments r\u00e9ellement plac\u00e9 dans la liste) et une capacit\u00e9 (qui correspond \u00e0 au nombre d’\u00e9l\u00e9ments que le tableau interne peut recevoir).<\/p>\n
\"\"<\/p>\n
Il est \u00e0 noter que, dans la majorit\u00e9 des langages, on peut donner une longueur initiale au constructeur des listes tableau afin de donner la capacit\u00e9 initiale du tableau afin d’\u00e9viter que trop de copies soient effectu\u00e9es.<\/p>\n
En g\u00e9n\u00e9ral, on utilise une liste tableau dans le cas o\u00f9 nous savons la taille n\u00e9cessaire (ou g\u00e9n\u00e9ralement n\u00e9cessaire) au travail de la liste.<\/p>\n
La documentation Java de la classe \u00ab\u00a0ArrayList\u00a0\u00bb est ici<\/a>.<\/p>\n
La documentation Eiffel de la classe \u00ab\u00a0ARRAYED_LIST\u00a0\u00bb est ici<\/a><\/p>\n
Notez que vous pouvez voir plusieurs impl\u00e9mentations de Liste tableau dans les exemples ci-dessus.<\/p>\n
Les listes li\u00e9es<\/h4>\n
Une liste li\u00e9e (ou \u00ab\u00a0Linked list\u00a0\u00bb) est une liste cr\u00e9\u00e9e \u00e0 partir de structures appel\u00e9es noeud li\u00e9es entre eux par des pointeurs.<\/p>\n
\"\"<\/p>\n
Les listes li\u00e9es ont beaucoup d’inconv\u00e9nients par rapport aux listes tableau. En premier lieu, chaque \u00e9l\u00e9ment prend plus de place que dans le cas d’une liste tableau (en plus de la valeur, il fait stocker les pointeurs dans chaque noeud). De mani\u00e8re encore plus importante, acc\u00e9der un \u00e9l\u00e9ment par index est tr\u00e8s peu performant puisque la liste doit traverser la liste (une complexit\u00e9 algorithmique de O(n)).<\/p>\n
\"\"<\/p>\n
L’avantage majeur d’une liste li\u00e9e est lorsque la taille maximale de la liste n’est pas connue \u00e0 priori. L’insertion et la suppression se font en temps constant (ordre de complexit\u00e9 d’ordre O(1)).<\/p>\n
On utilise g\u00e9n\u00e9ralement une liste li\u00e9e lorsqu’il est impossible de savoir la taille maximale que la liste aura lors de l’ex\u00e9cution (ou lorsque la taille maximale est tr\u00e8s rarement atteinte et que la taille g\u00e9n\u00e9ralement utilis\u00e9e n’est pas pr\u00e9visible).<\/p>\n
La documentation Java de la classe \u00ab\u00a0LinkedList\u00a0\u00bb est ici<\/a>.<\/p>\n
La documentation Eiffel de la classe \u00ab\u00a0LINKED_LIST\u00a0\u00bb est ici<\/a><\/p>\n
Puisque les listes li\u00e9es, tout comme les listes tableau, respectent l’interface publique de la liste, vous pouvez voir un exemple d’utilisation d’une liste li\u00e9e en modifiant les listes tableaux dans les exemples ci-haut par des listes li\u00e9es.<\/p>\n
Par exemple, en Java:<\/p>\n
\n
\/**<\/span>\r\n * Ex\u00e9cution de l'exemple.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> execute<\/span>(){<\/span>\r\n    List<\/span><<\/span>String<\/span>><\/span> lListe<\/span> =<\/span> new<\/span> LinkedList<\/span><<\/span>String<\/span>>();<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 1\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 2\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 3\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 4\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 5\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 6\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 7\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 8\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 9\"<\/span>);<\/span>\r\n    lListe<\/span>.<\/span>add<\/span>(<\/span>\"Element 10\"<\/span>);<\/span>\r\n    printListe<\/span>(<\/span>lListe<\/span>);<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
Un exemple en Eiffel:<\/p>\n
\n
make<\/span>\r\n\t\t-- Ex\u00e9cute l'exemple<\/span>\r\n\tlocal<\/span>\r\n\t\tl_liste<\/span>:<\/span>LINKED_LIST<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tcreate<\/span> l_liste<\/span>.<\/span>make<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 1\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 2\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 3\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 4\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 5\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 6\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 7\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 8\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 9\"<\/span>)<\/span>\r\n\t\tl_liste<\/span>.<\/span>extend<\/span> (<\/span>\"Element 10\"<\/span>)<\/span>\r\n\t\tprint_from_iterable<\/span>(<\/span>l_liste<\/span>)<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Les distributeurs<\/h3>\n
On appelle distributeur (ou \u00ab\u00a0dispenser\u00a0\u00bb) une structure abstraite permettant d’y d\u00e9poser un \u00e9l\u00e9ment \u00e0 la fois et d’avoir acc\u00e8s \u00e0 un \u00e9l\u00e9ment \u00e0 la fois (l’\u00e9l\u00e9ment doit \u00eatre retir\u00e9 pour avoir acc\u00e8s \u00e0 un autre \u00e9l\u00e9ment).<\/p>\n
Les distributeurs sont parfois appel\u00e9s des sacs (ou \u00ab\u00a0bag\u00a0\u00bb) parce que leurs utilisations ressemblent un peu \u00e0 un sac de piges. On place des \u00e9l\u00e9ments dans le sac et on les retire les un apr\u00e8s les autres. Pour observer un \u00e9l\u00e9ment, il faut le retirer.<\/p>\n
L’impl\u00e9mentation des distributeurs se fait g\u00e9n\u00e9ralement avec des structures li\u00e9es entre elles par des pointeurs (similaire aux listes li\u00e9es).<\/p>\n
Il est \u00e0 noter que le langage Java n’a pas de classe abstraite repr\u00e9sentant ce type de structure.<\/p>\n
La documentation de la classe Eiffel \u00ab\u00a0DISPENSER\u00a0\u00bb est ici<\/a><\/p>\n
Voici un exemple d’utilisation de distributeur en Eiffel:<\/p>\n
\n
remplir_dispenser<\/span>(<\/span>a_dispenser<\/span>:<\/span>DISPENSER<\/span>[<\/span>STRING<\/span>]<\/span>)<\/span>\r\n\t\t-- Ajoute des \u00e9l\u00e9ments dans `a_dispenser'<\/span>\r\n\tdo<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 1\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 2\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 3\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 4\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 5\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 6\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 7\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 8\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 9\"<\/span>)<\/span>\r\n\t\ta_dispenser<\/span>.<\/span>extend<\/span> (<\/span>\"Element 10\"<\/span>)<\/span>\r\n\tend<\/span>\r\n\r\nafficher_dispenser<\/span>(<\/span>a_dispenser<\/span>:<\/span>DISPENSER<\/span>[<\/span>STRING<\/span>]<\/span>)<\/span>\r\n\t\t-- Affiche et vide les \u00e9l\u00e9ments de `a_dispenser'<\/span>\r\n\tdo<\/span>\r\n\t\tfrom<\/span> until<\/span> a_dispenser<\/span>.<\/span>is_empty<\/span> loop<\/span>\r\n\t\t\tprint<\/span>(<\/span>a_dispenser<\/span>.<\/span>item<\/span> +<\/span> \"%N\"<\/span>)<\/span>\r\n\t\t\ta_dispenser<\/span>.<\/span>remove<\/span>\r\n\t\tend<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Pour ex\u00e9cuter cet exemple, nous utiliserons les exemples de Pile et de File que nous verrons ensuite.<\/p>\n
Les files<\/h3>\n
Une file (ou \u00ab\u00a0queue\u00a0\u00bb) est un distributeur utilisant un algorithme de type \u00ab\u00a0premier entr\u00e9, premier sorti\u00a0\u00bb (ou \u00ab\u00a0FIFO\u00a0\u00bb pour \u00ab\u00a0First In, First Out\u00a0\u00bb).<\/p>\n
Pour visualiser cet algorithme, on peut imaginer une file de personnes qui attendent \u00e0 une caisse. G\u00e9n\u00e9ralement, la premi\u00e8re personne \u00e0 \u00eatre arriv\u00e9 dans la file sera la premi\u00e8re personne \u00e0 passer \u00e0 la caisse (\u00e0 \u00eatre retir\u00e9 de la file).<\/p>\n
\"\"<\/p>\n
La documentation de \u00ab\u00a0Queue\u00a0\u00bb en Java est ici<\/a><\/p>\n
La documentation de \u00ab\u00a0QUEUE\u00a0\u00bb en Eiffel est ici<\/a><\/p>\n
Voici un exemple d’utilisation de File en Java:<\/p>\n
\n
\/**<\/span>\r\n * Ajoute des \u00e9l\u00e9ments \u00e0 une file.<\/span>\r\n *<\/span>\r\n * @param aFile La structure \u00e0 ajouter les \u00e9l\u00e9ments.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> remplirFile<\/span>(<\/span>Queue<\/span><<\/span>String<\/span>><\/span> aFile<\/span>)<\/span> {<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 1\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 2\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 3\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 4\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 5\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 6\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 7\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 8\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 9\"<\/span>);<\/span>\r\n    aFile<\/span>.<\/span>add<\/span>(<\/span>\"Element 10\"<\/span>);<\/span>\r\n}<\/span>\r\n\r\n\/**<\/span>\r\n * Affiche et vide les \u00e9l\u00e9ments d'une file.<\/span>\r\n *<\/span>\r\n * @param aFile La structure \u00e0 afficher.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> afficherFile<\/span>(<\/span>Queue<\/span><<\/span>String<\/span>><\/span> aFile<\/span>)<\/span> {<\/span>\r\n    while<\/span> (<\/span>aFile<\/span>.<\/span>peek<\/span>()<\/span> !=<\/span> null<\/span>){<\/span>\r\n        System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>aFile<\/span>.<\/span>element<\/span>());<\/span>\r\n        aFile<\/span>.<\/span>remove<\/span>();<\/span>\r\n    }<\/span>\r\n}<\/span>\r\n\/**<\/span>\r\n * Ex\u00e9cution de l'exemple.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> execute<\/span>(){<\/span>\r\n    Queue<\/span><<\/span>String<\/span>><\/span> lFile<\/span> =<\/span> new<\/span> ArrayDeque<\/span><<\/span>String<\/span>>();<\/span>\r\n    remplirFile<\/span>(<\/span>lFile<\/span>);<\/span>\r\n    afficherFile<\/span>(<\/span>lFile<\/span>);<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
L’exemple d’utilisation en Eiffel utilisera les m\u00e9thodes d\u00e9velopp\u00e9 dans la section \u00ab\u00a0distributeur\u00a0\u00bb (les m\u00e9thodes \u00ab\u00a0remplir_dispenser\u00a0\u00bb et \u00ab\u00a0afficher_dispenser\u00a0\u00bb:<\/p>\n
\n
make<\/span>\r\n\t\t-- Ex\u00e9cute l'exemple<\/span>\r\n\tlocal<\/span>\r\n\t\tl_queue<\/span>:<\/span>LINKED_QUEUE<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tcreate<\/span> l_queue<\/span>.<\/span>make<\/span>\r\n\t\tremplir_dispenser<\/span>(<\/span>l_queue<\/span>)<\/span>\r\n\t\tafficher_dispenser<\/span>(<\/span>l_queue<\/span>)<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Le r\u00e9sultat des codes Java et Eiffel ci-dessus est:<\/p>\n
Element 1\r\nElement 2\r\nElement 3\r\nElement 4\r\nElement 5\r\nElement 6\r\nElement 7\r\nElement 8\r\nElement 9\r\nElement 10<\/pre>\n
Les piles<\/h3>\n
Une pile (ou \u00ab\u00a0stack\u00a0\u00bb) est un distributeur utilisant un algorithme de type \u00ab\u00a0dernier entr\u00e9, premier sorti\u00a0\u00bb (ou \u00ab\u00a0LIFO\u00a0\u00bb pour \u00ab\u00a0Last In, First Out\u00a0\u00bb).<\/p>\n
Pour visualiser cet algorithme, on peut imaginer une pile d’assiettes. G\u00e9n\u00e9ralement, on prend l’assiette qui est sur le dessus de la pile et lorsqu’on d\u00e9pose une assiette, on la d\u00e9pose sur la pile.<\/p>\n
\"\"<\/p>\n
La documentation Java de \u00ab\u00a0Stack\u00a0\u00bb est ici<\/a><\/p>\n
La documentation Eiffel de \u00ab\u00a0STACK\u00a0\u00bb est ici<\/a><\/p>\n
Voici un exemple d’utilisation d’une pile en Java:<\/p>\n
\n
\/**<\/span>\r\n * Ajoute des \u00e9l\u00e9ments \u00e0 une pile.<\/span>\r\n *<\/span>\r\n * @param aPile La structure \u00e0 ajouter les \u00e9l\u00e9ments.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> remplirPile<\/span>(<\/span>Stack<\/span><<\/span>String<\/span>><\/span> aPile<\/span>)<\/span> {<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 1\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 2\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 3\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 4\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 5\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 6\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 7\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 8\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 9\"<\/span>);<\/span>\r\n    aPile<\/span>.<\/span>push<\/span>(<\/span>\"Element 10\"<\/span>);<\/span>\r\n}<\/span>\r\n\r\n\/**<\/span>\r\n * Affiche et vide les \u00e9l\u00e9ments d'une pile.<\/span>\r\n *<\/span>\r\n * @param aPile La structure \u00e0 afficher.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> afficherPile<\/span>(<\/span>Stack<\/span><<\/span>String<\/span>><\/span> aPile<\/span>)<\/span> {<\/span>\r\n    while<\/span> (!<\/span>aPile<\/span>.<\/span>empty<\/span>()){<\/span>\r\n        System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>aPile<\/span>.<\/span>peek<\/span>());<\/span>\r\n        aPile<\/span>.<\/span>pop<\/span>();<\/span>\r\n    }<\/span>\r\n}<\/span>\r\n\r\n\/**<\/span>\r\n * Ex\u00e9cution de l'exemple.<\/span>\r\n *\/<\/span>\r\npublic<\/span> void<\/span> execute<\/span>(){<\/span>\r\n    Stack<\/span><<\/span>String<\/span>><\/span> lPile<\/span> =<\/span> new<\/span> Stack<\/span><<\/span>String<\/span>>();<\/span>\r\n    remplirPile<\/span>(<\/span>lPile<\/span>);<\/span>\r\n    afficherPile<\/span>(<\/span>lPile<\/span>);<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
L’exemple d’utilisation en Eiffel utilisera les m\u00e9thodes d\u00e9velopp\u00e9es dans la section \u00ab\u00a0distributeur\u00a0\u00bb (les m\u00e9thodes \u00ab\u00a0remplir_dispenser\u00a0\u00bb et \u00ab\u00a0afficher_dispenser\u00a0\u00bb:<\/p>\n
\n
make<\/span>\r\n\t\t-- Ex\u00e9cute l'exemple<\/span>\r\n\tlocal<\/span>\r\n\t\tl_stack<\/span>:<\/span>LINKED_STACK<\/span>[<\/span>STRING<\/span>]<\/span>\r\n\tdo<\/span>\r\n\t\tcreate<\/span> l_stack<\/span>.<\/span>make<\/span>\r\n\t\tremplir_dispenser<\/span>(<\/span>l_stack<\/span>)<\/span>\r\n\t\tafficher_dispenser<\/span>(<\/span>l_stack<\/span>)<\/span>\r\n\tend<\/span>\r\n<\/pre>\n<\/div>\n
Le r\u00e9sultat des codes Java et Eiffel ci-dessus est:<\/p>\n
Element 10\r\nElement 9\r\nElement 8\r\nElement 7\r\nElement 6\r\nElement 5\r\nElement 4\r\nElement 3\r\nElement 2\r\nElement 1<\/pre>\n
Sac al\u00e9atoire<\/h3>\n
Un sac al\u00e9atoire (ou \u00ab\u00a0Random Bag\u00a0\u00bb ou \u00ab\u00a0Random Queue\u00a0\u00bb) est un distributeur dans lequel l’\u00e9l\u00e9ment qui est lu et retir\u00e9 est choisi au hasard dans le distributeur.<\/p>\n
Il est important de comprendre que tant que l’\u00e9l\u00e9ment n’est pas retir\u00e9, l’\u00e9l\u00e9ment lu ne doit pas changer. La seule fa\u00e7on de modifier l’\u00e9l\u00e9ment \u00e0 lire est de retirer l’\u00e9l\u00e9ment en question.<\/p>\n
L’impl\u00e9mentation d’un sac al\u00e9atoire n’est pas incluse dans Java ni dans Eiffel. Son impl\u00e9mentation est laiss\u00e9e en exercice aux plus courageux.<\/p>\n
Les \u00ab\u00a0buffers\u00a0\u00bb circulaires<\/h3>\n
Une file est une structure tr\u00e8s utile, mais dans certains contextes, elle peut \u00eatre lourde \u00e0 impl\u00e9menter. En effet, lorsqu’un programme est fait dans un environnement bas niveau (langage C ou assembleur, programmation de microcontr\u00f4leur, etc.) ou lorsque la performance est un \u00e9l\u00e9ment cl\u00e9 du programme, on peut remplacer une file par un \u00ab\u00a0buffer\u00a0\u00bb circulaire.<\/p>\n
Le \u00ab\u00a0buffer\u00a0\u00bb se comporte normalement comme une file (algorithme FIFO). Par contre, contrairement \u00e0 une file, le \u00ab\u00a0buffer\u00a0\u00bb circulaire est limit\u00e9 en taille. Il s’agit donc d’une sorte de file pouvant contenir un nombre maximal d’\u00e9l\u00e9ments.<\/p>\n
Voici comment on impl\u00e9mente un \u00ab\u00a0buffer\u00a0\u00bb circulaire:<\/p>\n