Estrutura, C (gcc)

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