段错误在简单的哈希表

我想用C来写一个简单的哈希表，并表示我main()代码测试时，我得到一个非常奇怪的段错误。段错误在简单的哈希表

The Design：我有一个散列表，其底层数组大小为10,000。我持有指向struct node_t（或node）指针数组开头的双指针。当我想put()东西放到哈希表，我是否在适当的位置node元素是NULL。如果是这样，我创建一个新的节点来填补现场，否则，如果有碰撞，我建立一个链接列表的碰撞节点。

场景：在main()中，我试图将put()的数字3328放到哈希表中。相反，程序段错误。这对我来说没有意义，因为前面的put()工作正常，您可以清楚地看到我将所有初始指针设置为NULL。据我所知，这指的是哈希表的位置3328的指针不获取设置为NULL，因为当我取消对它的引用在put()功能，当它出现segfaults那。我的主要功能看起来应该设置所有的指针为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; 
}

来源

2012-04-14 Daniel

你尝试使用调试器来调试程序的？ – 2012-04-14 16:14:04

'key> = 0有什么问题？键：-key'？ – pmg 2012-04-14 16:19:46

有至少一个问题：

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-14 16:14:52 cnicutar

哇，我从来没有想过这件事。我改变了这一点，它完美无瑕！因此，在指针算术中，如果其中一个值不是指针本身，C会乘以指针的大小吗？ – Daniel 2012-04-14 16:26:16

@Daniel在指针运算中，它将乘以指向类型的大小。 – cnicutar 2012-04-14 16:27:07

语法'return＆table [key];'不太容易出错，并且可读性更高。 – wildplasser 2012-04-14 17:08:50

上面的代码可以简化很多：

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-14 17:16:52 wildplasser

段错误在简单的哈希表

回答

相关问题