时间戳

首页 > 解决方案 > 带有链表的哈希表在c中不起作用？

c - 带有链表的哈希表在c中不起作用？

问题描述

我在 C 中为带有链表（为了避免冲突）的哈希表分配内存有问题。

我认为问题在于项目的分配。我做了两个 scruct，一个用于单个项目，一个用于表。第一个有两个指向下一个和上一个项目的指针。请帮我。我一直使用此代码直到 3 天。编码 ：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define CAPACITY 50000 

unsigned long hash(char *str) { 
    unsigned long int stringsum = 0; 
    for(; *str != '\0'; str++) { 
        stringsum += *str; 
    } 
    return stringsum % CAPACITY; 
    
} 


typedef struct item  { 
    char *value; 
    char *key; 
    struct item *next; 
    struct item *prev; 
} ht_item; 

typedef struct hashtable { 
    ht_item **items; 
    int dim; 
    int count; 
} HashTable; 

HashTable* create_table(int size); HashTable* create_item(HashTable *table, char *value, char *key); 
void print_table(HashTable* table, int dim); 


int main(void) { 
    HashTable *table = create_table(CAPACITY); 
    table = create_item(table, "Giuseppe", "Nome"); 
    print_table(table, CAPACITY); 
    return 0; 
    
} 


HashTable* create_item(HashTable *table, char *value, char *key) { 
    unsigned long index = hash(key);
    printf("%u", index); 
    ht_item *_iterator; ht_item *prev;
    for(_iterator = table->items[index], prev = NULL; _iterator != NULL; prev = _iterator, _iterator = _iterator->next);
     _iterator = (ht_item*)malloc(sizeof(ht_item));
     _iterator->key = (char*)malloc(200);
     _iterator->value = (char*)malloc(200); 
     strcpy(_iterator->key, key);
     strcpy(_iterator->value, value);
     _iterator->next = NULL;
     _iterator->prev = prev; 
    return table; 
} 


HashTable* create_table(int size)
{ 
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->dim = size; 
    table->items = (ht_item**)calloc(size, sizeof(ht_item*)); 
    for(int i = 0; i < size; i++){ 
        table->items[i] = NULL; 
    } 
    
    return table; 
} 


void print_table(HashTable* table, int dim) { 
    for(int i = 0; i < CAPACITY; i++)
     { 
        if(table->items[i] != NULL)
         { ht_item *_iterator = (ht_item*)malloc(sizeof(ht_item));
             for(_iterator = table->items[i]; _iterator != NULL;
             _iterator = _iterator->next)
             { 
                printf("Key: %s\tValue: %s\n", _iterator->key, _iterator->value); 
                } free(_iterator); 
            } 
        } 
}

标签： cmemorylinked-listhashtable

解决方案

该create_item功能可以而且应该被简化。我已经在内联了一些评论。

HashTable* create_item(HashTable *table, char *value, char *key) { 
    // use modulo operator here, not in the hash function
    unsigned long index = hash(key) % table->dim;

    // nicer way of allocating
    ht_item *insert = malloc(sizeof *insert);

    // use strdup to avoid wasted memory and buffer overflows
    insert->key = strdup(key);
    insert->value = strdup(value);

    // head insert rather than tail
    insert->next = table->items[index];
    table->items[index] = insert;        

    return table; 
}

我放弃了prev会员的使用。如果您在某处需要它，那么添加它是一项练习。我认为简单的哈希表没有必要。

推荐阅读