Witamy!

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software Engineer

Znaczenie algorytmów i struktur danych

• Struktury danych i algorytmy pozwalają
  • rozwiązywać codzienne problemy
  • przy użyciu wydajnego kodu
• Kurs można realizować w dowolnym języku programowania

Algorytmy i struktury danych

• Algorytm: zbiór instrukcji rozwiązujących problem

  1. Projektowanie

     

  2. Kod

     

• Struktury danych: przechowują dane i operują na nich podczas wykonywania algorytmu
  • Zaawansowane struktury danych: listy powiązane, stosy, kolejki...

Listy powiązane

• Sekwencja danych połączonych łączami

Listy powiązane – struktura

Listy powiązane – struktura

Listy powiązane – struktura

Listy powiązane – struktura

Listy powiązane – struktura

Listy powiązane – struktura

Listy powiązane – struktura

Listy powiązane – struktura

• Dane nie muszą być przechowywane w ciągłych blokach pamięci
• Dane mogą znajdować się pod dowolnym wolnym adresem pamięci

Listy jednokierunkowe

• Jedno łącze: lista jednokierunkowa

Listy dwukierunkowe

• Dwa łącza w obu kierunkach: lista dwukierunkowa

Listy powiązane – zastosowania

• Implementacja innych struktur danych:
  • stosy
  • kolejki
  • grafy
• Dostęp do informacji przez nawigację wstecz i wprzód
  • przeglądarka internetowa
  • lista odtwarzania muzyki

Listy powiązane – klasa Node

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

Listy powiązane – klasa LinkedList

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

Listy powiązane – metody

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

Listy powiązane – insert_at_beginning

Listy powiązane – insert_at_beginning

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

    if self.head:

Listy powiązane – insert_at_beginning

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

Listy powiązane – 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

Listy powiązane – 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

Listy powiązane – 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

Listy powiązane – search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Listy powiązane – 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

Listy powiązane – 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

Listy powiązane – przykład

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Listy powiązane – przykład

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

Listy powiązane – przykład

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

Listy powiązane – przykład

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie