Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
11 kB
6
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

typedef struct NodeO {
    int *keys;
    int *ocupado;
} NodeO;

typedef struct NodeC{
    int *slot[2];
    int *ocupado[2];
} NodeC;


Node* criaHT(int size) {
    Node* table = malloc(sizeof(Node) * size);
    for(int i=0; i<size; i++)
        table[i] = NULL;
    return table;
}

int hash(int key, int size) {
    return key % size;
}

Node criaN(int key) {
    Node newNode = malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;
    return newNode;
}

void insereL(Node* table, int key, int size) {
    int index = hash(key, size);
    Node newNode = criaN(key);
    if(table[index] == NULL) {
        table[index] = newNode;
        printf("%d -> %d\n", index, key);
        printf("OK\n");
    } 
    else {
        Node temp = table[index]; //loop para checkar se a key ja existe
        while(temp != NULL) {
            if(temp->key == key) {
                printf("Key %d EXISTS\n", key);
                return;
            }
            temp = temp->next;
        }
        newNode->next = table[index];//adicionar na head
        table[index] = newNode;
        printf("%d -> %d\n", index, key);
        printf("OK\n");
    }
}

void apagaL(Node* table, int key, int size) {
    int index = hash(key, size);
    Node temp = table[index];
    Node prev = NULL;
    while(temp != NULL) {
        if(temp->key == key) {
            if(prev == NULL) {
                table[index] = temp->next;
            } else {
                prev->next = temp->next;
            }
            free(temp);
            printf("OK\n");
            
            return;
        }
        prev = temp;
        temp = temp->next;
    }
    printf("NO\n");
}

void pesquisaL(Node* table, int key, int size) {
    int index = hash(key, size);
    Node temp = table[index];
    while(temp != NULL) {
        if(temp->key == key) {
            printf("%d\n", index);
            return;
        }
        temp = temp->next;
    }
    printf("NO\n");
}

void printL(Node* table, int size) {
    for(int i=0; i<size; i++) {
        Node temp = table[i];
        if(temp != NULL) {
            printf("%d", i);
            while(temp != NULL) {
                printf(" %d", temp->key);
                temp = temp->next;
            }
            printf("\n");
        }
    }
}

//-------------------------

int existeO(NodeO* table, int key, int size){
    int index = hash(key, size);
    int aux = key;
    int i = 0;
     
    for(; i < size+1;i++){
    if (table->keys[index] == key) return index;
    index = hash(aux++,size);
    }
    return -1;
}

NodeO* criaO (int size){
    NodeO* table = malloc(sizeof(NodeO));
    table->keys = malloc(sizeof(int) * size);
    table->ocupado = malloc(sizeof(int) * size);

    for (int i = 0; i < size; i++) {
        table->keys[i] = -1;//N PODE SER 0
        table->ocupado[i] = 0;
    }
    return table;
}
int insereO(NodeO* table, int key, int size) {
    int index = hash(key, size);
    int existe = existeO(table,key,size);
    int count = 0;
    int del = -1;
   
    while (count != size+1){
     
    if((table->ocupado[index] == 0 || table->ocupado[index] == del) && existe == -1) {
        table->keys[index] = key;
        table->ocupado[index] = 1;
        printf("%d -> %d\n", index, key);
        printf("OK\n");
        return 0;
    }
    else if(existe!=-1){
    printf("%d EXISTS\n",table->keys[existe]);
    for (int i = 0; i < size; i++) {
        if (table->ocupado[index] != 1) {
        table->keys[index] = key;
        table->ocupado[index] = 1;
        table->keys[existe] = -1;
        table->ocupado[existe] = del;
        return 0;
        }
        else if(table->ocupado[index] == 1 && table->keys[index]==key){
            return 0;
        }

        index = (index + 1) % size;
    }
    } 
    else if (table->ocupado[index]==1){
        index = (index + 1) % size;
        count++;        
    }   
}
    printf("GIVING UP!\n");
    return 6;
    
}

void apagaO(NodeO* table, int key, int size){
    int index = hash(key, size);
    int del = -1;
    int count = 0;

    while (count!=size+1){
    if(table->keys[index]==key){
    table->ocupado[index] = del;
    printf("OK\n");
    return;
    }

    else {
    if(table->keys[index]!=key)
    index = (index + 1) % size;
    count++;
    }
}
    printf("NO\n"); 
    return;

}

int pesquisaO(NodeO* table, int key, int size){
    int index = hash(key,size);
    int count = 0;
    int delIndex = -1;

    while(count != size){
        if (table->ocupado[index] == -1 && delIndex == -1){
            delIndex = index;
        }
        if (table->keys[index] == key && table->ocupado[index] == 1){
            if (delIndex != -1) {
                table->keys[delIndex] = key;
                table->ocupado[delIndex] = 1;
                table->keys[index] = -1;
                table->ocupado[index] = -1;
                printf("%d\n",delIndex);
            } else {
                printf("%d\n",index);
            }
            return 0;
        }
        index = (index + 1) % size; 
        count++;
    }
    printf("NO\n");
    return 0;        
}
    

void printO(NodeO* table, int size){

    for(int i = 0; i < size;i++){
    if(table->ocupado[i]!=0){
        if(table->ocupado[i] == -1) printf("%d\t%c\n",i,'D');
        else printf("%d\t%d\n",i,table->keys[i]);
    }
    }
}

//--------------------------------------------------

int hash2(int key, int size) {
    return (key/size) % size;
}
NodeC* criaHTC(int size) {
    NodeC* table = malloc(sizeof(NodeC));
    for(int i=0; i<2; i++) {
        table->slot[i] = malloc(sizeof(int) * size);
        table->ocupado[i] = malloc(sizeof(int) * size);
        for(int j=0; j<size; j++) {
            table->ocupado[i][j] = 0;
        }
    }
    return table;
}


int insereC(NodeC* table, int key, int size) {
    int n = 0;
    while (n <=size) {
        for(int j=0; j<2; j++) {
            int h = j == 0 ? hash(key, size) : hash2(key, size);
            if (!table->ocupado[j][h]) {
            table->slot[j][h] = key;
            table->ocupado[j][h] = 1;
            printf("%d %d -> %d\n", j, h, key);
            printf("OK\n");
            return 0;
            } 
            else {
            int temp = table->slot[j][h];
            table->slot[j][h] = key;
            key = temp;//***
            printf("%d %d -> %d\n", j, h, table->slot[j][h]);
            n++; 
            }
        if (n==size+1){
        printf("GIVING UP!\n");
        return 6;
        }
        } 
    }
    return 0;
}

void pesquisaC(NodeC* table, int key, int size) {
    for(int j=0; j<2; j++) {
        int h = j == 0 ? hash(key, size) : hash2(key, size);
        if (table->ocupado[j][h] && table->slot[j][h] == key) {
            printf("%d\t%d\n", j, h);
            return;
        }
    }
    printf("NO\n");
}

void apagaC(NodeC* table, int key, int size) {
    for(int j=0; j<2; j++) {
        int h = j == 0 ? hash(key, size) : hash2(key, size);
        if (table->ocupado[j][h] && table->slot[j][h] == key) {
            table->ocupado[j][h] = 0;
            printf("OK\n");
            return;
        }
    }
    printf("NO\n");
}

void printC(NodeC* table, int size) {
    for(int j=0; j<2; j++) {
        for(int i=0; i<size; i++) {
            if (table->ocupado[j][i]) {
                printf("%d\t%d\t%d\n", j, i, table->slot[j][i]);
            }
        }
    }
}

int openO(char* operacao, int key, int size, NodeO* table, 
                       int (*insereO)(NodeO*, int, int), 
                       void (*apagaO)(NodeO*, int, int), 
                       int (*pesquisaO)(NodeO*, int, int), 
                       void (*printO)(NodeO*, int)) {

    if (strcmp(operacao, "I") == 0) {
        if (insereO(table, key, size)==6)
        return -1;
        else
            return 0;
    } 
    else if (strcmp(operacao, "P") == 0) {
        printO(table, size);
    }
    else if (strcmp(operacao, "D") == 0) {
        apagaO(table, key, size);
    }
    else if (strcmp(operacao, "C") == 0) {
        pesquisaO(table, key, size);
    }
    return 0;
    
}
void link(char* operacao, int key, int size, Node* table, 
                       void (*insereL)(Node*, int, int), 
                       void (*apagaL)(Node*, int, int), 
                       void (*pesquisaL)(Node*, int, int), 
                       void (*printL)(Node*, int)) {

    if (strcmp(operacao, "I") == 0) {
        insereL(table, key, size);
    } 
    else if (strcmp(operacao, "P") == 0) {
        printL(table, size);
    }
    else if (strcmp(operacao, "D") == 0) {
        apagaL(table, key, size);
    }
    else if (strcmp(operacao, "C") == 0) {
        pesquisaL(table, key, size);
    }
    
}

int cuckoo(char* operacao, int key, int size, NodeC* table, 
                       int (*insereC)(NodeC*, int, int), 
                       void (*apagaC)(NodeC*, int, int), 
                       void (*pesquisaC)(NodeC*, int, int), 
                       void (*printC)(NodeC*, int)) {

    if (strcmp(operacao, "I") == 0) {
        if (insereC(table, key, size)==6)
        return -1;
        else
        return 0;
    } 
    else if (strcmp(operacao, "P") == 0) {
        printC(table, size);
    }
    else if (strcmp(operacao, "D") == 0) {
        apagaC(table, key, size);
    }
    else if (strcmp(operacao, "C") == 0) {
        pesquisaC(table, key, size);
    }
    return 0;
    
}
int main() {
    int size;
    char conflito[10];

    if (scanf("%d", &size) != 1 || scanf("%s ", conflito) !=1 ) {
        return 0;
    }
    if (strcmp(conflito, "LINK") != 0 && strcmp(conflito, "OPEN") != 0 && strcmp(conflito, "CUCKOO") != 0) {
        return 0;
    }

    char operacao[10];
    int key;
    int resultado;
    char input[100];

    Node* table = criaHT(size);
    NodeO* tableO = criaO(size);
    NodeC* tableC = criaHTC(size);

    while (fgets(input, sizeof(input), stdin)) {
        resultado = sscanf(input, "%s %d", operacao,&key);
        if(resultado < 1) break;
        if(strcmp(conflito,"LINK")==0){
        link(operacao, key, size, table, insereL, apagaL, pesquisaL, printL);
        }
        else if(strcmp(conflito,"OPEN")==0){
        if (openO(operacao, key, size, tableO, insereO, apagaO, pesquisaO, printO)==-1)
        return 0;
        }
        else if(strcmp(conflito,"CUCKOO")==0){
            if (cuckoo(operacao,key,size,tableC,insereC,apagaC,pesquisaC,printC)==-1)
            return 0;
        }
    else return 0;
}
}
Leave a Comment