Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados > Estruturas de Dados
Listas Lineares Matrizes Esparsas
Uma matriz esparsa é uma matriz extensa na qual poucos elementos são não-nulos (ou de valor diferente de zero). O problema de representação destas estruturas consiste em economizar memória armazenando apenas os dados válidos (i.e., não nulos) sem perda das propriedades matriciais (i.e., a noção de posição em linha e coluna de cada elemento). As implementações mais comuns são a representação em linhas ou por listas cruzadas.
Representação por Linhas
A forma mais simples (porém não necessariamente mais eficiente) de armazenar uma matriz esparsa é na forma de uma tabela (na verdade, uma lista ligada) de nós contendo a linha e coluna de cada elemento e suas demais informações. A lista é ordenada por linhas para facilitar o percurso neste sentido.
A matriz será acessível a partir do ponteiro de início da lista ligada que a representa.
typedef struct estrutura
{
int lin;
int col;
TIPOINFO info;
estrutura *prox;
} NO;
typedef struct
{
NO* inicio;
} MATRIZ;
A economia de espaço desta representação é bastante significativa. Para uma matriz de MAXLIN x MAXCOL elementos, dos quais n são não-nulos, seu uso será vantajoso (do ponto de vista da complexidade de espaço) sempre que:
(MAXCOL*MAXLIN*sizeof(TIPOINFO)) > (n*(sizeof(NO))
Lembrando que um nó é composto de dois inteiros, um TIPOINFO e um NO*. Por outro lado, a representação por linhas não apresenta bom tempo de resposta para certas operações matriciais. Em especial, percorrer uma linha da matriz exige que todas as linhas acima dela sejam percorridas. Pior do que isso, percorrer uma coluna da matriz exige que a matriz inteira (ou melhor, todos os seus elementos não-nulos) seja percorrida. Considerando-se que matrizes esparsas tendem a ser estruturas de grande porte, em muitas aplicações estes tempos de execução podem ser inaceitáveis.
Representação por Listas Cruzadas
Com um gasto adicional de espaço de armazenamento, podemos representar uma matriz esparsa com tempo de acesso proporcional ao volume de dados de cada linha ou coluna. Nesta representação, usamos uma lista ligada para cada linha e outra para cada coluna da matriz. As listas se cruzam, isto é, compartilham os mesmos nós em cada intersecção, e por este motivo cada nó armazena um ponteiro para a próxima linha (abaixo) e próxima coluna (à direita).
typedef struct estrutura
{
int lin;
int col;
TIPOINFO info;
estrutura *proxL;
estrutura *proxC;
} NO;
Referência Bibliográfica
Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.