0

C で単純なリストを実装するのに問題があります。問題は、ポインターを介したアイテムの接続です。
次のコードはハッシュテーブルのスニペットであり、衝突を避けるために同じインデックスを持つアイテムをリストに格納することになっています。

typedef struct dictEntry {
    void *key;
    void *value;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictEntry **table;
    unsigned long size;
    unsigned long used;
} dict;

void dictAdd(dict *d, void *key, void *value) {
    int index = hash(key) & d->size;
    dictEntry *entry;

    entry = malloc(sizeof(entry));

    entry->key   = key;
    entry->value = value;
    entry->next  = 0;

    if (d->table[index]) {
        /* this is does not work */
        dictEntry *next;
        next = d->table[index];

        while (next) {
            next = next->next;
        }

        next = entry;
    } else {
        d->table[index] = entry;
        d->used++;
    }
}

私の考えでは、リスト ( ) のすべての要素を反復処理し、最後の要素 ( ) へのnext->nextポインターを割り当てます。 コードの一部を書き直して移動してから数日経っても、まだ解決策が見つからないようです。entrynext = entry;

4

3 に答える 3

5

リンクされたリストを最初に実装するようにしてください。

最後に追加を実装する方法は次のとおりです（リスト自体を変更せずに一時的な「次の」変数を上書きするコードを変更しました）：

if (d->table[index]) {
    /* this should work*/
    dictEntry *next;
    dictEntry *prev = NULL;
    next = d->table[index];

    while (next) {
        prev = next;
        next = next->next;
    }

    // yes, add new entry as the "next" pointer to the "last" item
    prev->next = entry;
} else {

....

于 2012-05-20T21:51:04.547 に答える
1 
entry = malloc(sizeof(entry));

次のようにする必要があります。

entry = malloc(sizeof *entry);

また、dictAdd は非常に複雑です。この場合、ポインターツーポインターを使用すると役立ちます。

void dictAdd(dict *d, void *key, void *value) {
    unsigned index;
    dictEntry **pp;

    index = hash(key) % d->size;
    if (!d->table[index]) d->used++;

    for (pp = &d->table[index]; *pp; pp = &(*pp)->next) {;}

    *pp = malloc(sizeof **pp);
     /* Omitted : handle ((*pp) == NULL) malloc failure here */
    (*pp)->key   = key;
    (*pp)->value = value;
    (*pp)->next  = NULL;
}
于 2012-05-20T22:16:55.080 に答える
0

while ループを見てください。ゼロになるまで行ってnextいますが、次のポインターがゼロである最後のエントリが本当に必要です。それを修正すると、より近くなるはずです。

于 2012-05-20T21:51:18.640 に答える