Codigo java

Disponível somente no TrabalhosFeitos
  • Páginas : 14 (3354 palavras )
  • Download(s) : 0
  • Publicado : 27 de junho de 2011
Ler documento completo
Amostra do texto
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 (menottid@gmail.com)

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 trabalhoprá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 deuma 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ãoarmazenarmos 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 campodireita deve ser usadao para referenciar o próximo elemento diferente de zero na mesma linha. Dada uma matriz A, para um valor A(i,j) diferente de zero, deverá haver uma célula com o campo valor contendo A(i,j), o campo linha contendo i e o campo coluna contendo j. Essa célula deverá pertencer a lista ciruclar da linha i e também deverá pertencer à lista circular da coluna j. Ou seja, cada célulapertencerá a duas listas ao mesmo tempo. Para diferenciar as células cabeça, coloque -1 nos campos linha e coluna dessas células. Considere a seguinte matriz esparsa:

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 (menottid@gmail.com)  50  10 A= 0   − 30  0 0 0 20 0 0 0 − 60 0  0 0  5 

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 amatriz toda, desde que r seja suficientemente pequeno.

−1 −1

−1

−1

−1

−1

−1

1

1 50

−1

2

1 10

2

3 20

−1

−1

4

1 −30

4

3 −60

4

4 5

Figura 1. Exemplo de Matriz Esparsa. Dada a representação de listas duplamente encadeadas, o trabalho consiste em desenvolver em C/C++ um tipo abstrato de dados Matriz com as seguintes operações, conformeesta especificação:

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 (menottid@gmail.com)
a) void imprimeMatriz() Esse método imprime (uma linha da matriz por linha na saída) a matriz A, inclusive os elementos iguais a zero. b) void...
tracking img