Tad fila

Disponível somente no TrabalhosFeitos
  • Páginas : 11 (2685 palavras )
  • Download(s) : 0
  • Publicado : 13 de março de 2012
Ler documento completo
Amostra do texto
ˆ FACULDADE DE CIENCIAS E TECNOLOGIA DA UNIVERSIDADE DE COIMBRA
´ DEPARTAMENTO DE MATEMATICA

T. A. D. FILA RELAT´RIO O

1

INTRODUCAO ¸˜

1

1

Introdu¸ao c˜

Podemos definir uma fila como sendo uma lista ordenada na qual as inser¸˜es s˜o feitas co a num extremo, que designamos por cauda ou “fim” da fila, ao passo que as elimina¸˜es co s˜o feitas no outro extremo, designado porcabe¸a ou frente da fila. a c As opera¸˜es b´sicas numa fila s˜o: co a a Inserir - que insere um elemento no fim da fila. Remover - que apaga o elemento da frente da fila. A figura que se segue ilustra o modelo abstracto de uma fila. frente
'

Fila F

fim
'

F.remover()

F.inserir()

Uma fila ´ uma estrutura do tipo FIFO (first in first out), isto ´, “o primeiro e e elemento a entrar ´ o primeiro asair”. Um TAD fila ´ uma estrutura de dados que e e cont´m uma colec¸˜o de dados seguindo a pol´ e ca ıtica do FIFO, e ainda um conjunto de opera¸˜es gerais que, para al´m das opera¸˜es principais j´ referidas, engloba ainda um co e co a conjunto de outras opera¸˜es auxiliares, tais como: co • frente • fim • vazia • cheia • tamanho • listar que mais ` frente trataremos com maior pormenor. a O objectofila ´, pois, uma instancia¸˜o de uma classe espec´ e ca ıfica que generaliza os m´todos necess´rios para manipular um objecto fila. e a Em POO existem v´rias aproxima¸˜es para implemetar a classe Fila, sendo que a co estas diferem estre si, basicamente na forma como os dados est˜o alocados e como os a elementos est˜o relacionados entre si. a

2

Objectivos

Os objectivos principais deste trabalhos˜o a implementa¸˜o do TAD Fila em POO a ca e de um programa que permita demonstrar e testar a classe Fila implementada. Tal como j´ foi referido, v´rias s˜o as implementa¸˜es poss´ a a a co ıveis para esta classe, e portanto proposemo-nos a explorar uma delas n˜o deixando, contudo, de fazer referˆncia a oua e tras, igualmente poss´ ıveis. Pretende-se com este trabalho a aplica¸˜o deconhecimentos ca te´ricos apreendidos no ˆmbito da POO ilustrando-os com a defini¸˜o do TAD Fila, o a ca nomeadamente:

3

DESCRICAO ¸˜ • a organiza¸˜o do c´digo fonte em Objectos; ca o • a defini¸˜o das propriedades de um Objecto numa Classe; ca • a separa¸˜o do Objecto nas suas componentes: ca dados - que definem a informa¸˜o contida no Objecto (atributos) ca m´todos - que definem as opera¸˜es que podemser realizadas sobre o Objecto e co

2

• a Abstrac¸˜o - focar as caracter´ ca ısticas principais de um objecto, que o distinguem de todos os outros; • o princ´ ıpio da Modularidade - divis˜o do c´digo fonte em m´dulos que se relaa o o cionam entre si; • o Encapsulamento - (sonega¸˜o da informa¸˜o) uma vez escolhida uma impleca ca menta¸˜o, esta dever´ permanecer oculta, ou seja, os objectosescondem a sua ca a estrutura interna; fora do objecto, pode n˜o ser poss´ aceder aos seus dados ou a ıvel at´ mesmo ver o c´digo fonte exacto de um seu m´todo. e o e • a Instancia¸˜o ca

3
3.1

Descri¸ao c˜
M´todos e

Os m´todos que definem a classe fila s˜o: e a • Construir e inicializar um objecto Fila • Destruir um objecto Fila • Verificar se um objecto Fila ´ vazio e • Verificar se umobjecto Fila est´ cheio a • Consultar o elemento da frente de um objecto Fila • Consultar o elemento da cauda de um objecto Fila • Inserir um elemento num objecto Fila • Remover um elemento num objecto Fila • Determinar o tamanho de um objecto Fila • Listar os elementos de um objecto Fila

3

DESCRICAO ¸˜

3

3.2

Classe Fila - uma implementa¸ao dinˆmica c˜ a

Nesta implementa¸˜o oselementos da fila s˜o armazenados numa lista simplesmente ca a ligada. Deste modo, n˜o existe limita¸˜o em termos do n´mero m´ximo de elementos, a ca u a ao contr´rio do que acontece noutras aproxima¸˜es, sendo portanto desnecess´ria a a co a cria¸˜o de um m´todo que verifique se a fila est´ ou n˜o cheia. Um ponto importante ca e a a a destacar ´ a defini¸˜o de uma classe dentro da classe fila. Na...
tracking img