Estrutura de Dados

Prévia do material em texto

LÓGICA DE PROGRAMAÇÃO E 
ESTRUTURAS DE DADOS 
 
 
Professor Marcelo Ferreira Zochio 
 
 
 
 
 
 
 
 
 
2 
 
 
5 ESTRUTURA DE DADOS 
Neste bloco, você irá aprender como usar estruturas de dados dos tipos tuplas, 
dicionários, listas, pilhas, filas e deques; também verá como aplicar o conceito de 
matrizes na matemática em criptografia e aplicação prática de estruturas de dados. 
 
5.1 Listas, dicionários e tuplas 
Lista é uma sequência ordenada e armazenada de valores, que podem ser do tipo literal 
ou numérico, armazenados dentro de colchetes, separados por vírgulas. Cada valor em 
uma lista é localizado por um índice. Esses valores são chamados itens ou elementos de 
uma lista. Listas também são conhecidas como arrays em outras linguagens de 
programação. Exemplo: [1, 2, 3, 4]. 
Dicionários são valores também ordenados, mas concatenados entre si na estrutura 
“chave:objeto”, armazenados dentro de chaves. Exemplo: {1: ‘Genilson’, 2: ‘Genoveva’, 
3:’Sanderson’} 
Uma tupla é uma sequência ordenada e armazenada de valores semelhante à lista. 
Porém, tuplas são imutáveis. São representadas dentro de parênteses, diferente da lista, 
que é representada entre colchetes. Exemplo: (‘Genilson’, ‘Sanderson’, ‘Genoveva’) 
 
5.2 Matrizes 
São estruturas bidimensionais, semelhantes a tabelas, com colunas e linhas, que contém 
valores numéricos. Veja um exemplo: 
 
 
 
 
3 
 
Em Python, uma matriz pode ser representada por uma lista composta por listas: 
matriz = [[1, 5, 8], [6, 7, 4], [3, 9, 1]] 
 
Para realizar operações matemáticas com matrizes, você pode usar a biblioteca numpy; 
para tal, importe-a com o comando import numpy. 
import numpy 
a = [[1,2], [3,4]] 
# Transformando a variável em matriz da biblioteca 
a = numpy.array(a) 
b = [[5, 6], [7, 8]] 
b = numpy.array(b) 
# Mostrando o resultado da multiplicação de matrizes 
print(numpy.dot(a, b)) 
 
O seguinte programa no próximo slide mostrará na tela os valores de cada posição da 
matriz: 
matriz = [[1, 5, 8], [6, 7, 4], [3, 9, 1]] 
print(matriz[0][0]) 
print(matriz[0][1]) 
print(matriz[0][2]) 
print(matriz[1][0]) 
print(matriz[1][1]) 
print(matriz[1][2]) 
print(matriz[2][0]) 
print(matriz[2][1]) 
 
 
 
4 
 
print(matriz[2][2]) 
 
Mas, e se você quiser que o usuário escolha os valores da matriz, preenchendo-os 
interativamente? Eis um exemplo de programa que preenche uma matriz 2x2: 
# -*- coding: cp1252 -*- 
matriz = [[0]*2]+[[0]*2] 
print(matriz) 
matriz[0][0] = int(input("Digite o valor da posição 0,0 da matriz: ")) 
matriz[0][1] = int(input("Digite o valor da posição 0,1 da matriz: ")) 
matriz[1][0] = int(input("Digite o valor da posição 1,0 da matriz: ")) 
matriz[1][1] = int(input("Digite o valor da posição 1,1 da matriz: ")) 
print(matriz) 
 
Note que ao invés de usar a multiplicação para criar as linhas da matriz, usamos 
concatenação; isso se dá porque se usarmos multiplicação, todas as posições da matriz 
serão consideradas 0,0 e 0,1 no caso dessa matriz. Então, somente serão preenchidos 
os dois últimos valores que preenchermos no input em todas as posições. 
 
 
 
 
 
5 
 
5.3 Aplicação prática de matrizes 
Agora vamos ver uma aplicação prática de matrizes. Você sabia que dá para criptografar 
mensagens usando matrizes? É nisso que se baseia a cifra de Hill. Vejamos: 
Escolha uma matriz 2×2 cuja determinante seja diferente de zero. Usaremos esta: 
 
Vamos cifrar a palavra “TOUPEIRA”; atribua um valor numérico de acordo com a posição 
de cada letra no alfabeto, e separe as letras em pares: 
T-O U-P E-I R-A 
20-15 21-16 5-9 18-1 
 
Para codificar o par T-O, efetuamos o produto matricial em modal 26: 
 
Que fornece o valor cifrado H-G (valores 8 e 7, respectivamente). 
Para codificar o par U-P, efetuamos o produto matricial: 
 
Que fornece o valor cifrado S-L (valores 19 e 12, respectivamente). 
Para codificar o par E-I, efetuamos o produto matricial: 
 
Que fornece o valor cifrado A-K (valores 1 e 11, respectivamente). 
Para codificar o par R-A, efetuamos o produto matricial: 
 
 
 
6 
 
 
Que fornece o valor cifrado R-M (valores 18 e 13, respectivamente). 
 
Obtemos então a cifra: 
HGSLAKRM. 
Para decifrar as cifras de Hill, usamos a matriz inversa (mod 26) da matriz codificadora; 
daí a razão da determinante ser diferente de 0, pois só assim uma matriz quadrada é 
inversível. 
 
Como estamos trabalhando em mod 26, vamos usar a tabela de inversos multiplicativos 
nesse valor modal: 
 
A fórmula para decifrar é: 
 
Aplicando a fórmula: 
 
 
Pelas equivalências numéricas, o equivalente numérico do texto cifrado HGSLAKRM é: 
8-7-19-12-1-11-18-13 
 
 
 
 
7 
 
Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A: 
 
Que fornece o valor original T-O. 
Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A: 
 
Que fornece o valor original U-P. 
Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A: 
 
Que fornece o valor original E-I. 
Para obter os pares de texto plano, multiplicamos cada vetor pela inversa da matriz A: 
 
Que fornece o valor original R-A. 
 
5.4 Pilhas, filas e deques 
Pilha é uma lista que permite acesso em somente uma extremidade. Os dados inseridos 
vão se “empilhando”, de modo que o último que entrou será o primeiro a sair. Um 
exemplo de uso dessa estrutura são as calculadoras que usam notação polonesa inversa 
(A HP é uma delas). 
Filas são listas em sequências de espera; aumentam através do acréscimo de novos 
elementos no final e diminuem com a saída dos elementos da dianteira. Em relação à 
pilha, a principal diferença é que na fila o primeiro elemento que entra é o primeiro a 
ser retirado. Um exemplo clássico de uso de filas são os softwares simuladores de filas, 
para estudo de comportamento de filas em call centers. 
 
 
 
8 
 
Deques são listas que permitem remover elementos de qualquer lugar. São usados, por 
exemplo, em gerenciamento de memória RAM e em construção de programas diversos. 
SAIBA MAIS 
Neste vídeo, você aprenderá mais sobre pilhas, filas e deques aplicados a Python. 
Vídeo: Estrutura de dados - Pilhas, Filas e Deck 
ESTRUTURA de dados - Pilhas, Filas e Deck. 2014. Disponível em: 
<https://www.youtube.com/watch?v=Hn_0Jb2f7hY>. Acesso em: 14 fev. 2019. 
 
5.5 Aplicação prática de pilhas, filas e deques 
Veja um exemplo de como usar pilhas na vida real: imagine uma calculadora HP. Como 
ela processa as informações da expressão matemática a seguir? 
((1 + 1) * 4) + 3 
Veja na tabela: 
1 entra operando 1 
1 entra operando 1, 1 
+ adicionar 2 
4 entra operando 2, 4 
* multiplicar 8 
3 entra operando 8, 3 
+ adicionar 11 
 
Um exemplo prático do uso de filas em computação é a fila de impressão de uma 
impressora. Um documento é enviado a uma impressora; se ela estiver imprimindo tal 
documento e outro é enviado para impressão, este último fica na fila aguardando a saída 
do primeiro para começar a sua. 
https://www.youtube.com/watch?v=Hn_0Jb2f7hY
 
 
 
9 
 
Deques possuem várias aplicações. Quando você termina um processo em um 
computador, o espaço da memória RAM que ele estava ocupando é disponibilizado para 
uso, podendo ter antes e depois do seu endereçamento outros processos alocados. Essa 
é uma operação típica de deques, que permitem adição e remoção de elementos. 
 
Conclusão 
Nesse tópico, você aprendeu sobre como trabalhar com estruturas de dados na 
linguagem Python. No próximo tópico, você verá como representar e trabalhar com 
árvores binárias na linguagem Python. 
 
Referências 
PERKOVIC, Ljubomir. Introdução à computação usando Python: um foco no 
desenvolvimento de aplicações. Rio de Janeiro: LTC, 2016.