Быстрый способ реализовать словарь в C

Question

Одна из вещей, которую мне не хватает при написании программ на C, - это структура данных словаря.Какой самый удобный способ реализовать один в C?Я не ищу производительность, но легко кодировать ее с нуля.Я тоже не хочу, чтобы он был универсальным - подойдет что-то вроде string-> int.Но я хочу, чтобы он мог хранить произвольное количество предметов.

Это предназначено скорее как упражнение.Я знаю, что есть сторонние библиотеки, которые можно использовать.Но задумайтесь на мгновение, что их не существует.В такой ситуации, какой самый быстрый способ вы можете реализовать словарь, удовлетворяющий вышеуказанным требованиям.

Answer 1

Раздел 6.6 из Язык программирования C представляет простую словарную (хеш-таблицу) структуру данных.Я не думаю, что полезная реализация словаря может быть проще, чем эта.Для вашего удобства я воспроизведу код здесь.

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;
}

Обратите внимание, что если сталкиваются хэши двух строк, это может привести к O(n) времени поискаВы можете уменьшить вероятность столкновений, увеличив значение HASHSIZE.Для полного обсуждения структуры данных, пожалуйста, обратитесь к книге.

Answer 2

Самый быстрый способ - использовать уже существующую реализацию, например uthash .

И, если вы действительно хотитезакодируйте его самостоятельно, алгоритмы uthash можно изучить и использовать повторно.Он имеет лицензию BSD, поэтому, помимо требования о передаче уведомления об авторских правах, вы практически не ограничены в своих возможностях.

Answer 3

Для простоты реализации трудно превзойти наивный поиск в массиве. Помимо некоторой проверки ошибок, это полная реализация (непроверенная).

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);
}

Answer 4

Создайте простую хеш-функцию и несколько связанных списков структур, в зависимости от хеша, назначьте в какой связанный список вставить значение.Используйте хеш для его извлечения.

Некоторое время назад я сделал простую реализацию:

...
#define K 16 // chaining coefficient

struct dict
{
    char *name; /* name of key */
    int val;   /*  value */
    struct dict *next; /* link field */
};

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


void  putval ( char *,int);

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


    ptr->next = (struct dict *)table[hsh];
    table[hsh] = ptr;

}


int getval ( char *key_name )
{   
    int hsh = hash(key_name);   
    dict *ptr;
    for (ptr = table[hsh]; ptr != (dict *) 0;
        ptr = (dict *)ptr->next)
    if (strcmp (ptr->name,key_name) == 0)
        return ptr->val;
    return -1;
}

Answer 5

Я удивлен, что никто не упомянул hsearch / hcreate набор библиотек, который хотя и недоступен в Windows, но обязателен для POSIX и поэтому доступен в системах Linux / GNU.

Ссылка содержит простой и полный базовый пример, который очень хорошо объясняет ее использование.

Он даже имеет поточно-ориентированный вариант, прост в использовании и очень производительный.

Answer 6

вот быстрая реализация, я использовал ее, чтобы получить 'Matrix' (sruct) из строки.Вы можете иметь больший массив и изменять его значения на ходу:

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;
}

Answer 7

GLib и gnulib

Это ваши лучшие ставки, если у вас нет особых требований, поскольку они широко доступны, портативны и, вероятно, эффективны.

• GLib: https://developer.gnome.org/glib/ по проекту GNOME. Несколько контейнеров, документированных по адресу: https://developer.gnome.org/glib/stable/glib-data-types.html, включая «Хеш-таблицы» и «Сбалансированные двоичные деревья». Лицензия: LGPL

• gnulib: https://www.gnu.org/software/gnulib/ по проекту GNU. Вы должны скопировать вставить исходный код в ваш код. Несколько контейнеров, задокументированных по адресу: https://www.gnu.org/software/gnulib/MODULES.html#ansic_ext_container, включая «rbtree-list», «connectedhash-list» и «rbtreehash-list». Лицензия GPL.

См. Также: Существуют ли библиотеки C с открытым исходным кодом с общими структурами данных?

Answer 8

Хеш-таблица - это традиционная реализация простого «Словаря». Если вам не важны скорость или размер, просто Google для этого . Есть много свободно доступных реализаций.

вот первый, который я увидел - на первый взгляд, мне кажется, это нормально. (Это довольно просто. Если вы действительно хотите, чтобы он содержал неограниченное количество данных, вам нужно будет добавить некоторую логику для «перераспределения» памяти таблицы по мере ее роста.)

удачи!

Answer 9

Самый быстрый способ - использовать двоичное дерево.Его худший случай также только O (logn).

Answer 10

Хеширование - это ключ. Я думаю, использовать таблицу поиска и ключ хеширования для этого. Вы можете найти много функций хеширования онлайн.