Ласкаво просимо!

Структури даних і алгоритми в Python

Miriam Antona

Software Engineer

Важливість алгоритмів і структур даних

• Структури даних та алгоритми дають змогу
  • розв'язувати щоденні задачі
  • за допомогою ефективного коду
• Курс можна викладати будь-якою мовою програмування

Алгоритми та структури даних

• Алгоритм: набір інструкцій для розв'язання задачі

  1. Проєктування

     

  2. Кодування

     

• Структури даних: зберігають і опрацьовують дані під час виконання алгоритму
  • Складні структури даних: зв'язані списки, стеки, черги...

Зв'язані списки

• Послідовність даних, з'єднаних посиланнями

Зв'язані списки — структура

Зв'язані списки — структура

Зв'язані списки — структура

Зв'язані списки — структура

Зв'язані списки — структура

Зв'язані списки — структура

Зв'язані списки — структура

Зв'язані списки — структура

• Дані не обов'язково зберігати в суміжних блоках пам'яті
• Дані можуть бути в будь-якій доступній адресі пам'яті

Односпрямовані зв'язані списки

• Одне посилання: односпрямований зв'язаний список

Двоспрямовані зв'язані списки

• Два посилання в обох напрямках: двоспрямований зв'язаний список

Зв'язані списки — практичні застосування

• Реалізують інші структури даних:
  • стеки
  • черги
  • графи
• Доступ до інформації шляхом переходів назад і вперед
  • веббраузер
  • музичний плейлист

Зв'язані списки — клас Node

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

Зв'язані списки — клас LinkedList

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

Зв'язані списки — методи

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

Зв'язані списки — insert_at_beginning

Зв'язані списки — insert_at_beginning

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

    if self.head:

Зв'язані списки — insert_at_beginning

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

Зв'язані списки — 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

Зв'язані списки — 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

Зв'язані списки — 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

Зв'язані списки — search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Зв'язані списки — 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

Зв'язані списки — 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

Зв'язані списки — приклад

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Зв'язані списки — приклад

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

Зв'язані списки — приклад

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

Зв'язані списки — приклад

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Давайте потренуємось!

Структури даних і алгоритми в Python