Actualité

[[{"text":"

Imaginons une bibliothèque qui contienne vraiment beaucoup de livres l, répartis dans 17 576 salles reliées les unes aux autres par des portes.

Chaque salle contient une porte d'entrée et, possiblement, deux portes de sorties vers deux autres salles.

Pour retrouver facilement l'emplacement d'un livre, les bibliothécaires astucieux ont eu l'idée suivante. Dans la toute première salle, dans laquelle on entre par la porte d'entrée de la bibliothèque, ils ont mis tous les ouvrages dont le titre commence par MDB.

Si en revanche le titre commence par trois lettres venant avant MDB dans l'ordre alphabétique, alors il faut prendre la porte de sortie de gauche. Sinon, il faut prendre la porte

de sortie de droite.

On continue alors la recherche dans la salle suivante.

Si on est allé dans la salle de gauche, par exemple, on y trouve tous les ouvrages dont le titre commence par GBN. Là, de même, si le titre commence par trois lettres venant avant GBN dans l'ordre alphabétique, alors il faut prendre la porte de sortie de gauche, sinon la porte de droite. Et ainsi de

suite jusqu'à ce qu'on parvienne à la salle contenant tous les livres dont les trois premières lettres du titre sont celles du titre qui nous intéresse.

Une telle organisation est incroyablement efficace. En effet, avec la répartition choisie par les bibliothécaires, il ne faut jamais traverser plus de 15 salles pour trouver un ouvrage, alors qu'il y à, rappelons-le, 17576 salles au total.

******

Lu LHABIUS 7e PULIED WING UE IEUNIGIUIIS

On peut visualiser les salles de cette bibliothèque comme un arbre binaire, où chaque nœud correspond à une salle.

Un nœud est étiqueté par un mot de trois lettres et ses deux sous-arbres correspondent aux salles adjacentes.

Dans l'exemple ci-dessus, le haut de cet arbre ressemble à ceci :

___MDB____

/ \\

_GEN_ _SEP_

/ \\ / \\

... _JOH_ ... ...

/ \\

... ...

Comme on l'a compris, quand on se dirige du côté gauche, on trouve des mots plus petits dans l'ordre alphabétique et quand on se dirige du côté droit, on trouve des mots plus grands. Et cette propriété n'est pas vraie seulement pour la racine.

Elle est valable pour tous les nœuds de l'arbre.

Ainsi, dans le sous-arbre droit du nœud marqué JCH, on trouvera des mots plus grands que JCH et plus petits que MDB (car on reste à gauche de la racine).

De même, dans le sous-arbre gauche du nœud marqué SEP, on trouvera des mots plus petits que SEP mais plus grands que MDB (car on reste à droite de la racine).Et ainsi de suite.

On appelle cela un arbre binaire de recherche.

","title":"Arbres binaires de recherche","tagtitle":"h1"},{"edit":"

"}],[{"text":"

D'une manière générale, un arbre binaire de recherche (abrégé en ABR ou en anglais BST Binary Search Tree) est un arbre binaire dont les nœuds contiennent des valeurs qui peuvent être comparées entre elles, comme des entiers ou des chaînes de caractères par exemple, et tel que, pour tout nœud de l'arbre, toutes les valeurs situées dans le sous-arbre gauche (resp. droit) sont plus petites (resp. plus grandes) que la valeur située dans le nœud.

Ainsi, les deux arbres de gauche sont des ABR, mais celui de droite n'en est pas un:

___3___

/ \\

_1_ _4_

/ \\ / \\

_2_

/ \\

___3___

/ \\

_2_ _4_

/ \\ / \\

_1_

/ \\

___3___

/ \\

_2_ _4_

/ \\ / \\

_1_

/ \\

Pour l'arbre de droite, la propriété est bien vérifiée pour la racine, mais

elle ne l'est pas pour le nœud étiqueté par 2, qui contient 1 dans son sous-

arbre droit.

Comme l'illustrent les deux arbres de gauche, les mêmes valeurs peuvent être stockées dans plusieurs ABR différents.

","title":"Notion"},{"edit":"

"}],[{"text":"

Représentation en Python

Un ABR étant un arbre binaire, on le représente en Python exactement comme à la séquence précédente avec notre classe Noeud.

On nc fait qu'ajouter deux

contraintes :

- les valeurs contenues dans les nœuds peuvent être comparées avec les opérations <, >=, etc., de Python (c'est le cas des entiers et des chaînes de caractère notamment);

- les arbres vérifient la propriété d'ABR.

Ces deux contraintes ne sont pas encodées en Python.

Elles sont uniquement supposées ou garanties, selon le cas, par les fonctions que nous allons écrire dans les sections suivantes.

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

def __eq__(self, n):

return n is not None \\

and self.gauche == n.gauche \\

and self.valeur == n.valeur \\

and self.droit == n.droit

","title":""},{"edit":"

"}],[{"text":"

Opérations

Les fonctions définies à la séquence précédent sur les arbres binaires, à savoir taille, hauteur et parcours_infixe restent valables pour des ABR.

En particulier, le parcours infixe d'un ABR affiche les valeurs contenues dans

l'ABR par ordre croissant.

En effet, il commence par afficher les valeurs du sous-arbre gauche, puis affiche la racine, et affiche enfin les valeurs du sous-arbre droit.

Dans ce qui suit, nous allons maintenant programmer des opérations qui sont spécifiques aux ABR.

","title":""},{"edit":"

"}],[{"text":"

Comme on l'a compris avec l'exemple introductif, la propriété d'ABR

tire tout son intérêt de l'efficacité de la recherche qu'elle permet.

En effet, pour chercher une valeur dans un ABR, il suffit de la comparer à la valeur à la racine puis, si elle est différente, de se diriger vers un seul des deux sous-arbres.

On élimine ainsi complètement la recherche dans l'autre sous-arbre.

Écrivons une fonction

def appartient(x, a):

qui détermine si la valeur x apparaît dans l'ABR a.

On commence par le cas d'un arbre vide, pour lequel la réponse est évidente.

if a is None:

return False

Dans le cas contraire, cela veut dire que l'arbre contient au moins un nœud.

On peut donc comparer la valeur x avec la valeur située à la racine de l'arbre, c'est-à-dire a.valeur.

Si la valeur x est plus petite, il faut continuer la recherche dans le sous-arbre gauche, ce que l'on fait récursivement.

if x < a.valeur:

return appartient(x, a.gauche)

(Ne pas oublier le return, pour renvoyer le résultat de l'appel récursif.)

Si la valeur x est en revanche plus grande que a.valeur, alors on procède de même à une recherche dans le sous-arbre droit.

elif x > a.valeur:

return appartient(x, a.droit)

Enfin, si elle n'est ni plus petite ni plus grande, c'est que les deux valeurs

sont égales.

Autrement dit, la valeur x apparaît à la racine de l'arbre, ce que l'on signale en renvoyant True.

else:

return True

Le code complet est le suivant :

Programme — Recherche dans un ABR

def appartient(x, a):

\"\"\"détermine si x apparaît dans l'ABR a\"\"\"

if a is None:

return False

if x < a.valeur:

return appartient(x, a.gauche)

elif x > a.valeur:

return appartient(x, a.droit)

else:

return True

Tester le programme appartient avec les instructions suivantes et conclure:

a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\

8, \\

Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))

print(appartient(2,a5))

print(appartient(15,a5))

Efficacité

Quelle est l'efficacité de la fonction appartient, en terme du nombre d'opérations effectuées pour rechercher une valeur x dans un arbre à qui contient N éléments?

Si les éléments sont répartis à peu près équitablement entre les deux sous-arbres, la fonction appartient élimine la moitié des éléments à chaque étape.

Cela fait écho à la recherche dichotomique dans un tableau trié, où chaque étape divise par deux le nombre d'éléments à examiner.

Comme on l'a vu, c'est extrêmement efficace. Ainsi, il ne faut pas plus de 20 étapes pour chercher parmi un million de valeurs.

D'autre part, il n'y aucun risque de provoquer l'erreur RecursionError dans

ce cas.

Cela étant, rien ne garantit que les éléments sont équitablement répartis, à chaque étape, entre les deux sous-arbres.

En particulier, l'arbre a peut tout à fait être un peigne, comme les deux arbres suivants :

__O_ __O__

/ \\ / \\

__O__ __O__

/ \\ / \\

__O__ __O__ / \\ / \\

ou plus généralement un arbre complètement filiforme dont la hauteur est égale au nombre de nœuds.

Dans ce cas, la recherche est au contraire peu efficace, car elle est susceptible de parcourir l'arbre tout entier, par exemple dans le cas

d'une recherche infructueuse.

À cet égard, un ABR linéaire n'est pas meilleur qu'une liste chaînée.

D'une manière générale, le coût de la recherche dans un ABR est majoré par sa hauteur. En effet, chaque étape de la recherche descend dans l'un des deux sous-arbres. Du coup, on ne peut répéter cela un nombre de fois plus grand que la hauteur de l'arbre, par définition.

La hauteur d'un ABR dépend directement de la façon dont il a été construit, ce qui est discuté dans les deux sections suivantes.

","title":"Recherche dans un ABR"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Nous allons écrire une fonction ajoute(x, a) qui ajoute un nouvel élément x dans l'ABR a.

Ainsi, nous pourrons construire des ABR par ajouts successifs d'éléments avec la fonction ajoute, en partant d'un arbre vide.

Dans le principe, ajouter un nouvel élément dans un ABR n'est pas plus compliqué que de le chercher :

- s'il est plus petit, on va à gauche; - s'il est plus grand, on va à droite.

Et quand on arrive à un arbre vide, on ajoute un nouveau nœud.

Si par exemple il s'agit d'ajouter l'élément 2 dans l'arbre

___3___

/ \\

_1_ _4_

/ \\ / \\

alors on commence par aller à gauche, car 2 est plus petit que 3, puis on va à droite, car 2 est plus grand que 1, puis enfin on ajoute un nouveau nœud contenant 2 car on est arrivé sur un arbre vide.

On obtient donc cet arbre :

___3___

/ \\

_1_ _4_

/ \\ / \\

_2_

/ \\

En pratique, cependant, il n'est pas si facile de mettre en œuvre cette idée.

Naïvement, on pourrait penser que la fonction ajoute ne renvoie rien et se contente de modifier l'arbre reçu en argument, pour lui greffer un nouveau nœud.

Mais si l'arbre est vide, c'est-à-dire vaut None, une telle modification n'est pas possible. [l faudrait faire alors un cas particulier pour l'insertion dans un arbre vide, en dehors de notre fonction ajoute, ce qui est extrêmement déplaisant.

Par ailleurs, il faudrait faire également des cas particuliers dans la fonction ajoute elle-même, lorsqu'elle s'apprête à se rappele récursivement sur un sous-arbre vide.

Pour cette raison, nous allons adopter la même approche qu'avec les listes chaînées, à savoir ne pas modifier les arbres reçus en arguments mais en renvoyer de nouveaux.

Dit autrement, nous choisissons d'utiliser nos objets de classe Noeud de façon immuable, comme nous l'avions fait avec les objets de la classe Cellule.

Écrivons donc une fonction ajoute qui renvoie un nouvel arbre contenant x et tous les éléments de a.

def ajoute(x, a):

Comme pour la recherche, on procède récursivement.

Le cas de base est celui de l'ajout dans un arbre vide. Dans ce cas, il convient de renvoyer un arbre contenant un unique nœud, dont la valeur est x.

iF a is None:

return Noeud(None, x, None)

Si en revanche l'arbre a n'est pas vide, on compare x et a.valeur. Si x est plus petit, on doit l'ajouter dans le sous-arbre gauche.

L'appel récursif ajoute(x, a.gauche) nous renvoie, par définition, un arbre qui contient x et tous les éléments de a.gauche.

C'est le sous-arbre gauche de notre résultat, par dessus lequel nous réinstallons une racine de même valeur a.valeur et un sous-arbre droit a.droit inchangé.

if x < a.valeur:

return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)

Si en revanche x est supérieur ou égal à a.valeur, on doit l'ajouter au sous-

arbre droit.

On procède de façon similaire, avec cette fois un appel récursif ajoute(x,a.droit).

else:

return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))

On note qu'on ne fait pas ici de traitement particulier dans le cas où x est égal à a.valeur.

Ceci est discuté un tout petit peu plus loin.

Ceci achève donc notre fonction ajoute. Le code complet est le suivant :

Programme — Ajout dans un ABR

def ajoute(x, a):

\"\"\"ajoute x à l'arbre a, renvoie un nouvel arbre\"\"\"

if a is None:

return Noeud(None, x, None)

if x < a.valeur:

return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)

else:

return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))

Tester le programme avec les instructions suivantes et conclure :

a1 = ajoute(8,None)

a1 = ajoute(4,a1)

a1 = ajoute(2,a1)

a1 = ajoute(5,a1)

a1 = ajoute(12,a1)

a1 = ajoute(10,a1)

a1 = ajoute(14,a1)

affiche1(a1)

print()

Efficacité

La complexité de notre fonction ajoute n'est pas différente de celle de la fonction appartient. En effet, on prend exactement les mêmes décisions quant à la descente dans l'arbre et, comme pour la fonction appartient, on fait un nombre borné d'opérations à chaque étape.

La conclusion est donc la même :

la complexité dépend de la forme de l'arbre et elle est, dans le pire des cas, majorée par sa hauteur.

En ce qui concerne l'utilisation de la

mémoire, la fonction ajoute construit autant de nœuds qu'elle fait d'appels

récursifs. Sa complexité en espace est donc comparable à sa complexité en temps.

Exactement comme pour la concaténation des listes chaînées, certaines parties de l'arbre a sont réutilisées dans le résultat renvoyé par ajoute(x, a) et d'autres parties sont en revanche «dupliquées».

Plus précisément, tous les nœuds le long de la descente sont dupliqués et

tous les sous-arbres dans lesquels on ne descend pas sont partagés. Re-

prenons l'exemple ci-dessus où on ajoute successivement les éléments 3, 1

et 4, dans cet ordre, dans un arbre initialement vide. Quand on exécute

a = ajoute(3, None), on obtient un arbre réduit à un seul nœud, qui vient

d'être créé :

_3_

/. \\

Quand ensuite on exécute a = ajoute(1,a), ce nœud contenant 3 est dupliqué, par le return Noeud(...) qui encadre l'appel récursif pour insérer 1 dans le sous-arbre gauche. Puis un nouveau nœud contenant 1 est créé et on obtient au final un arbre qui ne partage rien avec le précédent :

_3_

/ \\

_1_

/ \\

En revanche, les choses deviennent plus subtiles quand on poursuit avec a = ajoute(4,a) car cette fois le sous-arbre gauche est partagé entre l'argument et le résultat. La racine contenant 3 est de nouveau dupliquée et bien sûr un nouveau nœud contenant 4 est construit. On peut l'illustrer ainsi, avec à gauche l'arbre passé en argument et à droite l'arbre renvoyé en résultat :

*****

Comme pour les listes, il n'y a pas de danger à réaliser un tel partage, tant

qu'on ne modifie pas (par des affectations) les sous-arbres ainsi partagés. Vu que notre fonction ajoute ne fait aucune affectation, il n'y a aucun risque tant qu'on se limite à cette fonction.

En première approximation, on n'a pas vraiment besoin de se soucier de ce partage. On peut tout à fait l'ignorer. En particulier, on peut continuer à dessiner le résultat précédent comme nous le faisions auparavant,

__3__

/ \\

_1_ _4_

/ \\ / \\

c'est-à-dire sans expliciter que le sous-arbre gauche est commun avec un autre arbre.

Seules des considérations d'occupation mémoire pourraient éventuellement faire une différence, si tous ces arbres cohabitaient en mémoire. Mais le plus souvent, ce n'est pas le cas. Ainsi, lorsqu'on exécute une séquence d'instructions telle que

a = ajoute(3, None)

a = ajoute(1, a)

a = ajoute(4, a)

seul le dernier arbre construit est stocké dans la variable a. Tous les sous-

arbres qui ne participent pas au résultat final sont récupérés par le GC de Python. Une fois que c'est fait, il n'y a plus de partage.

","title":"Ajout dans un ABR","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Doublons

Telle que nous l'avons écrite, notre fonction ajoute a la propriété de toujours ajouter un nouveau nœud à l'arbre.

En particulier, si l'élément x apparaît déjà dans l'arbre, un nouveau nœud contenant une nouvelle occurrence de x va être ajouté.

Plus précisément, lorsque x est égal à la racine a.valeur, on poursuit notre insertion dans le sous-arbre droit. Ainsi, si on insère 3 dans l'arbre donné en exemple plus haut qui contient déjà 1,2,3,4, alors on va obtenir l'arbre suivant :

____3____

/ \\

_1_ _4_

/ \\ / \\

_2_ _3_

/ \\ / \\

En effet, on commence par comparer l'élément à ajouter, 3, avec la racine, qui vaut 3 également. Dès lors, on se déplace vers le sous-arbre droit.

On pourrait tout à fait préférer insérer à gauche plutôt qu'à droite en cas d'égalité. Pour cela, il suffirait de remplacer la comparaison stricte < par une comparaison large <= dans le code de la fonction ajoute.

Nos ABR réalisent donc des multi-ensembles, c'est-à-dire des ensembles où un même élément peut paraître plusieurs fois. Si on veut en revanche réaliser des ensembles, où chaque élément apparaît exactement une fois, il ne faut pas ajouter de nouvelle occurrence de l'élément x lorsqu'il se trouve déjà

dans l'arbre.

Pour cela, il y a deux solutions. La première consiste à d'abord tester si x apparaît dans a, avec notre fonction appartient, et n'appeler la fonction ajouter qu'en cas de réponse négative.

La deuxième consiste à écrire une variante de la fonction ajoute qui n'ajoute pas de nouvelle occurrence de l'élément x s'il est déjà dans l'arbre a, mais renvoie un arbre identique à a.

","title":""},{"edit":"

"}],[{"text":"

Alternatives

Comme nous l'avons évoqué plus haut, il n'est pas impossible de réaliser une modification en place d'un arbre pour lui ajouter un nouvel élément.

Voici à quoi pourrait ressembler une fonction ajoute qui modifie l'arbre a reçu en argument et ne renvoie rien.

def ajoute(x,a):

if x < a.valeur:

if a.gauche is None:

a.gauche = Noeud(None, x, None)

else:

ajoute(x,a.gauche)

elif x > a.valeur:

if a.droit is None:

a.droit = Noeud(None, x, None)

else:

ajoute(x,a.droit)

On a illustré ici le cas d'une insertion dans le sous-arbre gauche.

On teste si ce sous-arbre est vide. Le cas échéant, on greffe le nouveau nœud.

Sinon, on procède récursivement.

On fait de même pour une insertion dans le sous-arbre droit.

Comme on le voit, le code est devenu plus

complexe. Mais surtout, il ne traite pas le cas de l'insertion dans un arbre vide, c'est-à-dire lorsque a vaut None.

On serait obligé de le traiter dans le code englobant, c'est-à-dire dans le code qui appelle ajoute initialement.

Tester la fonction ajoute avec les instructions suivantes :

a6 = Noeud(None,8,None)

ajoute(4,a6)

ajoute(12,a6)

ajoute(2,a6)

ajoute(6,a6)

ajoute(10,a6)

ajoute(14,a6)

ajoute(1,a6)

ajoute(3,a6)

ajoute(5,a6)

ajoute(7,a6)

ajoute(9,a6)

ajoute(11,a6)

ajoute(13,a6)

ajoute(15,a6)

affiche1(a6)

Comparer avec le la fonction précédente ajoute et conclure.

Il y a d'autres manières de procéder pour réaliser une insertion en place, mais elles sont toutes complexes, d'une façon ou d'une autre.

Au final, le premier programme ajout est plus simple simple qui soit. Par ailleurs, son efficacité est comparable à celle de toute autre solution, y compris les solutions qui modifient l'arbre.

En effet, le nombre d'opérations est dans tous les cas défini par la descente dans l'arbre jusqu'au point d'insertion, quelle que soit la méthode choisie.

Enfin, dans la dernière section, nous allons encapsuler un ABR dans un objet

pour lui donner notamment une interface impérative, où la méthode d'ajout ne renvoie rien. Ainsi, nous aurons réconcilié la simplicité des arbres immuables avec une utilisation impérative idiomatique en Python.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Pour supprmer un élément dans un ABR, on applique toujours le même principe, en procédant récursivement soit à gauche, soit à droite, selon le résultat de la comparaison.

Le cas de base, cependant, est plus délicat, car il s'agit de supprimer le nœud à la racine de l'arbre.

Pour conserver une structure d'arbre, il faut donner une racine à l'arbre renvoyé.

Pour cela, on peut prendre par exemple le plus petit élément du sous-arbre droit, pour en faire la racine, et le supprimer du sous-arbre droit. On est donc ramené à la suppression du plus petit élément d'un arbre, qui s'avère plus facile que la

suppression d'un élément quelconque.

En premier lieu, on suppose avoir écrit une fonction plus_petit(a) qui renvoie le plus petit élément de l'arbre a, c'est-à-dire l'élément se trouvant tout en bas à gauche de a en supposant l'arbre a non vide.

On écrit ensuite une fonction supprime_minimum(a) qui renvoie un arbre

contenant les mêmes éléments que a, à l'exclusion du plus petit élément de a.

Cela revient donc à supprimer l'élément situé tout en bas à gauche de a.

On suppose que l'arbre a est non vide. Cette fonction procède récursivement, avec un cas de

base et un cas récursif.

Le cas de base est celui d'un arbre dont le sous-arbre gauche est vide. Dans ce cas, le minimum est la racine et il suffit de renvoyer le sons-arbre droit. Sinon, on procède récursivement, en supprimant le minimum dans le sous-arbre gauche.

On peut enfin écrire une fonction supprime(x, a) qui supprime une occurrence de x dans a.

On rappelle en effet qu'on à potentiellement des doublons dans nos arbres et donc potentiellement plusieurs occurrences de x dans a.

Ici, on choisit de n'en supprimer qu'une.

Par ailleurs, on n'impose pas que l'élément x apparaisse dans a. S'il n'apparaît pas, la fonction supprime renvoie un arbre identique à a.

Le code de la fonction supprime est le suivant :

def plus_petit(a):

if a is None:

return None

if a.gauche is None:

return a.valeur

else:

return plus_petit(a.gauche)

def supprime_minimum(a) :

\"\"\"itisupprime Le plus petit élément de a

suppose a non vide\"\"\"

assert a is not None

if a.gauche is None:

# la racine est Le minimum

return a.droit

return Noeud(supprime_minimum(a.gauche) ,a.valeur,a.droit)

def supprime(x, a):

\"\"\"supprime une occurrence de x dans a\"\"\"

if a is None:

return None

if x < a.valeur:

return Noeud(supprime(x,a.gauche) ,a.valeur,a.droit)

elif x > a.valeur:

return Noeud(a.gauche,a.valeur,supprime(x,a.droit))

#il faut supprimer la racine

elif a.droit is None:

return a.gauche

else:

return Noeud(a.gauche, plus_petit(a.droit), \\

supprime_minimum(a.droit))

Tester le avec les instructions suivantes:

a6 = Noeud(None,8,None)

ajoute(4,a6)

ajoute(12,a6)

ajoute(2,a6)

ajoute(6,a6)

ajoute(10,a6)

ajoute(14,a6)

ajoute(1,a6)

ajoute(3,a6)

ajoute(5,a6)

ajoute(7,a6)

ajoute(9,a6)

ajoute(11,a6)

ajoute(13,a6)

ajoute(15,a6)

affiche1(a6)

print()

a7 = supprime(4,a6)

affiche1(a7)

Et conclure sur la fonction supprime.

Le cas d'un arbre vide est traité en premier lieu. Il suffit de renvoyer un arbre vide.

On traite ensuite le cas d'une valeur x située dans le sous-arbre gauche ou dans le sous-arbre droit, avec un appel récursif. Il reste enfin le cas où la valeur x est égale à a.valeur, c'est-à-dire le cas où l'on souhaite supprimer la racine de l'arbre. C'est 1à qu'on emploie les deux fonctions minimum et supprime_minimum, pour faire du plus petit élément de a.droit la nouvelle racine de l'arbre.

Bien entendu, on aurait pu utiliser tout autant le maximum du sous-arbre gauche, d'une façon totalement symétrique.

","title":"Suppression dans un ABR"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comme nous l'avons fait pour les listes chaînées, nous pouvons maintenant encapsuler nos arbres binaires de recherche dans une classe, ici appelée ABR.

Le code de cette classe est le suivant:

Programme — Encapsulation d'un ABR dans un objet

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

def __eq__(self, n):

return n is not None \\

and self.gauche == n.gauche \\

and self.valeur == n.valeur \\

and self.droit == n.droit

class ABR:

\"\"\"arbre binaire de recherche\"\"\"

def __init__(self):

self.racine = None

def ajouter(self, x):

if self.racine is None :

self.racine = Noeud(None,x,None)

else :

self.__ajoute__(x,self.racine)

def contient(self, x):

return self.__appartient__(x, self.racine)

def affiche(self):

self.__afficher__(self.racine)

print(\"\\n\")

def __afficher__(self,a):

if a is None:

return

print (\"(\", end=\"\")

self.__afficher__(a.gauche)

print(a.valeur, end=\"\")

self.__afficher__(a.droit)

print(\")\", end=\"\")

def __ajoute__(self,x,a):

if x < a.valeur:

if a.gauche is None:

a.gauche = Noeud(None, x, None)

else:

self.__ajoute__(x,a.gauche)

elif x > a.valeur:

if a.droit is None:

a.droit = Noeud(None, x, None)

else:

self.__ajoute__(x,a.droit)

def __appartient__(self,x, a):

\"\"\"détermine si x apparaît dans l'ABR\"\"\"

if a is None:

return False

if x < a.valeur:

return self.__appartient__(x, a.gauche)

elif x > a.valeur:

return self.__appartient__(x, a.droit)

else:

return True

Tester avec :

a8 = ABR()

a8.ajouter(8)

a8.ajouter(4)

a8.ajouter(12)

a8.ajouter(2)

a8.ajouter(6)

a8.ajouter(10)

a8.ajouter(14)

a8.ajouter(1)

a8.ajouter(3)

a8.ajouter(5)

a8.ajouter(7)

a8.ajouter(9)

a8.ajouter(11)

a8.ajouter(13)

a8.ajouter(15)

a8.affiche()

print(\"a8 contient 15? \",a8.contient(15))

print(\"a8 contient 17? \",a8.contient(17))

Et conclure.

Chaque objet de la classe ABR contient un unique attribut, racine, qui est l'arbre binaire de recherche qu'il représente. Le constructeur de la classe ABR renvoie un arbre vide, avec donc la valeur None dans l'attribut racine.

Ainsi, si on construit un arbre vide, que l'on stocke dans une variable a, on a la

situation suivante:

$\"arbre9.png$

a = ABR()

La classe ABR fournit deux méthodes, ajouter et contient, correspondant aux deux fonctions ajoute et appartient des deux sections précédentes.

Ainsi, on peut construire un arbre contenant les éléments 1, 2, 3, 4 en les

ajoutant avec la méthode ajouter. I! faut comprendre que chaque appel à la méthode ajouter remplace l'attribut racine par un nouvel arbre, à savoir celui qui est renvoyé par la fonction ajoute.

L'arbre qui était précédemment dans l'attribut racine est perdu et sera récupéré par le GC de Python, à sa discrétion.

En pratique, il faudrait ajouter d'autres méthodes à la classe ABR, correspondant à d'autres fonctions comme taille, hauteur, parcours_infixe, suprimer, etc.

a = ABR()

a.ajouter(3)

a.ajouter(1)

a.ajouter(4)

a.ajouter(2)

$\"arbre9.png$

Figure : Construction d'un ABR contenant quatre éléments.

","title":"Encapsulation dans un objet"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comme on l'a expliqué plus précédemment, le coût de la recherche ou de l'ajout dans un ABR dépend de sa structure. Il est borné par la hauteur de l'ABR.

Dans le pire des cas, l'arbre peut être complètement linéaire et le coût peut

donc être proportionnel au nombre d'éléments, ce qui en fait une structure

de peu d'intérêt. Autant mettre tous les éléments dans un tableau ou une liste chaînée si c'est pour faire une recherche linéaire.

Néanmoins, il est possible de s'assurer, pendant leur construction, que la hauteur des ABR « ne sera pas trop grande ».

Pour cela, on réorganise la structure de l'ABR lorsque c'est nécessaire, tout en maintenant la propriété d'arbre binaire de recherche.

Il existe de multiples façons de procéder. Parmi les plus connues, on peut citer les arbres AVL ou encore les arbres rouges et noirs.

Le détail de ces méthodes dépasse largement le cadre du programme de terminale.

On peut se contenter de dire que l'idée est, pour chaque sous-arbre, de mettre approximativement la moitié des nœuds dans le sous-arbre gauche et l'autre moitié dans le sous-arbre droit.

Ainsi, on divise par deux le nombre de nœuds à considérer à chaque descente dans l'arbre, comme dans le cas de la recherche dichotomique dans un tableau trié. Dit autrement, ces méthodes d'équilibrage des arbres permettent de garantir une hauteur logarithmique, c'est-à-dire l'existence d'une constante C telle que

h ≤ C.log2(N)

où h désigne la hauteur et N la taille d'un ABR.

Par exemple, pour les arbres AVL, on a C=1,44. On parle d'arbres équilibrés lorsqu'on à une telle inégalité. Les opérations de recherche ou d'ajout sur les arbres équilibrés ont une complexité logarithmique, ce qui en fait des opérations très efficaces en pratique.

Par ailleurs, il n'y a plus aucun risque de provoquer l'erreur RecursionError lorsque les arbres sont équilibrés.

","title":"Arbre équilibré "},{"edit":"

"}],[{"text":"

Un arbre binaire de recherche est un arbre binaire contenant des valeurs ordonnées, avec la propriété que tout nœud contient une valeur plus grande (resp. plus petite ou égale) que les valeurs contenues dans son sous-arbre gauche (resp. droit). Cette organisation permet de procéder par dichotomie, en n'ayant à considérer qu'un seul des

deux sous-arbres pendant une opération. Lorsqu'ils sont équilibrés, les arbres binaires de recherche constituent une méthode très efficace pour stocker et rechercher de l'information.

","title":"Conclusion"},{"edit":"

"}],[{"text":"

Pourquoi la bibliothèque donnée en exemple au début de ce

chapitre contient-elle 17576 salles ?

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"Parce qu’il y a 26x26x26 = 26³ = 17576 mots de trois lettres."}],[{"text":"

Donner tous les ABR formés de trois nœuds et contenant les entiers 1, 2 et 3.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

_3_ / \\ _2_ / \\ _1_ / \\	_3_ / \\ _1_ / \\ _2_ / \\	__2__ / \\ _1_ _3_ / \\ / \\
_1_ / \\ _2_ / \\ _3_ / \\	_1_ / \\ _3_ / \\ _2_ / \\

"}],[{"text":"

Dans un ABR, où se trouve le plus petit élément ? En déduire

unc fonction minimum(a) qui renvoie le plus petit élément de l'ABR a. Si

l'arbre à est vide, alors cette fonction renvoie None.

Tester avec :

a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\

8, \\

Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))

print(minimum(a5))

Résultat :

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Par définition d’un ARB, le plus petit élément se trouve en bas à gauche de l’arbre.

def minimum(a):

if a is None:

return None

if a.gauche is None:

return a.valeur

else:

return minimum(a.gauche)

"}],[{"text":"

def ajoute(x, a):

#ajoute x à l'arbre a, renvoie un nouvel arbre

if a is None:

return Noeud(None, x, None)

if x < a.valeur:

return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)

else:

return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))

Modifier la fonction ajoute qui n'ajoute pas l'élément x à l'arbre a s'il est déjà dedans.

Tester avec :

a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\

8, \\

Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))

a5 = ajoute(1,a5)

a5 = ajoute(15,a5)

a5 = ajoute(14,a5)

affiche1(a5)

Résultat :

(((1)2)4(5))8((10)12(14(15))))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def ajoute(x, a):

#ajoute x à l'arbre a, renvoie un nouvel arbre

if a is None:

return Noeud(None, x, None)

if x < a.valeur:

return Noeud(ajoute(x, a.gauche), a.valeur, a.droit)

elif x > a.valeur:

return Noeud(a.gauche, a.valeur, ajoute(x, a.droit))

else :

return a # x est dans a

"}],[{"text":"

Écrire une fonction compte(x, a) qui renvoie le nombre d'occurrences de x dans l'ABR. a. On ne suppose pas que l'arbre a à été construit à partir de la fonction ajoute, mais seulement qu'il s'agit d'un ABR.

Cela veut dire qu'une valeur égale à la racine peut se trouver encore dans le sous-arbre gauche autant que dans le sous-arbre droit.

Cela étant, on s'attachera à ne pas descendre dans les sous-arbres dans lesquels on est certain que la

valeur x ne peut apparaître.

Tester avec :

a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\

8, \\

Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))

print(compte(4,a5))

print(compte(14,a5))

print(compte(1,a5))

Résultat :

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Lorsque x est strictement plus petit ou strictement plus grand que a.valeur, il suffit d’aller d’un seul côté. En cas d'égalité, en

revanche, il faut continuer à compter des deux côtés.

def compte(x, a):

if a is None:

return 0

if x < a.valeur:

return compte(x, a.gauche)

elif x > a.valeur:

return compte(x, a.droit)

else:

return 1 + compte(x, a.gauche) + compte(x, a.droit)

"}],[{"text":"

Écrire une fonction remplir(a, t) qui ajoute tous les éléments de l'arbre a dans le tableau t, dans l'ordre infixe. Chaque élément x est ajouté au tableau t avec t.append(x).

Ajouter ensuite une méthode lister(self)

à la classe ABR qui renvoie un nouveau tableau contenant tous les éléments de l'ABR self par ordre croissant.

Tester avec :

a5 = Noeud(Noeud(Noeud(None,2,None),4,Noeud(None,5,None)), \\

8, \\

Noeud(Noeud(None,10,None),12,Noeud(None,14,None) ))

t1 = []

remplir(a5,t1)

print(t1)

Pour la classe ABR :

a6 = ABR()

a6.ajouter(8)

a6.ajouter(4)

a6.ajouter(2)

a6.ajouter(5)

a6.ajouter(12)

a6.ajouter(14)

a6.ajouter(10)

t2 = a6.lister()

print(t2)

Résultat :

[2, 4, 5, 8, 10, 12, 14]

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

C'est un cas particulier de parcours infixe (pro-

gramme 30 page 154) :

def remplir(a, t):

if a is None:

return

remplir(a.gauche, t)

t.append(a.valeur)

remplir(a.droit, t)

Pour la méthode lister dans la classe ABR, on crée un nouveau tableau, que l’on remplit avec la fonction remplir.

def lister(self):

t = []

remplir(self.racine, t)

return t

"}],[{"text":"

En utilisant l'exercice précédent, écrire une fonction trier(t) qui reçoit en argument un tableau d'entiers et renvoie un tableau trié contenant les mêmes éléments.

Quelle est l'efficacité de ce tri?

Tester avec :

t2 = [5,2,4,0,9,10,3,12,7]

t3 = trier(t2)

print(t3)

Résultat :

[0, 2, 3, 4, 5, 7, 9, 10, 12]

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

L'idée est d'ajouter tous les éléments du tableau t dans un ABR, puis d'utiliser la méthode lister de l'exercice précédent.

def trier(t):

a = ABR()

for x in t :

a.ajouter(x)

return a.lister()

L'efficacité de ce tri dépend fortement de la répartition des éléments dans le tableau initial. Si par exemple les éléments sont déjà triés dans le tableau

initial, alors l’arbre sera un peigne et le coût de la construction de l'ABR sera donc quadratique.

"}],[{"text":"

Ajouter la méthode hauteur(self) à la classe a qui renvoie la hauteur de l'arbre.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}],[{"text":"Ajouter la méthode supprimer(self,x) à la classe a qui supprime l'élément x de l'arbre.","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":""}]]

Détails: Écrit par : Richard GAUTHIER; Création : 16 Octobre 2020; Mis à jour : 26 Octobre 2020; Clics : 1763

[[{"text":"

$\"preview\"$

La notion de liste chaînée explorée dans les deux chapitres précédents est parfaite pour structurer un ensemble d'éléments destiné à être énuméré séquentiellement.

Comme on l'a vu avec la réalisation de piles et de files, cette structure permet également un accès simple au début de la séquence et éventuellement à certaines autres positions choisies.

Elle n'est en revanche pas adaptée aux accès ponctuels à des positions arbitraires dans la séquence, puisqu'il faut pour cela à chaque nouvel accès parcourir tous les maillons depuis la tête de la liste jusqu'à la position cherchée, ce qui prend en moyenne

un temps proportionnel au nombre d'éléments stockés dans la structure.

","title":"S.D. - Arbres binaires","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Les structures arborescentes forment une autre famille de structures chaînées, dans lesquelles le nombre de sauts à effectuer pour aller depuis le point de départ jusqu'à une position souhaitée est potentiellement bien moindre.

Ces structures sont omniprésentes en informatique et nous en avons déjà observé une :

l'arborescence des fichiers d'un ordinateur.

administrator@vps:/$ tree /home/

/home/

├── administrator

│ ├── 11.0

│ ├── odoo_install.sh

│ ├── www

│ └── documents

├── user1

│ └── documents

├── invite

└── ubuntu

Cette organisation des fichiers permet notamment, partant du répertoire racine et voyageant de répertoire en sous-répertoire, d'accéder en un petit nombre d'étapes à n'importe quel fichier choisi parmi des dizaines de milliers, pour peu qu'on aille dans la bonne direction.

Ce principe d'un point de départ unique à partir duquel une structure chaînée se scinde à chaque étape en plusieurs branches donne l'idée générale de la structure d'arbre en informatique, qui est à la base d'innombrables structures de données.

Cette structure permet en outre une organisation hiérarchique de l'information, qui la rend utile pour représenter des programmes, des formules de logique, le contenu de pages web, etc.

","title":"Structures arborescentes"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Un arbre binaire est un cas particulier de structure arborescente où chaque position ouvre sur exactement deux branches.

$\"preview\"$

Plus précisément, un arbre binaire est un ensemble fini de nœuds correspondant à l'un des deux cas suivants.

- Soit l'arbre est vide, c'est-à-dire qu'il ne contient aucun nœud.

- Soit l'arbre n'est pas vide, et ses nœuds sont structurés de la façon suivante :

- un nœud est appelé la racine de l'arbre:

- les nœuds restant sont séparés en deux sous-ensembles, qui forment récursivement deux sous-arbres appelés respectivement sous-arbre gauche et sous-arbre droit ;

- la racine est reliée à ses deux sous-arbres gauche et droit, et plus précisément à la racine de chacun de ses sous-arbres (lorsqu'ils ne sont pas vides).

On peut rapprocher la notion de nœud d'un arbre binaire de la notion de cellule d'une liste chaînée.

L'arbre vide est alors similaire à la liste vide qui est noté par le symbole L.

La racine d'un arbre non vide est l'équivalent de la tête d'une liste non vide et les liens vers les deux sous-arbres correspondent à deux chaînages « suivants » menant à deux suites disjointes.

De même que la taille d'une liste était définie comme son nombre de cellules, la faille d'un arbre binaire est ainsi définie comme son nombre de nœuds.

Voici un exemple d'arbre binaire contenant quatre nœuds.

$\"preview\"$

La racine de arbre cst représentée en haut — en informatique, les arbres poussent vers le bas.

Ici, le sous-arbre gauche contient deux nœuds et le sous-arbre droit un nœud.

Comme on le voit, chaque nœud est relié à ses deux sous-arbres, et plus précisément à la racine de chaque sous-arbre, le cas échéant.

On a également représenté les liaisons entre les nœuds et leurs sous-arbres vides, le cas échéant. Ainsi, on explicite le fait qu'un nœud possède toujours deux

sous-arbres, même si l'un ou l'autre ou les deux peuvent être vides.

Lorsqu'un nœud à deux sous-arbres vides, c'est-à-dire qu'il est de la forme

$\"preview\"$

on parle de feuille, Il est important de ne pas confondre une feuille, qui contient un nœud, et un arbre vide, qui n'en contient pas.

","title":"Définition et propriétés des arbres binaires"},{"edit":"

"}],[{"text":"

On définit la hauteur d'un arbre comme le plus grand nombre de nœuds rencontrés en descendant de la racine jusqu'à une feuille (ou, de façon équivalente, jusqu'à un arbre vide).

Tous les nœuds le long de cette descente sont comptés, y compris la racine et la feuille.

Ainsi, l'arbre

$\"preview\"$

a une hauteur 3.

De façon équivalente, on peut définir la hauteur récursivement sur la structure de l'arbre de la manière suivante :

- l'arbre vide a pour hauteur 0:

- un arbre non vide a pour hauteur le maximum des hauteurs de ses deux sous-arbres, auquel on ajoute 1.

Si N désigne la taille d'un arbre binaire, c'est-à-dire son nombre de nœuds, et si k désigne sa hauteur, alors ces deux quantités sont contraintes par les inégalités suivantes:

h ≤ N ≤ 2h - 1

L'inégalité de gauche s'interprète facilement comme le fait qu'un arbre de hauteur } possède au moins À nœuds, par définition de la hauteur. L'égalité

est possible lorsque l'arbre est complètement linéaire, avec un seul nœud à chaque profondeur.

Voici trois exemples d'arbres de taille de hauteur 4 :

$\"preview\"$

Les arbres comme celui de gauche on celui de droite, où le sous-arbre non

vide est systématiquement du même côté, sont appelés des peignes, car leur

forme évoque celle d'un peigne. On note qu'un peigne n'est pas différent, par sa structure, d'une liste chaînée.

De l'autre côté, la limite 2% — 1 sur la taille de l'arbre est atteinte pour

un arbre binaire parfait où toutes les feuilles sont exactement à la même

$\"preview\"$

est un arbre binaire parfait de hauteur 3 et sa taille est 2? —1=7.

La hauteur est une notion importante. Elle joue notamment un grand

rôle lorsque la complexité des algorithmes dépend directement de la hauteur

des arbres. Le chapitre suivant en donne plusieurs exemples.

","title":"Hauteur","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comme nous le verrons dans la séquence suivant, l'intérêt des arbres est d'y

stocker de l'information.

Pour cela, on va attacher une ou plusieurs valeurs à chaque nœud. Voici par exemple un arbre où chacun des quatre nœuds

contient une chaîne de caractères :

$\"preview\"$

Les arbres vides, en revanche, ne contiennent pas d'information.

","title":"De l'information dans les arbres","tagtitle":"h1"},{"edit":""}],[{"text":"

Dans la pratique, il existe de nombreuses

variantes des arbres binaires que nous venons de présenter.

Ainsi, il arrive que les feuilles contiennent une information d'une nature différente, ou encore que seules les feuilles contiennent une information.

Nous nous en tiendrons à la version la plus simple, qui est celle que nous avons présentée.

","title":"De nombreuses variantes","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Il y a de nombreuses façons de représenter un arbre binaire en Python.

Une manière traditionnelle consiste à représenter chaque nœud par un objet d'une classe, qu'on appellera ici Noeud.

Programme — Nœud d'un arbre binaire

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

Comme on le voit, un objet de cette classe contient trois attributs :

- un attribut gauche pour le sous-arbre gauche;

- un attribut valeur pour la valeur contenue dans le nœud;

- et un attribut droit pour le sous-arbre droit.

Par ailleurs, l'arbre vide est représenté par la valeur None.

Pour construire un arbre, il suffit d'appliquer le constructeur de la classe

Noeud autant de fois qu'il y a de nœuds dans l'arbre. Ainsi, arbre

$\"preview\"$

est construit et stocké dans la variable a avec cette instruction :

a = Noeud(Noeud(None, \"B\", Noeud(None, \"C\", None)),

\"A\",

Noeud(None, \"D\", None))

On a ici créé quatre objets de la classe Noeud, qui sont illustrés dans la figure ci-dessous.

La valeur contenue dans la variable a est l'adresse mémoire de l'objet contenant la valeur \"A\", qui constitue la racine de l'arbre.

Ce nœud contient lui-même dans son attribut gauche l'adresse mémoire de l'objet contenant la valeur \"B\" et dans son attribut droit l'adresse mémoire de

l'objet contenant la valeur \"D\", et ainsi de suite.

Certains des attributs gauche ou droit ont une valeur None, lorsque le sous-arbre correspondant est vide.

Dans la séquence suivant, nous expliquerons comment un arbre peut être

encapsulé dans un objet, exactement comme nous l'avons fait pour les listes

$\"preview\"$

","title":"Représentation en Python","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Représentations alternatives

Exactement comme pour les listes chaînées, d'autres représentations sont possibles.

Plutôt qu'un objet de la classe Noeud, on pourrait utiliser un triplet, et dans ce

cas écrire

a = ((None,\"B\", (None, \"C\",None)) , \"A\", (None, \"D\" ,None))

,un dictionnaire, ou encore un tableau à trois éléments.

Cependant, l'utitisation d'une valeur structurée avec des champs nommés (ici les attributs gauche, valeur et droit) est idiomatique, y compris dans un langage comme Python.

Orientation des arbres

Comme avec les listes doublement chaînées, il est tout à fait envisageable d'avoir un chaînage bidirectionnel dans les arbres, où chaque nœud qui n'est pas la racine est également relié à son

nœud parent.

Pour cela, il suffit d'ajouter un quatrième attribut à la classe Noeud, appelé parent, qui contient None pour un nœud racine et un objet de la classe Noeud sinon.

Homogénéité

Exactement comme les listes chaînées, les les arbres peuvent contenir des valeurs de n'importe quel type et nous recommandons une utilisation homogène des arbres, où les valeurs contenues dans les nœuds d'un même arbre sont toutes du même type.

","title":""},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La définition d'arbre binaire étant récursive, il est naturel d'écrire des

opérations sur les arbres binaires sous la forme de fonctions récursives.

L'exemple le plus simple est celui d'une fonction taille qui calcule la taille

d'un arbre.

def taille(a):

\"\"\"Le nombre de noeuds de l'arbre a\"\"\"

On commence par considérer le cas de base où l'arbre a est vide.

Dans ce cas, il convient de renvoyer 0, car il n'y à aucun nœud dans l'arbre.

if a is None:

return 0

Dans le cas contraire, l'arbre contient au moins un nœud (la racine de l'arbre), auquel on va ajouter la taille des sous-arbres gauche et droit, calculées récursivement.

else:

return 1 + taille(a.gauche) + taille(a.droit)

Il est important de noter que les expressions a.gauche et a.droite ne provoqueront pas d'erreur, car l'arbre a n'est pas vide.

Le code complet est le suivant:

Programme — Calcul de la taille et de la hauteur

def taille(a):

\"\"\"le nombre de noeuds de L'arbre a\"\"\"

if a is None:

return 0

else:

return 1 + taille(a.gauche) + taille(a.droit)

Ensuite, nous pouvons créer une fonction qui calcule la hauteur d'un arbre.Sa structure est très similaire à la fonction taille :

def hauteur(a):

\"\"\"la hauteur de l'arbre a\"\"\"

if a is None:

return 0

else:

return 1 + max(hauteur(a.gauche), hauteur(a.droit))

Efficacité. Il est clair que les deux fonctions taille et hauteur ont une

complexité directement proportionnelle au nombre de nœuds de l'arbre.

En effet, ces deux fonctions font un nombre d'opérations borné sur chaque nœud

(addition, maximum) et parcourent une fois et une seule chaque nœud.

Tester avec :

print(\"taille de a\",taille(a))

print(\"hauteur de a\",hauteur(a))

et conclure.

","title":"Algorithmique des arbres binaires"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Les deux fonctions que nous venons d'écrire, à savoir taille et hauteur, parcourent tous les nœuds de l'arbre.

L'ordre dans lequel ce parcours est

effectué n'est pas important. Que ce soit pour calculer la taille ou la hauteur, peu importe si on commence le calcul par le sous-arbre gauche ou droit.

Écrivons maintenant une autre fonction, qui affiche les valeurs contenues dans tous les nœuds de l'arbre, par exemple une par ligne.

L'ordre dans lequel le parcours des nœuds est effectué devient important. On peut

par exemple parcourir le sous-arbre gauche, puis afficher la valeur de la racine, puis enfin parcourir le sous-arbre droit.

On appelle cela un parcours infixe.

Le programme suivant contient le code d'une fonction parcours_infixe qui imprime les valeurs des nœuds d'un arbre dans un parcours infixe.

Programme — Parcours infixe d'un arbre binaire

def parcours_infixe(a):

\"\"\"affiche les éléments de a dans un parcours infite\"\"\"

if a is None:

return

parcours_infixe(a.gauche)

print (a.valeur)

parcours_infixe(a.droit)

Tester avec :

parcours_infixe(a)

Efficacité. La fonction parcours_infixe a une complexité directement proportionnelle au nombre de nœuds de l'arbre. Comme les fonctions taille et hauteur, elle fait un nombre d'opérations borné sur chaque nœud (ici, l'affichage de la valeur) et parcourt une fois et une seule chaque nœud.

","title":"Parcours d'un arbre binaire"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

D'autres parcours

Le parcours infixe n'est pas la seule façon de parcourir

les nœuds d'un arbre. On pourrait afficher la valeur avant de parcourir les

sous-arbres (on parle alors de parcours préfixe) ou après (on parle alors de

parcours postfixe).

Si on ajoute la possibilité de parcourir le sous-arbre droit avant le sous-arbre gauche, cela fait encore trois autres solutions, même si elles sont peu utilisées en pratique et ne portent du coup pas de nom.

Attention au partage

Rien ne nous empêche de réutiliser plusieurs fois un même sous-arbre dans une construction d'arbre. Ainsi, on peut

écrire le code Python à gauche et obtenir (en mémoire) l'arbre à droite :

f = Noeud(None, 1, None)

r = Noeud( f , 2, f )

Il s'agit là d'un arbre de taille 3, avec un sous-arbre gauche contenant un nœud et un sous-arbre droit contenant également un nœud.

Le fait que ces deux nœuds sont en réalité un même nœud en mémoire n'est

pas observable en première approximation.

En particulier, un appel à taille(r) renvoie la valeur 3, car la fonction taille parcourt d'abord le sous-arbre gauche, puis le sous-arbre droit.

On peut tout à faire réaliser un tel partage intentionnellement, par exemple pour économiser de la mémoire.

Maïs il faut bien avoir conscience que le partage est difficilement compatible avec des modifications de la structure de l'arbre ou des valeurs contenues dans les

nœuds.

","title":""},{"edit":"

"}],[{"text":"

$\"preview\"$

Un arbre binaire est un ensemble fini de nœuds, qui est soit vide, soit structuré à partir d'un nœud particulier, appelé la racine de l'arbre, et de deux sous-ensembles de nœuds formant récursivement

un sous-arbre gauche et un sous-arbre droit.

Un arbre peut être matérialisé en Python avec un objet par nœud, d'une classe qui à trois attributs : le sous-arbre gauche, le sous-arbre droit et une valeur stockée

dans le nœud,

La valeur None est utilisée pour représenter l'arbre vide.

","title":"Conclusion"},{"edit":"

"}],[{"text":"

Dessiner tous les arbres binaires ayant respectivement 3 et 4 nœuds.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Il y a 5 arbres binaires possédant 3 nœuds :

_1_ _1_ _1_

/ \\ / \\ / \\

_2_ _3_ _2_ _2_

/ \\ / \\ / \\ / \\

_3_ _3_

/ \\ / \\

_1_ _1_

/ \\ / \\ / \\

_2_ _2_

/ \\ / \\

_3_ _3_

/ \\ / \\

Il y a 14 arbres binaires possédant 4 nœuds :

__1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\	__1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\	__1__ / \\ _2_ _3_ / \\ / \\ _4_ / \\
__1__ / \\ _2_ _3_ / \\ /. \\ _4_ / \\	__1__ / \\ __2__ / \\ _3_ _4_ /. \\ / \\	__1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\
__1__ / \\ __2__ / \\ _3_ /. \\ _4_ / \\	__1__ / \\ _2_ / \\ _3_ / \\ _4_ / \\	__1__ / \\ _2_ / \\ _3_ / \\ _4_ / \\
__1__ / \\ __2__ / \\ _3_ _4_ /. \\ / \\	__1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\	__1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\
__1__ / \\ __2__ / \\ _3_ /. \\ _4_ /. \\	__1__ / \\ __2__ / \\ _3_ /. \\ _4_ / \\

"}],[{"text":"

Sachant qu'il y à 1 arbre binaire vide, 1 arbre binaire contenant 1 nœud, 2 arbres binaires contenant 2 nœuds, 5 arbres binaires contenant 3

nœuds et 14 arbres binaires contenant 4 nœuds, calculer le nombre d'arbres binaires contenant 5 nœuds.

On ne cherchera pas à les construire tous, mais seulement à les dénombrer.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour les dénombrer, on considère le nœud à la racine puis on répartit les quatre nœuds restants entre le sous-arbre gauche et le sous-arbre droit.

Par exemple, on peut mettre un nœud dans le sous-arbre gauche et trois dans le sous-arbre droit.

Au total, il y a cinq façons différentes

de répartir les nœuds (0+4, 1+3 , 2+2, 3+1, 4+0).

Pour chacune, on connaît le nombre de sous-arbres possibles, ce qui donne la somme

1x14 + 1x5 + 2x2 + 5x1 + 14x1

soit un total de 42 arbres binaires possédant 5 nœuds.

"}],[{"text":"

Écrire une fonction affiche1(a) qui imprime un arbre sous la forme suivante :

- pour un arbre vide, on n'imprime rien;

- pour un nœud, ou sa valeur, son sous-arbre droit (récursivement), puis enfin une parenthèse fermante.

Ainsi, pour l'arbre :

$\"preview\"$

on doit afficher ((B(C))A(D)).

Tester avec :

a1 = Noeud(Noeud(None,\"B\",Noeud(None,\"C\",None)),\"A\",Noeud(None,\"D\",None))

affiche1(a1)

Résultat :

((B(C))A(D))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def affiche1(a):

if a is None:

return

print (\"(\", end=\"\")

affiche1(a.gauche)

print(a.valeur, end=\"\")

affiche1(a.droit)

print(\")\", end=\"\")

"}],[{"text":"

Dessiner l'arbre binaire sur lequel la fonction affiche1 de l'exercice précédent produit la sortie :

(1((2)3)).

D'une manière générale, expliquer comment retrouver l'arbre dont l'affichage est donné.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour la sortie (1((2)3)), l'arbre est le suivant :

__1__

/ \\

_3_

/ \\

_2_

/ \\

D'une manière générale, on distingue deux cas : si l'affichage est vide, l’arbre

est vide; sinon, il y a une paire de parenthèses qui encadre la chaîne toute

entière. On cherche alors la valeur qui est contenue dans cette paire de parenthèses et qui n’est contenue dans aucune autre.

C’est la valeur que l'on place à la racine.

À gauche (resp. droite) de cette valeur, on trouve la sous-chaîne qui nous permet de reconstruire (récursivement) le sous-arbre gauche (resp. droit).

"}],[{"text":"

Ajouter à la classe Noeud une méthode __eq__ permettant de tester l'égalité entre deux arbres binaires à l'aide de l'opération ==.

Tester avec :

a = Noeud(None,\"C\",None)

b = Noeud(None,\"B\",None)

c = Noeud(a,\"A\",b)

d = Noeud(a,\"A\",b)

e = Noeud(a,\"A\",a)

print(c==d)

print(c==e)

Résultat :

True

False

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Les sous-arbres étant également des nœuds, pour lesquels on est justement en train de définir une méthode __eq_., il suffit de les comparer récursivement avec ==. Il faut en revanche bien vérifier avant cela que n n’est pas l'arbre vide et il ne faut surtout pas le faire avec == car cela provoquerait un appel récursif.

Comme il arrive parfois dans les fonctions récursives, le piège est au niveau du cas de base.

En revanche la vérification pour self est inutile : la méthode n’aurait pas pu être appelée sur un arbre égal à None.

class Noeud:

\"\"\"un noeud d'un arbre binaire\"\"\"

def __init__(self, g, v, d):

self.gauche = g

self.valeur = v

self.droit = d

def __eq__(self, n):

return n is not None \\

and self.gauche == n.gauche \\

and self.valeur == n.valeur \\

and self.droit == n.droit

"}],[{"text":"

Écrire une fonction parfait(h) qui reçoit en argument un entier h supérieur ou égal à zéro et renvoie un arbre binaire parfait de hauteur h.

Tester avec :

a2 = parfait(4)

affiche1(a2)

Résultat :

((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On procède récursivement :

def parfait(h):

\"\"\"construit un arbre binaire parfait de hauteur h\"\"\"

if h == 0:

return None

return Noeud(parfait(h-1), h, parfait(h-1))

On ne factorise pas l’appel récursif parfait(h-1) pour ne pas introduire de partage.

On a choisi ici de stocker la hauteur comme valeur dans chaque nœud.

"}],[{"text":"

Écrire une fonction peigne_gauche(h) qui reçoit en argument un entier h supérieur ou égal à zéro et renvoie un peigne de hauteur h où chaque nœud à un sous-arbre droit qui est vide.

Tester avec :

a3 = peigne_gauche(4)

affiche1(a3)

Résultat :

((((4)3)2)1)

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On peut le faire au choix avec une fonction récursive

(comme dans l’exercice précédent) ou avec une boucle. On choisit ici la

seconde solution :

def peigne_gauche(h) :

\"\"\"construit un peigne gauche de hauteur h\"\"\"

a = None

while h > 0:

a = Noeud(a, h, None)

h -= 1

return a

Il est intéressant de noter que les nœuds de l’arbre sont ici construits de bas

en haut. C’est ce qui nous permet notamment de l'écrire facilement avec une

boucle.

"}],[{"text":"

Écrire une fonction est_peigne_gauche(a) qui renvoie True si et seulement a est un peigne à gauche.

Tester avec :

a3 = peigne_gauche(4)

print(est_peigne_gauche(a3))

a4 = parfait(4)

print(est_peigne_gauche(a4))

Résultat :

True

False

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On l'écrit ici comme une fonction récursive :

def est_peigne_gauche(a):

if a is None:

return True

if not a.droit is None:

return False

return est_peigne_gauche(a.gauche)

Mais on pourrait le faire tout aussi bien avec une boucle (cinq lignes de code

également).

"}],[{"text":"

Donner cinq arbres de taille 3, différents, dont les nœuds contiennent les valeurs 1, 2, 3 et pour lesquels la fonction parcours_infixe affiche à chaque fois

dans cet ordre.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On reprend les cinq arbres de l’exercice sur le dessin des arbres et on les étiquette correctement à chaque fois:

_3_ / \\ _2_ / \\ _1_ / \\	_3_ / \\ _1_ / \\ _2_ / \\	__2__ / \\ _1_ _3_ / \\ / \\
_1_ / \\ _2_ / \\ _3_ / \\	_1_ / \\ _3_ / \\ _2_ / \\

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 16 Octobre 2020; Mis à jour : 22 Octobre 2020; Clics : 2131

[[{"text":"

Les structures de pile et de file permettent toutes deux de stocker des ensembles d'objets et fournissent des opérations permettant d'ajouter ou de retirer des objets un à un.

Les éléments retirés ne sont cependant, ni dans une structure ni dans l'autre, retirés dans un ordre arbitraire, et chacune de ces structures à sa règle.

Dans une pile (en anglais stack), chaque opération de retrait retire l'élément arrivé le plus récemment.

On associe cette structure à l'image d'une pile d'assiettes, dans laquelle chaque nouvelle assiette est ajoutée au-dessus des précédentes, et où l'assiette retirée est systématiquement celle du sommet.

$\"pile_file.png$

Cette discipline est nommée dernier entré, premier sorti (DEPS), ou plus couramment en anglais LIFO (last in, first out).

Dans une structure de file en revanche (en anglais queue), chaque opération de retrait retire l'élément qui avait été ajouté le premier.

On associe cette structure à l'image d'une file d'attente, dans laquelle des personnes arrivent à tour de rôle, patientent, et sont servies dans leur ordre d'arrivée.

$\"pile_file1.png$

Cette discipline est nommée premier entré, premier sorti (PEPS), ou plus couramment en anglais FIFO (first in, first out).

Classiquement, chacune de ces deux structures à une interface proposant au minimum les quatre opérations suivantes :

- créer une structure initialement vide,

- tester si une structure est vide,

- ajouter un élément à une structure,

- retirer et obtenir un élément d'une structure.

De même qu'on la déjà préconisé pour les tableaux et les listes chaînées, on s'attend à ce que les piles ct les files soient des structures homogènes, c'est-à-dire que tous les éléments stockés aient le même type.

Et évidemment, l'opération de retrait suit la discipline correspondant à la structure concernée.

Le plus souvent, les structures de pile et de file sont également considérées mutables : chaque opération

d'ajout ou de retrait d'un élément modifie la pile ou la file à laquelle elle s'applique.

Enfin, sauf mention contraire explicite, il n'y a pas de limite de principe au nombre d'éléments qui peuvent être accueillis dans une pile ou une file :

il est toujours possible d'en ajouter un nouveau.

En plus des opérations minimales déjà citées, les interfaces des piles ou des files ajoutent souvent d'autres opérations facilitant leur manipulation.

Par exemple :

- connaître le nombre d'éléments contenus dans une structure,

- vider une structure,

- consulter un élément d'une structure (celui qu'on aurait obtenu avec l'opération de retrait) sans le retirer,

- etc.

Dans ce chapitre, nous allons voir dans un premier temps les interfaces des structures de pile et de file et des exemples d'utilisation.

Ensuite, nous détaillerons plusieurs manières de réaliser ces structures.

","title":"Piles et files","posi":19},{"edit":"

"}],[{"text":"

Pour exprimer l'interface des piles, nous notons Pile[T] le type des piles contenant des éléments de type T.

L'opération est_vide, qui prend en paramètre une pile et renvoie un booléen indiquant la vacuité de la pile, a

donc le type suivant.

est_vide(Pile[T]) -> bool

À l'inverse, l'opération creer_pile de création d'une pile vide ne prend aucun paramètre et renvoie une nouvelle pile.

creer_pile() -> Pile[T]

On remarque que le type T des éléments de la pile ainsi créée ne peut pas être déduit des paramètres inexistants. Il faut simplement comprendre de cette définition que l'opération de création peut fournir une pile accueillant des éléments de n'importe quel type T.

Notez que cela ne signifie pas que chaque élément puisse avoir n'importe quel type.

En effet, ce type T, bien qu'arbitraire, reste valable pour toute la pile.

L'opération d'ajout d'un élément au sommet d'une pile est traditionnellement appelée empiler (ou push en anglais).

Elle prend en paramètres une pile et l'élément à ajouter, d'un type homogène avec celui des éléments de la pile.

Cette opération ne produit pas de résultat.

empiler(PilefTi, T) -> None

Inversement, l'opération de retrait de l'élément au sommet d'une pile est appelée depiler (ou pop en anglais). Elle prend en paramètre la pile et renvoie l'élément qui en a été retiré.

depiler(Pile[T}) -> T

Cette dernière opération suppose que la pile est non vide et lèvera une exception dans le cas contraire.

fonction	description
Pile[T] "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">creer_pile() -> Pile[T]	crée une pile vide
bool "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">est_vide(p: Pile[T]) -> bool	renvoie True si p est vide et False sinon
None"}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">empiler(p: Pile[T], e: T) -> None	ajoute e au sommet de p
T "}\" style=\"border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; padding: 2px 3px; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">depiler(p: Pile[T]) ->T	retire et renvoie l'élément au sommet de p

Notez que dans la suite nous montrerons des utilisations de cette interface où les opérations sont réalisées par des fonctions ordinaires, mais aussi des

utilisations supposant que la structure de pile est réalisée par une classe dont les opérations est_vide, empiler et depiler sont des méthodes.

L'ajout de l'élément e au sommet de la pile p s'écrira donc empiler(p, e) dans le premier cas et p.empiler(e) dans le second.

","title":"Interface et utilisation d'une pile"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

$\"pile_file.png$

Considérons un navigateur web dans lequel on s'intéresse à deux opérations : aller à une nouvelle page et revenir à la page précédente.

On veut que le bouton de retour en arrière permette de remonter une à une les pages précédentes, et ce jusqu'au début de la navigation.

En plus de l'adresse courante, qui peut être stockée dans une variable à part, il nous faut donc conserver l'ensemble des pages précédentes auxquelles il est possible de revenir.

Puisque le retour en arrière se fait vers la dernière

page qui a été quittée, la discipline « dernier entré, premier sorti » des piles est exactement ce dont nous avons besoin pour cet ensemble.

adresse_courante = “\"

adresses_precedentes = creer_pile()

Ainsi, lorsque l'on navigue vers une nouvelle page, l'adresse de la page courante peut être ajoutée au sommet de la pile des pages précédentes avec l'opération empiler.

l'adresse cible donnée en paramètre peut alors être

enregistrée comme nouvelle adresse courante.

def aller_a(adresse_ cible):

empiler(adresses_precedentes , adresse_courante)

adresse_courante = adresse_cible

Lorsque l'on veut revenir en arrière, il suffit alors de revenir à la dernière page enregistrée sur la pile.

Ici, en outre, on vérifie au préalable qu'il existe bien une page précédente et on ne fait rien si ce n'est pas le cas.

def retour():

if not est_vide(adresses_precedentes):

adresse_courante = depiler(adresses_precedentes)

Le programme ci-dessous redonne l'ensemble de cet exemple, en utilisant cette fois la notation des classes et des appels de méthodes.

Attention, il faut importer le module modPile.py et le mettre où se trouve votre programme.

Programme — Navigation

from modPile import Pile

class Navigation:

\"\"\"Gere la navigation du navigateur\"\"\"

def __init__(self):

self.adresse_courante = \"\"

self.adresses_precedentes = Pile()

def aller_a(self,adresse_cible):

self.adresses_precedentes.empiler(self.adresse_courante)

self.adresse_courante = adresse_cible

def retour(self):

if not self.adresses_precedentes.est_vide():

self.adresse_courante = self.adresses_precedentes.depiler()

def naviguer(self):

while True :

adresse = input(\"Adresse ou < :\")

if adresse == \"<\" :

self.retour()

else :

self.aller_a(adresse)

print(\"Page :\",self.adresse_courante)

Tester avec :

#Lancer la navigation

nav = Navigation()

#lancer la navigation

nav.naviguer()

","title":"Utilisation d'une pile : bouton de retour en arrière","tagtitle":"h1"},{"edit":"

"}],[{"text":"

On a parlé dans certaines séquences d'une « pile d'appels » existant à tout moment de l'exécution d'un programme et contenant, à chaque instant, les informations relatives à tous les appels de fonctions emboîtés en cours d'exécution.

Ce nom correspond bien à la structure d'une pile au sens que nous décrivons dans cette séquence.

En effet, lorsqu'une exécution d'une fonction f déclenche elle-même un appel à une autre fonction g (ou récursivement à la même fonction), la progression dans le code de f est suspendue jusqu'à obtention du

résultat de l'appel à g.

L'appel à f ne peut donc se conclure et disparaître

de la pile d'appels qu'après que l'appel à g est lui-même terminé. Dit autrement, le premier appel à quitter la pile d'appels est le dernier qui y est entré.

Ceci tient à la propriété des appels de fonctions d'être bien emboîtés.

","title":"Pile d'appels"},{"edit":"

"}],[{"text":"

Pour exprimer l'interface des files, nous notons File[T] le type des files contenant des éléments de type T.

Ceci étant fixé, l'interface des files, donnée par l'interface 2, est similaire à celle des piles.

L'opération d'ajout sera simplement appelée ajouter (elle est parfois appelée enfiler, ou en anglais enqueue) et l'opération de retrait retirer (parfois défiler, ou en anglais dequeue).

Interface 3 — File d'étéments de type T

fonction	description
Pile[T] "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">creer_file() -> File[T]	crée une file vide
bool "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">est_vide(f: File[T]) -> bool	renvoie True si f est vide et False sinon
None"}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">ajouter(f: File[T], e: T) -> None	ajoute e à l'arrière de f
T "}\" style=\"padding: 2px 3px; border-width: 1px; border-style: solid; border-color: rgb(204, 204, 204) rgb(0, 0, 0) rgb(0, 0, 0); border-image: initial; overflow: hidden; vertical-align: bottom; font-family: Roboto; font-size: 12pt; text-align: center;\">retirer(f: File[T]) ->T	retire et renvoie l'élément à l'avant de f

","title":"Interface et utilisation d'une file"},{"edit":"

"}],[{"text":"

$\"pile_file1.png$

Considérons le jeu de cartes de la bataille. Chaque joueur possède un paquet de cartes et pose à chaque manche la carte prise sur le dessus du paquet.

Le vainqueur de la manche récupère alors les cartes posées, pour les placer au-dessous de son paquet.

En plus des cartes posées au centre de la table, dont on discutera le traitement plus bas, nous avons besoin de conserver en mémoire le paquet de cartes de chaque joueur. Puisque les cartes sont remises dans un paquet à une extrémité et prélevées à l'autre, la discipline « premier entré, premier sorti » des files est exactement ce dont nous avons besoin pour chacun de

ces ensembles.

En supposant que les joueurs s'appellent Alice et Basile, nous pouvons donc créer ainsi deux paquets de cartes.

paquet_alice = File()

paquet_basile = File()

Une opération de distribution des cartes peut ensuite placer dans ces deux paquets les cartes de départ de chacun des joueurs.

#crée le jeu de 52 cartes

cartes = [i for i in range(0,52)]

#melange les cartes

random.shuffle(cartes)

#distribue les cartes aux 2 joueurs

for i in range(len(cartes)//2) :

paquet_alice.ajouter(cartes.pop())

paquet_basile.ajouter(cartes.pop())

Regardons maintenant quelques aspects de la réalisation d'un tour de jeu. Au moment de démarrer un tour, un joueur perd s'il n'a plus de cartes dans son paquet.

def tour():

global en_cours

if paquet_alice.est_vide():

print(\"Alice perd\")

en_cours = False

elif paquet_basile.est_vide():

print(\"Basile perd\")

en_cours = False

else :

tirer()

Si Ia partie n'est pas terminée, le jeu demande alors à chaque joueur de tirer sa première carte. Il s'agit de prélever la première carte du paquet de chaque joueur, avec l'opération defiler.

def joue():

a = paquet_alice.retirer()

b = paquet_basile.retirer()

valeura = a%13

valeurb = b%13

Remarque : modulo 13 (%13), car il y 13 cartes par couleur (pique, carreau, trèfle, coeur).

Si l'un des joueurs gagne ce tour, on peut alors remettre ces deux cartes au fond de son paquet, c'est-à-dire à l'arrière de sa file de carte, avec l'opération

enfiler.

print(\"Alice\",valeura,valeurb,\"Basile\")

#le programme ne gere pas l'égalité

if valeura > valeurb :

paquet_alice.ajouter(a)

paquet_alice.ajouter(b)

elif valeura < valeurb :

paquet_basile.ajouter(b)

paquet_basile.ajouter(a)

Sans présumer de la manière dont sont représentées les cartes, on suppose ici disposer d'une fonction valeur permettant une comparaison.

Vous terminerez en exercice ce jeu. Vous aurez à gérer d'une part la valeur des cartes et d'autre part les cas d'égalités.

Le programme partiel du jeu de bataille est le suivant :

from modFile import File

import random

paquet_alice = File()

paquet_basile = File()

#crée le jeu de 52 cartes

cartes = [i for i in range(0,52)]

#melange les cartes

random.shuffle(cartes)

#distribue les cartes aux 2 joueurs

for i in range(len(cartes)//2) :

paquet_alice.ajouter(cartes.pop())

paquet_basile.ajouter(cartes.pop())

#Gestion d'un tour de jeu

def tour():

global en_cours

if paquet_alice.est_vide():

print(\"Alice perd\")

en_cours = False

elif paquet_basile.est_vide():

print(\"Basile perd\")

en_cours = False

else :

tirer()

#Si la partie n'est pas terminée, tirage d'une carte

def tirer():

a = paquet_alice.retirer()

b = paquet_basile.retirer()

valeura = a%13

valeurb = b%13

print(\"Alice\",valeura,valeurb,\"Basile\")

#le programme ne gere pas l'égalité

if valeura > valeurb :

paquet_alice.ajouter(a)

paquet_alice.ajouter(b)

elif valeura < valeurb :

paquet_basile.ajouter(b)

paquet_basile.ajouter(a)

#démarrage du jeu

en_cours = True

nb_tours = 0

while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :

tour()

nb_tours+=1

print(\"Partie en \",nb_tours,\" tours\")

Importer le module modFile.py :

https://sciencesappliquees.com/images/nsi/modFile.py

et tester le jeu de carte de la bataille.

Conclure sur le role de la classe File.

","title":"Utilisation d'une file : jouer à la bataille"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

La structure de liste chaînée donne une manière élémentaire de réaliser une pile.

Empiler un nouvel élément revient à ajouter une nouvelle cellule en tête de liste, tandis que dépiler un élément revient à supprimer la cellule de tête.

Où peut ainsi construire une classe Pile définie par un unique attribut contenu associé à l'ensemble des éléments de la pile, stockés sous la forme d'une liste chaînée.

class Pile:

Le constructeur Pile(), défini par la méthode __init__ (self), construit une pile vide en définissant contenu comme la liste vide.

On rappelle que la liste chaînée vide est simplement représentée par la valeur None.

def __init__(self):

self.contenu = None

Ainsi, tester la vacuité d'une pile revient simplement à tester si son contenu

est la liste vide.

def est_vide(self):

return self.contenu is None

On empile un nouvel élément en ajoutant une nouvelle cellule devant celles que contient déjà notre liste chaînée. On peut réaliser cela en construisant

une nouvelle liste chaînée dont la première cellule contient :

- comme valeur l'élément que l'on souhaite empiler,

- comme cellule suivante la première cellule de la liste d'origine, c'est-à- dire self.contenu.

On écrit donc :

def empiler(self, v):

c = Cellule(v, self.contenu)

Ne reste alors qu'à définir cette nouvelle liste chaînée comme le nouveau contenu de notre pile.

self.contenu = c

Récupérer la valeur au sommet de la pile consiste alors à consulter la valeur de la première cellule, en supposant que cette première cellule existe, autrement dit en supposant que la pile n'est pas vide.

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

v = self.contenu.valeur

On complète l'opération de dépilement en retirant le premier élément, c'est-à-dire en redéfinissant le contenu de notre pile comme la liste d'origine

privée de sa première cellule. Autrement dit, la nouvelle cellule de tête est la cellule suivante de la cellule supprimée.

Après cette mise à jour, on peut renvoyer la valeur qui avait été prélevée dans la cellule de tête d'origine.

self.contenu = self.contenu.suivante

return v

Le programme ci-dessous regroupe tous ces éléments pour donner une mise en œuvre complète de la structure de pile à l'aide d'une liste chaînée.

Programme — Réalisation d'une pile avec une liste chaînée

class Cellule:

\"\"\"une cellule d'une liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

class Pile:

\"\"\"structure de pite\"\"\"

def __init__(self):

self.contenu = None

def est_vide(self):

return self.contenu is None

def empiler(self, v):

self.contenu = Cellule(v, self.contenu)

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

v = self.contenu.valeur

self.contenu = self.contenu.suivante

return v

def creer_pile():

return Pile()

Tester la création d'une pile avec les instructions suivantes :

p = Pile()

#ou p = creer_pile()

print(\"p est vide?\",p.est_vide())

p.empiler(1)

p.empiler(2)

p.empiler(3)

p.empiler(4)

print(\"p est vide ?\",p.est_vide())

print(\"retire le 1er element :\",p.depiler())

Décrire les instructions ci-dessous et dessiner la pile à la fin des instructions.

","title":"Réaliser une pile avec une liste chaînée","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

. Les tableaux de Python réalisent également

directement une structure de pile, avec leurs opérations append et pop.

On pourrait donc donner une définition en apparence très simple à une autre version de la classe Pile.

class PileTab:

\"\"\"structure de pile avec tableau\"\"\"

def __init__(self):

self.contenu = []

def est_vide(self):

return len(self.contenu) == 0

def empiler(self, v):

self.contenu.append(v)

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

return self.contenu.pop()

Dans le cadre d'un programme Python, cette réalisation est raisonnable et efficace, les opérations append et pop s'exécutant en moyenne en temps constant. Cette solution, cependant, ne s'exporte pas directement

à n'importe quel autre langage, puisqu'elle cache la richesse de la structure de tableau redimensionnable utilisée par les tableaux de Python.

Tester PileTab avec les instruction suivante et conclure par rapport au Pile précédent :

p = PileTab()

print(\"p est vide?\",p.est_vide())

p.empiler(1)

p.empiler(2)

p.empiler(3)

p.empiler(4)

print(\"p est vide ?\",p.est_vide())

print(\"affiche 1er element :\",p.depiler())

","title":"Piles et tableaux Python"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La structure de liste chaînée donne également une manière de réaliser une file, à condition de considérer la variante des listes chaînées mutables.

Comme dans la réalisation d'une pile, on peut retirer l'élément de tête en retirant la cellule de tête.

En revanche, l'ajout d'un nouvel élément à l'arrière de la file revient à ajouter une nouvelle cellule en queue de liste.

Une mutation intervient à cet endroit :

alors que la cellule qui était la dernière de la liste chaînée avant l'ajout n'avait pas de suivante définie, elle a comme suivante après l'ajout la nouvelle cellule créée pour le nouvel élément.

Autre différence avec la réalisation d'une pile, nous avons maintenant besoin de savoir accéder à la dernière cellule et plus seulement à la première. Il est possible, mais pas raisonnable, de trouver la dernière cellule en parcourant toute la liste chaînée à partir de la première cellule.

Il est plus intéressant de conserver dans notre structure

de données un attribut permettant d'accéder directement à cette dernière cellule.

On peut ainsi construire une classe File dont le constructeur définit deux attributs, l'un appelé tete et l'autre appelé queue, et désignant respectivement la première cellule et la dernière cellule de la liste chaînée utilisée pour stocker les éléments.

class File:

def __init__(self):

self.tete = None

self.queue = None

La file vide est caractérisée par le fait qu'elle ne contient aucune cellule.

En conséquence, sa tête et sa queue sont indéfinies.

En outre, l'une comme l'autre ne peut valoir None que dans ce cas. Pour tester la vacuité de la file, il suffit donc de consulter l'un des deux attributs.

def est_vide(self):

return self.tete îs None

L'ajout d'un nouvel élément à l'arrière de la file demande de créer une nouvelle cellule. Cette cellule prend la dernière place, et n'a donc pas de cellule

def ajouter(self, x):

c = Cellule(x, None)

Cette cellule est alors définie comme suivant la cellule de queue actuelle. On a cependant besoin de traiter le cas particulier où il n'existe pas de cellule de queue, qui correspond à une file initialement vide.

Dans ce cas la nouvelle cellule devient l'unique cellule de la file, et donc sa cellule de tête.

if self.est_vide():

self.tete = c

else:

self.queue.suivante = c

Dans tous les cas, notre nouvelle cellule devient en outre la nouvelle cellule de queue de la file .

self.queue = c

Pour retirer un élément il s'agit de supprimer la première cellule de la file, exactement comme il avait été fait lors de l'utilisation d'une liste chaînée pour réaliser une pile.

Cependant, si la cellule retirée est la dernière, on doit également redéfinir l'attribut self.queue à None, afin de maintenir notre invariant qu'une file vide à ses deux attributs qui valent None.

Le programme ci-dessous montre l'intégralité du code de la classe File que nous venons de décrire.

Programme — Réalisation d'une file avec une tiste chaînée mutable

class File:

\"\"\"structure de file\"\"\"

def __init__(self):

self.tete = None

self.queue = None

def est_vide(self):

return self.tete is None

def ajouter(self, x):

c = Cellule(x, None)

if self.est_vide():

self.tete = c

else:

self.queue.suivante = c

self.queue = c

def retirer(self):

if self.est_vide():

raise IndexError(\"retirer sur une file vide\")

v = self.tete.valeur

self.tete = self.tete.suivante

if self.tete is None:

self.queue = None

return v

Tester la création d'une file avec les instructions suivantes :

f = File()

print(\"f est vide?\",f.est_vide())

f.ajouter(1)

f.ajouter(2)

f.ajouter(3)

f.ajouter(4)

print(\"f est vide ?\",f.est_vide())

print(\"retire 1er element :\",f.retirer())

Décrire les instructions ci-dessous et dessiner la file à la fin des instructions.

","title":"Réaliser une file avec une liste chaînée mutable"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La réalisation d'une file donnée par le programme précédent impose une représentation unique de la file

vide, où les deux attributs se1f.tete et self .queue valent None.

Cela peut simplifier la réflexion sur la structure, mais impose de prendre des précautions en programmant, notamment en incluant les deux lignes

if self.tete fs None:

self.queue = None

dans la fonction retirer pour s'assurer que lorsque l'on rend la file vide, les deux attributs sont bien annulés.

On peut cependant s'autoriser un peu plus de souplesse, et décider que n'importe quelle file dont l'attribut self.tete vaut None est une file vide, sans tenir compte de la valeur de self.queue.

Cela simplifie l'écriture de toute fonction susceptible de vider la file, et on pourra par exemple simplifier le code de retirer de la manière suivante.

def retirer(self):

if self.est_vide():

raise IndexError(\"retirer sur une file vide\")

v = self.tete.valeur

self.tete = self.tete.suivante

return v

En revanche cela pose aussi de nouvelles contraintes :

le test de vacuité

ne doit être fait qu'en fonction de l'attribut self.tete, et surtout il ne faut jamais travailler avec l'attribut self.queue d'une file dont la tête vaudrait None, car la valeur de la queue n'a aucune signification dans ce cas.

","title":"Représentation plus souple de la file vide"},{"edit":"

"}],[{"text":"

Une réalisation radicalement différente de cette même structure de file consiste à utiliser deux piles, ou directement deux listes chaînées immuables.

On prend pour cela modèle sur un jeu de cartes où l'on disposerait d'une pioche, au sommet de laquelle on prend des cartes (disposées face cachée), et d'une défausse, au sommet de laquelle on en repose (disposées face visible)

Chacun de ces deux paquets de cartes est une pile, et ces deux paquets forment ensemble la réserve de cartes.

On a ensuite la discipline suivante :

- toute carte prise dans la réserve est retirée dans l'une de ces piles (la pioche),

- toute carte remise dans la réserve est ajoutée à l'autre pile (la défausse)

S'ajoute un mécanisme liant les deux paquets : une fois la pioche vide on retourne la défausse pour en faire une nouvelle pioche, laissant à la place une défausse vide.

Cette gestion des cartes correspond à une structure de file : une fois la pioche initiale vidée, les cartes seront piochées précisément dans l'ordre dans lequel elles ont été défaussées.

La première défaussée sera la première piochée (FIFO).

On peut donc définir une nouvelle version de la classe File utilisant ce principe.

Une file réalisée ainsi est caractérisée par deux attributs entree et sortie, le premier contenant une pile dans laquelle on ajoute les nouveaux éléments et le second une pile d'où l'on prend les éléments retirés.

class File:

def __init__ (self):

self.entree = creer _pile()

self.sortie = creer _pile()

Une file est vide lorsque ces deux piles sont toutes deux vides.

def est_vide(self):

return self.entree.est_vide() \\

and self.sortie.est_vide()

Ajouter un nouvel élément consiste simplement à empiler cet élément sur la pile d'entrée.

def ajouter(self, x):

self .entree .empiler(x)

Retirer un élément est l'opération la plus délicate. Dans le cas simple où la pile de sortie n'est pas vide, il suffit de dépiler son premier élément.

Dans le cas où la pile de sortie est vide, en revanche, il faut au préalable retourner la pile d'entrée pour la mettre à la place de la pile de sortie.

On peut réaliser cette opération intermédiaire en transférant un à un tous les éléments de la pile d'entrée sur la pile de sortie.

En effet, le premier élément prélevé sur la pile d'entrée est le dernier entrant (discipline FIFO de la pile utilisée), c'est-à-dire celui qui devra sortir de la file après tous les autres (discipline FIFO de la file que l'on veut réaliser}, et il sortira bien le dernier puisqu'il sera

ajouté le premier sur la pile de sortie (discipline FIFO de la pile utilisée).

def retirer(self):

if self .sortie.est_vide():

while not self.entree.est_vide():

self.sortie.empiler(self.entree.depiler())

On peut alors maintenant dépiler le premier élément de la nouvelle pile de sortie, qui, s'il y a eu retournement, était auparavant le dernier élément de la pile d'entrée, à moins que cette pile soit encore vide (ce qui signifierait

que les deux piles étaient vide, et donc la file également).

if self.sortie.est_vide():

raise IndexError(\"retirer sur une file vide\")

return self.sortie.depiler()

Le programme ci-dessous contient l'intégralité de cette nouvelle réalisation des fles.

Programme — Réalisation d'une file avec deux piles

class File2Piles:

\"\"\"structure de fite\"\"\"

def __init__(self):

self.entree = creer_pile()

self.sortie = creer_pile()

def est_vide(self):

return self.entree.est_vide() \\

and self.sortie.est_vide()

def ajouter(self, x):

self.entree.empiler(x)

def retirer(self):

if self.sortie.est_vide():

while not self.entree.est_vide():

self.sortie.empiler(self.entree.depiler())

if self.sortie.est_vide():

raise IndexError(\"retirer sur une file vide\")

return self.sortie.depiler()

Tester la création d'une file avec les instructions suivantes :

f = File2Piles()

print(\"f est vide?\",f.est_vide())

f.ajouter(1)

f.ajouter(2)

f.ajouter(3)

f.ajouter(4)

print(\"f est vide ?\",f.est_vide())

print(\"retire 1er element :\",f.retirer())

Décrire les instructions ci-dessous et dessiner la file à la fin des instructions.

","title":"Réaliser une file avec deux piles"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

La pile est une structure de données de type « dernier entré, premier sorti ». Elle peut être réalisée avec une

liste chaînée ou avec un tableau Python.

La file est une structure de données de type « premier entré, premier sorti ». Elle peut être réalisée avec une liste chaînée mutable ou encore avec deux piles.

","title":"Conclusion","tagtitle":"h1"},{"edit":"

"}],[{"text":"

Compléter la classe Pile avec les trois méthodes suivantes :

- consulter : retourne la valeur de l'élement en haut de la pile;

- taille : donne le nombre d'éléments dans la pile.

- vider : vide la pilz.

class Cellule:

\"\"\"une cellule d'une liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

class Pile:

\"\"\"structure de pite\"\"\"

def __init__(self):

self.contenu = None

def est_vide(self):

return self.contenu is None

def empiler(self, v):

self.contenu = Cellule(v, self.contenu)

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

v = self.contenu.valeur

self.contenu = self.contenu.suivante

return v

Quel est l'ordre de grandeur du nombre d'opérations effectuées par la fonction taille ?

Tester avec :

p = Pile()

p.empiler(1)

p.empiler(2)

print(p.consulter())

p.empiler(3)

p.empiler(4)

p.empiler(5)

p.empiler(6)

print(p.taille())

p.vider()

print(p.consulter())

print(p.taille())

Résultat :

La pile est vide

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La consultation de l’élément au sommet est similaire

à l'opération depiler, mais ne modifie pas le contenu.

def consulter(self):

if self.est_vide():

return \"La pile est vide\"

#raise IndexError(\"consulter sur une pile vide\")

return self.contenu.valeur

On peut vider la pile en redéfinissant le contenu comme la liste vide.

def vider(self):

self.contenu = None

Le calcul de la taille peut se faire à l’aide d’une fonction calculant la longueur d’une liste.

Le coût de cette opération est proportionnel à la longueur de la liste, c’est-à-dire ici au nombre d'éléments que contient la pile.

def taille(self):

return self.longueur(self.contenu)

def longueur(self,liste) :

if liste is None :

return 0

elif liste.suivante is None :

return 1

else :

return 1 + self.longueur(liste.suivante)

"}],[{"text":"

On souhaite compléter le programme navigation pour avoir également une fonction retour_avant dont le comportement est le suivant :

- chaque appel à la fonction retour place la page quittée au sommet d'une deuxième pile adresses_suivantes,

- un appel à la fonction retour_avant amène à la page enregistrée au sommet de la pile adresses_suivantes, et met à jour les deux piles de manière adaptée,

- toute nouvelle navigation avec aller_a annule les adresses suivantes.

Programme — Navigation

class Navigation:

\"\"\"Gere la navigation du navigateur\"\"\"

def __init__(self):

self.adresse_courante = \"\"

self.adresses_precedentes = Pile()

def aller_a(self,adresse_cible):

self.adresses_precedentes.empiler(self.adresse_courante)

self.adresse_courante = adresse_cible

def retour(self):

if not self.adresses_precedentes.est_vide():

self.adresse_courante = self.adresses_precedentes.depiler()

def naviguer(self):

while True :

adresse = input(\"Adresse ou < :\")

if adresse == \"<\" :

self.retour()

else :

self.aller_a(adresse)

print(\"Page :\",self.adresse_courante)

#Lancer la navigation

nav = Navigation()

#lancer la navigation

nav.naviguer()

Modifier et compléter le programme pour définir cette nouvelle fonction.

Remarque : On utilisera la touche \">\" pour naviquer vers l'avant.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

L'initialisation demande de créer une nouvelle pile, vide à l’origine.

def __init__(self):

self.adresse_courante = \"\"

self.adresses_precedentes = Pile()

self.adresses_suivantes = Pile()

La fonction de navigation principale annule les adresses suivantes en vidant la pile correspondante.

def aller_a(self,adresse_cible):

self.adresses_suivantes.vider()

self.adresses_precedentes.empiler(self.adresse_courante)

self.adresse_courante = adresse_cible

Chaque retour en arrière ajoute l’adresse courante à la pile des adresses suivantes, avant de revenir effectivement à la dernière adresse précédente connue.

def retour(self):

if not self.adresses_precedentes.est_vide():

self.adresses_suivantes.empiler(self.adresse_courante)

self.adresse_courante = self.adresses_precedentes.depiler()

Symétriquement, retour_avant va à la première adresse suivante, après avoir remis la page courante sur la pile des adresses précédentes.

def retour_avant(self):

if not self.adresses_suivantes.est_vide():

self.adresses_precedentes.empiler(self.adresse_courante)

self.adresse_courante = self.adresses_suivantes.depiler()

def naviguer(self):

while True :

adresse = input(\"Adresse , < ou > :\")

if adresse == \"<\" :

self.retour()

elif adresse == \">\" :

self.retour_avant()

else :

self.aller_a(adresse)

print(\"Page :\",self.adresse_courante)

"}],[{"text":"

Pour éviter le problème du calcul de taille à l'exercice sur la pile, on propose de revisiter la classe Pile en lui ajoutant un attribut taille, indiquant à tout moment la taille de la pile.

Quelles méthodes doivent être modifiées, et comment?

Programme - La classe pile

class Pile:

\"\"\"structure de pite\"\"\"

def __init__(self):

self.contenu = None

def est_vide(self):

return self.contenu is None

def empiler(self, v):

self.contenu = Cellule(v, self.contenu)

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

v = self.contenu.valeur

self.contenu = self.contenu.suivante

return v

def consulter(self):

if self.est_vide():

return \"La pile est vide\"

#raise IndexError(\"consulter sur une pile vide\")

return self.contenu.valeur

def vider(self):

self.contenu = None

def taille(self):

return self.longueur(self.contenu)

def longueur(self,liste) :

if liste is None :

return 0

elif liste.suivante is None :

return 1

else :

return 1 + self.longueur(liste.suivante)

Tester avec :

p = Pile()

p.empiler(1)

p.empiler(2)

print(p.consulter())

p.empiler(3)

p.empiler(4)

p.empiler(5)

p.empiler(6)

print(p.taille)

p.vider()

print(p.consulter())

print(p.taille)

Résultat :

La pile est vide

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On modifie le constructeur pour initialiser ce nouvel

attribut _taille à zéro, puis les deux opérations empiler et depiler pour que chacune mette à jour cet attribut en lui ajoutant ou retirant un.

Ainsi la valeur reste en permanence à jour

class Pile:

\"\"\"structure de pite\"\"\"

def __init__(self):

self.contenu = None

self.taille = 0

def est_vide(self):

return self.contenu is None

def empiler(self, v):

self.contenu = Cellule(v, self.contenu)

self.taille += 1

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

v = self.contenu.valeur

self.contenu = self.contenu.suivante

self.taille -= 1

return v

def consulter(self):

if self.est_vide():

return \"La pile est vide\"

#raise IndexError(\"consulter sur une pile vide\")

return self.contenu.valeur

def vider(self):

self.contenu = None

self.taille = 0

On pourrait également modifier la définition de est_vide pour utiliser une comparaison entre taille et 0, mais cela n’apporterait rien de particulier.

"}],[{"text":"

Calculatrice polonaise inverse à pile L'écriture polonaise inverse des expressions arithmétiques place l'opérateur après ses opérandes.

Cette notation ne nécessite aucune parenthèse ni aucune règle de priorité.

Ains l'expression polonaise inverse décrite par la chaîne de caractères

'1 2 3 x + 4 x'

désigne l'expression traditionnellement notée

(1+2 x 3) x 4.

La valeur d'une telle expression peut être calculée facilement en utilisant une pile pour stocker les résultats intermédiaires.

Pour cela, on observe un à un les éléments de l'expression et on effectue les actions suivantes :

- si on voit un nombre, on le place sur la pile:

- si on voit un opérateur binaire, on récupère les deux nombres au sommet de la pile, on leur applique l'opérateur, et on replace le résultat sur la pile.

Si l'expression était bien écrite, il y a bien toujours deux nombres sur la pile lorsque l'on voit un opérateur, et à la fin du processus il reste exactement un nombre sur la pile, qui est le résultat.

Écrire une fonction prenant en paramètre une chaîne de caractères représentant une expression en notation polonaise inverse composée d'additions et de multiplications de nombres entiers et renvoyant la valeur de cette expression.

On supposera que les éléments de lexpression sont séparés par des espaces.

Attention : cette fonction ne doit pas renvoyer de résultat si l'expression est mal écrite.

Tester avec :

exp_polo = '1 2 3 x + 4 x'

res_calcul = eval_polonaise_inverse(exp_polo)

print(res_calcul)

Résultat :

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On itère sur les éléments obtenus en découpant la

chaîne au niveau des espaces. On isole d’abord les cas des opérateurs qui

sont les plus faciles à identifier et on suppose que tout ce qui n’est pas \"+\"

où \"*' est un entier (cette branche échouera si on trouve encore autre chose

dans l’expression). À la fin, on dépile le dernier élément et on vérifie que la

pile est bien vide avant de renvoyer ce résultat. Si à un moment il n’était

pas possible de dépiler, le programme échoue de toute façon.

def eval_polonaise_inverse(s):

pile = Pile()

for e in s.split(\" \"):

if e == \"+\" or e == \"x\":

x = pile.depiler()

y = pile.depiler()

if e == \"+\" :

z=x+y

else :

z = x * y

pile.empiler (z)

else:

pile.empiler(int(e))

res = pile.depiler()

assert pile.est_vide()

return res

exp_polo = '1 2 3 x + 4 x'

res_calcul = eval_polonaise_inverse(exp_polo)

print(res_calcul)

"}],[{"text":"

Parenthèse associée

On dit qu'une chaîne de caractères comprenant, entre autres choses, des parenthèses ( et ) est bien parenthésée lorsque chaque parenthèse ouvrante est associée à une unique fermante, et réciproquement.

Écrire une fonction prenant en paramètres une chaîne bien parenthésée s , et qui renvoie l'indice de la parenthèse ouvrante associée.

Tester avec :

exp = \"(2*(2+4*(3+1)))\"

print(ouvrante_associee(exp))

exp = \"(2*(2+4*(3+1))\"

print(ouvrante_associee(exp))

exp = \"(2*(2+4*(3+1))))\"

print(ouvrante_associee(exp))

Résultat :

Index error

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

La première parenthèse fermée est la dernière qui a été ouverte. On utilise donc une pile pour suivre les associations. En l’occurrence, notre pile va enregistrer les indices des parenthèses ouvrantes qui n’ont pas encore été associées à des parenthèses fermantes.

def ouvrante_associee(s):

pile = Pile()

for c in s:

if c == \"(\":

pile.empiler(\"(\")

elif c == \")\":

pile.depiler()

return pile.taille

"}],[{"text":"

Chaînes bien parenthésées

On considère une chaîne de carac-

tères incluant à la fois des parenthèses rondes ( et ) et des parenthèses

carrées [ et 1. La chaîne est bien parenthésée si chaque ouvrante est asso-

ciée à une unique fermante de même forme, et réciproquement.

Écrire une fonction prenant en paramètre une chaîne de caractères conte-

nant, entre autres, les parenthèses décrites et qui renvoie True si la chaîne

est bien parenthésée et False sinon.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On utilise une pile pour stocker toutes les parenthèses ouvrantes qui n’ont pas encore trouvé de fermante associée. Chaque fermante étant censée être associée à la dernière ouvrante non encore associée, on vérifie à chaque fermentante rencontrée que la parenthèse ouvrante associé est la bonne forme.

On échoue si l’ouvrante associée n’a pas la bonne forme, ou s’il n’y a pas d’ouvrante associée, ou encore si la pile n’est pas vide à la fin du processus (ce qui signifierait qu’au moins une ouvrante n’a pas été fermée).

def bonnes_parentheses(s):

assoc = { \")\": \"(\" , \"]\": \"[\" }

pile = Pile()

for c in s :

if c == \"(\" or c == \"[\":

pile.empiler(c)

elif c == \")\" or c == \"]\":

if pile.est_vide() or pile.depiler() != assoc[c]:

return False

return pile.est_vide()

"}],[{"text":"

Pile bornée

Une pile bornée est une pile dotée à sa création d'une capacité maximale. On propose l'interface suivante :

fonction	description
creer_pile(p).	crée et renvoie une pile bornée de capacité c
est_vide(p)	renvoie True si p est vide et False sinon
est_pleine(p)	renvoie True si la pile est pleine et False sinon
empiler(f, e)	ajoute e au sommet de p si p n'est pas pleine, et lève une exception IndexError sinon
depiler(f)	retire et renvoie l'élément au sommet de p si p n'est pas vide, et lève une exception IndexError sinon

On propose de réaliser une telle pile bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité c.

Les éléments de la pile sont stockés consécutivement à partir de l'indice 0 (qui contient l'élément du fond de la pile).

On se donne également un entier enregistrant le nombre d'éléments dans la pile, qui permet donc également de désigner l'indice de la prochaine case libre.

Ainsi dans le schéma ci-dessous, les éléments sont ajoutés et retirés du côté droit de la pile.

0 nb

| |

....

None

...

None

Réaliser une telle structure à l'aide d'une classe ayant pour attributs le

tableau fixe et le nombre d'éléments dans la pile bornée.

Tester avec :

p = PileBornee(5)

print(p.est_vide())

p.empiler(1)

p.empiler(2)

p.empiler(3)

p.empiler(4)

p.empiler(5)

print(p.est_pleine())

print(p.depiler())

print(p.est_vide())

print(p.est_pleine())

Résultat :

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

À la création d’une pile bornée on définit son contenu comme un tableau de taille donnée par la capacité passée en paramètre, dont toutes cases contiennent None. La pile vide est caractérisée par un nombre d’éléments nb nul et la pile pleine par un nombre d'éléments égal à

la capacité.

class PileBornee:

\"\"\"pile à capacité bornée\"\"\"

def __init__(self, cap):

self.contenu = [None] * cap

self.nb = 0

def est_vide(self):

return self.nb == 0

def est_pleine(self):

return self.nb == len(self.contenu)

Les méthodes empiler et depiler vérifient l’une et l’autre qu’elles sont applicables, et mettent à jour le nombre d’éléments nb. Lorsque dépiler retire un élément, on a choisi de remplacer cet élément dans le tableau par

None.

La pile est aussi bien réalisée avec ou sans ce détail, puisque tous les éventuels éléments aux indices nb et suivants sont inaccessibles en utilisant

linterface de la pile. Cependant un élément présent dans le tableau, même

à un indice normalement inaccessible, ne pourrait plus être désalloué par le gestionnaire de mémoire. On évite donc en les supprimant d'éventuelles fuites de mémoire.

def empiler(self, v):

if self.est_pleine():

raise IndexError(\"empiler sur une pile pleine\")

self.contenu[self.nb] = v

self.nb += 1

def depiler(self):

if self.est_vide():

raise IndexError(\"depiler sur une pile vide\")

self.nb -= 1

v = self.contenu[self.nb]

self.contenu[self.nb] = None

return v

"}],[{"text":"

File bornée

Une file bornée est unc file dotée à sa création d'une capacité maximale.

On propose l'interface suivante.

fonction	description
creer_file(f).	crée et renvoie une file bornée de capacité c
est_vide(f)	renvoie True si f est vide et False sinon
est_pleine(f)	renvoie True si la file est pleine et False sinon
ajouter(f, e)	ajoute e à l'arrière de f si f n'est pas pleine, et lève une exception IndexError sinon
retirer(f)	retire et renvoie l'élément à l'avant de f si f n'est pas vide, et lève une exception IndexError sinon

Comme pour la pile bornée, on propose dc réaliser une telle file bornée à l'aide d'un tableau dont la taille est fixée à la création et correspond à la capacité.

Les éléments de la file sont stockés consécutivement à partir d'un indice premier correspondant à l'avant de la file, et le tableau est considéré comme circulaire :

après la dernière case, les éléments reviennent à la première.

Dans les schémas ci-dessous, un élément retiré l'est au niveau de l'indice premier, et un élément ajouté l'est à l'autre extrémité.

premier premier+nb

| |

None

...

None

....

None

...

None

(premier+nb)%cap premier

| |

....

None

...

None

....

Réaliser une telle structure à l'aide d'une classe ayant pour attributs le tableau fixe, le nombre d'éléments dans la file bornée et l'indice du premier élément.

Tester avec :

f = FileBornee(5)

print(f.est_vide())

f.ajouter(1)

f.ajouter(2)

f.ajouter(3)

f.ajouter(4)

f.ajouter(5)

print(f.est_pleine())

print(f.retirer())

print(f.est_vide())

print(f.est_pleine())

Résultat:

True

False

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

L'initialisation est comme celle des piles bornées, et ajoute un attribut premier a la valeur 0 :

à l’origine, les éléments sont placés au début du tableau.

class FileBornee:

\"\"\"UWfile à capacité bornée\"\"\"

def __init__(self, cap):

self.contenu = [None] * cap

self.premier = 0

self.nb = 0

# invariant O <= premier < len(contenu)

# invariant O <= nb <= len(contenu)

def est_vide(self):

return self.nb == 0

def est_pleine(self):

return self.nb == len(self.contenu)

Les éléments sont ajoutés à la fin de la file. L'opération incrémente nb.

def ajouter(self, v):

if self.est_pleine():

raise IndexError(\"ajouter sur une file pleine\")

i = (self.premier + self.nb) % len(self.contenu)

self.contenu[i] = v

self.nb += 1

def retirer(self):

if self.est_vide():

raise IndexError(\"retirer sur une file vide\")

v = self.contenu[self.premier]

self.contenu[self.premier] = None

self.nb -= 1

self.premier = (self.premier + 1) % len(self.contenu)

return v

On a pris soin d’écrire None à la place de v (pour ne pas conserver inutilement

un pointeur vers v à l’intérieur de la structure, ce qui empêcherait le GC de

Python de la récupérer lorsqu'elle ne sera plus accessible par ailleurs).

"}],[{"text":"

Dans cet exercice, on se propose d'évaluer le temps d'attente de clients à des guichets, en comparant la solution d'une unique file d'attente et la solution d'une file d'attente par guichet.

Pour cela, on modélise le temps par une variable globale, qui est incrémenté à chaque tour de boucle.

Lorsqu'un nouveau client arrive, il est placé dans une file sous la forme d'un entier égal à la valeur de l'horloge, c'est-à-dire égal à son heure d'arrivée.

Lorsqu'un client est servi, c'est-à-dire lorsqu'il sort de sa file d'attente, on obtient son temps d'attente en faisant la soustraction de la valeur courante de l'horloge et de la valeur qui vient d'être retirée de la file.

L'idée est de faire tourner une telle simulation relativement longtemps, tout en totalisant le nombre de clients servis et le temps d'attente cumulé sur tous les clients.

Le rapport de ces deux quantités nous donne le temps d'attente moyen. On peut alors comparer plusieurs stratégies (une ou plusieurs files, choix d'une file au hasard quand il y en à plusieurs, choix de la file où il y a le moins de clients, ete.).

On se donne un nombre N de guichets (par exemple, N=5). Pour simuler la disponibilité d'un guichet, on peut se donner un tableau d'entiers dispo de taille N.

La valeur de dispo[i] indique le nombre de tours d'horloge où le guichet i sera occupé.

En particulier, lorsque cette valeur vaut 0, cela veut dire que le guichet est libre et peut donc servir un nouveau client.

Lorsqu'un client est servi par le guichet à, on choisit un temps de traitement pour ce client, au hasard entre 0 et N, et on l'affecte à dispo[i].

À chaque tour d'horloge, on réalise deux opérations :

- on fait apparaître un nouveau client ;

- pour chaque guichet i,

- s'il est disponible, il sert un nouveau client (pris dans sa propre file ou dans l'unique file, selon le modèle}, le cas échéant ;

- sinon, on décrémente dispo[i].

Écrire un programme qui effectue une telle simulation, sur 100000 tours d'horloge, et affiche au final le temps d'attente moyen.

Comparer avec différentes stratégies.

","title":"Exercice","tagtitle":"h1"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On se donne quelques variables globales :

from random import randint

ng = 5 # nb de guichets

tick = 0 # horloge

dispo = [0] * ng

unique = File()

total = 0 # temps d’attente total

servis = 0 # nb de clients servis

On suppose ici une unique file, réalisée ici avec le programme 27. Lorsqu'un

nouveau client arrive, on ajoute son heure d’arrivée dans la file.

def nouveau_client():

unique.ajouter(tick)

On définit une fonction servir pour que le guichet g serve un client.

def servir(g):

global total, servis

if not unique.est_vide():

t = unique.retirer()

total += tick - t

servis += 1

dispo[g] = randint(0, ng)

Enfin, le programme principal est constitué de la boucle suivante.

or __ in range(100000):

tick += 1

nouveau_client()

for g in range(ng):

if dispo[g] == 0:

servir(g)

else:

dispo[g] -= 1

print(total / servis)

Avec ce code, on obtient un temps d’attente moyen quasi nul (0,017). Mais

si on modélise maintenant une file par guichet, en modifiant les fonctions

nouveau_client et servir en conséquence, alors ce temps moyen passe à

1,92 si un nouveau client choisit systématiquement la file contenant le moins de clients et à 3.88 si un client choisit une file au hasard.

"}],[{"text":"

Compléter le programme ci-dessous du jeu de la bataille.

Vous aurez à gérer d'une part la valeur des cartes et d'autre part les cas d'égalités.

Indice : il faut créer une file égalité.

Le programme partiel du jeu de bataille :

from modFile import File

import random

paquet_alice = File()

paquet_basile = File()

#crée le jeu de 52 cartes

cartes = [i for i in range(0,52)]

#melange les cartes

random.shuffle(cartes)

#distribue les cartes aux 2 joueurs

for i in range(len(cartes)//2) :

paquet_alice.ajouter(cartes.pop())

paquet_basile.ajouter(cartes.pop())

#Gestion d'un tour de jeu

def tour():

global en_cours

if paquet_alice.est_vide():

print(\"Alice perd\")

en_cours = False

elif paquet_basile.est_vide():

print(\"Basile perd\")

en_cours = False

else :

tirer()

#Si la partie n'est pas terminée, tirage d'une carte

def tirer():

a = paquet_alice.retirer()

b = paquet_basile.retirer()

valeura = a%13

valeurb = b%13

print(\"Alice\",valeura,valeurb,\"Basile\")

#le programme ne gere pas l'égalité

if valeura > valeurb :

paquet_alice.ajouter(a)

paquet_alice.ajouter(b)

elif valeura < valeurb :

paquet_basile.ajouter(b)

paquet_basile.ajouter(a)

#démarrage du jeu

en_cours = True

nb_tours = 0

while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :

tour()

nb_tours+=1

print(\"Partie en \",nb_tours,\" tours\")

Importer le module modFile.py :

https://sciencesappliquees.com/images/nsi/modFile.py

et tester le jeu de carte de la bataille.

Une fois terminé les modifications, vous transformerez le programme bataille en classe Bataille avec toutes les fonctions encapsulé dans cette-ci.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"Pour afficher la valeur de la carte, on utilise 2 tableau :

def affiche(valeur) :

couleur = [\"Ca\",\"Pi\",\"Co\",\"Tr\"]

numero = [\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"Va\",\"Da\",\"Ro\",\"1\"]

return (couleur[valeur//13],numero[valeur%13])

Le programme de la bataille modifié :

from modFile import File

import random

paquet_alice = File()

paquet_basile = File()

paquet_egalite = File()

#crée le jeu de 52 cartes

cartes = [i for i in range(0,52)]

#melange les cartes

random.shuffle(cartes)

#distribue les cartes aux 2 joueurs

for i in range(len(cartes)//2) :

paquet_alice.ajouter(cartes.pop())

paquet_basile.ajouter(cartes.pop())

#Gestion d'un tour de jeu

def tour():

global en_cours

if paquet_alice.est_vide():

print(\"Alice perd\")

en_cours = False

elif paquet_basile.est_vide():

print(\"Basile perd\")

en_cours = False

else :

tirer()

def affiche(valeur) :

couleur = [\"Ca\",\"Pi\",\"Co\",\"Tr\"]

numero = [\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\",\"10\",\"Va\",\"Da\",\"Ro\",\"1\"]

return (couleur[valeur//13],numero[valeur%13])

def tirer():

a = paquet_alice.retirer()

b = paquet_basile.retirer()

valeura = a%13

valeurb = b%13

print(\"Alice\",affiche(a),affiche(b),\"Basile\")

#le programme ne gere pas l'égalité

if valeura > valeurb :

paquet_alice.ajouter(a)

paquet_alice.ajouter(b)

while not paquet_egalite.est_vide() :

paquet_alice.ajouter(paquet_egalite.retirer())

elif valeura < valeurb :

paquet_basile.ajouter(b)

paquet_basile.ajouter(a)

while not paquet_egalite.est_vide() :

paquet_alice.ajouter(paquet_egalite.retirer())

else : #gerer l'egalité

print(\"Egalité\")

paquet_egalite.ajouter(b)

paquet_egalite.ajouter(a)

#carte à l'envers

if not paquet_alice.est_vide() :

paquet_egalite.ajouter(paquet_alice.retirer())

if not paquet_basile.est_vide() :

paquet_egalite.ajouter(paquet_basile.retirer())

#démarrage du jeu

en_cours = True

nb_tours = 0

while en_cours :#not paquet_alice.est_vide() and not paquet_basile.est_vide() :

tour()

nb_tours+=1

print(\"Partie en \",nb_tours,\" tours\")

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 16 Octobre 2020; Mis à jour : 21 Octobre 2020; Clics : 2062

[[{"title":"Listes chaînées","posi":0},{"text":"

La structure de tableau permet de stocker des séquences d'éléments mais n'est pas adaptée à toutes les opérations que l'on pourrait vouloir effectuer

sur des séquences. Les tableaux de Python permettent par exemple d'insérer ou de supprimer efficacement des éléments à la fin d'un tableau, avec les opérations append et pop, mais se prêtent mal à l'insertion ou la suppression d'un élément à une autre position.

En effet, les éléments d'un tableau étant contigus et ordonnés en mémoire, insérer un élément dans une séquence demande de déplacer tous les éléments qui le suivent pour lui laisser une

place.

Si par exemple on veut insérer une valeur v à la première position d'un tableau

il faut d'une façon où d'une autre construire le nouveau tableau

dans lequel la case d'indice 0 contient maintenant la valeur v.

On peut le faire en utilisant l'opération insert des tableaux de Python.

t = [1,1,2,3,5,8,13]

v = 4

print(\"t =\",t)

t.insert(v,0)

print(\"t =\",t)

Cette opération est cependant très coûteuse, car elle déplace tous les éléments du tableau d'une case vers la droite après avoir agrandi le tableau.

C'est exactement comme si nous avions écrit les lignes suivantes :

t = [1,1,2,3,5,8,13]

v = 4

print(\"t =\",t)

t.append(None)

for i in range(len(t) - 1, 0, -1):

t[i] = t[i - 1]

t[0] = v

print(\"t =\",t)

Avec une telle opération on commence donc par agrandir le tableau, en ajoutant un nouvel élément à la fin avec append.

None

Puis on décale tous les éléments d'une case vers la droite, en prenant soin de commencer par le dernier et de terminer par le premier.

Enfin, on écrit la valeur v dans la première case du tableau.

Au total, on a réalisé un nombre d'opérations proportionnel à la taille du tableau. Si par exemple le tableau contient un million d'éléments, on fera un

million d'opérations pour ajouter un premier élément.

En outre, supprimer le premier élément serait tout aussi coûteux, pour les mêmes raisons.

Dans cette séquence nous étudions une structure de données, la liste chaînée, qui d'une part apporte une meilleure solution au problème de l'insertion et de la suppression au début d'une séquence d'éléments, et d'autre part servira de brique de base à plusieurs autres structures dans les prochaines séquences.

"},{"text":""}],[{"text":"*****

Une liste chaînée permet avant tout de représenter une liste, c'est-à-dire une séquence finie de valeurs, par exemple des entiers.

Comme le nom le suggère sa structure est en outre caractérisée par le fait que les éléments sont chaînés entre eux, permettant le passage d'un élément à l'élément suivant.

Ainsi, chaque élément est stocké dans un petit bloc alloué quelque part dans la mémoire, que l'on pourra appeler maillon ou cellule, et y est accompagné d'une deuxième information : l'adresse mémoire où se trouve la cellule contenant l'élément suivant de la liste.

$\"\"$

Ici, on illustré une liste contenant trois éléments, respectivement 1, 2 et 3.

Programme — Cellule d'une liste chaînée

class Cellule:

\"\"\"une cellule d'une Liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

*****

contenant d'une part sa valeur (dans la case de gauche} et d'autre part l'adresse mémoire de la valeur suivante (dans la case de droite). Dans le cas

du dernier élément, qui ne possède pas de valeur suivante, on utilise une valeur spéciale désignée ici par le symbole ⊥ et marquant la fin de la liste.

Une façon traditionnelle de représenter une liste chaînée en Python consiste à utiliser une classe décrivant les cellules de la liste, de sorte que chaque élément de la liste est matérialisé par un objet de cette classe.

Cette classe est appelée ici Cellule et est donnée dans le programme ci-dessus. Tout objet de cette classe contient deux attributs : un attribut valeur pour la valeur

de l'élément (l'entier, dans notre exemple) et un attribut suivante pour la cellule suivante de la liste.

Lorsqu'il n'y à pas de cellule suivante, c'est-à-dire lorsque l'on considère la dernière cellule de la liste, on donne à l'attribut suivante la valeur None.

Dit autrement, None est notre représentation du

symbole ⊥.

Pour construire une liste, il suffit d'appliquer le constructeur de la classe Cellule autant de fois qu'il y a d'éléments dans la liste.

lst = Cellule(1, Cellule(2, Cellule(3, None)))

Ainsi, l'instruction construit la liste 1,2,3 donnée en exemple plus haut et la stocke dans une variable lst.

Plus précisément, on a ici créé trois objets de la classe Cellule, que l'on peut visualiser comme suit.

print(lst)

La valeur contenue dans la variable lst est l'adresse mémoire de l'objet contenant la valeur 1, qui lui-même contient dans son attribut suivante l'adresse mémoire de l'objet contenant la valeur 2, qui enfin contient dans

son attribut suivante l'adresse mémoire de l'objet contenant la valeur 3.

Ce dernier contient la valeur None dans son attribut suivante, marquant ainsi la fin de la liste.

Par la suite, on s'autorisera un dessin simplifié, de la

manière suivante.

Dans ce dessin, il faut interpréter chaque élément de la liste comme un objet de la classe Cellule.

","title":"Structure de liste chaînée"},{"edit":"

Mettre ici les résultats.

"}],[{"text":"

. Comme on le voit, une liste est soit la valeur None, soit un objet de la classe Cellule dout l'attribut suivante contient une liste. C'est là une définition récursive de la notion de liste.

","title":"Définition récursive des listes chaînées"},{"edit":"

Mettre le résultat ici.

"}],[{"text":"

Représentations alternatives. D'autres représentations des listes chaînées sont possibles. Plutôt qu'un objet de la classe Cellule, on pourrait

utiliser un couple, et dans ce cas écrire (1, (2, (3,None))), ou encore un tableau à deux éléments, et dans ce cas écrire [1, [2, [3,None]]]. Cependant, l'utilisation d'une valeur structurée avec des champs nominés

(ici les attributs valeur et suivante) est idiomatique, y compris dans un langage comme Python.

Variantes des listes chaînées. Il existe de nombreuses variantes de la structure de liste chaînée, dont la liste cyclique, où le dernier élément est lié au premier,

ou la liste doublement chaînée, où chaque élément est lié à l'élément suivant et à l'élément précédent dans la liste,

ou encore la liste cyclique doublement chaînée qui combine ces deux variantes.

Dans tout cette séquence, on ne manipule que des listes simplement chaînées et ne contenant pas de cycles.

Homogénéité. Bien que nous illustrions cette séquence avec des listes d'entiers, les listes chaînées, au même titre que les tableaux Python, peuvent

contenir des valeurs de n'importe quel type.

Ainsi, on peut imaginer des listes de chaînes de caractères, de couples, etc. Comme pour les tableaux, nous recommandons une utilisation homogène des listes chaînées, où tous les éléments de la liste sont du même type.

","title":""},{"edit":"

"}],[{"text":"

Dans cette section, nous allons programmer quelques opérations fondamentales sur les listes.

D'autres opérations sont proposées en exercices.

","title":"Opérations sur les listes"},{"edit":""}],[{"text":"

****

La première opération que nous allons programmer consiste à calculer la longueur d'une liste chaînée, c'est-à-dire le nombre de cellules qu'elle contient.

Il s'agit donc de parcourir la liste, de la première cellule jusqu'à la dernière, en suivant les liens qui relient les cellules entre elles.

On peut réaliser ce parcours, au choix, avec une fonction récursive ou avec une boucle.

Nous allons faire les deux. Dans les deux cas, on écrit une fonction longueur qui reçoit une liste lst en argument et renvoie sa longueur.

def longueur (lst):

\"\"\"renvoie La longueur de la Liste lst\"\"\"

Commençons par la version récursive. Elle consiste à distinguer le cas de base, c'est-à-dire une liste vide ne contenant aucune cellule, du cas général, c'est-à-dire une liste contenant au moins une cellule.

Dans le premier cas, il suffit de renvoyer 0 :

if lst is None:

return 0

Ici, on a testé si la liste lst est égale à None avec l'opération is de Python mais on aurait tout aussi bien pu utiliser ==, c'est-à-dire écrire lst == None.

Dans le second cas, il faut renvoyer 1, pour la première cellule, plus la longueur du reste de la liste, c'est-à-dire la longueur de la liste lst suivante, que l'on peut calculer récursivement :

else:

return 1 + longueur (lst.suivante)

On se persuade facilement que cette fonction termine, car le nombre de cellules de Ia liste passée en argument à la fonction longueur décroît strictement à chaque appel.

Écrivons maintenant la fonction longueur différemment, cette fois avec une boucle. On commence par se donner deux variables : une variable n contenant la longueur que l'on calcule et une variable c contenant la cellule courante du parcours de la liste.

def longueur (lst) :

\"\"\"renvoie la longueur de la liste lst\"\"\"

n = 0

c = lst

Initialement, n vaut 0 et c prend la valeur de lst, c'est-à-dire None si la liste est vide et la première cellule sinon.

Le parcours est ensuite réalisé avec une boucle while, qui exécute autant d'itérations qu'il y a de cellules dans

la liste.

while c is not None:

L'opération is not est, comme on le devine, la négation de l'opération is.

On exécuter donc cette boucic tant que c n'est pas égale à None.

À chaque étape, c'est-à-dire pour chaque cellule de la liste, on incrémente le compteur n et on passe à la cellule suivante en donnant à c la valeur de c.suivante.

n += 1

c = c.suivante

Une fois que l'on sort de la boucle, il suffit de renvoyer la valeur de n.

return n

Il est important de comprendre que, dans cette version itérative, seule la variable c est modifiée, pour désigner successivement les différentes cellules de la liste :

L'affectation c = c.suivante ne modifie pas le contenu ou la structure de la liste, seulement le contenu de la variable c, qui est l'adresse d'une cellule de ta liste.

Le code complet de ces deux fonctions Longueur est donné ci-dessous.

Programme — Calcul de la longueur d'une liste

class Cellule:

\"\"\"une cellule d'une Liste chaînée\"\"\"

def __init__(self, v, s):

self.valeur = v

self.suivante = s

lst = Cellule(1, Cellule(2, Cellule(3, None)))

# avec une fonction récursive

def longueurR(lst):

\"\"\"renvoie la Longueur de La liste lst\"\"\"

if lst is None :

return 0

else:

return 1 + longueurR(lst.suivante)

# avec une boucle

def longueurB(lst):

\"\"\"renvoie la longueur de la Liste lst\"\"\"

n = 0

c = lst

while c is not None:

n += 1

c = c.suivante

return n

print(longueurB(lst))

print(longueurR(lst))

Complexité. Il est clair que la complexité du calcul de la longueur est directement proportionnelle à la longueur elle-même, puisqu'on réalise un

*******

22 aatbete Je 12 dise A

nremhss nnmabtans Anune liste Lst de mille

cellules, longueur (lst) va effectuer mille tests, mille

appels récursifs et mille additions dans sa version récursive, et mille tests, mille additions et deux mille affectations dans sa version itérative.

","title":"Longueur d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comparaison avec None. À priori, il n'y à pas de différence entre écrire lst is None et lst == None.

Les deux opérations ne sont pas exactement les mêmes : l'opération is est une égalité physique {être identiquement le même objet, au même endroit dans la mémoire) et l'opération == est une égalité structurelle (être la même valeur, après une comparaison

en profondeur).

Mais dans le cas particulier de la valeur None, ces deux

égalités coïncident, car l'objet qui représente None est unique.

On teste donc bien si la valeur de lst est None dans les deux cas.

Cependant, une classe peut redéfinir l'égalité représentée par l'opération == et, dans ce cas, potentiellement modifier le résultat d'une comparaison avec None. Pour cette raison, il est d'usage de tester l'égalité à None avec is plutôt qu'avec ==. Bien évidemment, dans le cas précis de notre propre classe Cellule, nous savons qu'elle ne redéfinit pas l'opération ==, Néanmoins, nous choisissons de nous conformer à cette bonne pratique.

"}],[{"text":"

Comme deuxième opération sur les listes, écrivons une fonction qui renvoie le n-ième élément d'une liste chaînée.

On prend la convention que le premier élément est désigné par n = 0, comme pour les tableaux.

On cherche donc à écrire une fonction de la forme suivante.

def nieme_element(n, lst):

\"\"\"renvoie Le n-ième élément de la liste lst

Les éléments sont numérotés à partir de 9\"\"\"

Comme pour la fonction Longueur, nous avons le choix entre écrire la fonction nieme_element comme une fonction récursive ou avec une boucle.

Nous faisons ici le choix d'une fonction récursive.

Comme pour le calcul de la longueur, nous commençons par traiter le cas d'une liste qui ne contient aucun élément. Dans ce cas, on choisit de lever une exception, en l'occurrence la même exception IndexError que celle levée par Python lorsque l'on tente d'accéder à un indice invalide d'un tableau.

if lst is None:

raise IndexError (\"indice invalide\")

La chaîne de caractères passée en argument de l'exception est arbitraire.

Si en revanche la liste lst n'est pas vide, il y à deux cas de figure à considérer. Si n = 0, c'est que l'on demande le premier élément de la liste et il est alors renvoyé.

if n == 0:

return Ist.vaieur

Sinon, il faut continuer la recherche dans le reste de la liste. Pour cela, on fait un appel récursif à nieme_element en diminuant de un la valeur de n.

else:

return nieme_element(n - 1, lst.suivante)

Attention à ne pas oublier ici l'instruction return, car il faut renvoyer le résultat de l'appel récursif et non pas se contenter de faire un appel récursif.

Ceci achève le code de la fonction nieme_element. Le code complet est

Programme — N-ième élément d'une liste

lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def nieme_element(n, lst):

\"\"\"renvote le n-ième élément de La liste lst

les éléments sont numérotés à partir de O\"\"\"

if lst is None:

raise IndexError(\"indice invalide\")

if n == 0 :

return lst.valeur

else:

return nieme_element(n - 1, lst.suivante)

print(nieme_element(2,lst))

Complexité. La complexité de la fonction nieme_element est un peu plus subtile que celle de la fonction longueur. Dans certains cas, on effectue exactement n appels récursifs pour trouver le n-ième élément, et donc un nombre d'opérations proportionnel à n.

Dans d'autres cas, en revanche, on parcourt toute la liste. Cela se produit clairement lorsque n > longueur (lst). Il pourrait être tentant de commencer par comparer n avec la longueur de la liste, pour ne pas parcourir la liste inutilement, mais c'est inutile car le calcul de la longueur parcourt déjà toute la liste. Pire encore, calculer la longueur de la liste à chaque appel récursif résulterait en un programme de complexité quadratique (proportionnelle au carré de la longueur de la liste).

On peut remarquer que la liste est également intégralement parcourue lorsque n < 0. En effet, la valeur de n va rester strictement négative, puisqu'on la décrémente à chaque appel, et on finira par atteindre la liste vide.

Pour y remédier, ii suffit de modifier légèrement le premier test de la fonction, de la manière suivante :

if n < 0 or lst is None:

raise IndexError(\"indice invalide\")

On obtient exactement le même comportement qu'auparavant (la levée de l'exception IndexError) mais cela se fait maintenant en temps constant, car la liste n'est plus parcourue.

","title":"N-ième élément d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

*****

Considérons maintenant l'opération consistant à mettre bout à bout les éléments de deux listes données.

On appelle cela la concaténation de deux

listes.

Ainsi, si la première liste contient 1,2,3 et la seconde 4,5 alors le

****

de fanntinn nn la linda 4 D M O4 AT

sénat da la anmne

la concaténation sous la forme d'une fonction concatener qui reçoit deux listes en arguments et renvoie une troisième liste contenant la concaténation.

def concatener{(l1, l2):

\"\"\"concatène les listes l1 et l2, sous la forme d'une nouvelle liste\"\"\"

Il est ici aisé de procéder récursivement sur la structure de la liste 11. Si elle est vide, la concaténation est identique à la liste l2, qu'on se contente donc de renvoyer.

if l1 is None:

return l2

Sinon, le premier élément de la concaténation est le premier élément de l1 et le reste de la concaténation est obtenu récursivement en concaténant le reste de 11 avec l2.

else:

return Cellule(l1.valeur, concatener(l1.suivante,l2))

Le programme ci-dessus contient l'intégralité du code.

Il est important de comprendre ici que les listes passées en argument à la fonction concatener ne sont pas modifiées.

Plus précisément, les éléments de la liste l1 sont copiés et ceux de l2 sont partagés. Illustrons-le avec la

concaténation des listes 1,2,3 et 4,5.

Après les trois instructions

l1 = Celiule(1, Cellule(2, Cellule(3, None)))

l2 = Cellule(4, Cellule(5, None))

l3 = concatener(l1, l2)

on à la situation suivante, avec huit cellules au total :

On voit que les trois cellules de l1 ont été dupliquées, pour former le début de la liste 1,2, 3 ,4, 5, et que les deux cellules de l2 sont partagées pour former à

la fois la liste l2 et la fin de la liste l3.

Il n'y a pas de danger à réaliser ainsi un tel partage de cellules, tant qu'on ne cherche pas à modifier les listes, Une alternative consisterait à copier également tous les éléments de l2, ce qui pourrait se faire en écrivant une fonction copie et en remplaçant return l2 par

return copie(l2).

Mais c'est inutile dès lors qu'on choisit de ne jamais modifier les listes une fois construites.

Dans la section suivante, nous discuterons d'une autre façon de réaliser la concaténation de deux listes l1 et l2, consistant à modifier la dernière cellule de la liste 11 pour la faire pointer vers la première cellule de la liste l2.

Mais nous mettrons également en garde contre les dangers que comporte une

********

Programme - Concaténation de deux listes

def concatener(l1, l2):

\"\"\"concatène les listes l1 et l2, sous La forme d'une nouvelle liste\"\"\"

if l1 is None:

return l2

else:

return Cellule(l1.valeur, concatener(l1.suivante,l2))

l1 = Cellule(1, Cellule(2, Cellule(3, None)))

l2 = Cellule(4, Cellule(5, None))

l3 = concatener(l1, l2)

print(\"lg l3=\", longueurB(l3))

Complexité. Il est clair que le coût de la fonction concatener est directement proportionnel à la longueur de la liste 11. En revanche, il ne dépend

pas de la longueur de la liste l2.

","title":"Concaténation de deux listes"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Comme quatrième et dernière opération sur les listes, considérons le renversement d'une liste, c'est-à-dire une fonction renverser qui, recevant en argument une liste comme 1,2, 3, renvoie la liste renversée 3, 2,1.

Vu que la récursivité a été utilisée avec succès pour écrire les trois opérations précédentes, il semble naturel de chercher une écriture récursive de la fonction renverser.

Le cas de base est celui d'une liste vide, pour laquelle

il suffit de renvoyer la liste vide. Pour le cas récursif, en revanche, c'est plus délicat, car le premier élément doit devenir le dernier élément de la liste renversée. Aussi, il faut renverser la queue de la liste puis concaténer à la fin le tout premier élément.

Vu que nous venons justement d'écrire une fonction

concatener, il n'y a qu'à s'en servir. Cela nous donne un code relativement simple pour la fonction renverser.

def renverser1(lst):

if lst is None:

return None

else:

return concatener(renverser(lst.suivante), Cellule(lst.valeur, None))

l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))

r1 = renverser1(l1)

Un tel code, cependant, est particulièrement inefficace. Si on en mesure le temps d'exécution, on s'aperçoit qu'il est proportionnel au carré du nombre d'éléments.

Pour renverser une liste de 1000 éléments, il faut près d'un demimillion d'opérations.

En effet, il faut commencer par renverser une liste de 999 éléments, puis concaténer le résultat avec une liste d'un élément. Comme on l'a vu, cette concaténation coûte 999 opérations. Et pour renverser la liste de 999 éléments, il faut renverser une liste de 998 éléments puis concaténer le résultat avec une liste d'un élément. Et ainsi de suite.

Au total, on a donc au moins 999 + 998 + .. + 1 = 499500 opérations.

Une fois n'est pas coutume, la récursivité nous à mis sur la piste d'une mauvaise solution, du moins en termes de performance.

Il se trouve que dans le cas de la fonction renverser, une boucle while est plus adaptée.

En effet, il suffit de parcourir les éléments de la liste lst avec une simple boucle, et d'ajouter ses éléments au fur et à mesure en tête d'une seconde liste, appelons-la r.

Ainsi, le premier élément de la liste lst se retrouve en dernière position dans la liste r, le deuxième élément de lst en avant-dernière position dans r, etc., jusqu'au dernier élément de lst qui se retrouve en première position dans r.

Une bonne image est celle d'une pile de feuilles de papier sur notre bureau : si on prend successivement chaque feuille au sommet de la pile pour former à côté une seconde pile, alors on aura inversé l'ordre des feuilles au final.

Ici, la liste lst joue le rôle de la première pile et la liste r celle de la seconde.

Pour mettre en œuvre le code, on commence par se donner deux variables : une variable r pour le résultat et une variable c pour parcourir la liste lst.

def renverser(lst):

r = None

c = lst

On parcourt ensuite la liste avec une boucle while, en ajoutant à chaque étape le premier élément de c en tête de la liste r, avant de passer à l'élément suivant.

while c is not None:

Cellule(c.valeur, r)

c = c.suivante

Enfin, il ne reste plus qu'à renvoyer la liste r une fois sorti de la boucle.

return r

Le programme ci-dessous contient l'intégralité du code.

def renverser(lst):

\"\"\"renvoie une liste contenant les éléments de lst dans l'ordre inverse\"\"\"

r = None

c = lst

while c is not None:

r = Cellule(c.valeur, r)

c = c.suivante

return r

def afficher(lst) :

\"\"\"affiche les éléments d'une liste\"\"\"

c = lst

while c is not None:

print(c.valeur,c.suivante)

c = c.suivante

print(\"l1 = \")

l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))

afficher(l1)

print(\"r1 = \")

r1 = renverser(l1)

afficher(r1)

Complexité. Il est clair que cette nouvelle fonction

directement proportionnel à la longueur de la liste lst, car le code fait un simple parcours de la liste, avec deux opérations élémentaires à chaque étape.

Ainsi, renverser une liste de 1000 éléments devient presque instantané, avec un millier d'opérations, là où notre fonction basée sur la concaténation utilisait un demi-million d'opérations.

","title":"Renverser une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Jusqu'à présent, nous avons délibérément choisi de ne jamais modifier les deux attributs valeur et suivante d'un objet de la classe Cellule. Une fois qu'un tel objet est construit, il n'est plus jamais modifié.

Cependant, rien ne nous empêcherait de le faire, intentionnellement ou accidentellement, car il reste toujours possible de modifier la valeur de ces attributs a posteriori avec des affectations.

Reprenons l'exemple de la liste 1,2,3 du début de cette séquence, construite avec

lst = Cellule(1, Cellule(2, Cellule(3, None)))

et que nous représentons ainsi :

Nous pouvons modifier la valeur du deuxième élément de la liste avec l'affectation suivante

lst.suivante.valeu = 4

On n alors la situation suivante :

C'est-à-dire avec la liste 1,3,8.

Ici, on vient de modifie le contenu de la liste,

en modifiant un attribut valeur.

Mais on peut également modifier la structure de la liste, en modifiant un attribut suivante.

Si par exemple on réalise maintenant l'affectation

lst.suivante.suivante =Cellule(5,None)

alors on se retrouve avec la situation suivante :

Ici, on a représenté que l'attribut suivante du deuxième élément pointait anciennement vers l'élément 3 (en pointillés) et qu'il pointe désormais vers un nouvel élément 5. La variable lst contient maintenant la liste 1,4,3.

","title":"Modification d'une liste"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Puisque les listes peuvent être modifiées à posteriori, comme nous venons de l'expliquer, il peut être tentant d'en tirer profit pour écrire autrement certaines de nos opérations sur les listes.

Ainsi, pour réaliser la concaténation de deux listes, par exemple, il suffit de modifier l'attribut suivante du

dernier élément de la première liste pour lui donner la valeur de la seconde liste.

Cela semble une bonne idée. Mais il y a un risque.

Supposons que l'on construise deux listes 1,2,3

et 4,5 de la manière suivante :

l2 = Cellule(2, Cellule(3, None))

l1 = Cellule(1, l2)

l3 = Cellule(4, Cellule(5, None))

On note en particulier que la variable l2 contient toujours la liste 2,3, même si elle a servi depuis à construire la liste 1,2,3 stockée dans la variable l1.

S'il nous prend maintenant l'envie de concaténer les listes l1 et l3 en reliant le dernier élément de l1 au premier élément de l3, par exemple en appelant

une fonction concatener_en_place(l1, l3) qui ferait cela, alors on se retrouverait dans cette situation :

La variable l1 contient maintenant la liste 1,2,3,4,5, ce qui était recherché, mais la variable l2 ne contient plus la liste 2,3 mais la liste 2,3,4,5.

C'est là un effet de bord qui n'était peut-être pas du tout souhaité.

D'une manière générale, pouvoir accéder à une même donnée par deux chemins différents n'est pas un problème en soi, mais modifier ensuite la donnée par l'intermédiaire de l'un de ces chemins (ici l1) peut résulter en une modification non souhaitée de la valeur accessible par un autre chemin (ici l2).

Par ailleurs, que feraient deux appels supplémentaires à concatener_en_place(l1, l3)?

C'est pourquoi nous avons privilégié une approche où la concaténation, et plus généralement les opérations qui construisent des listes, renvoient de nouvelles listes plutôt que de modifier leurs arguments.

On peut remarquer que c'est là une approche également suivie par certaines constructions de Python. L'opération + de Python, par exemple, ne modifie pas ses arguments mais renvoie une nouvelle valeur, qu'il s'agisse d'entiers, de chaînes de caractères ou encore de tableaux.

Ainsi, si t est le tableau [1, 2], alors t + [3]

construit un nouveau tableau [1, 2, 3].

En ce sens, l'opération + se distingue d'autres opérations, comme .append, qui modifient leur argument.

Comme nous allons le voir dans la section suivante, cela ne nous empêche pas pour autant d'utiliser nos listes dans un style de programmation impératif.

","title":"Du danger des listes mutables"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

*****

Pour terminer cette séquence sur les listes chaînées, nous allons maintenant montrer comment encapsuler une liste chaînée dans un objet.

L'idée consiste à définir une nouvelle classe, Liste, qui possède un unique attribut, tete, qui contient une liste chaînée. On l'appelle tete car il désigne la tête de la liste, lorsque celle-ci n'est pas vide (et None sinon).

Le constructeur initialise l\"attribut tete avec la valeur None.

class Liste:

\"\"\"une Liste chaînée\"\"\"

def __init__(self):

self.tete = None

Autrement dit, un objet construit avec Liste() représente une liste vide.

On peut également introduire une méthode est_vide qui renvoie un booléen indiquant si la liste est vide.

def est_vide(self):

return self.tete is None

En effet, notre intention est d'encapsuler, c'est-à-dire de cacher, la représentation de la liste derrière cet objet. Pour cette raison, on ne souhaite pas que l'utilisateur de la classe Liste teste explicitement si l'attribut tete vaut None, mais qu'il utilise cette méthode est_vide.

On poursuit la construction de la classe Liste avec une méthode pour ajouter un élément en tête de la liste.

def ajoute(self, x):

self.tete = Cellule(x, self.tete)

Cette méthode modifie l'attribut tete et ne renvoie rien. Si par exemple on exécute les quatre instructions ci-dessous :

lst = Liste()

lst.ajoute(3)

lst.ajoute(2)

lst.ajoute(1)

on obtient la situation suivante :

On a donc construit ainsi la liste 1,2,3, dans cet ordre.

On peut maintenant reformuler nos opérations, à savoir longueur, nieme_element, concatener ou encore renverser, comme autant de méthodes de la classe Liste.

Ainsi, on peut écrire par exemple

def longueur(self):

return longueur(self.tete)

qui ajoute à la classe Liste une méthode longueur, qui nous permet d'écrire lst.longueur(} pour obtenir la longueur de la liste lst.

Il est important de noter qu'il n'y a pas confusion ici entre la fonction longueur définie précédemment et la méthode longueur.

En particulier, la seconde est définie en appelant la première. Le langage Python est ainsi fait que, lorsqu'on écrit longueur (self.tete), il ne s'agit pas d'un appel récursif à la méthode longueur. (Un appel récursif s'écrirait self. longueur().) Si l'on trouve que donner le même nom à la fonction et à la méthode est source de confusion, on peut tout à fait choisir un nom différent pour la méthode, comme par exemple

def taille(self):

return longueur(self.tete)

Mieux encore, on peut donner à cette méthode le nom __len__ et Python nous permet alors d'écrire len(lst} comme pour un tableau.

En eflet, lorsque l'on écrit len en Python, ce n'est qu'un synonyme pour l'appel de méthode __len__().

De même, on peut ajouter à la classe Liste une méthode pour accéder au n-ième élément de la liste, c'est-à-dire une méthode qui va appeler notre fonction nieme_element sur self.tete.

Le nom de la méthode est arbitraire et nous pourrions choisir de conserver le nom nieme_element. Mais

là encore nous pouvons faire le choix d'un nom idiomatique en Python, à savoir __getitem__

def __getitem_ _(self, n):

return nieme_element(n, self.tete)

Ceci nous permet alors d'écrire lst{[i] pour accéder au i-ème élément de notre liste, exactement comme pour les tableaux.

Pour la fonction renverser, on fait le choix de nommer la méthode reverse car là encore

*****

Dhaat nie nue must mena AIX masse dan obilansie da Dia

Programme - Encapsulation d'une liste dans un objet

class Liste:

\"\"\"une Liste chaînée\"\"\"

def __init__(self):

self.tete = None

def est_vide(self):

return self.tete is None

def ajoute(self, x):

self.tete = Cellule(x, self.tete)

def __len__(self):

return longueurB(self.tete)

def __getitem__(self, n):

return nieme_element(n, self.tete)

def reverse(self) :

self.tete = renverser(self.tete)

def __add__(self, lst):

r = Liste()

r.tete = concatener(self.tete, lst.tete)

return r

lst = Liste()

print(lst.est_vide())

lst.ajoute(3)

print(lst.est_vide())

lst.ajoute(2)

lst.ajoute(1)

print(len(lst))

print(lst[1])

Enfin, le cas de la concaténation est plus subtil, car il s'agit de renvoyer une nouvelle liste, c'est-à-dire un nouvel objet. On choisit d'appeler la méthode __add__ qui correspond à la syntaxe + de Python.

def __add__(self, lst):

r = Liste()

r.tete = concatener(self.tete, lst.tete)

return r

Ainsi, on peut écrire lst+lst pour obtenir la liste 1,2,3,1,2,3.

","title":"Encapsulation dans un objet"},{"edit":"

Mettre le résultat ici (code et figure).

"}],[{"text":"

Intérêt d'une telle encapsulation. Il est multiple. D'une part, il cache la représentation de la structure à l'utilisateur.

Ainsi, celui qui utilise notre classe Liste n'a plus à manipuler explicitement la classe Cellule.

Mieux encore, il peut complètement ignorer l'existence de la classe Cellule.

De même, il ignore que la liste vide est représentée par la valeur None. En particulier, la réalisation de la classe Liste pourrait être modifiée sans pour autant que le

code qui l'utilise n'ait besoin d'être modifié à son tour.

D'autre part, l'utilisation de classes et de méthodes nous permet de donner le même nom à toutes les méthodes qui sont de même nature.

Ainsi, on peut avoir plusieurs classes avec des méthodes est_vide, ajoute, etc. Si nous avions utilisé de simples fonctions, il faudrait distinguer

liste _est_vide, pile est vide, ensemble _est_vide, etc.

","title":""},{"edit":"

"}],[{"text":"

Écrire une fonction listeN(n) qui reçoit en argument un entier n, supposé positif ou nul, et renvoie la liste des entiers 1,2,...,n, dans cet ordre. Si n = 0, la liste renvoyée est vide.

Tester avec :

l2 = listeN(5)

afficher(l2)

Résultat :

1 <__main__.Cellule object at 0x103540a20>

2 <__main__.Cellule object at 0x103540a58>

3 <__main__.Cellule object at 0x103540da0>

4 <__main__.Cellule object at 0x103540a90>

5 None

Attention les adresses mémoires ne seront pas les mêmes.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def listeN(n):

lst = None

while n > 0:

lst = Cellule(n, lst)

n -= 1

return lst

l2 = listeN(5)

afficher(l2)

"}],[{"text":"

Écrire une fonction affiche liste(lst) qui affiche, en utilisant la fonction print, tous les éléments de la liste lst, séparés par des espaces, suivis d'un retour chariot.

L'écrire comme une fonction récursive, puis avec une boucle while.

Tester avec :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

affiche_liste(l2)

Le résultat est :

a b c d

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Pour éviter que print n’insère un retour chariot après chaque élément, on utilise print(..., end= \" \"), puis un unique print() à la fin de la liste.

Avec une récursivité :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def affiche_liste(lst):

if lst is None:

print()

else :

print(lst.valeur, end=\" \")

affiche_liste(lst.suivante)

affiche_liste(l2)

Avec une itération :

l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def affiche_liste(lst):

c = lst

while c is not None:

print(c.valeur, end=\" \")

c = c.suivante

print()

affiche_liste(l2)

"}],[{"text":"

Réécrire la fonction nieme_element

lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

def nieme_element(n, lst):

\"\"\"renvote le n-ième élément de La liste lst

les éléments sont numérotés à partir de O\"\"\"

if lst is None:

raise IndexError(\"indice invalide\")

if n == 0 :

return lst.valeur

else:

return nieme_element(n - 1, lst.suivante)

print(nieme_element(2,lst))

avec une boucle while.

Tester avec :

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

print(nieme_element(2,l1))

Résultat :

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Comme pour la fonction longueur, on se sert d’une

variable c pour parcourir la liste. On se sert également d’une variable i pour

mesurer notre avancement dans la liste. Il y a donc une double condition

d’arrêt à la boucle.

def nieme_element(n, lst):

i = 0

c = lst

while i < n and c is not None:

i += 1

c = c.suivante

if n < 0 or c is None:

raise IndexError(\"indice invalide\")

return c.valeur

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))

print(nieme_element(2,l1))

Note : la condition n < 0 nous préserve d’une valeur négative qui aurait été passée à la fonction nieme_element. Bien entendu, on aurait pu effectuer ce

test dès l’entrée de la fonction, avant même de parcourir la liste, ou encore supposer que n est positif ou nul.

"}],[{"text":"

Écrire une fonction occurrences(x, lst) qui renvoie le

nombre d'occurrences de la valeur x dans la liste lst.

L'écrire comme une fonction récursive, puis avec une boucle while.

Tester avec :

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

Résultat :

nb b : 3

nb a : 1

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Avec une fonction récursive :

def occurrences(x, lst):

if lst is None:

return 0

elif x == lst.valeur:

return 1 + occurrences(x, lst.suivante)

else:

return occurrences(x, lst.suivante)

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

Avec une itération (boucle) :

def occurrences(x, lst):

n=0

c = lst

while c.suivante is not None :

if x == c.valeur:

n += 1

c = c.suivante

if x == c.valeur:

n += 1

return n

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"nb b :\",occurrences(\"b\",l1))

print(\"nb a :\",occurrences(\"a\",l1))

"}],[{"text":"

Écrire une fonction trouve(x, lst} qui renvoie le rang de la première occurrence de x dans lst, le cas échéant, et None sinon.

L'écrire comme une fonction récursive, puis avec une boucle while.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

Tester avec ;

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

Résultat :

posi c : 2

posi a : 0

posi e : None

"},{"solution":"

Ici la version récursive est assez pénible à écrire, car

il faut tester si l’appel récursif a renvoyé None :

ef trouve(x, lst):

if lst is None:

return None

elif lst.valeur == x :

return 0

else:

r = trouve(x, lst.suivante)

if r == None:

return None

else:

return 1 + r

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

La boucle, en revanche, est plus simple à écrire :

def trouve(x, lst):

i=0

c = lst

while c is not None:

if c.valeur == x:

return i

c = c.suivante

i += 1

return None

l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))

print(\"posi c :\",trouve(\"c\",l1))

print(\"posi a :\",trouve(\"a\",l1))

print(\"posi e :\",trouve(\"e\",l1))

"}],[{"text":"

Écrire une fonction récursive concatener_inverse(l1, l2)

qui renvoie le même résultat que concatener(renverser(l1), l2), mais sans appeler ces deux fonctions.

En déduire une fonction renverser qui a la même complexité que le programme renverser de la séquence.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst = concatener_inverse(lst1,lst1)

affiche_liste(lst)

Résultat :

6 5 4 3 2 1 1 2 3 4 5 6

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On procède récursivement sur la structure de la

liste l1 :

def concatener_inverse(l1, l2):

if l1 is None:

return l2

else:

return concatener_inverse(l1.suivante, \\

Cellule(l1.valeur, l2))

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst = concatener_inverse(lst1,lst1)

affiche_liste(lst)

La fonction renverser s’en déduit trivialement, en prenant une liste videdef renverser (1st):

return concatener_inverse(lst, None)

"}],[{"text":"

Écrire une fonction identiques(l1, l2) qui renvoie un booléen indiquant si les listes l1 et l2 sont identiques, c'est-à-dire contiennent exactement les mêmes éléments, dans le même ordre.

On suppose que l'on peut comparer les éléments de l1 et l2 avec l'égalité == de Python.

Tester avec :

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))

print(identiques(lst1,lst2))

print(identiques(lst1,lst3))

Résultat :

True

False

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

On le fait ici avec une fonction récursive. Il faut

prendre soin de bien traiter le cas où l’une ou l’autre des listes est vide :

def identiques(l1, l2):

if l1 is None:

return l2 is None

if l2 is None:

return l1 is None

return l1.valeur == l2.valeur \\

and identiques(l1.suivante, l2.suivante)

lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))

lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))

print(identiques(lst1,lst2))

print(identiques(lst1,lst3))

"}],[{"text":"

Écrire une fonction inserer(x, lst) qui prend en arguments un entier x et une liste d'entiers lst, supposée triée par ordre croissant, et qui renvoie une nouvelle liste dans laquelle x a été inséré à sa place

Ainsi, insérer la valeur 3 dans la liste 1,2, 5,8 renvoie la liste 1,2,3,5,8.

On suggère d'écrire inserer comme une fonction récursive.

Tester avec :

lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))

affiche_liste(lst)

lst = inserer(4,lst)

lst = inserer(1,lst)

lst = inserer(14,lst)

affiche_liste(lst)

Résultat :

2 4 7 8 9 12

1 2 4 4 7 8 9 12 14

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le cas d'arrêt est double : soit la liste est vide,

soit x n’est pas plus grand que la valeur en tête de liste. Dans les deux cas, on ajoute x au début de lst. Sinon, on conserve le premier élément et on

insère x récursivement dans la liste lst.suivante.

def inserer(x, lst):

if lst is None or x <= lst.valeur:

return Cellule(x, lst)

else:

return Cellule(lst.valeur, inserer(x, lst.suivante))

lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))

affiche_liste(lst)

lst = inserer(4,lst)

lst = inserer(1,lst)

lst = inserer(14,lst)

affiche_liste(lst)

"}],[{"text":"

En se servant de l'exercice précédent, écrire une fonction tri_par_insertion(lst) qui prend en argument une liste d'entiers lst et renvoie une nouvelle liste, contenant les mêmes éléments et triée par ordre croissant.

On suggère de l'écrire comme une fonction récursive.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

affiche_liste(lst1)

lst2 = tri_par_insertion(lst1)

affiche_liste(lst2)

Résultat :

5 8 7 1 3 6

1 3 5 6 7 8

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

Le cas de base correspond à une liste de longueur

au plus 1, pour laquelle il suffit de la renvoyer.

def tri_par_insertion(lst):

if lst is None or lst.suivante is None:

return lst

else:

return inserer(lst.valeur, \\

tri_par_insertion(lst.suivante))

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

affiche_liste(lst1)

lst2 = tri_par_insertion(lst1)

affiche_liste(lst2)

Note : on pourrait également écrire if longueur(ist) <= 1 mais ce serait calculer inutilement la longueur de la liste (calculer la longueur oblige à parcourir toute la liste), ce qui dégraderait les performances de ce programme.

"}],[{"text":"

Exercice 57 Écrire une fonction liste_de_tableau(t} qui renvoie une liste qui contient les éléments du tableau t, dans le même ordre.

On suggère de l'écrire avec une boucle for.

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

Tester avec :

t1 = [2,4,5,7,9,10,12]

print(t1)

lst1 = liste_de_tableau(t1)

affiche_liste(lst1)

Résultat ;

[2, 4, 5, 7, 9, 10, 12]

2 4 5 7 9 10 12

"},{"solution":"

Pour préserver l’ordre des éléments, il faut prendre

soin de parcourir le tableau de la droite vers la gauche :

def liste_de_tableau(t):

lst = None

for i in range(len(t) - 1, -1, -1):

lst = Cellule(t[i], lst)

return lst

t1 = [2,4,5,7,9,10,12]

print(t1)

lst1 = liste_de_tableau(t1)

affiche_liste(lst1)

"}],[{"text":"

Écrire une fonction derniere_cellule(lst) qui renvoie l'adresse mémoire de la dernière cellule de la liste lst. On suppose la liste lst non vide.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

print(derniere_cellule(lst1))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

print(derniere_cellule(lst2))

Résultat :

<__main__.Cellule object at 0x10405f898>

<__main__.Cellule object at 0x10405fe48>

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def derniere_cellule(lst):

c = lst

while c.suivante is not None:

c = c.suivante

return c

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

print(derniere_cellule(lst1))

"}],[{"text":"

En utilisant la fonction de l'exercice précédent, écrire une seconde fonction, concatener_en_place(l1, l2), qui réalise une concaténation en place des listes l1 et l2, c'est-à-dire qui relie la dernière cellule de l1 à la première cellule de l2. Cette fonction doit renvoyer la toute première cellule de la concaténation.

Tester avec :

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

affiche_liste(lst1)

affiche_liste(lst2)

lst3 = concatener_en_place(lst1, lst2)

affiche_liste(lst1)

affiche_liste(lst2)

affiche_liste(lst3)

Résultat :

5 8 7 1 3 6

1 5 4 6 8

5 8 7 1 3 6 1 5 4 6 8

1 5 4 6 8

5 8 7 1 3 6 1 5 4 6 8

","title":"Exercice"},{"edit":"

Mettre le résultat ici (code et figure).

"},{"solution":"

def concatener_en_place(l1, l2):

if l1 is None:

return l2

c = derniere_cellule(l1)

c.suivante = l2

return l1

lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))

lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))

affiche_liste(lst1)

affiche_liste(lst2)

lst3 = concatener_en_place(lst1, lst2)

affiche_liste(lst1)

affiche_liste(lst2)

affiche_liste(lst3)

"}]]

Détails: Écrit par : Richard GAUTHIER; Création : 14 Octobre 2020; Mis à jour : 14 Octobre 2020; Clics : 1571

Exercice 1 :

L'entreprise LocHome souhaite moderniser son système de location. En effet, elle utilise des fiches papiers pour gérer ses locations.

1.1. Donner la modélisation relationnelle de service de location.

Cette dernière doit permettre de mentionner :

- le client, possédants un numéro de téléphone alphanumérique unique, nom, prénom et adresse;

- la maison, possédants un identifiant unique, nombre de pièces et adresse;

- en location, possédants la date de début, la date de fin et les relations entre client et maison.

On prendra soin de préciser toutes les contraintes utilisateurs qui ne peuvent êtres inscrites dans les schémas des relations.

1.2. Donner les commandes SQL pour écrire ces tables.

Exercice 2 :

Soit les tables suivantes :

« Candidats » composé des champs suivants :
+ Matricule : Numéro d'immatriculation du candidat
+ Nom: nom du candidat
+ DateNaissance : date de naissance du candidat
+ DateDiplome : date d'obtention du diplôme
+ Code_ecole : code de l'école qui a délivrée le diplôme

«Ecole » composé des champs suivants :
+ Code_ecole :
+ Lib_école : intitulé de l'école

2.1. Ecrire en SQL l'insertion dans la table « candidats » un nouveau candidat ayant le matricule 3200. nommé
« Albert ». né le 12052004, et qui a obtenu son diplôme le 03/07/2020 délivré par Lycée Sérusier ayant le code 29022.

2.2. Ecrire en SQL la requête pour avoir la liste des candidats triés par ordre alphabétique.

2.3. Ecrire en SQL la requête pour avoir la liste des candidats lauréats de l'école « Séruiser ».

2.4. Ecrire en SQL la requête pour calculer l'age moyen des candidats.

Exercice 3 :

Vous allez importer dans phpmyadmin la base world.sql (Télécharger ici).

Elle se décompose de la manière suivante :

Table

city

name, le nom

code, le code du pays

district

population, la population de la ville

Table

country

code, le cpde du pays

name, le nom du pays

capital, la capitale du pays

Table

countryinfo

` (

code, le code du pays

indepyear, date indépendance pays

region, la région ou se situe le pays

continent, le continent ou se situe le pays

surfaceArea, la surface du pays

`governmentForm, le régime du pays

`population

lifeExpectancy, l'espérance de vie du pays

Table

countrylanguage

code, le code du pays

language, langue parler dans le pays

isOfficial, langue officiel (True ou False),

percentage, % parler par la population

3.1. Importer la base world.sql dans phpmyadmin.

3.2. Ecrire la requête SQL pour afficher toute la table des pays (country).

3.3. Ecrire la requête SQL pour afficher population française (code pays FRA).

3.4. Ecrire la requête SQL pour mettre à jour la population française (67000000 et code pays FRA).

3.5. Ecrire la requête SQL qui affiche le pays le plus peuplé.

3.6. Ecrire la requête SQL pour inserer dans la table city la ville de carhaix avec les attributs suivants : Carhaix, FRA, Bretagne, 7100.

3.7. Ecrire la requête SQL qui calcule la population mondiale.

3.8.Ecrire la requête SQL qui afficher la liste des pays qui parlent le français dans le monde.

3.9. Ecrire en utilisant une jointure avec les tables country et city, la requête SQL qui affiche les villes en France dans la table city.

3.10. Ecrire la requête SQL qui supprime la table countrylangage.

Détails: Écrit par : Richard GAUTHIER; Création : 13 Octobre 2020; Mis à jour : 17 Octobre 2021; Clics : 1297

Page 45 sur 79

1ère Générale NSI

Term. Générale NSI

Terminale STI2D SIN

Bts Ccst

Technico-commercial 3.0

Vidéos YouTube

tnsi json sequence 20 arbre binaire de recherche

tnsi json sequence 19 arbre binaire

tnsi json sequence 18 Piles et files

tnsi json sequence 17 Listes chaînées

Devoir sql 2020