UNIDADE I - VETOR

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Conteúdo Programático
Unidade 1 – Tipos Estruturados Homogêneos Unidimensionais 
1.1 Características
1.2 Manipulação de Vetor 
Unidade 2 – Tipos Estruturados Homogêneos Multidimensionais 
2.1 Características
2.2 Manipulação de Matriz 
Unidade 3 – Estrutura de Dados na Construção de Tipos Estruturados 
3.1 Agregados heterogêneos (Registros)
3.2 Agregados homogêneos (Vetor de Registros)
3.3 Conjuntos e listas
Unidade 4 – Métodos de Pesquisa 
4.1 Pesquisa Sequencial
4.2 Pesquisa Binária
4.3 Pesquisa Interpolada 
Unidade 5 – Métodos de Ordenação 
5.1 Método Selection Sort
5.2 Método Insertion Sort
5.3 Método Bubble Sort
5.4 Método Quick-Sort
5.5 Método Merge-Sort
1
Unidade 1 (Vetor)
A declaração de várias variáveis , uma a uma, é suficiente para codificar um programa;
Porém, tal metodologia não é suficiente para resolver TODOS os problemas computacionais;
Ex.: Faça um programa que leia o nome de 500 pessoas e, em seguida, escreva o nome de cada uma.
Você iria declarar e utilizar 500 variáveis? Trabalhoso, não?
Para resolver problemas similares ao descrito acima, utilizamos vetores ou matrizes; 
Tipos estruturados homogêneos unidimensionais
	Algoritmo
		Var NotaAcima: Inteiro;
		 A, B, C, D, E, F, G, H, I, J, Média: Real;
		Início		
 NotaAcima ¬ 0;
		 leia (A,B,C,D,E,F,G,H,I,J);
		 Média ¬ (A + B + C + D + E + F + G + H + I + J)/10;
		 se (A > Média) então 
 NotaAcima ¬ NotaAcima + 1;
		 fimse;
		 . . .
			 . . .
		 se (J > Média) então
 NotaAcima ¬ NotaAcima + 1;
		 fimse;
		 escreva (NotaAcima);
	fimalgoritmo
Exemplo: Quantidade de notas acima da média usando variáveis primitivas simples.
Tipos estruturados homogêneos unidimensionais
Tipos estruturados homogêneos unidimensionais
Os tipos primitivos (inteiro, real, caracter e lógico) não são suficientes para representar todos os tipos de informação.
Particularmente quando temos mais de uma informação relacionada. Ex: Lista dos nomes dos alunos de uma sala, endereço de alguém etc.
Utilizaremos os tipos primitivos para construir outras estruturas de dados mais complexas.
Até agora os problemas eram resolvidos com tipos de dados simples (ou primitivos);
Agora estudaremos os tipos de dados estruturados;
Tipos de Dados Estruturados Homogêneos: sequência de valores de um mesmo tipo.
Vários valores poderão ser armazenados em uma única variável, chamada vetor;
Vetores possuem índices que, pelos quais, poderemos acessar valores armazenados;
Vetores funcionam como tabelas de uma linha e várias colunas:
Ex.: Um vetor de inteiros:
Tipos estruturados homogêneos unidimensionais
0
2
4
1
6
1
1
2
3
4
5
Índice 
Conteúdo 
Cada dado é identificado por um índice i
O acesso a cada elemento do vetor é feito através de uma indexação da variável v. Observamos que, em C, a indexação de um vetor varia de zero a n-1, onde n representa a dimensão do vetor. 
	Assim:
v[0] → acessa o primeiro elemento de v
v[1] → acessa o segundo elemento de v
...
v[9] → acessa o último 
	Mas:
v[10] → está ERRADO (invasão de memória)
Tipos estruturados homogêneos unidimensionais
Devemos observar que utilizamos o endereço de cada elemento do vetor v[i], pois desejamos capturar os valores armazenados no índice do vetor e, v[i+1] representa o (i+1)-ésimo elemento do vetor (elemento da vez ou próximo elemento).
Observamos que, em Pascal, a indexação de um vetor varia de 1 a N, onde N representa a dimensão do vetor. 
	
	Assim:
v[1] → acessa o primeiro elemento de v
v[2] → acessa o segundo elemento de v
...
v[10] → acessa o último
As Matrizes são construídas analogamente como vetores de vetores.
Tipos estruturados homogêneos unidimensionais
Declaração de um vetor em Algoritmo:
nome_vetor: vetor [1..Tam] de tipo_simples;
Tipo dos dados do conjunto
Dimensão, ou tamanho máximo do conjunto
Palavra chave usada para identificar a declaração de um conjunto (ou array, vetor, matriz,...)
Identificador ou nome do conjunto
Tipos estruturados homogêneos unidimensionais
Em Pascal, um vetor é identificado pela palavra reservada array;
Declaração de um vetor:
	var nome: array [inicio..fim] of tipo;
Em [inicio..fim], devemos definir a posição inicial e final do vetor, separado por ..
Ex.: [1..2], [3..5], [6..10], etc.;
Tipos estruturados homogêneos unidimensionais
OBS: 
O valor do índice inicial deve ser menor que o índice final;
A primeira posição (índice) de um array (vetor) em Pascal é a posição 1;
As posições (índices) são numeradas com valores INTEIROS. Não utilize outro tipo de valor em um índice! 
Tipos estruturados homogêneos unidimensionais
Estrutura de dados fundamentais
Diversas outras estruturas são implementadas usando arrays (vetores);
Em última análise, a própria memória é um array (vetor).
Problemas:
Alocação de memória
Quantas posições deve ter o array (vetor) para uma dada aplicação?
O que fazer se precisarmos mais?
Como inserir um novo dado entre o k-ésimo e o 
(k+1)-ésimo elemento?
Como remover o k-ésimo elemento?
Tipos estruturados homogêneos unidimensionais
Exemplo: declaração de um vetor para armazenar 10 valores numéricos inteiros;
vetor_int: vetor [1..10] de Inteiro;
Exemplo de manipulação:
vetor_int[3]50;	
1
4
2
3
50
7
6
5
8
9
10
Conteúdo:
Índice:
vetor_int
Nome:
Tipos estruturados homogêneos unidimensionais
Como atribuir valores a um vetor?
atribuições em vetor exigem que seja informada em qual de suas posições o valor ficará armazenado;
Exemplo:
Tipos estruturados homogêneos unidimensionais
Como escrever na tela os elementos de um vetor?
Também através dos índices;
Exemplo:
Tipos estruturados homogêneos unidimensionais
Preenchendo e mostrando os elementos de um vetor:
Para preencher um vetor, temos que atribuir valores para cada posição do mesmo;
Para apresentar todos os valores contidos em um vetor, temos que percorrer todas as posições do vetor e obter cada valor correspondente;
Tipos estruturados homogêneos unidimensionais
Como fazer tudo isso de uma maneira mais eficiente?
Deve-se implementar um mecanismo que controle o valor do índice;
Percebe-se que, para percorrer um vetor, a estrutura de repetição FOR se apresenta como um bom recurso;
A estrutura FOR permite contar um valor inicial até um valor final, coincidentemente com os índices de um vetor;
Tipos estruturados homogêneos unidimensionais
	Algoritmo
	Var	
			 VClasse: vetor [1 .. 10] de Real;
		 NotaAcima, X: Inteiro;
 Soma, Média: Real;
	Início	
 Soma ¬ 0; NotaAcima ¬ 0;
		 Para X de 1 até 10 passo 1 faça
			leia ( VClasse[X] );
			Soma ¬ Soma + VClasse[X];
		fimpara;
		Média ¬ Soma / 10;
		Para X de 1 até 10 passo 1 faça
			se ( VClasse[X] > Média )
				então NotaAcima ¬ NotaAcima + 1;
			fimse;
		fimpara;
		escreva (NotaAcima);
	fimalgoritmo
Tipos estruturados homogêneos unidimensionais
Exemplo: Quantidade de notas acima da média usando vetor.
Algoritmo
Var
 vet_notas : vetor [1..30] de Real;
 i: Inteiro;
Inicio
 Para i:=1 até 30 faça
 escreva ('Digite a nota: ');
 leia(vet_notas[i]);
 fimpara;
 Para i:=1 até 30 faça
 escreval ('Nota ['+ i +']: ', vet_notas[i]);
 fimpara;
fimalgoritmo
Tipos estruturados homogêneos unidimensionais
Exemplo: um algoritmo para armazenar a nota bimestral de um total de 30 alunos e ao final informar todas as notas em sequência.
Exercícios
Faça um programa em Pascal que recebe 10 números inteiros e os armazena em um vetor de 10 posições. O programa deverá escrever na tela apenas os valores pares do vetor;
program exercicio1;
uses crt;
var
 vet: array[1..10] of integer;
 i: integer;
begin
 //limpa tela
 clrscr;
 //Entrada de dados
 i:= 1;
 repeat
 write('Digite o valor ', i ,':'); read(vet[i]);
 i:= i + 1;
 until i > 10;
 //Saída da informação
 for i:= 1 to 10 do
 if (vet[i] mod 2 = 0) then
 writeln(vet[i],'
‚ par');
 //pausa
 Writeln('Pressione qualquer tecla para sair...');
 repeat until keypressed;
end.
Exercícios
Faça um programa em Pascal que recebe 10 números inteiros e os armazena em um vetor de 10 posições. O programa deverá trocar todos os valores negativos do vetor por 0. Após a substituição, escrever todo o conteúdo do vetor na tela;
program exercicio1;
uses crt;
var
 vet: array[1..10] of integer;
 i: integer;
begin
 //limpa tela
 clrscr;
 //Entrada de dados
 i:= 1;
 repeat
 write('Digite o valor ', i ,':'); read(vet[i]);
 i:= i + 1;
 until i > 10;
 //trocar valores negativos por ZERO
 for i:= 1 to 10 do
 if (vet[i] < 0) then
 vet[i] := 0;
 //Exibir os valores do vetor com as alterações
 for i:= 1 to 10 do
 writeln('posição ', i, ':', vet[i]);
 //pausa
 Writeln('Pressione qualquer tecla para sair...');
 repeat until keypressed;
end.
Exercícios
Faça um programa em Pascal que recebe 5 números inteiros e os armazena em um vetor X de 5 posições. O programa deverá armazenar o valor/2 de cada posição do vetor X em um vetor Y. Após a substituição, escrever todo o conteúdo dos vetores X e Y na tela;
Exercícios
Faça um programa em Pascal que possua um vetor com 3 nomes armazenados:
	nomes[1] := ‘Jose’;
	nomes[2] := ‘Maria’;
	nomes[3] := ‘Carlos’;
	O programa deverá solicitar a digitação de um nome qualquer, e buscará o nome digitado no vetor de nomes. Caso encontre o nome, escreverá ‘Achei!’; Caso contrário, escreverá ‘Não achei’;