Wie können neue Daten dynamisch zu einem 2D-Array hinzugefügt werden?

Question

Ich möchte eine einfache Hash-Tabelle mit Verkettung Kollisions-Handling implementieren. 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)); 
    } 
} 

In dem obigen Beispiel habe ich mehrere Möglichkeiten ausprobiert zu speichern der neue Eintrag in der HashTable aber keiner von t Saum gearbeitet. Ich verstehe auch nicht, warum die Adressen identisch sind.

Ausgang:

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

Ich habe auch versucht entries[0][0] = newEntry;, weil ich dachte ht_entry** entries; ein 2D Array ist aber das hat nicht funktioniert entweder.

Also wie kann ich meine HashTable füllen?

Answer 1

Werfen wir einen Blick auf htable_insert. Zuerst erstellen Sie einen neuen Eintrag im Heap und behalten einen Zeiger darauf (newEntry). Dann stellst du deine key und deine data ein.

So weit so gut.

Nun dereferenzieren Sie entries und setzen Sie den Wert auf newEntry. Da entries ein Array von Zeigern auf Zeiger ist (2D ist nur ein schicker Name dafür), Dereferenzierung gibt Ihnen einen Zeiger auf ht_entry. Das bedeutet, dass Sie die struct newEntry Punkte nicht in das Array kopieren, sondern nur den Zeiger speichern. Dann fahren Sie fort, dies noch 3 mal zu tun, jedes zum nächstgrößeren Index. Am Ende werden die Einträge mit 4 Zeigern auf die gleiche Struktur gefüllt. Wenn Sie also die Adressen drucken, erhalten Sie immer die gleiche Adresse.