Matrizes Esparsa

Georgya

Estrutura de Dados II

UNIFEV

Estrutura de Dados II
Eng. de Computação – 4º período – Noturno
2012

MATRIZES ESPARSAS
Objetivos:
Consiste em concretizar os conceitos de Listas implementadas por através de uma aplicação: Matrizes esparsas.

encadeamento

Descrição:
Matrizes esparsas são matrizes nas quais a maioria das posições é preenchida por zeros.
Para essas matrizes, podemos economizar um espaço significativo de memória se apenas os termos diferentes de zero forem armazenados. As operações usuais sobre essas matrizes (somar, multiplicar, inverter, pivotar) também podem ser feitas em tempo muito menor se não armazenarmos as posições que contêm zeros.
Uma maneira eficiente de apresentar estruturas com tamanho variável e/ou desconhecido é com o emprego de alocação encadeada, utilizando listas. Vamos usar essa representação para armazenar as matrizes esparsas. Cada coluna da matriz será representada por uma lista linear circular com uma célula cabeça. Da mesma maneira, cada linha da matriz também será representada por uma lista linear circular com uma célula cabeça.

A representação da matriz A pode ser vista na Figura 1. Com essa representação, uma matriz esparsa m x n com r elementos diferentes de zero gastará (m + n + r) células. É bem verdade que cada célula ocupa vários bytes na memória; no entanto, o total de memória usado será menor do que as m x n posições necessárias para representar a matriz toda, desde que r seja suficientemente pequeno.

EXEMPLOS:
Declarando a Matriz: typedef struct Celula {
Celula direita, abaixo; int linha, coluna; double valor;
} Celula;
Matriz (VOID MAIN) void main(void)
{
TMatriz A, B,C;
A.leMatriz(); A.imprimeMatriz();
B.leMatriz(); B.imprimeMatriz();
C = somaMatriz(A,B); C.imprimeMatriz();
B.leMatriz();
A.imprimeMatriz();B.imprimeMatriz();
C = somaMatriz(A,B); C.imprimeMatriz();
C = multiplicaMatriz(A,B); C.imprimeMatriz();
C = multiplicaMatriz(B,B);