Algoritmos II Apostila

Prévia do material em texto

ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 1 de 35 
 
 
Índice 
 
Capítulo I ....................................................................................................................................... 2 
1 – Estruturas de Dados homogêneas: Vetores. ......................................................................... 2 
1.1 – Definição: ......................................................................................................................................................... 2 
1.2 – O tipo vetor: ..................................................................................................................................................... 2 
1.3 – Usando vetores: ................................................................................................................................................ 3 
1.4 – Exercícios ......................................................................................................................................................... 5 
Capítulo II ...................................................................................................................................... 6 
2 – Estruturas de Dados homogêneas: Matrizes. ....................................................................... 6 
2.1 – Definição: ......................................................................................................................................................... 6 
2.2 – O tipo matriz: ................................................................................................................................................... 6 
2.3 – Usando matrizes: .............................................................................................................................................. 7 
2.4 – Exercícios ......................................................................................................................................................... 9 
Capítulo III .................................................................................................................................. 10 
3 – Estruturas de Dados heterogêneas: Registros. ................................................................... 10 
3.1 – Definição: ....................................................................................................................................................... 10 
3.2 – O tipo registro: ............................................................................................................................................... 10 
3.3 – Usando registros: ............................................................................................................................................ 10 
3.4 – Usando registros como elementos de vetores (Tabelas):................................................................................ 13 
3.5 – Exercícios ....................................................................................................................................................... 14 
Capítulo IV ................................................................................................................................... 15 
4 – Métodos de Pesquisa. ............................................................................................................ 15 
4.1 – Pesquisa sequêncial: ....................................................................................................................................... 15 
4.2 – Pesquisa binária: ............................................................................................................................................ 16 
4.3 – Pesquisa conclusões: ...................................................................................................................................... 18 
4.5 – Exercícios ....................................................................................................................................................... 18 
Capítulo V .................................................................................................................................... 19 
5 – Métodos de Ordenaçaão. ...................................................................................................... 19 
5.1 – Ordenação: ..................................................................................................................................................... 19 
 5.2 – Ordenação por inserção .............................................................................................................. 19 
 5.3 – Ordenação por troca .................................................................................................................. 21 
 5.4 – Ordenação por seleção ............................................................................................................... 21 
5.5 – Exercícios ....................................................................................................................................................... 25 
Capítulo VI ................................................................................................................................... 26 
6 – Arquivos. ................................................................................................................................ 26 
6.1 – Definição: ....................................................................................................................................................... 26 
6.2 – Declarando um arquivo: ................................................................................................................................. 26 
6.3 – Usando Arquivos:........................................................................................................................................... 27 
6.3.1 – Novos comandos: .................................................................................................................................... 27 
6.3.2 – Operações básicas: .................................................................................................................................. 28 
6.3.3 – Organização sequêncial: .......................................................................................................................... 28 
6.3.4 – Organização direta: ................................................................................................................................. 31 
6.4 – Exercícios ....................................................................................................................................................... 34 
Bibliografia .................................................................................................................................. 35 
 
 
 
 
 
 
 
 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 2 de 35 
 
 
Capítulo I 
 
1 – Estruturas de Dados homogêneas: Vetores. 
 
1.1 – Definição: 
 
Um vetor é uma estrutura de dados homogênea, pois é formado por uma única variável, 
com um único nome, dividida em vários pedaços, denominados de elementos do vetor, onde 
podemos guardar valores de mesmo tipo e mesmo significado. 
 
Exemplo 1: Um vetor de notas só contém notas. Não podemos guardar nos elementos de um 
único vetor, notas e salários, pois apesar de terem o mesmo tipo, real, possuem significados 
diferentes 
 
 Cada elemento de um vetor é identificado por um número: inteiro e seqüencial. Para o 
primeiro elemento podemos escolher qualquer número, podendo ser até um número negativo. 
Para os elementos seguintes somamos sempre um ao número do elemento anterior. 
 Um vetorpode ser chamado de variável composta homogênea ou agregado homogêneo. 
 
Exemplo 2: Representamos graficamente um vetor como abaixo, onde “NOMES” é uma 
variável do tipo vetor: 
 
NOMES 
João Ana Luis Vanda ................ José Maria elementos 
 1 2 3 4 29 30 índices 
 
1.2 – O tipo vetor: 
 
 Até agora temos criado variáveis simples, cada variável guarda um só valor, com tipos 
básicos como: inteiro, real, caracter e lógico. Uma variável do tipo vetor pode ser definida com 
várias formatações diferentes, pode variar o número e o tipo dos elementos, por isso o tipo vetor 
tem de ser definido pelo programador como veremos abaixo: 
 
 Formato: 
 
 Tipo “identificador” = vetor [i1:in] “tipos”; 
 
 Onde: i1 é o número do primeiro elemento do vetor ou primeiro índice. 
 i2 é o número do último elemento do vetor ou último índice. 
tipos é um único tipo que caracteriza o conteúdo de cada elemento do vetor, pode 
ser um tipo: básico, vetor ou registro,como veremos mais adiante. 
 
Ao especificarmos um tipo vetor, estamos apenas criando um molde ou modelo. Para 
que a variável vetor passe a existir temos que criá-la usando este molde. 
 
Exemplo 3: 
 Tipo x = vetor [1 : 30] caracter; 
 x: NOMES; 
 
 O número de elementos de um vetor é dado pela expressão: in - i1 + 1. Os elementos de 
um vetor são numerados a partir de i1, somando sempre 1 até in. 
 
Exemplo 4: 
 Para o vetor “NOMES”, o número de elementos é: in - i1 + 1, onde in = 30 e i1 = 1 
 Temos: 30 - 1 + 1 = 30 elementos 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 3 de 35 
 
 
1.3 – Usando vetores: 
 
 Para melhor entendermos o funcionamento de um vetor faremos uma analogia com um 
armário que possua várias gavetas numeradas de 1 a n. Para termos acesso a um objeto que esteja 
em uma gaveta de um armário temos que identificar o armário (nome do vetor) e a gaveta 
(número do elemento) onde guardamos o objeto. Para termos acesso ao conteúdo de um 
elemento de um vetor precisamos do nome do vetor e do número do elemento que queremos 
acessar. Desta forma um elemento de um vetor funciona como uma variável simples. 
 
Exemplo 5: 
 
 Seja o vetor do Exemplo 2: 
 
NOMES 
João Ana Luis Vanda ................ José Maria 
 1 2 3 4 29 30 
 
 Após serem executados os comandos abaixo: 
 
 NOMES[3]  “Rui”; 
 
 Podemos usar uma variável do tipo inteiro como índice; 
 
 I  4; 
 NOMES[I]  “Lu”; 
 
 Podemos atribuir valor para um elemento de um vetor através da leitura: 
 
 I 1; 
 Leia(NOMES[I]); {digitamos o valor “Carla”} 
 
 Temos: 
 
NOMES 
Carla Ana Rui Lu ................ José Maria 
 1 2 3 4 29 30 
 
 Ao executarmos o comando: Imprima (NOMES[4]); - será impresso o “Lu”. 
 
Exemplo 6: 
 
 Usando um vetor com o comando “Para”: 
 
 Algoritmo Vetor: 
 Tipo v = vetor[1:5] inteiro; 
 v: NUM; 
 Inicio 
 Para I de 1 até 5 faça; 
 NUM[I]  I; 
 Fim-Para; 
 Fim; 
 
 Temos ao fim da execução: 
 
 NUM 
1 2 3 4 5 
 1 2 3 4 5 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 4 de 35 
 
Exemplo 7: 
 Quando precisamos processar um conjunto de dados lidos mais de uma vez, vemos que as 
variáveis simples não são suficientes. Temos que usar variáveis do tipo vetor, como no algoritmo 
abaixo: 
 
Temos o enunciado: 
Faça um algoritmo que lê 100 notas e imprime as notas maiores que a média. 
 
Sem usar vetor, conseguiremos só calcular a média, de uma maneira simples: 
 
Algoritmo Média; 
 Real: NOTA, SOMA, MEDIA; 
 Inteiro: I; 
Inicio 
 Para I de 1 até 100 faça 
 Leia(NOTA); 
 SOMA  SOMA + NOTA; 
 Fim-Para; 
 MEDIA SOMA / 100; 
 Imprima(MEDIA); 
FIM; 
 
Para podermos comparar cada nota com a média temos que guardar as notas lidas para 
fazer as comparações após o cálculo da média: 
 
Algoritmo Notas_Maiores_que_Média; 
 Tipo v = vetor[1 : 100] real; 
 v: NOTAS; 
 Real: SOMA, MEDIA; 
 Inteiro: I; 
Inicio 
 Para I de 1 até 100 faça 
 Leia(NOTAS[I]); {cada nota lida fica guardada em uma posição do vetor} 
 SOMA  SOMA + NOTAS[I]; 
 Fim-Para; 
 MEDIA SOMA / 100; 
 Imprima(MEDIA); 
 Para I de 1 até 100 faça 
 Se NOTAS[I] > MEDIA 
 Então Imprima(NOTAS[I]); 
 Fim-Para; 
FIM; 
 
 
Como vimos acima uma das utilizações mais comuns de um vetor é quando precisamos 
processar mais de uma vez um conjunto de dados. Para não perdê-los, guardamos em um vetor 
na memória. 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 5 de 35 
 
 
1.4 – Exercícios 
 
1 – Faça um algoritmo que preencha totalmente um vetor com 10 números reais digitados pelo 
usuário. 
 
2 – Faça um algoritmo que preencha totalmente um vetor com 10 números reais digitados pelo 
usuário e em seguida imprima a soma dos valores contidos em cada elemento do vetor. 
 
3 – Faça um algoritmo que preencha totalmente um vetor com 10 números reais digitados pelo 
usuário e em seguida multiplique por 3 cada elemento do vetor e imprima o vetor com os novos 
valores. 
 
4 – Faça um algoritmo que preencha totalmente um vetor com 10 números reais digitados pelo 
usuário e em seguida preencha um segundo vetor com os valores do primeiro na ordem inversa, 
do último para o primeiro. 
 
5 – Faça um algoritmo que preencha totalmente um vetor com 10 números reais digitados pelo 
usuário e em seguida imprima os valores que estiverem nos elementos de índice impar, do maior 
para o menor. 
 
6 – Faça um algoritmo que preencha cada uma das 80 posições de um vetor com uma letra, lida. 
Em seguida leia mais uma letra e imprima o número de vezes que esta letra aparece dentro do 
vetor. 
 
7 – Faça um algoritmo que preencha cada uma das 80 posições de um vetor com uma letra, lida. 
Em seguida imprima quantos pares de letras existem no vetor, ou seja, quantas vezes aparecem 
duas letras repetidas uma após a outra. 
 
8 – Faça um algoritmo que preencha cada uma das 50 posições de um vetor com um número 
inteiro, lido. Em seguida percorra o vetor e dobre o valor do conteúdo de cada elemento se for 
ímpar e menor que o último número lido e triplique o valor dos demais. 
 
9 – Calculo do Digito verificador do número de matrícula de um aluno: 
 
O número de matrícula é formado por 5 dígitos, mais 1 dígito verificador que fica no 
final. Este dígito verificador é calculado de acordo com os outros 5 dígitos do número de 
matrícula. 
Apresentamos aqui uma forma simplificada para o calculo deste dígito: Somar os 
produtos de cada um dos dígitos do número de matrícula, pela sua respectiva posição, e pegar o 
resto da divisão inteira desta soma por 11. Este resultado será o digito verificador do número de 
matrícula. 
 
10 – Faça um algoritmo que lê o número e as quatro notas de cada aluno de uma turma com 20 
alunos. Imprima para cada aluno: nº do aluno, média do aluno, média da turma. 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 6 de 35 
 
Capítulo II 
 
 
2 – Estruturas de Dados homogêneas: Matrizes. 
 
2.1 – Definição: 
 
Uma matriz é uma estrutura de dados homogênea, pois é formada por uma única variável, 
com um único nome,dividida em vários pedaços, denominados de células ou elementos da 
matriz, onde podemos guardar valores de mesmo tipo e mesmo significado. Matrizes são 
estruturas de dados similares aos vetores, com a diferença que podem ter várias dimensões. 
 
Exemplo 1: Uma matriz de notas só contém notas, não podemos guardar nas células de uma 
mesma matriz notas e salários pois, apesar de terem o mesmo tipo, real, possuem significados 
diferentes. 
 
 Cada célula de uma matriz fica identificada pelo “nome” da matriz e tantos índices, 
números inteiros, quanto forem as suas dimensões. Neste capítulo estudaremos as matrizes de 
duas dimensões, formada por linhas e colunas, por serem as mais utilizadas. Uma célula em uma 
matriz de duas dimensões fica identificada pelo nome da matriz e os números da linha e da 
coluna como veremos mais adiante. Uma matriz pode ser chamada de conjunto ou vetor 
multidimensional. 
 
Exemplo 2: Representamos graficamente uma matriz como abaixo, onde “LETRAS” é uma 
variável do tipo matriz com 4 linhas e 3 colunas. É uma matriz 4 x 3: 
 
 
Exemplo 3: 
 LETRAS 
 
 1 2 3 
1 C F E 
2 D A B 
3 H G I 
4 L M J 
 
 
2.2 – O tipo matriz: 
 
 Uma variável do tipo matriz, assim como o vetor, pode ser definida com várias 
formatações diferentes, pode variar o número de linhas e de colunas e o tipo dos conteúdos das 
células, por isso o tipo matriz tem de ser definido pelo programador com veremos abaixo: 
 
 Formato: 
 
 Tipo “identificador” = matriz [L1:Ln , C1:Cn ] “tipo”; 
 
 Onde: L1 é o número, índice, da primeira linha da matriz 
 Ln é o número, índice, da última linha da matriz 
 C1 é o número, índice, da primeira coluna da matriz 
 Cn é o número, índice, da última coluna da matriz 
 tipo é um único tipo que caracteriza o conteúdo de cada elemento da matriz, pode 
ser um tipo: básico, vetor, matriz ou registro, como veremos mais adiante. 
 
Ao especificarmos um tipo matriz, estamos apenas criando um molde ou modelo. Para 
que uma variável do tipo matriz passe a existir temos que criá-la usando este molde. 
 
Cada valor armazenado na 
matriz poderá ser acessado 
através do cruzamento de sua 
respectiva linha com a sua 
coluna. 
Exemplo 4: 
Imprima(LETRAS[3,2]); 
 
Imprime a letra: “G” 
 
Linhas 
Colunas 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 7 de 35 
 
 
Exemplo 5: 
 Tipo m = matriz [1 : 4 , 1 : 3] caracter; 
 m: LETRAS; 
 
 O total de dimensões de uma matriz é igual ao número de vírgulas da declaração mais 1. 
Os números de células, ou elementos, são iguais ao produto do número de células de cada 
dimensão, ou seja: 
 
Número de células = (Ln - L1 + 1) * (Cn - C1 + 1) 
 
Exemplo 6: 
 Para a matriz LETRAS, o número dimensões é 2. Temos uma única vírgula o que 
caracteriza duas dimensões, que são identificadas pelas linhas, primeira dimensão, e as colunas, 
segunda dimensão. 
 
Para a matriz LETRAS, o número de células ou elementos é: 
 
 Número de células = (Ln – L1 + 1) * (Cn – C1 + 1) = (4 – 1 + 1) * (3 – 1 + 1) = 12 
 
2.3 – Usando matrizes: 
 
Para acessar o conteúdo de uma célula de uma matriz de 2 dimensões precisamos do 
nome da matriz, e dos números da linha e da coluna que correspondam à célula que queremos 
acessar. Desta forma um elemento de uma matriz funciona como uma variável simples. 
 
Exemplo 7: 
 
 Seja a matriz abaixo: 
 
 1 2 3 
1 7,8 5,5 8,7 
2 5,8 7,9 8,0 
3 9,7 7,6 8,4 
4 6,4 5,8 8,7 
5 4,5 7,4 8,0 
 
Após serem executados os comandos abaixo: 
 
 NOTAS[1 , 1]  9,0; 
 
 Podemos usar uma variável do tipo inteiro como índice; 
 
 I  4; J  3; 
 NOTAS[I , J]  7,5; 
 
Podemos atribuir valor para um elemento de uma matriz através da leitura: 
 
 I  3; J  2; 
 Leia(NOTAS[I , J]); {digitamos a nota 8,2} 
 
 Temos: 
 1 2 3 
1 9,0 5,5 8,7 
2 5,8 7,9 8,0 
3 9,7 8,2 8,4 
4 6,4 5,8 7,5 
5 4,5 7,4 8,0 
 
 
 Ao executarmos o comando: Imprima (NOTAS[1,2]); - será impresso 5,5. 
 
NOTAS 
NOTAS 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 8 de 35 
 
Exemplo 8: 
 
 Percorrendo a matriz NOTAS por linha: Fixe a linha e varie a coluna. 
 
 Algoritmo Matriz_Linha: 
 Tipo m = matriz[5:3] real; 
 m: NOTAS; 
 Real: X; 
 Inicio 
 X  2,0; 
 Para I de 1 até 5 faça; 
 Para J de 1 até 3 faça; 
 X  X + 0,5; 
 NOTAS[I , J]  X; 
 Fim-Para; 
 Fim-Para; 
 Fim; 
 
Exemplo 9: 
 
 Percorrendo a matriz NOTAS por coluna: Fixe a coluna e varie a linha. 
 
 Algoritmo Matriz_ Coluna: 
 Tipo m = matriz[5:3] real; 
 m: NOTAS; 
 Real: X; 
 Inicio 
 X  2,0; 
 Para J de 1 até 3 faça; 
 Para I de 1 até 5 faça; 
 X  X + 0,5; 
 NOTAS[I , J]  X; 
 Fim-Para; 
 Fim-Para; 
 Fim; 
Após executar o algoritmo, temos: 
 
 NOTAS 
 1 2 3 
1 2,5 3,0 3,5 
2 4,0 4,5 5,0 
3 5,5 6,0 6,5 
4 7,0 7,5 8,0 
5 8,5 9,0 9,5 
 
Após executar o algoritmo, temos: 
 
 NOTAS 
 1 2 3 
1 2,5 5,0 7,5 
2 3,0 5,5 8,0 
3 3,5 6,0 8,5 
4 4,0 6,5 9,0 
5 4,5 7,0 9,5 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 9 de 35 
 
 
2.4 – Exercícios 
 
1 – Dada uma matriz 4 x 4 de inteiros faça um algoritmo que permita o preenchimento de toda a 
matriz, por linha, com os valores digitados pelo usuário. 
 
2 – Dada a matriz 4x4 preenchida no exercício anterior, faça um algoritmo capaz de fazer a soma 
de todos os valores de cada coluna e apresente o resultado na tela. 
 
3 – Escreva um algoritmo capaz de calcular a soma dos elementos que se encontram abaixo da 
diagonal principal de uma matriz de 10 x10 do tipo inteiro, cujos conteúdos serão digitados pelo 
usuário, e apresente o resultado no final do processamento. 
 
4 – Faça um algoritmo capaz de somar todos os valores de cada linha de uma matriz 4 x 5 do tipo 
real, que deverão ser digitados pelo usuário, e apresente o resultado da soma de cada linha. 
 
5 – Faça um algoritmo capaz de somar os valores de cada linha de uma matriz 4 x 5 do tipo 
inteiro, que deverão ser digitados pelo usuário. O total de cada linha será colocado no elemento 
de um vetor de índice igual ao número da linha e, em seguida soma os elementos do vetor em 
uma variável e imprime o resultado. 
 
6 – Dada uma matriz 4 x 4 do tipo inteiro que deverá ser preenchida pelo usuário, faça um 
algoritmo capaz de criar uma nova matriz com as mesmas dimensões, baseada na primeira cujos 
elementos devem obedecer as seguintes regras: 
 Quando o número da coluna for maior que o número da linha, o elemento deverá ser 
multiplicado pelo valor da coluna e colocado na mesma posição na nova matriz. 
 Quando o número da linha for maior que o da coluna, o elemento deverá ser multiplicado pelo 
número da linha e colocado na mesma posição na nova matriz. 
 Quando o número da coluna for igual ao da linha, o elemento deverá ser multiplicado por 10 e 
colocado na mesma posição na nova matriz. 
Após o processamento o algoritmo deverá imprimir a nova matriz elemento a elemento. 
 
7 – Faça um algoritmo para gerar a seguinte matriz: 
 
 1 2 3 4 5 6 
1 1 1 1 1 1 1 
2 1 2 2 2 2 1 
3 1 2 3 3 2 1 
4 1 2 3 3 2 1 
5 1 2 2 2 2 1 
6 1 1 1 1 1 1 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. CastroPágina 10 de 35 
 
Capítulo III 
 
3 – Estruturas de Dados heterogêneas: Registros. 
 
3.1 – Definição: 
 
 Em uma loja, em uma escola, no emprego, muitas vezes nos é solicitado o preenchimento 
de um cadastro com dados que identifique o cliente, o aluno ou o funcionário. Um cadastro é 
formado por vários registros, onde cada registro os dados de um: cliente, aluno, funcionário, 
contém como abaixo: 
 
 
 
 
 
 
 
 
 
O Registro de Clientes acima, que podemos chamar de registro (registra os dados de um 
cliente), é composto por um conjunto de dados relacionados, porém podendo ter tipos e 
significados diferentes, que denominamos de campos do registro: Código (inteiro), Nome 
(caracter), Data de Nascimento (caracter), Endereço (caracter), Telefone (inteiro), Sexo 
(caracter), Renda (real). Todos os dados pertencem ao cliente cujo “nome” estiver escrito no 
campo “Nome” do Cadastro. 
 Registros ou agregados heterogêneos ou variáveis compostas heterogêneas ou estrutura 
de dados heterogêneos são compostos por campos que são dados relacionados entre si e que 
formam uma unidade que chamamos de registro. 
 
3.2 – O tipo registro: 
 
 Uma variável do tipo registro pode possuir tantos campos quantos forem necessários para 
a aplicação, podendo ser definido com várias formatações diferentes, por isso o tipo registro tem 
de ser definido pelo programador com veremos abaixo: 
 
 Formato: 
 
 Tipo “identificador” = registro 
 “tipo do campo1” = “identificador do campo1”; 
 “tipo do campo2” = “identificador do campo2”; 
 .................................................................................... 
 
 “tipo do campon” = “identificador do campon”; 
 Fim-registro; 
 
3.3 – Usando registros: 
 
Ao especificarmos um tipo registro, estamos apenas criando um molde ou modelo. Para 
que uma variável do tipo registro passe a existir temos que criá-la usando este molde. 
 
Exemplo 1: Registro de cliente 
 Tipo rcli1 = registro 
 Inteiro: Código, tel; 
 Caracter: Nome, Nasc, Endereco, Sexo; 
 Real: Renda; 
 Fim-registro; 
 
 rcli1: REGCLI1; 
 
Registro de Cliente 
 
Código: ___________ Nome: ____________ Data de Nascimento: ___/ ___/ ___ 
 
Endereço: _____________________________ Telefone: _____________ 
 
Sexo: ___ Estado Civil: ______________ Renda: ____________ 
 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 11 de 35 
 
 
 Para termos acesso a cada campo de uma variável do tipo registro temos que escrever: 
 
 “Nome da variável tipo registro.campo”  “valor” ou “variável”; 
 
 Para o REGCLI1 temos: 
 
 REGCLI1.Nome  “Luis”; {Luis fica no campo nome da variável REGCLI1} 
 
 Leia (REGCLI1.Renda); {O valor digitado fica no campo Renda da variável REGCLI1} 
 
 Imprima(REGCLI1.Nome); {Será impresso Luis} 
 
Exemplo 2: 
Em uma loja, em uma escola, no emprego, muitas vezes nos é solicitado o preenchimento 
de um formulário com dados que identifique o cliente, o aluno ou o funcionário, como abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Na versão do Registro de Cliente acima, temos campos com os tipos básicos: Código 
(inteiro), Nome (caracter), Data de Nascimento (caracter), Sexo (caracter), Estado Civil 
(caracter), Renda (real), Telefone (inteiro), Celular (inteiro), Email (caracter); temos campos do 
tipo registro: Endereço, que possui os campos: Rua (caracter), Nº (inteiro), Complemento 
(caracter), CEP (inteiro) e temos campos do tipo vetor: Compras no trimestre que é formado por 
um vetor com três elementos cada um contendo o valor total gasto em compras pelo cliente em 
cada mês do trimestre. Todos os dados pertencem ao cliente cujo “nome” estiver escrito no 
campo “Nome” do Registro. Para criarmos a variável do tipo registro que contenha os campos 
acima temos que criar os tipos vetor e registro que compõem a variável antes, como abaixo: 
 
Exemplo 3: Registro de cliente 
 
 Tipo rend = registro 
 Inteiro: Número, Cep; 
 Caracter: Rua, Complemento; 
 Fim-registro; 
 
 Tipo vcom = vetor [1 : 3] real; 
 
Tipo rcli2 = registro 
 Inteiro: Código, Telefone, Celular; 
 Caracter: Nome, Nasc, Sexo, EstCivil, Email; 
 Real: Renda; 
 rend: End; 
 vcom: Compras; 
 Fim-registro; 
 
 rcli2: REGCLI2; 
Registro de Cliente 
 
Código: ___________ Nome: ____________ Data de Nascimento: ___/ ___/ ___ 
 
Sexo: ___ Estado Civil: ______________ Renda: ____________ 
 
Endereço: 
 Rua: _____________ Nº: _____ Complemento: ___________ CEP:______ 
 
Telefone: _____________ Celular: _____________ Email: _______________ 
 
 Compras no trimestre: 
 1 2 3 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 12 de 35 
 
 
 Para o REGCLI2 temos: 
 REGCLI2.Nome  “Luis”; {Luis fica no campo nome da variável REGCLI2} 
 
 REGCLI2.End.Rua  “Rua A”; 
 
 REGCLI2.Compras[1]  250,00; ”; {250,00 fica no elemento 1 do vetor “Compras” 
da variável REGCLI2} 
 
 Leia (REGCLI2.End.Número, REGCLI2.Compras[3]); {O primeiro valor digitado 
fica no campo Número do campo End da variável REGCLI2 e o segundo valor 
digitado fica no terceiro elemento do vetor Compras da variável REGCLI2} 
 
 Imprima(REGCLI2.End.Rua, REGCLI2.Compras[1]); {Imprime: Rua A 250,00} 
 
Exemplo 4: 
 
Modificamos o Registro de Cliente acima para conter as compras do cliente nos quatro 
trimestres do ano, trocando o vetor pela matriz “Compras nos trimestres de um ano” que é uma 
matriz 4 x 3 como abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Para criarmos a variável do tipo registro que contenha os campos acima termos que criar 
os tipos matriz e registro que compõem a variável antes, como abaixo: 
 
Exemplo 5: Registro de cliente 
 
 Tipo rend = registro 
 Inteiro: Numero, Cep; 
 Caracter: Rua, Complemento; 
 Fim-registro; 
 
 Tipo mcom = matriz [4 : 3] real; 
 
Tipo rcli3 = registro 
 Inteiro: Codigo, Telefone, Celular; 
 Caracter: Nome, Nasc, Sexo, EstCivil, Email; 
 Real: Renda; 
 rend: End; 
 mcom: Compras; 
 Fim-registro; 
 
 Rcli3: REGCLI3; 
Cadastro de Cliente 
 
Código: ___________ Nome: ____________ Data de Nascimento: ___/ ___/ ___ 
 
Sexo: ___ Estado Civil: ______________ Renda: ____________ 
 
Endereço: 
 Rua: _____________ Nº: _____ Complemento: ___________ CEP:______ 
 
Telefone: _____________ Celular: _____________ Email: _______________ 
 
 Compras nos trimestres: 1 1111 
 2 2 
 3 
 4 
 1 2 3 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 13 de 35 
 
 
Para o REGCLI3 temos: 
 
 REGCLI3.Compras[1 , 3]  350,00;Leia (REGCLI3.Compras[3 , 2]); {O valor digitado fica na célula identificada pelo 
cruzamento da linha 3 com a coluna 2 da matriz Compras da variável REGCLI3} 
 
 Imprima(REGCLI3.Compras[1 , 3]); {Imprime: 350,00} 
 
3.4 – Usando registros como elementos de vetores (Tabelas): 
 
Vamos representar uma agenda telefônica com 10 páginas contendo em cada página 
espaço para guardar o “nome” e o “número de um telefone” de uma pessoa. Para tal, criamos 
uma variável do tipo vetor e em cada um de seus elementos colocamos um registro com dois 
campos: Nome, Telefone, como abaixo: 
 
 AGENDA 
Nome 
 
Tel 
Nome 
 
Tel 
Nome 
 
Tel 
 
..................................... 
Nome 
 
Tel 
Nome 
 
Tel 
 1 2 3 9 10 
 
Podemos ainda representar agenda como uma tabela na memória: 
 AGENDA 
 Nome Telefone 
0 José Maria da Silva 23293454 
1 Maria José da Silva 23236789 
2 
3 
. 
. 
. 
. 
. 
. 
. 
. 
. 
10 
 
Exemplo 6: Agenda Telefônica: 
 
Tipo ragen = registro 
 Caracter: Nome; 
 Inteiro: Tel; 
 Fim-registro; 
 
Tipo vagen = vetor [1 : 10] ragen; 
 
 vagen: AGENDA; 
 
 
Para a AGENDA temos: 
 
AGENDA[3].Nome  “Ana”; 
 
 Leia(AGENDA[3].Tel) { o número do telefone da Ana, ex.: 22224554, ao ser 
digitado fica no campo “Tel” do terceiro elemento do vetor AGENDA}; 
 
 Imprima(AGENDA[3].Nome, AGENDA[3].Tel) {Imprime: Ana 22224554} 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 14 de 35 
 
3.5 – Exercícios 
 
 
1 – Crie a variável do tipo registro correspondente ao Registro de Funcionário abaixo: 
 
 
 
 
 
 
 
 
 
 
2 – Faça um algoritmo que cria uma variável do tipo registro correspondente ao Registro de 
Funcionário abaixo, leia o conteúdo de um registro e preencha cada um de seus campos com os 
valores lidos. Imprima os salários maiores que o último: 
 
 
 
 
 
 
 
 
 
 
 
3 – Faça um algoritmo que cria uma variável do tipo registro correspondente ao Registro de 
Funcionário abaixo, leia o conteúdo de um registro e preencha cada um de seus campos com os 
valores lidos. Imprima o número do trimestre onde a soma dos salários é o maior: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 – Faça um algoritmo que tome por base a “AGENDA” do exemplo 3, crie a tabela 
correspondente acrescentando mais dois campos da sua escolha. Preencha todos os 10 elementos 
do vetor “AGENDA” com os valores lidos. Em seguida leia o nome de uma pessoa, procure este 
nome na “AGENDA” e, se existir imprima os dados dessa pessoa ou imprima a mensagem: 
“Nome não existe” caso não encontre. 
Registro de Funcionário 
 
Código: ___________ Nome: ____________ Data de Nascimento: ___/ ___/ ___ 
 
Departamento: ________ Profissão: ______________ Função: ____________ 
 
Ano: _____ Salário de Jan: _________ Salário de Fev:__________ Salário de Mar:_________ 
 
 
Registro de Funcionário 
 
Código: ___________ Nome: ____________ Data de Nascimento: ___/ ___/ ___ 
 
Departamento: ________ Profissão: ______________ Função: ____________ 
 
Ano: _____ 
Salários no trimestre: 
 1 2 3 
 
 
Registro de Funcionário 
 
Código: ___________ Nome: ____________ Data de Nascimento: ___/ ___/ ___ 
 
Departamento: ________ Profissão: ______________ Função: ____________ 
 
Ano: _____ 
 
Salário nos trimestres: 1 1111 
 2 2 
 3 
 4 
 1 2 3 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 15 de 35 
 
Capítulo IV 
 
4 – Métodos de Pesquisa. 
 
4.1 – Pesquisa sequêncial: 
 
 É o método mais simples de pesquisa. Neste método o vetor é percorrido 
sequêncialmente do primeiro até o último elemento ou do último até o primeiro elemento até 
encontrar o valor pretendido ou chegar ao fim do vetor, caso o valor pretendido não seja 
encontrado. 
 
Pesquisa em vetor desordenado: 
 Consideramos que os elementos do vetor não estão ordenados. 
 
Quando os valores no vetor não se repetem: 
 Buscar a ocorrência do valor no vetor. 
 
Quando os valores no vetor se repetem: 
 Buscar a primeira ocorrência de um valor no vetor. 
 Buscar a última ocorrência de um valor no vetor. 
 Buscar uma ocorrência qualquer de um valor no vetor. 
 Buscar todas as ocorrências de um valor no vetor. 
 
Algoritmo de pesquisa 
ALGORITMO PesquisaLinearSimples_Desordenado; 
{Busca todas as ocorrências do valor procurado no vetor desordenado. Cada vez que encontrar 
imprime o índice. Caso não encontre, imprime uma mensagem.} 
 Tipo v: vetor [1 : 50] caracter; 
 v:VP; 
 Inteiro: I; 
 Lógico: ACHOU; 
 Caracter: Procurado; 
INICIO 
 Imprima(„Digite o nome do elemento a ser pesquisado:‟) 
 Leia(Procurado); 
 Para I de 1 até 50 faça //atribuição de valores para o vetor 
 Leia ( VP[ I ] ); 
 Fim-Para; 
 ACHOU  .F.; 
 Para I de 1 até 50 faça 
 Se VP[ I ] = Procurado 
 Então Imprima(„o valor procurado foi encontrado na posição „, I) 
 ACHOU  .V.; 
 Fim-Se; 
 Fim-Para; 
 Se ACHOU = .F. 
 Então Imprima("Não encontrou"); 
 Fim-Se; 
Fim. 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 16 de 35 
 
 
Pesquisa em vetor ordenado: 
 Consideramos que os elementos do vetor estão ordenados. 
Quando os valores no vetor não se repetem: 
 Buscar a ocorrência do valor no vetor. 
 
Quando os valores no vetor se repetem: 
 Buscar a primeira ocorrência de um valor no vetor. 
 Buscar a última ocorrência de um valor no vetor. 
 Buscar uma ocorrência qualquer de um valor no vetor. 
 Buscar todas as ocorrências de um valor no vetor. 
 
Algoritmo de pesquisa 
ALGORITMO PesquisaLinearSimples_Ordenado; 
{Busca a primeira ocorrência do valor procurado no vetor ordenado. Cada vez que encontrar 
imprime o índice. Caso não encontre, imprime uma mensagem.} 
 Tipo v: vetor [1 : 50] caracter; 
 v:VP; 
 Inteiro: I; 
 Lógico: ACHOU; 
 Caracter: Procurado; 
INICIO 
 Imprima(„Digite o nome do elemento a ser pesquisado:‟) 
 Leia(Procurado); 
 Para I de 1 até 50 faça //atribuição de valores para o vetor 
 Leia ( VP[ I ] ); 
 Fim-Para; 
 I  1 
 Enquanto VP[I] < Procurado e I < 50 Faça 
 i  i + 1; 
 Fim-Enquanto; 
 Se VP[i] <> Procurado 
 Então Imprima ('O valor não foi encontrado') 
 Senão Imprima ('O valor foi encontrado na posição', i); 
FIM. 
 
4.2 – Pesquisa binária: 
Comparar o valor que se encontra no meio do vetor com o valor procurado, podendo 
acontecer uma de três coisas: 
 Encontrou: se é igual ao valor procurado 
 Continuar procurando (do mesmo modo) no sub-vetor à esquerda da posição do “meio” 
Se é maior doque o valor procurado 
 Continuar procurando (do mesmo modo) no sub-vetor à direita da posição do “meio” 
Se é menor do que o valor procurado 
Se o vetor inspecionado se reduzir a um vetor vazio, então o valor procurado não existe. 
 
Pesquisa em vetor ordenado: 
 Consideramos que os elementos do vetor estão ordenados. 
Quando os valores no vetor não se repetem: 
 Buscar a ocorrência de um valor no vetor. 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 17 de 35 
 
ALGORITMO PesquisaBinária; 
 Tipo v = vetor [ 1 : 128] Inteiro; 
 v: VP; 
 Inteiro: I, Inicio, Fim, Meio; 
 Inteiro: Procurado; 
INICIO 
 Imprima(„Digite o nome do elemento a ser pesquisado:‟) 
 Leia(Procurado); 
 PARA i de 1 até 128 Faça //atribuição de valores para o vetor 
 Leia ( VP[ I ] ); 
 Fim-Para; 
 Inicio  1; 
 Fim  128; 
 Enquanto Procurado <> VP[Meio] e Inicio <= Fim faça 
 Meio  (Inicio + Fim) div 2; 
 Se Procurado < VP[Meio] 
 Então Fim  Meio – 1; 
 Senão Então Inicio  Meio + 1 
 Fim-Se; 
 Fim-Enquanto; 
 SE VP[Meio] <> Procurado 
 Então Imprima("Não Encontrou") 
 Senão Imprima("Encontrou na posição : ", Meio) 
 Fim-Se; 
Fim. 
 
 
20 30 40 50 60 70 80 9010 100
início fimmeio
Chave de Busca = 60
1a. Iteração
20 30 40 50 60 70 80 9010 100
início fimmeio
2a. Iteração
20 30 40 50 60 70 80 9010 100
início
fimmeio
3a. Iteração
Exemplo: 
Algoritmo de pesquisa 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 18 de 35 
 
 
 
4.3 – Pesquisa conclusões: 
 
 Na pesquisa sequêncial simples, o número médio de comparações realizadas para 
encontrar um valor no vetor é N/2, onde N é o número de elementos do vetor. 
 
 Para um vetor com 128 elementos temos: 128/2 = 64 comparações em média. 
 
 Na pesquisa binária, o número máximo de comparações é log2 N. 
 
 Para um vetor com 128 elementos temos: log2 128 = 7 comparações no máximo. 
 
4.5 – Exercícios 
 
1. Faça um algoritmo que leia 10 valores numéricos inteiros. Após a leitura emita um 
relatório com cada valor diferente e o número de vezes que o mesmo apareceu no vetor. 
 
2. Dado uma relação de N nomes, faça um algoritmo que verifique se uma determinada 
pessoa está neste vetor. O nome da pessoa a ser pesquisada deverá ser lido, bem como os 
nomes a serem colocados no vetor. 
 
3. Dado que para cada aluno de uma turma de N alunos se tenha, o seu nome, e as notas das 
8 avaliações. Faça um algoritmo que: 
a) Imprima o nome a média de cada aluno; 
b) Para cada aluno imprima uma mensagem dizendo se o aluno tem ou não notas 
repetidas; 
c) Determine quantos alunos tem pelo menos duas notas acima de 7; 
 
4. Dado um vetor contendo números inteiros faça um algoritmo que pesquise se um 
determinado valor existe dentro do vetor. Caso exista, deverá ser dada uma mensagem 
para o usuário informando a posição dentro do vetor onde o valor foi encontrado. Caso o 
valor não exista deverá ser dado uma mensagem informando o usuário da não existência 
do valor dentro do vetor. 
 
5. Uma escola precisa de um algoritmo que controle a média das notas dos alunos de cada 
classe e a média das notas de todos os alunos da escola. Sabendo que essa escola possui 5 
classes, e em cada classe tem N alunos, gerando um total de 5xN notas, crie um algoritmo 
que leia as notas de cada aluno de cada classe e no final apresente a média de cada classe 
e a média da escola em geral. 
 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 19 de 35 
 
Capítulo V 
 
5 – Métodos de Ordenaçaão. 
 
5.1 – Ordenação: 
Ordenação corresponde ao método de organizar um conjunto de objetos em uma ordem 
crescente ou decrescente. É uma atividade relevante e fundamental em processamento de dados. 
Tem como objetivo facilitar a recuperação dos itens do conjunto 
– Recuperação de nomes em um lista telefônica 
 
Identificamos duas formas de ordenação 
• Ordenação Interna: 
– O conjunto de dados é pequeno, cabe todo na memória principal. 
– O processo de ordenação é realizado internamente na memória principal. 
– Os dados a serem ordenados estarão em um vetor ou em uma tabela, quando a 
ordenação é feita por um campo chamado de chave que identifica cada elemento do 
vetor que forma a tabela. 
• Ordenação Externa: 
– O conjunto de dados não cabe completamente em memória principal, 
– Os dados a serem ordenados estarão em disco ou fita em arquivos no formato de 
registros que são acessados seqüencialmente ou em blocos 
 
Alguns métodos de ordenação interna que estudaremos: 
 
Ordenação por inserção: 
• Método de Inserção direta (Insertion Sort) 
Ordenação por troca 
• Método de Bollha (bubble sort) 
• Método de troca e partição (QuickSort) 
Ordenação por seleção 
• Método de Seleção direta (Selection Sort) 
 
5.2 – Ordenação por inserção 
 
• Algoritmo: Método de Inserção Direta (Insertion Sort) 
 
 
• É um algoritmo simples 
• Procedimento 
1. Os elementos são divididos em uma seqüência de destino a1, ..., ai-1 e em uma 
seqüência fonte ai, ..., an. 
2. Em cada passo, a partir de i =2, o i-ésimo item da seqüência fonte é retirado e 
transferido para a seqüência destino sendo inserido na posição adequada 
• Exemplo 
 
 
 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 20 de 35 
 
 
 
• A inserção do item em uma posição adequada na seqüência de destino é realizada com a 
movimentação das chaves maiores para a direita e o item é inserido na posição vazia 
 
• Vantagens: 
– O número mínimo de comparações e movimentos ocorre quando os itens já estão 
originalmente ordenados 
– O número máximo ocorre quando os itens estão originalmente em ordem reversa, 
o que indica um comportamento natural para o algoritmo 
 
 
Implementação do algoritmo 
 
Program Insercao_Direta; 
Type 
 v=array[0..6] of string[1]; 
Var 
 A: v; 
 ITEM: String[1]; 
 I, J: Integer; 
Begin 
 For I := 1 to 6 do 
 Begin 
 Write('Digite uma letra: '); 
 Readln(A[I]); 
 End; 
 For I := 1 to 6 do 
 Write(I,':',A[I]:2,' '); 
 writeln; 
 For I := 2 to 6 do 
 Begin 
 ITEM := A[I]; 
 J := I - 1; 
 A[0] := ITEM; {sentinela} 
 While ITEM < A[J] do 
 Begin 
 A[J+1] := A[J]; 
 J := J - 1; 
 End; 
 A[J+1] := ITEM; 
 End; 
 For I := 1 to 6 do 
 Write(I,':',A[I]:2,' '); 
 readln; 
 End. 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 21 de 35 
 
5.3 – Ordenação por troca 
 
• Algoritmo: Método de Bollha (bubble sort) 
 
• Um dos algoritmos mais simples 
• Princípio: 
1. Em cada passo, cada elemento é comparado com o próximo e trocado se estiverer 
fora de ordem; 
2. Repete-se o processo de comparação e troca até que não ocorram mais trocas 
• O nome Bolha é devido a: 
1. Colocando o vetor a ordenar na vertical, com Item[n] em cima e Item[1] embaixo, 
em cada passo o menor elemento “sobe” até encontrar um elemento maior ainda, 
como se uma bolha subisse dentro de um tubo de acordo com sua densidade 
• Exemplo 
 
Implementação do algoritmo 
Program ORD1_Bolha; 
Typev = array[1..8] of Integer; 
Var 
 ITEM: v; 
 I, J,K: Integer; 
Begin 
 For I := 1 to 8 do 
 Begin 
 Write('Digite um número: '); 
 Readln(ITEM[I]); 
 End; 
 For I := 1 to 8 do 
 Write(I,':',ITEM[I]:2,' '); 
 writeln; 
 For I:= 2 to 8 do {inicio da ordenação} 
 For J:= 8 downto I do 
 If ITEM[J-1] > ITEM[J] 
 Then Begin 
 AUX:= ITEM[J-1]; 
 ITEM[J-1] := ITEM[J]; 
 ITEM[J] := AUX; 
 End; {fim da ordenasção} 
 For I := 1 to 8 do 
 Write(I,':',ITEM[I]:2,' '); 
 readln; 
End. 
Melhorando o algoritmo: 
No exemplo, as três últimas 
iterações não afetam a ordem do vetor. 
Então, o algoritmo, apesar de correto, 
pode ser melhorado. 
 Podemos melhorar, mantendo uma 
indicação para saber se houve ou não 
troca na última iteração: se não houve, o 
vetor já está ordenado 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 22 de 35 
 
 
 Algoritmo: Método de troca e partição (QuickSort) 
 
• O Quicksort é o algoritmo mais rápido para ordenação interna conhecido para uma 
grande quantidade de situações, sendo por isso o mais utilizado entre todos os algoritmos 
de ordenação 
• Princípio 
1. Dividir o problema de ordenar um conjunto de n itens em dois problemas menores 
2. Ordenar independentemente os problemas menores 
3. Combinar os resultados para produzir a solução do problema maior 
• Procedimento Algoritmo QuickSort 
1. Escolher arbitrariamente um item do vetor e colocar este valor em x 
2. Percorrer o vetor a partir da esquerda até que um item A[i]  x é encontrado; da 
mesma maneira, percorrer o vetor a partir da direita até que um item A[j]  x é 
encontrado; 
3. Como os itens A[i] e A[j] não estão na ordem correta no vetor final, eles devem 
ser trocados 
4. Continuar o processo (de partição) até que os índices i e j se cruzem em algum 
ponto do vetor 
• Ao final do processo, o vetor A[Esq..Dir] está particionado em dois seguimentos: 
5. Os itens em A[Esq], A[Esq+1],..., A[j] são menores ou iguais a x 
6. Os itens em A[i], A[i+1],..., A[Dir] são maiores ou iguais a x 
• Após obter os dois segmentos do vetor pelo processo de partição, executamos este 
processo em cada segmento de forma recursiva até que todo o vetor esteja ordenado 
 
Exemplo de Partição 
 
 
 
 
 
 
 
 
 
 
• O pivô é escolhido como sendo A[(i+j) div 2] 
• Inicialmente, i=1 e j=6, e então x=A[3] = D 
• A varredura a partir da posição 1 pára no item O e a varredura a partir da posição 6 pára 
em A, sendo os dois itens trocados 
• A varredura a partir da posição 2 pára em R e a varredura a partir da posição 5 pára no 
item D, e então os dois itens são trocados 
• Neste instante i e j se cruzam (i=3 e j=2), o que encerra o processo de partição 
 
 
 
 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 23 de 35 
 
Procedimento Ordena (após Partição) 
 
 
 
Implementação do algoritmo 
 
Program QuickSort; 
Type 
 v = array[1..6] of String[1]; 
Var 
 A: v; 
 i, j: Integer; 
Procedure Particao(Esq,Dir: Integer); 
var 
 MEIO, X: String[1]; 
Begin 
 i := Esq; j:= Dir; 
 MEIO:= A[(i+j) div 2]; {obtenção do meio} 
 Repeat; 
 while MEIO > A[i] do i:=i+1; 
 while MEIO < A[j] do j:=j-1; 
 If I <= j Then Begin 
 X := A[i]; 
 A[i]:= A[j]; 
 A[j]:= X; 
 i:=i+1; 
 j:=j-1; 
 End; 
 until i>j; 
 If Esq < j Then Particao(Esq,j); 
 If i < Dir Then Particao(i,Dir); 
end; 
Begin 
 For I := 1 to 6 do 
 Begin 
 Write('Digite um número: '); Readln(A[I]); 
 End; 
 For I := 1 to 6 do 
 Write(I,':',A[I]:2,' '); 
 writeln; 
 Particao(1,6); 
 For I := 1 to 6 do 
 Write(I,':',A[I]:2,' '); 
 readln; 
 End.
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 24 de 35 
 
5.4 – Ordenação por seleção 
 Algoritmo: Método de Seleção direta (Selection Sort) 
 
• Um dos algoritmos mais simples 
• Mais recomendado para conjuntos pequenos 
 
• Procedimento: 
o Selecione o elemento com a chave de menor valor 
o Troque-o com o com o primeiro elemento da sequencia 
o Repita essas operações com os n-1 elementos restantes, depois com os n-2 
elementos e assim sucessivamente até restar um só elemento, o maior deles. 
 
 
 
Implementação do algoritmo 
 
Program Selecao_Direta; 
Type 
 v=array[1..6] of string[1]; 
Var 
 A: v; 
 X: String[1]; 
 I, J, K: Integer; 
Begin 
 For I := 1 to 6 do 
 Begin 
 Write('Digite uma letra: '); Readln(A[I]); 
 End; 
 For I := 1 to 6 do Write(I,':',A[I]:2,' '); 
 Writeln; 
 For I:=1 to 6 do {Selecao_Direta} 
 Begin 
 K := I; {Posição a ser ordenada} 
 X := A[I]; 
 For J:=I+1 to 6 do 
 If (A[J] < X) 
 Then Begin 
 K := J; {Posição a ser trocada} 
 X := A[K]; 
 End; 
 A[K] := A[I]; {Troca} 
 A[I] := X; 
 End; 
 For I := 1 to 6 do Write(I,':',A[I]:2,' '); 
 Readln; 
End. 
• Exemplo 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 25 de 35 
 
5.5 – Exercícios 
 
1. Faça a ordenação do vetor abaixo com cada um dos quatro algoritmos de ordenação que 
estudamos. Vetor = { 4, 8, 2, 3, 7} Obs: Crie quatro programas Pascal, um para cada 
método. 
 
2. Faça um programa Pascal que preencha um vetor com dez números inteiros, calcule e 
mostre o vetor resultante de uma ordenação decrescente. 
Exemplo: Números lidos: 3 5 4 2 1 6 8 7 11 9 
 Vetor Ordenado: 11 9 8 7 6 5 4 3 2 1 
 
3. Faça um programa Pascal que preencha um vetor com vinte números inteiros, calcule e 
mostre o vetor resultante de uma ordenação crescente. Em seguida leia um número que 
exista no vetor e usando a pesquisa binária, imprima o seu índice no vetor. 
 
4. Compare cada um dos métodos de ordenação que estudamos, quanto o seu desempenho 
e diga, em quais situações (em relação ao tamanho do conjunto de dados a ordenar) 
devemos escolher cada um. 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 26 de 35 
 
Capítulo VI 
 
6 – Arquivos. 
 
6.1 – Definição: 
 
 No item 3.4 do capítulo anterior, criamos uma agenda colocando registros em cada um 
dos 10 elementos de um vetor, cada registro com 2 campos: “Nome” e “Telefone”. Assim, 
criamos uma tabela na memória principal onde podemos guardar dados de até 10 pessoas 
enquanto o programa estiver executando e o computador estiver ligado. 
 Se guardarmos estes mesmos registros, de cada pessoa, em uma memória secundaria: 
HD, CD, DVD, Pen Drive, etc..., temos um “Arquivo”. Um arquivo é formado por um conjunto 
de registro e fica armazenado em uma memória secundária. As vantagens são: não possui 
número fixo de registros, o limite é o espaço disponível na memória secundária; quandoo 
programa termina a sua execução o arquivo continua a existir, podendo ser usado por outros 
programas e até em outros computadores. Temos ainda arquivos formados por textos ou por 
um único dado de um tipo básico, porém trabalharemos com Arquivos formados por registros 
por serem os mais utilizados. 
 
Exemplo 1: Representamos graficamente um arquivo como uma tabela formada por registros, 
semelhante as tabelas descritas no item 3.4, como abaixo. A diferença é que agora, este conjunto 
de registro ficará guardado em uma memória secundária, sendo chamado de “Arquivo”. Temos 
então o Arquivo “AGENDA”: 
 
AGENDA 
 Nome Telefone 
0 José Maria da Silva 23293454 
1 Maria José da Silva 23236789 
2 
3 
. 
. 
. 
. 
. 
. 
. 
. 
. 
n 
 
6.2 – Declarando um arquivo: 
 
 Um arquivo fica armazenado em uma memória secundária com seus dados guardados em 
forma de registros. Estes registros são chamados de registros físicos e o arquivo, de arquivo 
físico, possui um nome (nome do arquivo físico) e fica dentro de uma pasta do Sistema 
Operacional. Para criarmos uma independência entre o programa que usará o arquivo físico e 
próprio arquivo, criamos um nome para o arquivo dentro do programa, arquivo lógico, e 
associamos este nome ao nome do arquivo que está em memória secundária, arquivo físico. 
Então temos que criar o nome lógico para o arquivo associando este nome a um registro que 
ficará na memória principal e terá o mesmo formato do registro do arquivo físico. A cada 
operação de “Leitura” no arquivo, um registro físico será transferido para o correspondente 
registro lógico que está na memória e só a partir deste instante teremos acesso aos seus campos. 
O processador não enxerga um campo diretamente na memória secundária. O processo inverso 
será realizado para gravarmos um registro físico no arquivo, ou seja, transferimos um registro 
lógico, completo, da memória principal para o registro corrente do arquivo físico na memória 
secundária. 
 
 Formato: 
 Arquivo “Identificador 1”, ... , “Identificador n” de “nome do registro”; 
 
 Identificador: é o nome lógico do arquivo no programa. 
1 - Como vimos, a estrutura ao 
lado seria uma “Tabela” se 
guardarmos os registro em um 
vetor na memória principal. 
Porém como está guardada em 
uma memória secundária, 
chamamos de Arquivo. 
 
2 - Em Banco de Dados, a 
estrutura que aqui chamamos 
de “Arquivo”, é chamada de 
“Tabela” 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 27 de 35 
 
 
Exemplo 1: Declaração do Arquivo Agenda. 
 
Tipo ragen = registro 
 Caracter: Nome; 
 Inteiro: Tel; 
 Fim-registro; 
 
 Arquivo: AGENDA de ragen; 
 
6.3 – Usando Arquivos: 
 
6.3.1 – Novos comandos: 
Para que um programa possa usar um arquivo físico, temos que fazer a ligação entre os 
dois através do nome lógico criado pelo tipo “Arquivo”, que será o nome do arquivo, ou apelido, 
no programa. O comando que realizará esta tarefa é o comando “Abra”, no algoritmo só usamos 
o nome lógico do arquivo. 
 
Formato: 
 Abra (“Identificador 1”, ... , “Identificador n”); 
 
 Identificador: é o nome lógico do arquivo no programa. 
 
Após a execução do comando “Abra” o ponteiro do arquivo estará apontando para o 
primeiro registro do arquivo que é o registro “0”. Isto significa que podemos acessar os dados 
deste registro trazendo seus campos para o registro lógico que criamos na memória principal. O 
comando que realizará esta tarefa é o comando “Leia”. Este comando, ao ser executado, traz 
para memória o registro corrente do arquivo e em seguida faz com que o ponteiro passe a apontar 
o registro seguinte. 
Formato: 
 Leia (“Identificador 1”, “Identificador 2”); 
 
 Identificador 1: é o nome do arquivo lógico no programa. 
 Identificador 2: é o nome do registro lógico no programa. 
 
O comando “Grave” faz o contrário do “Leia”, ele copia todos os campos do registro 
lógico que criamos na memória principal, para o registro físico corrente do arquivo, que está na 
memória secundária e em seguida faz com que o ponteiro dos registros físicos do arquivo passe a 
apontar o registro seguinte. 
 
Formato: 
 Grave (“Identificador 1”, “Identificador 2”); 
 
 Identificador 1: é o nome do arquivo lógico no programa. 
 Identificador 2: é o nome do registro lógico no programa. 
 
O comando “Posição” move o ponteiro do arquivo físico para uma posição, registro 
físico, determinada no arquivo físico, já que cada registro físico possui um número, onde o 
primeiro registro tem o número “0” e o número dos demais vai crescendo de um em um até o 
último. 
Formato: 
 Posição (“Identificador 1”, “Identificador 2”); 
 
 Identificador 1: é o nome do arquivo lógico no programa. 
 Identificador 2: contém o número do registro para o qual o ponteiro apontará. 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 28 de 35 
 
 
 
A função Fda, retorna verdadeiro quando o ponteiro está posicionado no fim do arquivo 
físico e falso em caso contrário. 
 
Formato: 
 Fda (“Identificador”); 
 
 Identificador: é o nome do arquivo lógico no programa. 
 
A função ArqPos, retorna o número do registro físico onde o ponteiro está posicionado. 
 
Formato: 
 ArqPos (“Identificador”); 
 
 Identificador: é o nome do arquivo lógico no programa. 
 
Após usar o arquivo o programa deve liberá-lo. O comando que realizará esta tarefa é o 
comando “Feche”. 
 
Formato: 
 Feche (“Identificador 1”, ... , “Identificador n”); 
 
 Identificador: é o nome do arquivo lógico no programa. 
 
6.3.2 – Operações básicas: 
 Temos quatro operações básicas: inclusão, alteração, exclusão e consulta. 
 - Inclusão: Novos registros são incluídos no arquivo. 
 - Alteração: Temos que encontrar o registro que queremos alterar e copiar para memória 
com o comando “Leia”. Estando na memória principal, podemos alterar os campos desejados e 
em seguida, com o comando “Grave”, gravar no arquivo sobre o registro que fora lido, que ficará 
com as alterações. 
 
 - Exclusão: Um registro ao ser excluído, não sai fisicamente do arquivo. O que fazemos 
é marcar um campo com “*” para caracterizar a sua exclusão lógica, pois ele não será mais lido 
apesar de continuar no arquivo. O que fazemos é uma alteração. 
 
 - Consulta: Encontramos o registro que queremos consultar e copiamos o seu registro 
físico para o registro lógico correspondente na memória usando o comando “Leia”. 
 
 A forma de trabalhar com um arquivo depende, do modo como está organizado. As duas 
formas básicas de organizar um arquivo são as organizações: seqüencial e direta. 
 
6.3.3 – Organização sequêncial: 
 Um arquivo está organizado sequencialmente quando os seus registros são gravados 
continuamente, um após o outro. Este tipo de arquivo é normalmente acessado sequencialmente 
e os novos registros são incluídos sempre após o último ou em registro marcado como excluído. 
A exclusão de um registro é uma exclusão lógica, pois marcamos um campo com “*” para que 
ele não seja mais “lido”. 
 Usando o nosso arquivo “AGENDA”, passamos a escrever os algoritmos que executam 
as operações básicas: 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 29 de 35 
 
 
Exemplo 1: Inclusão 
 Algoritmo Arq_Inclui; 
{Inclui um novo registro físico no final do arquivo a partir de dadosdigitados 
ou emite uma mensagem de erro caso o registro já exista no arquivo} 
 Tipo ragen = registro 
 Caracter: Exc, Nome; 
 Inteiro: Tel; 
 Fim-registro; 
 Arquivo: AGENDA de ragen; 
 ragen: AG; 
 ragen: ENT; 
 Inicio 
 Abra(AGENDA); 
 Leia(ENT.Nome); 
 Leia (AGENDA, AG); 
 Enquanto Não Fda(AGENDA) e (AGENDA.Nome <> ENT.Nome ou 
 AGENDA.Exc = “*”) faça 
 Leia (AGENDA, AG); 
 Fim-Enquanto; 
 Se AGENDA.Nome = ENT.Nome e AGENDA.Exc <> “*” 
 Então Imprima(“Nome: “, ENT.Nome, “ já existe”); 
 Senão Leia(ENT.Tel); 
 AG.Tel  ENT.Tel; 
 AG.Exc  “ “; 
 Grave (AGENDA, AG); 
 Fim-Se; 
 Feche(AGENDA); 
 Fim; 
Exemplo 2: Consulta 
 Algoritmo Arq_Consulta; 
 {Consulta o número do telefone se a pessoa está cadastrada, emite mensagem 
 em caso contrário} 
 Tipo ragen = registro 
 Caracter: Exc, Nome; 
 Inteiro: Tel; 
 Fim-registro; 
 Arquivo: AGENDA de ragen; 
 ragen: AG; 
 ragen: CON; 
 Inicio 
 Abra(AGENDA); 
 Leia(CON.Nome); 
 Leia (AGENDA, AG); 
 Enquanto Não Fda(AGENDA) e (AGENDA.Nome <> CON.Nome ou 
 AGENDA.Exc = “*”) faça 
 Leia (AGENDA, AG); 
 Fim-Enquanto; 
 Se AGENDA.Nome = CON.Nome e AGENDA.Exc <> “*” 
 Então Imprima (AG.Nome, AG.Tel); 
 Fim-Se; 
 Feche(AGENDA); 
 Fim; 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 30 de 35 
 
 
Exemplo 3: Alteração 
 Algoritmo Arq_Altera; 
{Altera o número do telefone em um registro físico a partir de dados digitados, 
se a pessoa está cadastrada, emite mensagem em caso contrário} 
 Tipo ragen = registro 
 Caracter: Exc, Nome; 
 Inteiro: Tel; 
 Fim-registro; 
 Arquivo: AGENDA de ragen; 
 ragen: AG; 
 ragen: ALT; 
 caracter: SN; 
 Inicio 
 Abra(AGENDA); 
 Leia(ALT.Nome); 
 Leia (AGENDA, AG); 
 Enquanto Não Fda(AGENDA) e (AGENDA.Nome <> ALT.Nome ou 
 AGENDA.Exc = “*”) faça 
 Leia (AGENDA, AG); 
 Fim-Enquanto; 
 Se AGENDA.Nome = ALT.Nome e AGENDA.Exc <> “*” 
 Então Imprima (AG.Nome, AG.Tel); 
 Imprima (“Deseja alterar o número do telefone? – S/N”); 
 Leia (SN); 
 Se SN = “S” or SN = “s” 
 Então Leia(ALT.Tel); 
 AG.Tel ALT.Tel; 
 Posição(AGENDA, ArqPos(AGENDA) - 1); 
 Grave (AGENDA, AG); 
 Fim-Se; 
 Senão Imprima(“Nome: “, ALT.Nome, “ não existe”); 
 Fim-Se; 
 Feche(AGENDA); 
 Fim; 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 31 de 35 
 
Exemplo 4: Exclusão 
 Algoritmo Arq_Exclui; 
 {Realiza uma exclusão lógica de um registro, marcando o registro como 
 excluído, colocando um “*” no campo “Exc”} 
 Tipo ragen = registro 
 Caracter: Exc, Nome; 
 Inteiro: Tel; 
 Fim-registro; 
 Arquivo: AGENDA de ragen; 
 ragen: AG; 
 ragen: ALT; 
 Inicio 
 Abra(AGENDA); 
 Leia(ALT.Nome); 
 Leia (AGENDA, AG); 
 Enquanto Não Fda(AGENDA) e (AGENDA.Nome <> ALT.Nome ou 
 AGENDA.Exc = “*”) faça 
 Leia (AGENDA, AG); 
 Fim-Enquanto; 
 Se AGENDA.Nome = ALT.Nome e AGENDA.Exc <> “*” 
 Então Imprima (AG.Nome, AG.Tel); 
 Imprima (“Deseja excluir? – S/N”); 
 Leia (SN); 
 Se SN = “S” or SN = “s” 
 Então AG.Exc  “*”; 
 Posição(AGENDA, ArqPos(AGENDA) - 1); 
 Grave (AGENDA, AG); 
 Fim-Se; 
 Senão Imprima(“Nome: “, ALT.Nome, “ não existe”); 
 Fim-Se; 
 Feche(AGENDA); 
 Fim; 
6.3.4 – Organização direta: 
 Os registros de um arquivo são numerados sequêncialmente a partir de “0”, ou seja, cada 
registro fica identificado por um número que representa a sua posição em relação ao primeiro 
registro mais 1. 
 
Exemplo: O registro de número 4 é o 5º registro do arquivo, já que o primeiro é o de número 0. 
Temos que 4 + 1 = 5 
 
 O comando Posição (“Identificador 1”, “Identificador 2”) posiciona o ponteiro do arquivo 
cujo nome esta em “Identificador 1” no registro cujo número esta em “Identificador 2”. Desta 
forma, podemos acessar diretamente um registro. Para acessarmos os registros de um arquivo da 
forma direta ou randômica, temos que projetá-lo para isto e dizemos que ele é um arquivo de 
organização direta. 
 Ao projetarmos um arquivo de organização direta, temos que criar, para cada registro, 
uma chave que será formada por um número que o identifique e que será o mesmo número do 
registro físico onde se encontra. 
 
Exemplo: Tomemos por exemplo uma empresa que dá para os seus funcionário códigos 
seqüenciais a partir de 1, sem se repetir. O “código do Funcionário” será a chave do registro e 
sempre que o usarmos no comando “Posição” encontraremos os dados do funcionário no registro 
que possui número igual ao da chave. 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 32 de 35 
 
Exemplo 1: Inclusão 
 Algoritmo Arq_Inclui; 
 {Inclui um registro, todos os seus campos, em um arquivo de acesso direto} 
 Tipo rfun = registro 
 Caracter: Exc, Nome; 
 Inteiro: Cod; 
 Real: Salario; 
 Fim-registro; 
 Arquivo: FUNC de rfun; 
 rfun: ENT; 
 Inicio 
 Abra(FUNC); 
 Leia(ENT.Cod, ENT.Nome, ENT.Salário); 
 ENT.Exc  “ “; 
 Se ENT.Cod > 0 
 Então Posição(FUNC, ENT.Cod); 
 Guarde(FUNC, ENT); 
 Fim-Se; 
 Feche(FUNC); 
 Fim; 
Exemplo 2: Consulta 
 Algoritmo Arq_Consulta; 
 {Consulta um registro em arquivo de acesso direto} 
 Tipo rfun = registro 
 Caracter: Exc, Nome; 
 Inteiro: Cod; 
 Real: Salário; 
 Fim-registro; 
 Arquivo: FUNC de rfun; 
 rfun: FUN, CON; 
 Inicio 
 Abra(FUNC); 
 Leia(CON.Cod); 
 Posição(FUNC, CON.Cod); 
 Leia (FUNC, FUN); 
 Se FUN.Exc = “ “; 
 Então Imprima(FUN.Cod, FUN.Nome, FUN.Salário); 
 Senão Imprima(“Registro excluído”); 
 Fim-Se; 
 Feche(FUNC); 
 Fim; 
Exemplo 3: Altera 
 Algoritmo Arq_Altera; 
 {Altera campos de um registro em arquivo de acesso direto} 
 Tipo rfun = registro 
 Caracter: Exc, Nome; 
 Inteiro: Cod; 
 Real: Salário; 
 Fim-registro; 
 Arquivo: FUNC de rfun; 
 rfun: FUN, ALT; 
 caracter: SN; 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 33 de 35 
 
 Inicio 
 Abra(FUNC); 
 Leia(ALT.Cod); 
 Posição(FUNC, ALT.Cod); 
 Leia (FUNC, FUN); 
 Se FUN.Exc = “ “; 
 Então Imprima(FUN.Cod, FUN.Nome, FUN.Salário);Imprima (“Deseja alterar? – S/N”); 
 Leia (SN); 
 Se SN = “S” or SN = “s” 
 Então Leia(ALT.Nome, ALT.Salário); 
 Se ALT.Nome <> “ “ 
 Então FUN.Nome  ALT.Nome; 
 Fim-Se; 
 Se ENT.Salário <> “ “! 
 Então FUN. Salário  ALT. Salário; 
 Fim-Se; 
 Posição(FUNC, FUN.Cod); 
 Grave (FUNC, FUN); 
 Fim-Se; 
 Senão Imprima(“Registro excluído”); 
 Fim-Se; 
 Feche(FUNC); 
 Fim; 
Exemplo 4: Exclui 
 Algoritmo Arq_Exclui 
 {Exclui logicamente um registro em arquivo de acesso direto} 
 Tipo rfun = registro 
 Caracter: Exc, Nome; 
 Inteiro: Cod; 
 Real: Salário; 
 Fim-registro; 
 Arquivo: FUNC de rfun; 
 rfun: FUN, EXC; 
 caracter: SN; 
 Inicio 
 Abra(FUNC); 
 Leia(EXC.Cod); 
 Posição(FUNC, EXC.Cod); 
 Leia (FUNC, FUN); 
 Se FUN.Exc  “ “; 
 Então Imprima(FUN.Cod, FUN.Nome, FUN.Salário); 
 Imprima (“Deseja excluir? – S/N”); 
 Leia (SN); 
 Se SN = “S” or SN = “s” 
 Então FUN.Exc  “*”; 
 Posição(FUNC, EXC.Cod); 
 Grave (FUNC, FUN); 
 Fim-Se; 
 Senão Imprima(“Código: “,FUN.Cod, “ não existe”); 
 Fim-Se; 
 Feche(FUNC); 
 Fim; 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 34 de 35 
 
6.4 – Exercícios 
 
1 – Acrescente o campo “Sexo” no Arquivo Agenda. Faça um algoritmo que lê sequencialmente 
cada registro do Arquivo Agenda e crie dois outros arquivos: um com as pessoas do sexo 
masculino e o outro com as do sexo feminino. 
 
2 – Faça um algoritmo que imprima todos os registros de cada um dos arquivos criados no 
exercício anterior. 
 
3 – Faça um algoritmo que lê sequencialmente um arquivo de clientes de uma loja que está 
desordenado e inclui cada registro lido, randomicamente, em um novo arquivo criado no 
programa. Ambos os arquivos têm o código do cliente como chave e possui os campos: Código 
(inteiro), Nome (caracter), Telefone (inteiro), Endereço (caracter). O novo arquivo estará 
ordenado pelo código do cliente. 
 
4 – Faça um algoritmo que lê sequencialmente o arquivo criado no exercício anterior e cria um 
novo arquivo que conterá todos os registro do arquivo de Clientes mais os dados de um novo 
cliente que será lido pelo teclado. O novo arquivo continuará ordenado pelo código do cliente. 
 
 5 – Refaça o algoritmo do exercício anterior fazendo a inclusão do novo registro 
randomicamente. 
 
 
 
ESTRUTURAS DE DADOS I 
Roberto Luís M. P. Castro Página 35 de 35 
 
 
Bibliografia 
 
FARRER, H. et al. Algoritmos Estruturados, Rio de Janeiro: L TC, 1999. 
FORBELLONE, André Luiz Villar, EBERSPACHER, Henri Frederico. Lógica de 
Programação. São Paulo, SP: Makron Books, 2000. 
GUIMARÃES, Angelo M., LAGES, Newton A.C. Algoritmos e Estrutura de dados. Rio de 
Janeiro, RJ: LTC, 1994. 
MANZANO, José Augusto N. G., YAMATUMI, Y. Wilson, Programando em Turbo Pascal 
7.0: guia prático de orientação e desenvolvimento. São Paulo, SP: Érica, 2001 
PINTO, Wilson S.. Introdução ao Desenvolvimento de Algoritmos e Estrutura de Dados. 
São Paulo, SP: Érica, 1990. 
SZWARCFITER, J. Luiz e MARKENZON, Lilian. Estrutura de Dados e seus Algoritmos. 
Editora LTC, 1997. 
VELOSO, Paulo. Estruturas de Dados. Editora Campus, 1998. 
VILLAS, M. V. et al. Estrutura de dados: conceitos e técnicas de implementação. Rio de 
Janeiro: Campus, 1993.