Tipos de Dados, Tipos Abstratos de Dados (TAD) e ...

1 Tipos de Dados , Tipos Abstratos de Dados Estruturas de Dados Tipo de Dados , tipo abstrato de Dados , estruturas de Dados Termos parecidos, mas com significados diferentesTipo de dado Em linguagens de programa o o tipo de dado de uma vari vel, constante ou fun o define o conjunto de valores que a vari vel, constante ou fun o podem assumir , vari vel booleanpode assumir valores trueou false Programador pode definir novos Tipos de Dados em termos de outros j definidos Tipos estruturados, , arrays, recordsEstrutura de Dados Um tipo estruturado um exemplo de estrutura de Dados Tipos estruturados s o estruturas de Dados j pr -definidas na linguagem de programa o O programador pode definir outras estruturas de Dados para armazenar as informa es que seu programa precisa manipular Vetores, registros, listas encadeadas, pilhas, filas, rvores, grafos, s o exemplos de estruturas de Dados t picas utilizadas para armazenar informa o em mem ria principalPerspectivas para Tipos de Dados Tipos de Dados podem ser vistos como m todos para interpretar o conte do da mem ria do computador Mas, podemos interpretar o conceito de tipo de dado sob outra perspectiva n o em termos do que um computador pode fazer (interpretar os )

2 , mas em termos do que os usu rios (programadores) desejam fazer ( , somar dois ) O programador n o se importa muito com a representa o no hardware, mas sim com o conceito matem tico de inteiro Um tipo inteiro suporta certas opera Abstrato de Dados (TAD) Os Tipos e estruturas de Dados existem para serem usados pelo programa para acessar informa es neles armazenadas, por meio de opera es apropriadas Do ponto de vista do programador, muitas vezes conveniente pensar nas estruturas de Dados em termos das opera es que elas suportam, e n o da maneira como elas s o implementadas Uma estrutura de Dados definida dessa forma chamada de um Tipo Abstrato de Dados (TAD)Tipo Abstrato de Dados (TAD) TAD, portanto, estabelece o conceito de tipo de dado divorciado da sua representa o Definido como um modelo matem tico por meio de um par (v,o) em que v um conjunto de valores o um conjunto de opera es sobre esses valores Ex.

3 : tipo real v= o= {+, -, *, /, =, <, >, <=, >=}Defini o de TAD Requer que opera es sejam definidas sobre os Dados sem estarem atreladas a uma representa o espec fica ocultamento de informa o (information hiding) Programador que usa um tipo de dado real,integer,arrayn o precisa saber como tais valores s o representados internamente mesmo princ pio pode ser aplicado a listas, pilhas, .. se existe uma implementa o dispon vel de uma lista, p. ex., um programador pode utiliz -la como se fosse uma caixa preta , acess -la por meio das opera es que ela suportaDefini o de TAD O conceito de TAD suportado por algumas linguagens de programa o procedimentais Ex. Modula 2, Ada Para definir um TAD programador descreve o TAD em dois m dulos separados Um m dulo cont m a defini o do TAD: representa o da estrutura de Dados e implementa o de cada opera o suportada Outro m dulo cont m a interface de acesso.

4 Apresenta as opera es poss veis Outros programadores podem, por meio da interface de acesso, usar o TAD sem conhecer os detalhes representacionais e sem acessar o m dulo de defini oDefini o de TAD Os m dulos (ou units) s o instalados em uma biblioteca e podem ser reutilizados por v rios programas A execu o do programa requer a linkedi o dos m dulos de defini o (que podem ser mantidos j pr -compilados em uma biblioteca) junto com o programa Mas o programador n o precisa olhar o c digo do m dulo de defini o para usar o TAD! Basta conhecer a interface de acessoImplementa o de um TAD Uma vez definido um TAD e especificadas as opera es associadas, ele pode ser implementado em uma linguagem de programa o Uma estrutura de Dados pode ser vista, ent o, como uma implementa o de um TAD implementa o do TAD implica na escolha de uma ED para represent -lo, a qual acessada pelas opera es que ele define ED constru da a partir dos Tipos b sicos (integer, real, char) ou dos Tipos estruturados (array, record) de uma linguagem de programa oCaracter sticas de um TAD Caracter stica essencial de TAD a separa o entre a defini o conceitual par (v, o) e a implementa o (ED espec fica)

5 O programa s acessa o TAD por meio de suas opera es, a ED nunca acessada diretamente "ocultamentode informa o" Caracter sticas de um TAD Programador tem acesso a uma descri o dos valores e opera es admitidos pelo TAD Programador n o tem acesso implementa o Idealmente, a implementa o invis vel e inacess vel Ex. pode criar uma lista de clientes e aplicar opera es sobre ela, mas n o sabe como ela representada internamente Quais as vantagens? Vantagens do uso de TADs Reuso: uma vez definido, implementado e testado, o TAD pode ser acessado por diferentes programas Manuten o: mudan as na implementa o do TAD n o afetam o c digo fonte dos programas que o utilizam (decorr ncia do ocultamentode informa o) m dulos do TAD s o compilados separadamente uma altera o for a somente a recompila odo arquivo envolvido e uma nova link-edi o do programa que acessa o TAD O programa mesmo n o precisa ser recompilado!

6 Corre o: TAD foi testado e funciona corretamente15 TADs em C: Exemplo/* TAD: Matriz m por n *//* Tipo Exportado */typedef structmatriz Matriz;/* Fun es Exportadas *//* Fun o cria -Aloca e retorna matriz m por n */Matriz* cria (intm, intn);/* Fun o libera -Libera a mem ria de uma matriz */voidlibera (Matriz* mat); /* */ Note que a composi oda estrutura Matriz (struct matriz) n o est explicita. Dessa forma, os demais m dulos que usarem esse TAD n o poder o acessar diretamente os campos dessa estrutura . Os clientes desse TAD s ter o acesso s informa es que possam ser obtidas atrav s das fun es em C: Exemplo/* Continua *//* Fun o acessa -Retorna o valor do elemento [i][j] */floatacessa (Matriz* mat, inti, intj);/* Fun o atribui -Atribui valor ao elemento [i][j] */voidatribui (Matriz* mat, inti, intj, floatv);/* Fun o linhas -Retorna o no.

7 De linhas da matriz */intlinhas (Matriz* mat);/* Fun o colunas -Retorna o no. de colunas da matriz */intcolunas (Matriz* mat);Arquivo em C: Exemplo#include < >/* malloc, free, exit */#include < >/* printf */#include " structmatriz {intlin;intcol;float*v;};voidlibera (Matriz* mat){free(mat->v);free(mat);}Arquivo em C: Exemplo/* Continua */Matriz* cria (int m, int n) {Matriz* mat = (Matriz*) malloc(sizeof(Matriz));if(mat == NULL) {printf("Mem ria insuficiente!\n");exit(1);}mat->lin = m;mat->col = n;mat->v = (float*) malloc(m*n*sizeof(float));returnmat;}Arq uivo em C: Exemplo/* Continua */floatacessa (Matriz* mat, inti, intj) {intk; /* ndice do elemento no vetor */if(i<0 ||i>=mat->lin||j<0 ||j>=mat->col) {printf("Acesso inv lido!\n");exit(1);}k = i*mat->col+ j; {armazenamento por linha}returnmat->v[k];}intlinhas (Matriz* mat) {returnmat->lin;}Arquivo em C: Exemplo/* Continua */voidatribui (Matriz* mat, int i, int j, float v) {intk; /* ndice do elemento no vetor */if(i<0 || i>=mat->lin || j<0 || j>=mat->col) {printf("Atribui o inv lida!)}}

8 \n");exit(1);}k = i*mat->col + j;mat->v[k] = v;}intcolunas (Matriz* mat) {returnmat->col;}Arquivo cliente que usa o TAD#include < >#include < >#include " "int main(int argc, char *argv[]){float a,b,c,d; Matriz *M;// cria o de uma matriz M = cria(5,5);// inser o de valores na matrizatribui(M,1,2,40);atribui(M,2,3,3) ;atribui(M,3,0,15);atribui(M,4,1,21); /* Continua */// verificando se a inser o foi feita corretamentea = acessa(M,1,2);b = acessa(M,2,3);c = acessa(M,3,0);d = acessa(M,4,1);printf ("M[1][2]: % \n", a);printf ("M[2][3]: % \n", b);printf ("M[3][0]: % \n", c);printf ("M[4][1]: % \n", d); system("PAUSE");return 0;}Exerc cio: TAD Conjuntos (SET) Um conjunto uma cole o de elementos Todos os elementos s o diferentes entre si e a ordem entre eles irrelevante Ex: {1,4} = {4, 1} ok{1,4, 1} n o okOpera es b sicas: uni o, interesec o e diferen a Se A e B s o conjuntos ent o A B o conjunto de elementos que s o membros de A ou B ou ambos Se A e B s o conjuntos ent o A B o conjuntos de elementos que est o em A e B Se A e B s o conjuntos ent o A B o conjunto de elementos em A que n o est o em B.

9 Ex: A = {a,b,c} B = {b,d} A B = {a,b,c,d} A B = {b} A B = {a,c}Opera es usuais Uni o(A,B,C) Intersec o(A,B,C) Diferen a(A,B,C) Membro(x,A) Cria_Conj_Vazio(A) Insere(x,A) Remove(x,A) Atribui(A,B) Min(A) Max(A) Igual(A,B)Defini o das opera es Uni o(A,B,C): toma os argumentos A e B que s o conjuntos e retorna A B variavel C Intersec o(A,B,C): toma os argumentos A e B que s o conjuntos e retorna A B variavel C Diferen a(A,B,C): toma os argumentos A e B que s o conjuntos e retorna A -B variavel C Membro(x,A): toma o conjunto A e o objeto x cujo tipo o tipo do elemento de A e retorna um valor booleano true se x A e false caso contr rio. Cria_Conj_Vazio(A): faz o conjunto vazio ser o valor para a vari vel conjunto A Insere(x,A): toma o conjunto A e o objeto x cujo tipo o tipo do elemento de A e faz x um membro de A.

10 O novo valor de A = A {x}. Se x j um membro de A, ent o a opera o insere n o muda A. Remove(x,A): remove o objeto x, cujo tipo o tipo do elemento de A, de A. O novo valor de A = A {x}. Se x n o pertence a A ent o a opera o remove n o altera A. Atribui(A,B): Seta o valor da vari vel conjunto A = ao valor da vari vel conjunto B. Min(A): retorna o valor m nimo no conjunto A. Esta opera o pode ser aplicada somente quando os membros do par metro A s o linearmente ordenados. Por exemplo: Min({2,3,1}) = 1 e Min({ a , b , c }) = a . Max(A): Similar a Min(A) s que retorna o m ximo do conjunto. Igual(A,B): retorna truese e somente se os conjuntos A e B consistem dos mesmos Implementar?Vetor de Booleanos Op o para conjuntos de inteiros: ithbit truese o elemento est no conjunto ConstN =.