Tipos Abstratos de Dados

Entendendo TADs e criando TADs simples (com Douglas Macharet)

Definição

  1. Modelo matemático, acompanhado das operações definidas sobre o modelo.
    • Conjunto dos inteiros acompanhado das operações de adição, subtração e multiplicação.
    • A implementação do algoritmo em uma linguagem de programação exige a representação do TAD em termos dos tipos de dados e dos operadores suportados.

Contrato

  1. TADs são contratos
  2. Funções que operam em cima da memória

Encapsulamento

  1. Conceito importante em TADs
    • Usuário:
      • Enxerga a interface
      • Não se preocupa, em primeiro momento, como é o TAD por baixo

Definindo Contratos

O que é um contrato?

  1. Acordo entre duas ou mais partes
    • Quais contratos existem em um programa?
    • Requisitos de funcionalidade, desempenho, …
  2. Operações disponíveis em um TAD
    • Entradas e saídas

Ideia de Contratos

TADs vs Structs

Então TADs são structs?

  1. Não!
  2. TADs são um conceito mais geral
  3. Existem em qualquer tipo de linguagem
  4. Em C++:
    • Sim, mapeiam bem para structs/classes + .h
    • Ou para interfaces
      • Assuntos futuro

TADs vs Algoritmos

Algoritmo

  1. Sequência de ações executáveis: entrada → saída
  2. Algoritmos usam TADs

TADs

  1. Contrato + Memória
  2. Podemos considerar TADs como generalizações de tipos primitivos e procedimentos como generalizações de operações primitivas.
  3. O TAD encapsula tipos de dados. A definição do tipo e todas as operações ficam localizadas numa seção do programa.
  4. Os usuários do TAD só tem acesso a algumas operações disponibilizadas sobre esses dados

Em outras Linguagens

  1. TADs são um conceito de programação
  2. Vamos aprender como implementar os mesmos usando classes e objetos
  3. Outras linguagens
    • structs + funções ( C )
    • traits ( Rust )
    • duck typing ( Python, Ruby )
    • classes e interfaces ( Java, C++ )

Como criar um TAD?

Supondo que vamos criar um TAD qualquer. Temos que responder:

  1. Como organizar a memória?
    • Quais dados vão no struct/classe
  2. Quais operações?
    • Contratos

A primeira pergunta é mais de implementação, o TAD é descrito pela 2.

Como fazer um TAD ponto?

Primeiro problema

  1. Quais dados temos que representar?
    • Valor no eixo-x
    • Valor no eixo-y

Vamos fazer em C:

typedef struct {
  double _x;
  double _y;
} ponto_t;

int main() {
  ponto_t p = {1.0, 2.0};
  return 0;
}

Destrinchando

  1. Observe como começamos dizendo que vamos criar um tipo novo: typedef.
  2. Após isto, dizemos que este tipo é um struct
  3. Depois damos um nome ponto_t.
    • Eu pessoalmente gosto de nomear structs com _t no fim
    • Eu também gosto de colocar um _ antes dos nomes dos campos internos. Isto é estilo. Não é uma regra.
typedef struct {
  double _x;
  double _y;
} ponto_t;

em C++

  1. A chamada é bem diferente mas com sentido
  2. Em breve vamos olhar para tudo com calma
class Ponto {
  private:
    double _x;
    double _y;

  public:
    Ponto(double x, double y) {
      _x = x;
      _y = y;
    }
};

int main() {
  Ponto p = Ponto(2.0, 3.0);
  return 0;
}

SOCORRO!!!!

  1. CLASS
  2. PUBLIC
  3. PRIVATE!

Visibilidade

  1. O public indica tudo que você tem acesso
  2. O private você não tem
  3. Por exemplo, o código abaixo vai falhar:
class Ponto {
  private:
    double _x;
    double _y;

    Ponto(double x, double y) {
      _x = x;
      _y = y;
    }
};

int main() {
  Ponto p = Ponto(2.0, 3.0);
  return 0;
}

É impossível fora da Classe acessar campos private.

Construtores

  1. Funções que iniciam o struct
  2. Chamadas de construtores
// ...

public:
  Ponto(double x, double y) {
    _x = x;
    _y = y;
  }

// ...
  1. Observe como a mesma apenas seta a memória!
  2. Preste atenção no passo a passo do C++ tutor acima.

Métodos

  1. Um método pode ser visto como uma função em C
  2. Porém a mesma pertence ao objeto. Falamos com o mesmo.
class Ponto {
  private:
    double _x;
    double _y;

  public:
    Ponto(double x, double y) {
      _x = x;
      _y = y;
    }

    void imprime() {
      std::cout << _x;
      std::cout << _y;
    }
};

int main() {
  Ponto p = Ponto(2.0, 3.0);
  p.imprime();
  return 0;
}

Em sala de Aula

Vamos criar um TAD String

  1. Entender melhor como criar um TAD
  2. Operações além da impressão
    • Substring
    • Starts With (Começa com)
    • Size
  3. O código inicial se encontra abaixo

Importância da Visibilidade

  1. Descomente as linhas que tentam acessar o _size do exemplo
  2. Temos um erro de compilação!
  3. Nunca quebramos a coerência do estado!

std::string

  1. Na prática já temos um tipo string para fazer uso
  2. Basta realizar include <string> como na aula anterior
  3. O nosso exemplo foi apenas para motivar TADs
  4. Leia a documentação da string de C++ aqui

Notas Finais

  1. Estamos iniciando o assunto da matéria
  2. Lembre-se que:
    • TADs → dados + operações
    • TADs guardam estado
  3. Podemos usar um struct em C
  4. Em C++ usamos classes

Notas Finais

Esses TADs são iguais ou diferentes?

class Ponto {
  private:
    float _x;
    float _y;
  public:
    Ponto(float x, float y) {
      _x = x;
      _y = y;
    }
}

class Ponto {
  private:
    float _r;
    float _theta;
  public:
    Ponto(float r, float theta) {
      _r = r;
      _theta = theta;
    }
}
  1. Iguais (em conceito)
    • Abstração do mesmo conceito da matemática
  2. Diferentes (em dados)!
  3. Tipo/TAD
    • Elementos com propriedades semelhantes
    • Clientes dependem do conceito geral

Notas Finais

  1. A implementação não deve ser conhecida
  2. A abstração deve prover os métodos que serão utilizados para manipular os dados

Próximas Aulas

  1. Usando alguns TADs mais complexos
  2. Criando TADs mais complexos
  3. Separando em módulos

Aonde queremos chegar Com TADs queremos que o resto do programa seja cliente. Apenas use as operações do mesmo.