Untitled
unknown
plain_text
a year ago
9.7 kB
7
Indexable
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <signal.h> #include <math.h> #define MAX 200 volatile sig_atomic_t sinal = 1; void executar_sinal () { sinal = 0; } enum Conflict_Resolutions{ OPEN, LINK, CUCKOO, NOTHING }; typedef struct lligada{ int valor; struct lligada *prox; } *Lista; int hash_function1 (int elemento, int nr_slots){ return (elemento % nr_slots); } int hash_function2 (int elemento, int nr_slots){ // NÃO ESQUECER DE COLOCAR -lm NO TERMINAL return ((int) floor(elemento / nr_slots) % nr_slots); } /* --------------------------------- LINEAR PROBING --------------------------------- */ int foi_inserido (char tabela[][MAX], int nr_slots, char elemento[], int chave, char pedido){ int posicao_livre = -1; // armazena o índice do primeiro slot vazio encontrado int posicao_elemento = -1; int esta_inserido = 0; /* if ((tabela[chave][0] == '\0' || tabela[chave][0] == 'D') && pedido == 'I'){ strncpy(tabela[chave], elemento, MAX); printf("%d -> %s\nOK\n", chave, tabela[chave]); return 1; } */ for (int i = chave, n = 0; n < nr_slots && !esta_inserido; n++){ if (((strlen(tabela[i]) == 0) || tabela[i][0] == 'D') && posicao_livre == -1 && pedido == 'I'){ posicao_livre = i; } if (pedido == 'C' && tabela[i][0] == 'D' && posicao_livre == -1){ posicao_livre = i; } if (strcmp(tabela[i], elemento) == 0){ esta_inserido = 1; posicao_elemento = i; if (pedido == 'D'){ memset(tabela[i], '\0', sizeof(tabela[i])); tabela[i][0] = 'D'; return 1; } if (pedido == 'C'){ if (posicao_livre != -1){ memcpy(tabela[posicao_livre], tabela[i], strlen(tabela[i]) + 1); memset(tabela[i], '\0', sizeof(tabela[i])); tabela[i][0] = 'D'; return posicao_livre; } return i; } } if ((i + 1) == nr_slots){ i = 0; } else{ i++; } } if (pedido == 'C' && !esta_inserido) return -1; if (pedido == 'D' && !esta_inserido) return 0; if (posicao_livre != -1 && !esta_inserido){ memcpy(tabela[posicao_livre], elemento, strlen(elemento) + 1); printf("%d -> %s\nOK\n", posicao_livre, tabela[posicao_livre]); return 1; } if (posicao_livre != -1 && esta_inserido && posicao_elemento > -1){ memcpy(tabela[posicao_livre], elemento, strlen(elemento) + 1); memset(tabela[posicao_elemento], '\0', sizeof(tabela[posicao_elemento])); printf("%s EXISTS\n", elemento); return 1; } if (posicao_livre == -1 && esta_inserido){ printf("%s EXISTS\n", elemento); return 1; } return esta_inserido; } void inserir_elemento (char tabela[][MAX], int nr_slots, char elemento[], enum Conflict_Resolutions resolucao, int chave){ if (resolucao == OPEN){ if (!foi_inserido(tabela, nr_slots, elemento, chave, 'I')) printf("GIVING UP!\n"); } } void mostrar_tabela (char tabela[][MAX], int nr_slots){ for(int i = 0; i < nr_slots; i++){ if (strlen(tabela[i]) > 0){ printf("%d\t%s", i, tabela[i]); putchar('\n'); } } } void linear_probing (char tabela[][MAX], int nr_slots){ signal(SIGINT, executar_sinal); while(sinal){ char pedido; // pedir para inserir um elemento, remover um elemento, verificar um elemento ou imprimir a tabela (omitindo slots vazios) char elemento[MAX] = ""; // pode ter o caracter 'D' char linha[200]; if (fgets(linha, MAX, stdin) == NULL) exit(EXIT_FAILURE); sscanf(linha, "%c", &pedido); if (pedido == 'P') mostrar_tabela(tabela, nr_slots); else{ sscanf(linha, "%c %s", &pedido, elemento); int valor = atoi(elemento); // converte a string elemento num inteiro int chave = hash_function1(valor, nr_slots); if (pedido == 'I') inserir_elemento(tabela, nr_slots, elemento, OPEN, chave); else if (pedido == 'D'){ if (foi_inserido(tabela, nr_slots, elemento, chave, 'D')) printf("OK\n"); else printf("NO\n"); } else if (pedido == 'C'){ int sucesso = foi_inserido(tabela, nr_slots, elemento, chave, 'C'); if (sucesso != -1) printf("%d\n", sucesso); else printf("NO\n"); } } } } /* --------------------------------- LINKED LISTS --------------------------------- */ int percorre_lista (Lista lista_ligada, int elemento){ int esta_na_lista = 0; if (lista_ligada == NULL) return 0; while (lista_ligada != NULL){ if (lista_ligada->valor == elemento){ esta_na_lista = 1; break; } lista_ligada = lista_ligada->prox; } return esta_na_lista; } int remove_lista (Lista *array_listas, Lista cabeca, int elemento){ if (*array_listas == NULL) return 0; if ((*array_listas)->valor == elemento){ Lista cabeca_atual = *array_listas; *array_listas = (*array_listas)->prox; free(cabeca_atual); return 1; } while (cabeca->prox != NULL){ if ((cabeca->prox)->valor == elemento){ Lista a_remover = cabeca->prox; cabeca->prox = (cabeca->prox)->prox; free(a_remover); return 1; } cabeca = cabeca->prox; } return 0; } int inserir_lista (Lista *array_listas, Lista cabeca, int elemento){ int esta_inserido = 0; if (cabeca == NULL){ Lista novo_elemento = malloc(sizeof(struct lligada)); novo_elemento->valor = elemento; novo_elemento->prox = NULL; *array_listas = novo_elemento; return 1; } esta_inserido = percorre_lista(cabeca, elemento); if (!esta_inserido){ Lista novo_elemento = malloc(sizeof(struct lligada)); novo_elemento->valor = elemento; novo_elemento->prox = cabeca; *array_listas = novo_elemento; return 1; } else return 0; } void mostra_listas (Lista array_listas, int indice){ if (array_listas != NULL) printf("%d ", indice); else return; while (array_listas != NULL){ printf("%d", array_listas->valor); if (array_listas->prox == NULL) putchar('\n'); else putchar(' '); array_listas = array_listas->prox; } } void linked_lists (Lista *array_listas[], int nr_slots){ signal(SIGINT, executar_sinal); while (sinal){ char pedido; int valor; char linha[MAX]; if (fgets(linha, MAX, stdin) == NULL) exit(EXIT_FAILURE); sscanf(linha, "%c", &pedido); if(pedido == 'P'){ for (int i = 0; i < nr_slots; i++){ mostra_listas(*array_listas[i], i); } } else{ sscanf(linha, "%c %d", &pedido, &valor); int chave = hash_function1(valor, nr_slots); if (pedido == 'I'){ int foi_inserido = 0; foi_inserido = inserir_lista(array_listas[chave], *array_listas[chave], valor); if (foi_inserido) printf("%d -> %d\nOK\n", chave, valor); else printf("%d EXISTS\n", valor); } else if (pedido == 'C'){ if (percorre_lista(*array_listas[chave], valor)) printf("%d\n", chave); else printf("NO\n"); } else if (pedido == 'D'){ if (remove_lista(array_listas[chave], *array_listas[chave], valor)) printf("OK\n"); else printf("NO\n"); } } } for (int i = 0; i < nr_slots; i++){ for (; *array_listas[i] != NULL;){ Lista proxima = (*array_listas[i])->prox; free(*array_listas[i]); // 'free' à cabeça da lista *array_listas[i] = proxima; } } } /* -------------------------------------- MAIN -------------------------------------- */ int main(){ int nr_slots; char *opcao = malloc(10 * sizeof(char)); enum Conflict_Resolutions resolucao; if (scanf("%d", &nr_slots) != 1){ exit(EXIT_FAILURE); } if (scanf("%s", opcao) != 1){ exit(EXIT_FAILURE); } char tabela_open[nr_slots][MAX]; Lista *array_listas[nr_slots]; Lista listas_cabecas[nr_slots]; if (strcmp(opcao, "OPEN") == 0){ resolucao = OPEN; } else if (strcmp(opcao, "LINK") == 0){ resolucao = LINK; } else if (strcmp(opcao, "CUCKOO") == 0){ resolucao = CUCKOO; } else{ resolucao = NOTHING; } free(opcao); switch(resolucao){ case OPEN: for (int i = 0; i < nr_slots; i++){ tabela_open[i][0] = '\0'; } linear_probing(tabela_open, nr_slots); break; case LINK: for (int i = 0; i < nr_slots; i++){ listas_cabecas[i] = NULL; array_listas[i] = &listas_cabecas[i]; } linked_lists(array_listas, nr_slots); break; case CUCKOO: printf("\nCUCKOO\n"); break; default: break; } return 0; }
Editor is loading...
Leave a Comment