INTEIROS BINÁRIOS E DECIMAIS

O CONCEITO DE IMPLEMENTAÇÃO
Até agora, discutimos os tipos de dados como um método de interpretação
do conteúdo da memória de um computador. O conjunto de tipos de dados
nativos que um computador pode suportar é determinado pelas funções
incorporadas em seu hardware. Entretanto, podemos visualizar o conceito
de "tipo de dado" sob uma perspectiva totalmente diferente; não em termos
do que um computador pode fazer, mas em função do que o usuário quer
fazer. Por exemplo, se alguém quiser obter a soma de dois inteiros, esse
usuário não se importará muito com o mecanismo detalhado pelo qual essa
soma será obtida. O usuário está interessado em manipular o conceito
matemático de "inteiro", não em manipular bits do hardware. O hardware
do computador pode ser usado para representar um inteiro e só será útil
para esse propósito se a representação tiver sucesso.
Quando o conceito de "tipo de dado" é dissociado dos recursos do
hardware do computador, um número ilimitado de tipos de dados pode ser
considerado. Um tipo de dado é um conceito abstrato, definido por um
conjunto de propriedades lógicas. Assim que um tipo de dado abstrato é
definido e as operações válidas envolvendo esse tipo são especificadas,
podemos implementar esse tipo de dado (ou uma aproximação). Uma
implementação pode ser uma implementação de hardware, na qual o
circuito para efetuar as operações necessárias é elaborado e construído como
parte de um computador; ou pode ser uma implementação de software,
na qual um programa consistindo em instruções de hardware já existentes
é criado para interpretar strings de bits na forma desejada e efetuar as
operações necessárias. Dessa maneira, a implementação de software inclui
uma especificação de como um objeto do novo tipo de dado é representado
por objetos dos tipos de dados já existentes, além de uma especificação de
como esse objeto será manipulado em conformidade com as operações definidas
para ele. No restante deste livro, o termo "implementação" será usado
no sentido de "implementação de software".
12 Estruturas de Dados Usando C Cap. 1
UM EXEMPLO
Ilustraremos esses conceitos com um exemplo. Vamos supor que o hardware
de um computador contenha uma instrução:
MOVE (origem, dest, compr)
que copia uma string de caracteres de bytes com o tamanho representado
por compr a partir de um endereço especificado por origem para um endereço
especificado por dest. (Apresentamos instruções do hardware com letras
maiúsculas. O tamanho deve ser especificado por um inteiro e, por essa razão,
nós o indicamos com letras minúsculas, origem e dest podem ser especificados
por identificadores que representam posições de armazenamento.) Um exemplo
dessa instrução é MOVE(a,b,3), que copia os três bytes começando na
posição a para os três bytes começando na posição 6.
Observe os papéis distintos desempenhados pelos identificadores a
e b nessa operação. O primeiro operando da instrução MOVE é o conteúdo
da posição especificada pelo identificador a. O segundo operando, entretanto,
não é o conteúdo da posição b, uma vez que esse conteúdo é irrelevante para
a execução da instrução. Em substituição, a própria posição é o operando
porque ela especifica o destino da string de caracteres. Embora um identificador
sempre represente uma posição, é comum o uso de um identificador
como referência ao conteúdo dessa posição. Sempre ficará evidente pelo
contexto se um identificador está referenciando uma posição ou seu conteúdo.
O identificador que aparece como primeiro operando de uma instrução
MOVE refere-se ao conteúdo de memória, enquanto o identificador que
aparece como segundo operando indica uma posição.
Além disso, partimos da premissa de que o hardware do computador
contém as usuais instruções aritméticas e de desvio, que indicamos usando
a notação ao estilo C. Por exemplo, a instrução:
z = x + y;
interpreta o conteúdo dos bytes nas posições x e y como inteiros binários,
soma-os e insere a representação binária de sua soma no byte na posição z.
(Não operamos sobre inteiros maiores que um byte e ignoramos a possibilidade
de sobrecarga.) Nesse caso, mais uma vez x ey são usados como referências a
conteúdos de memória, enquanto z é usado como referência a uma posição de
memória, mas a interpretação correta é evidenciada pelo contexto.
Cap. 1 Introdução às estruturas de dados 13
Ocasionalmente, é necessário acrescentar uma quantidade num
endereço para obter outro endereço. Por exemplo, se a é uma posição na
memória, é possível referenciar a posição quatro bytes à frente de a. Não
podemos referir-nos a essa posição como a + 4, uma vez que essa notação é
reservada ao conteúdo inteiro da posição a + 4. Sendo assim, introduzimos
a notação a[4] como uma referência a essa posição. Apresentamos também
a notação a[x] para referenciar o endereço dado pela soma do conteúdo dos
inteiros binários do byte em x com o endereço a.
A instrução MOVE exige que o programador especifique o tamanho
da string a ser copiada. Dessa forma, seu operador é uma string de caracteres
de tamanho fixo (isto é, o tamanho da string deve ser conhecido). Uma string
de tamanho fixo e um inteiro binário com tamanho em bytes podem ser
considerados tipos de dados nativos dessa máquina particular.
Vamos supor que precisemos implementar strings de caracteres de
tamanhos variáveis nessa máquina. Ou seja, permitiremos que os programadores
usem uma instrução:
MOVEVAR(origem, dest)
para deslocar uma string de caracteres da posição especificada por origem
para a posição representada por dest, sem precisar determinar qualquer
tamanho.
Para implementar esse novo tipo de dado, devemos primeiro determinar
como ele será representado na memória da máquina e, em seguida,
indicar como essa representação será manipulada. Evidentemente, é necessário
conhecer a quantidade de bytes que deve ser deslocada para executar
essa instrução. Como a operação MOVEVAR não especifica esse número, ele
precisa estar contido dentro da representação da própria string de caracteres.
Uma string de caracteres de tamanho variável, com o tamanho l, pode ser
representada por um conjunto contíguo de / + 1 bytes (l < 256). O primeiro
byte contém a representação binária do tamanho / e os bytes restantes
contêm a representação dos caracteres na string. As representações de três
strings como essas aparecem ilustradas na Figura 1.1.2. (Observe que os
dígitos 5 e 9 nessa figura não substituem os padrões de bits que representam
os caracteres '5' e '9', mas os padrões 00000101 e 00001001 [presumindo-se
oito bits para um byte], que representam os inteiros cinco e nove. De modo
semelhante, o 14 na Figura 1.1.2c substitui o padrão de bits 00001110. Note
também que esta representação é muito diferente do modo como as strings
de caracteres são realmente implementadas em C.)
14 Estruturas de Dados Usando C Cap. 1
O programa para implementar a operação de MOVEVAR pode ser
escrito como segue (i é uma posição de memória auxiliar):
MOVE(origem, d e s t , 1 ) ;
f o r ( i = l ; i < d e s t ; i++)
MOVE(origem[i], d e s t [ i ] , 1 ) ;
De maneira semelhante, podemos implementar uma operação
CONCATVAR(cl, c2, c3) para concatenar duas strings de caracteres de
tamanho variável nas posições cl e c2, e colocar o resultado em c3. A Figura
1.1.2c ilustra a concatenação das duas strings das Figuras 1.1.2a e b:
(a)
(b)
(c)
Figura 1.1.2 Strings de caracteres de tamanho variável.
/* move o comprimento */
z = c l + c 2 ;
MOVE(z, c 3 , 1 ) ;
/* move a primeira string */
for (i = 1; i <= c l ; MOVE(cl[i], c 3 [ i ] , 1);
/* move a segunda string */
for ( i = 1; i <= c2) {
x = c l + i ;
M0VE(c2[i], c3[x], 1);
} /* fim for */
5 H E L L O
9 E V
LU
R Y B O D Y
14 H E L L O E V E R Y B O D Y
Cap. 1 Introdução às estruturas de dados 15
Entretanto, uma vez que a operação de MOVEVAR esteja definida,
CONCATVAR pode ser implementada, usando MOVEVAR, como segue:
MOVEVAR(c2, c 3 [ c l ] ) ; / * move a segunda string */
MOVEVAR(cl, c 3 ) ; /* move a primeira string */
z = cl + c2; /* atualiza o tamanho do resultado */
M O V E ( z , c 3 , 1 ) ;
A Figura 1.1.3 ilustra as fases dessa operação sobre as strings da
Figura 1.1.2. Embora esta última versão seja mais curta, na verdade ela não
é mais eficiente, porque todas as instruções usadas na implementação de
MOVEVAR são executadas cada vez que MOVEVAR é usada.
A instrução z = cl + c2 em ambos os algoritmos anteriores é de
particular interesse. A instrução de adição opera independentemente do uso
de seus operandos (nesse caso, partes das strings de caracteres de tamanho
variável). A instrução é elaborada para tratar seus operandos como inteiros
de byte único, a despeito de qualquer outro uso que o programador determine
para eles. De modo semelhante, a referência a c3[cl] é para a posição cujo
endereço é dado pela soma do conteúdo do byte na posição cl com o endereço
c3. Sendo assim, o byte em cl é considerado armazenando um inteiro binário,
embora ele seja também o início de uma string de caracteres de tamanho
variável. Isso ilustra o fato de que um tipo de dado é um método de tratar o
conteúdo de memória e que esse conteúdo não tem um valor intrínseco.
Observe que essa representação de strings de caracteres de tamanho
variável permite somente strings cujo tamanho seja menor ou igual ao maior
inteiro binário que caiba num único byte. Se um byte tem oito bits, isso
significa que a maior string terá 255 (ou seja, 28"1) caracteres. Para permitir
strings mais extensas, deve-se escolher uma representação diferente e criar
um novo conjunto de programas. Se usarmos essa representação de strings
de caracteres de tamanho variável, a operação de concatenação será inválida
se a string resultante tiver mais de 255 caracteres. Como o resultado de uma
operação como essa é indefinido, uma ampla variedade de ações pode ser
implementada caso essa operação seja experimentada. Uma possibilidade é
usar somente os 255 primeiros caracteres do resultado. Outra possibilidade
é ignorar totalmente a operação e não deslocar nada para o campo do
resultado. Existe também a opção de imprimir uma mensagem de advertência
ou de pressupor que o usuário queira chegar a qualquer resultado que o
implementador determinar.
16 Estruturas de Dados Usando C Cap. 1
Figura 1.1.3 As operações de CONCATVAR.
C1
C2
C3 C3[C1]
(a) MOVEVAR (C2, C3[C1]);
(b) MOVEVAR (C2, C3);
C3
Z
C3
5 H E L L O
9 E V E R Y B O D Y
9 E V E R Y B O D Y
5 H E L L O E V E R Y B O D Y
14
14 H E L L O E V E R Y B O D Y
(c) Z = Cl + C2; MOVE (Z, C3, 1);
Cap. 1 Introdução às estruturas de dados 17
Na verdade, a linguagem C usa uma implementação totalmente
diferente de strings de caracteres, que evita esta limitação sobre o tamanho
da string. Em C, todas as strings terminam com um caractere especial, ' \ 0 ' .
Este caractere, que nunca aparece dentro de uma string, é automaticamente
introduzido pelo compilador no final de cada string. Como o tamanho da
string não é conhecido antecipadamente, todas as operações de strings devem
proceder de um caractere por vez até que ' \ 0 ' seja encontrado.
O programa para implementar a operação de MOVEVAR, sob esta
implementação, pode ser escrito assim:
i = 0;
while (source[i] != '\0') {
MOVE(source[i], d e s t [ i ] , 1);
i++;
}
d e s t [ i ] = '\O';
/* encerra a string de destino com '\0' */
Para implementar a operação de concatenação, CONCATVAR(cl ,c2,c3),
podemos escrever:
i = 0;
/* move a primeira string */
while ( c l [ i ] != '\O') {
MOVE(cl[Í], c 3 [ i ] , 1);
i++;
}
/* move a segunda string */
j = 0;
while ( c 2 [ j ] != '\0')
M O V E ( C 2 [ j + + ] , c 3 [ i + + ] , 1 ) ;
/* encerra a string de destino com um \0 */
c 3 [ i ] = ' \ 0 ' ;
Uma desvantagem da implementação de strings de caracteres de C é que o
tamanho de uma string de caracteres não está prontamente disponível sem
avançar na string um caractere por vez até encontrar um ' \ 0 ' . Isto é mais
do que compensado pela vantagem de não haver um limite arbitrário imposto
sobre o tamanho da string.
Assim que for definida uma representação para objetos de determinado
tipo de dado e forem escritas as rotinas para operar sobre esta
representação, o programador poderá usar este tipo de dado para solucionar
18 Estruturas de Dados Usando C Cap. 1
problemas. O hardware original da máquina mais os programas para implementar
tipos de dados mais complexos do que os fornecidos pelo hardware
podem ser considerados uma máquina "melhor" do que a que consiste no
hardware isoladamente. O programador da máquina original não precisa
preocupar-se com o modo como o computador é projetado e com o circuito
usado para executar cada instrução. O programador só precisa conhecer as
instruções disponíveis e como essas instruções podem ser usadas. De modo
semelhante, o programador que usar a máquina "estendida" (consistindo em
hardware e software), ou o "computador virtual", como citado ocasionalmente,
não precisará preocupar-se com os detalhes da implementação dos
diversos tipos de dados. Tudo o que o programador precisa saber é como eles
podem ser manipulados.