Crie um Tipo Abstrato de Dados (TAD) que represente o tipo conjunto de inteiros, utilizando uma representação de vetor de inteiros e que contenha as seguintes funções:
Intersecção

Passo 1

O enunciado pede para definir um TAD chamado Conjunto de inteiros, usando um vetor interno para armazenar os elementos, e implementar a operação de interseção entre dois conjuntos.

Passo 2

Primeiro, vamos estabelecer a representação interna do TAD: um vetor de inteiros de tamanho máximo fixo e um inteiro que indique quantos elementos efetivamente estão no conjunto. Isso garante acesso direto e controle de capacidade.

Passo 3

Em seguida, precisamos de operações auxiliares fundamentais para trabalhar com o conjunto: criar um conjunto vazio, verificar se um elemento pertence ao conjunto e inserir um elemento (sem duplicatas). Essas operações serão usadas pela interseção.

Passo 4

A operação de interseção recebe dois conjuntos A e B e retorna um novo conjunto C contendo apenas os elementos que aparecem em A e também em B. Podemos percorrer todos os elementos de A e, para cada um, usar o teste de pertencimento em B; se pertencer, inserimos em C.

Passo 5

Por fim, consolidamos tudo numa especificação de TAD, listando o tipo, a representação e a assinatura de cada operação, incluindo o algoritmo detalhado de interseção.

Resposta

TAD Conjunto de Inteiros
Representação:
  • Estrutura interna:
    • vetor: inteiro data[Max]
    • inteiro size // número atual de elementos
  • Invariante: 0 ≤ size ≤ Max e todos os elementos em data[0…size-1] são distintos
Operações:
  1. criaConjunto(): Conjunto
    • Descrição: retorna um conjunto vazio
    • Implementação:
    size ← 0
    // data permanece sem uso até inserção
    retorna Conjunto(data, size)
  2. pertence(C: Conjunto, x: inteiro): booleano
    • Descrição: testa se x ∈ C
    • Implementação:
    para i de 0 até C.size-1 faça
    se C.data[i] = x então
    retorna true
    retorna false
  3. insere(C: Conjunto, x: inteiro): Conjunto
    • Descrição: insere x em C se não estiver presente e se houver espaço
    • Pré-condição: C.size < Max
    • Implementação:
    se ¬pertence(C, x) então
    C.data[C.size] ← x
    C.size ← C.size + 1
    retorna C
  4. interseção(A: Conjunto, B: Conjunto): Conjunto
    • Descrição: retorna o conjunto de todos os elementos que estão em A e em B
    • Implementação:
    C ← criaConjunto()
    para i de 0 até A.size-1 faça
    x ← A.data[i]
    se pertence(B, x) então
    C ← insere(C, x)
    retorna C

Exercícios relacionados