Willkommen!

Datenstrukturen und Algorithmen in Python

Miriam Antona

Software Engineer

Warum Algorithmen und Datenstrukturen wichtig sind

• Datenstrukturen und Algorithmen helfen uns,
  • Alltagsprobleme zu lösen
  • mit effizientem Code
• Der Kurs kann in jeder Programmiersprache vermittelt werden

Algorithmen und Datenstrukturen

• Algorithmus: Folge von Anweisungen zur Lösung eines Problems

  1. Design

     

  2. Code

     

• Datenstrukturen: halten und verarbeiten Daten während der Ausführung eines Algorithmus
  • Fortgeschrittene Datenstrukturen: verkettete Listen, Stacks, Queues ...

Verkettete Listen

• Abfolge von Daten, verbunden durch Links

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

Verkettete Listen – Aufbau

• Daten müssen nicht in zusammenhängenden Speicherblöcken liegen
• Daten können an beliebigen Speicheradressen liegen

Einfach verkettete Listen

• Ein Link: einfach verkettete Liste

Doppelt verkettete Listen

• Zwei Links in beide Richtungen: doppelt verkettete Liste

Verkettete Listen – echte Anwendungen

• Andere Datenstrukturen umsetzen:
  • Stacks
  • Queues
  • Graphen
• Infos vor- und rückwärts durchlaufen
  • Webbrowser
  • Musik-Playlist

Verkettete Listen – Klasse Node

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

Verkettete Listen – Klasse LinkedList

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

Verkettete Listen – Methoden

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

Verkettete Listen – insert_at_beginning

Verkettete Listen – insert_at_beginning

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

    if self.head:

Verkettete Listen – insert_at_beginning

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

Verkettete Listen – 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

Verkettete Listen – 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

Verkettete Listen – 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

Verkettete Listen – search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Verkettete Listen – 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

Verkettete Listen – 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

Verkettete Listen – Beispiel

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Verkettete Listen – Beispiel

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

Verkettete Listen – Beispiel

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

Verkettete Listen – Beispiel

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Lass uns üben!

Datenstrukturen und Algorithmen in Python