Bem-vindo(a)!

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software Engineer

A importância de algoritmos e estruturas de dados

Estruturas de dados e algoritmos nos ajudam a
- resolver problemas do dia a dia
- com código eficiente
O curso pode ser dado em qualquer linguagem

Algoritmos e estruturas de dados

Algoritmo: conjunto de instruções para resolver um problema
1. Design
2. Código

Estruturas de dados: guardam e manipulam dados durante a execução do algoritmo
- Avançadas: listas ligadas, pilhas, filas...

Listas ligadas

Um exemplo visual de uma lista ligada com etapas para preparar pão.

Sequência de dados conectados por links

Listas ligadas - estrutura

A representação de um nó em uma lista ligada.

Listas ligadas - estrutura

A representação de um nó em uma lista ligada com a palavra "DATA" na primeira parte.

Listas ligadas - estrutura

A representação de um nó em uma lista ligada com as palavras "DATA" na primeira parte e "NEXT" com um ponteiro na segunda.

Listas ligadas - estrutura

A representação de dois nós de uma lista ligada conectados por um link.

Listas ligadas - estrutura

A representação de vários nós de uma lista ligada conectados por links.

Listas ligadas - estrutura

A representação de uma lista ligada em que o último nó aponta para null.

Listas ligadas - estrutura

A representação de uma lista ligada com a palavra "HEAD" no primeiro nó.

Listas ligadas - estrutura

A representação de uma lista ligada com a palavra "TAIL" no último nó.

Os dados não precisam estar em blocos contíguos de memória
Podem estar em qualquer endereço disponível

Listas simplesmente ligadas

A representação de uma lista simplesmente ligada.

Um link: lista simplesmente ligada

Listas duplamente ligadas

A representação de uma lista duplamente ligada.

Dois links em cada direção: lista duplamente ligada

Listas ligadas - usos reais

Implementar outras estruturas:
- pilhas
- filas
- grafos
Acessar info navegando pra trás e pra frente
- navegador
- playlist de música

Listas ligadas - classe Node

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

Listas ligadas - classe LinkedList

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

Listas ligadas - métodos

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

Listas ligadas - insert_at_beginning

A representação de uma lista simplesmente ligada.

Listas ligadas - insert_at_beginning

A representação de uma lista simplesmente ligada e um novo nó,

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

    if self.head:

Listas ligadas - insert_at_beginning

A representação de uma lista simplesmente ligada com o novo nó conectado.

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

Listas ligadas - insert_at_beginning

A representação de uma lista simplesmente ligada com o novo nó conectado e a palavra "HEAD" nesse nó.

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

Listas ligadas - insert_at_beginning

A representação de um novo nó em uma lista ligada vazia.

 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

Listas ligadas - 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

Listas ligadas - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

A representação de uma lista simplesmente ligada com a palavra "current_node" apontando para o primeiro nó.

Listas ligadas - 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

A representação de uma lista simplesmente ligada com a palavra "current_node" apontando para o segundo nó.

Listas ligadas - 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

A representação de uma lista simplesmente ligada com a palavra "current_node" apontando para o terceiro nó.

Listas ligadas - exemplo

A representação de um novo nó em uma lista ligada vazia.

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Listas ligadas - exemplo

A representação de um novo nó adicionado ao final de uma lista ligada.

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

Listas ligadas - exemplo

A representação de um novo nó adicionado ao começo de uma lista ligada.

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

Listas ligadas - exemplo

A representação de uma lista ligada.

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Vamos praticar!

Estruturas de Dados e Algoritmos em Python