Welkom!

Datastructuren en algoritmen in Python

Miriam Antona

Software Engineer

Het belang van algoritmen en datastructuren

Datastructuren en algoritmen helpen ons
- alledaagse problemen op te lossen
- met efficiënte code
De cursus kan in elke programmeertaal worden gegeven

Algoritmen en datastructuren

Algoritme: set instructies om een probleem op te lossen
1. Ontwerp
2. Code

Datastructuren: slaan data op en manipuleren die bij het uitvoeren van een algoritme
- Geavanceerde datastructuren: gelinkte lijsten, stacks, queues...

Gelinkte lijsten

Een visueel voorbeeld van een gelinkte lijst met de stappen om brood te bereiden.

Reeks data verbonden via links

Gelinkte lijsten - structuur

De weergave van een knoop in een gelinkte lijst.

Gelinkte lijsten - structuur

De weergave van een knoop in een gelinkte lijst met het woord "DATA" in het eerste deel.

Gelinkte lijsten - structuur

De weergave van een knoop in een gelinkte lijst met "DATA" in het eerste deel en "NEXT" met een pointer in het tweede deel.

Gelinkte lijsten - structuur

De weergave van twee knopen van een gelinkte lijst die met een link verbonden zijn.

Gelinkte lijsten - structuur

De weergave van meerdere knopen van een gelinkte lijst die met links verbonden zijn.

Gelinkte lijsten - structuur

De weergave van een gelinkte lijst waarbij de laatste knoop naar null wijst.

Gelinkte lijsten - structuur

De weergave van een gelinkte lijst met het woord "HEAD" in de eerste knoop.

Gelinkte lijsten - structuur

De weergave van een gelinkte lijst met het woord "TAIL" in de laatste knoop.

Data hoeft niet in aaneengesloten geheugenblokken te staan
Data kan op elk vrij geheugenadres staan

Enkelvoudig gelinkte lijsten

De weergave van een enkelvoudig gelinkte lijst.

Eén link: enkelvoudig gelinkte lijst

Dubbel gelinkte lijsten

De weergave van een dubbel gelinkte lijst.

Twee links in beide richtingen: dubbel gelinkte lijst

Gelinkte lijsten - echte toepassingen

Andere datastructuren implementeren:
- stacks
- queues
- grafen
Info benaderen door voor- en achteruit te navigeren
- webbrowser
- muziekafspeellijst

Gelinkte lijsten - Node-klasse

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

Gelinkte lijsten - LinkedList-klasse

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

Gelinkte lijsten - methoden

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

Gelinkte lijsten - insert_at_beginning

De weergave van een enkelvoudig gelinkte lijst.

Gelinkte lijsten - insert_at_beginning

De weergave van een enkelvoudig gelinkte lijst en een nieuwe knoop,

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

    if self.head:

Gelinkte lijsten - insert_at_beginning

De weergave van een enkelvoudig gelinkte lijst met de nieuwe knoop verbonden.

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

Gelinkte lijsten - insert_at_beginning

De weergave van een enkelvoudig gelinkte lijst met de nieuwe knoop verbonden en het woord "HEAD" in deze knoop.

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

Gelinkte lijsten - insert_at_beginning

De weergave van een nieuwe knoop in een lege gelinkte lijst.

 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

Gelinkte lijsten - 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

Gelinkte lijsten - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

De weergave van een enkelvoudig gelinkte lijst met het woord "current_node" dat naar de eerste knoop wijst.

Gelinkte lijsten - 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

De weergave van een enkelvoudig gelinkte lijst met het woord "current_node" dat naar de tweede knoop wijst.

Gelinkte lijsten - 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

De weergave van een enkelvoudig gelinkte lijst met het woord "current_node" dat naar de derde knoop wijst.

Gelinkte lijsten - voorbeeld

De weergave van een nieuwe knoop in een lege gelinkte lijst.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Gelinkte lijsten - voorbeeld

De weergave van een nieuwe knoop die aan het einde van een gelinkte lijst is toegevoegd.

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

Gelinkte lijsten - voorbeeld

De weergave van een nieuwe knoop die aan het begin van een gelinkte lijst is toegevoegd.

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

Gelinkte lijsten - voorbeeld

De weergave van een gelinkte lijst.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Laten we oefenen!

Datastructuren en algoritmen in Python