Codigo java

Universidade Federal de Ouro Preto – UFOP Instituto de Ciências Exatas e Biológicas – ICEB Departamento de Computação – DECOM Disciplina: Algoritmos e Estruturas de Dados I – CIC102 Professor: David Menotti ([e-mail])

Trabalho Prático 2 Listas / Filas / Pilhas
Valor: 1,2 pontos (12% da nota total) Documentação em Latex: 0,1 pontos extra Data de entrega: 22/10/2008

Este trabalho prático é divido em 3 partes principais. A primeira parte está relacionada com Listas duplamente encadeadas, enquanto que a segunda e terceira estão direcionadas à pilhas e filas, respectivamente.

1. Matrizes Esparsas
(Utilização de Listas por meio de Estruturas Auto-Referencias ([3] apud [2]))

Objetivos Consiste em concretizar os conceitos de Listas implementadas por encadeamento através de uma aplicação: Matrizes esparsas. 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 usais 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 presentar 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. Cad 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. Cada célula da estrutura, além das células cabeça, representará os termos diferentes de zero da matriz e deverá ser como no código abaixo: typedef struct Celula { Celula direita, abaixo; int linha, coluna; double valor; } Celula;

O campo abaixo deve ser usado para referenciar o elemento diferente de zero na mesma coluna. O campo