0

Cで単純なハッシュテーブルを作成しようとしていますが、表示されているコードでテストすると、非常に奇妙なセグメンテーション違反が発生しますmain()。

デザイン：サイズ10,000の基になる配列を持つハッシュテーブルがあります。struct node_t（またはnode）ポインターの配列の先頭へのダブルポインターを保持します。put()ハッシュテーブルに何かを入れたいときnodeは、適切な場所にある要素がであるかどうかを確認しNULLます。そうである場合は、スポットを埋めるために新しいノードを作成します。そうでない場合は、衝突がある場合は、衝突しているノードからリンクリストを作成します。

シナリオ：では、ハッシュテーブルに3328という番号main()を付けようとしています。put()代わりに、プログラムはsegfaultsします。put()前の例は正常に機能し、すべての初期ポインタをNULLに設定したことがはっきりとわかるので、これは私には意味がありません。私の知る限り、ハッシュテーブルの場所3328を参照するポインターは、put()関数で逆参照するとsegfaultが発生するため、NULLに設定されません。私のメイン関数は、すべてのポインタをNULLに設定する必要があるようですが...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int TABLE_SIZE = 10000;

typedef struct node_t {
    int key;
    int value;
    struct node_t* next;
} node;

node** table;

inline node** get_node_address(int key) {
    key = (key > -key ? key : -key) % TABLE_SIZE;
    return (node**) (table + key * sizeof(node*)); 
}

inline node* new_node(int key, int value) {
    node* n = malloc(sizeof(node));
    n->key = key;
    n->value = value;
    n->next = NULL;
    return n;
}

void put(int key, int value) {
    node** n = (node**) get_node_address(key);
    node* iterator = (node*) *n;

    if (*n == NULL) {
        *n = new_node(key, value);
    } else {
        while (iterator->next != NULL)
            iterator = iterator->next;

        iterator->next = new_node(key, value);
    }
}

int* get(int key) {
    node* iterator = (node*) *get_node_address(key);

    while (iterator != NULL && iterator->key != key) {
        iterator = iterator->next;
    }

    if (iterator == NULL)
        return NULL;
    else
        return &(iterator->value); 
}

int main() {
    printf("Starting..\n");

    int i;
    table = malloc(sizeof(node*) * TABLE_SIZE);
    memset(table, 0, sizeof(node*) * TABLE_SIZE);

    for (i = 0; i < TABLE_SIZE; i++) {
        table[i] = NULL;
        printf("setting %x\n", &table[i]);
    }

    printf("before bad: %x\n", *get_node_address(3327));
    printf("bad address: %x\n", *get_node_address(3328));
    printf("last address: %x\n", table + sizeof(node*) * TABLE_SIZE);

    printf("Hashing...\n");

    put(3328, 3338);
    printf("%d", *get(3328));

    return 0;
}
4

2 に答える 2

4

少なくとも1つの問題があります：

inline node** get_node_address(int key) {
      key = (key > -key ? key : -key) % TABLE_SIZE;
      return (node**) (table + key * sizeof(node*)); /* <---- */
}

掛けてはいけませんkey。ポインタ演算がCで機能する方法のため、 -番目の要素をtable + key生成します。key

于 2012-04-14T16:14:52.947 に答える
0

上記のコードは大幅に簡略化できます。

void put(int key, int value) {
  node **n = get_node_address(key);


  for (n = get_node_address(key); *n; n = &(*n)->next) {;}

  if(*n == NULL)
    *n = new_node(key, value);

}

int* get(int key) {
  node  **n;

  for (n = get_node_address(key); *n; n = &(*n)->next) {
    if (n->key == key) break;
    }

  if(*n == NULL)
    return NULL;
  else
    return &(*n)->value; 
}
于 2012-04-14T17:16:52.060 に答える