estrutura de dados

Prévia do material em texto

Aula 13 – Estrutura de Dados
continuação
Computação I - 2012/2 2
Listas - Fatias
Podemos usar a notação de fatias (slices) em listas.
>>> lista = ['a',2,[3,'f'], 'q']
>>> lista [1:]
 
>>> lista [:1]
 
>>> lista [1:2]
 
>>> lista [0:-1]
 
[start : end] : vai do índice start até o índice end-1 
[start : ] : vai de start até o final da lista
[ : end] : vai do início da lista até end-1
[ : ] : copia a lista toda
Computação I - 2012/2 3
Listas - Fatias
Podemos usar a notação de fatias (slices) em listas.
>>> lista = ['a',2,[3,'f'], 'q']
>>> lista [1:]
[2,[3,'f'], 'q']
>>> lista [:1]
['a']
>>> lista [1:2]
[2]
>>> lista [0:-1]
['a',2,[3,'f']]
[start : end] : vai do índice start até o índice end-1 
[start : ] : vai de start até o final da lista
[ : end] : vai do início da lista até end-1
[ : ] : copia a lista toda
Índice 1 até o final da lista
Índice 0 até o índice 0
Índice 1 até o índice 1
Índice 0 até o índice -2 (equivalente a ?)
Computação I - 2012/2 4
Listas - Fatias
Incremento:Incremento: podemos usar incremento / decremento para selecionar os 
elementos de uma lista.
Exemplo
>>> lista = [1,2,3,4,5,6]
>>> lista[0:-1:2]
 
>>> lista[5:0:-1]
 
>>> lista[0:-1:3]
 
>>> lista[::-1]
 
[start:end:step] : vai do índice start até end (sem ultrapassá-lo),
com passo step
Computação I - 2012/2 5
Listas - Fatias
Incremento:Incremento: podemos usar incremento / decremento para selecionar os 
elementos de uma lista.
Exemplo
>>> lista = [1,2,3,4,5,6]
>>> lista[0:-1:2]
[1, 3, 5]
>>> lista[5:0:-1]
[6, 5, 4, 3, 2]
>>> lista[0:-1:3]
[1, 4]
>>> lista[::-1]
[6, 5, 4, 3, 2, 1]
Índice 0 até o índice -2 de 2 em 2
[start:end:step] : vai do índice start até end -1(sem ultrapassá-lo),
com passo step
Índice 5 até o índice 1 de 1 em 1
Índice 0 até o índice -2 de 3 em 3
Inverte a lista
Computação I - 2012/2 6
Listas - Fatias
Atribuição:Atribuição: ao atribuir uma sequência a uma fatia, os elementos desta 
devem ser substituidos pelos elementos daquela.
>>> lista = [1,2,3,4,5]
[1, 2, 3, 4, 5] [1, ”a”, ”b”, 4, 5]
lista[1:3] = [“a”,”b”]
[1, 2, 3, 4, 5] [1, 2, ”a”, ”b”]
lista[2:] = [“a”,”b”]
Computação I - 2012/2 7
Listas - Fatias
Atribuição:Atribuição: ao atribuir uma sequência a uma fatia, os elementos desta 
devem ser substituidos pelos elementos daquela.
>>> lista = [1,2,3,4,5]
[1, 2, 3, 4, 5] [”a”, ”b”, 3, 4, 5]
lista[:2] = [“a”,”b”]
[1, 2, 3, 4, 5] [ [”a”, ”b”], 3, 4, 5]
lista[:2] = [[“a”,”b”]]
Computação I - 2012/2 8
Listas - Fatias
Atribuição:Atribuição: ao atribuir uma sequência a uma fatia, os elementos desta 
devem ser substituidos pelos elementos daquela.
>>> lista = [1,2,3,4,5]
>>> novalista = [8,10]
[1, 2, 3, 4, 5] [1, 2, 8, 10, 3, 4, 5]
lista[2:2] = novalista
[1, 2, 3, 4, 5] [ 1, 8, 10, 5]
lista[1:4] = novalista
Computação I - 2012/2 9
Listas - Fatias
Atribuição:Atribuição: ao atribuir uma sequência a uma fatia, os elementos desta 
devem ser substituidos pelos elementos daquela.
Exercício
>>> lista = [1,2,3,4,5]
>>> lista [1:1] = ['z']
 
>>> lista [1:3] = [[7]]
 
>>> lista [1:-1]= [8,9,10]
 
>>> lista[:3]="xyz"
 
>>> lista[:3]="a,b,c"
 
>>> lista[:2]=1,2,3
 
Computação I - 2012/2 10
Listas - Fatias
Atribuição:Atribuição: ao atribuir uma sequência a uma fatia, os elementos desta 
devem ser substituidos pelos elementos daquela.
Exercício
>>> lista = [1,2,3,4,5]
>>> lista [1:1] = ['z']
 [1, 'z', 2, 3, 4, 5]
>>> lista [1:3] = [[7]]
 [1, [7], 3, 4, 5]
>>> lista [1:-1]= [8,9,10]
 [1, 8, 9, 10, 5]
>>> lista[:3]="xyz"
 ['x', 'y', 'z', 10, 5]
>>> lista[:3]="a,b,c"
 ['a', ',', 'b', ',', 'c', 10, 5]
>>> lista[:2]=1,2,3
 [1, 2, 3, 'b', ',', 'c', 10, 5]
Computação I - 2012/2 11
Listas - Fatias
Exercício 
1- Faça um programa que dada uma lista ordenada 
(crescente) de números inteiros L, inclua um dado número 
n na posição correta.
2- Faça um programa que dada uma lista ordenada 
(decrescente) de números inteiros L, selecione a sublista 
formada por todos os elementos maiores que um dado número 
n.
3- Usando a lista L obtida no exercício 2, apresente a 
lista formada pelos elementos de L que estão em uma 
posição de índice par.
4- Faça um programa que dadas duas listas L1 e L2, gera 
uma lista L3 que é formada intercalando os elementos de 
L1 e L2. Exemplo: L1=[1,3,5] e L2=[2,4,6] gera 
L3=[1,2,3,4,5,6]. Considere que L1 e L2 tem o mesmo 
tamanho (maior ou igual a 1).
Computação I - 2012/2 12
Listas - Fatias
Atribuição:Atribuição: cuidado quando fizer cópia de listas!
Exemplo
>>> l1 = [1,2,3,4,5]
>>> l2 = l1
>>> l1 
 [1,2,3,4,5]
>>> l2
 [1,2,3,4,5]
>>> l2[0]=9
>>> l2
 [9,2,3,4,5]
>>> l1
 [9,2,3,4,5]
1 2 3 4 5
l1
l2
9
Computação I - 2012/2 13
Listas - Fatias
Atribuição:Atribuição: cuidado quando fizer cópia de listas!
Exemplo
>>> l1 = [1,2,3,4,5]
>>> l2 = l1[:]
>>> l1 
 [1,2,3,4,5]
>>> l2
 [1,2,3,4,5]
>>> l2[0]=9
>>> l2
 [9,2,3,4,5]
>>> l1
 [1,2,3,4,5]
1 2 3 4 5l1
l2 1 2 3 4 5
9
Computação I - 2012/2 14
Listas - Fatias
Incremento:Incremento: podemos usar incremento / decremento para selecionar os 
elementos de uma lista.
ATENÇÃO: Se um incremento de fatia é diferente de 1, uma 
atribuição à fatia deve ter o mesmo número de elementos.
>>> l = [1,2,3,4,5]
>>> l[0::2] = ['x','y','z']
>>> l
 ['x',2, 'y', 4, 'z']
>>> l[0::2] = [6,7]
Traceback (most recent call last): 
File "<pyshell#17>",line 1, in -toplevel-
l [0::2] = [6,7]
ValueError: attempt to assign sequence of size 2
to extended slice of size 3
Computação I - 2012/2 15
Listas - Fatias
Exercício: Defina os métodos append e extend usando 
fatias.
Lembrando:
>>> Lista = [ ] >>> Lista.extend([“q”])
>>> Lista.append(“a”) >>> Lista
>>> Lista ['a',2,[3,'f'], 'q']
['a'] 
>>> Lista.append(2) >>>Lista.extend([5])
>>> Lista >>> Lista
['a',2] ['a',2,[3,'f'], 'q', 5]
>>> Lista.append([3,"f"])
>>> Lista
['a',2,[3,'f']]
Computação I - 2012/2 16
Listas - Fatias
Exercício: Defina os métodos append e extend usando 
fatias.
>>> Lista = [ ] >>> Lista[len(Lista):] =[“q”]
>>> Lista[len(Lista):] = [“a”] >>> Lista
>>> Lista ['a',2,[3,'f'], 'q']
['a'] 
>>> Lista[len(Lista):] = [2] >>>Lista[len(Lista):] = [5]
>>> Lista >>> Lista
['a',2] ['a',2,[3,'f'], 'q', 5]
>>> Lista[len(Lista):] = [[3,"f"]]
>>> Lista
['a',2,[3,'f']]
Computação I - 2012/2 17
Listas - Métodos
insert(indice, elemento): insere elemento na lista na posição 
indicada por índice.
Ex.: >>> lista = [0,1,2,3]
 >>> lista.insert(1,'dois')
 >>> lista
[0,'dois', 1, 2, 3]
- Como o extend, altera a lista ao invés de retornar a lista. O 
valor retornado é None!
- Atribuições a fatias servem para a mesma finalidade mas são 
menos legíveis.
>>> lista = [0,1,2,3]
>>> lista [1:1] = ['dois'] 
>>> lista
 [0,'dois', 1, 2, 3]
Computação I - 2012/2 18
Listas - Métodos
remove(elemento): Remove da lista o primeiro elemento 
igual a elemento. Se não existe tal elemento, um erro é 
gerado.
Ex.:
>>> lista = ['oi', 'alo', 'ola']
>>> lista.remove('alo')
>>> lista
['oi', 'ola']
>>> lista.remove('oba')
Traceback (most recent call last):
 File "<pyshell#116>", line 1, in <module>
 lista.remove("oba")
ValueError: list.remove(x): x not in list
Computação I - 2012/2 19
Listas - Métodos
pop(índice): Remove da lista o elemento na posição índice e o 
retorna. Se índice não for mencionado, é assumido o último.
Ex.:
>>> lista = [1,2,3,4]
>>> lista.pop()
4
>>> lista
[1,2, 3]
>>> lista.pop(1)
2
>>> lista
[1,3]
Computação I - 2012/2 20
Listas - Métodos
count(elemento): Retorna quantasvezes o elemento aparece 
na lista
Ex.:
>>> [1,2,3,1,2,3,4].count(1)
2
index(elemento): Retorna o índice da primeira ocorrência de 
elemento na lista. Um erro ocorre se elemento não consta da 
lista.
Ex.:
>>> lista = [9,8,33,12]
>>> lista.index(33)
2
>>> lista.index(7)
Traceback (most recent call last):
 File "<pyshell#110>", line 1, in <module>
 lista.index(7)
ValueError: 7 is not in list
Computação I - 2012/2 21
Listas - Métodos
reverse(): Inverte a ordem dos elementos da lista.
Ex.:
>>> lista=[1,2,3]
>>> lista.reverse()
>>> lista
[3,2, 1]
sort(): ordena uma lista.
Ex.:
>>> lista=[2,1,3]
>>> lista.sort()
>>> lista
[1,2,3]
Computação I - 2012/2 22
Listas - Funções
filter(função, lista) : retorna uma lista formada pelos ítens 
de lista para os quais função é verdadeira.
Exemplo 
def f(x): 
return x % 2 != 0 and x % 3 != 0
>>> filter(f, range(2, 25)) (python 2.7)
[5, 7, 11, 13, 17, 19, 23]
>>> list(filter(f, range(2, 25))) (python 3.2)
[5, 7, 11, 13, 17, 19, 23]
Computação I - 2012/2 23
Listas - Funções
map(função, sequence): chama função(item) para cada 
item em sequence e retorna uma lista de valores.
Exemplo 
def cube(x):
return x*x*x
>>> map(cube, range(1, 11)) (python 2.7)
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
>>> list(map(cube, range(1, 11))) (python 3.2)
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
Computação I - 2012/2 24
Listas - Funções
map(função, sequence): chama função(item) para cada 
item em sequence e retorna uma lista de valores.
Mais de uma sequência pode ser passada, e a função deve 
ter portanto tantos argumentos quantas forem as 
sequências. 
Exemplo 
def add(x, y): return x+y
>>> seq = range(8)
>>> list(map(add, seq, seq)) (python 3.2)
[0, 2, 4, 6, 8, 10, 12, 14]
>>> seq1=[1,2,3]
>>> seq2=[4,5,6]
>>> list(map(add, seq1, seq2))
[5, 7, 9]
Computação I - 2012/2 25
Listas - Funções
reduce(function, sequence): retorna um único valor obtido 
aplicando-se a função function aos dois primeiros itens de 
sequence, depois o resultado com o próximo item, e assim 
sucessivamente. 
Exemplo 
def add(x, y): return x+y
>>> from functools import * (necessário python 3.2)
>>> reduce(add, range(1, 11)) 
55
((((0+1)+2)+3)+...+10) = 55
Computação I - 2012/2 26
Listas - Comprehension
Podemos criar listas de forma mais concisa. 
Exemplo 
>>> squares = []
>>> for x in range(10):
... squares.append(x**2)
...
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
ou
>>> squares = [x**2 for x in range(10)]
Computação I - 2012/2 27
Listas - Comprehension
Forma geral
 [ expressão for … for … if condição for … if condição ]
Exemplo 
>>> combs = []
>>> for x in [1,2,3]:
... for y in [3,1,4]:
... if x != y:
... combs.append((x, y))
...
>>> combs
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
0 ou mais vezes
Computação I - 2012/2 28
Listas - Comprehension
Forma geral
 [ expressão for … for … if condição for … if condição ]
Exemplo 
>>> [(x, y) for x in [1,2,3] for y in [3,1,4] if x != y]
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
0 ou mais vezes
Computação I - 2012/2 29
Listas - Comprehension
Exercício
>>> lista = [-4, -2, 0, 2, 4]
Criar uma nova lista com os valores dobrados
 
 
Criar uma lista só com valores positivos 
 
 
Calcule o valor absoluto dos elementos da lista
 
 
Criar uma lista formada pelos pares (elemento,quadrado), para 
elementos de 0 a 5.
 
 
Computação I - 2012/2 30
Listas - Comprehension
Exercício
>>> lista = [-4, -2, 0, 2, 4]
Criar uma nova lista com os valores dobrados
>>> [x*2 for x in lista]
[-8, -4, 0, 4, 8]
Criar uma lista só com valores positivos 
>>> [x for x in lista if x >= 0]
[0, 2, 4]
Calcule o valor absoluto dos elementos da lista
>>> [abs(x) for x in lista]
[4, 2, 0, 2, 4]
Criar uma lista formada pelos pares (elemento,quadrado), para 
elementos de 0 a 5.
>>> [(x, x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]
Computação I - 2012/2 31
Listas - Comprehension
Exercício
Transforme a lista [[1,2,3], [4,5,6], [7,8,9]] na lista [1, 2, 3, 4, 5, 
6, 7, 8, 9]
Computação I - 2012/2 32
Listas - Comprehension
Exercício
Transforme a lista [[1,2,3], [4,5,6], [7,8,9]] na lista [1, 2, 3, 4, 5, 
6, 7, 8, 9]
>>> lista = [[1,2,3], [4,5,6], [7,8,9]]
>>> [num for elem in lista for num in elem]
Computação I - 2012/2 33
Listas
Podemos usar listas dentro de listas para 
armazenar várias informações.
ExemploExemplo
Produto1 = [ “kiwis” , 10, 0.25 ]
Produto2 = [ “figos” , 15, 0.70 ]
Produto3 = [ “peras” , 40, 0.95 ]
Estoque = [Produto1, Produto2, Produto3]
print (Estoque)
[['kiwis', 10, 0.25], ['figos', 15, 0.69999999999999996],[['kiwis', 10, 0.25], ['figos', 15, 0.69999999999999996],
 ['peras', 40, 0.94999999999999996]]['peras', 40, 0.94999999999999996]]
Produto1 = [ “kiwis” , 10, 0.25 ]
Produto2 = [ “figos” , 15, 0.70 ]
Produto3 = [ “peras” , 40, 0.95 ]
Estoque = [Produto1, Produto2, Produto3]
for i in range(len(Estoque)):
 print("Produto: %s" % Estoque[i][0])
 print("Quantidade: %d" % Estoque[i][1])
 print("Valor: %5.2f" % Estoque[i][2])
 
Produto: kiwisProduto: kiwis
Quantidade: 10Quantidade: 10
Valor: 0.25Valor: 0.25
Produto: figosProduto: figos
Quantidade: 15Quantidade: 15
Valor: 0.70Valor: 0.70
Produto: perasProduto: peras
Quantidade: 40Quantidade: 40
Valor: 0.95Valor: 0.95
Computação I - 2012/2 34
Listas
Podemos usar listas dentro de listas para 
armazenar várias informações.
ExemploExemplo
Produto1 = [ “kiwis” , 10, 0.25 ]
Produto2 = [ “figos” , 15, 0.70 ]
Produto3 = [ “peras” , 40, 0.95 ]
Estoque = [Produto1, Produto2, Produto3]
for i in range(len(Estoque)):
 print("Produto: %s" % Estoque[i][0])
 print("Quantidade: %d" % Estoque[i][1])
 print("Valor: %5.2f" % Estoque[i][2])
 
Produto: kiwisProduto: kiwis
Quantidade: 10Quantidade: 10
Valor: 0.25Valor: 0.25
Produto: figosProduto: figos
Quantidade: 15Quantidade: 15
Valor: 0.70Valor: 0.70
Produto: perasProduto: peras
Quantidade: 40Quantidade: 40
Valor: 0.95Valor: 0.95
Produto1 = [ “kiwis” , 10, 0.25 ]
Produto2 = [ “figos” , 15, 0.70 ]
Produto3 = [ “peras” , 40, 0.95 ]
Estoque = [Produto1, Produto2, Produto3]
for e in Estoque:
 print("Produto: %s" % e[0])
 print("Quantidade: %d" % e[1])
 print("Valor: %5.2f" % e[2])
 
Computação I - 2012/2 35
Aula 13 – Estrutura de Dados
continuação
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35