ESCOLA SECUNDÁRIA DE VOUZELA Curso Tecnológico de … · Curso Tecnológico de Informática ... Designação Operador igual a = diferente de ... Tal como a saída de dados do computador

E S C O L A S E C U N D Á R I A D E V O U Z E L A Curso Tecnológico de Informática

1ª Versão 1999/2000

12º Ano

ApontamentosApontamentosApontamentosApontamentos Prof. José Alberto Pereira

NN OO TT AA II NN TT RR OO DD UU TT ÓÓ RR II AA

O objectivo destes apontamentos não é substituir as aulas, como tal, a exposição

de qualquer matéria não é realizada de modo detalhado. Será necessário consultar

entre outra bibliografia, a bibliografia geral da disciplina e outros manuais de

aplicação. O aluno também deve procurar uma actualização permanente, criando o

hábito de consultar publicações técnicas, investigar novos conceitos e discutir sobre

eles.

A disciplina tem áreas perfeitamente teóricas e rubricas eminentemente práticas.

Assim, uma a duas horas semanais serão dadas para desenvolvimento dos pontos

teóricos ao longo do ano. As restantes horas serão para exploração das unidades

práticas. Por fim no terceiro período haverá uma unidade final denominada projecto

e um exame a nível nacional cuja realização não é em laboratório.

Para além dos testes a avaliação desta disciplina é centrada nos trabalhos

práticos desenvolvidos pelo aluno, no acompanhamento do seu progresso, da sua

capacidade de trabalho em equipa e na observação da sua criatividade. A avaliação

desta disciplina é complementada pela observação da evolução do desempenho

técnico do aluno na sala de aula, no uso de software de base e ferramentas

adicionais, capacidade de ultrapassar dificuldades e solucionar problemas, bem

como facilidade de trabalho em equipa.

O professor: José Alberto Pereira

ESEV(Prof.Serv.) - Prof. José Alberto Pereira i

ÍÍ NN DD II CC EE

I ALGORITMOS 1

1. PSEUDOCÓDIGO 1

2. VARIÁVEIS 2

3. OPERADORES 3

4. INSTRUÇÕES 4

4.1. INSTRUÇÕES SIMPLES 4

Instruções de escrita 4

Instruções de leitura 4

Instruções de atribuição 5

4.2. INSTRUÇÕES ESTRUTURADAS OU ESTRUTURAS DE CONTROLO 6

Instruções compostas 6

Estrutura de decisão condicional - "Se" 7

Estrutura de escolha múltipla - "Caso" 8

Estrutura de repetição ou ciclos 9

Estrutura de repetição ou ciclos - "Repita para" 9

Estrutura de repetição ou ciclos - "Repita enquanto" 11

Estrutura de repetição ou ciclos - "Repetir ... até" 11

5. SUBALGORITMOS 12

5.1. EXEMPLOS 14

Função MÉDIA 14

Exemplo de utilização da função MÉDIA 14

Procedimento DIVIDE 15

Exemplo de utilização do procedimento DIVIDE 15

II ESTRUTURAS DE DADOS 16

1. ESTRUTURA DE DADOS 16

2. ESTRUTURA DE DADOS SIMPLES 16

2.1. VALORES LÓGICOS 17

2.2. INTEIROS 17

2.3. REAIS 18

Índice

ESEV(Prof.Serv.) - Prof. José Alberto Pereira ii

2.4. ALFANUMÉRICOS 20

2.5. PONTEIROS 21

3. ESTRUTURA DE DADOS COMPLEXAS 21

3.1. VECTORES 21

3.2. MATRIZES 23

3.3. REGISTOS 24

3.4. LISTAS 25

3.5. PILHAS 25

Representação de pilhas em pascal 26

3.6. FILAS 28

Representação de filas em pascal 29

3.7. LISTAS LIGADAS 38

Inserção de nós numa lista ligada 40

Remoção de nós numa lista ligada 41

Inserção de um elemento depois de um determinado nó 43

Implementação de uma pilha por meio de uma lista 44

Implementação de uma fila por meio de uma lista 45

3.8. FICHEIROS 46

Ficheiros do tipo texto 47

Ficheiros do tipo binário ou definidos pelo programador 47

Operações com ficheiros 48

Instruções em pseudocódigo para manipulação de ficheiros 49

Suportes físicos de ficheiros 50

3.9. ÁRVORES BINÁRIAS 51

Conceitos Básicos 51

Estrutura de uma árvore binária 52

Operações sobre uma árvore binária 52

Aplicações de árvores binárias 53

Travessias de uma árvores binárias 55

Algumas funções recursivas 57

4. MÉTODOS DE ORDENAÇÃO E PESQUISA 58

4.1. PESQUISA LINEAR NUM VECTOR NÃO ORDENADO 58

1ª Versão 58

2º Versão 59

4.2. PESQUISA LINEAR NUM VECTOR ORDENADA 59

4.3. PESQUISA BINÁRIA 60

4.4. FUSÃO SIMPLES 61

Índice

ESEV(Prof.Serv.) - Prof. José Alberto Pereira iii

4.5. ORDENAÇÃO POR INSERÇÃO SIMPLES 62

4.6. ORDENAÇÃO POR SELECÇÃO SIMPLES 63

4.7. ORDENAÇÃO POR TROCA SIMPLES 64

ESEV(Prof.Serv.) - Prof. José Alberto Pereira 1

II

AA LL GG OO RR II TT MM OO SS

1 . P S E U D O C Ó D I G O

Por pseudocódigo entende-se um código de escrita em que se utilizam

representações simbólicas para indicar as instruções do algoritmo. Essas

representações simbólicas são, usualmente, um misto de palavras da nossa

linguagem natural com termos e notações típicas de uma linguagem de

programação.

O uso da escrita em pseudocódigo presta-se a uma aproximação sucessiva à

versão do algoritmo na linguagem utilizada, ou seja, pode-se ir progredindo por

fases, revendo o pseudocódigo e substituindo-o progressivamente por terminologia

própria da linguagem de programação.

Não é demais relembrar que, depois de efectuar o algoritmo, deve-se verificar se

está escrito sem falhas do ponto de vista dos objectivos que se pretendiam alcançar,

por imprecisões, deficiente formulação algorítmica, vícios de raciocínio, etc.

Sintaxe de um algoritmo em pseudocódigo: Algoritmo <Título>

<Descrição>

<Passo>. [<Comentário>]

<Instruções>

(...)

Unidade I Algoritmos

ESEV(Prof. Serv.) - Prof. José Alberto Pereira 2

Exemplo de um algoritmo em pseudocódigo: Algoritmo PERCENTAGEM

Este algoritmo, para um vector de 15 notas de um teste, determina a percentagem dos

alunos com nota superior à média.

1. [Inicializar variáveis]

SOMA ! 0

CONT ! 0

2. [Ler as 15 notas e calcular a sua soma]

Repita para K=1,2,...,15

Leia(NOTA[K])

SOMA ! SOMA + NOTA[K]

3. [Calcular a média]

MÉDIA ! SOMA / 15

4. [Calcular o número de alunos com nota superior à média]


Se NOTA[K] > MÉDIA

Então CONT ! CONT + 1

5. [Calcular e imprimir a percentagem]

PERC ! (100 * CONT) / 15

Escreva('A percentagem de alunos com nota superior à média é ',PERC,'%')

6. [Terminar]

Saída

2 . V A R I Á V E I S

As variáveis podem assumir:

• um carácter global, quando são declaradas para uso em todo o algoritmo;

• um carácter local, quando são declaradas apenas para uso dentro do

subalgoritmo.



3 . O P E R A D O R E S

Operadores em pseudocódigo:

OPERADORES ARITMÉTICOS Designação Operador

Adição + Subtracção - Multiplicação * Divisão /

Os operadores aritméticos utilizam-se normalmente com dois operandos. No

entanto, os operadores + e - também podem ser usados com um só operando, caso

em que significam: o sinal positivo ou o sinal negativo atribuído ao operando.

OPERADORES DE COMPARAÇÃO Designação Operador

igual a = diferente de ≠ Maior que > menor que < Maior ou igual a ≥ menor ou igual a ≤

Os operandos empregues com os operadores de comparação devem ser de

tipos compatíveis entre si. Os resultados que devolvem são sempre do tipo valor

lógico, ou seja, verdadeiro ou falso. Estes operadores podem ser usados com

quaisquer tipos de ordinais, com reais, alfanuméricos e com ponteiros.

OPERADORES DE VALORE LÓGICO Designação Operador

Negação não Conjunção e Disjunção ou

Os operadores de valores lógicos operam normalmente com operandos do tipo

valor lógico e devolvem resultados desse mesmo tipo. Também são utilizados com

muita frequência, tal como os operadores relacionais, em estruturas de decisão e no

controlo de ciclos de repetição.



4 . I N S T R U Ç Õ E S

Tipicamente, um algoritmo consiste numa série de instruções escritas numa

determinada linguagem, segundo determinada ordem.

As instruções são frases, por assim dizer, que enunciam ou indicam as acções

ou operações que se pretende realizar com o algoritmo.

As instruções num algoritmo podem ser:

• Instruções simples;

• Instruções estruturadas ou estruturas de controlo.

Umas e outras são compostas por comandos. Os comandos são, normalmente,

palavras, abreviaturas ou conjuntos de caracteres que sugerem a acção que é

desempenhada; por exemplo: Saída; Se; Então; Repita; Escreva; Leia; etc.

4.1. Instruções Simples

Instruções de escrita

As instruções de escrita são aquelas que servem para enviar dados (mensagens,

valores de variáveis, etc.) para um dispositivo de saída ou periférico de "output".

Como se sabe, o dispositivo de saída mais comum no trabalho com um

computador é o monitor de vídeo ou ecrã; no entanto, o envio de dados para a

impressora ou para um ficheiro em disco ou disquete também são tarefas normais e,

por vezes, mesmo imprescindíveis.

Exemplos das instruções de escrita, mais usuais, em pseudocódigo: [Imprimir a mensagem]

Escreva('Não existe quarto vago do tipo escolhido.')

[Imprimir a percentagem]

Escreva('A percentagem de alunos com nota superior à media é ', PERC, '%')

Instruções de leitura

Tal como a saída de dados do computador para um periférico é essencial,

também a entrada de dados o é.



Os principais dispositivos que permitem a leitura, entrada ou "input" de dados

num sistema informático são, como se sabe, em primeiro lugar, o teclado, em

segundo, os dispositivos de armazenamento secundário, ou seja os discos e

disquetes, e ainda mais alguns outros, como o rato, etc.

Exemplo de uma instrução de escrita em pseudocódigo:

[Ler a remuneração mensal]

Leia(REMUNERAÇÃO)

[Ler as variáveis X e Y ]

Leia(X, Y)

Instruções de atribuição

Muitos dos dados com que se opera num algoritmo são variáveis. As variáveis e

constantes num algoritmo são designadas por meio de identificadores. Um

identificador é um nome normalmente atribuído pelo algoritmo ou utilizador a um

elemento com que se pretende trabalhar dentro de um algoritmo.

Exemplos, apresentados numa tabela com possíveis entidades e os

correspondentes identificadores das variáveis:

Nome do cliente NOME Morada dos clientes MORADA Data em que foi feita a encomenda DATA

Por convenção, vamos escrever o nome dos identificadores em letras

maiúsculas, para maior legibilidade do algoritmo.

Quando se trata de variáveis, um identificador vai traduzir-se em termos de

compilação, num endereço de memória, o qual corresponde a um determinado

espaço nessa mesma memória, onde se vai armazenar um dado - o valor que a dita

variável assume em cada momento. Isto leva-nos a considerar, em programação,

que um identificador é um endereço simbólico, pois que se preferimos, um candidato

a endereço de memória.



Exemplos de instruções de atribuição, em pseudocódigo: [Inicializar variáveis]

SOMA ! 0

[Calcular a Média e incrementar Valor]

MÉDIA ! SOMA / 15

VALOR ! VALOR + 1

4.2. Instruções Estruturadas ou Estruturas de Controlo

Nas estruturas de um algoritmo é, frequentemente, necessário:

• jogar com determinadas condições, para decidir se se deve executar uma ou

outra acção;

• repetir uma série de instruções, um determinado número de vezes ou

enquanto se verificar uma certa condição;

• noutros casos ainda, temos um conjunto de instruções que se repete em

diversos pontos do programa, tornando-se então útil passar a tratá-lo como

um subalgoritmo.

Instruções compostas

Uma instrução composta não é mais que um conjunto de instruções englobadas entre dois delimitadores - um início e um fim da referida instrução ("Início ... Fim") -

que, assim deve ser considerada um bloco.

A Sintaxe, em pseudocódigo, é a seguinte: <Instrução 1>

<Instrução 2> Início

<Instrução 2.1>

...

<Instrução 2.n>

Fim

...



Estrutura de decisão condicional - "Se"

A estrutura de decisão condicional mais difundida e utilizada é a que se baseia

na instrução "Se".

As estruturas "Se" podem ser "encaixadas" umas dentro das outras.

A Sintaxe desta estrutura, em pseudocódigo, é a seguinte: Se <Condição>

Então <Instrução se condição verdadeira>

[Senão <Instrução se condição falsa>]

• <Condição> - a condição de controlo é normalmente uma expressão do tipo

lógico, isto é, que pode assumir apenas um entre dois valores possíveis:

verdadeiro ou falso;

• <Instrução ...> - obviamente, será uma determinada acção que se pretende

efectuar. Esta instrução tanto pode ser uma instrução simples, como uma

instrução composta, ou seja, um conjunto de instruções;

• o significado dos parêntesis rectos [...] indica que se trata de uma parte opcional. Assim, o comando Senão e a sua respectiva instrução é opcional, ou

seja, só é utilizável quando se desejar ou for necessário.

Se tivermos um conjunto de instruções (instruções compostas) para considerar dentro da estrutura podemos inseri-la entre delimitadores "Início ... Fim".

Exemplos de estruturas de decisão condicional, em pseudocódigo: [Exemplo 1]

Se X = 1 e K > VALOR

Então Se K < MENOR

Então M ! VALOR

[Exemplo 2a]

Se ANDAR = 0

Então QUARTO_VAGO ! 0

K ! 0



[Exemplo 2b]

Se ANDAR = 0

Então Início

QUARTO_VAGO ! 0

K ! 0

Fim

Estrutura de escolha múltipla - "Caso"

Numa estrutura "Caso" há uma variável, cujos valores que possa assumir vão

ser utilizados no controlo das alternativas ou acções a escolher - a esta variável é

costume chamar-se selector.

A Sintaxe desta estrutura, em pseudocódigo, é a seguinte:

Caso <Variável/Selector>

<Valor 1> : <Instrução 1>

<Valor 2> : <Instrução 2>

(...)

<Valor n> : <Instrução n>

[Senão : <Instrução>]

Fim (Caso).

Quando se indica <Valor 1>, <Valor 2>, etc., estamos a referir aos valores

possíveis que a variável de controlo poderá assumir. Pode ser apenas um valor ou

um conjunto de valores.

Quando de indica <Instrução 1>, < Instrução 2>, etc., pode tratar-se de uma só

instrução ou de uma instrução composta, portanto um conjunto de acção a realizar.

Em algumas implementações existe também uma cláusula "Senão" que se

destina a complementar o leque de alternativas, no caso de haver ainda mais

hipóteses não explicitadas, e em que pode haver ainda uma outra acção ou conjunto

de acções a indicar.



Estrutura de repetição ou ciclos

Frequentemente é necessários repetir uma certa instrução ou conjunto de

instruções um determinado número de vezes ou manter um ciclo ("Loop") de

repetições um número indeterminado de vezes, enquanto se verificar certa condição.

Essa repetição, na maior parte das vezes, não tem que ser uma repetição exacta

das mesmas operações, pois pode haver pelo meio certos dados (variáveis) ou

parâmetros que se vão alterando à medida que o ciclo vai decorrendo.

Exemplo de estruturas de repetição:

• Repita para ...

• Repita enquanto ...

• Repetir ... até

Enquanto numa estrutura do tipo "Repita para..." o número de vezes que vai

ocorrer a repetição do ciclo é determinada à partida por uma variável de controlo que é incrementada ou decrementada à medida que o ciclo decorre. Na estrutura "Repita

Enquanto..." e "Repetir...até" o ciclo decorrerá um número indeterminado de vezes,

dependendo da verificação ou não da condição de controlo - o que depende dos

acontecimentos no decurso do próprio ciclo.

Estrutura de repetição ou ciclos - "Repita para"

Esta estrutura de repetição é controlada por uma variável - Variável de controlo -

que parte de um determinado valor e incrementa ou decrementa até um outro

determinado valor.

A Sintaxe, em pseudocódigo, é a seguinte: Repita para <Variável>=<Valores>

<Instrução>

Ou ainda:

Repita até ao passo <Passo> para <Variável>=<Valores>

<Instrução>

...



As expressões <Valores> podem ser valores numéricos directos, valores de

ouras variáveis ou expressões, desde que esses valores sejam números inteiros.

À variável que controla o ciclo, também é costume chamar "Índice" ou variável de

iteração, na medida em que vai assumindo valores sucessivos.

Os valores da variável de controlo podem variar num sentido crescente ou

decrescente.

Se tivermos um conjunto de instruções (instruções compostas) para considerar

dentro da estrutura podemos inseri-la entre delimitadores "Início ... Fim".

Outra Sintaxe (não usada em exame):

Para <Variável> desde <Valor Inicial> até <Valor Final>, incremento <Incremento>

<Instrução 1>

<Instrução 2>

...

<Instrução n>

Fim (Para)

Exemplos, em pseudocódigo: [Ler 10 elementos de um vector]


Leia (VEC[K])

[Ler as 15 notas e calcular a sua soma]


Leia (NOTA[K])

SOMA ! SOMA + NOTA[K]

[Inicializar a matriz TOTAIS]

Repita para I=1,2,...,10

Repita para J=1,2,...5

TOTAIS[I, J] ! 0



Outro exemplo: 1. [Percorre todos os dias da semana e inicializar a quantidade mínima]

Repita até ao passo 4 para J=1,2,...,7

QUANT_MIN ! SEMANAS[J]

2. [Procura o dia da semana mais eficiente]

(...)

Estrutura de repetição ou ciclos - "Repita enquanto"

O ciclo ou estrutura de repetição começa com a verificação de uma expressão

ou condição, digamos, a "condição de controlo".

Se a condição for verdadeira, a instrução ou conjunto de instruções, será

executado um número vezes indeterminado à partida, dependendo de a condição de

controlo se manter verdadeira ou passar a falsa.

A Sintaxe, em pseudocódigo, é a seguinte: Repita enquanto <Condição>

<Instrução>

Se tivermos um conjunto de instruções (instruções compostas) para considerar dentro da estrutura podemos inseri-la entre delimitadores "Início ... Fim".

Exemplo, em pseudocódigo: [Pesquisa um quarto vago]

J ! 1

QUARTO_VAGO ! 0

Repita enquanto J ≤ 10 e QUARTO_VAGO=0

Se QUARTOS[J] = 0

Então QUARTO_VAGO ! J

J ! J + 1

Estrutura de repetição ou ciclos - "Repetir ... até"

Como a condição de controlo de repetição só é avaliada no final do ciclo, a

instrução ou instruções será(ão) executada(s) sempre pelo menos uma vez.



O ciclo será interrompido quando a condição de controlo for verdadeira.

Sintaxe em pseudocódigo: Repetir

<Instrução 1>

<Instrução 2>

...

<Instrução n>

até <Condição>

5 . S U B A L G O R I T M O S

A decomposição de um problema é um aspecto muito importante na resolução

de qualquer problema. Os subalgoritmos são uma ferramenta importante que

possibilitam a divisão de um complexo algoritmo num determinado número de

componentes, sendo cada componente implementado como um subalgoritmo.

Dois tipos de subalgoritmos vão ser analisados:

• Funções (Functions)

• Procedimentos (Procedures)

As funções definidas pelo programador têm uma estrutura semelhante à dos

procedimentos, apenas com a obrigação de devolver um determinado resultado.

Isto vai implicar que o modo como uma função é declarada e chamada num

algoritmo é ligeiramente diferente do que se passa num procedimento.

Os parâmetros nos procedimentos podem ser de input ou de output, mas não

são sempre de input ou output, exclusivamente. Muitas vezes servem para transferir

informação para o subalgoritmo, funcionando como parâmetro de input, mas

recebem um novo valor do subalgoritmo, que devolvem ao ponto de chamada,

servindo então como parâmetro de output. Tais parâmetros são chamados

parâmetros de input-output.

A diferença entre uma função e um procedimento reflecte-se também no modo

como cada um destes dois tipos de subalgoritmos é chamado, nomeadamente:

• quando se trata de um procedimento, apenas tem que se escrever o

respectivo identificador, com os eventuais argumentos que ele exija;



• quando se trata de uma função, torna-se necessário incluí-la numa instrução

de escrita ou de atribuição.

Uma vantagem importantíssima dos subalgoritmos é que eles podem ser

chamados quantas vezes quisermos dentro de um algoritmo. Podemos assim

efectuar a mesma operação ou conjunto de operações em diferentes pontos de um

algoritmo.

Mas, a vantagem dos subalgoritmos vai mais longe: podemos querer efectuar,

em diferentes pontos de um algoritmo, o mesmo tipo de operações (o mesmo

subalgoritmo) mas com dados diferentes. Aí, surgem-nos novos elementos que os

subalgoritmos podem utilizar - os parâmetros.

Os parâmetros são elementos semelhantes às variáveis, mas que são inseridos

nos cabeçalhos dos subalgoritmos (procedimentos e funções) e que, depois, são

usados nas chamadas a esses mesmos subalgoritmos. Os valores indicados no

lugar dos parâmetros, quando se faz uma chamada a um subalgoritmo, são

chamados argumentos (valor).

Uma subalgoritmo pode conter mais do que um parâmetro (inseridos dentro de

parêntesis). Na altura em que é feita a chamada ao subalgoritmo, é tida em

consideração a ordem dos argumentos, bem como o tipo de dados a que pertencem

e são necessários tantos argumentos quantos os parâmetros. Os argumentos

utilizados nas chamadas a subalgoritmos podem ser não apenas valores directos,

mas também variáveis e expressões, desde que os valores sejam compatíveis com

os correspondentes parâmetros.

Existem um conjunto de funções intrínsecas normalmente disponíveis na maior

parte das linguagens de programação, tais como:

• Função TRUNC(X) - retorna o valor inteiro do seu argumento. Nota: O

número A é múltiplo de B, se TRUNC(A/B) = A/B

• Função ABS(X) - retorna o valor absoluto do seu argumento

• Função SQRT(X) - retorna o quadrado do seu argumento



5.1. Exemplos

Função MÉDIA

Função MÉDIA(VALOR1, VALOR2, VALOR3)

Esta função calcula a média dos três valores fornecidos pelos três parâmetros de input.

MED é uma variável local. Todas as variáveis são reais.

1. [Calcula a média]

MED ! (VALOR1 + VALOR2 + VALOR3) / 3.0

2. [Devolve resultado e regressa ao ponto de chamada - Saída da função]

Regresso(MED)

Exemplo de utilização da função MÉDIA

Algoritmo TESTA_MÉDIA

Este algoritmo ilustra o uso da função MÉDIA com vários argumentos. Todas as

variáveis são reais.

1. [Inicializar valores de teste]

A ! 2.0

B ! 6.1

C ! 7.5

2. [Utiliza a função numa expressão]

D ! MÉDIA(A, B, C)

3. [Utiliza a função numa expressão mais complexa]

E ! D + MÉDIA(B, 3.2, A+7)

4. [Imprimir a média]

Escreva('A média dos três valores é: ',D)

5. [Terminar]

Saída



Procedimento DIVIDE

Procedimento DIVIDE(DIVIDENDO, DIVISOR, QUOC, RESTO)

Este procedimento divide o parâmetro de input, DIVIDENDO pelo parâmetro DIVISOR

dando os parâmetros de output QUOC e RESTO. Todos os números são inteiros.

1. [Testa divisão]

SE DIVISOR = 0

Então Escreva('Divisão por zero. Impossível!')

Regresso

2. [Executar divisão de inteiros]

QUOC ! DIVIDENDO / DIVISOR

3. [Determina Resto]

RESTO ! DIVIDENDO - (QUOC * DIVISOR)

4. [Regressa ao ponto de chamada - Saída do procedimento]

Regresso

Exemplo de utilização do procedimento DIVIDE

Algoritmo TESTA_DIVIDE

Este algoritmo ilustra o uso do procedimento DIVIDE. Todas as variáveis são inteiros.

1. [Inicializar valores de teste]

VAL1 ! 5

VAL2 ! 3

2. [Chama procedimento para divisão]

Chama DIVIDE(VAL1, VAL2, QUOC1, RESTO1)

3. [Imprimir resultado]

Escreva('Quociente: ',QUOC1, 'Resto: ',RESTO1)

4. [Chama novamente o procedimento para divisão]

Chama DIVIDE(VAL1 * VAL2, VAL2 + 1, QUOC2, RESTO2)

5. [Imprimir o resultado]

Escreva('Quociente: ',QUOC2, 'Resto: ',RESTO2)

6. [Terminar]

Saída

ESEV(Prof.Serv.) - Prof. José Alberto Pereira 16

II II

EE SS TT RR UU TT UU RR AA SS DD EE DD AA DD OO SS

1 . E S T R U T U R A D E D A D O S

Na programação de alto nível, sempre que se declaram variáveis, estas têm de

ser associadas a um determinado tipo de dados, para que o compilador saiba com

que tipo de valores vai operar e que espaço deve ser reservado em memória para

cada variável. Para além das estruturas de dados que mantenha em memória

primária, existem estruturas de dados que conserve em memória secundária, que é

o caso dos ficheiros.

Para além de uma categoria de dados a que podemos chamar de Simples,

temos ainda os dados que são estruturadas, isto é, que são compostos por outros

dados.

asEstruturadou Complexas

Simples Dados de Estrutura

2 . E S T R U T U R A D E D A D O S S I M P L E S

Ponteiros :Dinâmicas Caracteres de Cadeias e Caracteres :cosAlfanuméri

Reais Inteiros

Numéricas

Lógicos Valores

Simples Dado de Estrutura

Unidade II Estruturas de Dados


2.1. Valores lógicos

Os dados deste tipo, são dados que podem assumir apenas dois valores

possíveis: verdadeiro e falso. A sua utilidade reside, fundamentalmente, ao nível do

seu emprego em estruturas de controlo.

2.2. Inteiros

Este tipo de dados é, na verdade, um subconjunto dos inteiros, que constituem,

como se sabe, um conjunto infinito. Como os dados em computação ocupam espaço

não podemos trabalhar com conjuntos infinitos. Assim, os inteiros variam num

intervalo de acordo com o número de bits para a sua representação no sistema

informático na forma de dígitos binários.

• n bits " 2n valores diferentes

• Representação no sistema binário dos números não negativos: 0 ≤ x ≤ 2n-1

- Uma palavra de n bits permite representar todos os inteiros não negativos compreendidos

entre 0 e (2n-1). • Representação dos números negativos:

- Código de sinal e valor absoluto: -(2n-1-1) ≤ x ≤ (2n-1-1) Obtém-se o código de sinal e valor absoluto colocando à esquerda dos números binários

que pretendemos afectar de sinal um bit que terá o valor "0" se se pretender representa um

sinal positivo e terá o valor de "1" se se pretender representar o sinal negativo. O referido

bit é denominado o bit de sinal. Ao representar este tipo de representação num sistema

caracterizado por uma palavra de n bits reserva-se o bit mais à esquerda para exprimir o

sinal e utilizam-se os restantes (n-1) bits para representar o valor absoluto. Deste modo,

uma palavra de n bits permite representar todos os inteiros compreendidos entre -(2n-1-1) e

(2n-1-1), incluindo o zero que tem duas representações: uma para +0 e outra para -0. O total

de números distintos que se podem representar por este processo é de (2n-1), incluindo o

zero.

- Notação dos complementos de um: -(2n-1-1) ≤ x ≤ (2n-1-1)

- Complementos de dois: -(2n-1) ≤ x ≤ (2n-1-1) Tem representação única para o zero.

- Código Binário Deslocado: -(2n-1) ≤ x ≤ (2n-1-1)

- etc.



Ex.: Para se representar um inteiro padrão em Pascal utilizam-se dois bytes no

tipo Integer (16 bits). O tipo Integer em Pascal, representa os inteiros em

Complemento de dois. Assim, os inteiros do conjunto Integer variam no intervalo:

[-216-1, +216-1-1] = [-32768, +32767]. O tipo Longint representa o tipo de inteiros

maior, que utiliza 4 bytes, o que permite definir o intervalo [-2147483647,

+2147483647]. O tipo Word que comporta apenas os números não negativos,

definido por 2 bytes: [0, +65535]. O tipo Shortint, um tipo de inteiros menor, que

utiliza apenas 1 byte. O intervalo deste subtipo é: [-127, +128]. O tipo Byte, um outro

conjunto de inteiros definido também só por um byte, constituído só por positivos e

zero: [0, +255].

2.3. Reais

Os dados do tipo real representam aproximadamente os números reais, portanto,

números que podem ter partes decimais.

O esquema da representação interna dos reais, a nível da memória e do

processador, como se sabe, é feita em números binários. A conversão de números

decimais para binários, tratando-se de reais, implica uma certa complexidade, num

esquema a que se costuma chamar representação em Vírgula flutuante. Uma parte

do número é chamado mantissa ou fracção (conjunto dos dígitos significativos), e

uma outra é o expoente. Existe um outro formato designado por vírgula fixa, mas

levanta várias dificuldades ao programador.

Representação de números reais, em virgula flutuante:

Sinal Mantissa * Base expoente

Esta notação é, afinal, aquela a que estamos habituados em cálculo científico.

O expoente pode ser positivo ou negativo, conforme a grandeza do número a

representar.

Por exemplo, um número real pode surgir com este formato: 1.567893E3

(notação em linguagem Pascal). A primeira parte do número, até à letra E, é a

mantissa; o número depois da letra E representa o expoente de base 10 a que o

número é elevado; assim, o número apresentado acima é equivalente a: 23.6 x 107

(notação científica). Como é evidente, esta representação não é única. Podemos

escrever igualmente, por exemplo: 2360 x 105. Para evitar estas ambiguidades, os



formatos em virgula flutuante utilizam, de entre todas as representações possíveis,

aquela que contém mais algarismos significativos, denominada representação

normalizada. Para normalizar um número expresso pela sua mantissa e pelo seu

expoente, deslocam-se os dígitos da mantissa para a esquerda até que o primeiro

dígito seja significativo, e altera-se o valor do expoente de tantas unidades quantos

os deslocamentos realizados. Exemplo de operação de normalização: 000236 x 1006

passaria a ser 236000 x 1003.

Como resultado da normalização, a mantissa é sempre enquadrada de tal forma

que as ultrapassagens de capacidade apenas se verificam no expoente.

É fácil de verificar que o número de dígitos da mantissa está directamente ligado

à precisão dos cálculos, enquanto que o números de dígitos do expoente determina

os números extremos que a máquina pode representar.

Existem várias convenções para representar os números flutuantes à custa de

uma palavra binária. A convenção mais corrente coloca as informações mais

significativas nas posições mais significativas: primeiro o sinal, depois o expoente, e

finalmente a mantissa:

O sinal + é representado por zero, e o sinal - por um 1. O expoente exprime

geralmente uma potência de 16. A mantissa pode ser considerada como inteira

supondo-se que a vírgula se encontra imediatamente à direita, ou como fraccionária,

supondo-se então que a vírgula se encontra imediatamente à esquerda.

Os formatos de vírgula flutuante implementados pela INTEL no seu processador

aritmético 80387 e no microprocessador 80486, seguem a norma de virgula flutuante

IEEE 754-195, publicada em 1985. São ao todo três formatos: de precisão simples,

de precisão dupla e de precisão expandida, que ocupam, respectivamente, 4, 8 e 10

bytes.

Sinal Expoente Mantissa

Sinal Expoente Mantissa Precisão simples 32 bits = 4 bytes

1 8 23



2.4. Alfanuméricos

Existem actualmente vários códigos susceptíveis de ser utilizados pelos

computadores digitais. Alguns desses códigos permitem representar, não apenas

grandezas numéricas, mas também caracteres literais e sinais de pontuação. É

exemplo o código ASCII ("American Standard Code for Information Interchange" -

leia-se "ásqui"), usado na transferência de informação entre um computador e os

seus dispositivos periféricos. Trata-se de um código que utiliza combinações de oito

bits (28 = 256) para representar os dez algarismos decimais (0, 1, 2, ..., 9), os

caracteres do alfabeto, sinais de pontuação, parêntesis, sinais das operações

aritméticas e de igualdade, e mais uma série de caracteres de controlo, entre outros

símbolos, num total de 256 símbolos.

Os códigos que se destinam a traduzir, não só informação numérica, mas

também caracteres do alfabeto e sinais convencionais são denominados códigos

alfanuméricos. O código ASCII, referido acima, representa o código alfanumérico

universalmente aceite.

Os dados do tipo carácter (Char em Pascal) correspondem a caracteres

individuais. Os caracteres disponíveis são geralmente os caracteres da Tabela

ASCII. Este tipo de dado pode assumir qualquer carácter da referida Tabela ASCII,

mas apenas um de cada vez. Por curiosidade, existe rotinas para converter um dado

número inteiro para o correspondente carácter na Tabela ASCII. Por exemplo, a

função CHR, em Pascal. Por sua vez, existe rotinas que dá o ordinal de um dado

carácter, por exemplo a função ORD em Pascal.

Sinal Expoente Mantissa Precisão dupla 64 bits = 8 bytes

1 11 52

Sinal Expoente Mantissa Precisão expandida 80 bits = 10 bytes

1 15 64



Para facilitar a manipulação de palavras ou mensagens, dentro de um programa,

existe outro tipo de dados: Cadeia de caracteres (Cadeia Alfanumérica). Estes tipos

de dados são mais adequados ao manuseamento de texto, nas instruções de leitura,

escrita e atribuição. Em Pascal este tipo de dados é representado pelo tipo de

variável: String.

Um dado do tipo String que tenha um número determinado de caracteres, pode

ser tratado como um vector do tipo Carácter (Char). Saber que podemos trabalhar

com Strings como vectores de caracteres, é útil, porque, por exemplo podemos

manipular as cadeias de caracteres com outros recursos de programação. Por

exemplo, podemos pretender um algoritmo que, dada uma determinada palavra,

introduzida pelo utilizador, seja capaz de contar quantas vogais existem nessa

palavra.

2.5. Ponteiros

O tipo de dados Ponteiro ou Apontador entra já num conceito diferente. Nas

variáveis deste tipo, não figuram valores directos, mas números que apontam para

endereços da memória.

3 . E S T R U T U R A D E D A D O S C O M P L E X A S

Árvores :Lineares Não

FicheirosFilasPilhas

Lineares Listas :variável oCompriment

Registos

MatrizesVectores

fixo oCompriment

Complexas Dados de Estruturas

3.1. Vectores

Um vector (Array unidimensional) é um tipo estruturado que pode agrupar

numa mesma variável um conjunto finito de valores todos do mesmo tipo. Um vector



é um conjunto de elementos representados por um identificador e um único índice.

Cada elemento tem uma única dimensão. O índice varia entre um limite inferior e um

limite superior, em correspondência com o número de elementos do conjunto. Os

vectores são colocados na memória em posições ordenadas e adjacentes.

Suponhamos que pretendemos representar, num programa, os gastos de um

determinado departamento em cada um dos 12 meses do ano. Evidentemente,

poderíamos definir 12 variáveis, designadas por 12 identificadores diferentes; por

exemplo: JAN; FEV; MAR; etc. Todavia, o uso de uma variável estruturada, neste

caso, um vector, com um único identificador agrupando os 12 elementos em causa,

revela-se uma técnica muito mais económica em termos de escrita, mas, sobretudo,

encerra muito mais potencialidades de manipulação em termos de programação.

Neste caso, poderíamos definir um vector mediante um único identificador, por

exemplo: GASTOS_MES

Mas, para que esse identificador possa representar os 12 elementos

correspondentes aos 12 meses do ano, temos de utilizar índices.

Em Pseudocódigo, poderíamos escrever assim:

GASTOS_MES: Vector[1,...,12] de Real

Em que:

• GASTOS_MES - é o identificador ou nome atribuído à variável;

• Vector - indica que a variável é do tipo Vector;

• [1,...,12] - define o número de elementos da variável e ao mesmo tempo o

intervalo dos seus índices, neste caso entre 1 e 12;

• de Real - indica qual o tipo de dados dos elementos do vector.

ou ainda GASTOS_MES[12]

De um modo geral, cada elemento desta variável de tipo Vector designa-se por:

GASTOS_MES[K]



Em que [K] representa a posição do elemento no conjunto que compõem o

vector, ou seja, neste caso, o número do mês que se pretende designar. Por exemplo o gasto do mês de Fevereiro seria designados por: GASTOS_MES[2]

Segue-se alguns exemplos de operações com vectores: [Definir um vector A de 40 elementos do tipo inteiro]

A: Vector[1, ..., 40] de Inteiro

[Instrução de leitura com acesso sequencial]


Leia(A[K])

[Instrução de atribuição: armazenar na 4ª posição do vector A o valor 13]

A[4] ! 13

[Instrução de escrita do 4ª elemento do vector A]

Escreva(A[4])

3.2. Matrizes

Uma matriz (Array multidimensional) é um tipo estruturado que pode agrupar

numa mesma variável um conjunto finito de valores todos do mesmo tipo.

No caso dos vectores, temos apenas um agrupamento de elementos, cujos

índices estão compreendidos entre dois limites; nas matrizes temos dois (ou mais)

elementos, cada qual com o seu par de limites próprio.

Uma matriz é um conjunto de elementos representados por um identificador e

dois índices. Da mesma forma do que os vectores, os dois índices varia entre um

limite inferior e um limite superior, em correspondência com o número de elementos

do conjunto.

Segue-se alguns exemplos de operações com matrizes:

[Definir uma matriz M com elementos do tipo inteiro]

M: Matriz[1, ..., 10; 1, ..., 5] de Inteiro



[Instrução de leitura com acesso sequencial]


Repita para L=1,2,...,5

Leia(M[K, L])

[Instrução de atribuição]

M[4, 3] ! 20

3.3. Registos

Os registos (Records) são um outro tipo de dados estruturados que permitem

agrupar elementos de vários tipos diferentes, sob a forma de campos.

A principal diferença que costuma apontar-se entre um vector/matriz é que,

quando um vector/matriz agrupa um conjunto de dados do mesmo tipo, um registo

pode conjugar diferentes tipos de dados na mesma estrutura. Todavia, existem

outras diferenças importantes, sobretudo no modo de acesso aos elementos de um

e de outro tipo de estrutura.

De facto, o que interessa sobretudo é a maneira como se vai aceder a essa

informação estruturada. Se o problema exige que o acesso seja por "indexação", isto

é, do género, "toma lá um índice, dá cá um valor", então o que faz falta é um

vector/matriz; se, por qualquer motivo, o que queremos é um acesso por

"nomeação" - "passa para cá a informação com este nome" - então o melhor é ir

pelos registos.

Um exemplo típico de dados organizáveis sob a forma de registos é o que se

relaciona com informação sobre pessoas. Os seguintes dados poderiam ser os

campos de um registo: nome; morada; idade; telefone; etc.

Em pseudocódigo seria:

[Registo que inclui os campos: Nome, Morada, Idade e Telefone]

DADOS_PESSOA de Registo

NOME

MORADA

IDADE

TELEFONE

Fim



3.4. Listas

Um Lista é um conjunto ordenado consistindo num número variável de

elementos aos quais se podem fazer inserções e eliminações.

lineares não lineares

Listas

Uma lista linear é uma Lista que apresenta a propriedade de adjacência entre os

seus elementos.

Algumas operações a realizar com Listas:

• Inserir um elemento na lista

• Eliminar um elemento na lista

• Remover um elemento na lista

• Fundir duas ou mais listas numa só

• Formar várias listas a partir de uma só

• Copiar uma lista

• Determinar o comprimento de uma lista, ou seja, o número de elementos de

uma lista

• Ordenar os elementos de uma lista

• Pesquisar um elemento na lista, que contenha um campo com um certo valor

• etc.

3.5. Pilhas

Uma pilha é uma lista linear na qual todas as eliminações e inserções, e

normalmente todos os acessos, são feitos num extremo da lista. Uma pilha (Stack) é

uma colecção ordenada de elementos sendo os novos elementos adicionados ou

elementos retirados a partir de uma das suas extremidades, designada por "Topo"

da pilha. Uma pilha é uma lista linear na qual todas as eliminações e inserções, e

normalmente todos os seus acessos, são feitos num extremo da lista.



A pilha é uma estrutura dinâmica, ou seja, de comprimento variável. A pilha é

também designada por uma estrutura LIFO ("Last-In", "First-Out"), o último e chegar

é o primeiro a sair. Na verdade a informação que se tem de uma pilha é o elemento

que está no topo.

Representação de pilhas em pascal

Há várias formas de representar uma pilha em pascal. Uma forma simples de

representar uma pilha é usar um vector. Nota-se contudo que um vector e uma pilha

são duas entidades extremamente diferentes, pois o número de elementos (máximo)

é fixo, enquanto que numa pilha esse número não existe. Uma pilha é uma entidade

dinâmica cuja dimensão varia constantemente. Temos então que declarar um vector

com uma dimensão suficientemente grande. Uma das "extremidades" do vector

corresponderá à "extremidade" da pilha que nunca varia.

É ainda necessário definir um outro campo que indicará qual a posição corrente

do topo da pilha.

Pode-se então declarar-se uma pilha usando um registo (record) contendo dois

campos: um vector (array) contendo os elementos da pilha; um inteiro para indicar a

posição do topo da pilha actual.

Algumas operações sobre Pilhas:

• Procedure PUSH(S, TOP, X) - adiciona (ou empilha) um novo elemento á

pilha, dado um elemento "X" e uma pilha "S". PUSH adiciona "X" ao topo da

pilha "S".

• Function POP(S, TOP) - Remove o elemento que está correctamente no topo

da pilha: X ! POP(S, TOP).

Quando se retira o último elemento de uma pilha, a pilha diz-se vazia. Não se

pode, portanto, aplicar-se sempre a operação POP a uma pilha, ao contrário do que

A

E

C Topo da pilha

1º elemento da pilha



acontece com a operação PUSH. É necessário saber se uma pilha ainda tem

elementos para retirar ou não. É necessário definir uma função EMPTY.

• Function EMPTY(S) - Determina se uma pilha está ou não vazia. Se vazia

EMPTY devolve o valor verdadeiro.

É ainda útil definir uma outra função STACK_TOP(S) que permite determinar

qual é o elemento que está no topo da pilha sem contudo o remover da pilha.

• Function STACK_TOP(S)

Esta função é equivalente a: X ! POP (S, TOP)

PUSH (S, TOP, X)

Tal como POP, STACK_TOP não é definida para uma pilha vazia.

TOP representa o elemento localizado no topo da pilha. Inicialmente quando a

pilha está vazia o valor de TOP é zero. De cada vez que se insere um elemento na

pilha, POP é incrementado de uma unidade, antes do elemento ser colocado na

pilha. POP é decrementado de uma unidade sempre que se elimina um elemento da

pilha.

Pseudocódigo de algumas operações sobre Pilhas:

Procedure PUSH(S, TOP, X)

Este procedimento empilha um elemento X no topo duma pilha que é representada por

um vector S com N elementos. O elemento no topo da pilha é indicado por um ponteiro TOP.

1. [Verificar se falta capacidade da pilha]

Se TOP ≥ N

Então Escreva('A pilha não suporta mais elementos - Overflow')

Regresso

2. [Incrementar o ponteiro do topo da pilha]

TOP ! TOP + 1

3. [Inserção do elemento na pilha]

S[TOP] ! X

4. [Terminar]

Regresso



Function POP(S, TOP)

Esta função retira o elemento do topo da pilha que é representada por um vector S e

devolve esse elemento. TOP é um ponteiro para o elemento no topo da pilha.

1. [Verificar se a pilha está vazia]

Se TOP = 0

Então Escreva('A pilha está vazia - Underflow')

Regresso

2. [Guarda o valor do elemento a eliminar]

Y ! S[TOP]

3. [Decrementar o ponteiro do topo da pilha]

TOP ! TOP - 1

4. [Devolve o valor do elemento que estava no topo da pilha e termina]

Regresso(Y)

Function STACK_TOP(S)

Dados um vector S, com N elementos e cujo elemento do topo é indicado por TOP, essa

função devolve o elemento do topo da pilha.

1. [Verificar se a pilha está vazia]

Se TOP = 0

Então Escreva('A pilha está vazia')

Regresso

2. [Devolve o elemento que está no topo da pilha e termina]

Regresso(S[TOP])

3.6. Filas

Uma fila (queue) é uma lista linear na qual todas as inserções são feitas num

extremo da lista (a parte de trás) e todas as eliminações, e normalmente todos os

acessos, são feitos no outro extremo da lista (parte da frente).



A fila é uma estrutura dinâmica, ou seja, de comprimento variável. A fila é

também designada por uma estrutura FIFO ("First-In", "First-Out"), o primeiro a

chegar é o primeiro a sair. Só os elementos que estão á frente podem ser apagados

e só se podem adicionar elementos na parte de trás.

Um exemplo familiar de uma fila é a fila de clientes de um supermercado junto às

caixas registadoras. A primeira pessoa na fila é a primeira a ser atendida.

Representação de filas em pascal

Apesar de uma fila ser uma entidade dinâmica, as suas operações podem ser

simuladas utilizando um vector com um número suficientemente grande de

elementos que nos permita manter a propriedade de comprimento variável. A

representação vectorial Q[1, ..., N] (vector de N elementos) de uma fila requer o uso

de dois ponteiros F e R, que representam a posição do elemento da Frente (primeiro

elemento da fila) e da Retaguarda (último elemento da fila), respectivamente.

Pode-se então declarar-se uma fila usando um registo (record) contendo três

campos: um vector contendo os elementos da lista; um inteiro para indicar a posição

do elemento da frente e outro para indicar o elemento da retaguarda.

Ignorando, para já, a possibilidade de ocorrência de overflow e underflow, as

operações de inserção e remoção poderiam ser implementadas do seguinte modo: [Inserção de um elemento Y: Incrementa primeiro R e depois insere o elemento]

R ! R + 1

Q[R] ! Y

[Remoção de um elemento Y: Primeiro remove o elemento e depois incrementa F]

Y ! Q[F]

F ! F + 1

1 2 3 4 5 6

A B C D E F

Frente Eliminar

Retaguarda Inserir



Operações primitivas sobre Filas:

• Procedure QINSERT(Q, F, R, N, Y) - Insere um novo elemento Y á fila na

parte de trás da fila Q de N elementos.

• Function QDELETE(Q, F, R, N) - Elimina o elemento da frente da fila Q de N

elementos.

• Function EMPTY(Q) - Determina se a fila contém ou não elementos. Se vazia

EMPTY devolve o valor verdadeiro.

Quando se retira o último elemento de uma fila, a fila diz-se vazia. Não se pode,

portanto, aplicar-se sempre a operação QDELETE a uma fila, ao contrário do que

acontece com a operação QINSERT.

Inicialmente R é 0 e F é 1. A fila está vazia enquanto R < F. O número de

elementos da fila será R-F+1. Se R = F só temos um elemento na fila.

Consideramos uma fila com máximo de 5 elementos (vector de comprimento 5):

Pseudocódigo com este tipo de implementação:

1 2 3 4 5

1ª Situação F=1 e R=0

Fila Vazia: R<F

1 2 3 4 5

A B C


Inserir 3 elementos

1 2 3 4 5

C

3ª Situação F=R=3

Remover 2 elementos

1 2 3 4 5

C D E


Inserir 2 elementos



Procedure QINSERT(Q, F, R, N, Y)

Dados F e R, ponteiros para os elementos da frente e retaguarda da fila, uma fila

vectorial Q com N elementos e um elemento Y, este procedimento insere Y na parte de trás da

fila. Antes do 1º uso do procedimento, F e R são inicializados a 0 e 1 respectivamente (F ! 1,

R ! 0).

1. [Verificar se excedeu a capacidade da fila]

Se R ≥ N

Então Escreva('A fila não suporta mais elementos - Overflow')

Regresso

2. [Incrementar o ponteiro de trás]

R ! R + 1

3. [Inserção do elemento na fila]

Q[R] ! Y

4. [Terminar]

Regresso

Function QDELETE(Q, F, R, N)

Dados F e R, ponteiros para os elementos da frente e retaguarda da fila, uma fila

vectorial Q com N elementos, esta função elimina e devolve o último elemento da fila (na

parte da frente da fila). Y é uma variável temporária.

1. [Verificar se a fila está vazia]

Se R < F

Então Escreva('A fila não tem elementos - Underflow')

Regresso

2. [Eliminar o elemento na fila]

Y ! Q[F]

3. [Incrementar o ponteiro da frente]

F ! F + 1

4. [Devolve o elemento e terminar]

Regresso(Y)



Se a fila exceder a sua capacidade e posteriormente efectuarmos sucessivas

operações até remover todos os seus elementos, esta implementação não permite

operações de inserção, apesar de a fila estar vazia. O problema desta

implementação é que não permite reutilizar a fila quando ela ficar vazia depois de ter

atingido a sua capacidade máxima.

O problema pode ser resolvido inicializando os apontadores R e F a zero e na

operação remoção, cada vez que a fila ficar vazia, reinicializar a zero os respectivos

apontadores. A fila estaria vazia para F=0 e o pseudocódigo passaria a ser o

seguinte:

Procedure QINSERT(Q, F, R, N, Y)

Dados os ponteiros F e R para a frente e retaguarda duma fila Q com N elementos e um

elemento Y, este procedimento insere Y na retaguarda da fila. Antes do 1º uso do

procedimento, F e R são limpos (F ! 0, R ! 0).


Se R ≥ N


Regresso

2. [Incrementar o ponteiro de trás]

R ! R + 1


Q[R] ! Y

4. [O ponteiro da frente tem o valor correcto? Necessário na inserção do 1º elemento da

fila]

Se F = 0

Então F ! 1

5. [Terminar]

Regresso




Dados os ponteiros F e R para a frente e retaguarda duma fila Q com N elementos, esta

função elimina e devolve o último elemento da fila (na parte da frente da fila). Y é uma

variável temporária.


Se F = 0


Regresso


Y ! Q[F]

3. [Fila Vazia? Senão Incrementa o ponteiro da frente]

Se F = R

Então F ! 0

R ! 0

Senão F ! F + 1


Regresso(Y)

O problema com estas duas possíveis implementações é que o vector pode ter

até 5 elementos e no entanto a fila não pode crescer mais, pois R teria que assumir

o valor 6, que corresponde ao índice do vector. Ou seja, a fila pode não crescer mais

(overflow) ao tentarmos inserir um elemento apesar de algumas das primeiras

localizações não estarem a ser usadas.

Uma solução possível, seria alterar a operação de remoção de um elemento, de

modo a que sempre que um elemento seja apagado, toda a fila seja deslocada para

o início do vector. Deixaria de ser necessário especificar o campo F, pois, a frente da

fila passaria a ser sempre o primeiro elemento do vector. Mas este método é

ineficiente, pois , cada vez que um elemento é removido, todos os outros têm que

ser deslocados.

A solução mais eficiente de todos estes problemas é tratar o vector que contem

os elementos da fila como sendo circular e não um segmento de recta, ou seja, o

primeiro elemento do vector segue-se ao seu ultimo elemento.



Com este tipo de implementação a condição R < F não serve para determinar se

a fila está vazia. Uma possível solução é convencionar que F é o índice do elemento

do vector que precede o 1º elemento da fila e R é o índice do elemento da

retaguarda do vector. Assim o teste de fila vazia seria: F=R. Os ponteiros F e R são

inicializados no último índice do vector, pois F precede o primeiro nesta

representação.

Antes da inserção de um elemento na fila, quando o vector está totalmente

preenchido, verifica-se a condição F = R que é utilizada para verificar a ocorrência

de underflow (fila vazia). O problema é que deste modo não há possibilidade de

distinguir a situação de underflow da situação de overflow. A solução deste

problema, é permitir que a fila cresça apenas até um número de elementos igual ao

total do vector menos um. Para isso na implementação da inserção implementa-se o

ponteiro R antes de efectuar o teste F=R.

Ignorando, para já, a possibilidade de ocorrência de overflow e underflow, as

operações de inserção e remoção para uma fila circular poderiam ser

implementadas do seguinte modo:

[Inserção de um elemento Y]

R ! R + 1

Q[R] ! Y

[Remoção de um elemento Y]

F ! F + 1

Y ! Q[F]

Antes de um dado elemento ser introduzido na fila é necessário utilizar o teste de

fila cheia. Antes de um elemento ser retirado da fila é necessário verificar se esta é

possível, recorrendo ao teste de fila vazia.

Consideramos como exemplo, uma fila circular com o máximo de 5 elementos

(vector de comprimento 5):




Inserir 3 elementos

2

3 4

1

5 A

B

C D


Remover 2 elementos

2

3 4

1

5

C D

1


Inserir 2 elementos

Fila cheia - Overflow

2

3 4

1

5 F

C D

E


Remover 2 elementos

2

3 4

1

5 F

E

1ª Situação F=R=5

Fila Vazia - Underflow

2

3 4

1

5


Inserir 1 elemento

F precede o 1º elemento

2

3 4

1

5 A



Pseudocódigo da implementação da fila com um vector circular:

Procedure QINSERT(Q, N, F, R, Y)

Dado o ponteiro F que precede o 1º elemento da fila (da frente) e o ponteiro R da

retaguarda duma fila circular Q de N elementos, e um elemento Y, este procedimento insere Y

na retaguarda da fila. Os ponteiros F e R são inicializados no último índice do vector:

(F ! N, R ! N).

1. [Guardar o ponteiro de trás, caso se exceda a capacidade]

TEMP ! R

2. [Reposiciona o ponteiro de trás]

Se R=N

Então R ! 1

Senão R ! R + 1


Se R = F


R ! TEMP

Regresso


Q[R] ! Y

5. [Terminar]

Regresso

Function QDELETE(Q,, F, R, N)

Dado o ponteiro F que precede o 1º elemento da fila (da frente) e o ponteiro R da

retaguarda duma fila circular Q de N elementos, esta função elimina e devolve o último

elemento da fila (na parte da frente da fila). Y é uma variável temporária.


Se R = F


Regresso



2. [Reposiciona o ponteiro da frente]

Se F=N

Então F ! 1

Senão F ! F + 1


Y ! Q[F]


Regresso(Y)

Esta implementação tem a pequena desvantagem de a fila crescer apenas até

um número de elementos igual ao total do vector menos um. A solução para este

pequeno problema é resolvido pelo pseudocódigo seguinte:

Procedure QINSERT(Q, N, F, R, Y)

Dado os ponteiros F e R da frente e da retaguarda duma fila circular Q de N elementos, e

um elemento Y, este procedimento insere Y na retaguarda da fila. Inicialmente F e R são

limpos: (F ! 0, R ! 0).

1. [Guardar o ponteiro de trás, caso se exceda a capacidade]

TEMP ! R

2. [Reposiciona o ponteiro de trás]

Se R=N

Então R ! 1

Senão R ! R + 1


Se R = F


R ! TEMP

Regresso


Q[R] ! Y



5. [O ponteiro da frente está colocado correctamente? (necessário na inserção do 1º

elemento da fila]

Se F = 0

Então F ! 1

6. [Terminar]

Regresso


Dado os ponteiros F e R da frente e da retaguarda duma fila circular Q de N elementos,

esta função elimina e devolve o último elemento da fila (na parte da frente da fila). Y é uma

variável temporária.


Se F = 0


Regresso


Y ! Q[F]

3. [Fila Vazia? Se sim devolve o elemento e termina. (a fila tinha um só elemento)]

Se F=R

Então F ! 0

R ! 0

Regresso(Y)

4. [Reposiciona o ponteiro da frente]

Se F=N

Então F ! 1

Senão F ! F + 1


Regresso(Y)

3.7. Listas Ligadas

Atendendo à definição de lista ligada (linked list), muitos autores chamam à lista

ligada, lista simplesmente ligada, ou ainda, lista ligada encadeada.



A utilização de armazenamento sequencial, por meio de um vector, para

representar pilhas e filas tem desvantagens:

• uma quantidade fixa de espaço de memória está reservada para a pilha ou fila

mesmo se estas estão praticamente vazias;

• tamanho máximo dos vectores introduz a possibilidade de overflow.

Numa representação sequencial o ordenamento dos elementos de uma pilha ou

fila é implícito e determinado pelo índice do vector. A solução para estes problemas,

é uma ordenação explícita dos elementos, fazendo com que cada elemento

contenha o endereço do seguinte. Estamos perante uma lista simplesmente ligada.

Numa lista simplesmente ligada os seus componentes estão ligados entre si por

meios de ponteiros ou apontadores (pointers). A ideia básica de uma lista ligada é

de que cada componente individual da lista contenha um apontador que indique

onde o próximo componente pode ser encontrado. Portanto, a ordem relativa dos

componentes pode ser facilmente mudada, alterando simplesmente os apontadores.

Assim, uma lista ligada não está limitada a um número máximo de componentes. Na

verdade o número total de elementos disponíveis em cada instante é finito devido ás

limitações de capacidade de memória primária dos computadores.

Tem-se assim a estrutura de uma lista ligada, em que cada "caixa" representada

na figura dá-se o nome de nodo ou nó (node).

Cada elemento de uma lista ligada é um nó com dois campos: o da informação e

o campo do endereço do elemento seguinte. Este endereço é designado por

ponteiro. O último nodo da lista não tem sucessor, e consequentemente, não tem

nenhum endereço no campo do ponteiro. O ponteiro nil é utilizado para indicar o fim

da lista. Uma lista sem elementos é uma lista vazia. A lista é acedida por meio de

um ponteiro externo, que aponta para o primeiro nó.

Primeiro elemento

Último elemento

Informação Ponteiro do endereço seguinte

A B C D NIL

Ponteiro de

Início



A estrutura de dados de um nó poderia ser a seguinte: Ponteiro = Nome_Registo

Nome_Registo = Registo

Info: Tipo

Próximo: Ponteiro

Fim Registo

Desde que não seja dito nada ao contrário, o nó é composto por dois campos: o

campo da informação e o campo do ponteiro para o próximo nó.

A lista é uma estrutura dinâmica que pode crescer ou diminuir, não tendo um

número predeterminado de elementos.

Inserção de nós numa lista ligada

Suponhamos que se tem uma lista com 3 elementos com informação do tipo

inteiro:

Suponhamos que queremos juntar o inteiro 6 ao topo da lista. Para isso é

necessário obter um nó vazio para armazenar o inteiro 6.

Suponhamos que existe uma função que fornece nós vazios: P ! CriarNodo

P é o endereço para o nó vazio.

5 3 8 NIL

List

5 3 8 NIL

List

p



É em seguida necessário inserir o inteiro 6 na parte Info do novo nó.

Convencionemos que a função seguinte o faz: Info(p) ! 6

É necessário agora armazenar no outro campo o endereço ao índice da lista:

Próximo(p) ! List

Resultando:

É necessário mudar o valor de List para que este ponteiro passe o apontador

para o novo primeiro elemento da lista. List ! p

O conjunto de operações foi a seguinte: P ! CriarNodo

Info(p) ! 6

Próximo(p) ! List

List ! p

Remoção de nós numa lista ligada

Para remover o primeiro nó de uma lista não vazia é armazenado o valor do seu

campo Info numa variável temporária x.

5 3 8 NIL

List

6

p

6 5 8 NIL

List

3



Suponhamos novamente, que se tem uma lista com 3 elementos com

informação do tipo inteiro e queremos remover o elemento com a informação 5:

P ! List

List ! Próximo(p)

x ! Info(p)

O nó para o qual p aponta é agora completamente inútil. Seria interessante

torná-la livre para outra utilização, assim como ao ponteiro p. Para isso usa-se a

seguinte função para libertar nó: LibertarNodo(p)

5 3 8 NIL

List

5 3 8 NIL

List

p

5 3 8 NIL

p

List

3 8 NIL

List



Inserção de um elemento depois de um determinado nó

A inserção de um novo elemento numa lista, depois de determinado nó, envolve:

a atribuição de um nó, a inserção da informação e o ajuste de dois ponteiros. Se se

designar esta operação por InserirDepois(List, P, X) a inserção do elemento X, depois

do nó apontado por P, numa lista List, a sua implementação pode ser a seguinte:

q ! CriarNodo

Info(q) ! X

Próximo(q) ! Próximo(p)

Próximo(p) ! q

Um elemento só pode ser inserido depois de um determinado nó, e não antes do

nó. Isso porque numa lista não há forma de a partir de um nó, aceder ao nó

precedente.

Do mesmo modo para se apagar o nó de uma lista é insuficiente a informação do

ponteiro para esse nó. Para se apagar determinado nó é necessário mudar o campo Próximo do nó que o precede de modo que ele fique a apontar para o nó seguinte.

3 5 8 NIL

List

X

5 3 8 NIL

List

P



Implementação de uma pilha por meio de uma lista

Uma pilha só pode ser acedida pelo seu elemento de topo, assim como, a lista. Seja uma pilha S, implementada por meio de uma lista:

A sua estrutura de dados em pascal, poderia ser a seguinte:

Type Pilha = ^NodoPilha;

NodoPilha = Record

Info: TipoDados;

Próximo: Pilha;

End;

Var S: Pilha;

Remover o primeiro elemento da lista é idêntico á execução da operação pop.

Uma implementação possível da operação Push(S, X), supondo que temos memória

suficiente no sistema, seria: P ! CriarNodo

Info(p) ! X

Próximo(P) ! S

S ! P

em que, S é o ponteiro de início da pilha e X o elemento a inserir.

A operação x ! Pop(S), pode ser implementada do seguinte modo:

Se PilhaVazia(S)

Então Escreva(‘Pilha vazia’)

Senão P ! S

S ! próximo(P)

X ! Info(P)

LibertarNodo(P)

3 2 1 NIL

S



em que, S é o ponteiro de início da pilha e PilhaVazia(S) é apenas um teste ao

ponteiro S (se é igual a nil).

Implementação de uma fila por meio de uma lista

O ponteiro da lista, que aponta para o primeiro elemento, representa a frente da

fila (ponteiro F). Outro ponteiro para o último elemento da lista representa a parte da

retaguarda da fila (ponteiro R).

Seja a fila Q, implementada por meio de uma lista:

A sua estrutura de dados em pascal, poderia ser a seguinte:

Type Ponteiro = ^NodoFila;

NodoFila = Record

Info: TipoDados;

Próximo: Ponteiro;

End;

Fila = Record

F: Ponteiro;

R: Ponteiro;

End;

Var Q: Fila;

Seja Q o ponteiro de início da fila e Frente(Q) uma função que acede à frente da

fila Q, e a função Retaguarda(Q) que acede à sua retaguarda. Uma implementação

da operação X ! QDelete(Q) de uma fila Q, que remove e devolve um elemento X da

fila Q (tira um nodo na frente da fila), poderia ser:

1 2 3 NIL

F R

Q



Se FilaVazia(Q)

Então Escreva(‘Fila Vazia’)

Senão P ! Frente(Q)

X ! Info(P)

Frente(Q) ! Próximo(P)

Se Frente(Q) = Nil

Então Retaguarda(Q) ! Nil

LibertaNodo(P)

A fila Q está vazia, quando ambos os ponteiros R e F estão nulos (Nil). A

operação QInserir(Q,, X), que insere um elemento X na fila Q (põe um nodo na

retaguarda da fila), pode ser implementada do seguinte modo:

P ! CriarNodo

Info(P) ! X

Próximo(P) ! Nil

Se Retaguarda(Q) = Nil

Então Frente(Q) ! P

Senão Próximo(Retaguarda(Q)) ! P

Retaguarda(Q) ! P

Quando a fila só tem um elemento, então os ponteiros R e F são iguais.

3.8. Ficheiros

Os ficheiros têm como função, armazenar a informação em suportes de memória

secundária ou externas (discos ou disquetes, etc.), onde essa informação possa ser

guardada para além do tempo em que o programa está a correr no computador, e,

eventualmente, reutilizada, nesse ou em outro programa.

As restantes estruturas de dados, são dados voláteis, porque são armazenados

apenas temporariamente na RAM (memória primária) do computador, quando estes

estão a funcionar com o programa. Quando se sai do programa em que os dados

foram introduzidos ou obtidos, toda a informação desaparece.



Assim, a unidade básica de armazenamento de informação em sistemas

informáticos é o ficheiro (file).Um ficheiro é uma unidade de informação, armazenada

fisicamente num suporte de memória secundária.

r)programado pelo (definidos binário tipo do ficheiros texto tipo do ficheiros

ficheiro de Tipo

Ficheiros do tipo texto

Os ficheiros do tipo texto, são ficheiros em que a informação é totalmente

armazenada em formato de caracteres (ASCII), podendo ser criados ou modificados

por um editor de texto, fora do programa que os utiliza.

O acesso aos dados neste tipo de ficheiros é do tipo sequencial, querendo isto

dizer, que a leitura dos dados tem de partir sempre do início e percorrer todos os

elementos até ao ponto pretendido.

Ficheiros do tipo binário ou definidos pelo programador

Os ficheiros definidos pelo programador são ficheiros que agrupam dados

simples (como por exemplo, um inteiro) ou estruturados (como por exemplo, um

registo), em formato binário, assumindo formas muito variáveis. Podemos, por

exemplo, ter ficheiros de números inteiros ou reais, de vectores ou de registos, etc. -

o que permite uma grande flexibilidade de trabalho com sequências de dados

armazenadas em suportes de memória secundária.

Em particular, os ficheiros de registos permitem manipular dados num formato

bem estruturado para trabalho com informação externa (em disco ou disquete). Com

este tipo de ficheiros (ficheiros de registos) pode trabalhar-se com informação um

pouco à maneira de bases de dados.

O acesso aos dados destes ficheiros pode ser feito de forma aleatória, ou seja,

por escolha da posição pretendida, e não forçosamente de forma sequencial, como

nos ficheiros de texto.

Em qualquer dos casos, um ficheiro de dados (Ficheiro de texto ou binário), para

além de permitir o armazenamento da informação num suporte de armazenamento

externo à memória primária, também permite reunir uma colecção de dados sem

tamanho fixo à partida. Qualquer um dos outros tipos de dados estruturados



(vectores, matrizes ou registos) tem um tamanho - em termos de número de

elementos - que é determinado à partida, na respectiva declaração do tipo ou da

variável. Em princípio, um ficheiro não tem essa limitação, pois pode conter um

número maior ou menor de dados, sem que esse número tenha que ser determinado

à partida. Um ficheiro pode ser acrescentado com mais dados, desde que estes

sejam compatíveis com o tipo-base dos dados que o constituem, ou pode ser

totalmente reescrito com um número completamente diferente de elementos.

Operações com ficheiros

Os ficheiros são estruturas de dados que implicam a sua manipulação a dois

níveis:

1) ao nível interno do programa, com variáveis que identificam os ficheiros e os

dados a ler ou escrever nessas unidade de informação;

2) ao nível externo ou de interacção entre o programa e os dispositivos físicos

onde são armazenados os ditos ficheiros.

As principais operações a ter em conta no trabalho com ficheiros são:

• declaração de tipos e variáveis de ficheiros;

• associação de uma variável de ficheiro com um nome externo de ficheiro;

• criação de novos ficheiros ou reescrita total de um ficheiro já existente;

• escrita de informação num ficheiro;

• abertura de um ficheiro para leitura;

• procura de dados num ficheiro;

• fecho de um ficheiro aberto;

• fusão de ficheiros;

• etc.

Exemplos de operações no trabalho com ficheiros de registo:

• consultar registo por registo;

• listar todos os registos de um ficheiro;

• acrescentar mais registos;

• alterar os dados de um determinado registo;

• consulta de uma registo dada a sua posição no ficheiro



Instruções em pseudocódigo para manipulação de ficheiros

Como exemplo vamos usar um ficheiro chamado NOMES.DAT, cujos registos

contem 4 campos com o NOME, MORADA, IDADE e TELEFONE dos alunos da

turma. Algumas instruções usadas em pseudocódigo para manipulação de ficheiros

são as seguintes:

1. Em primeiro lugar é preciso declarar o ficheiro, o seu nome e a estrutura dos

registos:

NOMES.DAT é ficheiro de ALUNO

ALUNO é um registo composto por

NOME – alfanumérica

IDADE – numérica, inteira

MORADA – alfanumérica

TELEFONE – alfanumérica

Fim de registo

2. Abrir um ficheiro para escrita Abrir NOMES.DAT para escrita

3. Escrita de um registo

Escrever NOMES.DAT, ALUNO

4. Abrir um ficheiro para leitura Abrir NOMES.DAT para leitura

5. Testar fim de ficheiro

ff (NOMES.DAT)

6. Leitura de um registo Ler ALUNO, NOMES.DAT

7. Fechar ficheiro Fechar NOMES.DAT



Suportes físicos de ficheiros

As memórias auxiliares, embora sendo exteriores ao computador, operam como

extensões da sua memória central. São meios de memorização capazes de

armazenar quantidades de informação muito superiores às que a memória central

pode guardar, e funcionam como armazéns de informação que a memória central

requisita sempre que necessário. Existem grande variedade de memórias auxiliares,

como suporte físico de ficheiros, sendo mais frequentes as unidades de discos

magnéticos e as unidades de fita magnética.

Suportes físicos mais utilizados para armazenar informação:

• banda magnética;

• disquetes;

• disco magnético duro;

• discos ópticos;

• tapes;

• etc.

A escolha dos suportes relaciona-se com três características:

1. capacidade - sendo as bandas magnéticas, discos duro e óptico e as tapes,

de maior capacidade;

2. tipo de tratamento a dar ao ficheiro;

3. velocidade de tratamento - em que os discos duros e ópticos são os mais

rápidos.

O acesso aos ficheiros nestes suporte é também de grande importância pois

condiciona algumas das características atrás referidas. Assim o acesso pode ser de

dois tipos:

• acesso sequencial;

• acesso directo - nunca se poderia utilizar a banda magnética.



3.9. Árvores Binárias

Conceitos Básicos

Uma árvore binária é o conjunto finito de elementos que: ou está vazio ou

contém um elemento chamado raiz da árvore, sendo os restantes elementos

divididos em dois subconjuntos disjuntos, cada um dos quais é, por si mesmo, uma

árvore binária.

Se n1 for a raiz de uma árvore binária e n2 for a raiz da sua sub-árvore direita ou

esquerda, então diz-se que n1 é o pai de n2, e que n2 é o filho direito ou esquerdo

de n1. O nó n2 é um descendente de n1 e n1 é o seu ascendente.

Um nó que não tenha filhos é uma folha. Dois nós são irmãos se são os filhos

direito e esquerdo do mesmo pai.

Nível de um nó numa árvore binária: a raiz da árvore tem nível 0. O nível de

outro nó qualquer é uma unidade mais que o nível do pai. Uma árvore binária

completa de nível n é uma árvore em que cada nó de nível “n” é uma folha e em que

todos os nós de nível menor que “n” têm sub-árvores direita e esquerda não vazias.

Uma árvore binária completa de nível 3 seria:

A

B C

D E

G

F

H I



Estrutura de uma árvore binária

Pode considerar-se que cada nó de uma árvore binária tem três campos. O campo de informação, que armazena informação Info(nodo), e dois campos de

ponteiros Esq(nodo) e Dir(nodo) que referenciam as raízes das sub-árvores esquerda

e direita da árvore binária cuja raiz é nodo. Se uma sub-árvore está vazia o seu

ponteiro é nil.

A estrutura de dados em pascal, de uma árvore binária, poderia ser a seguinte:

Type NodoPtr = ^Nodo;

Nodo = Record

Info: TipoDados;

Esq: NodoPtr;

Dir: NodoPtr;

End;

Var Tree: NodoPtr;

Operações sobre uma árvore binária

Algumas operações dinâmicas sobre uma árvore binária:

MakeTree(x) – Cria uma nova árvore binária consistindo num nó apenas, com x

no seu campo de informação e fornece um ponteiro para esse nó. Um algoritmo

possível seria: P ! CriarNodo

Info(p) ! x

Esq(p) ! nil

Dir(p) ! nil

MakeTree ! p

SetEsq(p, x) – Aceita um ponteiro p (p≠nil) para um nó de uma árvore binária sem

filho esquerdo, criando, no nodo p, um filho esquerdo novo, cujo campo de

informação é preenchido por x. Um algoritmo possível seria:

Se Esq(p) ≠ nil

Então Escreva(‘Inserção inválida’)

Senão q ! MakeTree(x)

Esq(p) ! q



SetDir(p, x) – Aceita um ponteiro p para um nó de uma árvore binária sem filho

direito, criando, no nodo p, um filho direito novo, cujo campo de informação é

preenchido por x.

Aplicações de árvores binárias

Uma árvore binária é uma estrutura de dados útil quando decisões com duas

alternativas são tomadas em cada ponto de um processo.

Por exemplo, determinar os número que estão duplicados numa lista de

números. Para se reduzir o número de comparações podemos usar uma árvore

binária.

O primeiro número lido é colocado num nó que passa a ser a raiz de uma árvore

binária com as sub-árvores esquerda e direita vazias.

Cada número sucessivo na lista é comparado ao número na raiz. Se for igual

existe um duplicado. Se for menor, o processo é repetido para a sub-árvore

esquerda, e se for maior o processo é repetido para a sub-árvore direita.

O processo continua até que outro duplicado seja encontrado ou até se chegar a

uma sub-árvore vazia. Se se chegar a uma sub-árvore vazia o número é colocado

num novo nó nessa posição na árvore.

Um algoritmo possível seria:

1. [Lê-se o primeiro número e insere-se numa árvore binária com um único nó.]

Ler(NUM)

TREE ! MakeTree(NUM)

2. [Comparar os números da entrada e percorrer a árvore]

Enquanto <existirem números na entrada>

Ler(NUM)

Q ! TREE {São necessários dois ponteiros para navegação na árvore}

P ! TREE

Enquanto NUM ≠ Info(P) e Q ≠ NIL {Continua até que um duplicado seja encontrado ou até se chegar a uma sub-árvore vazia}

P ! Q

Se NUM < Info(P)



Então Q ! Esq(P)

Senão Q ! Dir(P)

Fim Enquanto {Fim da pesquisa}

Se NUM = Info(P) {Duplicado encontrado?}

Então Escrever(NUM, ‘ está duplicado’) {Número duplicado}

Senão Se NUM < Info(P) {Colocar num novo nodo com o número da entrada}

Então SetEsq(P, NUM)

Senão SetDir(P, NUM)

Fim Enquanto {Fim de número da entrada}

Exemplo do algoritmo:

Sequência de números da lista: 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5

Nem sempre os nós de uma árvore binária contêm todos o mesmo tipo de

informação. Por exemplo para representar uma expressão binária com operadores

numéricos constantes, podemos usar uma árvore binária cujas folhas contêm

números, contendo os outros nós caracteres representando operadores. Para

representar este tipo de árvores em pascal podemos usar registos variáveis.

14

4 15

3 9

7

18

16 20

5 17



Travessias de uma árvores binárias

Outra aplicação seria percorrer uma árvore binária, atravessando todos os seus

nós, e enumerando-os.

No caso de uma árvore não há uma ordem “natural” de percurso. Vamos definir

três métodos para percorrer a árvore. Os métodos são definidos recursivamente de

modo que percorrer uma árvore binária implicará percorrer a raiz e as suas

sub-árvores esquerda e direita.

Métodos:

• Pré-ordem (ou em profundidade)

• Em-ordem (ou da ordem simétrica)

• Post-ordem

Método da pré-ordem 1. Visitar a raiz

2. Percorrer a sub-árvore esquerda em pré-ordem

3. Percorrer a sub-árvore direita em pré-ordem

Implementação recursiva: PréOrdem(p) – Imprime o conteúdo de uma

árvore binária em pré-ordem. p é um ponteiro para o nó raiz de uma árvore

binária.

Se p ≠ NIL

Então Escrever(Info(p))

PréOrdem(Esq(p))

PréOrdem(Dir(p))

Método da em-ordem 1. Percorrer a sub-árvore esquerda em em-ordem

2. Visitar a raiz

3. Percorrer a sub-árvore direita em em-ordem


ESEV(Prof. Serv.) - Prof. José Alberto Pereira

Implementação recursiva: EmOrdem(p) – Imprime o conteúdo de uma

árvore binária em em-ordem. p é um ponteiro para o nó raiz de uma árvore

binária.

Se p ≠ NIL

Então EmOrdem(Esq(p))

Escrever(Info(p))

EmOrdem(Dir(p))

Método da post-ordem 1. Percorrer a sub-árvore esquerda em post-ordem

2. Percorrer a sub-árvore direita em post-ordem

3. Visitar a raiz

Implementação recursiva: PostOrdem(p) – Imprime o conteúdo de uma

árvore binária em post-ordem. p é um ponteiro para o nó raiz de uma árvore

binária.

Se p ≠ NIL

Então PostOrdem(Esq(p))

PostOrdem(Dir(p))

Escrever(Info(p))

Exemplos:

A

B C

D E

H I G

Pré-ordem: A B D G C E H I F

Em-ordem: D G B A H E I C F

Post-ordem: G D B H I E F C A

56

F



Muitos algoritmos ou processos que usam árvores binárias começam por

construir uma árvore binária, e depois percorrem-na. Suponha-se que, dada uma

lista de números, se pretende imprimir esses números por ordem crescente.

Á medida que os números são lidos são inseridos numa árvore binária. Os

números duplicados são também incluídos na árvore binária. Quando um numero é

menor que o número contido num nó, é inserido no ramo da esquerda. Se o número

é maior que o número contido no nó (ou igual) é inserido no ramo da direita.

Nesta árvore binária todos os nós na sub-árvore esquerda de um nó “n” são

menores que o conteúdo de “n”, e todos os nós na sub-árvore direita de um nó “n”

são maiores ou iguais que o conteúdo do nó “n”.

Se a árvore for percorrida no método em-ordem (esquerda, raiz, direita) os

números são impressos em ordem crescente.

Algumas funções recursivas

O processo recursivo é constituído por duas partes: a primeira constituindo o

caso de base e a segunda o caso recursivo.

• ContaNós(p) – Contar o número de nós numa árvore p

Se p≠ NIL

Então ContaNós ! 0 {Caso base}

Senão ContaNós ! 1 + ContaNós(Esq(p)) + ContaNós(Dir(p)) {Caso recursivo}

• ContaFolhas(p) – Contar o número de folhas numa árvore p

Se p≠ NIL

Então ContaFolhas ! 0 {Caso base}

Senão Se (Esq(p)=NIL) e (Dir(p)=NIL)

Então ContaFolhas ! 1 {Caso base}

Senão ContaFolhas ! ContaFolhas(Esq(p)) + ContaFolhas(Dir(p)) {Caso recursivo}

• Altura(p) – Calcula a altura de numa árvore p

Se p≠ NIL

Então Altura ! 0 {Caso base}

Senão Altura ! 1 + Maior(Altura(Esq(p)), Altura(Dir(p)) {Caso recursivo}

Em que, a função Maior(a, b) devolve o maior número, a ou b.



4 . M É T O D O S D E O R D E N A Ç Ã O E P E S Q U I S A

4.1. Pesquisa Linear num Vector não Ordenado

1ª Versão

Dado um vector K não ordenado com N (≥ 1) elementos, pesquisa se existe ou não no

vector K um elemento K[I], de índice L, com o valor X dado.

1. [Inicializações]

L ! 1

2. [Pesquisar o vector enquanto não achar]

Repita enquanto L ≤ N e K[L] ≠ X

L ! L + 1

3. [Verificar se a pesquisa foi com ou sem sucesso]

Se L = N+1

Então Escrever(‘Insucesso’)

Senão Escrever(‘Sucesso em ‘, L)

4. [Termina]

Saída

Esta versão é óptima, mas não ideal! A condição de controlo do ciclo é simplificável com o uso de uma sentinela em N+1.

Nesta versão, existem duas condições diferentes que podem terminar o processo de pesquisa: encontra-se um elemento X = K[L]; o fim da sequência (L=N)

é atingido.

Estes ciclos com duas condições de fim de repetição simplificam-se usando uma sentinela K[N+1] = X, pois deixa de ser necessário verificar se se ultrapassou o fim

da sequência.



2º Versão

Dado um vector K desordenado, com N elementos (N ≥ 1) e dimensionado de N+1, este

algoritmo pesquisa o vector para encontrar um dado valor X. O elemento K[N+1] actua

como sentinela e antes da pesquisa recebe o valor de x.


L ! 1

K[N+1] ! X

2. [Pesquisar no vector]

Repita enquanto K[L] ≠ X

L ! L + 1


Se L = N+1

Então Escrever(‘Insucesso’)

Senão Escrever(‘Sucesso em ‘, L)

4. [Termina]

Saída

Neste algoritmo a pesquisa é sempre (...) “bem sucedida”, pois a sentinela é K[N+1] = X; por isso o índice L nunca é testado, o que torna esta versão mais

eficiente que a anterior.

É a pesquisa ideal, para vectores desordenados e deve sempre ser a utilizada.

4.2. Pesquisa Linear num Vector Ordenada

Dado um vector K ordenado, com N elementos, K[1] < K[2] < ... < K[N], este algoritmo

pesquisa no vector um dado elemento X. Por conveniência e rapidez supõe-se existir um

elemento K[N+1] que actua como sentinela: K[N+1] = ∞ > X.


L ! 1

K[N+1] ! 9999999



2. [Pesquisar no vector]

Repita enquanto X > K[L]

L ! L + 1


Se X = K[L]

Então Escrever(‘Sucesso em ‘, L)

Senão Escrever(‘Insucesso’)

4. [Termina]

Saída

Há métodos muito mais eficientes, de pesquisa em vectores ordenados, em que

o tempo de pesquisa é mais reduzido.

4.3. Pesquisa Binária

Dado um vector K de N elementos ordenado, por ordem crescente, pesquisa se X existe

em K.

1. [Inicialização dos limites inferiores, superiores e médio dos intervalos de pesquisa]

INF ! 1

SUP ! N

MED ! TRUNC((INF + SUP) / 2)

2. [Bissecta-se o intervalo de pesquisa enquanto este tiver elementos e não se encontrar

X]

Repita enquanto INF < SUP e X ≠ K[MED]

Se X < K[MED]

Então SUP ! MED –1

Senão INF ! MED +1

MED ! TRUNC((INF + SUP) / 2)

3. [Resultado da pesquisa]

Se X = K[MED]

Então Escrever(‘Pesquisa com sucesso: ‘, X, ‘ está na posição ‘, MED)

Senão Escrever(‘Insucesso’)



4. [Termina]

Saída

4.4. Fusão Simples

Fusão: combinação de dois ou mais vectores ordenados num só.

Dado dois vectores ordenados A e B com respectivamente a dimensão de N e M

elementos, este algoritmo faz a fusão destes vectores (intercala) e produz um vector ordenado

C, que contém N+M elementos. As variáveis I, J, K e L são usadas como índices dos vectores.

1. [Inicialização]

I ! J ! K ! 1

2. [Comparar elementos e escolher o menor]

Repita enquanto I ≤ N e J ≤ M

Se A[I] ≤ B[J]

Então C[K] ! A[I]

I ! I + 1

K ! K + 1

Senão C[K] ! B[J]

J ! J + 1

K ! K + 1

3. [Copiar os elementos não processados para o vector de saída]

Se I = N

Então Repita para L = J, J+1, ..., M

C[K] ! B[L]

K ! K +1

Senão Repita para L = I, I+1, ..., N

C[K] ! A[L]

K ! K +1

4. [Termina]

Saída



4.5. Ordenação por Inserção Simples

Dado um vector K de N elementos (N ≥ 2), é ordenado por ordem crescente.

1. [Ciclo que sucessivamente escolhe os elementos]

Repetir até ao passo 3 para

L = 2, ..., N

2. [Preparar a pesquisa da posição correcta para a inserção]

J ! L-1

X ! K[L] { Elemento a inserir }

3. [Ciclo que faz a pesquisa da posição]

Repita enquanto J > 0 e X < K[J]

K[J+1] ! K[J] { Deslocamento para arranjar vaga para inserção correcta }

J ! J – 1

K[J+1] ! X

4. [Terminar]

Saída

Há duas condições diferentes que podem terminar o processo de transposição

(ciclo ‘Repita enquanto’): encontrar-se um elemento K[J] ≤ X; o lado esquerdo da

sequência é atingida (J=0).

Exemplo:

K[1] K[2] K[3] K[4] K[5] K[6]

44 55 11 22 66 33

44 55 11 22 66 33 (55 foi inserido na posição 2)







4.6. Ordenação por Selecção Simples

Dado um vector K de N elementos, é ordenado por ordem crescente.

1. [Executar as N-1 passagens para sucessivamente seleccionar o mínimo e fazer a sua

troca com o elemento de índice PASS]

Repetir até ao passo 4 para

PASS = 1, 2, ..., N-1

2. [Inicializar o índice mínimo]

MIN ! PASS

3. [Executar uma passagem e obter o elemento com menor valor]

Repita para L=PASS+1, PASS+2, ..., N

Se K[L] < K[MIN]

Então MIN ! L

4. [Troca de elementos: se encontrou um mínimo faz a troca]

Se MIN ≠ PASS

Então TEMP ! K[MIN]

K[MIN] ! K[PASS]

K[PASS] ! TEMP

5. [Terminar]

Saída

Este algoritmo selecciona dos N elementos de um vector K aquele com o menor

valor e troca-o com o primeiro elemento. De seguida selecciona dos N-1 elementos

do vector aquele com o menor valor e troca-o com o segundo elemento. O algoritmo

repete estas operações com os restantes N-2, depois N-3, até que só um resta (o

maior).



Exemplo:

K[1] K[2] K[3] K[4] K[5] K[6]

44 55 11 22 66 33

Passagem nº 1: 11 55 44 22 66 33 (44 trocou com 11)





4.7. Ordenação por Troca Simples

Dado um vector K de N elementos, é ordenado por ordem crescente.

1. [Inicialização]

LIMITE ! N

TROCA ! 1 { Número qualquer maior que zero, isto é, que torna a condição de controlo do ciclo ‘Repita Enquanto’ verdadeira. }

2. [Passagens só enquanto houver trocas. Compara e troca. A variável ‘Troca’

armazena o índice do vector da última troca efectuada, durante o ciclo]

Repita enquanto TROCA > 0

TROCA ! 0 { Inicialmente, nenhuma troca foi efectuada }

Repita para J=1, 2, ..., Limite-1

Se K[J] > K[J+1]

Então X ! K[J] { Troca dos elementos K[J]!" K[J+1] }

K[J] ! K[J+1]

K[J+1] ! X

TROCA ! J { Armazena a posição da troca }

Fim Repita

LIMITE ! TROCA { Os elementos acima de ‘Limite’ já estão ordenados. Elementos de maior valor }

3. [Termina]

Saída



Quando uma passagem do ciclo ‘Repita para’ não tem trocas (TROCA = 0) o

algoritmo pode terminar, já que o vector K já está ordenado.

No fim de cada ciclo ‘Repita para’, deve-se memorizar a posição (valor do índice

do vector K) da última troca na variável Limite. Todos os pares de itens adjacentes

acima deste limite já estão ordenados, e por isso, nas passagens seguintes deve-se

terminar em limite.

Exemplo:

K[1] K[2] K[3] K[4] K[5] K[6]

44 55 11 22 66 33








Passagem nº 4: 11 22 33 44 55 66 (não houve troca e termina)



Na impossibilidade temporal de incluir organizadamente neste manual a

aplicação dos conceitos com respectivos exercícios, junta-se agora algumas

aplicações por forma a que o aluno possa testar alguns dos conceitos adquiridos.

EXERCÍCIOS

1. Durante a elaboração de um programa de um projecto de informatização de um

terminal rodoviário, surgiram as seguintes necessidades, no que se refere a

estrutura de suporte de dados:

• É necessário manter, em memória secundária, o número de chegadas de

autocarros nos dias úteis de uma semana (de 2ª a 6ª feira), para todas as

semanas de um ano (52 semanas).

• Temporariamente, durante a execução do programa, é necessário guardar,

em memória primária, os totais respeitantes ao número de chegadas de

autocarros, nos dias da semana (de 2ª a 6ª feira).

• Para futuro cálculo estatístico mensal é necessário registar em memória

secundária, para cada autocarro que passa pelo terminal rodoviário, o seu

número da semana ( de 1 a 52), dia da semana (de 1 a 5), hora e número

de passageiros.

Seleccione a estrutura de dados (vector, matriz ou ficheiro) que mais se

adequa a cada um dos casos anteriores, apresentando para os vectores e

matrizes as suas dimensões e para os ficheiros o nome dos seus campos.

2. Sugira uma estrutura de dados (vector, matriz ou ficheiro) adequada ao registo,

em memória secundária, do número de peças com e sem defeitos produzidas em

determinada data. Apresente, no caso da estrutura de dados escolhida ser um

vector ou matriz, a sua dimensão; no caso de ser um ficheiro, o nome dos campos

constituintes dos seus registos.

3. Transcreve, para a sua folha de prova, os “termos” adequados ao preenchimento

dos espaços assinalados no algoritmo seguinte (#, $, %, &, ', ().



Este algoritmo determina a taxa de retenção de IRS na fonte, com base na

remuneração mensal do funcionário e no seu número de dependentes.

Considera-se a tabela de trabalho dependente casado único titular do IRS

constituída por 31 intervalos de remuneração, para determinar a respectiva taxa.

O vector INTERVALOS, com 31 elementos, contém os intervalos de remuneração

mensal da tabela. A matriz TAXAS, com 31 linhas e 6 colunas, contém as taxas

de retenção aplicáveis mediante a remuneração auferida e o número de

dependentes (0, 1, 2, 3, 4, 5 ou mais). Consideram-se ambas as estruturas

devidamente preenchidas.

1. [ Ler a remuneração mensal e o número de dependentes do funcionário] Leia(REMUNERAÇÃO) Leia(N_DEPENDENTES) 2. [Determinar o índice do intervalo de remuneração] I ! 1 Repita enquanto # ______________________ $ __________ ! I + 1 3. [“Corrigir”, se necessário, o número de dependentes] Se N_DEPENDENTES % _____________ Então J ! & _______________ Senão ' ___________________ 4. [Imprimir a taxa de retenção adequada ao funcionário] ( _____________________________________________ 5. [Terminar] Saída

4. Dado dois vectores ordenados A e B contendo N e M elementos,

respectivamente, dispostos por ordem crescente, elabora um algoritmo que faz a

fusão destes vectores e produz um vector C ordenado, contendo todos os

elementos pares.

5. Dado dois vectores ordenados A e B, dispostos por ordem crescente, contendo N

e M elementos, respectivamente, e M maior que N, elabora um algoritmo para

verificar se A está contido em B. Nota: Procura tirar partido do ordenamento dos

elementos.



6. Elabora uma função que devolve o número de elementos negativos de um vector

K não ordenado de N elementos.

7. Completa o passo 1 e 2 do algoritmo seguinte, de forma que seja emitida a

mensagem “Tem direito a bónus”, se o funcionário respeitar os seguintes

requisitos:

• a totalidade dos dias de falta, desde o início do ano, não for superior a um dia

por mês decorrido, incluindo o mês a que se refere a remuneração (MÊS).

Assuma que o vector FALTAS está preenchido com o número de dias de falta,

em cada mês, do funcionário;

• ÍNDICE de produtividade for superior à produtividade média (PRODMÉDIA).

Considere que a produtividade média já foi calculada e atribuída à variável

respectiva;

• a CLASSIFICAÇÃO da qualidade do trabalho desenvolvido for “Bom”.

1. [Ler o mês, o Índice e a classificação]

2. [Avaliação dos requisitos de atribuição de bónus]

8. Elabora o passo 2 do algoritmo seguinte, de forma a que seja calculada e

impressa a importância a pagar pelo cliente relativamente ao tempo de aluguer de

um vídeo. O valor a cobrar por dia é calculado da seguinte maneira:

• no primeiro e segundo dia o aluguer do vídeo é pago a 400 Esc.; no terceiro

dia o aluguer do vídeo é pago a 500 Esc.; nos restantes dias o aluguer do

vídeo é pago com um acréscimo de 200 Esc. ao valor do dia anterior, ou seja,

no quarto é pago a 700 Esc., no quinto dia a 900 Esc., etc.

1. [Ler o número de dias de permanência]

Leia(DIAS)

2. [Calcular e imprimir a importância a pagar]



9. Suponha a adivinha do caracol que se encontra no fundo dum poço de 10

metros, subindo cada dia 3 metros, mas descendo depois 2. Quantos dias demora o

caracol a chegar ao topo?

Elabora um algoritmo, que através duma pilha, calcule a adivinha. Cada metro

deve representar um elemento da pilha. A pilha deve ser representada usando um

vector.

O trabalho deve ser realizado individualmente ou em grupo de dois elementos,

em pascal ou C. Todos os trabalhos apresentarão uma versão fonte devidamente

comentada e uma versão executável.

O objectivo fundamental deste trabalho é a capacidade de aplicar os conceitos

teóricos na resolução de questões de natureza prática.

Os trabalhos deverão ser entregues até dia 24 de Outubro, caso contrário a sua

avaliação será penalizada.

Documents

ESCOLA SECUNDÁRIA DE VOUZELA Curso Tecnológico de … · Curso Tecnológico de Informática ... Designação Operador igual a = diferente de ... Tal como a saída de dados do computador