段錯誤在簡單的哈希表

我想用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

段錯誤在簡單的哈希表

回答

相關問題