1 of 40

Operações sobre Coleções de Objetos

2 of 40

A classe Estudante a seguir será usada nesta aula...

from datetime import date

​

class Estudante:

​

def __init__(self,nome,matricula,anoNascimento):

self.nome = nome

# a matrícula será a chave

self.matricula = matricula

self.anoNascimento = anoNascimento

​

def idade(self):

anoAtual = date.today().year

idade = anoAtual - self.anoNascimento

return idade

3 of 40

CRUD

  • Numa coleção de estudantes, como em qualquer coleção de dados, o usuário do programa vai querer manipular os dados.
  • Esta manipulação de dados é o que chamamos de CRUD.

4 of 40

CRUD

São as operações típicas de manipulação de dados

  • (C)REATE
    • Criar, cadastrar, adicionar, inserir
  • (R)ETRIEVE
    • Recuperar, consultar, visualizar, ler
  • (U)PDATE
    • Atualizar, modificar, alterar, editar
  • (D)ELETE
    • Remover, apagar, deletar, excluir, eliminar

​

​

​

5 of 40

Busca

Em muitas situações, é normal ter de realizar uma busca antes de realizar a operação de CRUD

  • CREATE
    • Pode ser preciso localizar a posição na coleção onde o dado será armazenado. Além disso, deve-se evitar criar um objeto com chave já existente
  • RETRIEVE
    • É preciso localizar o dado antes de consultá-lo
  • UPDATE
    • É preciso localizar o dado antes de alterá-lo
  • DELETE
    • É preciso localizar o dado antes de removê-lo

6 of 40

Operando sobre coleções de objetos

Para cada uma das operações do CRUD e, adicionalmemente, para a busca, vamos projetar algoritmos e programas para realizá-las

  • Algoritmo Ingênuo
    • Apresenta uma sequência típica de suboperações da operação, sem tratar situações particulares.
  • Algoritmo Melhorado
    • Algoritmo que resolve o problema da operação completamente tratando os casos particulares.
  • Programa em Python
    • Implementação do algoritmo melhorado, geralmente na forma de uma função e de um programa principal que utiliza esta função.

7 of 40

Coleções Típicas de Objetos

É normal encontrarmos em sistemas de informação três coleções típicas de objetos:

  • Listas Não Ordenadas de Objetos
    • São coleções acessíveis por índices numéricos, sem nenhuma ordenação específica
  • Listas Ordenadas de Objetos
    • São coleções acessíveis por índices numéricos, mas ordenadas por um dos atributos (chave)
  • Dicionários de Objetos
    • São coleções acessíveis através de chaves, podendo ser ordenados ou não

​

​

8 of 40

BUSCA (SEARCH)

9 of 40

Busca: Algoritmo Ingênuo

  1. Entre com a chave do objeto.
  2. Localize a chave na coleção.
  3. Retorne o índice do objeto ou o objeto.

10 of 40

Busca: Algoritmo Melhorado

  1. Entre com a chave do objeto.
  2. Localize a chave na coleção.
  3. Se encontrar a chave
    1. Retorne o índice do objeto ou o objeto.
  4. Se não encontrar a chave
    • Retorne um índice inválido ou um objeto nulo

11 of 40

Busca: Programa em Python com uma lista não ordenada

# retorne o índice do objeto na lista

# ou -1 se não encontrar

def buscar(lista, chave):

# lista não ordenada pede uma busca linear

for i in range(len(lista)):

if (lista[i].matricula == chave):

return i

return -1

​

# Programa principal

estudantes = []

# Suponha que a lista estudantes já foi preenchida

chave = int(input("Entre com a matrícula do estudante: "))

indice = buscar(estudantes, chave)

if (indice > -1):

print("Achei o estudante na posição %d." % indice)

else:

print("Não há estudante com esta matrícula!")

12 of 40

Busca: Programa em Python com uma lista ordenada

def buscaBinaria(lista, chave, inicio, final):

while inicio <= final:

meio = (inicio + final)//2

if lista[meio].matricula == chave:

return meio

elif lista[meio].matricula < chave:

inicio = meio + 1

else:

final = meio - 1

return -1

def buscar(lista, chave):

# lista ordenada pede uma busca binária

return buscaBinaria(lista, chave, 0, len(lista)-1)

estudantes = []

# Suponha que a lista estudantes já foi preenchida

chave = int(input("Entre com a matrícula do estudante: "))

indice = buscar(estudantes, chave)

if (indice > -1):

print("Achei o estudante na posição %d." % indice)

else:

print("Não há estudante com esta matrícula!")

13 of 40

Busca: Programa em Python com um dicionário

​

# retorne o objeto no dicionário

# ou None se não encontrar

def buscar(dicionario, chave):

return dicionario.get(chave)

​

# Programa principal

estudantes = {}

# Suponha que o dicionário estudantes já foi preenchido

​

chave = int(input("Entre com a matrícula do estudante: "))

elemento = buscar(estudantes, chave)

if (elemento):

print("Achei o estudante pela matrícula.")

else:

print("Não há estudante com esta matrícula!")

14 of 40

CADASTRO (CREATE)

15 of 40

Cadastro: Algoritmo Ingênuo

  1. Crie o objeto.
  2. Entre com os dados do objeto.
  3. Encontre a posição do objeto na coleção
  4. Adicione o objeto na coleção.

16 of 40

Cadastro: Algoritmo Melhorado

  1. Busque pela chave se o objeto já não foi cadastrado anteriormente na coleção
  2. Se não encontrar a chave:
    1. Crie o objeto.
    2. Entre com os dados do objeto.
    3. Encontre a posição do objeto na coleção
    4. Adicione o objeto na coleção.
    5. Retorne sucesso
  3. Se encontrar a chave:
    • Retorne falha

17 of 40

Cadastro: Programa em Python com uma lista não ordenada

def cadastrar(lista, nome, matricula, anoNascimento):

if buscar(lista, matricula) == -1:

estudante = Estudante(nome,matricula,anoNascimento)

lista.append(estudante)

return True

else:

return False

​

# Programa principal

estudantes = []

if cadastrar(estudantes, 'Pedro', 123, 1995):

print('Pedro cadastrado.')

if cadastrar(estudantes, 'Paulo', 234, 1998):

print('Paulo cadastrado.')

if cadastrar(estudantes, 'Lucas', 123, 1999):

print('Lucas cadastrado.')

else:

print('Erro no cadastro de Lucas. Matrícula existente.')

18 of 40

Cadastro: Programa em Python com uma lista ordenada

def cadastrar(lista, nome, matricula, anoNascimento):

if buscar(lista, matricula) == -1:

estudante = Estudante(nome, matricula, anoNascimento)

i = 0

while (i < len(lista)):

if matricula < lista[i].matricula:

break

i += 1

lista.insert(i, estudante)

return True

else:

return False

# Programa principal

estudantes = []

if cadastrar(estudantes, 'Pedro', 123, 1995):

print('Pedro cadastrado.')

if cadastrar(estudantes, 'Paulo', 234, 1998):

print('Paulo cadastrado.')

if cadastrar(estudantes, 'Madalena', 197, 1998):

print('Madalena cadastrada.')

if cadastrar(estudantes, 'Lucas', 123, 1999):

print('Lucas cadastrado.')

else:

print('Erro no cadastro de Lucas. Matrícula existente.')

19 of 40

Cadastro: Programa em Python com um dicionário

def cadastrar(dicionario, nome, matricula, anoNascimento):

if dicionario.get(matricula):

return False

estudante = Estudante(nome, matricula, anoNascimento)

dicionario[matricula] = estudante

return True

​

# Programa principal

estudantes = {}

if cadastrar(estudantes, 'Pedro', 123, 1995):

print('Pedro cadastrado.')

if cadastrar(estudantes, 'Paulo', 234, 1998):

print('Paulo cadastrado.')

if cadastrar(estudantes, 'Lucas', 123, 1999):

print('Lucas cadastrado.')

else:

print('Erro no cadastro de Lucas. Matrícula existente.')

20 of 40

CONSULTA (RETRIEVE)

21 of 40

Consulta: Algoritmo Ingênuo

  1. Entre com a chave do objeto.
  2. Faça uma busca com a chave e retorne o índice do objeto ou o objeto.
  3. Mostre o objeto.

22 of 40

Consulta: Algoritmo Melhorado

  1. Entre com a chave do objeto.
  2. Faça uma busca com a chave e retorne o índice do objeto ou o objeto.
  3. Se encontrou o objeto:
    1. Mostre o objeto
  4. Se não encontrou o objeto:
    • Mostre uma mensagem de erro

23 of 40

Consulta: Programa em Python com uma lista não ordenada ou com uma lista ordenada

def mostrarEstudante(estudante):

print("Dados do estudante: ")

print("Matrícula: %d" % estudante.matricula)

print("Nome: %s" % estudante.nome)

print("Nascimento: %d" % estudante.anoNascimento)

print("Idade: %d\n\n" % estudante.idade())

​

def consultar(lista, chave):

indice = buscar(lista, chave)

if indice != -1:

mostrarEstudante(lista[indice])

else:

print("Matrícula %d não encontrada.\n\n" % chave)

​

# Programa principal

estudantes = []

cadastrar(estudantes, 'Pedro', 123, 1995)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

consultar(estudantes, 345)

consultar(estudantes, 111)

24 of 40

Consulta: Programa em Python com um dicionário

def mostrarEstudante(estudante):

print("Dados do estudante: ")

print("Matrícula: %d" % estudante.matricula)

print("Nome: %s" % estudante.nome)

print("Nascimento: %d" % estudante.anoNascimento)

print("Idade: %d\n\n" % estudante.idade())

​

def consultar(dicionario, chave):

estudante = buscar(dicionario, chave)

if estudante:

mostrarEstudante(estudante)

else:

print("Matrícula %d não encontrada.\n\n" % chave)

​

# Programa principal

estudantes = {}

cadastrar(estudantes, 'Pedro', 123, 1995)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

consultar(estudantes, 345)

consultar(estudantes, 111)

25 of 40

ALTERAÇÃO (UPDATE)

26 of 40

Alteração: Algoritmo Ingênuo

  1. Entre com a chave do objeto.
  2. Faça uma busca com a chave e retorne o índice do objeto ou o objeto.
  3. Altere o objeto.

27 of 40

Alteração: Algoritmo Melhorado

  1. Entre com a chave do objeto.
  2. Faça uma busca com a chave e retorne o índice do objeto ou o objeto.
  3. Se encontrou o objeto:
    1. Se a chave vai mudar com a alteração:
      1. Verifique se precisa alterar a chave na coleção
    2. Altere o objeto
  4. Se não encontrou o objeto:
    • Mostre uma mensagem de erro

28 of 40

Alteração: Programa em Python com uma lista não ordenada ou com uma lista ordenada

def alterar(lista, chave, nome, matricula, anoNascimento):

indice = buscar(lista, chave)

if indice != -1:

estudante = lista[indice]

estudante.nome = nome

estudante.matricula = matricula

estudante.anoNascimento = anoNascimento

print("Alteração realizada.")

mostrarEstudante(lista[indice]) // opcional

else:

print("Matrícula %d não encontrada.\n\n" % chave)

​

# Programa principal

estudantes = []

cadastrar(estudantes, 'Pedro', 123, 1992)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

consultar(estudantes, 123)

alterar(estudantes, 123, 'Pedro Santos', 101, 1995)

alterar(estudantes, 200, 'Paulo Silva', 102, 1998)

29 of 40

Alteração: Programa em Python com um dicionário

def alterar(dicionario,chave,nome,matricula,anoNascimento):

estudante = buscar(dicionario, chave)

if estudante:

if chave != matricula:

estudante = dicionario.pop(chave)

dicionario[matricula] = estudante

estudante.nome = nome

estudante.matricula = matricula

estudante.anoNascimento = anoNascimento

print("Alteração realizada.")

mostrarEstudante(dicionario[matricula])

else:

print("Matrícula %d não encontrada.\n\n" % chave)

# Programa principal

estudantes = {}

cadastrar(estudantes, 'Pedro', 123, 1992)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

consultar(estudantes, 123)

alterar(estudantes, 123, 'Pedro Santos', 101, 1995)

alterar(estudantes, 200, 'Paulo Silva', 102, 1998)

30 of 40

REMOÇÃO (DELETE)

31 of 40

Remoção: Algoritmo Ingênuo

  1. Entre com a chave do objeto.
  2. Faça uma busca com a chave e retorne o índice do objeto ou o objeto.
  3. Remova o objeto.

32 of 40

Remoção: Algoritmo Melhorado

  1. Entre com a chave do objeto.
  2. Faça uma busca com a chave e retorne o índice do objeto ou o objeto.
  3. Se encontrou o objeto:
    1. Remova o objeto
  4. Se não encontrou o objeto:
    • Mostre uma mensagem de erro

33 of 40

Remoção: Programa em Python com uma lista não ordenada ou com uma lista ordenada

def remover(lista, chave):

indice = buscar(lista, chave)

if indice != -1:

lista.pop(indice)

print("Remoção realizada.\n\n")

else:

print("Erro na remoção: Matrícula %d não encontrada.\n\n" % chave)

​

# Programa principal

estudantes = []

cadastrar(estudantes, 'Pedro', 123, 1992)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

consultar(estudantes, 123)

remover(estudantes, 123)

consultar(estudantes, 123)

remover(estudantes, 200)

34 of 40

Remoção: Programa em Python com um dicionário

def remover(dicionario, chave):

estudante = buscar(dicionario, chave)

if estudante:

dicionario.pop(chave)

print("Remoção realizada.\n\n")

else:

print("Erro na remoção: Matrícula %d não encontrada.\n\n" % chave)

​

# Programa principal

estudantes = {}

cadastrar(estudantes, 'Pedro', 123, 1992)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

consultar(estudantes, 123)

remover(estudantes, 123)

consultar(estudantes, 123)

remover(estudantes, 200)

35 of 40

ORDENAÇÃO DE COLEÇÕES DE OBJETOS

36 of 40

Ordenação de uma Lista de Objetos

  • A ordenação de uma lista de objetos é essencialmente similar à ordenação de uma lista de inteiros
  • As únicas diferenças são:
    • A comparação será feita pela chave de ordenação desejada do objeto
    • Ao trocar elementos, devem ser trocados os objetos

37 of 40

tamanho = len(lista)

for i in range(0, tamanho-1):

min = i

for j in range(i+1, tamanho):

//Encontra o menor

if (lista[j] < lista [min]):

min = j

lista[i], lista[min] = lista[min], lista[i]

Relembrando o Selection Sort ou Ordenação por Seleção

Dada uma lista chamada lista e seja tamanho o tamanho da lista...

38 of 40

Ordenação por Seleção: Programa em Python que ordena por matrícula uma lista não ordenada

def selectionSortPorMatricula(lista):

tamanho = len(lista)

for i in range(0, tamanho-1):

min = i

for j in range(i+1, tamanho):

# Encontra o menor

if (lista[j].matricula < lista[min].matricula):

min = j

lista[i], lista[min] = lista[min], lista[i]

# Programa principal

estudantes = []

cadastrar(estudantes, 'Marcos', 789, 1997)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

cadastrar(estudantes, 'Lucas', 456, 1999)

cadastrar(estudantes, 'Pedro', 123, 1995)

cadastrar(estudantes, 'João', 567, 2001)

for estudante in estudantes:

mostrarEstudante(estudante)

print("\n\nORDENANDO POR MATRÍCULA: \n")

selectionSortPorMatricula(estudantes)

for estudante in estudantes:

mostrarEstudante(estudante)

39 of 40

Ordenação por Seleção: Programa em Python que ordena por nome uma lista não ordenada

def selectionSortPorNome(lista):

tamanho = len(lista)

for i in range(0, tamanho-1):

min = i

for j in range(i+1, tamanho):

# Encontra o menor

if (lista[j].nome < lista[min].nome):

min = j

lista[i], lista[min] = lista[min], lista[i]

# Programa principal

estudantes = []

cadastrar(estudantes, 'Marcos', 789, 1997)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

cadastrar(estudantes, 'Lucas', 456, 1999)

cadastrar(estudantes, 'Pedro', 123, 1995)

cadastrar(estudantes, 'João', 567, 2001)

for estudante in estudantes:

mostrarEstudante(estudante)

print("\n\nORDENANDO POR MATRÍCULA: \n")

selectionSortPorNome(estudantes)

for estudante in estudantes:

mostrarEstudante(estudante)

40 of 40

Ordenação por Seleção: Programa em Python que apresenta um dicionário ordenado por matrícula

def selectionSortPorMatricula(lista):

tamanho = len(lista)

for i in range(0, tamanho-1):

min = i

for j in range(i+1, tamanho):

# Encontra o menor

if (lista[j] < lista[min]):

min = j

lista[i], lista[min] = lista[min], lista[i]

def retornarChavesOrdenadasPorMatricula(dicionario):

chaves = list(dicionario.keys())

selectionSortPorMatricula(chaves)

return chaves

# Programa principal

estudantes = {}

cadastrar(estudantes, 'Marcos', 789, 1997)

cadastrar(estudantes, 'Madalena', 345, 1987)

cadastrar(estudantes, 'Paulo', 234, 1998)

cadastrar(estudantes, 'Lucas', 456, 1999)

cadastrar(estudantes, 'Pedro', 123, 1995)

cadastrar(estudantes, 'João', 567, 2001)

for chave in estudantes:

mostrarEstudante(estudantes[chave])

print("\n\nAPRESENTANDO OS ESTUDANTES ORDENADOS POR MATRÍCULA:\n")

chaves = retornarChavesOrdenadasPorMatricula(estudantes)

for chave in chaves:

mostrarEstudante(estudantes[chave])