{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Listes chaînées" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

L'élément de base d'une liste simplement chaînée est une cellule constituée de deux parties.

\n", "\n", "\n", "Une liste est alors une succession de cellules, chacune pointant sur la suivante, et la dernière ayant un pointeur nul - i.e. ne pointant sur rien. \n", "En pratique, la variable «contenant» la liste est simplement un pointeur vers la première cellule.\n", "\n", "\n", "

À noter que les cellules n'ont pas à être placées de façon contigüe en mémoire - ce qui va donner à cette structure plus de souplesse qu'aux tableaux. Par exemple, l'insertion ou la suppression en début de liste s'effectue en temps constant grâce aux algorithmes que vous allez coder.

\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Remarques :

\n", "
    \n", "
  1. Avec cette définition, il n'y a pas d'accès direct aux valeurs des éléments. On avance dans la liste à partir de la tête, jusqu'à l'élément souhaité.
    2. \n", "
  2. Cette représentation occupe un espace mémoire important puisqu'il faut stocker pour chaque cellule, une valeur et une adresse.
    3. \n", "
  3. Elle est néanmoins performante en temps d'éxécution pour certaines opérations comme l'insertion ou la suppression.
    4. \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Encapsulation dans un objet\n", "Nous allons utiliser le paradigme de la programmation objet pour implémenter ce concept en python et définir deux classes : la classe `Cellule` qui définit une cellule et la classe `Lc` qui définit une liste chaînée, classe pour laquelle nous ajouterons ensuite des méthodes pour effectuer des opérations usuelles sur les listes.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "## Exercice 1\n", "La classe `Cellule` contient deux attributs initialisés par la méthode constructeur :\n", "* `valeur` : Contient la valeur de la cellule définie\n", "* `suivant`: Contient l'adresse mémoire de la cellule suivante, par défaut la valeur `None`\n", "\n", "Ecrire la méthode `__str(self)__` qui doit permettre d'afficher la valeur de la cellule.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Cellule:\n", " '''Cellule d'une liste chainee'''\n", " \n", " def __init__(self,valeur,suivant=None):\n", " self.valeur=valeur\n", " self.suivant=suivant\n", " \n", " def __str__(self):\n", " \"\"\" affichage de la valeur de la cellule \"\"\"\n", " pass\n", " \n", " \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Définition d'une cellule et affichage\n", "c1 = Cellule(\"coucou\")\n", "print(c1)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Construction d'une première liste\n", "Voici alors une première façon de construire la liste chaînée $2,4,1,5$ à l'aide de la classe `Cellule`:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "L=Cellule(2,Cellule(4,Cellule(1,Cellule(5))))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* La variable `L` contient l'adresse mémoire de l'objet contenant la valeur 2 qui lui même contient l'adresse de l'autre objet contenant 4 qui lui même contient l'adresse de l'objet contenant 1 qui lui même contient l'adresse de l'objet contenant 5 et l'attribut `None`. (qui n'est pas obligatoire car par défaut vaut `None`)\n", "\n", "* Cette implémentation est cependant incomplète, car il n'est pour l'instant pas possible d'afficher une version plus lisible de cette liste :" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n" ] } ], "source": [ "# Affichage d'une liste chaînée \n", "print(L)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "### Définition d'une liste\n", "Nous allons construire une classe `ListeChainee` qui va permettre de compléter l'implémentation.
Cette classe contient un attribut `tete` initialisé par le constructeur avec la valeur par défaut `None`. Cet attribut est simplement le lien vers l'adresse de la première cellule.\n", "
" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "class ListeChainee: # à completer au fur à mesure des questions\n", " '''Liste chaînée'''\n", " \n", " def __init__(self, tete=None):\n", " '''tete : lien vers la premiere cellule'''\n", " self.tete=tete\n", " \n", " def __str__(self):\n", " '''renvoie une forme lisible de Liste Chainée sous la forme : 2 -> 4 -> 1 -> 5 -> None '''\n", " ch=\"\"\n", " element=self.tete\n", " while element!=None:\n", " ch=ch+str(element.valeur)+\" -> \"\n", " element=element.suivant\n", " return ch + \"None\"\n", " \n", " def est_vide(self):\n", " return self.tete==None\n", " \n", " \n", " \n", " def __len__(self):\n", " '''renvoie la longueur de la liste'''\n", " # A compléter\n", " n=0\n", " element=self.tete\n", " while element!=None:\n", " n+=1\n", " element=element.suivant\n", " return n\n", " \n", " \n", " def __getitem__(self, index):\n", " pass\n", " \n", " \n", "\n", " \n", " \n", " def inserer(self,x,index):\n", " '''insere l'élément x dans la liste\n", " à l'index donné, numéroté à partir de 0'''\n", " # A compléter\n", " pass\n", " \n", " \n", " def supprimer(self,index):\n", " ''' Supprime l'élément d'index donné\n", " numéroté partir de 0, de la liste'''\n", " # A compléter\n", " pass# methodes à ajouter ( ex5)\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "### Exercice 2:\n", "Compléter la classe `ListeChainee` avec la méthode `__str(self)__` qui doit permettre d'afficher la liste considérée telle que nous la connaissons en python. Ainsi , si `L` est la liste définie plus haut, `print(L)` doit renvoyer ` 2 -> 4 -> 1 -> 5 -> None `.Si la liste est vide, alors la chaîne `None` est renvoyée.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "a. Crééer alors la liste $2,4,1,5$ ci-dessous en utilisant les classes `Cellule` et `ListeChainee`, puis l'afficher\n", "
" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2 -> 4 -> 1 -> 5 -> None\n" ] } ], "source": [ "# A compléter\n", "# on crée les cellules séparement\n", "c1=Cellule(2)\n", "c2=Cellule(4)\n", "c3=Cellule(1)\n", "c4=Cellule(5)\n", "# on crée les liens \n", "c1.suivant=c2\n", "c2.suivant=c3\n", "c3.suivant=c4\n", "# on crée la liste chainée à partir de la tete\n", "L=ListeChainee(c1)\n", "print(L)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "b. Ecrire un script qui permet d'afficher :\n", " * La valeur de la tête.\n", " * La valeur du deuxième élément à partir de la tête.\n", " * La valeur du dernier élément à partir de la tête.\n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#valeur de la tête\n", "\n", "#valeur du 2nd élément\n", "\n", "#valeur du dernier élément\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "### Exercice 3:\n", "a) Completer la classe `ListeChainee` avec les méthodes :\n", "
  • est_vide
    • \n", "
  • __len__ qui renvoie la taille de la liste
    • \n", " \n", "b) Ecrire un script permettant de tester ces methodes\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Remarques :\n", "* Les instructions `len(L)` et `L.__len__()` sont équivalentes(cela fonctionne par ailleurs avec les tableaux python)\n", "* Complexité du calcul de l'accès à un élément :\n", " * Quelque soit le nombre de cellules, il faut les parcourir toutes.\n", " * La complexité du calcul est donc proportionnelle au nombre $n$ de cellules, en $\\mathcal{O}(n)$\n", " * Pour $1000$ cellules, il faudra donc effectuer $1000$ tests (`while`), $1000$ additions (`n+1`), et $2000$ affectations (`=`), soit $4000$ opérations élémentaires." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#tests " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
    \n", " \n", "### Exercice 4:\n", "Ecrire la methode `__getitem__(self,i)` qui renvoie l'élement d'index `i`, numéroté à partir de 0 et faire un test \n", "
    " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Remarques :\n", "* Les instructions `L[i]` et `L.__getitem__(i)` sont équivalentes(cela fonctionne par ailleurs avec les tableaux python)\n", "* Complexité du calcul de l'accès à un élément :\n", " * Cela dépend de la valeur de `index` :\n", " * Dans certains cas, il faut autant de passages dans la boucle `while` que de cellules à parcourir jusqu'à l'index demandé.\n", " * Dans le pire des cas, il faut parcourir toute la liste (par exemple lorsque l'index est supérieur à égal à celui de la dernière cellule)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Tests de l'exercice 4\n", "assert L[2]==1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
    \n", " \n", "### Exercice 5 :\n", " Ecrire la methode `inserer(self, x, index)` qui insère l'élément `x` à l'index donné en paramètre numéroté à partir de $0$.\n", "
    " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " \n", "\n", "Le but de cet exercice est d'écrire la méthode `inserer(self, x, index)` qui insère l'élément `x` à l'index donné en paramètre numéroté à partir de $0$. \n", "* On envisagera d'abord les cas particuliers ou :\n", " * La liste est vide.\n", " * `index` est égal à $0$ (insertion en début de liste).\n", "\n", "\n", "* Cas général(voir exemple ci-contre):\n", "\n", " * On avance dans la liste jusqu'à la cellule numéro `index-1`\n", " * On crée une nouvelle cellule de valeur `x` et liée à la cellule numéro `index`\n", " * On lie la cellule numéro `index-1` à la nouvelle cellule\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# test\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Remarques :\n", "* On voit ici l'éfficacité de l'insertion dans une liste chaînée en début de liste. Il est inutile de décaler des éléments comme on le ferait pour un tableau, il suffit de créer une cellule à placer en tête et la lier à la cellule qui était précédemment en tête.\n", "* Dans ce cas la complexité de calcul est en temps constant( en $\\mathcal{O}(1)$) quelque soit la longueur de la liste !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
    \n", " \n", "### Exercice 6 :\n", " Ecrire la fonction la méthode `supprimer(self,index)` qui supprime l'élément `x` à l'index donné en paramètre numéroté à partir de $0$. \n", "
    " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suppression\n", " \n", "\n", "Le but de cet exercice est d'écrire la méthode `supprimer(self,index)` qui supprime l'élément `x` à l'index donné en paramètre numéroté à partir de $0$. \n", "* On envisagera d'abord le cas particulier ou `index` est égal à $0$ (le premier élément est supprimé) :\n", "\n", "\n", "* Cas général(voir exemple ci-contre):\n", "\n", " * On avance dans la liste jusqu'à la cellule numéro `index-1`\n", " * On lie la cellule numéro `index-1` à la cellule numéro `index+1`\n", "\n", "\n", "* Bonus : Si l'index est absurde, renvoyer `index error` ( ajouter des tests adéquats)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#tests" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Remarques :\n", "* Encore une fois la suppression dans une liste chaînée en début de liste est efficace. Il est inutile de décaler des éléments comme on le ferait pour un tableau, il suffit de bien choisir la cellule à placer en tête de liste.\n", "* Dans ce cas la complexité de calcul est en temps constant( en $\\mathcal{O}(1)$) quelque soit la longueur de la liste !" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.7" } }, "nbformat": 4, "nbformat_minor": 4 }