426
A Rappels algorithmiques
– la première fonction, premièreLettre, renvoie le premier symbole de la
chaîne ;
– la deuxième fonction finChaîne renvoie le premier suffixe de la chaîne si elle
est non vide, c’est-à-dire, la chaîne privée de son premier symbole.
Nous définissons d’abord le type Trie. Un champ de type Noeud permet de
repérer la racine du trie.
Struct Trie
Noeud racine
Le type Noeud est le type d’un nœud générique. Par définition, un trie admet
des nœuds de deux types. Les nœuds internes servent à guider le parcours dans
l’arbre et ne contiennent pas de données. Les nœuds externes contiennent des
chaînes de caractères correspondant à des suffixes de clés. Une manière élégante
pour l’implantation est d’employer des mécanismes de langages à objets. Ceux-ci
permettent de faire dériver deux sous-classes (nœuds externes et internes) d’une
classe nœud. Par commodité et aussi car ce n’est pas le propos de ce livre de manier
les concepts de programmation objet, la classe Noeud ci-après peut représenter un
nœud externe ou interne.
Struct Noeud
chaîne texte
dict enfant
Pour la structure Noeud, le champ enfant de type dict est une table
d’association, et s’apparente à un dictionnaire dans le langage Python. Ce champ
permet d’associer efficacement à une lettre de l’alphabet le nœud fils correspondant.
Lorsque le champ enfant est vide, ou plus exactement possède la valeur None, le
nœud est externe, sinon il est interne. Nous utiliserons des fonctions pour manipuler
ce champ :
– l’accès au fils par la lettre c se fait grâce à l’instruction “N.enfant[c]” ;
– Pour le test d’appartenance d’une clé, le prédicat “lettre dans N.enfant”
renvoie Vrai ou Faux selon que le nœud N admet ou non un fils pour la lettre c
(syntaxe ici encore directement inspirée du langage Python).
– Enfin nous supprimons le fils associé à la lettre c d’un nœud N grâce à
l’instruction “del N.Enfant[c]”.
Notons que le champ texte n’a d’utilité que pour un nœud externe. Nous
l’affecterons à la valeur chaîne vide "" pour un nœud interne par convention.
Nous définissons également un « constructeur » pour une structure de type
Noeud: l’appel à nouveauNoeud(txt) avec en argument une chaîne de caractères
txt de type chaîne renvoie le nouveau nœud externe créé dont les champ texte
et enfant sont initialisés respectivement à la valeur de la variable txt et None.
A Rappels algorithmiques
– la première fonction, premièreLettre, renvoie le premier symbole de la
chaîne ;
– la deuxième fonction finChaîne renvoie le premier suffixe de la chaîne si elle
est non vide, c’est-à-dire, la chaîne privée de son premier symbole.
Nous définissons d’abord le type Trie. Un champ de type Noeud permet de
repérer la racine du trie.
Struct Trie
Noeud racine
Le type Noeud est le type d’un nœud générique. Par définition, un trie admet
des nœuds de deux types. Les nœuds internes servent à guider le parcours dans
l’arbre et ne contiennent pas de données. Les nœuds externes contiennent des
chaînes de caractères correspondant à des suffixes de clés. Une manière élégante
pour l’implantation est d’employer des mécanismes de langages à objets. Ceux-ci
permettent de faire dériver deux sous-classes (nœuds externes et internes) d’une
classe nœud. Par commodité et aussi car ce n’est pas le propos de ce livre de manier
les concepts de programmation objet, la classe Noeud ci-après peut représenter un
nœud externe ou interne.
Struct Noeud
chaîne texte
dict enfant
Pour la structure Noeud, le champ enfant de type dict est une table
d’association, et s’apparente à un dictionnaire dans le langage Python. Ce champ
permet d’associer efficacement à une lettre de l’alphabet le nœud fils correspondant.
Lorsque le champ enfant est vide, ou plus exactement possède la valeur None, le
nœud est externe, sinon il est interne. Nous utiliserons des fonctions pour manipuler
ce champ :
– l’accès au fils par la lettre c se fait grâce à l’instruction “N.enfant[c]” ;
– Pour le test d’appartenance d’une clé, le prédicat “lettre dans N.enfant”
renvoie Vrai ou Faux selon que le nœud N admet ou non un fils pour la lettre c
(syntaxe ici encore directement inspirée du langage Python).
– Enfin nous supprimons le fils associé à la lettre c d’un nœud N grâce à
l’instruction “del N.Enfant[c]”.
Notons que le champ texte n’a d’utilité que pour un nœud externe. Nous
l’affecterons à la valeur chaîne vide "" pour un nœud interne par convention.
Nous définissons également un « constructeur » pour une structure de type
Noeud: l’appel à nouveauNoeud(txt) avec en argument une chaîne de caractères
txt de type chaîne renvoie le nouveau nœud externe créé dont les champ texte
et enfant sont initialisés respectivement à la valeur de la variable txt et None.