Cours XSLT : Transformation et Formatage de documents XML
Récursivité en XSL
Pourquoi et comment utiliser la récursivité dans les transformations XSL ?
1
Les limites de XSL
n La modification des variables est impossible
n Pas de boucle de type pour i de 1 à n
n Complexifie le codage de certains algorithmes pourtant simples à la base
Solution : la récursivité
n Utilisation de template récursif
n C’est-à-dire un template qui se rappelle lui-même
n Au lieu de modifier les variables, on modifie les paramètres du template
Exemple de problème n°1
n On cherche à déterminer le maximum dans une liste de nombres :
111 27 9
57
2
363
Algorithme simple
max ß premier élément nombre de listeNombres
Pour chaque élément nombre de listeNombres si nombre > max
alors max ß nombre
fsi
Finpour
Écrire max
Problème :
en XSL on ne peut pas modifier la valeur de max
Algorithme récursif
Fonction RechercheMax(max, indice){ si indice = nbéléments(listeNombres) alors si listNombre[indice] > max
alors écrire listNombre(indice) sinon écrire max
fsi
sinon si listNombre[indice] > max alors rechercheMax(listNombre[indice], indice + 1)
sinon rechercheMax(max, indice +1) fsi fsi
}
Premier appel : RechercheMax(listNombres[1],2)
|
…
…
Exemple de problème n°2
n Énoncé
n A partir d’une liste de nombres décimaux naturels, on souhaite récupérer un fichier XML contenant les mêmes nombres en
binaire
Exemple de problème n°2
0 1 2 3 4 |
0 1 10 11 100naire>
|
9
Algorithme récursif
Algorithme à appliquer pour chaque nombre de la listeNombre
fonction transformationBinaire(n:entier)
début si n
alors écrire(n)
sinon transformationBinaire(n ÷ 2) écrire(n mod 2) fsi fin
Template XSL correspondant
//écrire nb
//écrire nb mod 2
Exemple de problème n°3
n Énoncé
n A partir d’une liste de nombres décimaux naturels, on souhaite récupérer un fichier XML contenant les factoriels de chaque nombre
n Rappels :
n 0! = 1
n 1! = 1
n 4! = 4x3x2x1
n 5! = 5x4x3x2x1 = 5x4! (d’où la récursivité)
Exemple de problème n°3
0 1 2 3 4 |
1 1 2 6 24 |
Algorithme non récursif
Fonction calculFactoriel (n:entier) début pour i de n à 1
résultat= résultat * i
finpour écrire résultat
fin
Problèmes:
n Pas de boucles de ce type en XSL
n Impossible de revaloriser une variable en XSl
n Pas propre : ne suit pas la définition mathématique n! = n x (n-1)!
Algorithme récursif
n Il suffit de reprendre la définition mathématique :
n n!= n x (n-1)!
n 0! = 1
Fonction calculFactoriel(n:entier) début
si n=0 alors résultat ß 1
sinon résultat ß n * calculFactoriel (n-1)
fsi
écrire résultat fin
n Ecrire la XSL correspondante
n Solution
n ,
n Représentation en XML
n Parcours
n Algorithmes divers
17
Représentation des arbres B
n Essayons de représenter l’arbre suivant en fichier XML
Représentation des arbres B
Représentation arborescente
œud>
œud>
œud>
œud>
œud>
Représentation des arbres B
Représentation « à plat »
1
2
3
4
5
6
7 8
9
Avec fg: fils gauche et fd: fils droit
Les parcours d’arbres
n Parcours préfixé
n Parcours infixé
n Parcours postfixé
n Principe
n Il consiste à visiter le contenu du nœud dès qu'on est dessus, ensuite on parcourt son fils gauche puis son fils droit
Ainsi l’affichage de cet arbre en ordre préfixé donnerait :
1,2,4,5,7,8,3,6,9
n Algorithme :
fonction imprimerPréfixé(arbre : ArbreBinaireChaîne, noeud : Noeud)
début si non noeudvide(arbre,noeud) alors écrire(val(arbre, noeud))
imprimerPréfixé(arbre, fg(arbre, noeud)) imprimerPréfixé(arbre, fd(arbre, noeud))
fsi
fin
n Remarque :
n le paramètre noeud est nécessaire pour pouvoir utiliser la récursivité, il est la racine du sous-arbre en cours de traitement
n A l'appel de la fonction, noeud est la racine de arbre
Parcours préfixé en XSL:
Parcours postfixé
n Principe
n Il consiste à afficher le contenu du nœud après avoir parcouru et affiché ses deux fils
Ainsi l’affichage de cet arbre en ordre postfixé donnerait : 4,7,8,5,2,9,6,3,1
25
Parcours postfixé
n Algorithme
n Voici l’algorithme qui imprime un arbre dans l’ordre postfixé :
fonction imprimerPostfixé(arbre : ArbreBinaireChaîne, noeud : Noeud) début si non noeudvide(arbre, noeud) alors imprimerPostfixé(arbre, fg(arbre, noeud)) imprimerPostfixé(arbre, fd(arbre, noeud)) écrire(val(arbre, noeud))
fsi
fin
26
Parcours postfixé XSL: ,
n Principe
n Il consiste à visiter le contenu du noeud après avoir visité le contenu de son fils gauche; une fois que c'est fait, on visite son fils droit
Ainsi l’affichage de cet arbre en ordre infixé donnerait :
1,3,4,6,7,7,10,14,13
On remarque que cela affiche les valeurs dans l’ordre croissant lorsqu’on a affaire avec un arbre de recherche
28
n Algorithme :
fonction imprimerPostfixé(arbre : ArbreBinaireChaîne, noeud : Noeud) début si non noeudvide(arbre, noeud) alors imprimerPostfixé(arbre, fg(arbre, noeud)) écrire(val(arbre, noeud))
imprimerPostfixé(arbre, fd(arbre, noeud))
fsi
fin
29
Parcours infixé XSL: ,
Évaluation d’une expression
n Création de l’arbre d’une expression booléenne
n Évaluation de l’expression
31
n Représentation
n L’opérateur dans la racine et les valeurs dans les fils
32
Évaluation d’une expression booléenne représentée sous forme d’un arbre binaire
Les étapes de résolution
33
Algorithme
fonction evaluerExpression(arbre:arbreBin, nœud:Noeuds){
si val(arbre, nœud) = vrai
alors retourne vrai fsi
si val(arbre, nœud) = faux
alors retourne faux
fsi si val (arbre, nœud) = ‘et’
alors valFg ß evaluerExpression(arbre, fg(arbre, nœud) valFd ß evaluerExpression(arbre, fd(arbre, nœud) retrourne ( valFg et valFd)
fsi si val (arbre, nœud) = ‘ou’
alors valFg ß evaluerExpression(arbre, fg(arbre, nœud) valFd ß evaluerExpression(arbre, fd(arbre, nœud) retrourne ( valFg ou valFd)
fsi
}
valFg, valFd : booléen
XSL
//résultat du template
//résultat du template
./@val"/> //résultat du template
Combinaison de deux templates récursifs
n Principe
n Cette technique est très utile pour traiter la plupart
des problèmes à plusieurs dimensions n Elle consiste à utiliser plusieurs templates récursifs, dont certains font appel à d’autres
36
n Création d’une table de multiplication
n Une table de multiplication est représentée par un tableau à deux dimensions
n C’est pourquoi, il est judicieux de combiner deux templates récursifs
Exemple
n Les templates
n Le premier dessinera les lignes du tableau et utilisera le deuxième afin de dessiner les cellules pour chaque colonne de la ligne
Exemple :
Création d’une table de multiplication
n Objectif :
n A partir d’un fichier XML contenant des informations sur le nombre de lignes et de colonnes, il s’agit de créer une table de multiplication au format HTML
Template drawRow
// ligne suivante
| |
|
Template drawCell
//test de la position
#CCCCCC white
n Énoncé
n Inspirez-vous de l’exemple précédent pour construire le triangle de Pascal. On peut griser les 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
n Algorithme récursif function Pascal(x, y: integer): integer;
begin
if (x = 1) or (y = x) then Pascal := 1 else Pascal := Pascal(x, y - 1) + Pascal(x -
1, y - 1); end;
43
n Solution :
n
Les tours de Hanoi
n Résolution du problème des tours de
Hanoi
45
Les tours de Hanoi
n Explications
n Soient trois tours. Sur l'une d'entre sont empilés des disques par taille décroissante :
T1 T2 T3
n Le but du jeu consiste à déplacer les n disques de la tour de départ vers une des deux autres tours
Les tours de Hanoi
n Règles de déplacement :
n on ne peut déplacer qu'un seul disque à la fois
n un disque ne peut pas se trouver sur un disque de diamètre inférieur
Les tours de Hanoi
Algorithme de résolution du problème
fonction hanoï(nombredisques: entier, départ: chaîne, arrivée: chaîne, intermédiaire: chaîne)
début si nombredisques 0 alors hanoï(nombredisques-1, départ, intermédiaire, arrivée ) écrire(" déplacer le disque ", nombredisques, " de ", départ, " vers ", arrivée)
hanoï(nombredisques-1, intermédiaire, arrivée, départ )
fsi fin
Les tours de Hanoi
Test>
HanoiSize="3"/> Test>
// Appel
Résultat
n Énoncé
n TD-XSL-recursif
53