Segunda Prova AEDS II UFMG (gabarito)

Prévia do material em texto

Algoritmos e Estruturas de Dados II
Prova 2
Nome: __________________________________________________________________ Turma: ___________
	Q1 (4 pts) 
	Q2 (6 pts)
	Q3 (7 pts)
	Q4 (8 pts)
	Total (25 pts)
	
	
	
	
	
Introdução. Nesta prova você vai usar Lista Encadeada e Heap (vetor alocado dinamicamente) para implementar as principais funções do tipo abstrato de dados ordered_set (conjunto ordenado). Um ordered_set armazena uma coleção de elementos sem repetição, assim como o conjunto que você implementou na lista de exercício. Entretanto, um ordered_set tem duas operações adicionais que retornam e removem o menor elemento no conjunto.
OBS 1. Na Figura 1 (última folha), você pode ver a declaração do TAD ordered_set. Leia agora a definição de cada uma das funções que operam sobre um ordered_set. 
OBS 2. Considere que o tipo dos elementos no ordered_set (Type) estão definidos por um typedef. Você pode assumir em todas as questões que os operadores relacionais (<, >, =, etc.) estão definidos para este tipo.
OBS 3. Qualquer função auxiliar que você usar (faça ela parte do TAD ordered_set ou não) deve ser implementada, exceto aquelas explicitamente indicadas no enunciado da questão. 
OBS 4. Você pode usar um struct ou uma função auxiliar que você implementou para uma questão específica em qualquer outra questão da prova, bastando apenas indicar em qual questão da prova o struct a função auxiliar está implementada.
OBS 5. Em todas as questões, você deve descrever precisamente quais as estruturas de dados (e.g. struct ordered_set_t, struct Node, etc.) que você está utilizando para implementar as funções. Isto é fundamental para que sua questão possa ser corrigida corretamente. Caso as estruturas de dados utilizadas não sejam descritas, a questão não será corrigida.
OBS 6. A prova é sem consulta e sem perguntas. A interpretação das questões faz parte do processo de avaliação.
OBS 7. As respostas devem estar dentro dos respectivos quadros de resposta. Você pode usar o verso das folhas como rascunho. 
OBS 8. Você pode fazer a prova a lápis. Por favor, assine todas as folhas de sua prova assim que recebê-la.
Questão 1. Implemente a função void erase (Type k, ordered_set s). Assuma que ordered_set está implementado com listas duplamente encadeadas circulares com sentinela, e que os elementos estão ordenados do menor para o maior nesta lista.
	
struct Node{
 Type key;
 struct Node* prev; // Nó a esquerda.
 struct Node* next; // Nó a direita.
};
struct ordered_set_t{
 struct Node* end; // Nó sentinela.
 int size; // Número de elementos no conjunto.
};
void erase(Type k, ordered_set s) {
 for (struct Node* x = s->end->next; x != s->end; x = x->next) {
 if (x->key == k) {
 // Remove x da lista duplamente encadeada.
 x->prev->next = x->next;
 x->next->prev = x->prev;
 free(x);
 s->size--;
 }
 }
}
Questão 2. Implemente a função void insert(Type k, ordered_set s). Assuma que ordered_set está implementado com listas duplamente encadeadas circulares com sentinela, e que os elementos estão ordenados do menor para o maior nesta lista.
	
void insert(Type k, ordered_set s) {
 struct Node* x = s->end->next;
 while (x != s->end && x->key < k) {
 x = x->next;
 }
 if (x == s->end || x->key > k) {
 // Cria um novo nó e insere ele antes de x.
 struct Node* node = malloc(sizeof(struct Node));
 node->key = k;
 node->prev = x->prev;
 node->next = x;
 // Ajusta o valor dos ponteiros dos nós adjacentes ao novo nó.
 node->prev->next = node;
 node->next->prev = node;
 s->size++;
 }
}
Questão 3. Implemente a função void erase_min(ordered_set s). Assuma que ordered_set está implementado como um vetor alocado dinamicamente onde os elementos estão dispostos de acordo com um Heap de minimização, ou seja, o pai de cada elemento tem valor menor ou igual ao dele. 
DICA: implemente uma função auxiliar MinHeapfy, semelhante a vista em sala de aula. 
	
void swap(Type* a, Type* b) {
 Type aux = *a;
 *a = *b;
 *b = aux;
}
void MinHeapfy(int n, Type v[], int i) {
 int l = left(i);
 int r = right(i);
 int smallest = i;
 if (l < n && v[l] < v[i]) {
 smallest = l;
 }
 if (r < n && v[r] < v[smallest]) {
 smallest = r;
 }
 if (smallest != i) {
 swap(&v[i], &v[smallest]);
 MinHeapfy(n, v, smallest);
 }
}
void erase_min(ordered_set s) {
 s->array[0] = s->array[s->size - 1];
 s->size--;
 MinHeapfy(s->size, s->array, 0);
}
Questão 4. Implemente a função void insert(Type k, ordered_set s). Assuma que ordered_set está implementado como um vetor alocado dinamicamente, onde os elementos estão dispostos de acordo com um Heap de minimização, ou seja, o pai de cada elemento tem valor menor ou igual ao dele. 
DICA: Implemente e utilize uma função reserve(int m, ordered_set s) que aumenta a capacidade do vetor alocado dinamicamente para pelo menos m elementos.
	
bool find(Type k, ordered_set s) {
 for (int i = 0; i < s->size; i++) {
 if (s->array[i] == k) {
 return true;
 }
 }
 return false;
}
void reserve(int m, ordered_set s) {
 if (m > s->capacity) {
 s->capacity = m;
 Type* aux = malloc(m * sizeof(Type));
 for (int i = 0; i < s->size; i++) {
 aux[i] = s->array[i];
 }
 free(s->array);
 s->array = aux;
 }
}
void insert(Type k, ordered_set s) {
 if (!find(k, s)) {
 // Insere k no fim do vetor.
 if (s->size == s->capacity) {
 reserve(2 * s->capacity, s);
 }
 s->array[s->size] = k;
 s->size++;
 // Sobe k até que o vetor volte a ser uma heap.
 int i = s->size - 1;
 while (i > 0 && s->array[parent(i)] > s->array[i]) {
 swap(&s->array[parent(i)], &s->array[i]);
 i = parent(i);
 }
 }
}
	#ifndef ORDERED_SET_H_
#define ORDERED_SET_H_
#include <stdbool.h>
// Tipo dos elementos no conjunto.
typedef float Type;
// Tipo de dado ordered_set (Conjunto Ordenado).
// Para garantir o ecapsulamento, 'struct ordered_set_t' só é definido em ordered_set.c.
typedef struct ordered_set_t* ordered_set;
// Cria um conjunto vazio.
ordered_set new_ordered_set();
// Testa se o cojunto está vazio.
bool empty(ordered_set s);
// Retorna o número de elementos no conjunto.
int size(ordered_set s);
// Retorna o menor elemento de s.
// PRECONDIÇÃO: s tem pelo menos um elemento.
Type min(ordered_set s);
// Verifica se k pertence a s.
bool find(Type k, ordered_set s);
// Insere k no conjunto.
// Caso k já pertença ao conjunto, um novo elemento NÃO é inserido.
void insert(Type k, ordered_set s);
// Remove k do conjunto (caso lá ele esteja).
void erase(Type k, ordered_set s);
// Remove o menor elemento de s.
// PRECONDIÇÃO: s tem pelo menos um elemento.
void erase_min(ordered_set s);
// Remove todos os elementos do conjunto.
void clear(ordered_set s);
// Faz com que o conjunto q contenha exatamente os mesmos elementos
// do cojunto s.
void copy(ordered_set s, ordered_set q);
// Libera toda a memória alocada para o conjunto.
void delete_ordered_set(ordered_set s);
#endif // ORDERED_SET_H_
Figura 1: Tipo abstrato de dados ordered_set.
7/9