Introdução a Estruturas de Dados: mudanças entre as edições

De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
Linha 74: Linha 74:
===Declaração de dados===
===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.
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.
{| border=1
|-
| 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 10<sup><sup>38</sup></sup> até +3.4 x 10<sup><sup>+38</sup></sup>com até 6 dígitos de precisão
|-
| double || 8 Bytes || de -1.7 x 10<sup><sup>308</sup></sup> até +1.7 x 10<sup><sup>+308</sup></sup>com até 10 dígitos de precisão
|}


Por exemplo, se um programador C declarar:
Por exemplo, se um programador C declarar:

Edição das 20h23min de 1 de maio de 2014

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 2n valores diferentes.
Byte
É o termo clássico utilizado para uma palavra binária de 8 bits, o qual pode representar 28 = 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