HashTable и векторные структуры данных в C99 - PullRequest
Новая
       20

HashTable и векторные структуры данных в C99

1 голос
/ 28 октября 2011

Я хочу создать хеш-таблицу, которая опирается на независимую векторную структуру данных в C99. Я могу сделать это в C ++ с помощью ОО, но я не уверен, как подойти к этому, используя структуры и объединения.

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

Ответы [ 2 ]

1 голос
/ 28 октября 2011

В следующей книге, вероятно, лучшее описание как связанных списков, так и хеш-таблицы в C с использованием структур:

http://en.wikipedia.org/wiki/The_C_Programming_Language_(book)

Также реализован простой алгоритм хеширования.

Другим простым, но равномерно распределенным алгоритмом хеширования является алгоритм cdb, определенный здесь:

http://cr.yp.to/cdb/cdb.txt

1 голос
/ 28 октября 2011

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

typedef struct {
    size_t capacity, nelems;
    void **contents;
} Vector;

enum { INITIAL_CAPACITY = 256 };

Vector *make_vector()
{
    Vector *v = malloc(sizeof(Vector));
    if (v == NULL)
        return NULL;
    v->capacity = INITIAL_CAPACITY;
    v->contents = malloc(sizeof(void *) * v->capacity);
    if (v->contents == NULL) {
        free(v);
        return NULL;
    }
    v->nelems = 0;
    return v;
}

// exercise for the reader
int vector_append(Vector *, void *);
void *vector_at(Vector const *);

Имейте в виду, что общая хеш-функция будет иметь прототип size_t hash(void const *, size_t), т. Е. Вам нужно передать размер.

(Примечание: не OOP-функции C ++, которые вы собираетесь упустить; это шаблоны, безопасность типов, которые они покупают, и синтаксический сахар, такой как перегрузка операторов. Взгляните на OpenBSD ohash библиотека для большего количества примеров.)

...