Introdução a Estruturas de Dados

Introdução a Estruturas de Dados

O estudo de Estruturas de Dados inclui o exame da organização, manipulação e utilização das informações manipuladas por um computador.

Conceitos fundamentais

bit

É a menor unidade de informação manipulada pelo computador, podendo assumir dois valores, 0 ou 1.

O termo bit é a contração de binary digit.

Palavra binária

n bits formam uma palavra binária, a qual pode representar 2ⁿ valores diferentes.

Byte

É o termo clássico utilizado para uma palavra binária de 8 bits, o qual pode representar 2⁸ = 256 combinações diferentes.

Sistemas Numéricos e Aritmética Binária

Os Sistemas Numéricos são utilizados para representar valores numéricos.

Os sistemas numéricos mais utilizados na informática são o decimal, binário, octal e hexadecimal:

• O sistema decimal, com 10 digitos, é o método que utilizamos para representar valores numéricos no dia a dia.
• O sistema binário, com os dígitos 0 e 1, é o método mais amplamente usado para interpretar definições de bits como inteiros não-negativos no computador.
• O sistema octal, com 8 digitos, guarda correspondência de cada digito com uma palabra binária de 3 bits.
• O sistema hexadecimal, com 16 digitos, guarda correspondência de cada digito com uma palabra binária de 4 bits. É muito utilizado para representar de forma concisa palavras binárias múltiplas de 4 bits.

Além de armazenar informações codificadas em binário, o computador também realiza operações sobre números binários utilizando Aritmética Binária. Nestas operações, números binários inteiros positivos ou negativos são representados no computador na forma de complemento de 2.

A informação binária pode ser representada por outros Códigos Digitais, como por exemplo o Código BCD (binary coded decimal).

Números Reais

Números reais são normalmente representados nos computadores utilizando a notação de ponto flutuante.

O conceito chave da notação de ponto flutuante é que um número real é representado por um número, chamado mantissa, vezes uma base elevada a uma potência de inteiro, chamada expoente.

Exemplo

Inteiro base 10

38,753 = 38753 x 10-2
         |         |
         Mantissa  Expoente

Uma representação comum é representar a mantissa por um inteiro, sem os 0s (zeros) finais.

Binários de ponto flutuante

As representações normatizadas para binários de ponto flutuante definem números de precisão simples (32 bits) ou precisão dupla (64 bits).

Precisão simples de 32 bits

• 24 bits -> Mantissa
• 8 bits -> Expoente
• Base fixa 10

Exemplo

Decimal:

38,753 = 38753 x 10-2
         |         |
         Mantissa  Expoente

Binário:

000000001001011101100001 (Mantissa 24 bits)
11111110 (Expoente 8 bits - Representado em Complemento de 2)

Exercícios

Representar em binário de ponto flutuante de precisão simples:

• 0
• 100
• 0,5
• 0,00005
• -12
• 12000
• -12000

Strings de Caracteres

Para representar objetos não numéricos no computador, como as letras do alfabeto ou os símbolos numéricos, os mesmos devem ser codificados em algum código digital, como, por exemplo, o código ASCII.

No código ASCII, por exemplo, a letra 'A' é representada por 01000001 e a letra 'B' por 01000010, logo, a string de caracteres 'AB' deve ser representada pela palavra binária 0100000101000010. Em geral, uma string de caracteres é representada pela concatenação das palavras binárias que representam os caracteres individuais da string.

Memória do Computador

As informações binárias são normalmente armazenadas na memória do computador na forma de Bytes (8 bits). Cada Byte armazenado na memória recebe um endereço, o qual guarda a posição do dado da memória e é utilizado para acessar este dado.

Declaração de dados

Nas linguagem de programação de alto nível, como a linguagem C, quando declaramos varáveis estamos informando ao computador a quantidade de Bytes que deve ser reservada na memória para cada tipo de dado.

Tipo	Tamanho	Valores válidos
char	1 Byte	letras e símbolos: 'a', 'b', 'H', '^', '*','1','0'
int	2 Bytes	de -32767 até 32767 (inteiros com sinal)
float	4 Bytes	-3.4 x 1038 até +3.4 x 10+38com até 6 dígitos de precisão
double	8 Bytes	de -1.7 x 10308 até +1.7 x 10+308com até 10 dígitos de precisão

Por exemplo, se um programador C declarar:

int x, y;
float a, b;

será reservado espaço em quatro posições para quatro números diferentes. Esas quatro posições podem ser referenciadas pelas variáveis x, y, a e b. O conteúdo das posições reservadas para x e y será interpretado como inteiros, enquanto o conteúdo de a e b será interpretado como números de ponto flutuante.

O compilador responsável pela conversão de programas C em linguagem de máquina traduzirá o "+" contido na instrução

x = x + y; 

em soma de inteiros, e traduzirá o "+" contido na instrução

a = a + b; 

em soma de pontos flutuantes.

Referências

TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe. Estruturas de dados usando C. Makron Books, 1995.

---

Autoria

Evandro Cantú / IFPR - Câmpus Foz do Iguaçu

---