Índice > Lista > Matriz Esparsa e Lista Cruzada

Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel e Maria Cristina

Matriz Esparsa e Lista Cruzada

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:

    Exercícios

    Lista