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
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:
-
criaConjunto(): Conjunto
• Descrição: retorna um conjunto vazio
• Implementação:
size ← 0
// data permanece sem uso até inserção
retorna Conjunto(data, size) -
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 -
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 -
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