Maneira rápida de implementar o dicionário em C

132

Uma das coisas que sinto falta ao escrever programas em C é uma estrutura de dados do dicionário. Qual é a maneira mais conveniente de implementar uma em C? Não estou procurando desempenho, mas facilidade de codificá-lo do zero. Também não quero que seja genérico - algo como string-> int fará. Mas eu quero que ele seja capaz de armazenar um número arbitrário de itens.

Isto é pretendido mais como um exercício. Eu sei que existem bibliotecas de terceiros disponíveis que podem ser usadas. Mas considere por um momento que eles não existem. Em tal situação, qual é a maneira mais rápida de implementar um dicionário que atenda aos requisitos acima.

Rohit
fonte
4
Se você sente falta de fornecê-lo, por que deseja fazê-lo do zero, em vez de usar uma implementação de terceiros?
Karl Knechtel
Sim, essa alternativa sempre existe. Eu coloquei essa questão mais como um exercício.
Rohit
10
Escrever uma hashtable em C é um exercício divertido - todo programador sério de C deve fazer isso pelo menos uma vez.
Lee
Penso que um dicionário é um tipo de dados e não uma estrutura de dados, pois pode ser implementado de várias maneiras - uma lista, uma hashtable, uma árvore, uma árvore de auto-equilíbrio etc. Você está pedindo um dicionário ou uma hashtable ?
Paul Hankin
1
Relacionados: Como representar um Python-like dicionário em C [] (? Stackoverflow.com/questions/3269881/... )
Gaurang Tandon

Respostas:

114

A seção 6.6 da linguagem de programação C apresenta uma estrutura de dados simples de dicionário (hashtable). Eu não acho que uma implementação útil de dicionário possa ser mais simples que isso. Para sua conveniência, reproduzo o código aqui.

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}

char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
    if (p != NULL)
       strcpy(p, s);
    return p;
}

Observe que, se os hashes de duas seqüências colidirem, isso poderá levar a um O(n)tempo de pesquisa. Você pode reduzir a probabilidade de colisões aumentando o valor de HASHSIZE. Para uma discussão completa da estrutura de dados, consulte o livro.

Vijay Mathew
fonte
1
Se for do livro C, gostaria de saber se pode haver uma implementação mais compacta.
Rohit
30
@ Ohh, para um pedaço de código C útil, ele não fica muito mais compacto do que isso. Acho que se pode sempre remover alguns espaços em branco ...
Ryan Calhoun
7
por que está aqui hashval = *s + 31 * hashval;exatamente 31 e nada mais?
アレックス
12
31 é primo. Primes são freqüentemente usados ​​em funções de hash para reduzir a probabilidade de colisões. Tem algo a ver com fatoração inteira (ou seja, você não pode fatorar um primo).
Jnovacho # 4/14
2
@ Overdrivr: Não é necessário neste caso. hashtab é de duração estática. Variáveis ​​não inicializadas com duração estática (ou seja, aquelas declaradas fora das funções e declaradas com a classe estática de armazenamento) são garantidas para iniciar como um zero do tipo correto (ou seja: 0 ou NULL ou 0.0)
carveone
19

A maneira mais rápida seria usar uma implementação já existente, como uthash .

E, se você realmente deseja codificá-lo, os algoritmos de uthashpodem ser examinados e reutilizados. É licenciado pelo BSD, portanto, além do requisito de transmitir o aviso de direitos autorais, você é bastante ilimitado no que pode fazer com ele.

paxdiablo
fonte
8

Para facilitar a implementação, é difícil superar ingenuamente a pesquisa através de uma matriz. Além de algumas verificações de erros, esta é uma implementação completa (não testada).

typedef struct dict_entry_s {
    const char *key;
    int value;
} dict_entry_s;

typedef struct dict_s {
    int len;
    int cap;
    dict_entry_s *entry;
} dict_s, *dict_t;

int dict_find_index(dict_t dict, const char *key) {
    for (int i = 0; i < dict->len; i++) {
        if (!strcmp(dict->entry[i], key)) {
            return i;
        }
    }
    return -1;
}

int dict_find(dict_t dict, const char *key, int def) {
    int idx = dict_find_index(dict, key);
    return idx == -1 ? def : dict->entry[idx].value;
}

void dict_add(dict_t dict, const char *key, int value) {
   int idx = dict_find_index(dict, key);
   if (idx != -1) {
       dict->entry[idx].value = value;
       return;
   }
   if (dict->len == dict->cap) {
       dict->cap *= 2;
       dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s));
   }
   dict->entry[dict->len].key = strdup(key);
   dict->entry[dict->len].value = value;
   dict->len++;
}

dict_t dict_new(void) {
    dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))};
    dict_t d = malloc(sizeof(dict_s));
    *d = proto;
    return d;
}

void dict_free(dict_t dict) {
    for (int i = 0; i < dict->len; i++) {
        free(dict->entry[i].key);
    }
    free(dict->entry);
    free(dict);
}
Paul Hankin
fonte
2
"Para facilitar a implementação": você está exatamente certo: este é o mais fácil. Além disso, ele implementa a solicitação do OP "Eu quero que ele possa armazenar um número arbitrário de itens" - a resposta mais votada não faz isso (a menos que você acredite que escolher uma constante de tempo de compilação satisfaça "arbitrário" ...)
Davidbak
1
Essa pode ser uma abordagem válida, dependendo do caso de uso, mas o OP solicitou explicitamente um dicionário, e esse definitivamente não é um dicionário.
precisa saber é o seguinte
3

Crie uma função hash simples e algumas listas vinculadas de estruturas, dependendo do hash, atribua qual lista vinculada inserir o valor. Use o hash para recuperá-lo também.

Eu fiz uma implementação simples há algum tempo:

...
#define K 16 // coeficiente de encadeamento

dict de estrutura
{
    nome do personagem; / * nome da chave * /
    int val; /* valor */
    struct dict * next; / * campo do link * /
};

typedef struct dict dict;
dict * table [K];
int inicializado = 0;


putval vazio (char *, int);

void init_dict ()
{   
    inicializado = 1;
    int i;  
    para (i = 0; iname = (char *) malloc (strlen (key_name) +1);
    ptr-> val = sval;
    strcpy (ptr-> name, key_name);


    ptr-> next = (estrutura dict *) tabela [hsh];
    tabela [hsh] = ptr;

}


int getval (char * key_name)
{   
    int hsh = hash (nome-chave);   
    dict * ptr;
    para (ptr = tabela [hsh]; ptr! = (dict *) 0;
        ptr = (dict *) ptr-> próximo)
    if (strcmp (ptr-> name, key_name) == 0)
        return ptr-> val;
    retorno -1;
}
abc def foo bar
fonte
1
Você não está perdendo metade do código? onde está "hash ()" e "putval ()"?
swdev
3

GLib e gnulib

Essas são as suas melhores apostas prováveis ​​se você não tiver requisitos mais específicos, pois são amplamente disponíveis, portáteis e provavelmente eficientes.

Consulte também: Existem bibliotecas C de código aberto com estruturas de dados comuns?

Ciro Santilli adicionou uma nova foto
fonte
2

Aqui está uma implementação rápida, usei-a para obter uma 'Matrix' (sruct) de uma string. você pode ter uma matriz maior e alterar seus valores em execução também:

typedef struct  { int** lines; int isDefined; }mat;
mat matA, matB, matC, matD, matE, matF;

/* an auxilary struct to be used in a dictionary */
typedef struct  { char* str; mat *matrix; }stringToMat;

/* creating a 'dictionary' for a mat name to its mat. lower case only! */
stringToMat matCases [] =
{
    { "mat_a", &matA },
    { "mat_b", &matB },
    { "mat_c", &matC },
    { "mat_d", &matD },
    { "mat_e", &matE },
    { "mat_f", &matF },
};

mat* getMat(char * str)
{
    stringToMat* pCase;
    mat * selected = NULL;
    if (str != NULL)
    {
        /* runing on the dictionary to get the mat selected */
        for(pCase = matCases; pCase != matCases + sizeof(matCases) / sizeof(matCases[0]); pCase++ )
        {
            if(!strcmp( pCase->str, str))
                selected = (pCase->matrix);
        }
        if (selected == NULL)
            printf("%s is not a valid matrix name\n", str);
    }
    else
        printf("expected matrix name, got NULL\n");
    return selected;
}
dagoltz
fonte
2

Estou surpreso que ninguém tenha mencionado o conjunto de bibliotecas hsearch / hcreate que, embora não esteja disponível no Windows, é mandatado pelo POSIX e, portanto, disponível nos sistemas Linux / GNU.

O link possui um exemplo básico simples e completo que explica muito bem seu uso.

Ele ainda possui uma variante segura de threads, é fácil de usar e tem um ótimo desempenho.

fkl
fonte
2
Vale notar que as pessoas aqui dizem que é tipo de inútil, embora eu não tentei me: stackoverflow.com/a/6118591/895245
Ciro Santilli郝海东冠状病六四事件法轮功
1
Justo, no entanto, eu tentei a versão hcreate_r (para várias tabelas de hash) em pelo menos um aplicativo que foi executado por um tempo razoavelmente longo o suficiente para considerá-lo no mundo real. Concordou que é uma extensão GNU, mas também é o caso de muitas outras bibliotecas. Embora eu ainda diria que você ainda pode ser capaz de usá-lo para um par valor de chave grande a ser operado em algum aplicativo do mundo real
FKL
0

Uma hashtable é a implementação tradicional de um simples "Dicionário". Se você não se importa com velocidade ou tamanho, basta pesquisar no Google . Existem muitas implementações disponíveis gratuitamente.

aqui está o primeiro que eu vi - de relance, parece bom para mim. (é bastante básico. Se você realmente deseja que ele mantenha uma quantidade ilimitada de dados, precisará adicionar alguma lógica para "realocar" a memória da tabela à medida que ela cresce.)

boa sorte!

Lee
fonte
-1

Hashing é a chave. Eu acho que usar tabela de pesquisa e chave de hash para isso. Você pode encontrar muitas funções de hash online.

ashmish2
fonte
-1

O método mais rápido seria usar a árvore binária. Seu pior caso também é apenas O (logn).

programador
fonte
15
Isto está incorreto. A pesquisa de pior caso para uma árvore binária é O (n) (caso degenerado devido a uma ordem de inserção incorreta, resultando em uma lista de links, basicamente) quando está desequilibrada.
Randy Howard