Lista de Exercício 3 - MC404 2025

The only way to learn a new programming language is by writing programs in it. – Dennis Ritchie

Exercício 1

Vamos praticar as normas da ABI RISC-V, criando funções de uma heap de mínimos.

Uma heap de mínimos é uma estrutura de dados que permite armazenar números inteiros de forma que o menor número esteja sempre na raiz da árvore e todos os filhos são maiores ou iguais ao seu pai. A heap de mínimos é uma árvore binária completa, logo é armazenada em um vetor ao invés de uma lista encadeada. A raiz da árvore está na posição 0 do vetor, o filho esquerdo de um nó na posição i está na posição 2i+1 e o filho direito de um nó na posição i está na posição 2i+2. O pai de um nó na posição i está na posição (i-1)/2. Elementos nulos são representados por -1.

Entretanto para aumentar o desafio não daremos alguma função de alocação dinâmica de memória, então você deve implementar uma heap de mínimos com um vetor estático e não terá acesso a última posição da heap.

Atenção: utilize a funções puts e exit já implementadas em outros labs no seu arquivo .s

O arquivo .c ao qual seu código .s será vinculado pode ser encontrado através deste link

1.1 Inserção em heap

Você deve implementar uma função que insere um número em uma heap de mínimos. A função deve receber o número a ser inserido, endereço inicial da heap e o tamanho do buffer. A função deve retornar -1 se a heap estiver cheia. Cuidado para não estragar a heap. Dica: faça de baixo para cima. A função deve seguir a seguinte assinatura:

int insert(int number, int* heap, int size);

1.2 Remoção do mínimo

Você deve implementar uma função que remove o menor número da heap de mínimos. A função deve retornar o menor número. Se a heap estiver vazia retorne -2. Nessa função ao invés de retornar em a0 você deverá retornar no apontador ret. A função deve seguir a seguinte assinatura:

void remove_min(int* heap, int size, int* ret);

Exercício 2

Agora vamos praticar a ABI RISC-V com um pouco mais de complexidade, implementando uma função que insere nós em uma árvore binária não convecional. A qual possui a seguinte estrutura:

struct Node {
    int x, y;
    struct Node* left;
    struct Node* right;
};

Sendo x e y as coordenadas do nó em um plano cartesiano que tem pontos apenas no domínio dos naturais. A árvore é construída da seguinte forma: - Se o nó a ser inserido tem x menor que o nó atual, ele deve ser inserido na subárvore esquerda. - Se o nó a ser inserido tem x maior que o nó atual, ele deve ser inserido na subárvore direita. - Se o nó a ser inserido tem x igual ao nó atual, mas y menor, ele deve ser inserido na subárvore esquerda. - Se o nó a ser inserido tem x igual ao nó atual, mas y maior, ele deve ser inserido na subárvore direita. - Para simplificar não existem x's e y's iguais. Atenção: coloque as funções puts e exit previamente implementadas em outros exercícios no .s Você deve implementar uma função que insere um nó na árvore binária. A função deve receber o apontador para head e o nó a ser inserido. A função tem retorno void

void insert_node(struct Node* head, struct Node* node);

O arquivo .c ao qual seu código .s será vinculado pode ser encontrado através deste link