Bienvenue !

Structures de données et algorithmes en Python

Miriam Antona

Software Engineer

Importance algorithmes et structures données

• Structures de données et algorithmes
  • résoudre problèmes quotidiens
  • avec code efficace
• Possible dans n’importe quel langage de programmation

Algorithmes et structures données

• Algorithme : lot instructions résolution problème

  1. Conception

     

  2. Code

     

• Structures données : stockent/manipulent données lors exécution algorithme
  • Structures données avancées : listes chaînées, piles, files…

Listes chaînées

• Séquence de données reliées par des liens

Listes chaînées - structure

Listes chaînées - structure

Listes chaînées - structure

Listes chaînées - structure

Listes chaînées - structure

Listes chaînées - structure

Listes chaînées - structure

Listes chaînées - structure

• Pas besoin stocker données dans blocs contigus de mémoire
• Possible stocker données quelle adresse mémoire disponible

Listes simplement chaînées

• Un lien : liste simplement chaînée

Listes doublement chaînées

• Deux liens dans chaque sens : liste doublement chaînée

Listes chaînées - usages réels

• Implémenter autres structures données :
  • piles
  • files d’attente
  • graphes
• Accès info en naviguant en arrière et en avant
  • navigateur web
  • playlist musicale

Listes chaînées - classe Node

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

Listes chaînées - classe LinkedList

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

Listes chaînées - méthodes

• insert_at_beginning()
• remove_at_beginning()
• insert_at_end()
• remove_at_end()
• insert_at()
• remove_at()
• search()
• ...

Listes chaînées - insert_at_beginning

Listes chaînées - insert_at_beginning

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

    if self.head:

Listes chaînées - insert_at_beginning

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

Listes chaînées - insert_at_beginning

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

Listes chaînées - insert_at_beginning

 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

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

Listes chaînées - recherche

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Listes chaînées - recherche

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

Listes chaînées - recherche

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

Listes chaînées - exemple

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Listes chaînées - exemple

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 

Listes chaînées - exemple

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")

Listes chaînées - exemple

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Passons à la pratique !

Structures de données et algorithmes en Python