AS ESTRUTURAS DE DADOS

[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:

0 1 2 3 4 5 0 0 1 0 0 0 0 1 0 0 1 0 0 0 2 0 0 0 0 1 0 3 0 0 1 0 1 0 4 1 0 0 0 0 0 5 0 1 0 0 0 0

[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