Matrizes Esparsas

Comentários Gerais

1.
Comece a fazer este trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.
2.
Este trabalho exercita conceitos e estruturas de dados apresentados nos capítulos 1 e 2 do livro Ziviani (1993).
3.
Vão valer pontos clareza, indentação e comentários no programa.

O que deve ser apresentado:

1.
Listagem do programa em Pascal.
2.
Listagem dos testes executados.
3.
Descrição sucinta (por exemplo, desenho), das estruturas de dados e as decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.
4.
Estudo da complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).
[Zivi93] Ziviani, Nivio, Projeto de Algoritmos Com Implementações em Pascal e C, Editora Pioneira, 1993.

Matrizes Esparsas

Utilização de Listas Através de Apontadores

Retirado de (Árabe, 1992)

Matrizes esparsas são matrizes nas quais a maioria das posições são preenchidas por zeros. Para estas matrizes, podemos economizar um espaço significativo de memória se apenas os termos diferentes de zero forem armazenados. As operações usuais sobre estas 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 representar estruturas com tamanho variável e/ou desconhecido é através de alocação encadeada, utilizando listas. Vamos usar esta representação para armazenar as matrizes esparsas. Cada coluna da matriz será representada por uma lista linear circularListas!circulares 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. Cada célula da estrutura, além das células-cabeça, representará os termos diferentes de zero da matriz e devem ter o seguinte tipo:

type Apontador = ^ TipoC'elula;