Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Estrutura
#define _GNU_SOURCE 1 //necessário para não gerar warning devido a funcao strdup #include <stdio.h> #include <stdlib.h> #include <string.h> // Definições de Constantes #define TAMANHO (1024) #define FATOR_CRESCIMENTO (2) #define FATOR_CARGA_MAX (1) #define MULTIPLICADOR (97) // Estrutura de Dados typedef struct item { struct item *proximo; char *chave; char *valor; } Item; typedef struct dicionario { int tamanho; /* tamanho da tabela */ int quantidade; /* quantidade de itens armazenados */ Item **tabela; } Dicionario; // Declaração das Funções // Código de inicialização, utilizado na criação e aumento Dicionario* criar(int tamanho); // Cria um novo dicionário Dicionario* criar_agenda(void); // Destroi o dicionário void destruir(Dicionario *d); // Calcula o hash com base em uma string static unsigned long funcao_hash(const char *s); // Expande o dicionário static void expandir(Dicionario *d); // Insere um dado item no dicionário com base em sua chave void inserir(Dicionario *d, const char *chave, const char *valor); // Retorna o valor associado mais rescente, ou 0 (zero) se não encontrado. const char* busca(Dicionario *d, const char *chave); // Remove o valor mais rescente associado, ou se não localizado não há efeito void remover(Dicionario *d, const char *chave); // Main int main() { Dicionario *d; d = criar_agenda(); inserir(d, "joao", "Joao Carlos"); puts(busca(d, "joao")); inserir(d, "joao", "Joao Manoel"); puts(busca(d, "joao")); remover(d, "joao"); puts(busca(d, "joao")); remover(d, "joao"); remover(d, "joao"); destruir(d); return 0; } Dicionario* criar(int tamanho) { Dicionario *d; int i; d = (Dicionario *) malloc(sizeof(Dicionario)); d->tamanho = tamanho; d->quantidade = 0; d->tabela = malloc(sizeof(Item *) * tamanho); for(i = 0; i < d->tamanho; i++) d->tabela[i] = 0; return d; } Dicionario* criar_agenda(void) { return criar(TAMANHO); } void destruir(Dicionario *d) { int i; Item *item; Item *proximo; for(i = 0; i < d->tamanho; i++) { for(item = d->tabela[i]; item != 0; item = proximo) { proximo = item->proximo; free(item->chave); free(item->valor); free(item); } } free(d->tabela); free(d); } static unsigned long funcao_hash(const char *s) { unsigned const char *us; unsigned long hash; hash = 0; // apenas um cálculo de hash que considera cada letra da string for(us = (unsigned const char *) s; *us; us++) { hash = hash * MULTIPLICADOR + *us; } return hash; } static void expandir(Dicionario *d) { Dicionario *d2; /* novo dicionário */ Dicionario tmp; /* estrutura temporária para transferência */ int i; Item *item; // Cria o dicionario com espaço extra prevendo a expansão d2 = criar(d->tamanho * FATOR_CRESCIMENTO); // PREENCHER!! // Uma vez tendo sido expandido, a estrutura antiga é eliminada destruir(d2); } void inserir(Dicionario *d, const char *chave, const char *valor) { Item *item; unsigned long hash; item = (Item *) malloc(sizeof(*item)); item->chave = strdup(chave); item->valor = strdup(valor); hash = funcao_hash(chave) % d->tamanho; item->proximo = d->tabela[hash]; d->tabela[hash] = item; d->quantidade++; // Aumenta a tabela se o fator de carga já ultrapassou. if(d->quantidade >= d->tamanho * FATOR_CARGA_MAX) { expandir(d); } } const char* busca(Dicionario *d, const char *chave) { Item *item; for(item = d->tabela[funcao_hash(chave) % d->tamanho]; item != 0; item = item->proximo) { if(!strcmp(item->chave, chave)) { return item->valor; } } return 0; } void remover(Dicionario *d, const char *chave) { Item **anterior; // O item que deve ser alterado se houver remoção Item *item; // O item a ser removido for(anterior = &(d->tabela[funcao_hash(chave) % d->tamanho]); *anterior != 0; anterior = &((*anterior)->proximo)) { if(!strcmp((*anterior)->chave, chave)) { item = *anterior; *anterior = item->proximo; free(item->chave); free(item->valor); free(item); break; } } }
run
|
edit
|
history
|
help
1
-Wall
EL PANGRAMA PERFECTO
challoc
Tern operators
18BCE2182 ASSESS_2 Q4
18BCE2182 MIDTERM PART-B CRITICAL
A_141117_Primo01
Hello world
test1.c
MyWall1