我要按以下方式实现哈希表:

struct list
{
 char *string;
 struct list *next;
};

struct hash_table
{
 int size;     /* the size of the table */
 struct list **table; /* the table elements */
};

我可以不使用上面这样的结构哈希表,而是使用:
struct hash_table
{
 int size;              /* the size of the table */
 struct list   *table; /* the table elements */
};

也就是说,对于哈希表元素,我可以使用单指针而不是双指针吗?如果是,请解释元素在表中存储方式的差异?

最佳答案

那要看情况了。如果你看一下表[我],你怎么知道它是空的还是不空的?如果使用list**,那么table[i]是list*类型,因此可以很容易地根据它是否为空来判断它是否为空。如果使用list*类型,那么table[i]是一个列表,因此除非对键使用null、empty或其他值作为指示列表为空的sentinel值,否则它将不起作用。所以,是的,您可以使用list*,但是您需要添加一个额外的sentinel条件,这也可能限制您允许的密钥类型或者,您可以忽略list[i]的第一个元素,但是这是浪费。我还应该指出,使用list*而不是list**会使在表[I]前面插入元素变得更加困难;如果使用list**类型,则只需将新项的下一个指针设置为表[I]的当前值,然后将新分配项的地址分配给表[I]。如果使用类型list*,则需要在表[i]和表[i]>next之间插入项,这使得插入的逻辑不必要地复杂。
另外,我还要补充一点,您的哈希表定义有缺陷。哈希表应该将一组项映射到另一组项。列表结构只有一个值。它需要一个键和一个值。更好的散列表声明如下:

typedef struct HashTableEntry
{
    char* key;
    void* value;
    struct HashTableEntry* next;
} HashTableEntry;

typedef struct HashTable
{
     HashTableEntry** entries;
     int capacity; // size of entries
     int length; // number of key/value pairs currently in map
} HashTable;

关于c - 我可以在C语言的哈希表中使用单个指针吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2849344/

10-11 23:22
查看更多