LINUX.ORG.RU

Hash table, nodes, linked lists

 ,


0

1

Добрый день!

Изучаю hash tables и linked lists (совсем на начальной стадии изучения С и вообще программирования). Пожалуйста, помогите разобраться

в предложенном на одном из сайтов примере (вот сайт: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx).

Пожалуйста, посмотрите код и мои вопросы ниже:

struct jsw_node
{
    void *key;
    struct jsw_node *next;
};

struct hash_table
{
    struct jsw_node **table;
    size_t size;
};

int jsw_find(struct hash_table *table, void *key, size_t size)
{
    /* Get an index for the key */
    size_t h = hash(key, size) % table->size;

    if (table->table[h] != EMPTY)
    {
        /* Find the matching key in the chain, if any */
        struct jsw_node *it = table->table[h];

        while (it != NULL)
        {
            if (compare(key, it->key) == 0)
            {
                return 1;
            }

            it = it->next;
        }
    }

    return 0;
} 

struct jsw_node
{
    void *key;
    struct jsw_node *next;
};

struct hash_table
{
    struct jsw_node **table;
    size_t size;
};

Пишу смесь русского с английским, потому что плохо разбираюсь в русских эквивалентах.

1) struct jsw_node

Декларируется структура jsw_node, которая включает некое значение

key. Данный ключ имеет тип void, потому что предполагается, что

key может быть любого типа - integer, character, string.

Почему в данном случае используется указатель, а не значение key,

то есть почему void *key?

Второй элемент структуры jsw_node - указатель на следующую такую же

структуру (это понятно).

2) struct hash_table

Первый элемент данной структуры указатель на указатель на структуру

jsw_node. Второй элемент - размер данной структуры, то есть насколько

я понимаю количество table.

Что означает и почему используется pointer to pointer, то есть

struct jsw_node **table, как данный эелемент соотносится с предыдущей

структурой?

3) Функция jsw_find имеет один из параметров указатель на структуру

hash_table и данный параметр называется table. В базовой программе,

которая есть в начале страницы, на которую я дала ссылку, есть декларация

array table[].

 if (table->table[h] != EMPTY) 

Я не поняла вот эту часть table->table[h]: в структуре hash_table

нет ни одного элемента array, но есть двойной указатель на struct jsw_node.

В struct jsw_node также нет ни одной array. Как тогда table

указывает на элемент table[h]?

Большое спасибо за помощь!


то есть почему void *key?

Вероятно потому, что в key могут лежать разные типы данных, и не факт что сводимые к 1. Ну вот char, int, string (который, раз уж сишка - то так или иначе юзает char*). Как ты сведешь к чему-то из других типов string?

alex4321 ()

шли бы вы в девелопмент с такими вопросами :)

vel ★★★★★ ()

Вы неправильно начали. Начните с чего-нибудь попроще. Вместо того чтобы читать сложные программы с указателями попробуйте написать программу, и тогда через пару дней вы поймёте зачем нужны указатели и указатели на указатели. Возьмите например эту книгу: http://www.stroustrup.com/programming.html

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.