ESTRUTURA DE DADO1

Prévia do material em texto

ESTRUTURA DE DADOS, VETOR E MATRIZ
	Com os estudos realizados até agora, aprendemos que para toda informação que necessitamos para um determinado processamento, é necessário ter uma variável para levar e ou trazer a informação para/da memória principal. Percebe-se que se essa fosse a única maneira de trabalhar com informações, a solução de alguns problemas ficaria muito difícil de descrever. Imaginemos todos os alunos de uma turma, e que queiramos listá-los com as respectivas notas em ordem alfabética. A solução deste problema, independente do número de alunos da turma, necessitará que armazenemos o nome de todos os alunos para depois ordená-los.
	Para resolver o problema acima, e outros que necessitem que trabalhemos com grande quantidade de informações, introduziremos o conceito de estrutura que dados que nada mais é do que um conjunto de informações. 
	
VETOR
	É um conjunto de informações de mesmo tipo, ou seja, as informações vão para a MP ou vem da MP através de uma única variável. Vetores são estruturas de dados homogêneas (mesmo tipo) de apenas uma dimensão (unidimensional). A figura abaixo representa graficamente um vetor.
	
Ou seja;
	Índice
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	elemento
	1°
	2°
	3°
	4°
	5°
	6°
	7°
	8°
	9°
	10°
	variável
	NOME[1]
	NOME[2]
	NOME[3]
	NOME[4]
	NOME[5]
	NOME[6]
	NOME[7]
	NOME[8]
	NOME[9]
	NOME[10]
	informação
	Vivi
	Abel
	Juca
	Zeca
	Lulu
	Beto
	Nico
	Mane
	Zico
	Lili
	
A notação que será utilizada para trabalhar com vetores nos algoritmos, tomando o exemplo da figura será:
VAR NOME: vetor[1..10] de caractere[10] 
{a variável NOME é um vetor de 10 informações do tipo caractere cujos índices serão 1,2,3,4,5,6,7,8,9,10}
Início
 NOME[ 1 ] ←´Vivi´ {leve para a MP Vivi na primeira posição do vetor}
.
.
 Mostre NOME[ 7 ] {irá mostrar Zico}
ÍNDICE
	O índice indica em qual posição do vetor a informação ficará armazenada. Fazendo uma analogia com uma rua teríamos que, o nome da rua seria o nome do vetor, os números das casas seriam os índices e as pessoas nas casas seriam as informações, ou seja, para chegar à informação, preciso do nome da rua (vetor) e o número da casa (índice).
	O índice tem que ser uma informação de tipo numérica inteira.
	O índice pode ser indicado por:
Uma constante; NOTA [5] ← 87;
Uma variável; leia nota [a];
Uma expressão; FREQ [ no1 div 10] ← FREQ [ no1 div 10] + 1(cujo resultado tem que ser um número inteiro);
Outro vetor; mostre dezena[ vet [3] ] ( 1° verifica qual o conteúdo da 3ª posição do vetor vet, para depois mostrar o conteúdo do vetor dezena indicado por vet).
	Exemplo: 
FUP que leia dez números e mostre-os na ordem inversa da leitura.
Solução sem o conceito de estrutura de dados:
Var a,b,d,e,f,c,g,h,i,j : inteiro { 10 variáveis, uma para cada número}
Início
 Leia a,b,c,d,e,f,g,h,i,j { lê os 10 números e leva para MP associando as variáveis}
 Mostre j,i,h,g,f,e,d,c,b,a { Mostra o conteúdo da MP na ordem inversa da leitura}
Fim
 
	A solução apresentada acima ficaria inviável se a quantidade de números a serem lidas fosse muito grande (dez mil, por exemplo).
Solução com o conceito de estrutura de dados (VETOR)
Var num: vetor[1..10] de inteiro {declara que a variável num, é um vetor de 10 posições com índices variando de 1 até 10}
 a,b:inteiro
 Início
 faça de a ←1até 10
 leia num[a] {lê os 10 num. e leva para MP colocando cada num. em uma posição da variável num}
 faça de b ←10 até 1 de -1
 mostre num[b] {mostra o conteúdo da MP na ordem inversa pois começa por num[10]}
Fim
	Se for necessário aumentar para dez mil números, bastaria substituir todos os 10 da solução acima, por 10000.
	MATRIZ
	Suponha que queiramos levar para MP o nome de todos os alunos do turno da manhã de uma determinada escola, por sala. Para acessar depois qualquer um dos alunos, não basta apenas saber qual a posição dele dentro de uma sala, é necessário também, saber em qual das salas ele está.
	Para que a solução do problema fique mais fácil, usaremos dois índices para individualizar a informação (aluno), um índice indicará a sala e o outro a posição do aluno dentro da sala.
	Sempre que o vetor possuir mais de um índice, diremos que é uma matriz, logo, matriz é uma estrutura de dados homogênea (informações de mesmo tipo) que possui mais de um índice para individualizar a informação
NOME
	
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	1
	Zé
	Juca
	Mané
	Lelé
	Lalá
	Bela
	Eva
	Ivo
	Nino
	Raí
	Pepe
	Xico
	Abel
	Boco
	Cara
	2
	Mano
	Dida
	Fafá
	Giba
	Jaja
	Kaká
	Lico
	Manu
	Nana
	Oto
	Popo
	Rafa
	Tetê
	Tita
	Tata
	3
	Deda
	Lulu
	Lima
	Ava
	Xuxa
	Neno
	Bico
	Café
	Zaza
	Sasá
	Cipó
	Juba
	Dado
	Love
	Bida
	4
	Dedé
	Luma
	Céu
	Fofo
	Fofa
	Gato
	Gata
	Luca
	Capa
	Xuxu
	Velo
	Helio
	Helia
	Nona
	Pepeu
 
 Índices
	Como no exemplo de vetor, as informações estão em azul. A notação que será utilizada para trabalhar com vetores nos algoritmos, tomando o exemplo da figura acima será:
Var NOME: VETOR[1..4,1..15] DE CARACTERE[10] {matriz de 4 linhas por 15 colunas}
{A variável NOME é uma matriz que possui os índices
 	 1,1; 1,2; 1,3; 1,4; 1,5; 1,6; 1,7;...; 1,15
 2,1; 2,2; 2,3; 2,4; 2,5; 2,6; 2,7;...; 2,15
					 . . . . . . . . . . . . . . . . . . . . 
					 . . . . . . . . . . . . . . . . . . . . 
 4,1; 4,2; 4,3; 4,4; 4,5; 4,6; 4,7;...; 4,15}
Início
.
Nome[3,5] ← ´Xuxa´
.
Mostre nome[2,11] {será mostrado Popo}
	Generalizando, matriz é uma estrutura de dados homogênea (informações de mesmo tipo) que necessita de mais de um índice para individualizar a informação.
	Exemplo: FUP que gere uma matriz 10 x 6, sendo que cada elemento deve ser o resultado da multiplicação dos dois índices que indicam a sua posição dentro da matriz. Após gerar a matriz, mostrá-la.
Var mat: vetor[1..10,1..6] de inteiro
 a,b : inteiro
Início
 Faça de a ← 1 até 10
 Faça de b ← 1 até 6
 Mat[a,b] ← a*b
 Faça de b ← 1 até 10
 Faça de b ← 1 até 6
 Mostre Mat[a,b]
Fim 
	Supondo que se queira colocar, em uma única variável, o nome de qualquer aluno de um determinado Estado, identificados por sala, turno, campus, escola e cidade. Considerar que temos 30 cidades no Estado; 20 escolas, no máximo, por cidade; 10 campi, no máximo, por escola; 3 turnos; no máximo 20 salas por campi e no máximo 60 alunos por sala. A declaração da variável ficaria:
Var alun:vetor[1..30,1..20, 1..10, 1..3, 1..20, 1..60] de caractere
 Cid, esc, cam, tur, sal, alu: inteiro
Início
..
..
Alun[4,3,2,3,4,45] ← ´MARCELINO´
{ou seja, MARCELINO, seria o aluno na posição 45 da sala 4 do turno 3 do 2° prédio da 3ª escola da 4ª cidade}
Mostre alun[22,15,8,2,16,4]
{ou seja, ........................................................................................, individualize a informação seguindo o exemplo de MARCELINO (qual cidade, qual escola...)}
�
1�
2�
3�
4�
5�
6�
7�
8�
9�
10�
�
NOME�
Vivi�
Abel�
Juca�
Zeca�
Lulu�
Beto�
Nico�
Mane�
Zico�
Lili�
�
					
				Informações		Índices
Nome da variável que representa o vetor