Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire.
Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau.
Type Python
Type
Opération
Exemple
Complexité
N’existe pas
Tableau
Accès à un élément
tab[i]
O(1)
Modification d’un élément
tab[i] = x
O(1)
Effacement d’un élément
retire(tab, i)
O(n)
Insertion d’un élément
insere(tab, x, i)
O(n)
Recherche d’un élément
est_dans(tab, x)
O(n)
Info
La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques.
Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.
Pourquoi la recherche d’un élément dans un tableau quelconque (non trié donc) est en O(N) ?
Écrire le prédicat est_dans de spécification :
defest_dans(tab:List[int],n:int)->bool:"""
Recherche si la valeur n est présente au moins une fois
dans le tableau tab.
Algorithme itératif.
"""
Écrire un jeu de tests.
(Facultatif) Écrire le prédicat est_dans_rec de spécification :
defest_dans_rec(tab:List[int],n:int,i:int=0)->bool:"""
Recherche si la valeur n est présente au moins une fois
dans le tableau tab.
Algorithme récursif, i est l'indice de recherche.
"""
Quelle est la complexité des algorithmes précédents en fonction de N, la taille du tableau ?
Réponse
Dans l’algorithme itératif, dans le pire des cas (valeur absente du tableau) N tours de boucle sont effectués.
Dans l’algorithme récursif, N appels récursifs sont effectués.
L’algorithme est donc en O(N).
Pourquoi l’insertion d’un élément dans un tableau est en O(N) ?
Dans cette partie, on imagine que le tableau a cette allure :
1
1
2
3
4
5
vide
vide
vide
Si on introduit, en position 1, la valeur 7. Le tableau est alors :
7
1
1
2
3
4
5
vide
vide
Avertissement
Cette opération n’est possible, sans crainte de perdre des données, que si toutes les cellules du tableau ne contiennent pas des données.
Toute fonction permettant l’insertion de valeurs doit donc avertir un utilisateur dans le cas contraire.
Remarque : Dans le code ci-dessous, les cellules seront considérées vides si elles contiennent la valeur None.
Écrire la fonction insere dont la spécification est :
definsere(tab:List[int],n:int,i:int)->None:"""
Insère la valeur n à l'indice i du tableau tab.
Algorithm itératif et en place.
Lève une exception si le tableau est déjà plein.
HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
l'algorithme se contente de décaler les valeurs vers
la droite.
"""
(Facultatif) Écrire la fonction insere_rec dont la spécification est :
definsere_rec(tab:List[int],n:int,i:int,k:int)->None:"""
Insère la valeur n à l'indice i du tableau tab.
Algorithm récursif et en place. k est l'indice de recherche. Sa première valeur doit être len(tab) - 1.
Lève une exception si le tableau est déjà plein.
HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
l'algorithme se contente de décaler les valeurs vers
la droite.
"""
Quelle est la complexité des algorithmes précédents en fonction de N, la taille du tableau ?
Réponse
Dans le pire des cas (insertion à la première place du tableau), on déplace N−1 valeurs.
L’algorithme est donc en O(N).
Structure de liste chaînée
À retenir
Les listes chaînées constituent une structure de données :
de longueur modifiable ;
plus efficace que les tableaux lorsqu’il s’agit d’ajouter ou de retirer un élément (il n’est pas nécessaire de faire de la place en déplaçant les éléments) ;
qui servira de brique à l’élaboration d’autres structures de données.
À retenir
Une liste chaînée permet de représenter une liste ; chaque élément de cette liste est une cellule contenant :
la valeur de l’élément à stocker ;
l’adresse mémoire de la cellule représentant l’élément suivant.
Remarque : le symbole ⊥ marque la fin de la liste dans les schémas.
Comment implémenter une cellule ?
En langage Python, on peut implémenter une cellule à l’aide d’une classe, de listes ou de tuples.
Définir la classe Cellule dont la spécification est :
classCellule:"""
Implémentation d'une cellule de liste chaînée
de nombres entiers.
Attributs
---------
valeur : int
Valeur à stocker dans la liste
suivante : Cellule
Addresse de la cellule suivante (chaînée)
"""
Info
La dernière cellule d’une liste chaînée devra pointer vers l’objetNonequi représente donc une cellule vide.
Instancier 3 objets c1, c2, c3, de type Cellule, dont les valeurs sont 1, 2, 3.
Tous ces objets sont pour l’instant isolés (ils ne pointent vers aucune autre cellule si ce n’est la cellule vide None).
Créer la liste lst à l’aide de ces trois objets.
Comment aurait-on pu créer la liste lst en une seule instruction ?
Les listes chaînées sont des structures fondamentalement récursives
À retenir
Une liste chaînée est :
soit la liste vide (objet None) ;
soit constituée de son premier élément (objet de type Cellule) et du reste des éléments qui forment aussi une liste.
Une liste chaînée est donc une structure récursive.
Une liste chaînée est-elle forcément homogène
Tout au long de ce document nous allons uniquement envisager des listes chaînées de nombres entiers. Rien n’impose, cependant, à l’attribut valeur de la classe Cellule d’être un entier. Chaque cellule peut même posséder des attributs valeur de type différent. Les listes chaînées peuvent donc être hétérogènes.
Quelques opérations sur les listes chaînées
Avertissement
Le point de vue envisagé dans la suite de ce document est celui de la programmation impérative : nous allons définir des fonctions qui vont modifier la liste chaînée.
Nous créerons une classe enveloppe dans un prochain document, de façon à ce notre liste chaînée ait la même interface qu’une liste Python.
Longueur d’une liste chaînée
Écrire la fonction longueur dont la spécification est :
deflongueur(lst:Cellule)->int:"""
Détermine la longueur de la liste lst.
Algorithme récursif.
"""
Écrire la fonction longueur_iter dont la spécification est :
deflongueur_iter(lst:Cellule)->int:"""
Détermine la longueur de la liste lst.
Algorithme itératif.
"""
Déterminer la complexité du calcul de la longueur d’une liste.
Réponse
On réalise autant d’appels récursifs (ou de tours de boucles qu’il y a d’éléments dans la liste).
La complexité est donc en O(N).
Affichage de tous les éléments d’une liste
Écrire la fonction affichage_elements_liste dont la spécification est :
defaffichage_elements_liste(lst:Cellule)->None:"""
Affiche tous les éléments de la liste lst.
Chaque élément est séparé par une tabulation "\t"
"""
Définir la fonction list_to_str dont la spécification est :
deflist_to_str(lst:Cellule,premier:bool=True)->str:"""
Retourne une chaîne de caractères constituée de toutes
les valeurs, sous la forme : "[valeur1, valeur2, ...]".
premier est positionné à True si la valeur est la première
de la liste et à False pour toutes les autres valeurs.
"""
Valeur du n-ième élément d’une liste
Écrire la fonction n_ieme_element dont la spécification est :
defn_ieme_element(lst:Cellule,i:int)->int:"""
Retourne le n-ième élément de la liste. La convention
suivie est celle de Python, le premier élément ayant
l'indice i = 0.
Algorithme récursif.
Lève une exception si l'indice de la liste est trop grand.
"""
Écrire la fonction n_ieme_element_iter dont la spécification est :
defn_ieme_element_iter(lst:Cellule,i:int)->int:"""
Retourne le n-ième élément de la liste. La convention
suivie est celle de Python, le premier élément ayant
l'indice i = 0.
Algorithme itératif.
Lève une exception si l'indice de la liste est trop grand.
"""
Déterminer la complexité de la recherche du n-ième élément d’une liste.
Réponse
Si l’élément dont on cherche la valeur est le dernier de la liste il est nécessaire de faire N appels récursifs (ou tours de boucles).
Si l’indice est hors des limites, il est ici aussi nécessaire de parcourir toute la liste avant de s’en rendre compte.
L’algorithm est donc en O(N).
Modification de la valeur d’une cellule sans modifier la structure de la liste
Écrire la fonction modifier_n_ieme_element dont la spécification est :
defmodifier_n_ieme_element(lst:Cellule,i:int,valeur:int)->None:"""
Modifie le n-ième élément de la liste. La convention
suivie est celle de Python, le premier élément ayant
l'indice i = 0.
Algorithme récursif.
Lève une exception si l'indice de la liste est trop grand.
"""
Ajout d’une valeur à la fin de la liste
Écrire la fonction ajout_fin_liste dont la spécification est :
defajout_fin_liste(lst:Cellule,valeur:int)->None:"""
Ajout de valeur à la fin de la liste.
La liste lst est modifiée.
Algorithme récursif.
"""
Quelle est la complexité de la fonction ajout_fin_liste ?
Réponse
On doit parcourir toute la liste pour ajouter un élément à la fin. La complexité est donc linéaire.
Ajout d’une valeur au début de la liste
Écrire la fonction ajout_debut_liste dont la spécification est :
defajout_debut_liste(lst:Cellule,valeur:int)->Cellule:"""
Ajout de valeur au début de la liste.
La nouvelle adresse de la tête de liste doit être
retournée.
"""
Quelle est la complexité de cette fonction ?
Réponse
O(1)
Retrait du dernier élément d’une liste
Écrire la fonction retrait_dernier_element dont la spécification est :
defretrait_dernier_element(lst:Cellule)->int:"""
Retire le dernier élément de la liste et le retourne.
Algorithme récursif.
"""
Quelle est la complexité de cette fonction ?
Réponse
Il faut parcourir la liste, donc O(N).
Retrait du premier élément d’une liste
Écrire la fonction retrait_premier_element dont la spécification est :
defretrait_premier_element(lst:Cellule)->tuple[int,Cellule]:"""
Retire le premier élément de la liste et le retourne.
La nouvelle adresse de la tête de liste doit être
retournée.
"""
Quelle est la complexité de cette fonction ?
Réponse
O(1).
Retrait du n-ième élément d’une liste
Écrire la fonction retrait_n_ieme_element dont la spécification est :
defretrait_n_ieme_element(lst:Maillon,i:int)->int:"""
Retire le n-ième élément de la liste lst. La convention
suivie est celle de Python, le premier élément ayant
l'indice i = 0.
Algorithme récursif.
Lève une exception si l'indice de la liste est trop grand,
ne prend pas en charge le retrait du premier élément.
"""
Quelle est la complexité de cette fonction ?
Réponse
Le retrait en lui-même est en O(1) mais il faut arriver jusqu’à la valeur. L’ensemble est donc en O(N).
Concaténation de deux listes
À retenir
On appelle concaténation de deux listes l’opération consistant à mettre bout à bout les deux listes.
Écrire la fonction concatener dont la spécification est :
defconcatener(lst1:Cellule,lst2:Cellule)->Cellule:"""
Concatène les listes lst1 et lst2. Une nouvelle liste est
créée et retournée.
Les éléments de la première liste sont copiés alors que ceux
de la deuxième sont insérés. lst1 et lst2 ne sont donc pas modifiées.
ATTENTION : tout élément de lst partagé avec lst2 modifié l'est aussi
dans lst2.
Algorithme récursif.
"""
Écrire la fonction copie dont la spécification est :
defcopie(lst:Cellule)->Cellule:"""
Réalise une nouvelle copie de la liste lst.
Algorithme récursif.
"""
Se servir de la fonction copie pour écrire la fonction concatener_avec_copie_integrale dont la spécification est :
defconcatener_avec_copie_integrale(lst1:Cellule,lst2:Cellule)->Cellule:"""
Concatène les listes lst1 et lst2. Les éléments des listes lst1 et lst2
sont recopiés pour former une nouvelle liste.
Algorithme récursif.
"""
Quelle est la complexité de la fonction concatener ? Même question pour la fonction concatener_avec_copie_integrale.
Réponse
Dans le premier cas, il est nécessaire de recopier tous les éléments de lst1. La complexité est donc linéaire et dépend du nombre d’élements de lst1.
Dans le second cas, on recopie tous les éléments de lst1 et de lst2. La complexité est donc linéaire et est la somme du nombre d’éléments de lst1 et de lst2.
Renverser une liste
Écrire la fonction renverser dont la spécification est :
defrenverser(lst:Cellule)->Cellule:"""
Retourne une nouvelle liste formée des éléments de lst à l'envers.
Les éléments peuvent avoir été recopiés ou pas.
Algorithme récursif.
"""
Remarque. Cette fonction doit s’appuyer sur les fonctions concatener ou concatener_avec_copie_integrale.
Remarque. Cet algorithme est particulièrement inefficace.
Conclusion
À retenir
Une liste chaînée est une structure de données utile pour représenter une séquence finie d’éléments.
Chaque élément est contenu dans une cellule, qui fournit, en plus de la valeur, un moyen pour accéder à la cellule suivante.
Les éléments d’une liste chaînée ne sont pas situés dans des emplacements contigüs en mémoire.
Les opérations sur les listes chaînées se programment sous la forme de parcours qui suivent ces liaisons, en utilisant la récursivité ou des boucles.
À retenir
Une liste chaînée est un type abstrait de données qui doit, au minimum, fournir les fonctions suivantes :
insère : insère un élément dans la liste ;
supprime : supprime et renvoie l’élément de position spécifié de la liste ;
longueur : renvoie le nombre d’éléments de la liste ;
est_vide : détermine si la liste est vide ou pas ;
nième_élément : retourne la valeur du nième élément depuis le début.
Action
Liste chaînée
Tableau
Tableau dynamique
Accès à un élément
O(n)
O(1)
O(1)
Insertion/suppression du 1er élément
O(1)
O(n) (si place)
O(n)
Insertion à la fin
O(n)
O(1) (si place)
O(1) (si place) O(n) (si pas de place)
Suppression du dernier élément
O(n)
O(1)
O(1)
Insertion/suppression au milieu
O(n)
O(n) (si place)
O(n)
Quelques exemples d’utilisation des listes chaînées
Les logiciels de visualisation d’images utilisent parfois une liste chaînée pour afficher les images précédentes et suivantes à l’aide des boutons « précédent » et « suivant ».
Des navigateurs Web peuvent utiliser une liste chaînée pour accéder aux pages à l’aide des boutons « précédent » et « suivant ».
Les boutons « précédent » et « suivant » des lecteurs de musique peuvent utiliser une liste chaînée doublement/circulaire.
Les tracés et les formes sur le canevas, de MS-Paint sont connectés via une liste chaînée.
Le balayage « gauche/droite » sur Tinder utilise une liste doublement chaînée.
On peut garder la trace des tours dans un jeu multi-joueurs à l’aide d’une liste chaînée circulaire.
Les lignes de code dans un IDE peuvent être enregistrées dans une liste doublement chaînée.
Annexe : Tests possibles pour les fonctions codées
if__name__=="__main__":# c1 = Cellule(1, None)# c2 = Cellule(2, None)# c3 = Cellule(3, None)# lst = c1# lst.suivante = c2# c2.suivante = c3lst=Cellule(1,Cellule(2,Cellule(3,Cellule(4,None))))affichage_elements_liste(lst)assertlongueur(lst)==4assertlongueur_iter(lst)==4assertn_ieme_element(lst,0)==1assertn_ieme_element(lst,3)==4# print(n_ieme_element(lst, 4))assertn_ieme_element_iter(lst,0)==1assertn_ieme_element_iter(lst,3)==4# print(n_ieme_element_iter(lst, 4))lst1=Cellule(1,Cellule(2,Cellule(3,Cellule(4,None))))lst2=Cellule(5,Cellule(6,Cellule(7,None)))lst3=concatener_avec_copie_integrale(lst1,lst2)print(lst3)print(list_to_str(lst3))# Modification de la listemodifier_n_ieme_element(lst,0,12)assertn_ieme_element_iter(lst,0)==12# Ajout en fin de listeajout_fin_liste(lst,Cellule(25,None))affichage_elements_liste(lst)print(list_to_str(lst))# Ajout en début de listelst=ajout_debut_liste(lst,Cellule(34,None))affichage_elements_liste(lst)# Retrait dernier élémentdernier=retrait_dernier_element(lst)print(dernier)affichage_elements_liste(lst)
Implémentation du type abstrait Liste Chaînée à l'aide de listes Python
Reprendre toutes les fonctions des sections 2 et 3 du document 1 de ce chapitre, en implémentant cette fois le type abstrait « Liste chaînée » à l’aide de tuples (à la place de la classe).
Réponse
defest_dans(tab:list[int],val:int)->bool:"""
Recherche la présence de val dans tab.
"""trouve=Falsei=0whilei<len(tab)andnottrouve:ifval==tab[i]:trouve=Truei+=1returntrouvedefest_dans_rec(tab:list[int],n:int,i:int=0)->bool:"""
Recherche si la valeur n est présente au moins une fois
dans le tableau tab.
Algorithme récursif, i est l'indice de recherche.
"""ifi==len(tab):returnFalseeliftab[i]==n:returnTrueelse:returnest_dans_rec(tab,n,i+1)definsere(tab:list[int],n:int,i:int)->None:"""
Insère la valeur n à l'indice i du tableau tab.
Algorithm itératif et en place.
Lève une exception si le tableau est déjà plein.
HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
l'algorithme se contente de décaler les valeurs vers
la droite.
"""dernier_indice=len(tab)-1iftab[dernier_indice]!=None:raiseException("Tableau plein !")k=dernier_indicewhilek>i:tab[k]=tab[k-1]k-=1# for k in range(dernier_indice, i, -1):# tab[k] = tab[k - 1]tab[i]=ndefinsere_rec(tab:list[int],n:int,i:int,k:int)->None:"""
Insère la valeur n à l'indice i du tableau tab.
Algorithm récursif et en place. k est l'indice de
recherche.
Sa première valeur doit être len(tab) - 1.
Lève une exception si le tableau est déjà plein.
HYPOTHÈSE : la gestion des "trous" n'est pas
assurée, l'algorithme se contente de décaler
les valeurs vers la droite.
"""dernier_indice=len(tab)-1iftab[dernier_indice]!=Noneandk==dernier_indice:raiseException("Tableau plein !")elifk==i:tab[i]=nreturnNoneelse:tab[k]=tab[k-1]returninsere_rec(tab,n,i,k-1)if__name__=="__main__":tab=[iforiinrange(20)]assertest_dans(tab,12)==Trueassertest_dans(tab,0)==Trueassertest_dans(tab,20)==Falseassertest_dans_rec(tab,12)==Trueassertest_dans_rec(tab,0)==Trueassertest_dans_rec(tab,20)==Falseprint("Insertion itérative")tab=[1,1,2,3,4,5,None,None,None]print(tab)insere(tab,7,0)print(tab)insere(tab,7,0)print(tab)insere(tab,7,0)print(tab)# insere(tab, 7, 0)# print(tab)print()print("Insertion récursive")tab=[1,1,2,3,4,5,None,None,None]print(tab)insere_rec(tab,7,0,len(tab)-1)print(tab)insere_rec(tab,7,0,len(tab)-1)print(tab)insere_rec(tab,7,0,len(tab))print(tab)
Par transformation des fonctions du document 1 dans ce chapitre en méthodes, écrire le code de la classe Liste qui définit le type abstrait « Liste chaînée ».
Réponse
from__future__importannotationsclassMaillon:"""
Un maillon de la liste.
"""def__init__(self:Maillon,valeur:int,suivant:Maillon=None)->None:self.valeur=valeurself.suivant=suivantclassListe:"""
Implémentation de la classe liste.
"""def__init__(self:Liste,valeur:int=None)->None:"""
Initialisation de l'objet. Il est possible de créer une liste
vide ou une liste contenant un élément.
Il est possible de créer directemnt une liste contenant plusieurs
éléments il faut utiliser une fonctionnalité de Python que vous
ne connaissez pas forcément et qui n'est pas au programme.
"""ifvaleurisNone:self.maillons=Noneelse:self.maillons=Maillon(valeur)defest_vide(self:Liste)->bool:"""Détermine si la liste est vide."""returnself.maillonsisNonedef__len__(self:Liste)->int:"""Retourne le nombre d'éléments dans la liste."""ifself.est_vide():return0else:nbre=0maillon=self.maillonswhilemaillonisnotNone:nbre+=1maillon=maillon.suivantreturnnbredefappend(self:Liste,valeur:int)->None:"""
Ajoute valeur à la fin de la liste.
"""ifself.est_vide():self.maillons=Maillon(valeur)else:maillon=self.maillonswhilemaillon.suivantisnotNone:maillon=maillon.suivantmaillon.suivant=Maillon(valeur)defappend_first(self:Liste,valeur:int)->None:"""
Ajoute valeur au début de la liste.
"""maillon=Maillon(valeur)maillon.suivant=self.maillonsself.maillons=maillondefpop(self:Liste)->int:"""
Retire le dernier élément de la liste et le retourne.
Lève une erreur si la liste est vide.
"""ifself.est_vide():# Liste videraiseException("La liste est vide !")maillon=self.maillonsifmaillon.suivantisNone:# Cas d'une liste à un élémentvaleur=maillon.valeurself.maillons=Nonereturnvaleurelse:whilemaillon.suivant.suivantisnotNone:# Cas généralmaillon=maillon.suivantvaleur=maillon.suivant.valeurmaillon.suivant=Nonereturnvaleurdefpop_first(self:Liste)->int:"""
Retire le premier élément de la liste et le retourne.
Lève une erreur si la liste est vide.
"""ifself.est_vide():# Liste videraiseException("La liste est vide !")valeur=self.maillons.valeurself.maillons=self.maillons.suivantreturnvaleurdef__getitem__(self:Liste,i:int)->int:"""
Redéfinition de la fonction d'accès à l'élément d'indice i.
"""ifself.est_vide():raiseException("La liste est vide !")maillon=self.maillonsj=0whilej<i:ifmaillonisNone:raiseIndexError("Indice hors des limites !")maillon=maillon.suivantj+=1returnmaillon.valeurdef__str__(self:Liste)->str:"""
Représentation de la liste sous-forme d'une chaîne de caractères.
"""rep="["maillon=self.maillonswhilemaillonisnotNone:rep+=str(maillon.valeur)ifmaillon.suivantisnotNone:rep+=", "maillon=maillon.suivantrep+="]"returnrep