Baixe o app para aproveitar ainda mais
Prévia do material em texto
GCC 105 – LINGUAGENS DE PROGRAMAÇÃO I AULA 3 – Tipos de Dados 1º Semestre de 2015 Prof. Janderson Rodrigo de Oliveira Universidade Federal de Lavras Departamento de Ciência da Computação Introdução • Um tipo de dado define uma coleção de valores de dados e um conjunto de operações pré-definidas sobre eles. • É crucial uma linguagem oferecer suporte para uma coleção apropriada de tipos e estruturas de dados. • Nas primeiras linguagens, todas as estruturas de dados do espaço do problemas tinham de ser modeladas com apenas poucas estruturas de dados suportadas pela linguagem (Fortran pré-90). Introdução • COBOL foi a primeira linguagem a permitir que programadores especificassem a precisão dos valores de dados decimais. • Uma abordagem melhor, introduzida no ALGOL 68, é fornecer alguns tipos básicos e operadores de definição de estrutura flexíveis que permitem a um programador projetar uma estrutura de dados para cada necessidade. Introdução • Vantagens dos tipos definidos pelo usuário: – fornecem uma legibilidade melhorada, por meio de nomes significativos para os tipos; – permitem a verificação de tipos de variáveis de uma categoria especial de uso; – ajudam na facilidade de fazer modificações - é possível modificar o tipo de uma categoria de variáveis em um programa trocando apenas uma sentença de definição de tipo. Introdução • Levando o conceito de tipo definido pelo usuário adiante, tem-se os tipos abstratos de dados (TAD). • Tipos abstratos de dados são suportados pela maioria das linguagens de programação projetadas desde a metade dos anos 1980. • Ideia do TAD: a interface de um tipo é separada da representação e do conjunto de operações sobre valores desse tipo. Introdução • Existem diversos usos do sistema de tipos de uma linguagem: – Detecção de erros; – Assistência à modularização de programas – verificação de tipos em diferentes módulos, o que garante a consistência das interfaces entre eles; – Documentação – as declarações de tipo em um programa documentam informação sobre seus dados e fornecem diretrizes sobre o comportamento de uma programa. Introdução • O sistema de tipos de uma linguagem de programação define como um tipo é associado com cada expressão na linguagem e inclui suas regras para equivalência e compatibilidade de tipos. • Os dois tipos de dados estruturados (não escalares) são as matrizes e os registros. • Os tipos de dados estruturados são definidos por meio de operadores de tipos, usados para formas expressões de tipos. Em C, usa-se colchetes e asteriscos como operadores de tipos para especificar matrizes e ponteiros. Tipos de Dados Primitivos • Tipos de dados não definidos em termos de outros são chamados tipos de dados primitivos. • Os tipos de dados primitivos de uma linguagem são usados, com um ou mais construtores de tipo, para fornecer os tipos estruturados. • Tipos de dados primitivos – Tipos numéricos; – Tipos booleanos; – Caracteres. Tipos Numéricos • Inteiro – Tipo de dado primitivo numérico mais comum. – Computadores suportam diversos tamanho de inteiros (Java inclui quatro tamanhos inteiros com sinal: byte, short, int e long). – Algumas linguagens incluem tipos inteiros sem sinal (C++ e C#). – Um valor inteiro com sinal é representado em um computador como uma cadeia de bits, com um dos bits (normalmente o mais à esquerda) representando o sinal. Tipos Numéricos • Ponto flutuante – Tipos de dados de ponto flutuante modelam números reais, mas as representações são apenas aproximações para muitos valores reais. – Por exemplo, é impossível representar pi em um qualquer espaço finito. – Outro problema com tipos ponto flutuante é a perda de precisão por meio de operações aritméticas. Tipos Numéricos • Ponto flutuante – Valores de ponto flutuante são representados como frações expoentes, uma forma emprestada da notação científica. – A maioria das linguagens inclui dois tipos de ponto flutuante, chamados de float e double. – O tipo float é o tamanho padrão e, normalmente é armazenado em quatro bytes de memória. Tipos Numéricos • Ponto flutuante – Variáveis de precisão dubla normalmente ocupam o dobro de espaço de armazenamento das variáveis float e fornecem ao menos o dobro do número de bits de fração. – A coleção de valores que podem ser representados por um tipo ponto flutuante é definida em termos de precisão e faixa. • Precisão: exatidão da parte fracionária. • Faixa: combinação da faixa de frações e de exponentes. Tipos Numéricos • Ponto flutuante – Formato IEEE Floating-Point Standard 754 Tipos Numéricos • Complexo – Algumas linguagens suportam um tipo de dados complexo (Fortran e Python). – Valores complexos são representados como pares ordenados de valores de ponto flutuante. – Em Python a parte imaginária de um literal complexo é especificada por um j ou J. Por exemplo: (7 + 3j). – Linguagens que suportam este tipo de dado incluem operações para aritmética em valores complexos. Tipos Numéricos • Decimal – Tipos de dados decimais armazenam um número fixo de dígitos decimais, com o ponto decimal em uma posição fixa no valor. – Exemplos de linguagens que apresentam o tipo decimal: COBOL e C#. – Tipos decimais têm a vantagem de serem capazes de armazenar precisamente valores decimais. Sua desvantagem é que estes valores estão dentro de uma faixa restrita. Tipos Booleanos • A faixa de valores dos tipos booleanos possuem apenas dois elementos: um para verdadeiro e outro para falso. • Foram introduzidos em ALGOL 60 e incluídos na maioria das linguagens de propósito geral projetadas desde 1960. • Exceção: C89, no qual expressões numéricas são usadas como condicionais. – Todos os valores diferentes de zero são considerados verdadeiros e zero é considerado falso. – O C99 e C++ possuem o tipo booleano, mas também permitem a utilização de expressões numéricas como se fossem booleanas. Tipos Booleanos • Tipos booleanos são geralmente usados para representar escolhas ou como flags em programas. • Apesar de outros tipos, como inteiros, poderem ser usados para tais propósitos, o uso de tipos booleanos é mais legível. • Usualmente, valores booleanos são armazenados na menor célula de memória eficientemente endereçável, um byte. Caracteres • Dados na forma de caracteres são armazenados nos computadores como codificações numéricas. • Tradicionalmente, a codificação mais usada era o ASCII (American Standard Code for Information Interchange) de 8 bits. – Utiliza valores de 0 a 127 para codificar 128 caracteres diferentes. • Por causa da globalização dos negócios e da conectividade entre os computadores pelo mundo, o ASCII se tornou inadequado. Caracteres • Em 1991, o Consórcio Unicode publicou o padrão UCS-2, um conjunto de caracteres de 16 bits. • Essa codificação é geralmente chamada Unicode, incluindo os caracteres da maioria das linguagens naturais do mundo. • Algumas linguagens que adotaram o Unicode: Java, JavaScript, Python, Perl e C#. Tipos Ordinais Definidos pelo Usuário • Um tipo ordinal é um no qual a faixa de valores possíveis pode ser facilmente associada com o conjunto dos inteiros positivos. • Em Java, por exemplo, os tipos ordinais primitivos são integer, char e boolean. • Existem dois tipos ordinais definidos pelo usuário: – Tipos enumeração – todos os valores possíveis são fornecidos, ou enumerados, na definição; – Tipos subfaixa – subsequência contígua de um tipo ordinal (nenhuma linguagem contemporânea, exceto Ada 95, possui tipos subfaixa). Tipos Enumeração • Tipos enumeração fornecem uma maneira de definir e agrupar coleçõesde constantes nomeadas, chamadas de constantes de enumeração. • Exemplo em C#: • Constantes de enumeração são preenchidas implicitamente por atribuições de valores inteiros. enum days {Seg, Ter, Qua, Qui, Sex, Sab, Dom}; Tipos Enumeração • Em linguagens que não têm tipos enumeração, os programadores normalmente simulam enumerações usando valores inteiros. • Exemplo em C: • Problemas com esta abordagem: – Não definiu-se um tipo para as cores; – Não há como existir uma verificação de tipos; int vermelho = 0, azul = 1; Tipos Enumeração • C e Pascal foram as primeiras linguagens amplamente usadas a incluírem tipos enumeração. C++ inclui os tipos enumeração de C. • Exemplo em C++: • Os valores de enumeração são convertidos para int quando inseridos em um contexto inteiro. Isso permite seu uso em qualquer expressão numérica. enum cores {vermelho, azul, verde, amarelo, preto}; cores minhaCor = azul, suaCor = vermelho; Tipos Enumeração • Um tipo enumeração foi adicionado à linguagem Java em sua versão 5.0, em 2004. Todos os tipos enumeração em Java são subclasses implícitas da classe pré-definida Enum. • Tipos enumeração em C# nunca são convertidos para inteiros. • Tipos enumeração fornecem vantagens tanto em relação à legibilidade quanto à confiabilidade. – Nenhuma variável de enumeração pode ter um valor atribuído a ela fora de sua faixa definida. Matrizes • Uma matriz é um agregado homogêneo de elementos de dados no qual um elemento individual é identificado por sua posição na agregação, relativamente ao primeiro elemento. • Na maioria das linguagens, como C, C++, Java, Ada e C#, todos os elementos de uma matriz precisam ser do mesmo tipo. • Os elementos de dados individuais de uma matriz são especificados usando expressões de índices. Matrizes e Índices • Elementos específicos de uma matriz são referenciados por meio de um mecanismo sintático de dois níveis: – Primeiro nível: nome agregado; – Segundo nível: seletor possivelmente dinâmico que consiste de um ou mais itens conhecidos como índices ou subscritos. • A operação de seleção pode ser pensada como um mapeamento do nome de uma matriz e o conjunto de valores de índices para um elemento no agregado. Matrizes e Índices • Simbolicamente, esse mapeamento pode ser mostrado como: nome_matriz(lista_valores_índices) → elemento • O nome da matriz é seguido por uma lista de índices, envoltos ou em parênteses ou em colchetes. • Nas matrizes multidimensionais, cada índice aparece em seu próprio colchete. Matrizes e Índices • Dois tipos distintos estão envolvidos em um tipo matriz: o do elemento e o do índice. • O tipo dos índices é normalmente uma subfaixa de inteiros. – Algumas linguagens permitem que qualquer tipo ordinal seja usado como índice, por exemplo: Ada. • As primeiras linguagens de programação não especificavam que as faixas de índices deveriam ser verificadas. – Erros de faixas em índices são comuns em programas (confiabilidade). – A maioria das linguagens contemporâneas NÃO faz verificação de faixas. Vinculações de Índices • É possível referenciar um elemento de uma matriz em Perl com um índice negativo – o valor do índice é um deslocamento a partir do fim da matriz. • A vinculação do tipo do índice a uma variável matriz é normalmente estática, mas a faixa de valores do índice pode ser vinculada dinamicamente em algumas linguagens. • Em muitas linguagens, o limite inferior da faixa de índices é implícito. – Baseadas em C, o limite inferior é fixado em 0; – Em Fortran 95, é padronizada em 1. Vinculações de Índices • Existem diversas categorias de matrizes, baseadas: 1. Na vinculação das faixas de índices; 2. Na vinculação ao armazenamento; 3. A partir de onde o armazenamento é alocado. • Quando a faixa de índices são fixas, a matriz não pode modificar seu tamanho. Inicialização de Matrizes • Algumas linguagens fornecem meios para inicializar matrizes no momento em que seu armazenamento é alocado. • Exemplo em C: • Neste caso, o compilador define o tamanho da matriz. Custo da abordagem: remove a possibilidade do sistema de detectar alguns tipos de erros, como deixar um valor de fora da lista por engano. int lista[] = {4, 5, 7, 83}; Inicialização de Matrizes • Cadeias de caracteres em C e C++ são implementadas como matrizes de char. • Matrizes de cadeias em C e C++ também podem ser inicializadas como literais do tipo cadeia. • Correspondente em Java: char nome[] = “Maria”; char *nomes[] = {“Maria”, “Jose”, “Joao”}; String[] nomes = {“Maria”, “Jose”, “Joao”}; Operações de Matrizes • Uma operação de matriz atua nesta como uma unidade. • As mais comuns são a atribuição, a concatenação, a comparação por igualdade e diferença. • Linguagens baseadas em C não fornecem operações de matrizes, exceto por meio de métodos e Java, C++ e C#. • Perl oferece suporte à atribuição de matrizes, mas não para comparações. Operações de Matrizes • Ada permite atribuição de matrizes e concatenação, esta última especificada pelo símbolo &. • Praticamente todos os tipos em Ada têm operadores relacionais próprios para igualdade e diferença. • Python fornece atribuição de matrizes, operações para concatenação de matrizes (+) e para verificar se um elemento pertence à matriz (in). Além de operadores para igualdade de matrizes. Implementação de Matrizes • Uma matriz de uma dimensão é implementada como uma lista de células de memórias adjacentes. • Suponha que lista seja definida como tendo um limite inferior para a faixa de índices de valor 0. A função de acesso para lista é geralmente construída da seguinte forma: endereço(lista[k]) = endereço(lista[0]) + k*tamanho_do_elemento onde: • 1º operando: parte constante da função de acesso; • 2º operado: parte variável. Implementação de Matrizes • A generalização dessa função de acesso para um limite inferior arbitrário é : endereço(lista[k]) = endereço(lista[limite_inferior]) + ((k – limite_inferior)*tamanho_do_elemento) • Matrizes multidimensionais são mais complexas de implementar do que as de uma dimensão. • A memória em hardware é linear. Então, valores de tipos de dados que têm duas ou mais dimensões devem ser mapeados para a memória de uma única dimensão. Implementação de Matrizes • Existem duas formas pelas quais matrizes multidimensionais podem ser mapeadas para uma dimensão: – Ordem principal de linha – a matriz é armazenada pelas linhas; – Ordem principal de coluna – a matriz é armazenada pelas colunas. • Por exemplo, considere uma matriz 3x3. Linha 1 Linha 2 Linha 3 Implementação de Matrizes • Pela ordem principal de linha, o computador enxerga esta matriz 3 x 3 como um arranjo de 9 posições contíguas na forma: • Em contrapartida, pela ordem principal de coluna, o mapeamento seria realizado segundo as colunas (1ª coluna, 2ª coluna e 3ª coluna). Linha 1 Linha 2 Linha 3 Implementação de Matrizes • A ordem principal de coluna é usada no Fortran, mas a maioria das linguagens que têm matrizes multidimensionais usam a ordem principal de linhas. • O acesso sequencial aos elementos da matriz será mais rápido se eles forem acessados na ordem em que foram armazenados, porque isso resultará em uma melhor localidade de memória. • A função de acesso para uma matriz multidimensional é o mapeamento de seu endereço base e um conjunto de valores de índices para o endereço de memória do elemento especificado pelos valores de índices. Implementação de Matrizes • Assumindo uma matriz bidimensional em ordem principal de linha, cujos limites inferiores dos índices sejam iguais a um, a função de acesso pode serescrita como: endereço(a[i,j]) = endereço(a[1,1]) + ((((número de linhas acima da i- ésima linha) * (tamanho_de_uma_linha)) + (número de elementos à esquerda da j-ésima coluna)) * (tamanho_do_elemento) • Desenvolvendo: endereço(a[i,j]) = endereço(a[1,1]) – ((n + 1) * tamanho_do_elemento) + ((i * n + j) * tamanho_do_elemento) em que, n é a quantidade de colunas da matriz. Implementação de Matrizes • A generalização para limites inferiores arbitrários resulta na seguinte função de acesso: endereço(a[i,j]) = endereço(a[li_linha,li_col]) – (((li_linha * n) + li_col) * tamanho_do_elemento) + ((i * n + j) * tamanho_do_elemento) em que: – n: número de colunas da matriz; – li_lin: limite inferior das linhas; – li_col: limite inferior das colunas. Registros • Um registro é um agregado de elementos de dados no qual os elementos individuais são identificados por nomes e acessados por meio de deslocamentos a partir do início da estrutura. • Os registros têm sido parte de todas as linguagens de programação mais populares, exceto pelas versões anteriores ao Fortran 90. • Em C, C++ e C#, os registros são suportados por meio do tipo de dados struct. Registros • Os elementos de um registro são de tamanhos potencialmente diferentes e residem em posições de memórias adjacentes. • A diferença fundamental entre um registro e uma matriz é que elementos de registro, ou campos, não são referenciados por índice. • Em vez disso, os campos são nomeados com identificadores. Registros • Referências aos campos individuais dos registros são especificadas sintaticamente por métodos distintos, um dos métodos mais tradicionais é nomear o campo desejado e o registro que o envolve. • A maioria das linguagens usa notações por pontos para referências a campos, onde os componentes da referência são conectados por pontos. – Ordem da notação: nome do maior registro que envolve os outros primeiro e o nome do campo por último. • C e C++ usam essa sintaxe. Fortran 95 substitui os pontos por sinais de percentual (%). Registros • A atribuição é uma operação comum em registros. Na maioria dos casos, os tipos dos dois lados devem ser idênticos. • Ada permite comparações entre registros para igualdade e diferença. • Registros e matrizes são fortemente relacionados com formas estruturais e é interessante compará-los. Registros • Matrizes – Todos os valores de dados têm o mesmo tipo e/ou são processados da mesma forma. • Registros – A coleção de valores é heterogênea e os campos diferentes não são processadas da mesma maneira. – Os campos de um registro normalmente não precisam ser processados em uma ordem em particular. – Nomes dos campos são como índices literais e fornecem um acesso muito eficiente aos campos.
Compartilhar