Hashset

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define fator 0.75
#define capacidade_inicial 7

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node** table;
    int capacidade;
    int size;
} Hash;

Node* cria_no(int valor) {
    Node* novo = (Node*)malloc(sizeof(Node));
    novo->data = valor;
    novo->next = NULL;
    return novo;
}

Hash* cria_hash() {
    Hash* hash = (Hash*)malloc(sizeof(Hash));
    hash->table = (Node**)malloc(capacidade_inicial * sizeof(Node*));
    for (int i = 0; i < capacidade_inicial; i++) {
        hash->table[i] = NULL;
    }
    hash->capacidade = capacidade_inicial;
    hash->size = 0;
    return hash;
}

int dispercao(int key, int capacidade) {
    return key % capacidade;
}

void resize(Hash* hash, int nova_capacidade) {
    Node** newTable = (Node**)malloc(nova_capacidade * sizeof(Node*));
    for (int i = 0; i < nova_capacidade; i++) {
        newTable[i] = NULL;
    }

    for (int i = 0; i < hash->capacidade; i++) {
        Node* current = hash->table[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            int newIndex = dispercao(temp->data, nova_capacidade);
            temp->next = newTable[newIndex];
            newTable[newIndex] = temp;
        }
    }
    free(hash->table);
    hash->table = newTable;
    hash->capacidade = nova_capacidade;
}

bool has(Hash* hash, int valor, int* comparisons) {
    int index = dispercao(valor, hash->capacidade);
    Node* current = hash->table[index];
    *comparisons = 1;
    while (current != NULL) {
        if (current->data == valor) {
            return true;
        }
        current = current->next;
        (*comparisons)++;
    }
    return false;
}

bool add(Hash* hash, int valor, int* comparisons) {
    int index = dispercao(valor, hash->capacidade);
    Node* novo = cria_no(valor);

    if (has(hash, valor, comparisons))
    return false;

    novo->next = hash->table[index];
    hash->table[index] = novo;
    hash->size++;

    float loadFactor = (float)hash->size / hash->capacidade;
    if (loadFactor > fator) {
        resize(hash, 2 * hash->capacidade - 1);
    }
    return true;
}

bool del(Hash* hash, int valor, int* comparisons) {
    int index = dispercao(valor, hash->capacidade);
    Node* current = hash->table[index];
    Node* prev = NULL;
    *comparisons = 1;
    while (current != NULL) {
        if (current->data == valor) {
            if (prev == NULL) {
                hash->table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            hash->size--;
            return true;
        }
        prev = current;
        current = current->next;
        (*comparisons)++;
    }
    return false;
}

void print(Hash* hash) {
    int max_tam = 0;
    int num_elementos = 0;
    for (int i = 0; i < hash->capacidade; i++) {
        int count = 0;
        Node* current = hash->table[i];
        while (current != NULL) {
            count++;
            current = current->next;
        }
        if (count > max_tam) {
            max_tam = count;
        }
        num_elementos += count;
    }
    printf("%d %d %d\n", hash->capacidade, num_elementos, max_tam);
}

void freeHash(Hash* hash) {
    for (int i = 0; i < hash->capacidade; i++) {
        Node* current = hash->table[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(hash->table);
    free(hash);
}

int main() {
    Hash* myTable = cria_hash();
    char comando[4];
    int i = 0;
    while (true) {
        int valor;
        int comparisons = 0;
        if(scanf("%3s", comando) != 1){
            break;
        }
        printf("%d ", i);
        if (!strcmp(comando, "ADD")) {
            scanf("%d",&valor);
            printf("%d %d ", add(myTable, valor, &comparisons), comparisons);
        } else if (!strcmp(comando, "DEL")) {
            scanf("%d",&valor);
            printf("%d %d ", del(myTable, valor, &comparisons), comparisons);
        } else if (!strcmp(comando, "HAS")) {
            scanf("%d",&valor);
            printf("%d %d ", has(myTable, valor, &comparisons), comparisons);
        } else if (!strcmp(comando, "PRT")) {
            print(myTable);
        }
        i++;
        printf("\n");
    }
    freeHash(myTable);
    return 0;
}