Aula 002

Programação

PRONATEC

Programa Nacional de Acesso ao

Ensino Técnico e Emprego

PRONATEC

Programa Nacional de Acesso

ao Ensino Técnico e Emprego

1. Estrutura de Dados• Programar em qualquer linguagem é criar algoritmos para

trabalhar com dados. • O essencial são os dados, eles são o objetivo da

programação, portanto programas devem ser voltados a trabalhar com dados

• A melhor forma de trabalhar com os dados é utilizar “Dados Estruturados”, ou seja, que tenham em si mesmos já algum tipo de organização ou estrutura

• Logo um bom programa deve utilizar técnicas estruturadas em “dados estruturados”.

• Uma analogia entre diferença de dados simples e dados estruturados é como o uso de um guarda roupas: se as roupas estão jogadas dentro dele de qualquer forma (simples) ou se as mesmas tem uma ordem lógica que facilite o seu manuseio (estruturado).

2. Estrutura de Dados• A organização dos dados em memória permite a

construção de algoritmos mais sofisticados e eficientes do que sem ela

• Dados podem apresentar-se estruturados em duas formas: homogênea e heterogênea

• Homogêneas: são aquelas estruturas onde cada elemento tem o mesmo tipo. Exemplo: vetor,matriz

• Heterogêneas: são aquelas estruturas onde cada elemento pode ter tipos diferentes uns dos outros. Exemplo: registro

• Nesse curso vamos estudar: vetor, matriz e registro

3. Vetores• São estruturas de dados homogêneas

• Consiste em uma seqüência de valores de um mesmo tipo onde cada um pode ser acessado pelo nome do Vetor seguido de abre e fecha colchetes “* +” e entre eles um índice que é um número inteiro indicando qual elemento da seqüência estamos nos referindo

• Em Delphi já existe o tipo de dados “Array” que é definido para conter vetores

• Para declarar um vetor em Delphi faremos desta forma: “var vet:array[1..10] of integer;” aqui declaramos um vetor “vet” com dez inteiros (of integer) cujos índices de acesso vão de 1 a 10. Se quisermos acessar o quinto elemento usamos esta sintaxe: “vet*5+” e podemos tê-lo. Para atribuirmos um elemento fazemos assim: “vet*3+ := 0;” –fazemos o terceiro elemento valer zero.

4. Operações com Vetores• Definir e declarar um vetor em Delphi

• Preencher e ler dados de um vetor

• Mostrar dados do vetor em ordem inversa

• Ordenar os elementos do vetor

• Buscar um elemento no vetor

Declarar um Vetor Preencher VetorVar v:array[1..10] of integer; i:integer;Begin

randomize;for i:=1 to 10 do

v[i] := random(20000);End;Randomize: inicia gerador de números aleatóriosRandom(n:integer):integer; -função que retorna um aleatório inteiro de 0 a N

Ler dados do VetorVar s:string;

Begin

s := ‘ ‘;

for i:=1 to 10 do

s := s+IntToStr ( v[i] );

ShowMessage (s);

End;

Ler dados InvertidosVar s:string;

Begin

s := ‘ ‘;

for i:=10 downto 1 do

s := s+IntToStr ( v[i] );

ShowMessage (s);

End;

Ordenar Vetores• Ordenar um vetor é colocar os seus elementos

em uma sequência crescente ou decrescente de acordo com seus valores

• Ex: V = [5,2,1,0,3,4] Ordenando = [0,1,2,3,4,5]

• Existem diversos algoritmos para ordenar um vetor: bolha, seleção, inserção, quicksort

• Bolha: método mais simples porém o menos eficiente. Percorrer o vetor de N elementos N-1 vezes e a cada vez trazer o menor elemento antes do maior, lembrando uma bolha subindo na água

• Exemplo: v=[3,0,2,1], passo1:[0,2,1,3], passo final:[0,1,2,3]

Algoritmo de Ordenação de Vetor pelo método da Bolha: BubbleSort

Em Pascal / Delphi:

Var aux, i, j, k:integer; v:array[1..100] of integer;

Begin

k := 100-1;

for i:=1 to 100 do begin

j := 1;

while j <= k do begin

if v[j] > v[j+1] then begin

aux := v[j];

v[j] := v[j+1];

v[j+1] := aux;

end;

j := j + 1;

end;

k := k + 1;

end;

End;

Ordenação pelo Método Inserção• Nesse método monta-se um novo vetor destino e a partir do original

vamos transferindo os elementos já ordenando-os de acordo• Vantagem: simplicidade do algoritmo• Desvantagem: gasto elevado de memória e baixa eficiência com relação

a performance

Ordenação pelo Método Seleção• O princípio é a cada passo obter o menor valor do vetor e troca-

lo com o primeiro dos ainda não ordenados• Vantagem: simplicidade de execução• Desvantagem: lento e consome muito recurso de hardware

QuickSort• Divide o vetor em dois e aplica-se a

ordenação QuickSort novamentesobre cada um dos dois, no final aunião de todos os vetores formará ovetor final ordenado

• Vantagem: é o mais rápido de todos

• Desvantagem: por ser recursivo exigemuito recurso de memória do equipamento

Matrizes• Matriz é uma estrutura de Dados Estática e

Homogênea que define um grupo de dados organizado em duas dimensões: linhas X colunas

• Exemplo:

• Em pascal definimos uma Matriz pelo tipo Array de vetores, ou seja, um array de array

• Ex: var Matriz: array[1..5] of array[1..4] of integer;

• Esse comando declara a matriz desenhada logo acima com 5 linhas X 4 colunas de nome Matriz

• Outra forma é criar um tipo “Vetor” e então definir “Matriz” como dependente desse tipo

• Ex: type Vetor = array[1..4] of integer;• Ex: type Matriz = array[1..5] of Vetor;

Acessando Elementos das Matrizes• Uma forma simplificada de declaração em Pascal

ainda pode ser assim:

• Ex: var Matriz: array[1..5,1..4] of integer;

• Todas as declarações criam a mesma estrutura de dados Matriz

• Para acessar um elemento devemos usar o nome da matriz seguido de “* +” com os índices dentro separados por “,”. Exemplo: Matriz*3,2+ é o inteiro “7” no exemplo da matriz já mostrada antes, ou seja elemento da Linha “3” e Coluna “2”.

• Para varrer todos os elementos de uma matriz precisamos de dois comandos “FOR”, um para varrer as linhas e outro para varrer as células de cada linha

Lendo e Mostrando uma Matriz• Montando uma Matriz lendo do Teclado

• Mostrando uma Matriz NxM

Busca em Matriz• Buscando o elemento “x” na Matriz “w” com dimensões “n” x “m”• Retorna “True” se ele está na matriz ou “False” caso contrário

Registros (record)• Estrutura de dados Estática e Heterogênea, ou seja contem

vários dados e cada um pode ser de tipo diferente do outro• Em Pascal / Delphi usamos o comando de tipo “record”

para criar uma estrutura de registro.• Ex: cria um registro “Registro” com as informações de:

nome, fone (texto) e sexo (caracter), data_nascimento(data), e CPF (número inteiro longo)

var Registro : record

nome : string;fone : string;sexo : char;data_nascimento : TDateTime;CPF : longint;

end;

Usando Registro em Pascal• Depois de definir uma variável do tipo registro

podemos acessar seus elementos usando o nome da estrutura seguido de “.” (ponto) e depois o nome do atributo (dado). Usando o exemplo do registro anterior teriamos:

• Exemplos:

• Registro.nome - devolve o nome do registro

• Registro.fone := ‘(34)9192-1234’; - atribui “fone” ao registro “Registro”

• Registro.CPF := 00100200304; - atribui um número de CPF à variável Registro

• Registro.Data_Nascimento; - devolve a data de nascimento em Registro

Combinando Vetores e Registros• Uma das formas mais usadas em Informática para acesso a um arquivo de

dados é criar vários registros com a mesma estrutura, por exemplo um cadastro de cliente podemos ter para cada cliente cadastrado: nome, fone, endereço, cpf

• O tipo desse registro em Pascal seria definido assim:Type

regCliente = recordnome : string;fone : string;endereco : string;cpf : longint;

end;• Agora se desejarmos uma variável que represente um arquivo com espaço

para 100 clientes devemos definir um vetor de elementos do tipo “regCliente”, assim:

• Var arqCliente : array[1..100] of regCliente;• “arqCliente” é um vetor que irá conter até 100 registros de cliente do tipo

“regCliente”, assim para acessar o nome do primeiro cliente do cadastro podemos fazer: arqCliente[1].nome; ou seu cpf: arqCliente[1].cpf; e assim por diante