---
breaks: false
tags: edb1
title: '2022-10-10 slide 7 edb1'
---
# EDB1 - slide 7
**Tipo Abstrato de Dados: Conjuntos e Sequências**

# Tipo Abstrato de Dados (TAD)
- Os tipos trabalhados até o momento, como inteiro e ponto flutuante, são tipos já previamente implementados pela linguagem de programação. Não há a preocupação, por parte do programador, sobre como esses tipos são implementados em diferentes sistemas operacionais;
- Já quando falamos de um tipo abstrato de dados, este define a natureza do dado que será armazenado e as operações que podem ser realizadas;
- Modelo matemático que não tem compromisso com a implementação em um computador.
- Existem alguns tipos de dados mais complexos, como os conjuntos, onde a natureza desse tipo é um conjunto de dados de algum outro tipo;
- Podemos aplicar várias operações sobre os esses conjuntos (inserção, remoção, comparação, etc);

# Tipo Abstrato de Dados x Estrutura de Dados
- Uma estrutura de dados é a implementação de um tipo abstrato de dados. Ela define qual o mapeamento entre o tipo de dados e a memória, como um dado específico será armazenado na memória de um computador. Também deve definir quais os algoritmos que vão implementar as operações definidas sobre estes dados.
- A partir de agora vamos explorar os TAD que chamamos de estruturas lineares, os conjuntos e sequências.
- Serão avaliadas as diferentes formas de implementar esses dados através de diferentes estruturas, vamos diferenciar as diferentes implementações, avaliar a qualidade de cada uma delas, entendendo a mais adequada para cada uma delas.

| Tipo abstrato de dados | Estrutura de Dados |
| ----- | ------------------ |
| Define o dado | Define o mapeamento de memória |
| Define as operações | Define o algoritmo da operação |

# Conjuntos e Sequências

## Conjuntos - conceitos
- Conjuntos: Símbolos, letras, números.
- Operações sobre os conjuntos: inserção, remoção, intersecção, união, busca por elementos nos conjuntos.
- Como mapear esses conjuntos? como que implementa-se essas operações?

## Sequências: Tipo especial de um conjunto
- Elementos dispostos numa ordem específica. Inserções, remoções devem observar a posição em que serão realizadas.
- Busca: Por ex, um elemento específico está contido nessa sequencia?
- Ordenação.

## Sequências – no caso de uso de vetor
- Como é mapeado na memoria do computador?
- Vetor: considera um bloco de memoria (sequência) e armazena direto sobre o bloco. Cada elemento da sequência em cada uma das posições de memória.
- Pra implementar é necessária a indicação do início do bloco e do tamanho do bloco.

**Alocando um vetor.**

- Estática: Ocorre na declaração, por ex:

int var [9]

- Dinâmica:

int *var = (int *) malloc (9* sizeof(int));

- Operações a serem trabalhadas:
- Inserção
- remoção
- acesso (ex qual o elemento está na 10ª posição)
- busca (verificar se um elemento está contido no vetor)
- ordenação.

- Análise de diferentes algoritmos para fazer a mesma operação. Quais as diferenças na implementação sobre sequencias ou conjuntos.

:::info
**Obs**: Outro exemplo que será visto mais adiante é a lista ligada, ao invés de vetores.
:::

## Busca em Sequencia
- Verificar se um elemento está ou não contido em uma sequencia.
- Definição do problema:
- Quais são as saídas possíveis (qual a resposta que se pode esperar), quais as condições que levam a cada um dessas respostas.
- Entradas: Sequência e uma chave de busca. Saídas possíveis: verdadeiro e falso. Dependendo se a chave está ou não contida na sequência.
- Instância do problema, por ex: S = 3, 4, 5 , 9, 8, 6, 1. x = 1.
- Solução: verificar se é verdadeiro, se a chave é igual ao elemento pesquisado.
- Objetivo: Encontrar um algoritmo que faça isso.

## Implementação do problema de busca na sequencia

- Vetor: aloca um bloco, cada posição com seu endereço, precisa-se de um apontador que vai apontar para a primeira posição do vetor e um inteiro com o tamanho do número de elementos inseridos no vetor. Também é preciso a chave, o elemento a ser buscado.

Função:

bool busca(char* V, int N, char x)

- `char* V`: Ponteiro que aponta para o início do vetor
- `int N`: valor do tamanho dos dados inseridos
- `char x`: chave de busca

## Exemplo de implementação – Jogo da memória
- 3 operações:
- 1a: selecionar uma carta para avaliar.
- 2a: identificar a carta, acessar.
- 3a: comparar com a chave.
- Essas operações são repetidas, até que a chave seja igual a carta acessada.
- Algoritmos diferentes para fazer as operações, com estratégias diferentes.