Tipos Abstratos de Dados TADs - Fundamentos e Implementacao

Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências ECOI04 Algoritmos e Estrutura de Dados I Tipos Abstratos de Dados Sandro Izidoro Universidade Federal de Itajubá UNIFEI Campus Itabira 13 de janeiro de 2022 Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 1 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Sumário 1 Fundamentos 2 Tipos Abstratos de Dados TADs 3 Implementação de TADs 4 Exemplo 5 Referências Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 2 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Fundamentos Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 3 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Fundamentos Algoritmo Sequência de ações executáveis para a solução de um determinado tipo de problema Em geral algoritmos trabalham sobre Estruturas de Dados Estruturas de Dados Conjunto de dados que representa uma situação real Abs tração da realidade Representação dos dados Dados podem estar representados estruturados de diferentes maneiras Normalmente a escolha da representação é determinada pelas operações que serão utilizadas sobre eles Em linguagens de programação o tipo de dados de uma variável define o conjunto de valores que a variável poderá assumir Por exemplo uma variável do tipo boo lean pode assumir dois valores true ou false Uma variável declarada em C especifica duas coisas 1 A quantidade de bytes que devem ser reservadas para a variável 2 Como o dado representado por esses bytes deve ser interpretado Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 4 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Tipos Abstratos de Dados TADs Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 5 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Tipos Abstratos de Dados TADs Um TAD pode ser visto como um modelo matemático acompanhado das opera ções definidas sobre o modelo O conjunto dos inteiros acompanhado das operações de adição subtração e mul tiplicação forma um exemplo de um tipo abstrato de dados A representação do modelo matemático por trás do tipo abstrato de dados é reali zada mediante uma estrutura de dados TADs podem ser considerados generalizações de tipos primitivos de dados da mesma forma que procedimentos são generalizações de operações primitivas tais como adição subtração e multiplicação Da mesma forma que um procedimento é usado para encapsular partes de um algoritmo o TAD pode ser usado para encapsular tipos de dados Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 6 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Tipos Abstratos de Dados TADs Usuário do TAD x Programador do TAD Usuário só enxerga a interface não a implementação Dessa forma o usuário pode abstrair da implementação específica Qualquer modificação nessa implementação fica restrita ao TAD A escolha de uma representação específica é fortemente influenciada pelas ope rações a serem executadas Podemos considerar uma aplicação que utilize uma lista de inteiros Poderíamos definir um tipo abstrato de dados Lista com as seguintes operações sobre a lista 1 Faça a lista vazia 2 Obtenha o primeiro elemento da lista Se a lista estiver vazia então retorne nulo 3 Insira um elemento na lista Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 7 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Implementação de TADs Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 8 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Implementação de TADs Em linguagens orientadas por objeto C Java a implementação é feita através de classes Em linguagens estruturadas C Pascal a implementação é feita pela definição de tipos juntamente com a implementação de funções Estruturas Uma estrutura é uma coleção de uma ou mais variáveis possivel mente de tipos diferentes colocadas juntas sob um único nome para manipulação conveniente Por exemplo para representar um aluno são necessárias as informa ções nome matrícula conceito Ao invés de criar três variáveis é possível criar uma única variável contendo três campos 1 struct Aluno 2 char nome 1 0 0 3 int matricula 4 char conceito 5 Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 9 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Implementação de TADs Declaração de Tipos Para simplificar uma estrutura ou mesmo outros tipos de dados podem ser definidos como um novo tipo Em C usando typedef 1 typedef struct 2 char nome 1 0 0 3 int matricula 4 char conceito 5 TipoAluno 6 7 typedef int 10 Vetor Para implementar um TAD utilizase a definição de tipos juntamente com a imple mentação de funções que agem sobre aquele tipo Como boa prática de programação evitase acessar o dado diretamente fazendo o acesso só através das funções Uma boa técnica de programação é implementar os TADs em arquivos separados do programa principal Por exemplo NomeDoTADh com a declaração NomeDoTADcpp com a implementação O programa ou outros TADs que utilizam o seu TAD devem inserir da seguinte maneira include NomeDoTADh Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 10 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Exemplo Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 11 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Exemplo Um TAD ContaBancaria com os campos número e saldo onde os clientes podem fazer as seguintes operações 1 Iniciar uma conta com um número e saldo inicial 2 Depositar um valor 3 Sacar um valor 1 Codigo de definicao ContaBancaria h 2 3 ifndef CONTAH 4 define CONTAH 5 6 definicao do t i p o 7 typedef struct 8 int numero 9 double saldo 10 ContaBancaria 11 12 Prototipo das funcoes 13 void I n i c i a l i z a ContaBancaria int double 14 void I n i c i a l i z a ContaBancaria int float 15 void I n i c i a l i z a ContaBancaria int 16 17 void Deposito ContaBancaria double 18 void Saque ContaBancaria double 19 void Imprime ContaBancaria 20 21 void Transferencia ContaBancaria ContaBancaria double 22 23 24 endif Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 12 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Exemplo ContaBancariacpp I 1 Implementando as funcoes da ContaBancaria 2 3 include iostream 4 include ContaBancaria h 5 6 using namespace std 7 8 void I n i c i a l i z a ContaBancaria conta int numero double saldo 9 conta numero numero 10 conta saldo saldo 11 12 13 void I n i c i a l i z a ContaBancaria conta int numero float saldo 14 conta numero numero 15 conta saldo double saldo 16 17 18 void I n i c i a l i z a ContaBancaria conta int numero 19 conta numero numero 20 conta saldo 00 21 22 23 void Deposito ContaBancaria conta double valor 24 conta saldo valor 25 26 27 void Saque ContaBancaria conta double valor 28 conta saldo valor Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 13 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Exemplo ContaBancariacpp II 29 30 31 void Imprime ContaBancaria conta 32 cout Dados da conta endl 33 cout Numero conta numero endl 34 cout Saldo conta saldo endl 35 cout endl 36 37 38 void Transferencia ContaBancaria c1 ContaBancaria c2 double valor 39 Saque c1 valor 40 Deposito c2 valor 41 Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 14 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Exemplo maincpp I 1 Programa p r i n c i p a l 2 3 include iostream 4 include ContaBancaria h 5 6 using namespace std 7 8 int main 9 10 ContaBancaria conta1 conta2 conta3 11 12 I n i c i a l i z a conta1 1234 30000 13 I n i c i a l i z a conta2 5678 50000 14 I n i c i a l i z a conta3 5679 15 16 cout Antes da movimentacao endl 17 18 Imprime conta1 19 Imprime conta2 20 Imprime conta3 21 22 Deposito conta1 5000 23 Saque conta1 7000 24 25 cout Depois da movimentacao endl 26 27 Imprime conta1 28 Imprime conta2 Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 15 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Exemplo maincpp II 29 30 Transferencia conta2 conta1 100 31 32 Imprime conta1 33 Imprime conta2 34 35 return 0 36 Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 16 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Referências Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 17 18 Fundamentos Tipos Abstratos de Dados TADs Implementação de TADs Exemplo Referências Referências 1 Material elaborado a partir das notas de aula do professor Edmilson Marmo Moreira UNIFEI 2 Deitel H M Deitel P J C Como Programar 5a edição Porto Alegre Bookman 2009 3 Victorine Viviane Mizrahi Treinamento em Linguagem C Módulo 1 e 2 Makon Books São Paulo 2007 4 Ziviani Nivio Projeto de algoritmos com implementações em Pascal e C 3 ed rev e ampl São Paulo Cengage Learning 2011 5 Feofiloff Paulo Algoritmos em linguagem C Rio de Janeiro Elsevier 2009 6 Drozdek Adam Estrutura de Dados e Algoritmos em C Pioneira Thomson Learning São Paulo 2002 Sandro Izidoro UNIFEI ICT ECOI04 13 de janeiro de 2022 18 18