O Python dispõe de várias estruturas de dados usadas para conjuntos de valores. A mais versátil é a lista, que pode ser escrita como uma lista de valores separados por vírgulas (itens) entre parênteses retos. As listas podem conter itens de tipos diferentes, mas geralmente todos os itens têm o mesmo tipo.
Os valores que compõem uma lista são chamados elementos da lista. Cada elemento é identificado por um índice, que é a posição do elemento na lista. Quando uma lista não tem valores, diz-se vazia e representa-se por [].
Exemplo:
lista=[10,5,6,2,7]
Notas:
A lista acima contém 5 elementos;
Os elementos são identificados pelos índices 0, 1, 2, 3 e 4, respetivamente. Por exemplo, o elemento lista[2] contém o valor 6.
Exemplo:
lista=["a",1,2,"Maria",2.3]
Notas:
A lista contém elementos de vários tipos de dados: strings, inteiros e float;
Este tipo de lista heterogénea, embora admissível no Python, não é muito usado.
Exemplo:
lista=[]
Notas:
A lista acima está vazia;
Usamos esta estratégia quando não sabemos o número de elementos que a lista irá conter;
Posteriormente, podemos adicionar os valores necessários.
Aceder aos valores de uma lista
Para aceder aos valores de uma lista, temos que indicar o nome da lista e a posição do elemento na lista ou a posição inicial e final da fatia de elementos a que queremos aceder.
Exemplo:
>>> lista=[10,5,6,2,7]
>>> print(lista[2])
6
>>> print(lista[2:3])
[6]
>>> print(lista[2:4])
[6, 2]
>>> print(lista[-1])
7
>>> print(lista[2:])
[6, 2, 7]
Notas:
lista[2] - 3º elemento da lista (pois o 1º elemento tem o índice zero);
lista[2:4] - fatia dos elementos com os índices compreendidos no intervalo [2,4[;
lista[-1] - último elemento da lista (contagem a partir do fim);
lista[2:] - fatia a partir da 3ª posição até ao fim.
Exemplo:
notas=[18,15,20]
media=(notas[0]+notas[1]+notas[2])/3
print(media)
Para uma lista de 3 notas, calcula a média. Obviamente que se o número de elementos da lista for grande devemos usar um ciclo.
Exemplo:
notas=[18,15,20]
for i in range(3):
print(notas[i])
18
15
20
Imprime as notas (uma em cada linha) da lista «notas».
Alternativamente:
notas=[18,15,20]
for nota in notas:
print(nota)
18
15
20
Alterar valores de uma lista
Exemplo:
>>> lista
[10, 5, 44, 2, 7]
>>> lista[2]=22
>>> lista
[10, 5, 22, 2, 7]
>>> lista[1]=11
>>> lista
[10, 11, 22, 2, 7]
Nota: os elementos 1 e 2 da lista foram alterados para os valores 11 e 22, respetivamente.
Eliminar valores de uma lista
Exemplo:
>>> lista
[10, 11, 22, 2, 7]
>>> del lista[2]
Nota: elimina o elemento índice 2 da lista.
Leitura de valores para listas
Para inserir valores em listas, via “input”, tenho de começar por criar uma lista vazia e, posteriormente, acrescentar os valores lidos.
Exemplo (ler e imprimir os alunos com as melhores notas):
# Imprime os alunos da turma que tiveram a melhor nota
import math
n=int(input("Quantos alunos tem a turma?"))
# Ler os alunos e notas
nomes=[]
notas=[]
for i in range(n):
nomes.append(input("Digite o nome:"))
notas.append(int(input("Digite a nota:")))
# Determinar a nota máxima
max_nota=-math.inf
for i in range(n):
if notas[i]>max_nota:
max_nota=notas[i]
# Imprimir os alunos com a melhor nota
print("Alunos com as melhores notas")
for i in range(n):
if notas[i]==max_nota:
print(nomes[i])
Comprimento de uma lista
len(lista) - devolve o tamanho da lista.
Exemplo:
>>> idades=[3,1,6,7,10,22,4]
>>> len(idades)
7
É possível concatenar (juntar) os valores de duas listas usando o operador “+”.
Exemplo:
>>> profs=["Paulo","Maria","Miguel"]
>>> alunos=["Rui","Pedro","Marco","Joana"]
>>> profs_alunos=profs+alunos
>>> profs_alunos
['Paulo', 'Maria', 'Miguel', 'Rui', 'Pedro', 'Marco', 'Joana']
O operador * repete n vezes os elementos que já estão na lista, isto é, lista*n equivale a lista+lista+...+lista (n vezes).
Exemplo:
>>> lista=[1,2,3]
>>> lista=lista*3
>>> lista
[1, 2, 3, 1, 2, 3, 1, 2, 3]
Duplica 3 vezes a lista.
Inicialização de listas
Em muitas situações é útil inicializar a lista com um número de elementos preenchidos com um dado valor (por exemplo, zero).
Exemplo:
>>> lista=[0]*10
>>> lista
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Outras funcionalidades disponíveis nas listas
Operador in e not in
Os operadores in e not in, usados no contexto das listas, testam a pertença de uma elemento a uma lista.
Exemplo:
>>> nomes=["Paulo","Rui","Ana"]
>>> "Rui" in nomes
True
>>> "Maria" not in nomes
True
Nota: como "Rui" pertence à lista é devolvido o valor lógico True; como "Maria" não pertence à lista é devolvido o valor lógico True.
Algoritmos clássicos de programação do âmbito das listas
Independentemente de, atualmente, as linguagens de programação modernas implementarem os algoritmos que serão apresentados de seguida, convém conhecê-los, pois são particularmente educativos.
Pesquisa Linear
Como o nome indica a pesquisa linear trata-se de uma forma de pesquisar uma ocorrência numa lista. Nesta pesquisa, cada um dos elementos da lista é comparado com o valor a pesquisar e, quando encontrado, é determinado o índice da primeira ocorrência. Dependendo das implementações, quando o elemento não é encontrado é devolvido erro ou -1.
Pesquisa linear (com for):
# Pesquisa linear com for
n=5
v=[8,4,5,2,1]
x=int(input())
p=-1
for i in range(n):
if v[i]==x:
p=i
break
print(p)
Pesquisa linear (com while):
# Pesquisa linear com while
n=5
v=[8,4,5,2,1]
x=int(input())
i=0
while i<n and v[i]!=x:
i+=1
if i==n:
p=-1
else:
p=i
print(p)
Pesquisa Binária
Se tivermos uma lista ordenada e se formos inteligentes com nossas comparações, podemos ser muito mais eficientes.
Na busca sequencial, quando comparamos com o primeiro item e não é esse o procurado, há no máximo n-1 mais itens para examinar.
Na pesquisa binária, em vez de pesquisar toda a lista em sequência, começa-se examinando o item do meio. Se esse item é o que estamos à procura, damos a pesquisa por concluída. Se não for esse o item correto, podemos usar a natureza ordenada da lista, para eliminar metade dos itens restantes. Se o item que procuramos for maior do que o item do meio, sabemos que a metade inferior da lista e o item do meio, podem ser eliminados da nossa pesquisa, pois o item, se estiver na lista, estará na metade superior.
Pesquisa Binária:
# Pesquisa binária (a lista tem que estar ordenada)
lista=[2,8,10,12,45]
x=int(input())
primeiro=0
ultimo=len(lista)-1
encontrado=False
while primeiro<=ultimo and not encontrado:
meio=(primeiro+ultimo)//2
if lista[meio]==x:
encontrado=True
else:
if x<lista[meio]:
ultimo=meio-1
else:
primeiro=meio+1
if encontrado:
print(meio)
else:
print(-1)
Ordenação
Existem muitos algoritmos para ordenar uma lista. Estes métodos variam em eficiência e em dificuldade de implementação. O método que se apresenta de seguida é um dos mais simples: bubble sort (ou ordenação por "borbulhamento"). Para conhecer melhor este método consulte: https://pt.wikipedia.org/wiki/Bubble_sort. Existem também disponíveis na internet animações que ajudam a compreender o processo.
Ordenação (Bubble Sort - versão clássica):
# Bubble sort "clássico"
lista=[12,2,45,8,10]
n=len(lista)
for i in range(n-1):
for j in range(n-1-i):
if lista[j]>lista[j+1]:
lista[j],lista[j+1]=lista[j+1],lista[j] # Troca lista[i]<->lista[i+1]
for i in range(len(lista)):
print(lista[i])
Ordenação (Bubble Sort - versão otimizada):
# Bubble sort "optimizado"
lista=[12,2,45,8,10]
n=len(lista)
sorted=False
while not sorted:
sorted=True
for i in range(n-1):
if lista[i]>lista[i+1]:
sorted=False
lista[i],lista[i+1]=lista[i+1],lista[i] # Troca lista[i]<->lista[i+1]
for i in range(len(lista)):
print(lista[i])