Données Liste Implémentation

Identification

Infoforall

12 - Implémenter une Liste 1/3


Aujourd'hui, nous allons implémenter une Liste Récursive (Tête, Queue) sous forme d'une structure de donnée nommée Liste Chaînée.

Serpent Tête et Queue
Image libre de droit

Version du vocabulaire utilisé ici :

  • Type abstrait de données : une idée abstraite mais précise de la façon de traiter les données. On trouve souvent l'acronyme TAD
  • Type : l'implémentation en machine d'une donnée. Cela regroupe donc les types simples et les types construits.
  • Type simple : l'implémentation en machine d'une donnée unique, comme un entier, un flottant...
  • Type structuré, type construit : l'implémentation en machine d'une donnée se comportant comme un conteneur : elle contient d'autres données.
  • D'où le nom de la fonction native Python type().

  • Une structure de données est le nom qu'on donne à l'ensemble d'un type associé aux fonctions qu'on peut appliquer aux données stockées.
  • TETE : la première Place d'une Liste.
  • QUEUE : l'ensemble des autres Places d'une Liste.
  • FIN : la dernière Place d'une Liste.

Prerequis : l'activité sur les Listes.

Documents de cours : open document ou pdf

1 - Liste chainée sous forme de tuples

Implémentation correcte ?

Pour que l'implémentation soit qualifiée de "correcte", il faut que ces opérations primitives aient un coût faible.

1.1 - La structure Liste Chaînée : un ensemble de Cellules reliées entre elles

Une bonne manière d'implémenter une Liste Récursive est d'utiliser à l'interne une Liste Chaînée : les Places sont des Cellules sans numéro mais reliées entre elles.

Une Cellule contient au moins deux informations :

  1. L'Elément que la Cellule stocke
  2. La référence du successeur : la Cellule suivante dans la Liste Chainée
Cellule (25) qui mène à une Cellule (15) qui mène à une Cellule (5)
  • La Tête est ici la Cellule contenant 25.
  • La Queue est la Liste Chaînée qui commence par le Cellule contenant 15. La Queue est bien une Liste Chaînée, dont la Tête est la Cellule contenant 15.
  • La Fin est la Cellule contenant 5.
1.2 La Liste Chaînée sous forme d'un tuple

De façon à obtenir facilement une structure immuable, nous décidons de partir sur la manipulation de tuples qui possèdent justement cette propriété dans Python.

Liste Vide

On fait le choix de représenter une Liste Vide par un tuple vide ().

>>> liste_vide = ()

Cellule (Elément de Tête, Queue)

On implémente chaque Cellule comme un tuple (Elément de tête, Successeur).

Cellule = (Element, Successeur)

Une Cellule c contient deux informations :

  • c[0] : l'Elément stocké,
  • c[1] : le Successeur qui peut être soit une Liste Vide, soit une Cellule

Exemple avec la Cellule a qui contient 5 et n'a pas de successeur.

>>> a = (5, liste_vide) >>> a (5, ())

Rajouter une Tête est donc facile. Exemple : rajoutons une Cellule b qui contient 15 et dont le successeur est la Cellule a.

>>> b = (15, a) >>> b (15, (5, ()))

Rajoutons une Cellule c qui contient 25 et dont le successeur est la Cellule b.

>>> c = (25, b) >>> c (25, (15, (5, ())))
Cellule (25) qui mène à une Cellule (15) qui mène à une Cellule (5)

Connaissant la localisation mémoire de la Cellule c, il est assez facile de trouver son contenu (25 pour c) et de trouver son successeur (b pour c) :

>>> c (25, (15, (5, ()))) >>> c[0] 25 >>> c[1] (15, (5, ()))

On voit assez facilement que supprimer une Tête ou récupérer une Queue est facile : il suffit de récupérer l'indice 1 de la Cellule de Tête.

>>> c (25, (15, (5, ()))) >>> lst = c[1] >>> lst (15, (5, ()))

On voit que la queue qu'on récupère est donc simplement une référence vers la Cellule de tête d'avant, b.

Liste Chaînée ; une simple référence vers la Cellule de Tête ?

Presque car il y a une autre possibilité.

Dans notre implémentation Tête-Queue, une Liste est :

  1. soit une référence vers une Liste Vide, le tuple ().
  2. soit une référence vers la Cellule de Tête, un tuple (Element, Successeur)

On pourait donc écrire ceci :

>>> lst1 = c

Vous allons maintenant réaliser une implémentation de cette structure de données.

Une fois que les 7 opérations primitives auront été créées, nous compléteront l'interface de façon à offrir les fonctions manquantes pour permettre de qualifier cette structure de données de Liste.

Nous aurons alors un beau module qui nous permettra d'utiliser des Listes Chaînées et donc de pouvoir programmer facilement les algorithmes qui sont décrits en manipulant une Liste Récursive.

Le MODULE PRIMITIVES de la liste_chainee_tq de ce TP

Voici le module non finalisé implémentant une Liste Chaînée sous forme de tuples (vide ou couple (Elément de Tête, Queue)).

On notera que premier() n'est pas vraiment une primitive mais un raccourci bien pratique.

Pour l'instant, la plupart des fonctions ne contiennent que l'instruction pass.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
'''INTERFACE d'une structure de données Liste Chaînée Description des types non natifs utilisés dans les fonctions + Element : le type des éléments disponibles dans votre Liste si elle est homogène. + Cellule : la référence d'un conteneur (Element, Cellule suivante). + Liste : la référence de la Cellule de la Tête ou d'une Liste Vide. Opérations primitives de la Liste Chaînée + nouvelleListe() -> Liste + estListeVide(lst:'Liste') -> bool + insererTete(lst:'Liste', elt:'Element') -> 'Liste' + supprimerTete(lst:'Liste Non Vide') -> 'Liste' + accesTete(lst:'Liste Non Vide') -> 'Cellule' + contenu(c:'Cellule') -> 'Element' + successeur(c:'Cellule Non Finale') -> 'Cellule' + premier(lst:'Liste Non Vide') -> 'Element' ''' # Importation : aucune # Déclaration des CONSTANTES : aucune # Déclaration des fonctions de la première partie def nouvelleListe() -> 'Liste': '''Renvoie une liste vide''' return () def estListeVide(lst:'Liste') -> bool: '''Prédicat qui renvoie True si la liste est vide''' return lst == () def insererTete(lst:'Liste', elt:'Element') -> 'Liste': '''Renvoie une nouvelle liste où elt est la Tête menant à lst devenue la queue''' pass def supprimerTete(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une liste obtenue en supprimant la tête de la liste NON VIDE lst''' pass def accesTete(lst:'Liste Non Vide') -> 'Cellule': '''Renvoie la Cellule de Tête de la liste NON VIDE lst''' pass def contenu(c:'Cellule') -> 'Element': '''Renvoie le contenu de la cellule''' pass def successeur(c:'Cellule Non Finale') -> 'Cellule': '''Renvoie la cellule qui succède à c, c NE DOIT PAS être la DERNIERE Cellule de la liste''' pass def premier(lst:'Liste Non Vide') -> 'Element': '''Renvoie le contenu de la tête de la liste NON VIDE lst''' pass def representerListe(lst:'Liste') -> str: '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête''' reponse = [] while not estListeVide(lst): valeur_tete = premier(lst) reponse.append(valeur_tete) lst = supprimerTete(lst) return str(reponse).replace(',',' -> ').replace('[','').replace(']','') # Instructions du programme principal if __name__ == '__main__': # Ces fonctions ne seront en mémoire qu'en lancement direct def tester_insererTete(): a = nouvelleListe() a = insererTete(a, 5) assert a == (5, ()) a = insererTete(a, 2) assert a == (2, (5, ())) b = insererTete(a, 20) assert a == (2, (5, ())) assert b == (20, (2, (5, ()))) print('Test OK pour insererTete()') def tester_supprimerTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) b = supprimerTete(a) assert a == (2, (5, ())) assert b == (5, ()) c = supprimerTete(b) assert estListeVide(c) print('Test OK pour supprimerTete()') def tester_accesTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) assert accesTete(a) == a print('Test OK pour accesTete()') def tester_contenu(): a = nouvelleListe() a = insererTete(a, 5) b = insererTete(a, 2) assert contenu(accesTete(a)) == 5 assert contenu(accesTete(b)) == 2 print('Test OK pour contenu()') def tester_successeur(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = insererTete(c, 20) assert successeur(accesTete(d)) == c assert successeur(accesTete(c)) == b print('Test OK pour successeur()') def tester_p1(): # Tous les tests de la partie 1 tester_insererTete() tester_supprimerTete() tester_accesTete() tester_contenu() tester_successeur() print("Module lancé directement, il ne s'agit pas d'une importation")

01° Enregistrer ce module en le nommant bien liste_chainee_tq.py, sans accent attention. Lancer le module directement.

>>> a = () >>> estListeVide(a) ??? >>> b = nouvelleListe() >>> estListeVide(b) ???

Questions

  1. Que vont renvoyer ces instructions ?
  2. Quelle est la seule proposition qui utilise bien l'interface proposée plutôt que de manipuler directement l'implémentation de la liste (la documentation se trouve en début de module, voir les lignes 8 à 16) ?
  3. L'utilisateur d'un module est-il sensé savoir comment les données sont réellement implémentées ?

...CORRECTION...

Question 1

>>> a = () >>> estListeVide(a) True >>> b = nouvelleListe() >>> estListeVide(b) True

Question 2

Seule b respecte l'interface : avec a crée une liste sans passer par la fonction d'interface nouvelleListe(). Cette manipulation directe implique qu'on manipule directement les données.

Question 3

L'utilisateur n'est pas sensé manipuler les données internes du module : il doit utiliser uniquement les fonctions d'interface qu'on lui a fourni. De cette façon, ses programmes resteront fonctionnels même si les créateurs du module changent légèrement la gestion interne après une mise à jour.

02° Modifier la fonction d'interface insererTete() qui ne répond pas ce qu'il faut pour le moment.

Prototype

def insererTete(lst:'Liste', elt:'Element') -> 'Liste':

Exemple d'utilisation :

>>> a = nouvelleListe() >>> a () >>> a = insererTete(a, 5) >>> a (5, ()) >>> a = insererTete(a, 2) >>> a (2, (5, ()))

AIDE : il suffit de renvoyer un nouveau tuple dont

  • L'élément de tête est notre elt et
  • Le successeur est l'ancien tuple lst qui pointe bien vers l'ancienne cellule de tête.

Vous pourrez tester votre résultat en activant la fonction de tests intégrée au module :

>>> tester_insererTete()

Historiquement, dans LISP cette fonction se nomme cons() (comme _cons_truct) lorsqu'elle insère bien le nouvelle élément en tant que nouvelle tête.

...CORRECTION...

1 2 3
def insererTete(lst:'Liste', elt:'Element') -> 'Liste': '''Renvoie une nouvelle liste où elt est la Tête menant à lst devenue la queue''' return (elt, lst)

On remarquera que le fait de taper a dans la console permet de visualiser le contenu réel de notre liste. Il faudrait donc créer une fonction d'interface permettant de montrer le contenu de la liste à l'utilisateur sans qu'il sache qu'elle est stockée dans des tuples. Nous allons le faire à la question 5.

03° Modifier la fonction d'interface supprimerTete() qui ne renvoie pas la réponse attendue pour le moment.

Prototype

def supprimerTete(lst:'Liste Non Vide') -> 'Liste':

supprimerTete(lst:Liste) -> Liste
Renvoie une nouvelle liste où la tête est maintenant le deuxième élément (la tête de la queue précédente !).

Précondition : lst est une liste NON VIDE. Inutile donc gérer les cas où on vous envoie une liste vide, ou pire : un truc qui n'est pas une liste. Ce n'est pas votre problème en tant que concepteur de cette fonction.

Voici quelques exemples d'utilisation :

>>> a = nouvelleListe() >>> a = insererTete(nouvelleListe(), 5) >>> a (5, ()) >>> b = supprimerTete(a) >>> b ()
>>> a = (20, (15, (5, ()))) >>> a (20, (15, (5, ()))) >>> b = supprimerTete(a) >>> b (15, (5, ())) >>> a (20, (15, (5, ())))

AIDE : on aurait pu nommer cette fonction recupererQueue() puisque c'est ce qu'elle fait.

Fonction de test

>>> tester_supprimerTete()

...CORRECTION...

1 2 3
def supprimerTete(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une liste obtenue en supprimant la tête de la liste NON VIDE lst''' return lst[1]

04° Passons aux fonctions manipulant les Cellules.

  1. Expliquer pourquoi, dans cette implémentation, la fonction accesTete() renvoie effectivement la Cellule de Tête avec l'instruction return lst.
  2. Modifier la fonction d'interface contenu() pour qu'elle renvoie bien l'élément contenu dans la Cellule c qu'on lui fournit.
  3. Modifier la fonction d'interface successeur() pour qu'elle renvoie bien le successeur Cellule de la Cellule c qu'on lui fournit. Attention à la précondtion : la Cellule envoyée DOIT avoir un vrai Successeur. Ce n'est pas à vous de gérer le cas où la Cellule qu'on vous transmet est la dernière et que son successeur est vide. C'est une précondition. C'est donc à l'utilisateur de vérifier.
39 40 41 42 43 44 45 46 47 48 49
def accesTete(lst:'Liste Non Vide') -> 'Cellule': '''Renvoie la Cellule de Tête de la liste NON VIDE lst''' return lst def contenu(c:'Cellule') -> 'Element': '''Renvoie le contenu de la cellule''' pass def successeur(c:'Cellule Non Finale') -> 'Cellule': '''Renvoie la cellule qui succède à c, c NE DOIT PAS être la DERNIERE Cellule de la liste''' pass

Fonctions de test

>>> tester_accesTete() >>> tester_contenu() >>> tester_successeur()

...CORRECTION...

Question 1

Dans cette implémentation, nous avions remarqué qu'une Liste Non Vide n'est finalement qu'une référence vers une Cellule.

La liste n'est donc qu'un alias pour désigner la Cellule de Tête.

Questions 2-3

39 40 41 42 43 44 45 46 47 48 49
def accesTete(lst:'Liste Non Vide') -> 'Cellule': '''Renvoie la Cellule de Tête de la liste NON VIDE lst''' return lst def contenu(c:'Cellule') -> 'Element': '''Renvoie le contenu de la cellule''' return c[0] # une Cellule est le couple (Element, Successeur) def successeur(c:'Cellule Non Finale') -> 'Cellule': '''Renvoie la cellule qui succède à c, c NE DOIT PAS être la DERNIERE Cellule de la liste''' return c[1] # une Cellule est le couple (Element, Successeur)

05-A° Il est assez pénible d'accéder à la valeur stockée dans la Cellule de Tête pour l'instant : il faut d'abord utiliser la fonction accesTete() puis utiliser contenu().

recup = contenu(accesTete(lst))

Réaliser la fonction premier() qui renvoie directement l'élément stocké en Tête d'une Liste NON VIDE. On vous demande ici de manipuler directement l'implémentation sans passer par les autres opérations primitives.

Prototype

def premier(lst:'Liste Non Vide') -> 'Element':

premier(lst:Liste) -> Element
Renvoie la tête de la liste lst.

PRECONDITION : La Liste ne doit pas être vide.

Exemple d'utilisation

>>> a = insererTete(nouvelleListe(), 5) >>> a = insererTete(a, 15) >>> premier(a) 15 >>> b = nouvelleListe() >>> premier(b) IndexError: tuple index out of range

...CORRECTION...

1 2 3
def premier(lst:'Liste Non Vide') -> 'Element': '''Renvoie le contenu de la tête de la liste NON VIDE lst''' return lst[0] # manipulation directe de l'implémentation

05-B° Même question, mais cette fois, on vous demande de réaliser une version qui n'utilise que les autres opérations primitives déjà réalisées : vous devrez manipuler directement le tuple (élément, successeur).

...CORRECTION...

1 2 3
def premier(lst:'Liste Non Vide') -> 'Element': '''Renvoie le contenu de la tête de la liste NON VIDE lst''' return contenu(accesTete(lst)) # utilisation des opérations primitives

05-C° On considère que l'implémentation Python des tuples permet de lire un tuple ou une case de tuple à coût constant.

  1. Quel est le coût de nouvelleListe() ?
  2. Quel est le coût de estListeVide() ?
  3. Quel est le coût de insererTete() ?
  4. Quel est le coût de supprimerTete() ?
  5. Quel est le coût de accesTete() ?
  6. Quel est le coût de contenu() ?
  7. Quel est le coût de successeur() ?
  8. Quel est le coût de premier() version 5A ?
  9. Quel est le coût de premier() version 5B ?
  10. Quelle est la version de premier() à privilégier ?

...CORRECTION...

  1. Quel est le coût de nouvelleListe() ?
  2. On renvoie juste un tuple. Le coût est donc constant.

  3. Quel est le coût de estListeVide() ?
  4. On lit un tuple (coût constant), on lit le tuple vide (coût constant), on effectue une comparaison (coût constant).

    On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 3 opérations basiques).

  5. Quel est le coût de insererTete() ?
  6. On lit la variable elt (coût constant), on lit la variable lst (coût constant), on génère un couple en fournissant les deux valeurs précédentes (coût constant).

    On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 3 opérations basiques).

  7. Quel est le coût de supprimerTete() ?
  8. On lit la variable lst (coût constant), et on accède à son indice 0 (coût constant).

    On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).

  9. Quel est le coût de accesTete() ?
  10. On lit juste la variable lst (coût constant).

  11. Quel est le coût de contenu() ?
  12. On lit la variable lst (coût constant), et on accède à son indice 0 (coût constant).

    On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).

  13. Quel est le coût de successeur() ?
  14. On lit la variable lst (coût constant), et on accède à son indice 1 (coût constant).

    On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).

  15. Quel est le coût de premier() version 5A ?
  16. On lit la variable lst (coût constant), et on accède à son indice 0 (coût constant).

    On obtient donc un coût constant (quelque soit la taille de la Liste, on aura toujours juste ces 2 opérations basiques).

  17. Quel est le coût de premier() version 5B ?
  18. On utilise l'opération primitive accesTete() (coût constant) puis à l'opération primitive contenu (coût constant).

    On obtient donc un coût constant.

  19. Quelle est la version de premier() à privilégier ?
  20. Puisque les deux fonctions ont le même coût, on préférera clairement la version qui manipule juste les opérations primitives puisqu'on ne manipule pas directement les données internes. On passe par des fonctions qui le font à notre place.

Il nous manque encore une chose qui pourrait être pratique mais qui ne fait pas partie de l'interface obligatoire : de quoi représenter la liste sans montrer son implémentation mémoire réelle. Il s'agit donc d'une fonction faisant partie de l'IHM (Interface Homme Machine).

Nous aimerions afficher '10 -> 15 -> 5' plutôt que de montrer le contenu réel (10, (15, (5, ()))) par exemple.

06° Placer cette fonction representerListe() parmi vos fonctions d'interface.

1 2 3 4 5 6 7 8
def representerListe(lst:'Liste') -> str: '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête''' reponse = [] while not estListeVide(lst): valeur_tete = premier(lst) reponse.append(valeur_tete) lst = supprimerTete(lst) return str(reponse).replace(',',' -> ').replace('[','').replace(']','')

Elle renvoie un string représentant le contenu interne de la Liste de façon totalement arbitraire : le contenu affiché n'a rien à voir avec le contenu réel (des tuples dans des tuples).

Utiliser les instructions suivantes :

>>> a = insererTete(insererTete(insererTete(nouvelleListe(), 5), 15), 20) >>> representerListe(a) '20 -> 15 -> 5'

Question : un utilisateur peut-il avoir une idée de l'implémentation interne de notre Liste en utilisant nos fonctions d'interface ?

...CORRECTION...

Non. C'est même le principe fondamental de l'interfaçage : quelque soit l'implémentation interne, l'utilisateur doit pouvoir utiliser les fonctions d'interface pour obtenir les mêmes effets. L'utilisateur ne doit donc pas avoir besoin de connaître l'implémentation interne pour manipuler ses données. Il doit juste utiliser les fonctions d'interface qu'on lui fournit, qui ont certainement étaient optimisées pour gérer ce type de données.

Attention : notre fonction d'affichage ne parviendra donc pas à gérer correctement les listes contenant des strings contenant des crochets [ et ] puisqu'elle les supprime de l'affichage.

Si vous voulez gérer des contenus de ce type, il faudra modifier la fonction.

Notre implémentation a deux avantages manifestes :

  1. Implémentation légère : pas de choses compliquées. Il faut se souvenir que l'ordre des qualités d'un programme est souvent : d'abord de marcher, ensuite d'être clair, et finalement d'être performant.
  2. Implémentation qui colle au plus près de la notion de Tête -> Queue.

2 - Création des autres opérations primitives

Nous allons maintenant voir que cette implémentation présente en réalite quelques désavantages.

Tentons de créer maintenant les autres opérations importantes du type Liste :

  • On veut une fonction longueur()
  • On veut une fonction inserer() pour insérer en tant que Cellule d'indice i
  • On veut une fonction supprimer() pour supprimer la Cellule d'indice i
  • On veut une fonction acces() pour accéder à la Cellule d'indice i
MODULE version 2

Voici le programme que vous allez utiliser sur cette deuxième partie : il contient les corrections de la partie 1 ainsi que les fonctions et fonctions de test de la partie 2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
'''INTERFACE du type Liste Chaînée basée sur des tuples : () ou (tete, queue) Description des types non natifs -------------------------------- Element : le type des éléments disponibles dans votre Liste si elle est homogène. Cellule : la référence d'un conteneur (Element, Cellule suivante). Liste : la référence de la Cellule de la Tête ou d'une Liste Vide. Opérations primitives de la Liste Chainée ------------------------------------------------------- + nouvelleListe() -> Liste + estListeVide(lst:'Liste') -> bool + insererTete(elt:'Element', lst:'Liste') -> 'Liste' + supprimerTete(lst:'Liste Non Vide') -> 'Liste' + accesTete(lst:'Liste Non Vide') -> 'Cellule' + contenu(cellule:'Cellule') -> 'Element' + successeur(cell:'Cellule') -> 'Cellule' + premier(lst:'Liste Non Vide') -> 'Element' Fonctions d'interface supplémentaires ------------------------------------- + aSuccesseur(lst:'Liste') -> bool + longueur(lst:'Liste') -> int + acces(lst:'Liste Non Vide', i:int) -> 'Cellule' + ieme(lst:'Liste Non Vide', i:int) -> 'Element' + inserer(elt:'Element', lst:'Liste', i:int) -> 'Liste' + supprimer(lst:'Liste Non Vide', i:int) -> 'Liste' + concatener(gauche:'Liste', droite:'Liste') -> 'Liste' + rechercher(lst1:'Liste', elt:'Element') -> int ''' # Importations # CONSTANTES # Déclaration des fonctions de la première partie def nouvelleListe() -> 'Liste': # cout constant '''Renvoie une liste vide''' return () def estListeVide(lst:'Liste') -> bool: # cout constant '''Prédicat qui renvoie True si la liste est vide''' return lst == () def insererTete(lst:'Liste', elt:'Element') -> 'Liste': # cout constant '''Renvoie une nouvelle liste où elt est la Tête menant à lst devenue la queue''' return (elt, lst) def supprimerTete(lst:'Liste Non Vide') -> 'Liste': # cout constant '''Renvoie une liste obtenue en supprimant la tête de la liste NON VIDE lst''' return lst[1] def accesTete(lst:'Liste Non Vide') -> 'Cellule': # cout constant '''Renvoie la Cellule de Tête de la liste NON VIDE lst''' return lst def contenu(c:'Cellule') -> 'Element': # cout constant '''Renvoie le contenu de la cellule''' return c[0] # une Cellule est le couple (Element, Successeur) def successeur(c:'Cellule Non Finale') -> 'Cellule': # cout constant '''Renvoie la cellule qui succède à c, c NE DOIT PAS être la DERNIERE Cellule de la liste''' return c[1] # une Cellule est le couple (Element, Successeur) def premier(lst:'Liste Non Vide') -> 'Element': # cout constant '''Renvoie le contenu de la tête de la liste NON VIDE lst''' return contenu(accesTete(lst)) # manipulation des opérations primitives def representerListe(lst:'Liste') -> str: '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête''' reponse = [] while not estListeVide(lst): valeur_tete = premier(lst) reponse.append(valeur_tete) lst = supprimerTete(lst) return str(reponse).replace(',',' -> ').replace('[','').replace(']','') # Déclaration des fonctions de la deuxième partie def aSuccesseur(lst:'Liste') -> bool: '''Prédicat qui renvoie True si la Tête de Liste a une Cellule qui lui succède''' return not(estListeVide(lst) or estListeVide(supprimerTete(lst))) def longueur(lst:'Liste') -> int: '''Renvoie le nombre d'éléments dans la liste lst''' pass def acces(lst:'Liste Non Vide', i:int) -> 'Cellule': '''Renvoie la Cellule de position i VALIDE dans la liste NON VIDE lst''' pass def ieme(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie le contenu de la Cellule de position i VALIDE dans la liste NON VIDE lst''' pass def inserer(elt:'Element', lst:'Liste', i:int) -> 'Liste': '''Renvoie une nouvelle liste où on a inséré elt en tant qu'élément de position i''' pass def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste': '''Renvoie une liste obtenue en supprimant l'élément de position i VALIDE dans la liste NON VIDE lst''' pass def concatener(gauche:'Liste', droite:'Liste') -> 'Liste': '''Renvoie une nouvelle liste commençant par la tête de gauche vers la fin de droite''' pass def rechercher(lst:'Liste', elt:'Element') -> int: '''Renvoie la position éventuelle de elt dans lst, -1 si non trouvé''' pass # Instructions du programme principal if __name__ == '__main__': # Ces fonctions ne seront en mémoire qu'en lancement direct def tester_insererTete(): a = nouvelleListe() a = insererTete(a, 5) assert a == (5, ()) a = insererTete(a, 2) assert a == (2, (5, ())) b = insererTete(20, a) assert a == (2, (5, ())) assert b == (20, (2, (5, ()))) print('Test OK pour insererTete()') def tester_supprimerTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) b = supprimerTete(a) assert a == (2, (5, ())) assert b == (5, ()) c = supprimerTete(b) assert estListeVide(c) print('Test OK pour supprimerTete()') def tester_accesTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) assert accesTete(a) == a print('Test OK pour accesTete()') def tester_contenu(): a = nouvelleListe() a = insererTete(a, 5) b = insererTete(a, 2) assert contenu(a) == 5 assert contenu(b) == 2 print('Test OK pour contenu()') def tester_successeur(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = insererTete(c, 20) assert successeur(d) == c assert successeur(c) == b print('Test OK pour successeur()') def tester_p1(): # Tous les tests de la partie 1 tester_insererTete() tester_supprimerTete() tester_accesTete() tester_contenu() tester_successeur() def tester_longueur(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert longueur(a) == 0 assert longueur(b) == 1 assert longueur(c) == 2 print('Test OK pour longueur()') def tester_acces(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert acces(b, 0) == b assert acces(c, 0) == c assert acces(c, 1) == b print('Test OK pour acces()') def tester_ieme(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert ieme(b, 0) == 5 assert ieme(c, 0) == 2 assert ieme(c, 1) == 5 print('Test OK pour lire()') def tester_inserer(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) assert d == (2, (20, (5, ()))) print('Test OK pour inserer()') def tester_supprimer(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) e = supprimer(d, 2) assert d == (2, (20, (5, ()))) assert e == (2, (20, ())) print('Test OK pour supprimer()') def tester_concatener(): a = nouvelleListe() b1 = insererTete(a, 5) b2 = insererTete(b1, 2) b3 = insererTete(b2, 50) c1 = insererTete(a, 20) c2 = insererTete(c1, 200) d = concatener(b3, c2) assert d == (50, (2, (5, (200, (20, ()))))) print('Test OK pour concatener()') def tester_rechercher(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) assert rechercher(d, 30) == -1 assert rechercher(d, 20) == 1 assert rechercher(d, 2) == 0 assert rechercher(d, 5) == 2 print('Test OK pour rechercher()') print("Module lancé directement, il ne s'agit pas d'une importation")

07° Utiliser ce nouveau module à la place de l'ancien. Trois questions :

  1. Expliquer pourquoi cette expression vérifie que la liste n'a pas de vrai successeur :
  2. estListeVide(lst) or estListeVide(supprimerTete(lst))

  3. Formuler en fançais la question qu'on pose à l'interpréteur en inversant la réponse precédente ?
  4. not( estListeVide(lst) or estListeVide(supprimerTete(lst)) )

  5. En se souvenant que NON (a OU b) est équivalent à (NON a) ET (NON b), comment aurait-on pu écrire la réponse de la fonction ?
  6. Expliquer ensuite pourquoi on ne peut pas juste utiliser la fonction successeur() et vérifier que la réponse n'est pas une Cellule vide. Pensez au "défaut" majeur de la fonction successeur().

...CORRECTION...

  1. Expliquer pourquoi cette expression vérifie que la liste n'a pas de successeur :
  2. estListeVide(lst) or estListeVide(supprimerTete(lst))

    On demande si la liste est vide (et n'a donc évidemment pas de vrai successeur) ou si le successeur de la liste est vide (et la liste n'a donc pas de vrai successeur).

  3. Formuler en fançais la question qu'on pose à l'interpréteur en inversant la réponse precédente ?
  4. not( estListeVide(lst) or estListeVide(supprimerTete(lst)) )

    L'inverse logique de "N'a pas de vrai successeur" est "A un successeur".

    La question qu'on pose est donc "La Liste a-t-elle un successeur ?

  5. En se souvenant que NON (a OU b) est équivalent à (NON a) ET (NON b), comment aurait-on pu écrire la réponse de la fonction ?
  6. not estListeVide(lst) and not estListeVide(supprimerTete(lst))

    Pour éviter les confusions, on peut placer des parenthèses si on veut (mais ce n'est pas nécessaire ici car not)

    (not estListeVide(lst)) and (not estListeVide(supprimerTete(lst)))

  7. Expliquer ensuite pourquoi on ne peut pas juste utiliser la fonction successeur() et vérifier que la réponse n'est pas une Cellule vide. Pensez au "défaut" majeur de la fonction successeur().
  8. La documentation précise bien que la fonction renvoie TOUJOURS une Cellule. Or, pour que la fonction puisse renvoyer une Cellule, il faut que la Cellule est un vrai successeur. Il ne peut donc pas s'agir de la dernière Cellule d'une Liste Chaïnée.

08-A° Créer la fonction d'interface longueur() en utilisant les fonctions d'interface estListeVide() et supprimerTete(). Le principe est bien de compter une à une les cellules. Commencer soit par la version récursive, soit par la version itérative puis... faire la version qui vous plait moins.

Prototype

def longueur(lst:'Liste') -> int:

AIDE : puisque Successeur() a une précondition assez sérieuse, et que longueur est toujours à coût linéaire, le plus simple pour savoir si la Tête d'une Liste a un vrai successeur est de supprimer la Tête et de voir si on obtient une liste vide.

Vous pourrez utiliser la fonction tester_longueur() pour vérifier votre réponse OU comprendre ce qu'on attend de vous. Finalement, les fonctions de test, c'est pratique pour la phase d'écriture non ?

...CORRECTION...

1 2 3 4 5 6 7 8
def longueur(lst:'Liste') -> int: '''Renvoie le nombre d'éléments dans la liste lst''' if estListeVide(lst): # Cas de base de la liste vide return 0 elif estListeVide(supprimerTete(lst)): # Cas de base de la dernière Cellule return 1 else: # Cas récursif return 1 + longueur(supprimerTete(lst))
1 2 3 4 5 6 7
def longueur(lst:'Liste') -> int: '''Renvoie le nombre d'éléments dans la liste lst''' n = 0 while not estListeVide(lst): n = n + 1 lst = supprimerTete(lst) # Attention : lst devient juste une variable locale return n

08-B° Quel est le coût de votre fonction longueur() ? Sa complexité ?

09-A° Créer la fonction d'interface acces() en utilisant les fonctions d'interface existantes. Le principe est bien de se déplacer vers la bonne Cellule. Attention à la précondition : l'indice i qu'on vous envoie est valide et la liste n'est donc pas vide.

Prototype

def acces(lst:'Liste Non Vide', i:int) -> 'Cellule':

Vous pourrez utiliser la fonction tester_acces().

...CORRECTION...

Beaucoup de versions possibles : récursives ou itératives, avec successeur(), avec supprimerTete() ou avec supprimer()...

Quelques possibilités :

1 2 3 4 5 6
def acces(lst:'Liste Non Vide', i:int) -> 'Cellule': '''Renvoie la Cellule de position i VALIDE dans la liste NON VIDE lst''' if i == 0: # Cas de base return accesTete(lst) else: # Cas récursif return acces(supprimerTete(lst), i-1)
1 2 3 4 5 6
def acces(lst:'Liste Non Vide', i:int) -> 'Cellule': '''Renvoie la Cellule de position i VALIDE dans la liste NON VIDE lst''' c = accesTete(lst) for indice in range(i): c = successeur(c) return c

09-B° Quel est le coût de votre fonction acces() ? Sa complexité ?

10-A° Créer la fonction d'interface ieme(). Maintenant que la fonction acces() est réalisée, c'est facile.

Prototype

def ieme(lst:'Liste Non Vide', i:int) -> 'Element':

Vous pourrez utiliser la fonction tester_ieme().

...CORRECTION...

Beaucoup de versions possibles. Le plus simple est d'utiliser la primitive acces() qu'on vient de créer.

1 2 3
def ieme(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie le contenu de la Cellule de position i VALIDE dans la liste NON VIDE lst''' return contenu(acces(lst, i))

10-B° Quel est le coût de votre fonction ieme() ? Sa complexité ?

RAPPEL : variable de boucle nommée _ ?

On utilise ce nom de variable de boucle lorsqu'on veut simplement dire qu'on veut faire l'action k fois : for _ in range(10) veut donc dire qu'on va faire le bloc 10 fois.

11° Observer la fonction inserer() ci-dessous.

inserer(lst:Liste, elt:Element, i:int) -> Liste
Renvoie une nouvelle liste où l'élément fourni lst est maintenant l'élément de la liste situé à l'indice i voulu.

PRECONDITION : l'indice doit être un indice VALIDE pour la liste fournie. Transmettre un indice égale à la longueur de la liste, cela veut dire de placer l'élément en fin de liste. Si la liste est vide, le seul indice valide est donc l'indice 0.

listeA = (12, 15, 18, 7)
listeB = inserer(listeA, 5, 2)
listeB contiendra les éléments dans cet ordre : (12, 15, 5, 18, 7).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def inserer(lst:'Liste', elt:'Element', i:int) -> 'Liste': '''Renvoie une nouvelle liste où on a inséré elt en tant qu'élément de position i''' # 1 - Suppression et mémorisation des éléments de 0 à i-1 memoire = nouvelleListe() for _ in range(i): # on réalise le bloc i fois v = premier(lst) # on lit la valeur de Tête memoire = insererTete(memoire, v) # on stocke en tête de mémoire lst = supprimerTete(lst) # on supprime une tête (lst devient une variable locale) # 2 -Rajout du nouvel élément lst = insererTete(lst, elt) # 3 - Remise en place des éléments précédents for _ in range(i): # on réalise le bloc i fois v = premier(memoire) # on lit la valeur de Tête de mémoire lst = insererTete(lst, v) # on la rajoute en tête de lst memoire = supprimerTete(memoire) # on supprime cette valeur de la mémoire return lst

Exemple d'utilisation :

>>> a = insererTete(insererTete(insererTete(nouvelleListe(), 5), 15), 20) >>> representerListe(a) '20 -> 15 -> 5' >>> a = inserer(a, 12, 1) >>> representerListe(a) '20 -> 12 -> 15 -> 5' >>> a = inserer(a, 20, 2) >>> representerListe(a) '20 -> 12 -> 20 -> 15 -> 5'

Questions :

  1. Expliquer comment fonctionne cette fonction.
  2. Que vaut le coût de l'insertion d'un nouvel élément dans le pire des cas pour notre implémentation (c'est à dire lorsque l'élément à rajouter est à placer en fin de liste) :
    1. Le coût est constant  : 𝞗(1)
    2. Le coût est logarithmique  : 𝞗(lg n)
    3. Le coût est linéaire : 𝞗(n)
    4. Le coût est quadratique : 𝞗(n2)
    5. Le coût est exponentielle : 𝞗(en)
  3. Que vaut le coût de l'insertion d'un nouvel élément dans le meilleur des cas pour notre implémentation (c'est à dire lorsque l'élément à rajouter est à placer en tête de liste) :
    1. Le coût est constant  : 𝞗(1)
    2. Le coût est logarithmique  : 𝞗(lg n)
    3. Le coût est linéaire : 𝞗(n)
    4. Le coût est quadratique : 𝞗(n2)
    5. Le coût est exponentielle : 𝞗(en)

...CORRECTION...

Pire des cas

Si notre liste possède n éléments, on voudra le placer à l'index n-1.

On remarque qu'on a n-1 opérations de suppression de têtes puis n-1 opérations d'insertion de têtes.

On a donc 2 * (n-1) opérations linéaires à effectuer.

On a donc 2 n - 2 opérations.

Si on néglige le -2 pour les grandes valeurs de n, on obtient 2 n opérations.

On omet le facteur multiplicateur puisqu'on ne cherche que l'évolution pour cette même structure pour deux valeurs de n différentes : on voit donc que l'insertion possède un coût en n : il s'agit d'une évolution linéaire.

Meilleur des cas

Il suffit de créer un nouveau tuple en allant lire l'adresse de l'ancien tuple, en créant un nouveau tuple (tete, queue) et en renvoyant le résultat : 3 actions élémentaires quelque soit le nombre de données réel dans la liste. Le coût est donc constant quelque soit la longueur n des données.

12-A° Réaliser la fonction supprimer() qui se rapproche de la fonction inserer(). La différence vient de l'action une fois sur place. On supprime la Cellule plutôt que de créer une nouvelle liaison.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste': '''Renvoie une liste obtenue en supprimant l'élément de position i VALIDE dans la liste NON VIDE lst''' # 1 - Suppression et mémorisation des éléments de 0 à i-1 memoire = nouvelleListe() for _ in range(i): # on réalise le bloc i fois v = premier(lst) # on lit la valeur en Tête memoire = insererTete(memoire, v) # on stocke en tête de mémoire lst = supprimerTete(lst) # on supprime une tête (lst devient une variable locale) # 2 -Suppression de cet élément lst = supprimerTete(lst) # 3 - Remise en place des éléments précédents for _ in range(i): # on réalise le bloc i fois v = premier(memoire) # on lit la valeur de Tête de la mémoire lst = insererTete(lst, v) # on rajoute en tête de lst memoire = supprimerTete(memoire) # on supprime de la mémoire return lst

12-B° Quel est le coût de votre fonction supprimer() ? Sa complexité ?

Coût de l'implémentation en tuple (tête, queue)

Vous venez de créer l'ensemble des opérations primitives permettant de nommer notre structure de données une Liste. Notre implémentation est basée sur la Liste Chaînée qui est la meilleure façon de réaliser une Liste Récursive.

On notera que toutes les actions sur la Tête sont à coût constant (complexité 𝞗(1)).

On peut dire que dans un cas quelconque :

  • La lecture est à coût linéaire (complexité en 𝞞(n) car c'est linéaire ou moins)
  • L'insertion et la suppression est à coût linéaire (complexité en 𝞞(n) car c'est linéaire ou moins)

3 - Concaténation et autres créations

Regardons l'un des autres avantages des Listes Chaînées : la concaténation de deux listes.

Changement de référence

13-A° Créer la fonction d'interface concatener(). Elle doit parvenir à réaliser une nouvelle Liste à partir de la liste de gauche et de la liste de droite

  • La Tête de la nouvelle liste est la Tête de la liste de gauche
  • La Fin de la liste de gauche doit mener à la Tête de la liste de droite
  • La Fin de la nouvelle liste est la Fin de la liste de droite

Prototype

def concatener(gauche:'Liste', droite:'Liste') -> 'Liste':

Attention, les listes de base peuvent très bien être vides.

13-B° Si on désigne par n1 la longueur de la liste de gauche et par n2 la longueur de la liste de droite, quel est le coût puis la complexité de cette opération de concaténation ?

  1. Coût linéaire par rapport à (n1+n2) et complexité 𝞗(n1 + n2)
  2. Coût linéaire par rapport à (n1+n2) et complexité 𝞞(n1 + n2)
  3. Coût linéaire par rapport à n1 et complexité 𝞗(n1)
  4. Coût linéaire par rapport à n1 et complexité 𝞞(n1)
  5. Coût linéaire par rapport à n2 et complexité 𝞗(n2)
  6. Coût linéaire par rapport à n2 et complexité 𝞞(n2)

Voilà, vous en avez fini pour la conception du module. Vous trouverez dans la partie FAQ de nouvelles fonctionnalités pratiques mais dont le coût est malheureusement linéaire. Quelqu'un ne comprennant pas le type Liste Chainée pourrait croire à tord qu'utiliser ces fonctions est très rapide puisqu'on les appelle en n'utilisant qu'une instruction. Vous avez maintenant compris qu'il faut plus de compréhension d'une structure de données pour répondre à la question de l'efficacité d'une instruction.

Description du MODULE final LISTE CHAINEE IMMUABLE TETE-QUEUE

Voici les fonctions d'interface disponibles, classées selon trois catégories :

  • Caractéristiques et fondamentales du type Liste Chaînées,
  • Primitives manquantes être le type Liste généraliste,
  • Fonctions supplémentaires pratiques.
'''INTERFACE du type Liste Chaînée IMMUABLE basée sur des tuples : () ou (tete, queue) Description des types non natifs -------------------------------- Element : le type des éléments disponibles dans votre Liste si elle est homogène. Cellule : la référence d'un conteneur (Element, Cellule suivante). Liste : la référence de la Cellule de la Tête ou d'une Liste Vide. Opérations primitives de la Liste Chainée ----------------------------------------- + nouvelleListe() -> Liste CST + estListeVide(lst:'Liste') -> bool CST + insererTete(lst:'Liste', elt:'Element') -> 'Liste' CST + supprimerTete(lst:'Liste Non Vide') -> 'Liste' CST + premier(lst:'Liste Non Vide') -> 'Element' CST + accesTete(lst:'Liste Non Vide') -> 'Cellule' CST + contenu(c:'Cellule') -> 'Element' CST + successeur(c:'Cellule Non Finale') -> 'Cellule' CST Autres opérations nécessaires du type Liste ------------------------------------------- + longueur(lst:'Liste') -> int LIN θ(n) + acces(lst:'Liste Non Vide', i:int) -> 'Cellule' LIN θ(i) O(n) + inserer(lst:'Liste', elt:'Element', i:int) -> 'Liste' LIN θ(i) O(n) + supprimer(lst:'Liste Non Vide', i:int) -> 'Liste' LIN θ(i) O(n) Fonctions d'interface supplémentaires ------------------------------------- + representerListe(lst:"Liste') -> str + aSuccesseur(lst:'Liste') -> bool CST + ieme(lst:'Liste Non Vide', i:int) -> 'Element' LIN θ(i) O(n) + concatener(gauche:'Liste', droite:'Liste') -> 'Liste' LIN θ(n_gauche) + rechercher(lst1:'Liste', elt:'Element') -> int LIN θ(i) O(n) + liste(x) -> 'Liste' LIN θ(n_x) + copie(lst:'Liste') -> 'Liste' LIN θ(n) + dernier(lst:'Liste Non Vide') -> 'Element' LIN θ(n) + accesFin(lst:'Liste Non Vide') -> 'Cellule' LIN θ(n) '''

14° En regardant simplement la documentation des fonctions disponibles, quelle est la partie de la notre Liste Chaînée Tête-Queue basique sur laquelle il est le plus difficile d'intervenir ?

15° Aller chercher le module finalisé dans la partie FAQ. Nous allons réaliser un court programme en utilisant notre module de listes chaînées.

  1. Etudier la fonction liste() qui permet de générer une liste à partir d'une autre donnée, quelconque : quel est son coût ?
  2. 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
    def liste(x) -> 'Liste': '''Renvoie une liste générée à partir de x''' nouvelle = nouvelleListe() if type(x) == list or type(x) == tuple: for i in range(len(x)-1, -1, -1): nouvelle = insererTete(nouvelle, x[i]) elif type(x) == dict: for couple in dict.items(): nouvelle = insererTete(nouvelle, couple) elif type(x) == int or type(x) == float or type(x) == str or type(x) == bool: nouvelle = insererTete(nouvelle, x) return nouvelle
  3. Placer le module (qu'on nommera liste_chainee_tq.py) au même endroit que le programme suivant. Lancer pour constater le bon fonctionnement.
  4. 1 2 3 4 5 6 7 8 9 10 11 12 13
    from liste_chainee_tq import liste from liste_chainee_tq import concatener from liste_chainee_tq import representerListe as representer t = ['alice', 'bob', 'clark'] t2 = ['diane', 'elise', 'fred'] lst1 = liste(t) lst2 = liste(t2) total = concatener(lst1, lst2) print(representer(total))

16° Etudier la fonction copie() et expliquer son fonctionnement et déterminer son coût par rapport aux nombres d'éléments n de la liste de base.

1 2 3 4 5 6 7 8 9 10 11 12 13
def copie(lst:'Liste') -> 'Liste': '''Renvoie une copie peu profonde de la liste lst envoyée''' nouvelle = nouvelleListe() temporaire = nouvelleListe() for _ in range(longueur(lst)): elt = premier(lst) temporaire = insererTete(temporaire, elt) lst = supprimerTete(lst) for _ in range(longueur(temporaire)): elt = premier(temporaire) nouvelle = insererTete(nouvelle, elt) temporaire = supprimerTete(temporaire) return nouvelle
CONCLUSION ::Primitives du type et fonctions d'interface

En conclusion, les primitives sont un ensemble de fonctions bien choisies qui sont les seules à manipuler directement la structure interne de notre structure de données.

Toutes les autres fonctions manipulent juste les primitives et n'ont pas de contact direct avec les données internes.

4 - FAQ

On peut avoir le module déjà réalisé ?

Vous pouvez maintenant directement télécharger ce module :

MODULE LISTE CHAINEE TETE-QUEUE

Un coût linéaire en lecture et en insertion/suppression. Pas terrible pour cette première Liste. Regardons si on peut faire mieux.

Activité publiée le 14 10 2020
Dernière modification : 03 10 2022
Auteur : ows. h.