Vítejte!

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software Engineer

Význam algoritmů a datových struktur

Datové struktury a algoritmy umožňují
- řešit každodenní problémy
- pomocí efektivního kódu
Kurz lze aplikovat v libovolném programovacím jazyce

Algoritmy a datové struktury

Algoritmus: sada instrukcí řešící daný problém
1. Návrh
2. Kód

Datové struktury: uchovávají a manipulují s daty při provádění algoritmu
- Pokročilé datové struktury: propojené seznamy, zásobníky, fronty…

Propojené seznamy

Vizuální příklad propojeného seznamu obsahujícího kroky přípravy chleba.

Sekvence dat propojená pomocí odkazů

Propojené seznamy – struktura

Znázornění uzlu v propojeném seznamu.

Propojené seznamy – struktura

Znázornění uzlu v propojeném seznamu se slovem „DATA" v první části.

Propojené seznamy – struktura

Znázornění uzlu v propojeném seznamu se slovem „DATA" v první části a „NEXT" s ukazatelem v druhé části.

Propojené seznamy – struktura

Znázornění dvou uzlů propojeného seznamu spojených odkazem.

Propojené seznamy – struktura

Znázornění několika uzlů propojeného seznamu spojených odkazy.

Propojené seznamy – struktura

Znázornění propojeného seznamu, kde poslední uzel ukazuje na null.

Propojené seznamy – struktura

Znázornění propojeného seznamu se slovem „HEAD" v prvním uzlu.

Propojené seznamy – struktura

Znázornění propojeného seznamu se slovem „TAIL" v posledním uzlu.

Data nemusí být uložena v souvislých blocích paměti
Data mohou být umístěna na libovolné dostupné adrese v paměti

Jednosměrně propojené seznamy

Znázornění jednosměrně propojeného seznamu.

Jeden odkaz: jednosměrně propojený seznam

Obousměrně propojené seznamy

Znázornění obousměrně propojeného seznamu.

Dva odkazy v obou směrech: obousměrně propojený seznam

Propojené seznamy – praktické využití

Implementace dalších datových struktur:
- zásobníky
- fronty
- grafy
Přístup k informacím procházením dopředu i dozadu
- webový prohlížeč
- hudební playlist

Propojené seznamy – třída Node

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

Propojené seznamy – třída LinkedList

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

Propojené seznamy – metody

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

Propojené seznamy – insert_at_beginning

Znázornění jednosměrně propojeného seznamu.

Propojené seznamy – insert_at_beginning

Znázornění jednosměrně propojeného seznamu a nového uzlu.

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

    if self.head:

Propojené seznamy – insert_at_beginning

Znázornění jednosměrně propojeného seznamu s připojeným novým uzlem.

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

Propojené seznamy – insert_at_beginning

Znázornění jednosměrně propojeného seznamu s připojeným novým uzlem a slovem „HEAD" v tomto uzlu.

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

Propojené seznamy – insert_at_beginning

Znázornění nového uzlu v prázdném propojeném seznamu.

 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

Propojené seznamy – 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

Propojené seznamy – search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Znázornění jednosměrně propojeného seznamu se slovem „current_node" ukazujícím na první uzel.

Propojené seznamy – 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

Znázornění jednosměrně propojeného seznamu se slovem „current_node" ukazujícím na druhý uzel.

Propojené seznamy – 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

Znázornění jednosměrně propojeného seznamu se slovem „current_node" ukazujícím na třetí uzel.

Propojené seznamy – příklad

Znázornění nového uzlu v prázdném propojeném seznamu.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Propojené seznamy – příklad

Znázornění nového uzlu přidaného na konec propojeného seznamu.

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

Propojené seznamy – příklad

Znázornění nového uzlu přidaného na začátek propojeného seznamu.

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

Propojené seznamy – příklad

Znázornění propojeného seznamu.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Let's practice!

Datové struktury a algoritmy v Pythonu