DM_SC

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

#define MAX 100 // Broj bucket-a u hash tablici
#define MAX_LINE_LENGTH 100
#define MAX_WORDS 80 // Maksimalan broj riječi

struct element {
    char *data;
    struct element *next;
};

struct element *ht[MAX];
int num_elements = 0; // Ukupan broj elemenata u hash tablici
int num_collisions = 0; // Broj kolizija

// Inicijalizacija hash tablice
void inicijalizacija() {
    for (int i = 0; i < MAX; i++) {
        ht[i] = NULL;
    }
}

// Hash funkcija koristeći Division Method
int hash(char *value) {
    int sum = 0;
    for (int i = 0; value[i] != '\0'; i++) {
        sum += value[i];
    }
    return sum % MAX;
}

// Insert funkcija s brojanjem kolizija i provjerom load factora
void insert(char *value) {
    if ((float)num_elements / MAX > 0.75) {
        printf("Hash tablica load factor premašuje 0.75. Nove riječi se ne dodaju.\n");
        return;
    }

    struct element *novi = malloc(sizeof(struct element));
    novi->data = strdup(value); // Kopiraj string kako bi izbjegli prepisivanje
    novi->next = NULL;

    int index = hash(value);
    if (ht[index] == NULL) {
        ht[index] = novi;
    } else {
        // Kolizija detektirana
        num_collisions++;
        struct element *tmp = ht[index];
        int found = 0;
        while (tmp) {
            if (strcmp(tmp->data, value) == 0) {
                found = 1;
                break;
            }
            tmp = tmp->next;
        }
        if (!found) {
            novi->next = ht[index];
            ht[index] = novi;
        } else {
            free(novi->data);
            free(novi);
            printf("Element '%s' već postoji!\n", value);
        }
    }
    num_elements++;
}

// Funkcija za mjerenje vremena unosa i brojanje kolizija
void measure_insertion_time(FILE *file) {
    char line[MAX_LINE_LENGTH];
    int word_count = 0;
    clock_t start, end;
    double total_time;

    start = clock();
    while (fgets(line, MAX_LINE_LENGTH, file) && word_count < MAX_WORDS) {
        line[strcspn(line, "\n")] = '\0'; // Ukloni novi red
        insert(line);
        word_count++;
    }
    end = clock();
    total_time = ((double)(end - start)) / CLOCKS_PER_SEC;

    printf("Vrijeme unosa: %f sekundi\n", total_time);
    printf("Broj riječi: %d\n", word_count);
    printf("Broj kolizija: %d\n", num_collisions);
}

int main() {
    FILE *in_file = fopen("words.txt", "r");
    if (!in_file) {
        printf("Nije moguće otvoriti datoteku!\n");
        exit(-1);
    }

    inicijalizacija();
    measure_insertion_time(in_file);

    fclose(in_file);
    return 0;
}