Aula 12 - Aplicações de listas e outras estruturas

Prévia do material em texto

Aplicações de listas e 
outras estruturas 
SCC 202/502 – Algoritmos e Estruturas 
de Dados I 
Prof. Robson L. F. Cordeiro 
Material original editado: Prof. Thiago A. S. Pardo 
11 
Matrizes 
n  Matriz é um arranjo (tabela) retangular de 
números dispostos em linhas e colunas 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
829
601
473
33x
B
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
−
1289
4352
3401
43x
A
nº de elementos = nº de linhas * nº de colunas 
Matriz = Arranjo bidimensional 
12 
Matrizes especiais 
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
10900
8760
0542
0021
44x
B
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
654
032
001
33x
A
Tri-diagonal 
Triangular inferior 
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
000010000
002008000
000040000
000000000
000000000
020000020
000003001
97x
C
Matriz esparsa: 
excessivo nº de 
elementos nulos (0) 
 
8 não nulos dentre 63 
13 
Matrizes esparsas 
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
−
00010000
00041000
00000000
00000000
00000020
00003001
900700
!
""""""""
!
!
!
!
!
x
C
700 x 900 = 630.000 elementos 
Matriz esparsa com 9 elementos não nulos 
14 
Matrizes esparsas 
n  Uso da matriz tradicional 
n  Vantagem 
n  Ao se representar dessa forma, preserva-se o 
acesso direto a cada elemento da matriz 
§  Algoritmos simples 
n  Desvantagem 
n  Muito espaço para armazenar zeros 
15 
Matrizes esparsas 
n  Necessidade 
n  Método alternativo para representação de 
matrizes esparsas 
n  Solução 
n  Estrutura de lista encadeada contendo 
somente os elementos não nulos 
16 
Matrizes esparsas - solução 1 
n  Listas simples encadeadas 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
500
001
203
33x
A
linha coluna valor prox 
Estrutura de um nó: 
•  linha, coluna: posição 
•  valor: ≠ zero 
•  prox: próximo nó 
3 1 1 2 3 1 
0 0 0 
0 0 0 
1 1 2 5 3 3 
0 0 0 Nós zerados opcionais 
para auxiliar na 
divisão de linhas 
17 
Matrizes esparsas - solução 1 
n  Desvantagens? 
18 
Matrizes esparsas - solução 1 
n  Desvantagens 
n  Perda da natureza bidimensional de matriz 
n  Acesso ineficiente à linha 
n  Para acessar o elemento na i-ésima linha, deve-se 
atravessar as i-1 linhas anteriores 
n  Acesso ineficiente à coluna 
n  Para acessar os elementos na j-ésima coluna, tem 
que se passar por várias outras antes 
n  Questão 
n  Como organizar essa lista, preservando a natureza 
bidimensional de matriz? 
Matrizes esparsas - solução 2 
n  Listas cruzadas 
n  Para cada matriz, usam-se dois vetores com N 
ponteiros para as linhas e M ponteiros para as colunas 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
500
001
203
33x
A
1 31 3 21
3 53
1 -1 2
lin[1] 
col[2] col[1] col[3] 
lin[2] 
lin[3] 
Estrutura de um nó: 
linha coluna valor 
proxlin proxcol 
20 
Matrizes esparsas - solução 2 
n  Listas cruzadas 
n  Cada elemento não nulo é mantido 
simultaneamente em duas listas 
n  Uma para sua linha 
n  Uma para sua coluna 
21 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  Em termos de tempo 
n  Operações mais lentas em listas cruzadas: 
acesso não é direto 
22 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  Em termos de espaço 
n  Supor que inteiro e ponteiro para inteiro ocupam um 
bloco de memória 
n  Listas cruzadas: tamanho do vetor de linhas (l) + 
tamanho do vetor de colunas (c) + n elementos não 
nulos * tamanho do nó 
§  l + c + n*5 
n  Matriz tradicional bidimensional 
§  l*c 
23 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  Listas cruzadas 
§  l + c + n*5 = 700 + 900 + 9*5 = 1.645 
n  Matriz tradicional bidimensional 
§  l*c = 700*900 = 630.000 
9 não nulos 
24 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  E nessa matriz? 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
500
001
203
33x
A
25 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  Listas cruzadas 
§  l + c + n*5 = 3 + 3 + 4*5 = 26 
n  Matriz tradicional bidimensional 
§  l*c = 3*3 = 9 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
500
001
203
33x
A
26 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  Necessidade de avaliação tempo-espaço para 
cada aplicação 
n  Em geral, usam-se listas cruzadas quando há 
no máximo 1/5 dos elementos 
n  De onde vem isso? 
27 
Matrizes esparsas 
n  Listas cruzadas vs. matriz tradicional 
n  Necessidade de avaliação tempo-espaço para 
cada aplicação 
n  Em geral, usam-se listas cruzadas quando há 
no máximo 1/5 dos elementos 
n  De onde vem isso? 
Dica: l+c+n*5 < l*c 
28 
Matrizes esparsas - operações 
n  Em geral 
n  Multiplicar uma dada linha ou coluna por uma 
constante 
n  Somar uma constante a todos os elementos 
de uma linha ou coluna 
n  Somar duas matrizes esparsas de igual 
dimensão 
n  Multiplicar matrizes esparsas 
n  Transpor matrizes esparsas 
n  Inserir, remover ou alterar elementos 
n  Etc. 
29 
Matrizes esparsas - operações 
n  Após a realização de alguma operação sobre 
a matriz 
n  Quando um elemento da matriz se torna nulo 
n  Remoção do elemento 
n  Quando algum elemento se torna não nulo 
n  Inserção do elemento 
30 
Matrizes esparsas - operações 
n  Por exemplo, ao se somar -4 na coluna 5 do 
exemplo 
31 
Exercício: somar -5 na coluna 3 
1 3 1 3 2 1 
3 5 3 
1 -1 2 
lin[1] 
col[2] col[1] col[3] 
lin[2] 
lin[3] 
32 
Exercício 
n  Declare em C a estrutura da matriz esparsa 
representada via lista cruzada 
33 
Exercício 
n  Declare em C a estrutura da matriz esparsa 
representada via lista cruzada 
 
#define n ... //número de linhas 
#define m ... //número de colunas 
 
typedef struct no { 
 int lin, col, val; 
 struct no *proxlin, *proxcol; 
} No; 
 
typedef struct { 
 No *L[n], *C[m]; 
} MatrizEsparsa; 
34 
Matrizes esparsas 
n  Exercício para casa 
n  Implementar uma sub-rotina para somar um 
número K qualquer a uma coluna da matriz 
n  Usando listas cruzadas 
35 
Matrizes esparsas - outra solução 
n  Listas circulares com nós de cabeçalho 
n  Ao invés de vetores de ponteiros, linhas e 
colunas são listas circulares com nós de 
cabeçalho 
n  Nós de cabeçalho: reconhecidos por um 0 no 
campo linha ou coluna 
§  1 único ponteiro para a matriz: navegação em 
qualquer sentido 
n  Exemplo 
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
−
−
8100
0042
3020
0000
44x
A
36 
Matrizes esparsas - outra solução 
A 0 1 2 3 4 
0 
1 
2 
3 
4 
00 10 20 30 40
01
02
03
04 -1 34 844
-2 13 423
222 342
Exercício 
n  Declare em C a estrutura dessa matriz 
37 
Exercício 
n  Declare em C a estrutura dessa matriz 
 
typedef struct no { 
 int lin, col, val; 
 struct no *proxlin, *proxcol; 
} No; 
 
typedef struct { 
 No *inicio 
} MatrizEsparsa; 
38 
39 
Matrizes esparsas - outra solução 
n  Exercício em grupos de 3 (para entregar) 
1.  Representar a matriz abaixo com listas circulares 
com nós de cabeçalho 
2.  Implementar em C uma sub-rotina que some todos 
os elementos de uma matriz qualquer representada 
dessa forma 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
500
001
203
33x
A
40 
Matrizes esparsas - outra solução 
n  Representação da matriz? 
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
500
001
203
33x
A
41 
Matrizesesparsas - outra solução 
n  Implementação da sub-rotina com análise de 
complexidade 
42 
Matrizes esparsas - outra solução 
n  Quais as desvantagens dessa 
representação? 
n  Quais as vantagens dessa representação? 
43 
Matrizes esparsas - outra solução 
n  Quais as desvantagens dessa 
representação? 
n  Mais complexa de se manipular 
n  Quais as vantagens dessa representação? 
n  A matriz pode crescer dinamicamente 
44 
Matrizes esparsas 
n  Desafio para casa! 
n  Implemente o TAD matriz esparsa com listas 
circulares e nós de cabeçalho 
45 
Fila de prioridade 
n  Pilha e fila 
n  Elementos processados em função da sequência na 
qual foram inseridos 
n  Fila de prioridade 
n  Os elementos são processados de acordo com sua 
importância (prioridade), não importando o momento 
em que elementos com prioridades distintas entraram 
na fila 
n  Por exemplo, atendimento de idosos e gestantes em 
bancos, importância de processos em sistemas 
operacionais, substituição de páginas menos 
utilizadas na memória 
46 
Fila de prioridade 
n  Tipos 
n  Ascendente 
n  Remove-se o item de menor valor 
n  Descendente 
n  Remove-se o item de maior valor 
47 
Fila de prioridade 
n  Estruturas 
n  Sequencial: é necessário que se desloque 
elementos para inserção/remoção 
n  Encadeada: é mais simples inserir/remover 
48 
Fila de prioridade 
n  Estruturas 
n  Listas não ordenadas 
n  Vantagens e desvantagens? 
n  Listas ordenadas 
n  Vantagens e desvantagens? 
49 
Fila de prioridade 
n  Estruturas 
n  Listas não ordenadas 
n  Inserção é simples, mas remoção exige busca 
n  Listas ordenadas 
n  Remoção é simples, mas inserção exige busca 
50 
Fila de prioridade 
n  Questões 
n  O que é um heap? 
n  Como pode ser usado para representar filas 
de prioridade? 
51 
Fila de prioridade 
n  Exercício para casa 
n  Implementar o TAD fila de prioridade sobre 
uma lista ordenada dinâmica e encadeada 
n  Declare a estrutura 
n  Defina e implemente as sub-rotinas relevantes 
52 
Deque 
n  deque = double-ended queue 
n  Fila de extremidade dupla 
n  Estrutura de dados relativamente comum, mas pouco 
conhecida por esse nome 
n  Enquanto pilha e fila exigem inserções e remoções em 
extremidades específicas da estrutura, deque permite inserções 
e remoções em quaisquer extremidades 
n  Se insere em uma extremidade e remove dela: pilha 
n  Se insere em uma extremidade e remove da outra: fila 
n  Deque permite inserções e remoções dos dois tipos, 
�misturadas� 
53 
Deque 
n  Implementação do TAD deque 
n  Estrutura de dados tradicional 
n  Funções diferenciadas para inserção e 
remoção em ambas as extremidades