Actualité

[[{"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 : 1404

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 : 1149

[[{"login":"aa"}],[{"quiz":1090}]]

Détails: Écrit par : Richard GAUTHIER; Création : 11 Octobre 2020; Mis à jour : 11 Octobre 2020; Clics : 1196

[[{"login":"devoir"}],[{"quiz":1090}]]

Détails: Écrit par : Richard GAUTHIER; Création : 11 Octobre 2020; Mis à jour : 6 Octobre 2021; Clics : 792

[[{"text":"Vous allez répondre à un QCM sur la partie 1 du programme de NSI : Encodage des données.

Consignes :

- 1 seul moniteur d'allumé;

- 1 seul onglet ouvert sur sciencesappliquees.com dans le navigateur chrome;

- Aucun autre logiciel doit être exécuté pendant le test.

Si vous enfreignez une de ces consignes, vous aurez 0 avec 2 heures de colles pour tentative de triche!

","title":""}],[{"text":"Quel est un avantage du codage UTF8 par rapport au codage ASCII ?","theme":"A","nume":"1","sujet":3,"annee":2020},{"radio":[{"label":" il permet de coder un caractère sur un octet au lieu de deux"},{"label":" il permet de coder les majuscules"},{"label":" il permet de coder tous les caractères","sol":true},{"label":" il permet de coder différentes polices de caractères"}]}],[{"text":"On considère les codes ASCII en écriture hexadécimale (en base 16).
Le code ASCII de la lettre A est 0x41, celui de la lettre B est 0x42, celui de la lettre C est 0x43, etc. Quel est le code ASCII, en hexadécimal, de la lettre X (c'est la 24e lettre de l'alphabet usuel). ","theme":"A","nume":"2","sujet":3,"annee":2020},{"radio":[{"label":" 0x58","sol":true},{"label":" 0x64"},{"label":" 0x7A"},{"label":" 0x88"}]}],[{"text":"Quelle est la représentation en binaire de l'entier 64 sur un octet ?","theme":"A","nume":"3","sujet":3,"annee":2020},{"radio":[{"label":" 0101 0000"},{"label":" 1100 0100"},{"label":" 0100 0000","sol":true},{"label":" 0000 1100"}]}],[{"text":"Le codage d’une couleur se fait à l'aide de trois nombres compris chacun, en écriture décimale, entre 0 et 255 (code RVB).
La couleur « vert impérial » est codée, en écriture décimale, par (0, 86, 27).
Le codage hexadécimal correspondant est :","theme":"A","nume":"4","sujet":3,"annee":2020},{"radio":[{"label":" (0, 134, 39)"},{"label":" (0, 134, 1B)"},{"label":" (0, 56, 1B)","sol":true},{"label":" (0, 56, 39)"}]}],[{"text":"Quelle est l’écriture hexadécimale de l’entier dont la représentation en binaire non signé est 1100 0011 ? ","theme":"A","nume":"5","sujet":3,"annee":2020},{"radio":[{"label":" BB"},{"label":" C3","sol":true},{"label":" CB"},{"label":" 7610"}]}],[{"text":"Quel est le nombre maximal de bits du produit de deux entiers positifs codés sur 8 bits ?","theme":"A","nume":"6","sujet":3,"annee":2020},{"radio":[{"label":"8 "},{"label":" 16 ","sol":true},{"label":" 32 "},{"label":" 64"}]}],[{"text":"Un nombre entier signé est codé en complément à deux sur 8 bits par : 0111 0101. Que peut-on dire ?","theme":"A","nume":"1","sujet":4,"annee":2020},{"radio":[{"label":" c'est un nombre positif","sol":true},{"label":" c'est un nombre négatif"},{"label":" c'est un nombre pair"},{"label":" 7 bits auraient suffi à représenter cet entier signé en complément à deux"}]}],[{"text":"Comment s'écrit en base 16 (en hexadécimal) le nombre dont l'écriture binaire est 0010 1100 ? ","theme":"A","nume":"2","sujet":4,"annee":2020},{"radio":[{"label":" 1D"},{"label":" 2C","sol":true},{"label":" 3C "},{"label":" 3E"}]}],[{"text":"On considère les nombres dont l'écriture en base 16 (en hexadécimal) sont de la forme suivante : un 1 suivi de 0 en nombre quelconque, comme 1, 10, 100, 1000 etc.
Tous ces nombres sont exactement :","theme":"A","nume":"3","sujet":4,"annee":2020},{"radio":[{"label":" les puissances de 2"},{"label":" les puissances de 8"},{"label":" les puissances de 10"},{"label":" les puissances de 16","sol":true}]}],[{"text":"Quelle est la représentation hexadécimale de l'entier qui s'écrit 106 en base 10 ? ","theme":"A","nume":"4","sujet":4,"annee":2020},{"radio":[{"label":" 6A","sol":true},{"label":" A6"},{"label":" 64 "},{"label":" 46"}]}],[{"text":"Quel est le résultat de l'addition binaire 0010 0110 + 1000 1110 ? ","theme":"A","nume":"5","sujet":4,"annee":2020},{"radio":[{"label":" 1010 1110"},{"label":" 0000 0110"},{"label":" 1011 0100","sol":true},{"label":" 0101 0001"}]}],[{"text":"Combien de bits doit-on utiliser au minimum pour représenter en base 2 le nombre entier 72 ?","theme":"A","nume":"6","sujet":4,"annee":2020},{"radio":[{"label":"2 "},{"label":"6 "},{"label":"7 ","sol":true},{"label":"8","sol":false}]}],[{"text":"Le résultat de la soustraction en binaire 101001 - 101 est égal au nombre binaire :","theme":"A","nume":"1","sujet":5,"annee":2020},{"radio":[{"label":" 100000"},{"label":" 101110"},{"label":" 100100","sol":true},{"label":" 100110"}]}],[{"text":"Quelle est l'écriture décimale de l'entier positif dont l'écriture hexadécimale (en base 16) est 3F ? ","theme":"A","nume":"2","sujet":5,"annee":2020},{"radio":[{"label":" 18"},{"label":" 45"},{"label":" 63","sol":true},{"label":" 315"}]}],[{"text":"Quel est l'entier relatif codé en complément à 2 sur un octet par le code 1111 1111 ? ","theme":"A","nume":"3","sujet":5,"annee":2020},{"radio":[{"label":" – 128"},{"label":" – 127","sol":false},{"label":"–1 ","sol":true},{"label":" 255"}]}],[{"text":"Quelle est, en écriture décimale, la somme d'entiers dont l'écriture en base 16 (hexadécimale) est 2A + 2 ? ","theme":"A","nume":"4","sujet":5,"annee":2020},{"radio":[{"label":" 22"},{"label":" 31"},{"label":" 49 "},{"label":" 44","sol":true}]}],[{"text":"Laquelle de ces affirmations concernant le codage UTF-8 des caractères est vraie ?","theme":"A","nume":"6","sujet":5,"annee":2020},{"radio":[{"label":" le codage UTF-8 est sur 7 bits"},{"label":" le codage UTF-8 est sur 8 bits"},{"label":" le codage UTF-8 est sur 1 à 4 octets","sol":true},{"label":" le codage UTF-8 est sur 8 octets"}]}],[{"text":"Soit 𝑛 l'entier dont la représentation binaire en complément à deux codée sur 8 bits est 0110 1110. Quelle est la représentation binaire de −𝑛 ?","theme":"A","nume":"1","sujet":6,"annee":2020},{"radio":[{"label":" 0001 0001"},{"label":" 0001 0010"},{"label":" 1001 0001","sol":false},{"label":" 1001 0010","sol":true}]}],[{"text":"À quoi sert le codage en complément à 2 ?","theme":"A","nume":"3","sujet":6,"annee":2020},{"radio":[{"label":" à inverser un nombre binaire"},{"label":" à coder des nombres entiers négatifs en binaire","sol":true},{"label":" à convertir un nombre en hexadécimal"},{"label":" à multiplier par 2 un nombre en binaire"}]}],[{"text":"Quel est le plus grand entier positif que l'on peut coder sur un mot de 16 bits ?","theme":"A","nume":"1","sujet":7,"annee":2020},{"radio":[{"label":" 2¹⁵−1=32767"},{"label":" 2¹⁵ = 32768"},{"label":" 2¹⁶−1=65535","sol":true},{"label":" 2¹⁶ = 65536"}]}],[{"text":"Combien de bits sont nécessaires pour représenter 15 en binaire ?","theme":"A","nume":"2","sujet":7,"annee":2020},{"radio":[{"label":"2 "},{"label":"3 "},{"label":"4 ","sol":true},{"label":"5"}]}],[{"text":"Deux entiers positifs ont pour écriture en base 16 : A7 et 84. Quelle est l'écriture en base 16 de leur somme ?","theme":"A","nume":"4","sujet":7,"annee":2020},{"radio":[{"label":" 1811"},{"label":" 12B"},{"label":" 13A","sol":true},{"label":" A784"}]}],[{"text":"Quelle est la valeur de l’entier négatif –42 codé en complément à deux sur un octet (8 bits) ?","theme":"A","nume":"6","sujet":7,"annee":2020},{"radio":[{"label":" –0010 1010"},{"label":" 0010 1010"},{"label":" 1101 0101"},{"label":" 1101 0110","sol":true}]}],[{"text":"Parmi les caractères ci-dessous, lequel ne fait pas partie du code ASCII ?","theme":"A","nume":"2","sujet":8,"annee":2020},{"radio":[{"label":"a "},{"label":"B "},{"label":"@ "},{"label":"é","sol":true}]}],[{"text":"Quelle est l'écriture en hexadécimal (base 16) du nombre entier positif qui s'écrit 1110 1101 en base 2 ? ","theme":"A","nume":"3","sujet":8,"annee":2020},{"radio":[{"label":" DE"},{"label":" ED","sol":true},{"label":" EDF"},{"label":" FEFD"}]}],[{"text":"Que peut-on dire du programme Python suivant de calcul sur les nombres flottants ?
x = 1.0
while x != 0.0:
x = x - 0.1","theme":"A","nume":"1","sujet":9,"annee":2020},{"radio":[{"label":" l'exécution peut ne pas s'arrêter, si la variable x n'est jamais exactement égale à 0.0","sol":true},{"label":" à la fin de l'exécution, x vaut – 0.00001"},{"label":" à la fin de l'exécution, x vaut 0.00001"},{"label":" l'exécution s'arrête sur une erreur FloatingPointError"}]}],[{"text":"Combien de bits faut-il au minimum pour coder le nombre décimal 4085 ?","theme":"A","nume":"1","sujet":10,"annee":2020},{"radio":[{"label":"4"},{"label":" 12","sol":true},{"label":" 2042"},{"label":" 2043"}]}],[{"text":"Quelle est la représentation binaire du nombre entier 173 ?","theme":"A","nume":"3","sujet":10,"annee":2020},{"radio":[{"label":" 1010 1101","sol":true},{"label":" 1011 0101"},{"label":" 1011 0100"},{"label":" 1011 1101"}]}],[{"text":"Quelle est l'écriture décimale du nombre qui s'écrit 11,0101 en binaire ?","theme":"A","nume":"5","sujet":10,"annee":2020},{"radio":[{"label":"3"},{"label":" 3,0101"},{"label":" 3,05"},{"label":" 3,3125","sol":true}]}],[{"text":"Quelle est l'écriture binaire sur 8 bits en complément à deux de l'entier négatif –108 ?","theme":"A","nume":"6","sujet":10,"annee":2020},{"radio":[{"label":" 1000 1000"},{"label":" 0110 1100"},{"label":" 1001 0100","sol":true},{"label":" 1110 1100"}]}],[{"text":"Combien de nombres entiers positifs peut-on coder en binaire sur 4 bits ?","theme":"A","nume":"3","sujet":11,"annee":2020},{"radio":[{"label":"4"},{"label":" 16","sol":true},{"label":" 64"},{"label":" 256"}]}],[{"text":"La couleur « bleu roi » a pour code RGB (65,105,225), sa représentation en hexadécimal est :","theme":"A","nume":"4","sujet":11,"annee":2020},{"radio":[{"label":" #2852C2"},{"label":" #4169E1","sol":true},{"label":" #33A5C61"},{"label":" #C3T622"}]}],[{"text":"Quel est le nombre minimum de bits qui permet de représenter les 7 couleurs de l'arc-en-ciel ?","theme":"A","nume":"5","sujet":11,"annee":2020},{"radio":[{"label":"2 "},{"label":"3 ","sol":true},{"label":"4 "},{"label":"5"}]}],[{"text":"Quelle est l’écriture décimale de l’entier dont la représentation en binaire non signé est 0001 0101 ? ","theme":"A","nume":"1","sujet":12,"annee":2020},{"radio":[{"label":" 15"},{"label":" 21","sol":true},{"label":" 111"},{"label":" 420"}]}],[{"text":"Combien de bits sont nécessaires pour écrire le nombre entier 16 en base 2 ?","theme":"A","nume":"2","sujet":12,"annee":2020},{"radio":[{"label":"4 "},{"label":"5 ","sol":true},{"label":"6 "},{"label":"7"}]}],[{"text":"Quelle est l'écriture décimale de l'entier positif dont la représentation binaire est 1101 0101 ? ","theme":"A","nume":"3","sujet":12,"annee":2020},{"radio":[{"label":" 135"},{"label":" 213","sol":true},{"label":" 231"},{"label":" -42"}]}],[{"text":"Combien de valeurs entières positives ou nulles un octet peut-il représenter ?","theme":"A","nume":"4","sujet":12,"annee":2020},{"radio":[{"label":"2 "},{"label":"8"},{"label":" 16 "},{"label":" 256","sol":true}]}],[{"text":"L'entier positif 255 se représente en hexadécimal (base 16) par :","theme":"A","nume":"3","sujet":13,"annee":2020},{"radio":[{"label":" 99 "},{"label":" AA "},{"label":" CC "},{"label":" FF","sol":true}]}],[{"text":"Quelle est l'écriture décimale de l'entier qui s'écrit 1010 en binaire ?","theme":"A","nume":"2","sujet":14,"annee":2020},{"radio":[{"label":"5 "},{"label":" 10 ","sol":true},{"label":" 20 "},{"label":" 22"}]}],[{"text":"Quelle est la représentation hexadécimale de l'entier dont la représentation binaire s'écrit : 0100 1001 1101 0011 ?","theme":"A","nume":"1","sujet":15,"annee":2020},{"radio":[{"label":" 18899"},{"label":" 3D94"},{"label":" 49D3","sol":true},{"label":" 93A3"}]}]]

Détails: Écrit par : Richard GAUTHIER; Création : 11 Octobre 2020; Mis à jour : 11 Octobre 2020; Clics : 1375

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 17 Listes chaînées

Devoir sql 2020

1nsi devoir 2 login theme a

1nsi devoir 2 login theme a (2)

1nsi devoir 2 theme a json