LinguagensdeProgramação

AndreiRimsaÁlvares

TiposdeDados

Sumário

•  Introdução•  TiposPrimi:vos•  TiposCompostos

LinguagensdeProgramação

INTRODUÇÃO

Introdução

•  Valores:tudoaquiloquepodeseravaliado,armazenadoepassadocomoparâmetro–  Valores são agrupados em tipos

•  Ex.:32.5'a'"Paulo"0x1F026false

•  Tipos:conjuntodevaloresedeoperaçõesqueestãodefinidasparaosmesmos–  Podemserclassificadoscomo:

•  Primi:vos•  Compostos

TiposdeDados

•  UmApodedadosdefineumacoleçãodedadosdeobjetoseumconjuntodeoperaçõespredefinidasnestesdadosdeobjetos

•  Umdescritoréumconjuntodeatributosdeumavariável–  Ex.:nome,endereço,valor,:po,tempodevida,escopo

•  Umobjetorepresentaumainstânciadeum:po(dadosabstratos)definidapelousuário

Quaisoperaçõessãodefinidasecomoelassãoespecificadas?

LinguagensdeProgramação

TIPOSPRIMITIVOS

TiposPrimi:vos

•  Pra:camentetodalinguagemprovêumconjuntode:posprimi:vos

•  Tiposdedadossãodefinidosemtermosdeoutros:posoudelemesmo

•  Nãopodemserdecompostosemvaloresmaissimples,ouseja,sãoatômicos

•  Alguns:possãomeramentereflexosdohardware,outrosexigemumpoucodesuportenão-hardwareparasuaimplementação

TiposPrimi:vos

•  Exemplosde:posprimi:vos

–  Inteiro–  Pontoflutuante–  Complexo–  Decimal–  Lógico(boolean)–  Caractere–  Cadeiadecaracteres(string)–  TipoOrdinal(enumeradoeIntervalodeinteiros)

TipoInteiro

•  Correspondeaumintervalodoconjuntodosnúmerosinteiros–  EmC,intervalossãodefinidosnaimplementaçãodocompilador–  EmJAVA,ointervalodecada:pointeiroéestabelecidonadefiniçãodaprópriaLP

•  Podemexis:rvários:posinteirosnumamesmaLP,comoemC:

–  Inteirocom/semsinal,inteirobasedecimal,inteirobasebinária,precisãosimples,...

TipoInteiro

•  Tabelacomos:posprimi:vosinteirosdeJava

Tipo Tamanho(bits)

Intervalo

Início Fim

byte 8 -128 127

short 16 -32,768 32,767

int 32 -2,147,483,648 2,147,483,647

long 64 -9,223,372,036,854,775,808 9,223,372,036,854,775,807

•  O:poprimi:vopontoflutuantemodelaosnúmerosreais,massomentecomoaproximações

•  LPsnormalmenteincluemdois:posdepontoflutuante–  float(precisãode32bits)edouble(precisãode64bits)

TipoPontoFlutuante

PadrãoIEEE754(Precisãosimples)

PadrãoIEEE754(PrecisãoDupla)

TipoComplexo

•  Algumaslinguagenssuportamo:pocomplexo–  Ex.:C99,FortranePython

•  Cadavalorconsistededoisnúmerosdeponto-flutuante(float),aparterealeaparteimaginária

•  ExemplodenúmeroliteralemPython:7 + 3j–  7:partereal–  3j:parteimaginária

TipoDecimal

•  Armazenaumnúmerofixodedígitosdecimais

•  Ú:lparaaplicaçõesfinanceiras–  EssencialparaCobol–  Na:voemC#:decimal salario = 540.0m;

•  Vantagem:acurácia•  Desvantagem:faixalimitada,desperdíciodememória

•  ExemploemCobol(representaçãointerna)

00100011 00110000 10000110 0111100100000010 10000011

4casasdecimais7casasinteirasSinal

4bytes 2bytes

TipoLógico(Boolean)

•  Tipomaissimples–  Possuiapenasdoisvalores(verdadeiroefalso)–  Pode ser implementado com 1 bit, mas normalmente éimplementadocom1byte

•  Vantagem:Legibilidade

•  Exemplos:–  C++(bool),Java(boolean)–  C: não possui o :po booleano, mas aceita expressões emcondicionais

•  ≠zero⇒verdadeiro•  =zero⇒falso

TipoCaractere

•  Armazenadoscomocódigosnuméricos–  TabelasEBCDIC,ASCIIeUNICODE

•  PASCALeMODULA2oferecemo:pochar

•  EmC,o:poprimi:vocharéclassificadocomoum:pointeiro

char a = 'a' + 3;printf("%c\n", a);printf("%d\n", a);

int d = 65;printf("%c\n", d);printf("%d\n", d);

TipoCadeiadeCaracteres(String)

•  Valoressãosequênciasdecaracteres

•  Decisõesdeprojeto–  Tipoprimi:voouarranjo?–  Tamanhodastringestá:caoudinâmica?

•  Operaçõescomstrings–  Atribuição–  Comparação(=,>,<,etc.)–  Concatenação(junçãoaofimdastring)–  Referênciaasubstring–  Correspondênciadepadrão(Pa3ernmatching)

TipoCadeiadeCaracteres(String)

•  CeC++–  Nãoéprimi:vo–  Usaarranjosdecharebibliotecadefunçõesparaoperações

•  SNOBOL4(LPquemanipulastrings)–  Éprimi:vo–  Váriasoperações,incluindopa3ernmatching

•  Java–  Primi:voatravésdaclasseString

•  Perl–  Padrõessãodefinidosemtermosdeexpressõesregulares–  Grandepoderdeexpressão–  Exemplo:palavrascontendounicamenteletras

if ($dados =~ /[A-Za-z]+/) print ‘Somente letras’;

TipoCadeiadeCaracteres(String)

•  Está:co(COBOL,classStringdeJava)–  Descritordefinido/u:lizadoemtempodecompilação

•  Dinâmicolimitado(CeC++)–  Umcaractereespecialéusadoparaindicarofimdastring,aoinvésdemanterotamanho

•  Dinâmico(SNOBOL4,PerleJavaScript)–  Precisadeumdescritoremtempodeexecução–  Reserva/liberaçãodememóriaéumproblema

ImplementaçõesdeStrings

Adasuportatodosostrês:pos

•  TamanhoestáAco:descritoremtempodecompilação•  Tamanhodinâmicolimitado:podemprecisardeumdescritorem

tempodeexecução(emboranãoemC/C++)•  Tamanhodinâmico:precisadedescritoremtempodeexecução;

alocação/liberaçãoéomaiorproblemadeimplementação

ImplementaçõesdeStrings

StringestáAca:descritoremtempodecompilação Stringdinâmicalimitada:descritor

emtempodeexecução

•  Avaliação

–  Ajudanaregibilidadedoprograma

–  O:poprimi:vodetamanhoestá:coéeficiente,porquenãooter?

–  Tamanhodinâmicoébom,masmuitocaro,seráquevaleapena?

TipoCadeiadeCaracteres(String)

TipoOrdinal

•  Tipocujaamplitudedepossíveisvalorespodemserassociadoscomosinteirosposi:vos–  Ex:integer,char,boolean

•  Muitaslinguagensdeprogramaçãopermitemosseguintes:posordinais–  TipoEnumerado–  TipoIntervalodeInteiros

TipoOrdinal:Enumerado

•  Permiteenumerarvaloresatravésdeconstantessimbólicas

•  Exemplos–  Pascal:type cor = (vermelho, azul, branco, preto);

–  C,C++:enumcor{vermelho,azul,branco,preto};

–  C#,Java>=5.0(Implementadocomoclasse)enumcor{vermelho,azul,branco,preto};

TipoOrdinal:Enumerado

•  Consideraçõesdeprojeto

–  Podeumaconstantesimbólicapertenceramaisdeumadefiniçãode:po?Sesim,comoverificar?

–  Asenumeraçõespodemserconver:daseminteiros?

–  Algumoutro:popodeserconver:doparaumaenumeração

TipoOrdinal:Enumerado

•  Vantagens–  Legibilidade

•  Ex:nãoprecisacodificarcorescomointeiros

–  Confiabilidade•  Nãopermitequeseoperecores(soma)•  Nãosepodedefinirvaloresforadafaixadaenumeração•  Ada,C#eJava>=5.0nãofazemcoerçãoparainteiros

TipoOrdinal:IntervalodeInteiros

•  Subsequênciaordenadacon|nuadeum:poenumeradoordinal

•  Exemplo–  Pascal:

type positivo = 0 .. MAXINT;–  ADA:

type Days is (mon, tue, wed, thu, fri, sat, sun); subtype Weekdays is Days range mon..fri;

TipoOrdinal:IntervalodeInteiros

•  Avaliação–  Melhoralegibilidade–  Podemguardarapenascertosvaloreslimitadosàfaixa

•  Melhoraconfiabilidade–  Detecçãodeerrosedasamplitudesdosvalores

TipoOrdinal:IntervalodeInteiros

•  Implementação–  Tiposenumeradosgeralmentesãoimplementadosassociandonúmerosinteirosacadaconstante

–  Subfaixassãoimplementadasdamesmaformaqueos:pospais

•  Ocódigopararestringiratribuiçõesavariáveisdesubfaixasdeveserinseridopelocompilador

LinguagensdeProgramação

TIPOSCOMPOSTOS

TiposCompostos

•  Aquelesquepodemsercriadosapar:rde:posmaissimples–  Registros,vetores,listas,arquivos

•  Entendidosemtermosdosconceitos–  Produtocartesiano,uniões(livresedisjuntas),mapeamentos,conjuntospotênciae:posrecursivos

•  Cardinalidade–  Númerodevaloresdis:ntosquefazempartedo:po

ProdutoCartesiano

•  Combinaçãodevaloresde:posdiferentesemtuplas

•  Cardinalidade

#(S1 x S2 x ... x Sn) = #S1 x #S2 x ... x #Sn

ab cde(a,c)(a,d)(a,e)

(b,c)(b,d)(b,e)

S TSxT

X =

ProdutoCartesiano

•  SãoprodutoscartesianoosregistrosdePASCAL,MODULA2,ADAeCOBOLeasestruturasdeC

•  EmLPsorientadasaobjetos,produtoscartesianossãodefinidosa

par:rdoconceitodeclasse(Javasótemclasses)

struct nome {char primeiro[20];char meio[10];char sobrenome[20];

};

struct empregado {struct nome nfunc;float salario;

} emp;

ProdutoCartesiano

•  Exemplo

–  Inicialização

–  Acessoaosmembros(atravésdeseletores)

–  Cardinalidade

#INTEGER x #INTEGER x #INTEGER

struct data {int dia, mes, ano;

};

struct data d = { 7, 9, 1999 };

printf("%02d\n", d.dia);d.mes = 10;

Uniões

•  Consiste na união de valores de :pos dis:ntos para formar umnovo:podedados

•  Cardinalidade#(S1 + S2 + ... + Sn) = #S1 + #S2 + ... + #Sn

abc bcd abcd

S T S+T

+ =

Uniões

•  Uniõeslivres–  Pode haver interseção entre o conjunto de valores dos :posqueformamaunião

–  Hápossibilidadedeviolaçãonosistemade:pos

•  Exemplo

union medida { int centimetros; float metros;};

void funct() { union medida medicao; float altura;

medicao.centimetros = 180; altura = medicao.metros; printf("\naltura: %f m\n", altura);}

Uniões

•  Uniõesdisjuntas–  Não há interseção entre o conjunto de valores dos :pos queformamaunião

–  RegistrosvariantesdePASCAL,MODULA2eADAeauniondeALGOL68

•  ExemploemPascalTYPE Representacao = (decimal, fracionaria);

Numero = RECORD CASE Tag: Representacao OFdecimal: (val: REAL); fracionaria: (numerador, denominador: INTEGER);

END

var num of Numero;Numero.Tag = decimal;Numero.val = 1.5;

Uniões

•  Exemplo

–  Possíveisvalores

(25.00, musica(16)) (35.00, livro(257)) (40.00, video(121, TRUE))

–  Cardinalidade#REAL x (#INTEGER + #INTEGER + (#INTEGER x #BOOLEAN))

TYPE TipoProduto = (musica, livro, video);Compra = RECORD valor: REAL;

CASE produto: TipoProduto OF musica: (numeromusicas: INTEGER);

livro: (numeropaginas: INTEGER); video: (duracao: INTEGER, colorido: BOOLEAN);

END;

Mapeamentos

•  Mapeamentospodemser–  Finitos–  Atravésdefunções

•  Tiposdedadoscujoconjuntodevalorescorrespondeatodosospossíveismapeamentosdeum:podedadosSemoutroT

uv

abc

uv

abc

S T S T

•  Cardinalidade#(S→T) = (#T)#S

MapeamentosFinitos

•  Oconjuntodomínioéfinito•  Vetoresematrizes

–  array S of T; (S → T)–  array [1..50] of char; ([1,50] → char)

•  Oconjuntoíndicedeveserfinitoediscreto

•  Verificação de índices em C vs. JAVA: verificação em tempo deexecuçãoaumentaaconfiabilidade,masperdeeficiência

azdrs…fhwo12345…47484950

int v[7];v[13] = 198;

CategoriadeVetores

•  Está:cos(emC)

•  Semi-está:cos(emC)

void f() { static int x[10];}

void f() { int x[10];}

•  Semi-dinâmicos(emCISO/99)

•  Dinâmicos(emC++)

void f(int n) { int x[n];}

void f(int n) { int x[] = new int [n];}

CategoriadeVetores

•  Tabelacomascategoriasdevetores

CategoriadeVetor Tamanho Tempode

Definição Alocação LocaldeAlocação

ExemplosdeLPs

Está:cos Fixo Compilação Está:ca Base FORTRAN77

Semi-Está:cos Fixo Compilação Dinâmica Pilha PASCAL,C,

MODULA2

Semi-Dinâmicos Fixo Execução Dinâmica Pilha ALGOL68,

ADA,C

Dinâmicos Variável Execução Dinâmica Heap APL,PERL

VetoresDinâmicos

•  Podem ser implementados em C, C++ e JAVA através do monte(heap)

•  Necessário alocar nova memória e copiar conteúdo quando vetoraumentadetamanho

•  Éencargodoprogramadorcontrolaralocaçãoecópia.EmCeC++,oprogramador deve controlar liberação também. Isso torna aprogramaçãomaiscomplexaesusce|velaerros

VetoresMul:dimensionais

•  Exemplo

–  Representação

{0, …, 4} x {0, …, 3} → int–  Conjuntodevalores

(#INT)#({0, …, 4} x {0, …, 3}) =(#INT)#{0, …, 4} x #{0, …, 3} =(#INT)5 x 4 =(#INT)20

int mat[5][4];

mat[2][3]

VetoresMul:dimensionais

•  Elementossãoacessadosatravésdaaplicaçãodefórmulas

posição mat[i][j] = endereço de mat[0][0] + i × tamanho da linha + j × tamanho do elemento = endereço de mat[0][0] + (i × número de colunas + j) × tamanho do elemento

VetoresMul:dimensionais

•  Em JAVA vetores mul:dimensionais são vetores unidimensionaiscujoselementossãooutrosvetores

•  Omesmoefeitopodeserob:doemCcomousodeponteirosparaponteiros

int [][]a = new int [5][];for (int i = 0; i < a.length; i++) {

a[i] = new int [i + 1];}

int** a = new int [5][];for (int i = 0; i < 5; i++) {

a[i] = new int [i + 1];}

OperaçõescomVetores

•  Vetorespodemsuportarasseguintesoperações

–  Indexação–  Inicialização–  Atribuição–  Comparação(igualdadeedesigualdade)–  Concatenação

MapeamentosAtravésdeFunções

•  UmafunçãoimplementaummapeamentoS → Tatravésdeumalgoritmo

•  OconjuntoSnãonecessariamenteéfinito

•  Oconjuntodevaloresdo:pomapeamentoS → T sãotodasasfunçõesquemapeiamoconjuntoSnoconjuntoT

•  Valoresdomapeamento[ int → boolean ]emJava

–  Outrosexemplos:palindromo,impar,par,primo

boolean positivo(int n) {return n > 0;

}

MapeamentosAtravésdeFunções

•  C u:liza o conceito de ponteiros para manipular endereços defunçõescomovalores

01: int impar(int n) { return n % 2; }02: int negativo(int n) { return n < 0; }03: int multiplo7(int n) { return !(n % 7); }04: int conta(int x[], int n, int (*p)(int)) {05: int j, s = 0;06: for (j = 0; j < n; j++)07: if ((*p)(x[j]))08: s++;09: return s;10: }11: void main() {12: int vet[10] = { ... };13: printf("%d\n", conta(vet, 10, impar));14: printf("%d\n", conta(vet, 10, negativo));15: printf("%d\n", conta(vet, 10, multiplo7));16: }

Javanãotratafunçõescomovalores

ConjuntosPotência

•  Tipos de dados cujo conjunto de valores corresponde a todos ospossíveissubconjuntosquepodemserdefinidosapar:rdeum:pobaseS: ϕS = {s | s ⊆ S}

•  Cardinalidade#ϕS = 2#S

abcS

{}{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}

ϕS

ConjuntosPotência

•  Operaçõesbásicas

–  Per:nência–  Contém–  Estácon:do–  União–  Diferença–  Diferençasimétrica–  Interseção

ConjuntosPotência

•  Poucas linguagens de programação oferecem o :po conjuntopotência,muitasvezesdeformarestrita

•  ExemploemPascalTYPE Carros = (corsa, palio, gol);

ConjuntoCarros = SET OF Carros;VAR Carro: Carros;

CarrosPequenos: ConjuntoCarros;BEGIN

Carro:= corsa;CarrosPequenos := [palio, gol];             /*atribuicao*/CarrosPequenos:= CarrosPequenos + [corsa];  /*uniao*/CarrosPequenos:= CarrosPequenos * [gol];    /*intersecao*/

   if Carro in CarrosPequenos then             /*pertinencia*/   if CarrosPequenos >= [gol, corsa] then      /*contem*/

ConjuntosPotência

•  Restrições de PASCAL visam permi:r implementação eficiente,atravésdemapasdebits

•  Exemplo

VARS: SET OF [ ’a’ .. 'h' ];

BEGIN S := ['a', 'c', 'h'] + ['d'];

END;

1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0OR['a’,'c’, 'h’] ['d’]

:=['a’,'c’,'d’,'h’]

Recursivos

•  Tipos recursivos são :pos de dados cujos valores são compostosporvaloresdomesmo:po–  R ::= <parte inicial> R <parte final>–  Lista ::= Lista Vazia | (Elemento x Lista)

•  A cardinalidade de um :po recursivo é infinita; isto é verdademesmoquandoo:podoelementodalistaéfinito

•  O conjunto de valores do :po listas é infinitamente grande (nãopodendoserenumerado)emboratodalistaindividualsejafinita

Recursivos

•  Tipos recursivos podem ser definidos a par:r de ponteiros ouatravésdereferências

•  Exemplos

struct No {int elem;struct No* prox;

};

class No {public: int elem; No* prox;};

class No {int elem;No prox;

};

EmC EmC++ EmJava

Ponteiros

•  Nãoserestringeaimplementaçãode:posrecursivosemborasejaseuusoprincipal

•  Ponteiro é um conceito de baixo nível relacionado com aarquiteturadoscomputadores

•  O conjunto de valores de um :po ponteiro são os endereços dememóriaeovalornil

•  Sãoconhecidoscomoosgoto’sdasestruturasdedados

Ponteiros

•  Atribuição

•  Alocação

•  Liberação

int *p, *q, r; // dois ponteiros para int e um intq = &r; // atribui endereço de r a qp = q; // atribui endereço armazenado em q a p

int* p = (int*) malloc(sizeof(int)); // em Cint* p = new int; // em C++

free(p); // em Cdelete p; // Em C++

Ponteiros

•  Dereferenciamentoexplícito

•  Dereferenciamentoimplícito

INTEGER, POINTER :: PTRPTR = 10PTR = PTR + 10

int *p;*p = 10;*p = *p + 10;

Ponteiros

•  Aritmé:cadeponteiros

•  Indexaçãodeponteiros

p++;++p;p = p + 1;p--;--p;p = p - 3;

x = p[3];

PonteirosGenéricos

•  Aritmé:cadeponteiros

•  Servemparacriaçãodefunçõesgenéricasparagerenciarmemória

•  Servemparacriaçãodeestruturasdedadosheterogêneas(aquelascujoselementossãode:posdis:ntos)

int f, g;void* p;f = 10;p = &f;g = *p; // erro: ilegal dereferenciar ponteiro p/ void

ProblemascomPonteiros

•  Baixa legibilidade: Inspeção simples não permite determinar qualestruturaestásendoatualizadaequaloefeito

•  Possibilitamviolarosistemade:pos

•  Objetospendentes:provocavazamentodememória

p->cauda = q;

int i, j = 10;int* p = &j; // p aponta para a variavel inteira j p++; // p pode nao apontar mais para um inteiroi = *p + 5; // valor imprevisivel atribuido a i

int* p = (int*) malloc(10*sizeof(int));int* q = (int*) malloc(5*sizeof(int));p = q; // área apontada por p torna-se inacessivel

ProblemascomPonteiros

•  ReferênciasPendentes–  Exemplo1:

–  Exemplo2:

–  Exemplo3:

int* p = (int*) malloc(10*sizeof(int));int* q = p;free(p); // q aponta agora para area de memoria desalocada

int *p, x;x = 10;if (x) {

int i;p = &i;

}// p continua apontando para i, que nao existe mais

int *r; // ponteiro não inicializado*r = 0;

Referência

•  O conjunto de valores desse :po é formado pelos endereços dascélulasdememória

•  Todasasvariáveisquenãosãode:posprimi:vosemJAVAsãodo:poreferência

•  Exemplo(emC++)

int x = 0;int& ref = x; // ref passa a referenciar xref = 100; // x passa a valer 100

Strings

•  Valorescorrespondemaumasequênciadecaracteres

•  Nãoexisteconsensosobrecomodevemsertratadas

•  Podemser consideradas:posprimi:vos,mapeamentosfinitosou:porecursivolista

•  Trêsformascomunsdeimplementação–  Está:ca–  Semi-está:ca–  Dinâmica

HierarquiadeTipos

Tipos

Primi:vos Compostos

Booleanos

Inteiros

Caracteres

Decimais

PontoFlutuantes

Enumerados

Intervalos

Uniões

Strings

Recursivos

Mapeamentos

ConjuntosPotência

ProdutosCartesianos

Ponteiros

Livres Disjuntas

Finitos Funções

LinguagensdeProgramação

ISSOÉTUDOPESSOAL!