0.0.0.13 - Arrays 1

Arrays, arranjos, vetores e matrizes.

Objetivo desta aula:

Apresentar o primeiro tipo abstrato de dados.

links citados durante a aula

M

T

Introdução

Chamamos tipos abstratos de dados (ADT ou TAD) os tipos de dados que não são os primitivos. Arrays e Strings são tipos abstratos presentes na maioria das linguagens de programação. Outros tipos podem ser criados pelos usuários ou pelos mantenedores da linguagem. Por exemplo, o tipo que representa datas em C (struct tm no arquivo time.h). No sentido estrito, TAD se refere apenas às variáveis, e não aos métodos.

  struct tm                                                                                                
  {                                                                                                   
     int tm_sec;           /* Segundos */      
     int tm_min;           /* Minutos */                            
     int tm_hour;          /* Horas */                       
     int tm_mday;          /* Dia do mes */             
     int tm_mon;           /* Meses */                
     int tm_year;          /* Anos  */                       
     int tm_wday;          /* Dia da semana */                 
     int tm_yday;          /* Dia do ano */                        
     int tm_isdst;         /* DST.     [-1/0/1]*/         
  }
  

A extensão do conceito de tipo abstrato, para incluir métodos, ou seja, associar métodos aos dados, originou a idéia de objeto. Como Java é uma linguagem orientada a objetos, torna-se difícil ilustrar o conceito de tipo abstrato, pois Java já parte do conceito estendido.

Os tipos abstratos Arrays ou arranjos representam conjuntos homogêneos (por exemplo números) distintos por sua posição relativa. Estes são usados em computação para representar vetores e matrizes, e são essencialmente a mesma estrutura da informação.

Além do seu uso em física e matemática, para representar pontos, transformações de coordenadas e sistemas de equações, são utilizados para representar listas, imagens, grafos. As imagens que se formam na tela de um computador, independente de serem texto ou imagem, estão armazenadas em uma matriz, fotos digitais também são matrizes. Os algoritmos de roteamento (do GPS) trabalham sobre uma representação da cidade como um grafo.

Funcionamento

Em Java, um array de bytes com cinco elementos é declarado e inicializado com:

   byte[] A={21, 9, 77, 32, 44};
  

O que indica que A é um array (e não um byte) são os colchetes após o tipo. Esse array contém os elementos 21, 9, 77, 32 e 44, que são acessados usando A[0], A[1], A[2],A[3],A[4], tanto para escrita quanto para leitura, ou seja:

   System.out.println (A[3]); // imprime 32
   A[2]=22;   // escreve 22 no lugar de 77
  

Podemos considerar a memória do computador um array (de 2G posições de um byte cada), também iniciando pelo índice zero.

Os elementos de um array são colocados na memória de forma contígua, ou seja, o elemento zero é imediatamente anterior ao elemento um, que é imediatamente anterior ao elemento dois e assim por diante. Supondo que o endereço do elemento de índice zero seja 0x0378 (em hexadecimal)

Endereço	Conteúdo
0x378	21
0x379	9
0x37A	77
0x37B	32
0x37C	44

No caso acima, um endereço da memória armazena exatamente um valor do tipo byte, logo, passar para o próximo elemento equivale a passar para o próximo endereço, mas em outros tipos, como short (2 bytes) ou int (4 bytes), temos que "pular" de dois em dois ou de quatro em quatro. Isso é resolvido automaticamente pelo compilador/máquina virtual.

Este talvez seja o ponto menos intuitivo: em A está armazenada a referência para os dados. Referências são números que são convertidos em endereços de memória.

O comando

int[] A;

informa ao compilador/JVM que deve-se alocar memória para uma variável do tipo int[] com identificador (nome) A. Este tipo é uma referência para um inteiro. Quando não inicializadas, essas variáveis não se referenciam a dados válidos.

O comando

{21, 9, 77, 32, 44};

aloca um bloco de memória e armazena os elementos nesse bloco.

O comando de atribuição armazena na posição de memória cujo endereço corresponde a A, o endereço do bloco de memória.

Assim, A é inicializada com a referência para os dados. Complementando o mapa de memória, suponha que a variável A seja alocada no endereço 0x500. Que valor ela conterá? (resposta na tabela).

Endereço	Conteúdo
0x378	21
0x379	9
0x37A	77
0x37B	32
0x37C	44
...	...
0x500	0x378

Certamente há outras formas de criar e usar arrays e outros tipos abstratos, inclusive formas que prescindem do uso de referências, mas esta solução tem vantagens (a que voltaremos em mais detalhes quando tratarmos sobre objetos):

• Evita cópia desnecessária de grandes quantidades de dados;
• Permite passar dados complexos para dentro e para fora de métodos;
• Fornece uma forma simples e uniforme de tratar atribuições.

Voltando ao array, como acessamos seus elementos? Por exemplo A[2]? Bem, o acessamos tomando o endereço base (0x378) e acrescentando o offset (2* oTamanhoDe(int)), o que resulta em 0x37A. Desta forma, a que offset corresponde o endereço base?

Em geral, quando usamos um array, este será percorrido de alguma forma, e é o programador quem deve definir como isso será feito. Por exemplo, se quisermos escrever na tela o conteúdo de A, poderia ser uma boa resposta:

   {
    byte[] A={21, 9, 77, 32, 44};
    for (int i=0;i<5;i++) {
     System.out.println ("A["+i+"]="+A[i]);
    }
   }
  

Por favor, explique o que o código acima faz, e como.

Próxima parte