Matrizes

Universidade Federal do Esp´ ırito Santo
Departamento de Inform´tica a Estrutura de Dados/Estruturas de Informa¸˜o 2009/2 ca Profa. Claudine Badue

Trabalho Pr´tico 2 a 07 de Outubro de 2009

1

Matrizes Esparsas – Utiliza¸˜o de Listas por meio de Apontadores ca [Ziviani, 2004; Exerc´ ıcio 3.3]

Matrizes esparsas s˜o matrizes nas quais a maioria das posi¸˜es ´ preenchida por zeros. Para estas matrizes, a co e podemos economizar um espa¸o significativo de mem´ria se apenas os termos diferentes de zero forem armazenados. c o
As opera¸˜es usuais sobre estas matrizes (somar, multiplicar, inverter, pivotar) tamb´m podem ser feitas em tempo co e muito menor se n˜o armazenarmos as posi¸˜es que contˆm zeros. a co e Uma maneira eficiente de representar estruturas com tamanho vari´vel e/ou desconhecido ´ com o emprego de a e aloca¸˜o encadeada, utilizando listas. Vamos usar esta representa¸˜o para armazenar as matrizes esparsas. Cada ca ca coluna da matriz ser´ representada por uma lista linear circular com uma c´lula cabe¸a. Da mesma maneira, a e c cada linha da matriz tamb´m ser´ representada por uma lista linear circular com uma c´lula cabe¸a. Cada c´lula e a e c e da estrutura, al´m das c´lulas cabe¸a, representar´ os termos diferentes de zero da matriz e devem ser como no e e c a
Programa 1.
Programa 1: Estrutura da c´lula da matriz esparsa e typedef struct T i p o C e l u l a ∗ Apontador ; typedef struct T i p o C e l u l a
{
Apontador D i r e i t a , Abaixo ; int Linha , Coluna ; f l o a t Valor ;
} TipoCelula ;
O campo Abaixo deve ser usado para apontar o pr´ximo elemento diferente de zero na mesma coluna. O campo o Direita deve ser usado para apontar o pr´ximo elemento diferente de zero na mesma linha. Dada uma matriz A, o para um valor A(i, j) diferente de zero, dever´ haver uma c´lula com o campo Valor contendo A(i, j), o campo a e
Linha contendo i e o campo Coluna contendo j. Esta c´lula dever´