Bienvenue !

Structures de données et algorithmes en Python

Miriam Antona

Software Engineer

L’importance des algorithmes et des structures de données

  • Les structures de données et les algorithmes permettent de
    • résoudre des problèmes courants
    • avec un code efficace
  • Le cours peut être enseigné dans n’importe quel langage
Structures de données et algorithmes en Python

Algorithmes et structures de données

  • Algorithme : ensemble d’instructions pour résoudre un problème

    1. Conception

      Schéma de la conception d’un algorithme.

    2. Code

      Schéma du code d’un algorithme.

  • Structures de données : stockent et manipulent les données lors de l’exécution d’un algorithme
    • Structures avancées : listes chaînées, piles, files…
Structures de données et algorithmes en Python

Listes chaînées

Exemple visuel d’une liste chaînée contenant les étapes pour préparer du pain.

  • Suite de données reliées par des liens
Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation d’un nœud d’une liste chaînée.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation d’un nœud d’une liste chaînée avec le mot « DATA » dans la première partie.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation d’un nœud d’une liste chaînée avec « DATA » dans la première partie, et « NEXT » avec un pointeur dans la seconde.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation de deux nœuds d’une liste chaînée reliés par un lien.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation de plusieurs nœuds d’une liste chaînée reliés par des liens.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation d’une liste chaînée où le dernier nœud pointe vers null.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation d’une liste chaînée avec le mot « HEAD » dans le premier nœud.

Structures de données et algorithmes en Python

Listes chaînées - structure

Représentation d’une liste chaînée avec le mot « TAIL » dans le dernier nœud.

  • Les données n’ont pas besoin d’être contiguës en mémoire
  • Elles peuvent se trouver à n’importe quelle adresse libre
Structures de données et algorithmes en Python

Listes simplement chaînées

Représentation d’une liste simplement chaînée.

  • Un lien : liste simplement chaînée
Structures de données et algorithmes en Python

Listes doublement chaînées

Représentation d’une liste doublement chaînée.

  • Deux liens dans chaque sens : liste doublement chaînée
Structures de données et algorithmes en Python

Listes chaînées - usages concrets

  • Implémenter d’autres structures :
    • piles
    • files
    • graphes
  • Accéder en naviguant avant/arrière
    • navigateur web
    • playlist musicale
Structures de données et algorithmes en Python

Listes chaînées - classe Node

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
Structures de données et algorithmes en Python

Listes chaînées - classe LinkedList

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None
Structures de données et algorithmes en Python

Listes chaînées - méthodes

  • insert_at_beginning()
  • remove_at_beginning()
  • insert_at_end()
  • remove_at_end()
  • insert_at()
  • remove_at()
  • search()
  • ...
Structures de données et algorithmes en Python

Listes chaînées - insert_at_beginning

Représentation d’une liste simplement chaînée.

Structures de données et algorithmes en Python

Listes chaînées - insert_at_beginning

Représentation d’une liste simplement chaînée et d’un nouveau nœud,

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:
Structures de données et algorithmes en Python

Listes chaînées - insert_at_beginning

Représentation d’une liste simplement chaînée avec le nouveau nœud connecté.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
Structures de données et algorithmes en Python

Listes chaînées - insert_at_beginning

Représentation d’une liste simplement chaînée avec le nouveau nœud connecté et le mot « HEAD » sur ce nœud.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
Structures de données et algorithmes en Python

Listes chaînées - insert_at_beginning

Représentation d’un nouveau nœud dans une liste chaînée vide.

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node
Structures de données et algorithmes en Python

Listes chaînées - insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node
Structures de données et algorithmes en Python

Listes chaînées - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Représentation d’une liste simplement chaînée avec le mot « current_node » pointant vers le premier nœud.

Structures de données et algorithmes en Python

Listes chaînées - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

Représentation d’une liste simplement chaînée avec le mot « current_node » pointant vers le deuxième nœud.

Structures de données et algorithmes en Python

Listes chaînées - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

Représentation d’une liste simplement chaînée avec le mot « current_node » pointant vers le troisième nœud.

Structures de données et algorithmes en Python

Listes chaînées - exemple

Représentation d’un nouveau nœud dans une liste chaînée vide.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")
Structures de données et algorithmes en Python

Listes chaînées - exemple

Représentation d’un nouveau nœud ajouté à la fin d’une liste chaînée.

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll")
Structures de données et algorithmes en Python

Listes chaînées - exemple

Représentation d’un nouveau nœud ajouté au début d’une liste chaînée.

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")
Structures de données et algorithmes en Python

Listes chaînées - exemple

Représentation d’une liste chaînée.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...