Created
December 31, 2015 15:28
-
-
Save guilhermeoki/06123b98a1cb7cf8bce9 to your computer and use it in GitHub Desktop.
LinkedHashMap
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * File: main.c | |
| * Author: Guilherme Oki | |
| */ | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| /* | |
| * fator de carga = #chaves / #buckets f = m/n | |
| */ | |
| int temp = 0; | |
| typedef struct aluno { | |
| char nome[100]; | |
| float CR; | |
| int DRE; | |
| }ALUNO; | |
| typedef struct node { | |
| ALUNO * aluno; | |
| int chave; | |
| struct node* prox; | |
| struct node* prox_linked; | |
| struct node* anterior_linked; | |
| }LINKEDHASHMAP_NODE; | |
| typedef struct linked_list { | |
| LINKEDHASHMAP_NODE*primeiro; | |
| LINKEDHASHMAP_NODE*fim; | |
| int node_count; | |
| }LINKED_LIST; | |
| typedef struct linkedhashmap { | |
| //LINKEDHASHMAP_NODE ** buckets; | |
| LINKED_LIST * buckets; | |
| LINKEDHASHMAP_NODE*inicio; | |
| LINKEDHASHMAP_NODE*fim; | |
| int buckets_size; //m | |
| int elements_count; //n | |
| float load_factor; | |
| }LINKEDHASHMAP; | |
| int hash(int chave,LINKEDHASHMAP *lhm){ | |
| return chave % lhm->buckets_size; | |
| } | |
| ALUNO *get(LINKEDHASHMAP* lhm,int key){ | |
| int bucket_index = hash(key,lhm); | |
| LINKED_LIST lista = lhm->buckets[bucket_index]; | |
| LINKEDHASHMAP_NODE * No = lista.primeiro; | |
| //vou varrendo o no | |
| while(No != NULL) { | |
| if (No->chave == key){ | |
| return No->aluno; | |
| } | |
| No = No->prox; | |
| } | |
| return NULL; | |
| } | |
| LINKEDHASHMAP * inicializa_hash(int length,float load_factor) { | |
| LINKED_LIST *buckets; | |
| LINKEDHASHMAP *hashmap; | |
| LINKEDHASHMAP_NODE *no_proximo; | |
| LINKEDHASHMAP_NODE *no_anterior; | |
| int m = length/load_factor; | |
| int i; | |
| no_proximo = (LINKEDHASHMAP_NODE*)malloc(sizeof(LINKEDHASHMAP_NODE)); | |
| no_anterior = (LINKEDHASHMAP_NODE*)malloc(sizeof(LINKEDHASHMAP_NODE)); | |
| hashmap = (LINKEDHASHMAP*)malloc(sizeof(LINKEDHASHMAP)); | |
| buckets = (LINKED_LIST*)malloc(m*sizeof(LINKED_LIST)); | |
| for (i=0;i<m;i++){ | |
| buckets[i].primeiro = NULL; | |
| buckets[i].fim = NULL; | |
| buckets[i].node_count = 0; | |
| } | |
| hashmap->buckets = buckets; | |
| hashmap->load_factor = load_factor; | |
| hashmap->buckets_size = m; | |
| hashmap->elements_count = 0; | |
| hashmap->inicio = hashmap->fim = NULL; | |
| return hashmap; | |
| } | |
| void insert_linked_list(int key,LINKEDHASHMAP *lhm,ALUNO *aluno,LINKEDHASHMAP_NODE *NovoNo) { | |
| int bucket_index = hash(key,lhm); | |
| LINKED_LIST lista = lhm->buckets[bucket_index]; | |
| LINKEDHASHMAP_NODE *No = lista.primeiro; | |
| if (No==NULL){ | |
| lista.primeiro = NovoNo; | |
| lista.fim = NovoNo; | |
| lista.node_count++; | |
| temp++; | |
| lhm->buckets[bucket_index] = lista; | |
| return; | |
| } | |
| else { | |
| while(1){ | |
| if (No->chave == key && No->prox == NULL){ | |
| No->prox = NovoNo; | |
| lista.fim = NovoNo; | |
| lista.node_count++; | |
| lhm->buckets[bucket_index] = lista; | |
| return; | |
| } | |
| else { | |
| return; //tratar colisão | |
| } | |
| No = No->prox; | |
| } | |
| } | |
| } | |
| void insert_linked_hash(int key,LINKEDHASHMAP*lhm,ALUNO *aluno,LINKEDHASHMAP_NODE *NovoNo){ | |
| int bucket_index = hash(key,lhm); | |
| LINKED_LIST lista = lhm->buckets[bucket_index]; | |
| LINKEDHASHMAP_NODE *No = lista.primeiro; | |
| if(lhm->elements_count == 0){ | |
| lhm->inicio = lhm->fim = NovoNo; | |
| } | |
| else if( lhm->elements_count < lhm->buckets_size ) { | |
| lhm->inicio->anterior_linked = NovoNo; | |
| NovoNo->prox_linked = lhm->inicio; | |
| lhm->inicio = NovoNo; | |
| } | |
| //hash cheia, esvazia um bucket | |
| else if (lhm->elements_count >= lhm->buckets_size) { | |
| int bucket_index_removed = hash(lhm->fim->chave,lhm); | |
| LINKED_LIST list; | |
| lhm->buckets[bucket_index_removed] = list; | |
| lhm->fim->anterior_linked->prox_linked = NULL; | |
| free(lhm->fim); | |
| lhm->fim = lhm->fim->anterior_linked; | |
| lhm->inicio->anterior_linked = NovoNo; | |
| NovoNo->prox_linked = lhm->inicio; | |
| lhm->inicio = NovoNo; | |
| temp--; //lhm->element_count-- | |
| } | |
| } | |
| void insert(int key,LINKEDHASHMAP* lhm,ALUNO *aluno){ | |
| LINKEDHASHMAP_NODE *NovoNo = (LINKEDHASHMAP_NODE*)malloc(sizeof(LINKEDHASHMAP_NODE)); | |
| NovoNo->chave = key; | |
| NovoNo->aluno = aluno; | |
| insert_linked_list(key,lhm,aluno,NovoNo); | |
| insert_linked_hash(key,lhm,aluno,NovoNo); | |
| lhm->elements_count = temp; | |
| } | |
| ALUNO *create_aluno(char* nome,float CR, int dre){ | |
| ALUNO *aluno; | |
| aluno = (ALUNO*)malloc(sizeof(ALUNO)); | |
| strcpy(aluno->nome,nome); | |
| aluno->DRE = dre; | |
| aluno->CR = CR; | |
| return aluno; | |
| } | |
| void print_linkedhashmap(LINKEDHASHMAP *lhm){ | |
| LINKEDHASHMAP_NODE *Node = lhm->inicio; | |
| while(1){ | |
| if(Node!=NULL){ | |
| printf("%d %s\n",hash(Node->chave,lhm) , Node->aluno->nome); | |
| } | |
| else if (Node==NULL){ | |
| return; | |
| } | |
| Node = Node->prox_linked; | |
| } | |
| } | |
| int main(int argc, char** argv) { | |
| int key = 1; | |
| int key2 = 2; | |
| int key3 = 3; | |
| int key4 = 4; | |
| int key5 = 5; | |
| int key6 = 6; | |
| LINKEDHASHMAP *lhm = inicializa_hash(4,1); | |
| ALUNO *aluno1 = create_aluno("Fulano",6.7,111333444); | |
| ALUNO *aluno2 = create_aluno("Ciclano",6.7,111333444); | |
| ALUNO *aluno3 = create_aluno("Beltrano",6.7,111333444); | |
| ALUNO *aluno4 = create_aluno("Ultrano",6.7,111333444); | |
| ALUNO *aluno5 = create_aluno("Raltrano",6.7,111333444); | |
| ALUNO *aluno6 = create_aluno("Geltrano",6.7,111333444); | |
| insert(key,lhm,aluno1); | |
| insert(key2,lhm,aluno2); | |
| insert(key3,lhm,aluno3); | |
| insert(key4,lhm,aluno4); | |
| insert(key5,lhm,aluno5); | |
| insert(key2,lhm,aluno6); | |
| ALUNO *alunoget2 = get(lhm,key2); | |
| print_linkedhashmap(lhm); | |
| return (EXIT_SUCCESS); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment