Добро пожаловать!

Структуры данных и алгоритмы на 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

Связные списки – поиск

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Связные списки – поиск

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

Связные списки – поиск

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