Aulas Do 2º Semestre

Análise e Desenvolvimento de Sistemas

Web Aula 1

Introdução a Listas Lineares de Fila por Alocação Sequencial, utilizando teste de mesa para melhor compreensão.

• Implementação das operações de inserção, pesquisa, modificação e exclusão, em uma lista linear de fila por alocação sequencial.

• Inserção: da variável Y para V .............. Y → V

• Respeitando a regra de fila “sempre no final”.

• Exclusão: de V para variável Y ............ Y ← V

• Respeitando a regra de fila “sempre no início”

• Pesquisa: localiza variável Y em V ....... Y ? V

• Respeitando a regra de fila “a partir do início”

• Modificação: localiza variável Y em V; troca valor de V pela variável X X ↔ V ? V

P�gina

Um exemplo de Inserção da variável Y para V .............. Y → V

se FIM = n

• então OVERFLOW;

• senão FIM := FIM +1;

• V[FIM] := Y; (onde Y = Felipe)

• se FIM = 1 então COMEÇO := 1;

• fim se;

Segue abaixo a tela inicial do nosso algoritmo, onde encontraremos valores para Fim = 3, Y= Felipe e Começo = 1.

Próximo passo:

• Fim começa com valor 3 e N com valor 4.

• Como não são iguais, não teremos erro de fim de fila “overflow”. Então, como não é final de fila:

• Fim será 3 mais 1, ficando Fim = 4. Observe na figura abaixo.

P�gina

Último passo:

• V[FIM] := Y , ou seja, V[4] := Felipe (onde V[4] indica a quarta posição do vetor da fila)

• E se Fim fosse 1, iria atribuir 1 para a variável começo “se FIM = 1, então, COMEÇO := 1”.

(neste primeiro exemplo, esta condição não será atendida, pois Fim está valendo 4 e não 1).

Exemplo: Inserção da variável Y para V - Y → V com Overflow

se FIM = n

• então OVERFLOW;

• senão FIM := FIM +1;

• V[FIM] := Y; (onde Y = Felipe)

• se FIM = 1 então COMEÇO := 1;

• fim se;

Utilizando o nosso algoritmo, ainda podemos avaliar que a variável Fim está iniciando com valor 4, e N também tem valor 4. Então, se FIM = n, teremos a situação de OVERFLOW;

P�gina

Exemplo: de YèV para 1º elemento Y → V

se FIM = n

• então OVERFLOW;

• senão FIM := FIM +1;

• V[FIM] := Y; (onde Y = Felipe)

• se FIM = 1 então COMEÇO := 1;

• fim se;

Primeiro passo: onde Fim = 0, então Fim = N não, pois N é igual a 4.

Passo 2 – Fim irá receber 0 + 1, ficando com valor Fim = 1.

P�gina

[FIM] := Y , ou seja, V[1] := Felipe (onde V[1] indica a primeira posição do vetor da fila)

• Note que iremos, então, na condição ainda não explorada,

• se FIM = 1 então Começo := 1

Um exemplo de Exclusão: de V para variável Y Y ← V

se FIM = 0

• então UNDERFLOW;

• senão Y:= V[COMEÇO];

• COMEÇO := COMEÇO + 1;

• se COMECO>FIM então COMEÇO := 0;

• FIM := 0;

• fim se

• fim se;

Se o Fim for igual a zero, então teremos um underflow, ou seja, não há nada na fila. Neste exemplo inicial, não temos situação de underflow.

Siga o primeiro modelo da figura à esquerda.

Situação inicial do nosso algoritmo, então, como fim não é zero,

Siga o modelo da figura à direita.

Primeiro, Y irá receber o valor encontrado no vetor na posição 1 que o valor da variável começo.

se COMEÇO>FIM, então, COMEÇO := 0 e FIM := 0 – como começo não é maior, eu fim ainda não irá satisfazer esta condição.

A partir da figura da sua direita, execute o algoritmo mais duas vezes e nos encaminhe o teste de mesa da forma apresentada acima.

Execute o mesmo algoritmo, mas iniciando com a variável COMEÇO = 3