Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Для новичков > Хеш таблица


Автор: vovamakr 24.11.2015, 12:41
Нужна помощь в реализации хеш таблице
Я  хочу вывести на екран свою хеш таблицу
Код

void Print(const HashTable* hashTable)
{
    for (HashTable::BucketNode* listNode = hashTable->buckets; listNode != nullptr; listNode = listNode->nextNode) // тут выдает ошибку.  
        printf("%d\n", listNode->value);
    printf("\n");
}

Мой хедер файл:
Код

#ifndef __HASHTABLE_H__
#define __HASHTABLE_H__

struct String;

struct HashTable
{
    struct BucketNode
    {
        String* key;
        int value;
        BucketNode* nextNode;
    };
    BucketNode** buckets;
    unsigned maxNumBuckets;
    unsigned numElements;
};

(есть еще и  другии функции)
const int* Get(const HashTable* hashTable, const char* key);
void Remove(HashTable* hashTable, const char* key);
void Print(const HashTable* hashTable);

#endif


Добавлено @ 12:51
Тоже самое и в функциях Get(), Remove();
Код

const int* Get(const HashTable* hashTable, const char* key)
{
    for (HashTable::BucketNode* listNode = hashTable->buckets; listNode != nullptr; listNode = listNode->nextNode)
    {
        if (strcmp(listNode->key->str, key) == 0)
            return listNode;
    }
    return nullptr;
}
void Remove(HashTable* hashTable, const char* key)
{
    HashTable::BucketNode* temp = hashTable->buckets;
    hashTable->buckets = temp->nextNode;
    free(temp);
}

Автор: vovamakr 24.11.2015, 13:06
Print переделал: 
Код

void Print(const HashTable* hashTable)
{
    for (int bucketIndex = 0; bucketIndex < hashTable->maxNumBuckets; ++bucketIndex)
    {
        HashTable::BucketNode*& headNode = hashTable->buckets[bucketIndex];
        for (HashTable::BucketNode* listNode = headNode; listNode != nullptr; listNode = listNode->nextNode)
            printf("%d\n", listNode->value);
    }
}

а от Remove не правильно работает(
Код

void Remove(HashTable* hashTable, const char* key)
{
    for (int bucketIndex = 0; bucketIndex < hashTable->maxNumBuckets; ++bucketIndex)
    {
        HashTable::BucketNode*& headNode = hashTable->buckets[bucketIndex];
        for (HashTable::BucketNode* listNode = headNode; listNode != nullptr; listNode = listNode->nextNode)
        {
            HashTable::BucketNode* temp = listNode;
            if (strcmp(listNode->key->str, key) == 0)
            {
                listNode = temp->nextNode;
                free(temp);
                return;
            }
        }
    }
} 

Автор: Sajtran 25.11.2015, 11:42
в чём проблема то?
и чем из STL реализация не устраивает?

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Khesh-tablitsa-id565430edae2015220a8b4567#findElement_E7045_56557481ae20158e1144f8a7_0

Автор: volatile 25.11.2015, 12:36
Цитата(vovamakr @  24.11.2015,  12:41 Найти цитируемый пост)
  for (HashTable::BucketNode* listNode = hashTable->buckets; listNode != nullptr; listNode = listNode->nextNode)
    {
        if (strcmp(listNode->key->str, key) == 0)

зачем вообще хеш, если тупо искать линейным поиском?

Автор: math64 25.11.2015, 14:10
Я уже объяснял ТС, в другой темее, как должна реализовываться хеш-таблица:
http://forum.vingrad.ru/index.php?showtopic=385508&view=findpost&p=2649741
хеш-код можно считать например так:
Код

int HashCode(Node* node)
  int hash = node->hash;
  if (hash == 0)
    const char* s = node->key;
    while(*s)
      hash = hash * 31 + *s++;
    node->hash = hash;
  }
  return hash;  
}

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)