如何动态地将新数据添加到二维数组？

Question

我想使用链接冲突处理实现一个简单的散列 table。 main.c:

int main ()
{
    const int size = 20;
    const int key = 30;
    const int data = 40;

    htable ht;
    htable_init(&ht, size);
    htable_insert(&ht, key, data);
    htable_insert(&ht, key+1, 22);
    htable_insert(&ht, key+2, 23);
    htable_insert(&ht, key+2, 23);
    assert(htable_get(&ht, key) == data); // Expected: 40
    int d = htable_get(&ht, 415);
    assert(htable_delete(&ht, key) == data); // Expected: 40
    assert(htable_delete(&ht, key) == 0); // Expected: 0
    htable_destroy(&ht);

    // It is recommended to do further tests on your own

    return 0;
}

htable.h:

struct _ht_entry_ {
    int key;
    int data;
    struct _ht_entry_* next;
    struct _ht_entry_* prev;
};
typedef struct _ht_entry_ ht_entry;

struct _htable_ {
    ht_entry** entries;
    int size;
};

htable.c:

void htable_init(htable* ht, int initial_size)
{
    ht->entries = (ht_entry**) calloc(initial_size, sizeof(ht_entry*));
    if(ht->entries)
    {
        ht->size = initial_size;
    }
}

void htable_insert(htable* ht, int key, int data)
{
    ht_entry* newEntry = malloc(sizeof(ht_entry));
    if(!newEntry)
        return;

    newEntry->data = data;
    newEntry->key = key;
    newEntry->next = NULL;
    newEntry->prev = NULL;

    ht_entry** entries = ht->entries;
    *entries = newEntry;
    newEntry->data = 1;
    *(entries + 1) = newEntry;
    newEntry->data = 2;
    *(entries + 2) = newEntry;
    newEntry->data = 3;
    *(entries + 3) = newEntry;
    newEntry->data = 4;
    int i = 0;
    for ( i = 0; i < 3; i++ ) {
        ht_entry* entry = *(entries + i);
        printf("*(entries + %d) : %p\n",  i, *(entries + i) );
    }
}

在上面的示例中，我尝试了几种方法将新条目存储在 HashTable 中，但其中 none 有效。我也不明白为什么地址是一样的。

输出：

*(entries + 0) : data: 2  0x60003a410
*(entries + 1) : data: 2  0x60003a410
*(entries + 2) : data: 2  0x60003a410

我也尝试了 entries[0][0] = newEntry; 因为我认为 ht_entry** entries; 是 2D Array 但那也不起作用。

那么我该如何填写我的HashTable？

Answer 1

我们来看看htable_insert。首先，您在堆上创建一个新条目并保留一个指向它的指针（名为 newEntry）。然后设置 key 和 data。

到目前为止一切顺利。

现在您取消引用 entries 并将其值设置为 newEntry。由于 entries 是指向指针的指针数组（2D 只是一个奇特的名称），取消引用它会为您提供指向 ht_entry 的指针。这意味着您不会将指向的结构 newEntry 复制到数组中，而只是保存它的指针。然后你继续这样做 3 次，每次都在下一个更大的索引处。最后，entries 填充了 4 个指向相同结构的指针。因此，当你打印它的地址时，你总是得到相同的地址。

如何动态地将新数据添加到二维数组？

How to dynamically add new data to a 2D Array?

c

pointers

hashtable

multidimensional-array

dynamic-memory-allocation