03 Estruturas de dados
Estruturas de dados: listas¶
condição = True
if condição:
print("Executado porque a condição é verdadeira")
condição = False
if condição:
print("Executado porque a condição é verdadeira")
# Nada foi impresso porque a condição é falsa
Existe uma outra forma da expressão if. Se a condição for verdadeira, funciona igual. Caso contrário executa a parte do else:
condição = False
if condição:
print("Executando porque a condição é verdadeira")
else:
print("Executando porque a condição é FALSA")
Algumas vezes queremos escolher mais de uma condição.
Para isso temos o elif.
Com isso o if vai verificar cada condição sequencialmente.
Quando alguma das condições for verdadeira (True).
cond1 = False
cond2 = False
cond3 = False
cond4 = True
if cond1:
print("cond1")
elif cond2:
print("cond2")
elif cond3:
print("cond3")
elif cond4:
print("cond4")
else:
print("Nada foi verdadeiro")
Detalhe importante:¶
Até este momento associei if a expressões condicionais. Este é o jeito mais seguro e comum de usar. Na verdade, if (e elif) considera algo verdadeiro se não foi 0, False ou estrutura de dados vazia (veremos estruturas de dados hoje). O resto é verdade
if 0:
print("TRUE")
else:
print("FALSE")
Repetições¶
Mostramos como se repete alguma operação com Python. O mecanismo mais básico é a expressão while:
while condição:
# Executar este bloco
# enquanto condição for verdadeira
Enquanto a condição for verdadeira, o bloco vai ser executado. Por isso é importante que se faça algo para tornar a condição falsa de modo a interromper o laço.
i = 1
while i <= 5:
print(i)
i = i + 1
Algo que não foi falado é que você pode interromper
em qualquer lugar a execução do laço com a expressão break.
i = 1
while True:
if i > 5:
break
print(i)
i = i + 1
Em várias linguagens de programação existem mecanismos para se criar laços onde o teste está no final, de modo que o corpo do laço seja executado pelo menos uma vez. Em C, isso seria os laços do - while. Não existe nada parecido em Python. Mas isso não é necessário, basta usar o break
i = 1
while True:
print(i)
i = i + 1
if i > 5: break
Muitas vezes você não quer sair do laço
mas simplesmente ir para a próxima iteração.
Para isso existe a expressão continue
i = 0
while i < 5:
i = i + 1
if i == 3:
continue
print(i)
Estrtuturas de dados¶
Até este momento, vimos a criação de variáveis que armazenavam números (inteiros ou de ponto flutuante) ou strings. E se quisermos trabalhar com uma quantidade variável de números (ou strings)? Teríamos que criar mais de uma variável. Isso não apenas é chato mas bem limitante. Para isso existem as estruturas de dados que são elementos do Python que permitem armazenar e gerenciar mais de um objeto (números, strings, ou qualquer outra coisa).
O strings são um caso especial pois são uma coleção de caracteres. Mas em geral os strings são tratados como um elemento único.
Listas¶
As listas são um tipo de variável que permitem armazenar vários valores acessados por um índice. A lista pode conter 0 ou mais elementos de qualquer tipo, inclusive outras listas (e outras estruturas de dados).
Assim como os caracteres de uma string, as listas são indexadas por números inteiros começando em 0.
# Uma lista vazia
L = []
print(len(L))
L
Z = [15, 8, 9]
print(Z[0])
print(Z[1])
print(Z[2])
# Erro se o índice não existir
Z[3]
# É possível mudar o valor das variáveis
Z[1] = 123
Z
# Programa para cálculo da média de 5 notas
notas = [6, 7, 5, 8, 9]
soma = 0
i = 0
while i < 5:
soma += notas[i]
i += 1
print(f"Média: {soma/i:4.1f}")
# Versão do programa onde o professor pode entrar com as notas
notas = [0,0,0,0,0]
soma = 0
i = 0
while i < 5:
notas[i] = float(input(f"Nota {i}: "))
soma += notas[i]
i += 1
print(f"Média: {soma/i:4.1f}")
Exercício 1¶
Modifique os programas acima para ler 7 notas no lugar de 5.
Cópia e fatiamento de listas¶
L = [1,2,3,4,5]
V = L
L
V
V[0] = 999
V
L
L = [1,2,3,4,5]
V = L[:]
V[0] = 999
V
L
Fatiamento de listas¶
Lembra do fatiamento de strings? Listas funcionam de maneira bem parecida
s = "ABCDEF"
s[:]
L = [1,2,3,4,5]
L[0:5]
L[0:3]
L[2:]
L[:2]
L[1:4]
Tamanho de listas¶
A função len retorna o número de elementos de uma lista.
len([])
len([1])
len([1,2,3])
len(L)
Lembra do programa para tirar a média? Com len dá para melhorar!
# Programa para cálculo da média de 5 notas
notas = [6, 7, 5, 8, 9]
soma = 0
i = 0
while i < len(notas):
soma += notas[i]
i += 1
print(f"Média: {soma/i:4.1f}")
Adicionando elementos a uma lista¶
As listas podem crescer de acordo com a conveniência. Para adicionar um elemento a uma lista, basta usar o método append.
Um método parece com uma função (como len) mas está associado ao objeto. Em python, as variáveis armazenam objetos que podem ser números, strings, listas, e um monte de outras coisas.
Funções recebem (entre parênteses) objetos e retornam um outro objeto. Mas métodos estão associados a estes objetos, são parte intrínseca dos objetos. No final do curso vamos ver em detalhes como isso funciona. Mas por enquanto, vamos aprender a utilizá-los.
Dica de como ver os métodos disponíveis¶
Se você tiver alguma variável, digite seu nome, digite ponto (sem espaço!) e pressione a tecla TAB. Vai aparecer uma lista com os métodos disponíveis para a variável.
x = []
L = []
L.append("a")
L
L.append("b")
L
L.append("c")
len(L)
L.append([1,2,3])
L
# Programa para adicionar números a uma lista
L = []
while True:
n = int(input("Digite um número (0 sai): "))
if n == 0:
break
L.append(n)
L
Vocês se lembram da concatenação de strings?¶
A mesma coisa é possível com listas. Apenas com listas!
[1,2,3] + [4]
[1,2,3] + [4,5,6]
[1,2,3] + 4
O método append adiciona elementos novos à lista.
Já o método extend funciona como a concatenação acima.
L = [1,2,3]
L.append(4)
L
L.append([5,6])
L
L.extend([7,8])
L
Exercício 2¶
Reescreva o programa para calcular médias de modo que o professor primeiro entra com o número de notas e em seguida o programa lê este número de notas e calcula a média.
Exercício 3¶
Faça um programa que percorra duas listas inteiras e gere uma terceira sem elementos repetidos
Remoção de elementos da lista¶
Algumas vezes você quer remover elementos da lista. Isso é feito com a instrução del:
L = [1,2,3]
del L[1]
L
L = list(range(101))
del L[10:90]
L
x = list(range(11))
x.pop(5)
x
Filas¶
Uma lista pode ser utilizada como uma fila. Numa fila as pessoas entram no final e saem no começo. Na literatura a fila é conhecida como FIFO (First In First Out, primeiro que entra primeiro que sai). É uma estrutura de dados muito útil em diversas situações.
Como exemplo vamos simular uma fila de banco:
# Simulação de fila de banco:
último = 10
fila = list(range(1, último + 1))
while True:
print(f"\nExistem {len(fila)} clientes na fila")
print(f"Fila atual: {fila}")
print("Digite F para adicionar um cliente ao fim da fila, ")
print("ou A para realizar o atendimento. S para sair.")
operação = input("Operação (F, A ou S): ")
if operação == "A":
if len(fila) > 0:
atendido = fila.pop(0)
print(f"Cliente {atendido} atendido")
else:
print("Fila vazia! Nenhum cliente para atender.")
elif operação == "F":
último += 1 # Incrementa o ticket
fila.append(último)
elif operação == 'S':
break
else:
print("Operação inválida. Digite apenas A, F ou S!")
Exercício 4¶
O que acontece quando não verificamos se a lista está vazia antes de chamar o método pop?
Exercício 5¶
Altere o programa da fila de modo que se possa trabalhar com vários comandos digitados de uma só vez. No programa acima, apenas uma operação pode ser digitada por vez. Faça com que o programa aceite strings com vários comandos
Exemplo: FFFAAAS significa três chegadas de novos clientes, três atendimentos e saída do programa.
Listas como pilhas¶
Uma outra estrutura de dados muito importante é a pilha. Em inglês isso se chama stack. Neste tipo de estrutura, você insere elementos no final e eles saem pelo final. Na literatura, listas são conhecidas como LIFO - Last In First Out (último a entrar é o primeiro a sair).
Nesse caso, para se adicionar um elemento à pilha, usa-se o método append. Para se retirar um elemento da pilha, o método pop sem nenhum argumento (our argumento -1 que indica o último elemento).
# Programa para gerenciar a lavagem de pratos
prato = 5
pilha = list(range(1,prato+1))
while True:
print(f"\nExistem {len(pilha)} pratos na pilha")
print(f"Pilha atual: {pilha}")
print("Digite E para empilhar um novo prato,")
print("ou D para desempilhar e lavar. S para sair.")
operação = input("Operação (E, D ou S): ")
if operação == 'D':
if len(pilha) > 0:
lavado = pilha.pop(-1)
print(f"Prato {lavado} lavado")
else:
print("Pilha vazia, nada para lavar!")
elif operação == 'E':
prato += 1
pilha.append(prato)
elif operação == 'S':
break
else:
print("Operação inválida. Digite apenas E, D ou S!")
Exercício 6¶
Faça um programa que leia uma expressão com parênteses. Usando pilhas, verifique se os parênteses foram abertos e fechados na ordem correta. Exemplo:
- (()) OK
- ()()(()()) OK
- ()) Erro
Pesquisando¶
Uma outra operação importante é pésquisar uma lista e verificar se um elemento é parte dela.
L = [15, 7, 27, 39]
p = int(input("Digite o valor a procurar: "))
achou = False
i = 0
while i < len(L):
if L[i] == p:
achou = True
break
i += 1
if achou:
print(f"{p} foi encontrado na posição {i}.")
else:
print(f"{p} não foi encontrado na lista.")
Exercício 7¶
Modifique o programa de modo que realize a mesma tarefa sem usar a variável achou. Dica: observe a condição de saída do while.
Exercício 8¶
Modifique o exemplo para pesquisar dois valores. Em vez de apenas p, leia outro valor v que também será procurado. Na impressão, indique qual dos dois valores foi encontrado primeiro.
Usando for¶
Para realizar repetições temos usado a instrução while. Repare que muitas vezes a gente quer percorrer uma lista ou um range de números. Isso é tão comum que o python fornece uma instrução de repetição para estes casos: `for.
L = [8,9,15]
for e in L:
print(e)
No exemplo anterior, em cada iteração do laço for, o valor e assume um valor da lista L de maneira sequencial.
O código acima é equivalente ao código a seguir que usa while:
L = [8,9,15]
i = 0
while i < len(L):
e = L[i]
print(e)
i = i + 1
As instruções break e continue funcionam da mesma maneira no laço for.
# Programa de busca
L = [7,9,10,12]
p = int(input("Digite um número a pesquisar: "))
for e in L:
if e == p:
print("Elemento encontrado!")
break
else:
print("Elemento não encontrado")
i = 1
while i < 3:
print(i)
i += 1
else:
print("Terminou")
# Programa para achar o máximo de uma lista:
x = [8, 23, 2, 67, 4]
xmax = x[0]
for e in x:
if e > xmax:
xmax = e
print(f"Valor máximo de {x} é {xmax}")
Exercício 9¶
Tente converter este programa (exemplo acima)
# Programa para adicionar números a uma lista
L = []
while True:
n = int(input("Digite um número (0 sai): "))
if n == 0:
break
L.append(n)
usando for.
Explique se for pode ser sempre usado no lugar de while e porquê.
Range¶
Usamos anteriormente a função range. Esta função cria uma sequência de números e parece ser uma lista mas não é. Sendo uma sequência conhecida, porque gastar memória armazenando todos os elementos?
range(5)
# A função `list` converte para lista:
list(range(5))
# Dá para especificar o valor inicial
list(range(3,10))
# E também dá para escpeficar o intervalo (passo entre valores:)
list(range(3,33,3))
# Mas mais importante, dá para usar nos laços `for`!
for i in range(5):
print(i)
for t in range(3,33,3):
print(t, end=" ") # Repare no `end`
print()
#print("ABCDEF")
enumerate¶
Muitas vezes (quase sempre?) além do valor do elemento na lista, queremos também o índice. Para isso, usamos enumerate
L = [5,9,13]
i = 0
for e in L:
print(f"L[{i}] = {e}")
i += 1
L = [5,9,13]
for i, e in enumerate(L):
print(f"L[{i}] = {e}")
Exercício 10¶
Escreva um programa que acha o menor elemento de uma lista
Exercício 11¶
Modifique o programa para achar o máximo de modo que encontre o máximo mas também encontre o índice onde este máximo ocorre.
Exercício 12¶
Escreva um programa que encontra o máximo e o mínimo de uma lista
Ordenação de listas¶
Colocar a lista em ordem crescente ou descrescente é extremamente importante. Aqui vamos apresentar o método de ordenação de bolhas (bubble sort na literatura)
Qual a idéia do algorítmo? Vamos tomar como exemplo a lista
L = [9, 2, 4, 3, 8, 6]
Começamos a percorrer a lista ordenando a lista par a par
-
[2, 9, 3, 4, 8, 6]
-
[2, 3, 9, 4, 8, 6]
-
[2, 3, 4, 9, 8, 6]
-
[2, 3, 4, 8, 9, 6]
-
[2, 3, 4, 8, 6, 9]
Agora começamos novamente mas não precisamos ir até o final: o maior elemento já está lá!
-
[2, 3, 4, 8, 6, 9] # Não fez nada 2 < 3
-
[2, 3, 4, 8, 6, 9] # Não fez nada 3 < 4
-
[2, 3, 4, 8, 6, 9] # Não fez nada 4 < 8
-
Começamos de novo mas agora só até o penúltimo. Mas agora a lista está ordenada então podemos parar.
[2, 3, 4, 6, 8, 9] # Não fez nada 4 < 8
L = [9, 2, 4, 3, 8, 6]
N = len(L)
for i in range(N):
trocou = False
for k in range(N-i-1):
if L[k] > L[k+1]: # Inverter a posição
trocou = True
tmp = L[k]
L[k] = L[k+1]
L[k+1] = tmp
if not trocou:
break
L
Exercício 13¶
Modifique o programa anterior para que ordene a lista em modo decrescente
?L.sort
Exercício 14¶
O que acontece se você tentar usar o programa acima com uma lista de strings? Tente e brinque um pouquinho.
Por outro lado, o que acontece se misturarmos números e strings?
Exercício 15¶
Um aspecto importante é saber p quão eficiente é este algorítimo. Para tanto, precisamos saber quanto tempo leva para ordenar a lista.
Mas isso vai depender do tamanho da lista, do tipo de dados dentro da lista e do computador que está executando o programa. No entanto, para efeito comparativo, podemos estimar o número de operações. Neste caso, podemos falar em quantas comparações foram realizadas (A linha L[k] > L[k+1]). Também é interessante saber quantas inversões foram realizadas. Estime esse custo para os dois seguintes casos:
- Uma lista ordenada de maneira crescente de comprimento N
- Uma lista ordenada de maneira decrescente de comprimento N
Métodos das listas¶
As listas já possuem métodos úteis. Você pode procurar isso na documentação mas também pode ver isso de maneira iterativa no terminal ou no notebook Jupyter. Basta criar uma variável que armazena a lista, digitar esta variável, ponto e pressionar TAB:
x = [2,5,3,8,5,3,5,7,9,]
x.<TAB>
x = [2,5,3,8,5,3,5,7,9,]
x.
?x.
Alguns dos métodos:¶
Se a lista está armazenada em x, temos os seguintes métodos:
-
x.append: adiciona elementos ao final da lista -
x.clear: apaga todos os elementos da lista -
x.copy: copia a lista e os elementos -
x.count: conta o número de ocorrências de um elemento -
x.extend: extende a lista com os elementos de outra lista -
x.index: encontra índice de um elemento -
x.insert: adiciona um elemento na posição antes do índice -
x.pop: remove e retorna o elemento na posição do índice -
x.remove: remove a primeira ocorrência de um valor -
x.reverse: reverte a ordem dos elementos -
x.sort: reordena os elementos da listaEstes métodos são úteis e em geral é recomendado que sejam utilizados: provavelmente são mais rápidos, flexíveis e seguros do que qualquer coisa que você faça.
Exercício 16¶
Explore os métodos das listas
Exercício 17¶
Não são apenas as listas que têm métodos. Números e strings também têm métodos. Explore-os da mesma maneira que você fez com os métodos das listas.
Antecipando o futuro: funções¶
O algorítimo de ordenação pode ser encapsulado numa função. Assim o programa pode ser reutilizado quando for necessário.
def bubble_sort(L):
N = len(L)
for i in range(N):
trocou = False
for k in range(N-i-1):
if L[k] > L[k+1]: # Inverter a posição
trocou = True
tmp = L[k]
L[k] = L[k+1]
L[k+1] = tmp
if not trocou:
break
L = [23,4,5,2,3,6,2345,6,32,345,4]
bubble_sort(L)
L
Comentários
Comments powered by Disqus