5.1 Sequências de Dados

Você percebe como a cada passo estamos criando entidades cada vez mais abstratas? Um bit pode ter seu componente físico, mas uma sequência de 4 bytes representa um número inteiro apenas porque é essa abstração que associamos com eles. Nada impede, portanto, de dar continuidade a este processo de abstração a partir dos tipos primitivos do computador.

A ideia aqui é usar a composição de tipos primitivos e, por meio desse processo, criar tipos mais complexos. Este processo eleva o nível de abstração de nossos algoritmos, permitindo avançarmos na construção de programas mais complexos.

Está na hora de você ser apresentado a mais algumas abstrações valiosas.

 

5.1 SEQUÊNCIAS DE DADOS

Programas são escritos para criar um modelo computacional de um problema do mundo real. Escolhemos determinados aspectos do mundo real que sejam relevantes para nosso problema e os representamos com os recursos disponíveis no computador. Seria impossível representar todas as variáveis do mundo real dentro do computador. O mundo real é complexo demais. Todo modelo computacional é uma simplificação do mundo.

No capítulo anterior, vimos ações que podem ser executadas sobre dados primitivos, no caso, números. O cálculo da média de notas seria um desses problemas.

Assim, no programa 3.1, calculamos a média de duas notas, decidindo, em seguida, se o aluno ficou em prova final. Neste programa foram criadas duas variáveis, nota1 e nota2, que guardavam as notas para serem usadas no cálculo.

Mas o que aconteceria se você tivesse de calcular a média de 10

notas? Criaria 10 variáveis, indo de nota1 até nota10? Convenhamos que não seria muito prático. Seria ainda pior se você tivesse de fazer este cálculo para uma turma inteira. Como resolver esse problema?

Para isso, é necessário ter alguma forma de manipular diversos

dados como se fossem uma única entidade, porém mesmo assim de maneira que se possa ter acesso aos dados individualmente.

Um número ocupa uma área da memória do computador. No

programa 3.1 associamos a variável nota1 a uma área de memória suficiente para conter um número, e nota2 com outra área de

memória equivalente, como na representação da Figura 5.1.

 

Figura 5.1 nota1 e nota2.

 

Perceba que não importa muito em que posição da memória

estão localizados os objetos indicados por esses dois nomes. Contudo, o nosso problema é indicar dez valores de notas sem ter de criar dez nomes diferentes. Como resolver este problema? Uma forma é usar uma área de memória com espaço suficiente para conter dez notas, uma após a outra, e fazer um identificador notas

referenciar a posição inicial dessa área, como na Figura 5.2.

O problema de ter acesso a cada elemento pode ser resolvido

atribuindo-se um índice a cada posição. Este índice vem entre colchetes, logo após o nome da variável que referencia a estrutura. Deste modo, quando queremos manipular a primeira nota, escrevemos notas[0]; a segunda, notas[1]; a terceira, notas[2]; até que a décima viria a ser notas[9].

Figura 5.2 Variável notas.

 

 

Fato 5.1 – Por que o primeiro índice é zero?

Você deve ter notado algo estranho: na notação usada para indicar cada elemento de

notas, o índice do primeiro elemento é zero! “Por que não começar a numerar os

elementos com 1 e terminar em 10?” A nal, as pessoas começam a contar a partir de

um, não de zero. O primeiro colocado em uma corrida recebe o número 1, não o zero.

Parece mais lógico chamar o primeiro elemento da estrutura de notas[1] e

não notas[0], enquanto o último seria notas[10] e não notas[9].

Porém, a maioria das linguagens de programação adota o índice inicial como zero. Por

quê?

Figura 5.3 Quem é o primeiro?

 

A resposta mais simples é que isso é feito em função da forma como as linguagens

de programação são projetadas. O índice indica a distância do elemento do início da

estrutura. Assim, o primeiro elemento está logo no início, distante, portanto, zero

elementos; enquanto o último está 9 posições distante do início.

Uma resposta mais elaborada começa quando se percebe um teorema básico da

Matemática:

“ N Para qualquer base b, os primeiros b números inteiros positivos são representados por exatamente N dígitos.”

 

Isto só é verdade se, e somente se, a contagem se iniciar com zero, com seus

números indo de 0 até N-1 b, e não com 1, que teria números indo de 1 até N b.

Para começar com 1, teríamos de perder um endereço de memória, aquele

composto apenas por zeros, e precisaríamos de mais um dígito para o endereçamento.

Isto é facilmente visto com números binários (base b = 2). Para representar 8 (bN)

endereços precisamos de 3 (N) bits. Mas isso só é possível se o primeiro endereço for

zero. Se o primeiro endereço for 1, o oitavo elemento precisaria de 4 bits (1000) para

ser endereçado, no entanto, começando com zero, necessita de apenas 3 bits (111).

Figura 5.4 Começar em zero ou em um?

 

Se você ainda sente di culdades com o sistema binário, basta pensar em decimal.

Com um dígito decimal você endereça dez posições, entre 0 e 9, mas para começar em

1, precisaria endereçar entre 1 e 10, usando mais um dígito decimal.

Esse teorema é a base do endereçamento dos sistemas digitais e foi adotado pelas

linguagens de programação em geral.

Porém, você deve estar pensando: para facilitar a vida do programador, o

compilador ou interpretador da linguagem poderia facilmente converter um índice 1

em um índice 0 e, consequentemente, o índice 8 no índice 7, economizando um bit de

endereçamento. Isto é verdade, porém implicaria uma tradução de endereços para

toda a operação com índices, com o custo associado a esse cálculo.

O uso do índice inicial zero facilita a tradução do que o programador escreve em

relação àquilo que o sistema irá executar, sem precisar de uma conversão de endereços

para cada acesso da estrutura de dados.

 

Essa estrutura de dados é normalmente chamada de vetor ou array, no seu nome em inglês. O vetor, para um programador, não tem o significado matemático ou biológico da palavra, mas se refere a um conjunto de dados. Em geral, este conjunto é homogêneo. Neste caso, isto quer dizer que um vetor se refere a um conjunto de dados de um só tipo. Assim podemos, por exemplo, criar um vetor de números inteiros, no qual todos os elementos são, como você já deve ter deduzido, números inteiros.

Esta estrutura do vetor ocupa uma área de memória contígua,

portanto, o segundo elemento está na memória logo após o primeiro elemento; o terceiro, após o segundo; e assim até que o último elemento esteja após o penúltimo. Um vetor de n elementos inteiros ocupa a memória equivalente a pelo menos n inteiros. Qualquer que seja o tipo de dados armazenados em um vetor, a memória ocupada por este vetor será pelo menos um múltiplo da memória ocupada por um elemento solitário.

Como essa estrutura pode tornar mais eficiente o uso das

informações? Primeiro, se você procura algo em um vetor, basta checar cada elemento, seguindo endereços de memória contíguos. Para acrescentar um elemento no meio do vetor, basta deslocar elementos para criar espaço.

O vetor é uma forma de agrupar dados bem eficiente: temos um

acesso em tempo constante a qualquer elemento do vetor. Ler o elemento da posição 3 ou da posição 1452 toma o mesmo tempo do processador. Quando você quer ler ou escrever o elemento da posição 3, e escreve notas[3], você está dizendo ao computador:

“Pegue o endereço inicial do vetor notas, depois some a este endereço 3 vezes o tamanho do elemento básico do vetor e, finalmente, leia ou escreva nesta posição”.

 

O cálculo do endereço é o mesmo para a posição 1452 ou outra

qualquer, contudo, usando o 1452 no lugar do 3 e, consequentemente, toma o mesmo tempo de processamento. Podemos até dar uma fórmula geral para esse acesso: