Baixe o app para aproveitar ainda mais
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.
Compartilhar