Välkommen!

Datastrukturer och algoritmer i Python

Miriam Antona

Software Engineer

Vikten av algoritmer och datastrukturer

• Datastrukturer och algoritmer gör det möjligt att
  • lösa vardagliga problem
  • med effektiv kod
• Kursen kan ges i vilket programmeringsspråk som helst

Algoritmer och datastrukturer

• Algoritm: en uppsättning instruktioner som löser ett problem

  1. Design

     

  2. Kod

     

• Datastrukturer: lagrar och hanterar data när vi kör en algoritm
  • Avancerade datastrukturer: länkade listor, stackar, köer...

Länkade listor

• En sekvens av data som är sammankopplad via länkar

Länkade listor – struktur

Länkade listor – struktur

Länkade listor – struktur

Länkade listor – struktur

Länkade listor – struktur

Länkade listor – struktur

Länkade listor – struktur

Länkade listor – struktur

• Data behöver inte lagras i sammanhängande minnesblock
• Data kan finnas på valfri ledig minnesadress

Enkellänkade listor

• En länk: enkellänkad lista

Dubbellänkade listor

• Två länkar i vardera riktning: dubbellänkad lista

Länkade listor – praktiska användningsområden

• Implementera andra datastrukturer:
  • stackar
  • köer
  • grafer
• Navigera bakåt och framåt i information
  • webbläsare
  • musikspellistor

Länkade listor – Node-klassen

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

Länkade listor – LinkedList-klassen

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

Länkade listor – metoder

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

Länkade listor – insert_at_beginning

Länkade listor – insert_at_beginning

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

    if self.head:

Länkade listor – insert_at_beginning

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

Länkade listor – 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

Länkade listor – 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

Länkade listor – 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

Länkade listor – search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Länkade listor – 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

Länkade listor – 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

Länkade listor – exempel

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Länkade listor – exempel

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

Länkade listor – exempel

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

Länkade listor – exempel

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Nu kör vi en övning!

Datastrukturer och algoritmer i Python