Estrutura De Dados

ATPS – ESTRUTURA DE DADOS

Estrutura de Dados é o nome dado à organização de dados e algoritmos de forma coerente e racional de modo a otimizar o seu uso. Por meio da maneira como os dados são organizados e como as operações são efetuadas sobre estes dados, se podem solucionar de forma simples problemas extremamente complexos. Existem diversos modelos de estruturas de dados, e novos modelos são criados constantemente, pois acompanham também a evolução dos algoritmos e das linguagens de programação. Escolher uma estrutura de dados ideal pode tornar-se um problema difícil para uma determinada solução. As pesquisas e estudos das estruturas de dados estão em constante desenvolvimento, apesar disso, existem estruturas que têm se mostrado padrão, ou seja, são clássicas. Podemos citar as listas, pilhas, filas, árvores e grafos como estruturas de dados clássicas.

Neste desafio, deverá ser apresentada uma solução computacional baseada em Estruturas de Dados para uma empresa aérea chamada VOEBEM que deseja automatizar alguns processos adotados pela companhia. A empresa necessita de um sistema que permita controlar a lista de voos diários e de passageiros por voos, realize a reserva de assentos e liberação para taxiamento das aeronaves, realize o controle de armazenamento das bagagens no compartimento de carga e realize levantamento das rotas devoos.

1. Estrutura de Dados.

TIPOS DE DADOS

Em informática todas as informações são armazenadas em Bits que representa a menor unidade de medida que só aceita 2 valores (0 e 1) que são mutuamente exclusivas, ou seja, um Bit não pode assumir dois valores ao mesmo tempo, a representação de números decimais é feita através de um calculo onde cada Bit representauma potência de 2 a contar a partir do ultimo elemento da direita, ou seja, o numero binário 00101110 seria em decimal 46. Veja o porque:

00101110 contando da direita para esquerda todos os elementos que são 1 temos a seguinte fração:

21+22+23+25=2+4+8+32=46.

se quisermos representar o mesmo numero porem negativo, basta invertemos os números, ou seja, onde é 0 fica 1 e onde é 1 fica 0, veja como ficaria nosso numero negativo:

11010001=-46.

Pode-se dizer então que todo numero binário que representa um numero decimal se iniciado com 0 é positivo e se iniciado com 1 é negativo. Para representar números reais utiliza-se a notação de ponto flutuante.No qual o numero real é representado pela mantissa multiplica pela base elevada a uma potencia de inteiro (expoente). Em geral, a

base é fixa, e a mantissa e o expoente variam de modo a representar números reais diferentes. Um número real é representado por uma string de 32 bits consistindo

em uma mantissa de 24 bits seguida por um expoente de 8 bits. A vantagem da notação de ponto flutuante é que ela pode ser usada para representar números com valores absolutos muito grandes ou muito pequenos. O menor número positivo que pode ser representado é 10-128, que é muito pequeno. O fator limitante na exatidão com a qual os números podem ser representados em determinada máquinaé o número de dígitos binários significativos na mantissa.

Para representar caracteres não numéricos utilizamos a string de caracteres, cada caractere possuem 8 Bits.Exemplo. A letra “A” em binário é 01000001, e a letra “B” é 01000010 esses caracteres são conhecidos como strings de Bits para escrever os caracteres “AB” juntos ficaria 0100000101000010 (junção do códigos binários de cada letra), e isto é considerado uma string de caracteres uma vez que para escrever mais de uma letra é utilizado a concatenação de caracteres. Um método de interpretar um padrão de bits é frequentemente chamado tipo de dado.

MEMÓRIA

A memória é um conjunto de Bits (chaves).Os bits na memória de um computador são agrupados em unidades maiores, como bytes.Em alguns computadores, vários bytes são agrupados em unidades chamadas palavras. Cada unidade desse tipo recebe a atribuição de um endereço, isto é, um nome que identifica determinada unidade entre todas as unidades na memória. Um endereço é frequentemente chamado posição, e o conteúdo de uma posição são os valores dos Bits que formam a unidade nessa posição.Todo computador tem um conjunto de tipos de dados "nativos". Isso significa que ele é construído com um mecanismo para manipular padrões de bits coerentes com os objetos que eles representam. Por exemplo, um computador quecontem a instrução para somar dois inteiros binários e introduzir sua soma em determinada posição na memória para uso posterior. Sendo assim, deve existir um mecanismo incorporado no computador para: extrair os padrões de bits dos operandos de duas posições determinadas; produzir um terceiro padrão de bits representando o inteiro binário que seja a soma dos dois inteiros binários representados pelos dois operandos; e armazenar o padrão de bits resultante em determinada posição. O computador "sabe" interpretar os padrões de bits nas posições específicas como inteiros binários porque o hardware que executa a instrução foi projetado para fazer isso. Se a mesma máquina tiver também uma instrução para somar dois números reais, deverá existir um mecanismo embutido separado para interpretar operandos como números reais. São necessárias duas instruções distintas para as duas operações, e cada instrução carrega em si mesma uma identificação implícita dos tipos de seus operandos, além de suas posições explícitas.

É importante reconhecer o papel-chave desempenhado pelas declarações numa linguagem de alto nível. É por meio das declarações que o programador especifica como o conteúdo da memória do computador deve ser interpretado pelo programa.

IMPLEMENTAÇÃO

Existem dois tipos de implementação, implementação dehardware e implementação de software.

Na implementação de hardware é construído um circuito para efetuar as operações necessárias; Na implementação de software 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, sendo assim, nesta implementação é possível criar um novo tipo de dado que interaja com um tipo de dado já existente, assim como manipula e o mesmo.

Para implementar um novo tipo de dados é necessário descrever como ele será representado na memória e