UNIVERSIDADE SALGADO DE OLIVEIRA
CURSO DE ANÁLISE DE SISTEMAS
APOSTILA DE
LINGUAGEM DE PROGRAMAÇÃO I
Prof. Giuliano Prado de Morais Giglio
Curso de Análise de Sistemas
Linguagem de Programação I
SUMÁRIO
Capitulo 01 - Registros
03
Capítulo 02 – Tipos Definidos pelo Usuário e Constantes
09
Capítulo 03 – Modularização (Funções e Procedimentos)
12
Capítulo 04 – Arquivos
22
Capítulo 05 – Métodos de Pesquisa
34
Capítulo 06 – Métodos de Classificação
37
Prof. Giuliano Prado M. Giglio
2
Curso de Análise de Sistemas
Linguagem de Programação I
CAPÍTULO 1
REGISTROS
Os tipos de dados que são mais comumente usados, e que foram vistos com maior ênfase em
Algoritmos, são :
1.
2.
3.
4.
5.
6.
7.
8.
WORD
INTEGER
REAL
BYTE
STRING
CHAR
ARRAY
BOOLEAN
Uma outra forma de definir uma variável em Pascal, é através do tipo RECORD. Esse tipo
é diferente das demais formas de definir variáveis, porque permite que uma variável armazene
valores de diversos tipos diferentes.
Exemplo 01: Imagine que fosse desejado armazenar informações de uma pessoa, tais
como: Nome, Idade, Altura, Sexo, Número de Dependentes, Profissão.
Na forma tradicional, seria necessário definir uma variável para cada tipo de informação, ou seja:
VAR
Nome
Idade
Altura
Sexo
NumDep
Profissão
: STRING;
: BYTE;
: REAL;
: CHAR;
: BYTE;
: STRING;
Utilizando o tipo RECORD ou Registro, teremos uma outra definição, que será explicado
mais adiante:
1.1. Conceituando Registros
São conjuntos de dados logicamente relacionados, mas de tipos diferentes (inteiro, real,
string, etc.).
Exemplo 02: Numa dada aplicação, pode-se ter os seguintes dados sobre funcionários de uma
empresa:
⇒ Nome
⇒ Endereço
⇒ Idade
Prof. Giuliano Prado M. Giglio
3
Curso de Análise de Sistemas
Linguagem de Programação I
⇒ Salário
Cada conjunto de informações do funcionário pode ser referenciado por um mesmo nome, por
exemplo, FICHA. Tais estruturas são conhecidas como registros, e aos elementos do registros
dá-se o nome de campos.
O conceito de registro visa facilitar o agrupamento de variáveis que não são do mesmo tipo,
mas que guardam estreita relação lógica.
1.2. Declaração
Criam-se estruturas de dados agrupados na forma de registro através da seguinte
declaração:
lista-de-identificadores :
onde:
RECORD
< campos >
END;
lista-de-identificadores => são os nomes que estão sendo associados aos registros que
se deseja declarar;
campos => são declarações de variáveis, separadas por ponto-e-vírgula.
Exemplo 03:
Declarar o registro FICHA especificado anteriormente.
Var FICHA : record
end;
NOME : string[30];
ENDERECO : string[40];
IDADE : byte;
SALARIO : real;
1.3. REFERÊNCIA
A referência ao conteúdo de um dado campo do registro será indicada pela notação:
identificador-do-registro . identificador-do-campo
Exemplo 04: Sabendo-se que o registro FICHA, em um dado instante, contivesse os valores a
seguir:
NOME : Antônio Ajuizado
ENDEREÇO: Rua das Virtudes, s/n
IDADE: 20 anos
SALÁRIO: R$ 150,00
FICHA.IDADE estaria fazendo referência ao conteúdo do campo IDADE do registro FICHA,
isto é, 20.
Prof. Giuliano Prado M. Giglio
4
Curso de Análise de Sistemas
Linguagem de Programação I
Outro exemplo:
No exemplo 1 no começo do capítulo, vimos como representar um conjunto de dados de uma
pessoa em diferentes variáveis. Logo, utilizando a estrutura de registros ou o tipo RECORD,
teremos a seguinte definição:
VAR
Pessoa : RECORD
Nome
Idade
Altura
Sexo
NumDep
Profissão
END;
: STRING;
: BYTE;
: REAL;
: CHAR;
: BYTE;
: STRING;
Ao definir uma variável como sendo do tipo RECORD, devemos definir, também quais
serão as partes componentes desta variável(Nome, Idade, Altura , Sexo, NumDep e Profissão),
junto com o seu tipo. Quando estamos trabalhando com RECORD, as partes componentes do
mesmo recebem um Nome próprio, o qual é conhecido como “campo “. Desta forma, uma variável
RECORD pode ter campos de qualquer tipo válido do Pascal, sendo permitido inclusive que um
RECORD seja definido dentro do outro, ou como parte de um ARRAY.
Continuando o Exemplo, caso desejarmos atribuir um valor a variável Pessoa, devemos
fazê-lo da seguinte forma:
Pessoa.idade : = 45
O uso do “.” indica que esta variável possui campos, e que “Idade” é um deles. É
importante lembrar que as operações realizadas sobre uma variável RECORD, são as mesmas de
uma variável “comum”, a única diferença que devemos indicar o Nome da variável, seguido de um
ponto(.), seguido do Nome do campo.
É possível atribuir o conteúdo de uma variável RECORD para outra variável, de mesmo
tipo, da mesma forma que é feito como as outras variáveis do Pascal.
Exemplo 05: Caso duas variáveis, digamos A e B sejam definidas como sendo RECORDs, e caso
seja desejado passar o conteúdo, isto é os valores existentes nos campos, a variável A para a
variável B, bastará realizar a seguinte atribuição:
A: =B
Prof. Giuliano Prado M. Giglio
5
Curso de Análise de Sistemas
Linguagem de Programação I
1.4. CONJUNTO DE REGISTROS
Podem-se ter conjunto de registros referenciáveis por um mesmo nome e individualizados por
índices, através da utilização de um array de registros.
Exemplo:
Var
TAB : array[1..50] of record
MATR : integer;
NOME : string[30];
MEDIA : real;
end;
1.4.1. Exercício Resolvido
Considerando o registro de uma mercadoria de uma loja contendo as seguintes informações:
código, nome, preço e estoque, fazer um programa que, dado o registro de 50 mercadorias, leia
um código exiba o nome, preço e estoque da respectiva mercadoria.
Program MERCADORIAS;
Uses Crt;
Const N = 50;
Var TAB : array[1..N] of record
COD :
NOME :
PRECO:
EST :
end;
I : integer;
K : string[6];
RESP : char;
string[6];
string[15];
real;
integer;
Begin
clrscr;
{Leitura dos dados}
for I:=1 to N do
begin
write('Código: '); readln(TAB[I].COD);
write('Nome: '); readln(TAB[I].NOME);
write('Preço: '); readln(TAB[I].PRECO);
write('Estoque: '); readln(TAB[I].EST);
end;
Prof. Giuliano Prado M. Giglio
6
Curso de Análise de Sistemas
Linguagem de Programação I
repeat
{leitura da chave de pesquisa}
write('entre com o código desejado: ');
Readln(K);
{testa em cada registro se o código é igual a chave
pesquisada}
for I:=1 to N do
if K = TAB[I].COD then
writeln(TAB[I].NOME, TAB[I].PRECO, TAB[I].EST);
{verifica se o usuário deseja pesquisar outro código}
write('Repetir(S/N)?');
RESP := readkey;
until upcase(RESP) = 'N';
End.
1.5. O Comando WITH
Este comando permite que os campos de um registro sejam denotados unicamente por seus
identificadores, sem a necessidade de serem precedidos pelo identificador do registro. Forma
geral:
WITH identificador-do-registro DO
comandos
1.5.1. Exercício Resolvido
Reescrever o programa MERCADORIAS (R8.01), utilizando o comando WITH.
Program MERCADORIAS_WITH;
Uses
Crt;
Const N = 50;
Var TAB : array[1..N] of record
COD :
NOME :
PRECO:
EST :
end;
I : integer;
K : string[6];
RESP : char;
string[6];
string[15];
real;
integer;
Begin
clrscr;
Prof. Giuliano Prado M. Giglio
7
Curso de Análise de Sistemas
Linguagem de Programação I
{Leitura dos dados}
for I:=1 to N do
with TAB[I] do
begin
write('Código: '); readln(COD);
write('Nome: '); readln(NOME);
write('Preço: '); readln(PRECO);
write('Estoque: '); readln(EST);
end;
repeat
{leitura da chave de pesquisa}
write('entre com o código desejado: '); Readln(K);
{testa em cada registro se o código é igual a chave
pesquisada}
for I:=1 to N do
with TAB[I] do
if K = COD then
writeln(NOME, PRECO, EST);
{verifica se o usuário deseja pesquisar outro código}
write('Repetir(S/N)?');
RESP := readkey;
until upcase(RESP) = 'N';
End.
Prof. Giuliano Prado M. Giglio
8
Curso de Análise de Sistemas
Linguagem de Programação I
CAPÍTULO 2
Tipos Definidos Pelo Usuário e Constantes
2.1. Tipos Definidos Pelo Usuário
O Pascal possui vários tipos pré-definidos, como INTEGER, WORD, REAL etc, mas além
destes tipos básicos, existe a possibilidade de o usuário definir seus próprios tipos de dados.
Para isto, é necessário o uso da palavra reservada TYPE, a qual indica que um novo tipo será
criado.
Exemplo: Imagine que seja desejado criar um tipo matriz 4X4, sendo que logo em seguida
este novo tipo será usado para definir uma variável como sendo deste tipo. Para isto deverá ser
usada a seguinte definição:
TYPE
Matriz = ARRAY[1..4,1..4] OF INTEGER
VAR
Mat
: Matriz
O Pascal permite a definição de tipos usando qualquer um dos tipos pré-definidos, ou até
mesmo utilizando tipos definidos pelo usuário
Exercício de Fixação:
1. Seja a seguinte definição para um aluno de uma determinada escola: Nome, Semestre, Sala,
Curso, Notas(total de seis). Crie um tipo de dado para alunos e em seguida defina uma variável
como sendo um ARRAY deste tipo. A título de ilustração, defina o RECORD do campo endereço,
como sendo também um tipo.
Prof. Giuliano Prado M. Giglio
9
Curso de Análise de Sistemas
Linguagem de Programação I
2.2. Constantes
Uma constante é uma posição de memória que possui um valor fixo, constante, durante
toda a existência do programa. A sua utilização possibilita uma maior clareza do código, tornando
a tarefa de manutenção ou entendimento do programa muito mais simples.
Exemplo:
IF Tecla = CHR(24) THEN
BEGIN
<executa comandos>;
END;
O pedaço de código mostrado acima seria mais legível se , ao invés da utilização
da
Função CHR(24), fosse utilizado uma constante. Desta forma , o programa alterado ficaria como
é mostrado abaixo:
IF Tecla = SetaParaBaixo THEN
BEGIN
<executa comandos>;
END;
A forma de se declarar uma constante é através do uso da palavra reservada CONST.
Prof. Giuliano Prado M. Giglio
10
Curso de Análise de Sistemas
Linguagem de Programação I
Exemplo: Declarar uma constante que representa o valor da seta para baixo, do teclado do PC.
CONST
SetaParaBaixo=CHR(24)
BEGIN
<Comandos>;
END
Um outro uso muito útil de constantes é o de definir o tamanho de um ARRAY e o escopo
dos laços de repetição, como FOR DO, WHILE DO e REPEAT UNTIL.
PROGRAM Teste;
CONST
TotalLinhas = 10;
TotalColunas = 20;
TYPE
matriz = ARRAY[ 1..totallinhas, 1 ..totalcolunas] OF INTEGER;
VAR
Mat : matriz;
lin,col : BYTE;
BEGIN
FOR lin : = 1 TO totallinhas DO;
BEGIN
FOR col: = 1 TO totalcolunas DO
BEGIN
READ(mat[lin,col]);
END;
END;
END.
Prof. Giuliano Prado M. Giglio
11
Curso de Análise de Sistemas
Linguagem de Programação I
CAPÍTULO 3
MODULARIZAÇÃO
A modularização consiste num método utilizado para facilitar a construção de grandes
programas, através de sua divisão em pequenas etapas, que são os módulos ou subprogramas. A
primeira delas, por onde começa a execução do trabalho, recebe o nome de programa principal, e
as outras são os subprogramas propriamente ditos, que são executados sempre que ocorre uma
chamada dos mesmos, o que é feito através da especificação de seus nomes.
Vantagens da utilização de subprogramas:
• Economia de código: escreve-se menos;
• Desenvolvimento modularizado: pensa-se no algoritmo por partes;
• Facilidade de depuração (correção/acompanhamento): é mais fácil corrigir/detectar um erro
apenas uma vez do que dez vezes;
• Facilidade de alteração do código: se é preciso alterar, altera-se apenas uma vez;
• Generalidade de código com o uso de parâmetros: escreve-se algoritmos para situações
genéricas.
Há duas espécies de subprogramas: PROCEDIMENTO e FUNÇÃO.
3.1. PROCEDIMENTO
Um subprograma do tipo PROCEDIMENTO é, na realidade, um programa com vida própria, mas
que, para ser processado, tem que ser solicitado pelo programa principal que o contém, ou por
outro subprograma, ou por ele mesmo.
Declaração:
PROCEDURE nome;
declaração dos objetos locais ao Procedimento
BEGIN
comandos do Procedimento
END;
onde:
nome
é o identificador associado ao procedimento.
Prof. Giuliano Prado M. Giglio
12
Curso de Análise de Sistemas
Linguagem de Programação I
EXEMPLO:
O programa abaixo calcula a média aritmética entre 2 notas, sem o uso de procedimentos.
Program CALCULA_MÉDIA; {sem o uso de procedimentos}
var
NOTA1,NOTA2,MEDIA : real;
begin
{lê as notas}
write('Digite a primeira nota: ');
readln(NOTA1);
write('Digite a segunda nota: ');
readln(NOTA2);
{calcula a media}
MEDIA := (NOTA1 + NOTA2) / 2;
{escreve o resultado}
writeln('Media = ',MEDIA,4:1)
end.
Mostraremos agora o mesmo programa, utilizando um procedimento.
Program CALCULA_MÉDIA; {usando procedimento}
var
NOTA1,NOTA2,MEDIA : real;
{declaração do procedimento}
procedure LER_NOTAS;
begin
write('Digite a primeira nota: ');
readln(NOTA1);
write('Digite a segunda nota: ');
readln(NOTA2);
end;
{Programa Principal}
begin
LER_NOTAS; {ativação do procedimento LER_NOTAS}
MEDIA := (NOTA1 + NOTA2) / 2; {calcula a media}
Writeln('Media = ',MEDIA,4:1) {escreve o resultado}
end.
Prof. Giuliano Prado M. Giglio
13
Curso de Análise de Sistemas
Linguagem de Programação I
3.2. FUNÇÃO
As funções, embora bastante semelhantes aos procedimentos, têm a característica especial de
retornar ao programa que as chamou um valor associado ao nome da função. Esta característica
permite uma analogia com o conceito de função da Matemática.
Declaração:
FUNCTION nome : tipo;
declaração dos objetos locais à Função
BEGIN
Comandos da Função
END;
onde:
nome
é o identificador associado à função.
tipo
é o tipo da função, ou seja, o tipo do valor de retorno.
EXEMPLO:
O programa abaixo calcula a média dos elementos de um vetor, sem uso de Procedimentos ou
Funções.
Program SOMA_VETOR; {sem o uso de procedimentos ou funções}
const N = 30;
var VETOR : array[1..N] of integer;
I,SOMA,MEDIA : integer;
begin
{lê os valores do vetor}
for I:=1 to N do
readln(VETOR[I]);
{calcula a media}
SOMA := 0;
for I:=1 to N do
SOMA := SOMA + VETOR[I];
MEDIA := SOMA div N;
{escreve o resultado}
writeln(MEDIA)
end.
Mostraremos agora o mesmo programa, utilizando um procedimento para ler os valores do vetor e
uma função para efetuar o cálculo da média.
Prof. Giuliano Prado M. Giglio
14
Curso de Análise de Sistemas
Linguagem de Programação I
Program SOMA_VETOR; {usando uma função e um procedimento}
const
N = 30;
var
VETOR : array[1..N] of integer;
{declaração do procedimento}
procedure LER_DADOS;
var I : integer;
begin
for I:=1 to N do
readln(VETOR[I]);
end;
{declaração da função}
function MEDIA : integer;
var I,SOMA : integer;
begin
SOMA := 0;
for I:=1 to N do
SOMA := SOMA + VETOR[I];
MEDIA := SOMA div N;
end;
{Programa Principal}
begin
{ativa o procedimento LER_DADOS}
LER_DADOS;
{escreve o resultado, chamando a função MEDIA}
writeln(MEDIA)
end.
3.3. Variáveis GLOBAIS e Variáveis LOCAIS
Observe que, no exemplo anterior, declaramos uma variável no programa principal e outras
nos subprogramas. Podemos dizer que a variável VETOR, que foi declarada no programa principal
é uma variável global aos subprogramas, enquanto que a variável I é dita variável local ao
procedimento LER_DADOS e as variáveis I e SOMA são locais à função MEDIA. É importante
ressaltar que a variável I do procedimento LER_DADOS é diferente da variável I da função
MEDIA, embora possuam o mesmo identificador.
Prof. Giuliano Prado M. Giglio
15
Curso de Análise de Sistemas
Linguagem de Programação I
O uso de variáveis globais dentro de procedimentos e funções serve para implementar um
mecanismo de transmissão de informações de um nível mais externo para um mais interno.
As variáveis locais dos procedimentos e funções são criadas e alocadas quando da sua
ativação e automaticamente liberadas quando do seu término.
A utilização de variáveis globais não constitui, no entanto, uma boa prática de
programação. Assim, todos subprogramas devem apenas utilizar as variáveis locais, conhecidas
dentro dos mesmos, e a transmissão de informações para dentro e fora dos subprogramas deve
ser feita através dos parâmetros de transmissão, que serão apresentados a seguir.
3.4. Parâmetros
Quando se deseja escrever um subprograma que seja o mais genérico possível, deve-se
usar a passagem de parâmetros.
A passagem de parâmetros formaliza a comunicação entre os módulos. Além disto,
permite que um módulo seja utilizado com operandos diferentes, dependendo do que se deseja do
mesmo.
Dá-se a designação de parâmetro real ou de chamada ao objeto utilizado na unidade
chamadora/ativadora e de parâmetro formal ou de definição ao recebido como parâmetro no
subprograma.
Dentre os modos de passagem de parâmetros, podemos destacar a passagem por valor e
a passagem por referência.
Na passagem de parâmetros por valor, as alterações feitas nos parâmetros formais,
dentro do subprograma, não se refletem nos parâmetros reais. O valor do parâmetro real é
copiado no parâmetro formal, na chamada do subprograma. Assim, quando a passagem é por valor,
isto significa que o parâmetro é de entrada.
Na passagem de parâmetros por referência, a toda alteração feita num parâmetro formal
corresponde a mesma alteração feita no seu parâmetro real associado. Assim, quando a passagem
é por referência, isto significa que o parâmetro é de entrada-saída.
Na linguagem Pascal, a declaração dos procedimentos e funções com parâmetros se
diferencia da forma já apresentada apenas pela inclusão da lista de parâmetros formais no
Prof. Giuliano Prado M. Giglio
16
Curso de Análise de Sistemas
Linguagem de Programação I
cabeçalho. Esta deve vir entre parênteses e cada parâmetro deve ter o seu tipo especificado. A
forma geral é:
PROCEDURE nome (lista de parâmetros formais)
FUNCTION nome (lista de parâmetros formais) : tipo
A lista de parâmetros formais tem a seguinte forma:
parâmetro1 : tipo; parâmetro2 : tipo; ...; parâmetro n : tipo
Exemplos da lista de parâmetros:
procedure PROC (X,Y,Z:integer; K:real)
function FUNC (A,B:real; C:string) : integer
Na forma apresentada, a passagem dos parâmetros será por valor. Para se utilizar a passagem por
referência, deve-se acrescentar a palavra VAR antes do nome do parâmetro.
EXEMPLO:
Procedure PROC(A:integer; var B,C:integer)
Na chamada de procedimentos ou funções utilizando parâmetros, devemos acrescentar
após o nome do procedimento ou função uma lista de parâmetros reais (de chamada), os quais
devem ser do mesmo tipo e quantidade dos parâmetros formais declarados.
O exemplo a seguir demonstra a diferença entre a passagem de parâmetros por
referência e a passagem de parâmetros por valor:
Program EXEMPLO_PASSAGEM_PARÂMETROS;
var N1,N2 : integer;
Procedure PROC(X:integer; var Y:integer);
begin
X:=1;
Y:=1;
end;
begin
Prof. Giuliano Prado M. Giglio
17
Curso de Análise de Sistemas
Linguagem de Programação I
N1:=0; N2:=0;
PROC(N1,N2);
writeln(N1); {será exibido o valor 0}
writeln(N2); (será exibido o valor 1}
end.
3.4.1. Exercícios Resolvidos
1. Escrever uma função chamada MAIOR que receba dois números inteiros e retorne o maior deles.
Escrever um programa para ler dois números inteiros e, utilizando a função MAIOR, calcular e exibir o
maior valor entre os números lidos.
Program CALCULA_MAIOR;
var X,Y,M : integer;
function MAIOR
begin
If NUM1 >
MAIOR
else
MAIOR
end;
(NUM1,NUM2:integer) : integer;
NUM2 then
:= NUM1
:= NUM2;
begin
readln(X,Y);
M := MAIOR(X,Y);
writeln(M);
end.
2. Escrever um procedimento chamado DOBRA que multiplique um número inteiro (recebido como
parâmetro) por 2. Escrever um programa para ler um valor inteiro e , utilizando o procedimento
DOBRA, calcular e exibir o dobro do mesmo.
Program CALCULA_DOBRO;
var X : integer;
procedure DOBRA (var NUM:integer);
begin
NUM := NUM * 2
end;
begin
readln(X);
DOBRA(X);
writeln(X);
end.
Prof. Giuliano Prado M. Giglio
18
Curso de Análise de Sistemas
Linguagem de Programação I
3.5. Recursividade
Diz-se
que uma FUNCTION ou uma PROCEDURE é recursiva, quando ela chama a si
própria, esta característica pode , a princípio parecer estranha, ou até mesmo desnecessária
devido ao nível de programas o qual estamos trabalhando, mas o uso da recursividade muitas
vezes , é a única forma de resolver problemas complexos. No nível que será dado este curso,
bastará saber o conceito e o funcionamento de uma sub-Rotina recursiva.
Abaixo seguem exemplos de sub-Rotinas recursivas:
a)
PROCEDURE Recursão(A : BYTE);
BEGIN
IF a > 0 THEN
BEGIN
WRITE(A);
Recursão (A - 1);
END;
END;
b)
PROCEDURE Recursão( A : BYTE);
BEGIN
IF a > 0 THEN
BEGIN
Recursão ( A -1 );
WRITE( A ); { Esta linha será executada ao final de cada execução
da Rotina recursiva }
END;
END;
No primeiro Exemplo, a saída gerada será a seguinte seqüência de números: 5 4 3 2 1.
No segundo Exemplo, a saída gerada será a seguinte seqüência de números: 1 2 3 4 5 .
c)
PROCEDURE Recursão(A : BYTE) ;
VAR
Valor : BYTE;
BEGIN
Valor : = A DIV 2;
IF valor > 0 THEN
BEGIN
Recursão(Valor);
END;
WRITE(valor);
END;
Para um valor inicial igual a 80, a seqüência gerada será a seguinte: 0 1 2 5 10 20 40
No Exemplo acima será criado, a chamada da Rotina Recursão, uma variável diferente de
Nome “Valor”, a qual assumirá valores diferentes, dependendo do valor do parâmetro “A”.
Prof. Giuliano Prado M. Giglio
19
Curso de Análise de Sistemas
Linguagem de Programação I
Uma característica importante das Rotinas recursivas diz respeito a forma de
tratamento das variáveis e parâmetros. Usando como Exemplo o item acima, vemos que existe um
parâmetro chamado “A” e uma variável local a sub-Rotina, chamado Valor. É importante notar que
a cada ativação da Rotina recursiva, todos os parâmetros e variáveis locais, são tratados como
sendo posições de memória totalmente diferentes e independentes, apesar de terem o mesmo
Nome.
Segue abaixo uma representação das variáveis e seus conteúdos em cada uma das chamadas:
1a Chamada
A=80
Valor=40
2a Chamada
A=40
Valor=20
3a Chamada
A=20
Valor=10
4a Chamada
A=10
Valor=5
5a Chamada
A=5
Valor=2
6a Chamada
A=2
Valor=1
7a Chamada
A=1
Valor=0
Um exemplo clássico e comum de uma definição recursiva é o da função fatorial de “n”.
A função fatorial é denotada matematicamente por n! e expressa o valor do produto de todos os
números inteiros até (e inclusive) “n”. Assim, o fatorial de “n” é definido como:
n! =
1, se n = 0
n * (n - 1)! , se n > 0
Esta função pode ser escrita facilmente utilizando-se a recursividade:
function Fatorial (N : integer) : integer;
begin
if (N > 0)
then Fatorial := N * Fatorial(N - 1)
else Fatorial := 1;
end;
Embora não seja usada nenhuma estrutura de repetição, está sendo realizado um
produto de “n” termos.
Prof. Giuliano Prado M. Giglio
20
Curso de Análise de Sistemas
Linguagem de Programação I
3.5.1. Exercícios Propostos:
1. Explique qual será o resultado e o funcionamento dos seguintes programas:
a)-
PROGRAM Teste;
FUNCTION XXX(A : WORD) : WORD;
BEGIN
IF a = 0 THEN
BEGIN
XXX : = 1;
ELSE
XXX : =A * XXX(A - 1);
END;
END;
BEGIN
WRITE(XXX(5));
END.
b)
PROGRAM Teste;
PROCEDURE Recursão(a : BYTE);
BEGIN
a : = a - 1;
IF a > 0 THEN
BEGIN
Recursão(a);
END;
WRITE(a);
END;
BEGIN
Recursão(5);
END.
c)
PROGRAM Teste;
PROCEDURE Recursão(VAR a: BYTE);
BEGIN
a : = a - 1;
IF a > 0 THEN
BEGIN
Recursão(a);
END;
WRITE(a);
END;
BEGIN
Recursão(5);
END.
Prof. Giuliano Prado M. Giglio
21
Curso de Análise de Sistemas
Linguagem de Programação I
CAPÍTULO 4
Organizações Básicas de Arquivos
4.1. Conceitos
Arquivo: coleção de registros lógicos, cada um deles representando um objeto ou
entidade
Registro lógico (registro) : seqüência de itens, cada item sendo chamado de campo
ou atributo, correspondendo a uma característica do objeto representado. Os
registros podem ser de tamanho fixo ou de tamanho variável.
Campo: item de dados do registro, com um nome e um tipo associados
Bloco: unidade de armazenamento do arquivo em disco, também denominado registro
físico. Um registro físico normalmente é composto por vários registros lógicos. Cada
bloco armazena um número inteiro de registros.
Chave: é uma seqüência de um ou mais campos em um arquivo
Chave primária: é uma chave que apresenta um valor diferente para cada registro do
arquivo. É usada para identificar, de forma única, cada registro.
Chave secundaria: é uma chave que pode possuir o mesmo valor em registro distintos.
É normalmente usada para identificar um conjunto de registros.
Chave de acesso: é uma chave usada para identificar o(s) registro(s) desejado(s) em
uma operação de acesso ao arquivo.
4.2. Estruturas de Arquivos
4.2.1 Arquivo seqüencial
Nos arquivos seqüenciais a ordem lógica e física dos registros armazenados é a mesma.
Os registros podem estar dispostos seguindo a seqüência determinada por uma chave primária
(chamada chave de ordenação), ou podem estar dispostos aleatoriamente.
Prof. Giuliano Prado M. Giglio
22
Curso de Análise de Sistemas
#
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Linguagem de Programação I
Numero
1000
1050
1075
1100
1150
1180
1250
1270
1300
1325
1340
1360
1400
1450
Nome
ADEMAR
AFONSO
CARLOS
CESAR
DARCI
EBER
ENIO
FLAVIO
IVAN
MIGUEL
MARIA
RAMON
SANDRA
TATIANA
Idade
25
27
28
30
23
22
27
28
30
34
35
32
29
30
Salario
600
700
500
1000
1500
2000
750
600
700
1000
1500
2000
700
500
Acesso a um registro
Podemos considerar dois tipos de acesso: seqüencial ou aleatório.
O acesso seqüencial consiste em acessar os registros na ordem em que estão
armazenados, ou seja, o registro obtido é sempre o posterior ao último acessado. Como os
registros são armazenados em sucessão contínua, acessar o registro “n” de um arquivo requer a
leitura dos “n-1” registros anteriores.
O acesso aleatório se caracteriza pela utilização de um “argumento de pesquisa” (chave
de acesso), que indica qual o registro desejado. Neste caso, a ordem em que os registros são
acessados pode ser diferente da ordem em que eles estão armazenados fisicamente. Se o arquivo
está ordenado e a chave de acesso coincide com a chave de ordenação, podemos utilizar a
pesquisa binária. Caso contrário, deve ser realizada uma pesquisa seqüencial no arquivo.
Inserção de um registro
Se o arquivo não está ordenado, o registro pode ser simplesmente inserido após o último
registro armazenado.
Se o arquivo está ordenado, normalmente é adotado o seguinte procedimento:
Prof. Giuliano Prado M. Giglio
23
Curso de Análise de Sistemas
Linguagem de Programação I
Dado um arquivo base B, é construído um arquivo de transações T, que contem os
registros a serem inseridos, ordenado pela mesma chave que o arquivo B. Os arquivos B e T são
então intercalados, gerando o arquivo A, que é a versão atualizada de B.
Arquivo B
#
Num
0
1000
1
1050
2
1075
3
1100
4
1150
5
1180
6
1250
7
1270
8
1300
9
1325
10 1340
11 1360
12 1400
13 1450
Nome
ADEMAR
AFONSO
CARLOS
CESAR
DARCI
EBER
ENIO
FLAVIO
IVAN
MIGUEL
MARIA
RAMON
SANDRA
TATIANA
Idade
25
27
28
30
23
22
27
28
30
34
35
32
29
30
Arquivo
# Num
0 1070
1 1120
2 1280
3 1310
4 1420
T
Nome
ANGELA
CLAUDIA
IARA
LUIS
SONIA
Idade
25
27
28
30
23
Arquivo A
# Num Nome
0 1000 ADEMAR
1 1050 AFONSO
2 1070 ANGELA
3 1075 CARLOS
4 1100 CESAR
5 1120 CLAUDIA
6 1150 DARCI
7 1180 EBER
8 1250 ENIO
9 1270 FLAVIO
10 1280 IARA
11 1300 IVAN
12 1310 LUIS
13 1325 MIGUEL
14 1340 MARIA
15 1360 RAMON
16 1400 SANDRA
17 1420 SONIA
18 1450 TATIANA
Idade
25
27
25
28
30
27
23
22
27
28
28
30
30
34
35
32
29
23
30
Exclusão de um registro
Normalmente é implementada como a inserção, com a criação de um arquivo de
transações que contém os registros a serem excluídos, que é processado posteriormente.
Pode ainda ser implementada através de um campo adicional no arquivo que indique o
estado (status) de cada registro. Na exclusão, o valor deste campo seria alterado para “excluído”.
Posteriormente, é feita a leitura seqüencial de todos os registros, sendo que os registros que não
estiverem marcados como “excluídos” são copiados para um novo arquivo.
Alteração de um registro
Consiste na modificação do valor de um ou mais atributos de um registro. O registro
deve ser localizado, lido e os campos alterados, sendo gravado novamente, na mesma posição.
A alteração é feita sem problemas, desde que ela não altere o tamanho do registro nem
modifique o valor de um campo usado como chave de ordenação.
Prof. Giuliano Prado M. Giglio
24
Curso de Análise de Sistemas
Linguagem de Programação I
4.2.2. Arquivo seqüencial-indexado
Quando o volume de acessos aleatórios em um arquivo seqüencial torna-se muito grande,
é necessário utilizar uma estrutura de acesso que ofereça maior eficiência na localização de um
registro com base em uma chave de acesso.
O arquivo seqüencial-indexado é um arquivo seqüencial acrescido de uma estrutura de
acesso (índice). Um índice é formado por uma coleção de pares, associando um valor da chave de
acesso a um endereço de registro. Deve existir um índice específico para cada chave de acesso.
Índice Primário
# Num
End.
0 1300
0
1 1605
3
2
**
6
** Maior valor
que a chave pode
assumir
Índice Secundário
# Num
End.
0 1070 0
1 1200 3
2 1300 6
3 1430 9
4 1520 12
5 1605 15
6 1710 18
7 1745 21
8
**
24
** Maior valor que a
chave pode assumir
Arquivo
#
Num
0
1000
1
1050
2
1070
3
1075
4
1100
5
1200
6
1250
7
1275
8
1300
9
1310
10 1400
11 1430
12 1470
13 1510
14 1520
15 1530
16 1590
17 1605
18 1650
19 1700
20 1710
21 1730
22 1740
23 1745
24 1800
25 1905
26 2010
Nome
Idade
ADEMAR
25
AFONSO
27
ANGELA
25
CARLOS
28
CESAR
30
CLAUDIA
25
CRISTIE
26
DARCI
29
DIOGO
25
ELBER
27
EDISON
25
EDMUNDO 28
ENIO
30
FLAVIO
25
GENARO
26
GERSON
29
HELENA
25
IARA
27
IVAN
25
LUIS
28
MARIA
30
MIGUEL
25
RAMON
26
SANDRA
29
SONIA
32
TATIANA
34
WILSON
20
4.2.3. Arquivo indexado
O arquivo indexado é aquele em que os registros são acessados através de um ou mais
índices, não havendo qualquer compromisso com a ordem em que os registros estão armazenados.
Prof. Giuliano Prado M. Giglio
25
Curso de Análise de Sistemas
Linguagem de Programação I
Podem existir tantos índices quantas forem as chaves de acesso aos registros. As
entradas no índice são ordenadas pelo valor das chaves de acesso, sendo cada uma delas
constituída por um par (chave do registro, endereço do registro).
Índice
Num
1000
1070
1075
1200
1250
1310
1400
1470
1510
1520
1530
1590
1605
1650
1700
1710
1745
1800
1905
2010
End.
1
2
12
3
8
10
4
16
5
9
14
6
11
7
13
17
15
18
19
0
Arquivo
#
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Num
2010
1000
1070
1200
1400
1510
1590
1650
1250
1520
1310
1605
1075
1700
1530
1745
1470
1710
1800
1905
Nome
WILSON
ADEMAR
ANGELA
CLAUDIA
EDISON
FLAVIO
HELENA
IVAN
CRISTIE
GENARO
ELBER
IARA
CARLOS
LUIS
GERSON
SANDRA
ENIO
MARIA
SONIA
TATIANA
Idade
26
32
28
25
22
30
26
32
25
24
26
32
28
32
26
32
25
24
22
30
Salário
1000
250
300
750
1500
250
300
750
1500
750
250
300
750
1500
400
400
750
400
750
400
4.2.4 Arquivo direto
A idéia básica de um arquivo direto é o armazenamento dos registros em endereços
determinados com base no valor de uma chave primária, de modo que se tenha acesso rápido aos
registros especificados por argumentos de pesquisa, sem que haja necessidade de percorrer uma
estrutura de índice.
Em um arquivo direto ao invés de um índice é usada uma função que calcula um endereço
de registro a partir do argumento de pesquisa.
Prof. Giuliano Prado M. Giglio
26
Curso de Análise de Sistemas
C=’CLAUDIA’
E=F(C)
Linguagem de Programação I
E=3
Arquivo
#
Num
0
2010
1
2
1070
3
1200
4
5
6
7
8
9
10
11
12
13
14
15
...
Nome
WILSON
Idade
26
Salário
1000
ANGELA
CLAUDIA
28
25
300
750
1300
DIOGO
24
400
1650
1730
1250
IVAN
MIGUEL
CRISTIE
32
28
25
750
400
1500
1050
AFONSO
30
1500
1800
SONIA
22
750
O principal problema associado com os arquivos diretos é o da determinação de uma
função F, que transforme o valor C da chave de um registro no endereço E, que lhe corresponde
no arquivo.
Geralmente são usadas “funções probabilísticas” que geram, para cada valor da chave,
um endereço “tão único quanto possível”, podendo gerar, para valores distintos da chave, o mesmo
endereço. Este fato é denominado “colisão”, e devem ser estabelecidos procedimentos para
tratá-lo.
4.3. Arquivos em Pascal
4.3.1. Tipo Text
Os arquivos do tipo Text (text files) são utilizados para armazenamento de strings em
disco. São arquivos que só permitem o acesso seqüencial, sendo que as inclusões são feitas
sempre no final do arquivo (append).
4.3.1. Tipo File
Os arquivos do tipo File (typed files) são utilizados para armazenamento de estruturas
de dados genéricas. São também denominados “file of records” ou arquivos de registros, já que
Prof. Giuliano Prado M. Giglio
27
Curso de Análise de Sistemas
Linguagem de Programação I
usualmente a estrutura a ser armazenada é do tipo “record” (registro). Estão enquadrados na
organização seqüencial, porém permitem acesso aleatório, através do número do registro.
4.4. Rotinas de arquivos
assign(var_arq, nome_arq)
Procedure que associa o nome do arquivo em disco (nome_arq) à variável var_arq (do
tipo Text ou File) declarada no programa. Deve ser a primeira rotina a ser usada na manipulação
de arquivos em disco.
rewrite(var_arq)
Procedure que cria e abre um novo arquivo em disco, associado à variável var_arq.
Arquivos do tipo Text são abertos apenas para escrita. Arquivos do tipo File são posicionados no
registro #0.
reset(var_arq)
Procedure que abre um arquivo já existente, associado à variável var_arq. Arquivos do
tipo Text são abertos apenas para leitura. Arquivos do tipo File são posicionados no registro #0.
append(var_arqtxt)
Procedure utilizada com arquivos do tipo Text. Abre um arquivo já existente,
posicionando o ponteiro no final do arquivo. O arquivo está aberto apenas para escrita.
close(var_arq)
Procedure que fecha um arquivo externo, gravando antes as informações do buffer.
eof(var_arq)
Função lógica que retorna True se o ponteiro estiver no fim do arquivo.
eoln(var_arq)
Função lógica que retorna True se o ponteiro estiver no fim de uma linha (CR+LF) ou no
fim do arquivo.
Prof. Giuliano Prado M. Giglio
28
Curso de Análise de Sistemas
Linguagem de Programação I
erase(var_arq)
Procedure que remove um arquivo do disco.
FilePos(var_arq)
Função inteira que retorna a posição do ponteiro no arquivo associado a var_arq. O
primeiro registro está na posição #0. Não é válida para arquivos do tipo Text.
FileSize(var_arq)
Função inteira que retorna a posição do último registro no arquivo associado a var_arq.
O número de registros no arquivo é igual a FileSize+1. Não é válida para arquivos do tipo Text.
flush(var_arqtxt)
Procedure que força a gravação dos dados contidos no buffer de um arquivo do tipo
Text.
seek(var_arq, num)
Procedure que posiciona o ponteiro do arquivo var_arq no registro indicado por num. O
primeiro registro está na posição #0. Não é válida para arquivos do tipo Text.
read(var_arq, var)
Procedure utilizada para leitura de dados a partir do arquivo indicado por var_arq. Os
dados lidos são armazenados na variável var (geralmente do tipo record). Se var_arq não for
indicada, os dados são lidos a partir do dispositivo padrão de entrada (teclado). Após a leitura o
ponteiro do arquivo avança para a posição seguinte.
readLn(var_arq, var)
Semelhante a Read, porém os dados são lidos até ser encontrada uma seqüência de fimde-linha (CR+LF).
write(var_arq, var)
Procedure utilizada para escrever os dados armazenados na variável var (geralmente do
tipo record) no arquivo indicado por var_arq. Os dados são escritos na posição atual do arquivo.
Prof. Giuliano Prado M. Giglio
29
Curso de Análise de Sistemas
Linguagem de Programação I
Se var_arq não for indicada, os dados são escritos no dispositivo padrão de saída (monitor de
vídeo). Após a leitura o ponteiro do arquivo avança para a posição seguinte.
writeLn(var_arq, var)
Semelhante a Write, porém é escrita uma seqüência de fim-de-linha (CR+LF) após
escrever a variável.
4.5. Exemplos de programas
Text Files
Criação de um arquivo Texto:
program Criar_Txt;
var
ArqTxt : Text;
S : string;
i : integer;
begin
assign(ArqTxt,'Text01.txt');
rewrite(ArqTxt);
S := 'Linha de tamanho variavel';
for i := 1 to 13 do begin
writeln(ArqTxt, 'Linha #', i,' ',copy(S,1,i*2));
end;
close(ArqTxt);
end.
Leitura de um arquivo Texto:
program Ler_Txt;
var
ArqTxt : Text;
S : string;
begin
assign(ArqTxt,'Texto1.txt');
reset(ArqTxt);
while not eof(ArqTxt) do begin
readln(ArqTxt, S);
writeln(S);
end;
close(ArqTxt);
end.
Inserção de linhas em um arquivo Texto:
program Inserir_Txt;
var
ArqTxt : Text;
S : string;
i : integer;
begin
assign(ArqTxt,'Texto1.txt');
append(ArqTxt);
Prof. Giuliano Prado M. Giglio
30
Curso de Análise de Sistemas
Linguagem de Programação I
S := 'Linha acrescentada #';
for i := 1 to 5 do begin
writeln(ArqTxt, S, i);
end;
close(ArqTxt);
end.
Type Files
Criação de um arquivo de dados a partir de um arquivo texto:
program Cria_Dat;
type
reg_func = record
status : char;
codigo : string[4];
nome
: string[10];
idade
: integer;
salario : real;
end;
var
ArqTxt : Text;
ArqFunc : file of reg_func;
Linha : string;
func : reg_func;
code : integer;
begin
assign(ArqTxt,'Func.txt');
assign(ArqFunc, 'Func.dat');
reset(ArqTxt);
rewrite(ArqFunc);
while not eof(ArqTxt) do begin
readln(ArqTxt,linha);
func.status := ' ';
func.codigo := copy(linha,1,4);
func.nome
:= copy(linha,5,10);
val(copy(linha,15,2), func.idade, code);
val(copy(linha,17,7), func.salario, code);
write(ArqFunc, func);
end;
close(ArqTxt);
close(ArqFunc);
end.
Leitura de um arquivo de dados, com exibição na tela:
program Ler_Dat;
type
reg_func = record
status : char;
codigo : string[4];
nome
: string[10];
idade
: integer;
salario : real;
end;
var
ArqFunc : file of reg_func;
func : reg_func;
pos : longint;
begin
Prof. Giuliano Prado M. Giglio
31
Curso de Análise de Sistemas
assign(ArqFunc, 'Func.dat');
reset(ArqFunc);
while not eof(ArqFunc) do begin
pos := filepos(ArqFunc);
read(ArqFunc, func);
with func do
writeln('#',pos, ' ',status,'
',salario:7:2);
end;
close(ArqFunc);
end.
Linguagem de Programação I
',codigo,'
',nome,'
',idade,'
Inserção em um arquivo de dados, com uso de um arquivo de transações:
program Insere_Dat;
type
reg_func = record
status : char;
codigo : string[4];
nome
: string[10];
idade
: integer;
salario : real;
end;
var
ArqFunc, ArqIns, ArqNovo : file of reg_func;
Func, FuncIns : reg_func;
procedure Ler_Func;
begin
if not eof(ArqFunc)
then read(ArqFunc,Func)
else Func.Codigo := '9999';
end;
procedure Ler_FuncIns;
begin
if not eof(ArqIns)
then read(ArqIns,FuncIns)
else FuncIns.Codigo := '9999';
end;
function Fim : boolean;
begin
Fim := (Func.Codigo='9999') and (FuncIns.Codigo='9999');
end;
begin
assign(ArqFunc,'Func.dat');
assign(ArqIns, 'FuncIns.dat');
assign(ArqNovo, 'FuncNovo.dat');
reset(ArqFunc);
reset(ArqIns);
rewrite(ArqNovo);
Ler_Func;
Ler_FuncIns;
while not Fim do begin
while (Func.Codigo < FuncIns.Codigo) do begin
write(ArqNovo,Func);
Ler_Func;
end;
while (FuncIns.Codigo < Func.Codigo) do begin
write(ArqNovo,FuncIns);
Prof. Giuliano Prado M. Giglio
32
Curso de Análise de Sistemas
Linguagem de Programação I
Ler_FuncIns;
end;
end;
close(ArqIns);
close(ArqFunc);
close(ArqNovo);
end.
Exclusão de um registro em um arquivo de dados:
program Exclui_Dat;
type
reg_func = record
status : char;
codigo : string[4];
nome
: string[10];
idade
: integer;
salario : real;
end;
var
ArqFunc : file of reg_func;
Func : reg_func;
ultimo, nReg : longint;
begin
assign(ArqFunc, 'Func.dat');
reset(ArqFunc);
if not eof(ArqFunc) then begin
ultimo := filesize(ArqFunc);
writeln('Arquivo possui ',ultimo+1,' registros.');
write('Informe qual registro deseja excluir [0..',ultimo,'] :
');
readln(nReg);
if (nReg >= 0) and (nReg <= ultimo) then begin
seek(ArqFunc, nReg);
read(ArqFunc, Func);
writeln('Excluindo
funcionario
',func.codigo,'',func.nome,'...');
Func.Status := '*';
seek(ArqFunc, nReg);
write(ArqFunc, Func);
end else writeln('Registro fora da faixa valida!');
end;
close(ArqFunc);
end.
Prof. Giuliano Prado M. Giglio
33
Curso de Análise de Sistemas
Linguagem de Programação I
CAPÍTULO 5
MÉTODOS DE PESQUISA
5.1. Conceitos
A pesquisa (ou busca) de chaves em uma estrutura de dados é uma operação que se
encontra praticamente em todos os sistemas. A escolha da técnica de pesquisa a ser utilizada é
muito importante, pois vai influenciar diretamente o desempenho do sistema.
Os dois tipos de pesquisa mais utilizados em estruturas estáticas são a pesquisa
seqüencial e a pesquisa binária.
Pesquisa seqüencial
Consiste em percorrer a estrutura do início ao fim, ou até a posição onde se encontra a
chave procurada.
Considerando:
N : número de elementos em um vetor
V : vetor com N elementos
Chave : valor sendo pesquisado
Void PesquisaSequencial(int V[], int N, int Chave)
{
int ind;
ind = 0;
while (ind < N) and (V[ind] != Chave)
ind = ind + 1;
if (ind > N)
printf(“Chave não encontrada”)
else printf (“Chave encontrada na posicao %d”, ind);
}
A pesquisa pode ser agilizada incluindo um elemento após a última posição do vetor com
a chave procurada. Assim precisamos apenas de uma comparação durante o laço.
Considerando:
N : número de elementos originais em um vetor
V : vetor com N+1 elementos
Chave : valor sendo pesquisado
Prof. Giuliano Prado M. Giglio
34
Curso de Análise de Sistemas
Linguagem de Programação I
void PesquisaSequencialRapida(int V[], int N+1, int Chave)
{
int ind;
V[N+1] = Chave;
ind = 0;
while (V[ind] != Chave)
ind = ind + 1;
if (ind = N+1)
printf(“Chave não encontrada”)
else printf (“Chave encontrada na posicao %d”, ind);
}
Se os elementos estiverem ordenados no vetor, o algoritmo pode ser modificado.
Considerando:
N : número de elementos originais em um vetor
V : vetor com N+1 elementos
Chave : valor sendo pesquisado
MaxValor : Maior valor que a chave pode assumir;
Void PesquisaSequencialOrdenada(int V[], int N+1, int Chave)
{
int ind;
V[N+1] = MaxValor;
ind = 0;
while (V[ind] < Chave)
ind = ind + 1;
if (V[ind] > Chave)
printf(“Chave não encontrada”)
else printf (“Chave encontrada na posicao %d”, ind);
}
5.1.2 Pesquisa binária
Esta é a técnica mais utilizada para pesquisa em um conjunto ordenado de valores.
Consiste em obter o elemento do meio da estrutura e comparar este valor com a chave procurada.
Como resultado desta comparação podemos ter:
Se Chave é menor que o valor do meio, ela deve ser procurada no intervalo entre o
início do vetor até o meio.
Se Chave é maior que o valor do meio, ela deve ser procurada no intervalo entre o
meio do vetor e seu final.
Se Chave é igual ao valor do meio, a pesquisa é encerrada.
Considerando:
N : número de elementos em um vetor
V : vetor com N elementos
Chave : valor sendo pesquisado
Prof. Giuliano Prado M. Giglio
35
Curso de Análise de Sistemas
Linguagem de Programação I
Ini : limite inicial para pesquisa
Fim : limite final para pesquisa
Meio : posicao no meio do vetor
void PesquisaBinaria(int V[], int N, int Chave)
{
int ini, fim, meio;
ini = 0;
fim = N-1;
While (ini <= fim)
{
meio := (ini+fim)/2) + 1;
if (Chave < V[meio])
fim := meio – 1;
else
if (Chave > V[meio])
ini := meio + 1
else
ini := fim + 1;
}
if (Chave != V[meio])
printf(“Chave não encontrada”)
else printf (“Chave encontrada na posicao %d”, meio);
}
Prof. Giuliano Prado M. Giglio
36
Curso de Análise de Sistemas
Linguagem de Programação I
CAPÍTULO 6
MÉTODOS DE CLASSIFICAÇÃO
6.1. Conceitos
Classificação ou ordenação de dados constitui uma das tarefas mais freqüentes e
importante em processamento de dados.
Classificação de dados é o processo pelo qual é determinada a ordem em que devem se
apresentar as entradas de uma tabela ou os registros de um arquivo, baseado no valor de um ou
mais campos. Estes campos são chamados de chaves de classificação (ou ordenação).
Existem basicamente dois tipos de ordenação:
Interna: onde a ordenação é realizada totalmente na memória principal;
Externa: onde é utilizada a memória secundária, geralmente caracterizada por um
disco.
Existem diversos métodos de classificação interna: por inserção, por seleção, por troca,
por distribuição e por intercalação.
6.2. Classificação com Inserção Direta (Insert Sort)
Consiste em realizar a ordenação da lista de valores pela inserção de cada um dos
elementos em sua posição correta dentro da lista, segundo a chave de ordenação. É usado apenas
com pequenos conjuntos de dados.
Neste método, o vetor V é dividido em dois segmentos. Inicialmente o primeiro
segmento possui apenas o primeiro elemento, estando portanto classificado, enquanto o segundo
segmento contem os elementos V[2] a V[N]. Através de iterações sucessivas é feita a inserção de
todos os elementos do segundo segmento no primeiro, de forma ordenada. Após cada inserção, o
primeiro segmento possuirá mais um elemento e o segundo, menos um.
Considerando:
N : número de elementos no vetor
V : vetor com N posições (1 a N) contendo as chaves
i : Posição do elemento a ser retirado do 2o. segmento
Prof. Giuliano Prado M. Giglio
37
Curso de Análise de Sistemas
Linguagem de Programação I
J : Limite do 1o. segmento em determinado instante
X : Chave do 2o. segmento a ser inserida no 1o.
void OrdenacaoInsercao(int V[],int N)
{
int i, j, X;
for (i= 1; i < N; i++)
{
X = V[i];
j = i;
while ((X < V[j-1]) && (j > 0))
{
V[j] = V[j-1];
j = j -1;
}
V[j] = X;
}
}
6.3. Classificação por Seleção
Consiste em fazer seleções sucessivas da menor chave de ordenação e colocar o
elemento correspondente na sua posição definitiva dentro da lista.
Considerando:
N : número de elementos do vetor
V : vetor com N posições (1 a N) contendo as chaves
i : limite inferior do vetor em dado instante
PosMenor : posição da menor chave
V[PosMenor} : valor da menor chave selecionada em uma passada
J : variável auxiliar
Aux: variável auxiliar para realizar a troca
void OrdenacaoSelecao(int V[],int N)
{
int i, j, PosMenor, aux;
for (i= 0; i < N –1; i++)
{
PosMenor = i;
for (j = i+1; j < N; j++)
{
if (V[j] < V[PosMenor])
PosMenor = j;
}
Aux = V[PosMenor];
V[PosMenor] = V[i];
V[i] = Aux;
}
}
Prof. Giuliano Prado M. Giglio
38
Curso de Análise de Sistemas
Linguagem de Programação I
6.4. Classificação por Troca (BubbleSort)
Também conhecido como “método da bolha”, consiste na comparação de pares de chaves
de ordenação, trocando os elementos correspondentes, caso estejam fora de ordem.
Considerando:
N : número de elementos do vetor
V : vetor com N posições (1 a N) contendo as chaves
i : limite inferior do vetor em dado instante
j : variável auxiliar
Procedure BublleSort(int V[],int N)
{
int i,j, Aux;
for (i = 1; i < N; i++)
for (j = i+1; j < N; j++)
{
if (V[i] > V[j])
{
Aux = V[i];
V[i] = V[j];
V[j] = Aux;
}
}
}
6.5. Classificação Rápida por troca (QuickSort)
Em 1962, Hoare desenvolveu um dos algoritmos mais eficientes de ordenação. O
algoritmo particiona o vetor a ser ordenado em dois subconjuntos, um à esquerda e outro à
direita, de tal forma que todo elemento do subconjunto à esquerda seja menor que qualquer
elemento do subconjunto à direita. Cada subconjunto é reparticionado segundo este mesmo
critério, e assim sucessivamente. Isto nos leva a uma solução recursiva.
O particionamento ocorre a partir de um elemento que será o pivô. É a comparação entre
este pivô e as demais chaves que determina o correto posicionamento dos elementos para um novo
particionamento. Neste exemplo, o pivô será o elemento central de cada partição.
Considerando:
V : vetor com N posições (1 a N) contendo as chaves
PosEsquerda : posição inicial da partição
PosDireita : posição final da partição
Pivo : elemento do meio da partição
Prof. Giuliano Prado M. Giglio
39
Curso de Análise de Sistemas
Linguagem de Programação I
void QuickSort (int V[], int N, int PosEsquerda, int PosDireita)
{
int Esq, Dir, Pivo;
Esq = PosEsquerda;
Dir = PosDireita;
Pivo := V[ROUND(float)((PosEsquerda+PosDireita)/2)];
while (Esq <= Dir)
{
while V[Esq] < Pivo { Esq := Esq + 1 };
while V[Dir] > Pivo { Dir := Dir – 1 };
if (Esq <= Dir)
{
Aux = V[Esq];
V[Esq] = V[Dir];
V[Dir] = Aux;
Esq = Esq + 1;
Dir = Dir – 1;
}
}
if (PosEsquerda < Dir) QuickSort(PosEsquerda, Dir);
if (PosDireita > Esq) QuickSort(Esq, PosDireita);
}
Prof. Giuliano Prado M. Giglio
40