哈希表添加-C
Hashtable Add - C
在以下算法中出现段错误以将元素添加到哈希中的正确存储桶table。
我的结构很基础:
struct kv {
char* key;
unsigned val;
struct kv* next;
};
struct hashtable {
struct kv** table;
unsigned size;
};
还有我的越野车功能:
struct kv* ht_find_or_put(char* word, unsigned value,
struct hashtablet* hashtable,
unsigned (*hash)(char*))
{
unsigned index = hash(word) % hashtable->size;
struct kv* ke = malloc(sizeof (struct kv));
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
{
if (strcmp(ke->key, word) == 0)
return ke;
}
if (ke == NULL)
{
ke->key = word;
ke->val = value;
ke->next = hashtable->table[index];
hashtable->table[index] = ke;
}
return ke;
}
我知道我还没有添加所有测试(如果 malloc 失败等)只是试图调试这个特定问题...
我正在这样分配我的 table:
struct hashtable* hashtable_malloc(unsigned size)
{
struct hashtable *new_ht = malloc(sizeof(struct hashtable));
new_ht->size = size;
new_ht->table = malloc(sizeof(struct kv) * size);
for(unsigned i = 0; i < size; i++)
new_ht->table[i] = NULL;
return new_ht;
}
我们将不胜感激任何形式的帮助。我才刚刚开始学习。
第一个问题是内存泄漏,例如- 您使用 malloc 分配内存,但在覆盖指针时丢失了对它的引用:
// allocate memory
struct kv* ke = malloc(sizeof (struct kv));
// lose the reference
// VVVVVVVVVVV
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
可能导致段错误的第二个问题是您尝试取消引用空指针:
if (ke == NULL)
{
// ke is NULL, you can't de-reference it
ke->key = word;
ke->val = value;
ke->next = hashtable->table[index];
hashtable->table[index] = ke;
}
解决方案是,恕我直言,只有在找不到新元素时才分配和放置新元素:
struct kv* ht_find_or_put(char* word, unsigned value, struct hashtablet* hashtable, unsigned (*hash)(char*))
{
unsigned index = hash(word) % hashtable->size;
struct kv* ke;
// first we try to find the node
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
{
if (strcmp(ke->key, word) == 0)
return ke;
}
// didn't find it - lets create and put a new one.
if (ke == NULL)
{
ke = malloc(sizeof (struct kv));
// later add a check if the allocation succeded...
ke->key = word;
ke->val = value;
ke->next = hashtable->table[index];
hashtable->table[index] = ke;
}
return ke;
}
由于我不想引入全新的代码,那样只会让您感到困惑,所以我对原始代码进行了最少的更改。
在以下算法中出现段错误以将元素添加到哈希中的正确存储桶table。
我的结构很基础:
struct kv {
char* key;
unsigned val;
struct kv* next;
};
struct hashtable {
struct kv** table;
unsigned size;
};
还有我的越野车功能:
struct kv* ht_find_or_put(char* word, unsigned value,
struct hashtablet* hashtable,
unsigned (*hash)(char*))
{
unsigned index = hash(word) % hashtable->size;
struct kv* ke = malloc(sizeof (struct kv));
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
{
if (strcmp(ke->key, word) == 0)
return ke;
}
if (ke == NULL)
{
ke->key = word;
ke->val = value;
ke->next = hashtable->table[index];
hashtable->table[index] = ke;
}
return ke;
}
我知道我还没有添加所有测试(如果 malloc 失败等)只是试图调试这个特定问题...
我正在这样分配我的 table:
struct hashtable* hashtable_malloc(unsigned size)
{
struct hashtable *new_ht = malloc(sizeof(struct hashtable));
new_ht->size = size;
new_ht->table = malloc(sizeof(struct kv) * size);
for(unsigned i = 0; i < size; i++)
new_ht->table[i] = NULL;
return new_ht;
}
我们将不胜感激任何形式的帮助。我才刚刚开始学习。
第一个问题是内存泄漏,例如- 您使用 malloc 分配内存,但在覆盖指针时丢失了对它的引用:
// allocate memory
struct kv* ke = malloc(sizeof (struct kv));
// lose the reference
// VVVVVVVVVVV
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
可能导致段错误的第二个问题是您尝试取消引用空指针:
if (ke == NULL)
{
// ke is NULL, you can't de-reference it
ke->key = word;
ke->val = value;
ke->next = hashtable->table[index];
hashtable->table[index] = ke;
}
解决方案是,恕我直言,只有在找不到新元素时才分配和放置新元素:
struct kv* ht_find_or_put(char* word, unsigned value, struct hashtablet* hashtable, unsigned (*hash)(char*))
{
unsigned index = hash(word) % hashtable->size;
struct kv* ke;
// first we try to find the node
for (ke = hashtable->table[index]; ke != NULL; ke = ke->next)
{
if (strcmp(ke->key, word) == 0)
return ke;
}
// didn't find it - lets create and put a new one.
if (ke == NULL)
{
ke = malloc(sizeof (struct kv));
// later add a check if the allocation succeded...
ke->key = word;
ke->val = value;
ke->next = hashtable->table[index];
hashtable->table[index] = ke;
}
return ke;
}
由于我不想引入全新的代码,那样只会让您感到困惑,所以我对原始代码进行了最少的更改。