AtividadeMatriz_Esparsa

Prévia do material em texto

Matriz Esparsa 
Material gentilmente emprestado pelo professor Edmundo Spoto 
 
Problema: Representação de matrizes contendo grande parte de seus elementos nulos. 
Por exemplo seja a matriz abaixo, a qual contém 5 linhas e 6 colunas. Apenas 5 de seus 
30 elementos são não nulos. 
 
Precisamos buscar uma representação que evite o armazenamento de tantas posicões 
nulas. 
Veremos uma solução que utiliza, as listas cruzadas como estruturas de dados. 
Estrutura de Dados de Listas Cruzadas 
Numa matriz genérica, para cada elemento temos as informacões de: 
• Linha, 
• Coluna e 
• Valor 
Para não representarmos os valores nulos, fazemos listas de linhas e listas de colunas 
tais que o elemento a(ij) diferente de 0 pertence: 
• à lista dos elementos da linha i 
• à lista dos elementos da coluna j 
Então se a matriz tem nl linhas e nl colunas, temos nl listas de linhas e nc listas de 
colunas. Graficamente podemos ter algo como: 
 
Para o exemplo anterior, temos: 
 
ED e Operações 
Definição da ED 
Type 
 Preg = ^Reg; 
 Lista = Preg; 
 Reg = record 
 linha: 1..nl; 
 coluna: 1..nc; 
 valor: TipoElemento; 
 PL,PC: Preg; { pont p/ prox registro } 
 end; 
 
var 
 L: array[1..nl] of Lista; 
 C: array[1..nc] of Lista; 
 
1) Acesso ao primeiro elemento não nulo da linha i: 
• L[i] ^ 
2) Acesso ao elemento i,j: 
• percorrer a lista L[i] até encontrar registro com campo de coluna = j ou 
• percorrer a lista C[j] até encontrar registro com campo de linha = i 
Operações com matrizes esparsas 
Além de armazenar matrizes esparsas, as aplicações normalmente exigem a realização 
de operações sobre essas matrizes, como por exemplo: 
• multiplicar uma dada linha ou coluna por uma constante 
• somar uma constante a todos os elementos de uma linha ou coluna 
• somar duas matrizes esparsas de igual dimensão 
Como consequência desses operacões, alguns elementos podem deixar de ser nulos, 
enquanto que outros podem se tornar nulos. 
Por exemplo, ao se somar -4 a coluna 5 do exemplo temos: 
 
Esse exemplo ilustra que, quando um elemento a(i,j) deve ser eliminado, ele deve ser 
eliminado, de fato, de duas listas: L[i] e L[j]. 
Algoritmo: Somar k aos elementos da coluna j 
 Procedure Soma (k: TipoElemento); 
 Var p: Lista; 
 begin 
 p := C[j]; 
 for i := 1 to nl do 
 if p = nil then insere (i,j,k) 
 else 
 begin 
 if p^.linha <> i then { valor era nulo} 
 inserir(i,j,k) {insere antes de p} 
 else 
 begin 
 p^.valor := p^.valor + k; 
 if p^.valor = 0 then 
 begin 
 p := p^.pl; 
 eliminar(i,j); 
 end 
 else p := p^.pl; 
 end; 
 end; 
 end; 
 
Usabilidade 
Quando a representação de listas cruzadas é vantajosa em relação à representação 
convencional (bidimensional) ? 
Fator Espaço 
Suponhamos o caso de: 
• uma matriz esparsa que armazena inteiros 
• um ponteiro que ocupa o mesmo espaço que um inteiro 
Matriz Esparsa 
Espaço ocupado por uma matriz esparsa de nl linhas, nl colunas e n valores não-nulos: 
• 5 * n espaços para ponteiros para os registros (um para cada campo do registro: 
linha, coluna, valor, PL, PC) 
• nl espaços para ponteiros para o vetor L 
• nc espaços para ponteiros para o vetor C 
• espaço total de 5n + nl + nc 
Representação bidimensional 
• o espaço ocupado seria nl * nc 
Conclusão: 
Em termos de espaço ocupado, há vantagem em utilizar-se a representação de listas 
cruzadas quando: 
 5n + nl + nc < nl * nc 
ou seja, quando: 
 n < [(nl - 1) * (nc - 1) -1] / 5 
Como (nl - 1) * (nc - 1) é aproximadamente o tamanho da matriz, pode-se dizer, de uma 
maneira geral que, há ganho em termos de espaço, quando um número inferior a 1/5 dos 
elementos da matriz forem não nulos. 
Fator Tempo 
As operações sobre listas cruzadas podem ser mais lentas e complicadas que para o caso 
bidimensional. 
Portanto, para algumas aplicações, deve ser feita uma reavaliação de tempo-espaço.