lista2_fila

Prévia do material em texto

IBILCE UNESP Departamento de Ciências de Computação e Estatística 
Disciplina Estrutura de Dados 
Curso Bacharelado em Ciências da Computação 
Profa. Dra. Inês Ap.Gasparotto Boaventura 
Lista de Exercícios Filas 
1. Uma fila circular pode ser definida da seguinte forma 
 
 
 
 
 
 
 Defina e implemente a classe nocirc 
 
2. Use a classe nocirc do exercício anterior e desenvolva uma implementação da classe 
fila, conforme ilustração abaixo. Declare um nó cabeça como um elemento private da 
classe e realize inserções e remoções como segue: 
Qinsert: inserir após o nó final. 
Qdelete: Remover após o nó cabeça. Verificar para não remover elementos de 
uma fila vazia. 
 
 
 
 
 
 
 
 
 
3. Para um dado número inteiro n > 1, o menor inteiro d > 1 que divide n é chamado 
de fator primo. É possível determinar a fatoração prima de n achando-se o fator 
primo d e substituindo n pelo quociente n / d, repetindo essa operação até que n 
seja igual a 1. Utilizando um dos TADs vistos em sala (Lista, Pilha ou Fila) para 
auxiliá-lo na manipulação de dados, implemente uma função que compute a 
fatoração prima de um número imprimindo os seus fatores em ordem decrescente. 
Por exemplo, para n=3960, deverá ser impresso 11 * 5 * 3 * 3 * 2 * 2 * 2. Justifique 
a escolha do TAD utilizado. 
 
4. Considere a implementação de filas usando vetore “circulares”. Escreva um método 
FuraFila(T item) que insere um item na primeira posição da fila. O detalhe é que 
seu procedimento deve ser O(1), ou seja, não pode movimentar os outros itens da 
fila. (observe que este neste caso, estaremos desrespeitando o conceito de FILA – 
primeiro a entrar é o primeiro a sair). 
 5 8 10 L 
L 
Fila Vazia 
 
início
final início 
final 
� representação de fila vazia (o 
primeiro nó é um nó extra e não tem 
informações da fila) 
 
5. Considere uma pilha P vazia e uma fila F não vazia. Utilizando apenas os testes de 
fila e pilha vazias, as operações Enfileira, Desenfileira, Empilha, Desempilha, e 
uma variável aux do Tipo Item, escreva uma função que inverta a ordem dos 
elementos da fila. 
 
6. Se uma fila representada por arranjos (vetores) não é considerada circular, 
sugere-se que cada operação Desenfileira deve deslocar para “frente” todo 
elemento restante de uma fila. Um método alternativo é adiar o deslocamente até 
que “tras” seja igual ao último índice do vetor. Quando essa situação ocorre e faz-
se uma tentativa de inserir um elemento na fila, a fila inteira é deslocada para 
“frente”, de modo que o primeiro elemento da fila fique na primeira posição do 
vetor. Quais são as vantagens desse método sobre um deslocamento em cada 
operação Desenfileira? Quais as desvantagens? Reescreva as funções 
Desenfileira, Enfileira e Vazia usando esse novo método. 
 
7. Sabendo que as funções de alocação e liberação de memória gastam muito 
tempo de processamento, implemente funções insere e remove em uma Fila 
Dinâmica de modo que nunca se liberem os nós removidos. Ou seja, deve-se 
de alguma forma marcar os nós que não são mais utilizados. Quando um novo 
elemento for inserido, deve-se utilizar o espaço já alocado, caso tiver algum 
livre, caso contrário deve-se alocar um novo espaço. Defina as estruturas Fila e 
No para tratar este problema. 
 
8. Dada um fila implementada por meio de uma lista simplesmente encadeada, 
implemente uma função inverte(Fila *f) que inverta a ordem dos elementos da 
fila. OBS: utilize apenas as funções de manipulação de filas.