AS ESTRUTURAS DE DADOS
Por: Isabela Bertochi • 24/5/2020 • Trabalho acadêmico • 5.295 Palavras (22 Páginas) • 223 Visualizações
[pic 1]
Isabela Tempesta Bertochi;
RA: N518JF-3
Arthur Felipe Reducino.
RA: N5334B-0
Disciplina: Linguaguem e técnicas de programação
Professor: Douglas Rodrigues
Estrutura de dados
Atividade complementar entregue
como requisito parcial para
composição da nota NP2 da disciplina
linguagem e técnicas de programação.
Filas
Uma fila é uma estrutura de dados dinâmica que admite remoção de elementos e inserção de novos objetos. Mais especificamente, uma fila (= queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo.
Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).
Implementação em um vetor__________________
Suponha que nossa fila mora em um vetor fila[0..N-1]. (A natureza dos elementos do vetor é irrelevante: eles podem ser inteiros, bytes, ponteiros, etc.) Digamos que a parte do vetor ocupada pela fila é
fila[p..u-1] .
O primeiro elemento da fila está na posição p e o último na posição u-1. A fila está vazia se p == u e cheia se u == N. A figura mostra uma fila que contém os números 111, 222, … , 666:
0 | p | u | N-1 | ||||||||
111 | 222 | 333 | 444 | 555 | 666 |
Para tirar, ou remover (= delete = de-queue), um elemento da fila basta fazer: x = fila[p++];
Isso equivale ao par de instruções x = fila[p]; p += 1;, nesta ordem. É claro que você só deve fazer isso se tiver certeza de que a fila não está vazia. Para colocar, ou inserir (= insert = enqueue), um objeto y na fila basta fazer: fila[u++] = y;
Isso equivale ao par de instruções fila[u] = y; u += 1;, nesta ordem. Note como esse código funciona corretamente mesmo quando a fila está vazia. É claro que você só deve inserir um objeto na fila se ela não estiver cheia; caso contrário, a fila irá transbordar(ou seja, ocorre um overflow).
Para ajudar o leitor human, podemos embalar as operações de remoção e inserção em duas pequenas funções. Se os objetos da fila forem números inteiros, podemos escrever
int tiradafila (void) {
return fila[p++];
}
void colocanafila (int y) {
fila[u++] = y;
}Estamos supondo aqui que as variáveis fila, p, u e N são globais, isto é, foram definidas fora do código das funções. (Para completar o pacote, precisaríamos de mais três funções: uma que crie uma fila, uma que verifique se a fila está vazia e uma que verifique se a fila está cheia; veja exercício abaixo.)
Aplicação: distâncias________________________
A ideia de fila aparece naturalmente no cálculo de distâncias em um grafo. (Uma versão simplificada do problema é a varredura por níveis de uma árvore binária.) Imagine N cidades numeradas de 0 a N-1 e interligadas por estradas de mão única. As ligações entre as cidades são representadas por uma matriz A da seguinte maneira:
A[i][j] vale 1 se existe estrada de i para j
e vale 0 em caso contrário. Suponha que a matriz tem zeros na diagonal, embora isso seja irrelevante. Segue um exemplo em que N vale 6:
| [pic 2] |
A distância de uma cidade c a uma cidade j é o menor número de estradas que precisamos percorrer para ir de c a j. (A distância de c a j é, em geral, diferente da distância de j a c.) Nosso problema: dada uma cidade c,
determinar a distância de c a cada uma das demais cidades.
As distâncias podem ser armazenadas em um vetor dist: a distância de c a j é dist[j]. É preciso tomar uma decisão de projeto para cuidar do caso em que é impossível ir de c a j. Poderíamos dizer que dist[j] é infinito nesse caso; mas é mais limpo e prático dizer que dist[j] vale N, pois nenhuma distância real pode ser maior que N-1. Se tomarmos c igual a 3 no exemplo acima, teremos
...